Compactification: Remove spliced entries.

During garbage collection remove from the storage every entry that has the large entry.

6 files changed, 208 insertions, 1 deletions

diff --git a/src/buildtool/storage/TARGETS b/src/buildtool/storage/TARGETS
index ad846a85..d52d6402 100644
--- a/src/buildtool/storage/TARGETS
+++ b/src/buildtool/storage/TARGETS
@@ -33,9 +33,14 @@
     , "garbage_collector.hpp"
     , "large_object_cas.hpp"
     , "large_object_cas.tpp"
+    , "compactifier.hpp"
     ]
   , "srcs":
-    ["target_cache_key.cpp", "target_cache_entry.cpp", "garbage_collector.cpp"]
+    [ "target_cache_key.cpp"
+    , "target_cache_entry.cpp"
+    , "garbage_collector.cpp"
+    , "compactifier.cpp"
+    ]
   , "deps":
     [ "config"
     , "file_chunker"
diff --git a/src/buildtool/storage/compactifier.cpp b/src/buildtool/storage/compactifier.cpp
new file mode 100644
index 00000000..01c5c7a6
--- /dev/null
+++ b/src/buildtool/storage/compactifier.cpp
@@ -0,0 +1,85 @@
+// Copyright 2024 Huawei Cloud Computing Technology Co., Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "src/buildtool/storage/compactifier.hpp"
+
+#include <algorithm>
+#include <array>
+#include <filesystem>
+
+#include "src/buildtool/file_system/file_system_manager.hpp"
+#include "src/buildtool/file_system/object_type.hpp"
+#include "src/buildtool/storage/local_cas.hpp"
+
+namespace {
+/// \brief Remove spliced entries from the kType storage.
+/// \tparam kType         Type of the storage to inspect.
+/// \param cas            Storage to be inspected.
+/// \return               True if the kType storage doesn't contain spliced
+/// entries.
+template <ObjectType... kType>
+requires(sizeof...(kType) != 0)
+    [[nodiscard]] auto RemoveSpliced(LocalCAS<false> const& cas) noexcept
+    -> bool;
+}  // namespace
+
+auto Compactifier::RemoveSpliced(LocalCAS<false> const& cas) noexcept -> bool {
+    return ::RemoveSpliced<ObjectType::Tree>(cas) and
+           ::RemoveSpliced<ObjectType::File, ObjectType::Executable>(cas);
+}
+
+namespace {
+template <ObjectType... kType>
+requires(sizeof...(kType) != 0)
+    [[nodiscard]] auto RemoveSpliced(LocalCAS<false> const& cas) noexcept
+    -> bool {
+    // Obtain path to the large CAS:
+    static constexpr std::array types{kType...};
+    auto const& large_storage = cas.StorageRoot(types[0], /*large=*/true);
+
+    // Check there are entries to process:
+    if (not FileSystemManager::IsDirectory(large_storage)) {
+        return true;
+    }
+
+    // Obtain paths to object storages.
+    std::array const storage_roots{cas.StorageRoot(kType)...};
+
+    FileSystemManager::UseDirEntryFunc callback =
+        [&storage_roots](std::filesystem::path const& entry_large,
+                         bool is_tree) -> bool {
+        // Use all folders.
+        if (is_tree) {
+            return true;
+        }
+
+        // Pathes to large entries and spliced results are:
+        // large_storage / entry_large
+        //       storage / entry_object
+        //
+        // Large objects are keyed by the hash of their spliced result, so for
+        // splicable objects large_entry and object_entry are the same.
+        // Thus, to check the existence of the spliced result, it is
+        // enough to check the existence of { storage / entry_large }:
+        auto check = [&entry_large](std::filesystem::path const& storage) {
+            std::filesystem::path file_path = storage / entry_large;
+            return not FileSystemManager::IsFile(file_path) or
+                   FileSystemManager::RemoveFile(file_path);
+        };
+        return std::all_of(storage_roots.begin(), storage_roots.end(), check);
+    };
+    return FileSystemManager::ReadDirectoryEntriesRecursive(large_storage,
+                                                            callback);
+}
+}  // namespace
diff --git a/src/buildtool/storage/compactifier.hpp b/src/buildtool/storage/compactifier.hpp
new file mode 100644
index 00000000..ced458fe
--- /dev/null
+++ b/src/buildtool/storage/compactifier.hpp
@@ -0,0 +1,31 @@
+// Copyright 2024 Huawei Cloud Computing Technology Co., Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef INCLUDED_SRC_BUILDTOOL_STORAGE_COMPACTIFIER_HPP
+#define INCLUDED_SRC_BUILDTOOL_STORAGE_COMPACTIFIER_HPP
+
+template <bool>
+class LocalCAS;
+
+class Compactifier final {
+  public:
+    /// \brief Remove spliced entries from the storage.
+    /// \param local_cas      Storage to be inspected.
+    /// \return               True if object storages do not contain spliced
+    /// entries.
+    [[nodiscard]] static auto RemoveSpliced(LocalCAS<false> const& cas) noexcept
+        -> bool;
+};
+
+#endif  // INCLUDED_SRC_BUILDTOOL_STORAGE_COMPACTIFIER_HPP
diff --git a/src/buildtool/storage/garbage_collector.cpp b/src/buildtool/storage/garbage_collector.cpp
index 7c5f9db2..1b7dc09b 100644
--- a/src/buildtool/storage/garbage_collector.cpp
+++ b/src/buildtool/storage/garbage_collector.cpp
@@ -18,6 +18,7 @@
 
 #include <cstddef>
 #include <filesystem>
+#include <memory>
 #include <vector>
 
 #include "nlohmann/json.hpp"
@@ -31,6 +32,7 @@
 #include "src/buildtool/file_system/object_type.hpp"
 #include "src/buildtool/logging/log_level.hpp"
 #include "src/buildtool/logging/logger.hpp"
+#include "src/buildtool/storage/compactifier.hpp"
 #include "src/buildtool/storage/config.hpp"
 #include "src/buildtool/storage/storage.hpp"
 #include "src/buildtool/storage/target_cache_entry.hpp"
@@ -236,6 +238,16 @@ auto GarbageCollector::TriggerGarbageCollection(bool no_rotation) noexcept
                             remove_me_dir.string());
             }
         }
+
+        // Compactification must take place before rotating generations.
+        // Otherwise, an interruption of the process during compactification
+        // would lead to an invalid old generation.
+        if (not GarbageCollector::Compactify()) {
+            Logger::Log(LogLevel::Error,
+                        "Failed to compactify the youngest generation.");
+            return false;
+        }
+
         // Rotate generations unless told not to do so
         if (not no_rotation) {
             auto remove_me_dir =
@@ -278,4 +290,23 @@ auto GarbageCollector::TriggerGarbageCollection(bool no_rotation) noexcept
     return success;
 }
 
+auto GarbageCollector::Compactify() noexcept -> bool {
+    const bool mode = Compatibility::IsCompatible();
+
+    // Return to the initial compatibility mode once done:
+    auto scope_guard = std::shared_ptr<void>(nullptr, [mode](void* /*unused*/) {
+        Compatibility::SetCompatible(mode);
+    });
+
+    // Compactification must be done for both native and compatible storages.
+    auto compactify = [](bool compatible) -> bool {
+        auto const storage =
+            ::Generation(StorageConfig::GenerationCacheDir(0, compatible));
+        Compatibility::SetCompatible(compatible);
+
+        return Compactifier::RemoveSpliced(storage.CAS());
+    };
+    return compactify(mode) and compactify(not mode);
+}
+
 #endif  // BOOTSTRAP_BUILD_TOOL
diff --git a/src/buildtool/storage/garbage_collector.hpp b/src/buildtool/storage/garbage_collector.hpp
index 28a5f08b..6bca3f3c 100644
--- a/src/buildtool/storage/garbage_collector.hpp
+++ b/src/buildtool/storage/garbage_collector.hpp
@@ -89,6 +89,11 @@ class GarbageCollector {
         -> std::optional<LockFile>;
 
     [[nodiscard]] auto static LockFilePath() noexcept -> std::filesystem::path;
+
+    /// \brief Remove spliced objects from the youngest generation.
+    /// \return True if the youngest generation does not contain spliced
+    /// objects afterwards.
+    [[nodiscard]] auto static Compactify() noexcept -> bool;
 };
 
 #endif  // INCLUDED_SRC_BUILDTOOL_STORAGE_GARBAGE_COLLECTOR_HPP
diff --git a/test/buildtool/storage/large_object_cas.test.cpp b/test/buildtool/storage/large_object_cas.test.cpp
index da348727..fe3b8e6d 100644
--- a/test/buildtool/storage/large_object_cas.test.cpp
+++ b/test/buildtool/storage/large_object_cas.test.cpp
@@ -31,6 +31,7 @@
 #include "src/buildtool/file_system/file_system_manager.hpp"
 #include "src/buildtool/file_system/object_type.hpp"
 #include "src/buildtool/storage/config.hpp"
+#include "src/buildtool/storage/garbage_collector.hpp"
 #include "src/buildtool/storage/large_object_cas.hpp"
 #include "src/buildtool/storage/storage.hpp"
 #include "src/utils/cpp/tmp_dir.hpp"
@@ -421,6 +422,52 @@ static void TestExternal() noexcept {
     }
 }
 
+// Test compactification of a storage generation.
+// If there are objects in the storage that have an entry in
+// the large CAS, they must be deleted during compactification.
+template <ObjectType kType>
+static void TestCompactification() {
+    SECTION("Compactify") {
+        static constexpr bool kIsTree = IsTreeObject(kType);
+        static constexpr bool kIsExec = IsExecutableObject(kType);
+
+        using TestType = std::conditional_t<kIsTree,
+                                            LargeTestUtils::Tree,
+                                            LargeTestUtils::Blob<kIsExec>>;
+
+        auto const& cas = Storage::Instance().CAS();
+
+        // Create a large object and split it:
+        auto object = TestType::Create(
+            cas, std::string(TestType::kLargeId), TestType::kLargeSize);
+        REQUIRE(object);
+        auto& [digest, path] = *object;
+        auto result = kIsTree ? cas.SplitTree(digest) : cas.SplitBlob(digest);
+        REQUIRE(std::get_if<std::vector<bazel_re::Digest>>(&result) != nullptr);
+
+        // Ensure all entries are in the storage:
+        auto get_path = [](auto const& cas, bazel_re::Digest const& digest) {
+            return kIsTree ? cas.TreePath(digest)
+                           : cas.BlobPath(digest, kIsExec);
+        };
+
+        auto const& latest = Storage::Generation(0).CAS();
+        REQUIRE(get_path(latest, digest).has_value());
+
+        // Compactify the youngest generation:
+        // Generation rotation is disabled to exclude uplinking.
+        static constexpr bool no_rotation = true;
+        REQUIRE(GarbageCollector::TriggerGarbageCollection(no_rotation));
+
+        // All entries must be deleted during compactification, and for blobs
+        // and executables there are no synchronized entries in the storage:
+        REQUIRE_FALSE(get_path(latest, digest).has_value());
+
+        // All entries must be implicitly splicable:
+        REQUIRE(get_path(cas, digest).has_value());
+    }
+}
+
 TEST_CASE_METHOD(HermeticLocalTestFixture,
                  "LocalCAS: Split-Splice",
                  "[storage]") {
@@ -429,18 +476,21 @@ TEST_CASE_METHOD(HermeticLocalTestFixture,
         TestSmall<ObjectType::File>();
         TestEmpty<ObjectType::File>();
         TestExternal<ObjectType::File>();
+        TestCompactification<ObjectType::File>();
     }
     SECTION("Tree") {
         TestLarge<ObjectType::Tree>();
         TestSmall<ObjectType::Tree>();
         TestEmpty<ObjectType::Tree>();
         TestExternal<ObjectType::Tree>();
+        TestCompactification<ObjectType::Tree>();
     }
     SECTION("Executable") {
         TestLarge<ObjectType::Executable>();
         TestSmall<ObjectType::Executable>();
         TestEmpty<ObjectType::Executable>();
         TestExternal<ObjectType::Executable>();
+        TestCompactification<ObjectType::Executable>();
     }
 }