Merge pull request #24377 from vespa-engine/geirst/generic-generation-hold-list

Implement a generic hold list for data elements associated with a gen…

7 files changed, 211 insertions, 10 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index b84a90465ea..532ec870ce9 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -181,9 +181,10 @@ vespa_define_module(
     src/tests/util/bfloat16
     src/tests/util/cgroup_resource_limits
     src/tests/util/file_area_freelist
+    src/tests/util/generation_hold_list
+    src/tests/util/generation_holder
     src/tests/util/generationhandler
     src/tests/util/generationhandler_stress
-    src/tests/util/generation_holder
     src/tests/util/hamming
     src/tests/util/md5
     src/tests/util/mmap_file_allocator
diff --git a/vespalib/src/tests/util/generation_hold_list/CMakeLists.txt b/vespalib/src/tests/util/generation_hold_list/CMakeLists.txt
new file mode 100644
index 00000000000..c85b2537745
--- /dev/null
+++ b/vespalib/src/tests/util/generation_hold_list/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_generation_hold_list_test_app TEST
+    SOURCES
+    generation_hold_list_test.cpp
+    DEPENDS
+    vespalib
+    GTest::GTest
+)
+vespa_add_test(NAME vespalib_generation_hold_list_test_app COMMAND vespalib_generation_hold_list_test_app)
diff --git a/vespalib/src/tests/util/generation_hold_list/generation_hold_list_test.cpp b/vespalib/src/tests/util/generation_hold_list/generation_hold_list_test.cpp
new file mode 100644
index 00000000000..0490a99f1e0
--- /dev/null
+++ b/vespalib/src/tests/util/generation_hold_list/generation_hold_list_test.cpp
@@ -0,0 +1,45 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/gtest/gtest.h>
+#include <vespa/vespalib/util/generation_hold_list.hpp>
+#include <vespa/vespalib/util/generationholder.h>
+
+using vespalib::GenerationHeldBase;
+using vespalib::GenerationHoldList;
+
+using MyElem = GenerationHeldBase;
+using MyHoldList = GenerationHoldList<MyElem::UP, true>;
+
+TEST(GenerationHoldListTest, holding_of_unique_ptr_elements_with_tracking_of_held_bytes)
+{
+    MyHoldList h;
+    h.insert(std::make_unique<MyElem>(3));
+    h.assign_generation(0);
+    h.insert(std::make_unique<MyElem>(5));
+    h.assign_generation(1);
+    h.insert(std::make_unique<MyElem>(7));
+    h.assign_generation(2);
+    h.insert(std::make_unique<MyElem>(11));
+    h.assign_generation(4);
+    EXPECT_EQ(3 + 5 + 7 + 11, h.get_held_bytes());
+
+    h.reclaim(0);
+    EXPECT_EQ(3 + 5 + 7 + 11, h.get_held_bytes());
+    h.reclaim(1);
+    EXPECT_EQ(5 + 7 + 11, h.get_held_bytes());
+    h.reclaim(2);
+    EXPECT_EQ(7 + 11, h.get_held_bytes());
+
+    h.insert(std::make_unique<MyElem>(13));
+    h.assign_generation(6);
+    EXPECT_EQ(7 + 11 + 13, h.get_held_bytes());
+
+    h.reclaim(6);
+    EXPECT_EQ(13, h.get_held_bytes());
+    h.reclaim(7);
+    EXPECT_EQ(0, h.get_held_bytes());
+    h.reclaim(7);
+    EXPECT_EQ(0, h.get_held_bytes());
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/util/generation_hold_list.h b/vespalib/src/vespa/vespalib/util/generation_hold_list.h
new file mode 100644
index 00000000000..5e12cb72bbd
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/generation_hold_list.h
@@ -0,0 +1,83 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "generationhandler.h"
+#include <atomic>
+#include <deque>
+#include <vector>
+
+namespace vespalib {
+
+/**
+ * Class used to hold data elements until they can be safely reclaimed when they are no longer accessed by readers.
+ *
+ * This class must be used in accordance with a GenerationHandler.
+ */
+template <typename T, bool track_bytes_held>
+class GenerationHoldList {
+private:
+    using generation_t = vespalib::GenerationHandler::generation_t;
+
+    struct ElemWithGen {
+        T elem;
+        generation_t gen;
+        ElemWithGen(T elem_in, generation_t gen_in)
+            : elem(std::move(elem_in)),
+              gen(gen_in)
+        {}
+        size_t byte_size() const { return elem->byte_size(); }
+    };
+
+    using ElemList = std::vector<T>;
+    using ElemWithGenList = std::deque<ElemWithGen>;
+
+    ElemList _phase_1_list;
+    ElemWithGenList _phase_2_list;
+    std::atomic<size_t> _held_bytes;
+
+    /**
+     * Transfer elements from phase 1 to phase 2 list, assigning the current generation.
+     */
+    void assign_generation_internal(generation_t current_gen);
+
+    void reclaim_internal(generation_t oldest_used_gen);
+
+
+public:
+    GenerationHoldList();
+
+    /**
+     * Insert the given data element on this hold list.
+     */
+    void insert(T data);
+
+    /**
+     * Assign the current generation to all data elements inserted on the hold list
+     * since the last time this function was called.
+     */
+    void assign_generation(generation_t current_gen) {
+        if (!_phase_1_list.empty()) {
+            assign_generation_internal(current_gen);
+        }
+    }
+
+    /**
+     * Reclaim all data elements where the assigned generation < oldest used generation.
+     **/
+    void reclaim(generation_t oldest_used_gen) {
+        if (!_phase_2_list.empty() && (_phase_2_list.front().gen < oldest_used_gen)) {
+            reclaim_internal(oldest_used_gen);
+        }
+    }
+
+    /**
+     * Reclaim all data elements from this hold list.
+     */
+    void reclaim_all();
+
+    size_t get_held_bytes() const { return _held_bytes.load(std::memory_order_relaxed); }
+
+};
+
+}
diff --git a/vespalib/src/vespa/vespalib/util/generation_hold_list.hpp b/vespalib/src/vespa/vespalib/util/generation_hold_list.hpp
new file mode 100644
index 00000000000..e7eee2b0aef
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/generation_hold_list.hpp
@@ -0,0 +1,63 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "generation_hold_list.h"
+
+namespace vespalib {
+
+template <typename T, bool track_bytes_held>
+void
+GenerationHoldList<T, track_bytes_held>::assign_generation_internal(generation_t current_gen)
+{
+    for (auto& elem : _phase_1_list) {
+        _phase_2_list.push_back(ElemWithGen(std::move(elem), current_gen));
+    }
+    _phase_1_list.clear();
+}
+
+template <typename T, bool track_bytes_held>
+void
+GenerationHoldList<T, track_bytes_held>::reclaim_internal(generation_t oldest_used_gen)
+{
+    auto itr = _phase_2_list.begin();
+    auto ite = _phase_2_list.end();
+    for (; itr != ite; ++itr) {
+        if (itr->gen >= oldest_used_gen) {
+            break;
+        }
+        if (track_bytes_held) {
+            _held_bytes.store(get_held_bytes() - itr->byte_size(), std::memory_order_relaxed);
+        }
+    }
+    if (itr != _phase_2_list.begin()) {
+        _phase_2_list.erase(_phase_2_list.begin(), itr);
+    }
+}
+
+template <typename T, bool track_bytes_held>
+GenerationHoldList<T, track_bytes_held>::GenerationHoldList()
+    : _phase_1_list(),
+      _phase_2_list(),
+      _held_bytes()
+{
+}
+
+template <typename T, bool track_bytes_held>
+void
+GenerationHoldList<T, track_bytes_held>::insert(T data)
+{
+    _phase_1_list.push_back(std::move(data));
+    if (track_bytes_held) {
+        _held_bytes.store(get_held_bytes() + _phase_1_list.back()->byte_size(), std::memory_order_relaxed);
+    }
+}
+
+template <typename T, bool track_bytes_held>
+void
+GenerationHoldList<T, track_bytes_held>::reclaim_all()
+{
+    _phase_1_list.clear();
+    _phase_2_list.clear();
+    _held_bytes = 0;
+}
+
+}
diff --git a/vespalib/src/vespa/vespalib/util/generationholder.cpp b/vespalib/src/vespa/vespalib/util/generationholder.cpp
index 5bfa7d152ce..f2b10ff3af1 100644
--- a/vespalib/src/vespa/vespalib/util/generationholder.cpp
+++ b/vespalib/src/vespa/vespalib/util/generationholder.cpp
@@ -23,8 +23,8 @@ GenerationHolder::~GenerationHolder()
 void
 GenerationHolder::hold(GenerationHeldBase::UP data)
 {
-    _hold1List.push_back(GenerationHeldBase::SP(data.release()));
-    _heldBytes.store(getHeldBytes() + _hold1List.back()->getSize(), std::memory_order_relaxed);
+    _hold1List.push_back(std::move(data));
+    _heldBytes.store(getHeldBytes() + _hold1List.back()->byte_size(), std::memory_order_relaxed);
 }
 
 void
@@ -36,7 +36,7 @@ GenerationHolder::transferHoldListsSlow(generation_t generation)
     for (; it != ite; ++it) {
         assert((*it)->_generation == 0u);
         (*it)->_generation = generation;
-        hold2List.push_back(*it);
+        hold2List.push_back(std::move(*it));
     }
     _hold1List.clear();
 }
@@ -50,7 +50,7 @@ GenerationHolder::trimHoldListsSlow(generation_t usedGen)
         GenerationHeldBase &first = *_hold2List.front();
         if (static_cast<sgeneration_t>(first._generation - usedGen) >= 0)
             break;
-        _heldBytes.store(getHeldBytes() - first.getSize(), std::memory_order_relaxed);
+        _heldBytes.store(getHeldBytes() - first.byte_size(), std::memory_order_relaxed);
         _hold2List.erase(_hold2List.begin());
     }
 }
diff --git a/vespalib/src/vespa/vespalib/util/generationholder.h b/vespalib/src/vespa/vespalib/util/generationholder.h
index ed68a80a308..df44f39ebff 100644
--- a/vespalib/src/vespa/vespalib/util/generationholder.h
+++ b/vespalib/src/vespa/vespalib/util/generationholder.h
@@ -17,16 +17,16 @@ public:
 
     generation_t _generation;
 private:
-    size_t	 _size;
+    size_t	 _byte_size;
 
 public:
-    GenerationHeldBase(size_t size)
+    GenerationHeldBase(size_t byte_size_in)
         : _generation(0u),
-          _size(size)
+          _byte_size(byte_size_in)
     { }
 
     virtual ~GenerationHeldBase();
-    size_t getSize() const { return _size; }
+    size_t byte_size() const { return _byte_size; }
 };
 
 /*
@@ -39,7 +39,7 @@ private:
     typedef GenerationHandler::generation_t generation_t;
     typedef GenerationHandler::sgeneration_t sgeneration_t;
 
-    typedef std::vector<GenerationHeldBase::SP> HoldList;
+    typedef std::vector<GenerationHeldBase::UP> HoldList;
 
     HoldList _hold1List;
     HoldList _hold2List;