diff options
author | Geir Storli <geirst@yahooinc.com> | 2022-10-10 12:52:56 +0000 |
---|---|---|
committer | Geir Storli <geirst@yahooinc.com> | 2022-10-10 13:08:59 +0000 |
commit | 846907b511ccf4f2ecdc4d2b12273e6287c08575 (patch) | |
tree | fc7f9b92e1b114b3e20d7badc10bee8aecc4bf0f /vespalib | |
parent | 240a62de8a9b3c93fb9f7031f5e204264d414817 (diff) |
Implement a generic hold list for data elements associated with a generation.
Diffstat (limited to 'vespalib')
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; |