diff options
author | Geir Storli <geirst@yahooinc.com> | 2022-10-05 14:08:11 +0000 |
---|---|---|
committer | Geir Storli <geirst@yahooinc.com> | 2022-10-05 14:08:11 +0000 |
commit | 31ac12e49fcf843d3a56f20b430dbacd3b12beb6 (patch) | |
tree | b3a7927a1cb289fc7665ecbcf610893c3cb1b735 | |
parent | 0e7eaa58bcf3d2ffa4bfdc222f0c595ec0e438ff (diff) |
Use datastore free list handling with a simpler API.
13 files changed, 70 insertions, 192 deletions
diff --git a/vespalib/src/tests/datastore/datastore/datastore_test.cpp b/vespalib/src/tests/datastore/datastore/datastore_test.cpp index b77599c4e34..9522aa1e0dc 100644 --- a/vespalib/src/tests/datastore/datastore/datastore_test.cpp +++ b/vespalib/src/tests/datastore/datastore/datastore_test.cpp @@ -670,7 +670,8 @@ TEST(DataStoreTest, can_reuse_active_buffer_as_primary_buffer) TEST(DataStoreTest, control_static_sizes) { EXPECT_EQ(96, sizeof(BufferTypeBase)); - EXPECT_EQ(32, sizeof(BufferState::FreeList)); + EXPECT_EQ(24, sizeof(FreeList)); + EXPECT_EQ(56, sizeof(BufferFreeList)); EXPECT_EQ(1, sizeof(BufferState::State)); EXPECT_EQ(144, sizeof(BufferState)); BufferState bs; diff --git a/vespalib/src/tests/datastore/free_list/free_list_test.cpp b/vespalib/src/tests/datastore/free_list/free_list_test.cpp index d80020d3dc5..44e11b2316b 100644 --- a/vespalib/src/tests/datastore/free_list/free_list_test.cpp +++ b/vespalib/src/tests/datastore/free_list/free_list_test.cpp @@ -21,7 +21,7 @@ struct FreeListTest : public testing::Test { for (size_t i = 0; i < 3; ++i) { bufs.emplace_back(dead_elems); - bufs.back().on_active(array_size); + bufs.back().set_array_size(array_size); } } void TearDown() override { @@ -114,6 +114,18 @@ TEST_F(FreeListTest, buffer_free_lists_are_reused_in_lifo_order) EXPECT_TRUE(list.empty()); } +TEST_F(FreeListTest, buffer_free_list_can_be_disabled_and_detached_when_not_currently_reused) +{ + enable_all(); + push_entry({10, 0}); + push_entry({20, 1}); + EXPECT_EQ(2, list.size()); + bufs[0].disable(); + EXPECT_EQ(1, list.size()); + EXPECT_EQ(MyEntryRef(20, 1), pop_entry()); + EXPECT_TRUE(list.empty()); +} + TEST_F(FreeListTest, dead_elems_count_is_updated_when_popping_an_entry) { enable(0); diff --git a/vespalib/src/tests/datastore/unique_store_string_allocator/unique_store_string_allocator_test.cpp b/vespalib/src/tests/datastore/unique_store_string_allocator/unique_store_string_allocator_test.cpp index 21330c22166..777da0c2b16 100644 --- a/vespalib/src/tests/datastore/unique_store_string_allocator/unique_store_string_allocator_test.cpp +++ b/vespalib/src/tests/datastore/unique_store_string_allocator/unique_store_string_allocator_test.cpp @@ -129,7 +129,7 @@ TEST_F(StringTest, string_length_determines_buffer) TEST_F(StringTest, free_list_is_used_when_enabled) { - allocator.get_data_store().enableFreeLists(); + // Free lists are default enabled for UniqueStoreStringAllocator EntryRef ref1 = add(small.c_str()); EntryRef ref2 = add(spaces1000.c_str()); remove(ref1); @@ -161,7 +161,7 @@ TEST_F(StringTest, free_list_is_not_used_when_disabled) TEST_F(StringTest, free_list_is_never_used_for_move) { - allocator.get_data_store().enableFreeLists(); + // Free lists are default enabled for UniqueStoreStringAllocator EntryRef ref1 = add(small.c_str()); EntryRef ref2 = add(spaces1000.c_str()); EntryRef ref3 = add(small.c_str()); diff --git a/vespalib/src/vespa/vespalib/datastore/buffer_free_list.h b/vespalib/src/vespa/vespalib/datastore/buffer_free_list.h index 9ad24f7f03e..74fd47056de 100644 --- a/vespalib/src/vespa/vespalib/datastore/buffer_free_list.h +++ b/vespalib/src/vespa/vespalib/datastore/buffer_free_list.h @@ -30,12 +30,17 @@ private: public: BufferFreeList(std::atomic<ElemCount>& dead_elems); ~BufferFreeList(); + BufferFreeList(BufferFreeList&&) = default; // Needed for emplace_back() during setup. + BufferFreeList(const BufferFreeList&) = delete; + BufferFreeList& operator=(const BufferFreeList&) = delete; + BufferFreeList& operator=(BufferFreeList&&) = delete; void enable(FreeList& free_list); void disable(); - void on_active(uint32_t array_size) { _array_size = array_size; } + void set_array_size(uint32_t value) { _array_size = value; } bool enabled() const { return _free_list != nullptr; } bool empty() const { return _free_refs.empty(); } + uint32_t array_size() const { return _array_size; } void push_entry(EntryRef ref) { if (empty()) { attach(); diff --git a/vespalib/src/vespa/vespalib/datastore/bufferstate.cpp b/vespalib/src/vespa/vespalib/datastore/bufferstate.cpp index cde891b477d..d24d8336131 100644 --- a/vespalib/src/vespa/vespalib/datastore/bufferstate.cpp +++ b/vespalib/src/vespa/vespalib/datastore/bufferstate.cpp @@ -10,11 +10,6 @@ using vespalib::alloc::MemoryAllocator; namespace vespalib::datastore { -BufferState::FreeListList::~FreeListList() -{ - assert(_head == nullptr); // Owner should have disabled free lists -} - BufferState::BufferState() : _usedElems(0), _allocElems(0), @@ -22,10 +17,7 @@ BufferState::BufferState() _holdElems(0u), _extraUsedBytes(0), _extraHoldBytes(0), - _freeList(), - _freeListList(nullptr), - _nextHasFree(nullptr), - _prevHasFree(nullptr), + _free_list(_deadElems), _typeHandler(nullptr), _buffer(Alloc::alloc(0, MemoryAllocator::HUGEPAGE_SIZE)), _arraySize(0), @@ -39,11 +31,9 @@ BufferState::BufferState() BufferState::~BufferState() { assert(getState() == State::FREE); - assert(_freeListList == nullptr); - assert(_nextHasFree == nullptr); - assert(_prevHasFree == nullptr); + assert(!_free_list.enabled()); + assert(_free_list.empty()); assert(_holdElems == 0); - assert(isFreeListEmpty()); } void @@ -114,10 +104,7 @@ BufferState::onActive(uint32_t bufferId, uint32_t typeId, assert(getHoldElems() == 0); assert(getExtraUsedBytes() == 0); assert(getExtraHoldBytes() == 0); - assert(isFreeListEmpty()); - assert(_nextHasFree == nullptr); - assert(_prevHasFree == nullptr); - assert(_freeListList == nullptr || _freeListList->_head != this); + assert(_free_list.empty()); size_t reservedElements = typeHandler->getReservedElements(bufferId); (void) reservedElements; @@ -133,11 +120,11 @@ BufferState::onActive(uint32_t bufferId, uint32_t typeId, assert(typeId <= std::numeric_limits<uint16_t>::max()); _typeId = typeId; _arraySize = typeHandler->getArraySize(); + _free_list.set_array_size(_arraySize); _state.store(State::ACTIVE, std::memory_order_release); typeHandler->onActive(bufferId, &_usedElems, &_deadElems, buffer.load(std::memory_order::relaxed)); } - void BufferState::onHold(uint32_t buffer_id) { @@ -150,17 +137,9 @@ BufferState::onHold(uint32_t buffer_id) _deadElems.store(0, std::memory_order_relaxed); _holdElems.store(size(), std::memory_order_relaxed); // Put everyting on hold getTypeHandler()->onHold(buffer_id, &_usedElems, &_deadElems); - if ( ! isFreeListEmpty()) { - removeFromFreeListList(); - FreeList().swap(_freeList); - } - assert(_nextHasFree == nullptr); - assert(_prevHasFree == nullptr); - assert(_freeListList == nullptr || _freeListList->_head != this); - setFreeListList(nullptr); + _free_list.disable(); } - void BufferState::onFree(std::atomic<void*>& buffer) { @@ -182,11 +161,9 @@ BufferState::onFree(std::atomic<void*>& buffer) _state.store(State::FREE, std::memory_order_release); _typeHandler = nullptr; _arraySize = 0; - assert(isFreeListEmpty()); - assert(_nextHasFree == nullptr); - assert(_prevHasFree == nullptr); - assert(_freeListList == nullptr || _freeListList->_head != this); - setFreeListList(nullptr); + _free_list.set_array_size(_arraySize); + assert(!_free_list.enabled()); + assert(_free_list.empty()); _disableElemHoldList = false; } @@ -209,70 +186,6 @@ BufferState::dropBuffer(uint32_t buffer_id, std::atomic<void*>& buffer) assert(buffer.load(std::memory_order_relaxed) == nullptr); } - -void -BufferState::setFreeListList(FreeListList *freeListList) -{ - if (getState() == State::FREE && freeListList != nullptr) { - return; - } - if (freeListList == _freeListList) { - return; // No change - } - if (_freeListList != nullptr && ! isFreeListEmpty()) { - removeFromFreeListList(); // Remove from old free list - } - _freeListList = freeListList; - if ( ! isFreeListEmpty() ) { - if (freeListList != nullptr) { - addToFreeListList(); // Changed free list list - } else { - FreeList().swap(_freeList);; // Free lists have been disabled - } - } -} - - -void -BufferState::addToFreeListList() -{ - assert(_freeListList != nullptr && _freeListList->_head != this); - assert(_nextHasFree == nullptr); - assert(_prevHasFree == nullptr); - if (_freeListList->_head != nullptr) { - _nextHasFree = _freeListList->_head; - _prevHasFree = _nextHasFree->_prevHasFree; - _nextHasFree->_prevHasFree = this; - _prevHasFree->_nextHasFree = this; - } else { - _nextHasFree = this; - _prevHasFree = this; - } - _freeListList->_head = this; -} - - -void -BufferState::removeFromFreeListList() -{ - assert(_freeListList != nullptr); - assert(_nextHasFree != nullptr); - assert(_prevHasFree != nullptr); - if (_nextHasFree == this) { - assert(_prevHasFree == this); - assert(_freeListList->_head == this); - _freeListList->_head = nullptr; - } else { - assert(_prevHasFree != this); - _freeListList->_head = _nextHasFree; - _nextHasFree->_prevHasFree = _prevHasFree; - _prevHasFree->_nextHasFree = _nextHasFree; - } - _nextHasFree = nullptr; - _prevHasFree = nullptr; -} - - void BufferState::disableElemHoldList() { diff --git a/vespalib/src/vespa/vespalib/datastore/bufferstate.h b/vespalib/src/vespa/vespalib/datastore/bufferstate.h index 639f4f9dfc6..8f32a93b487 100644 --- a/vespalib/src/vespa/vespalib/datastore/bufferstate.h +++ b/vespalib/src/vespa/vespalib/datastore/bufferstate.h @@ -2,6 +2,7 @@ #pragma once +#include "buffer_free_list.h" #include "buffer_type.h" #include "entryref.h" #include <vespa/vespalib/util/generationhandler.h> @@ -30,17 +31,6 @@ class BufferState public: using Alloc = vespalib::alloc::Alloc; - class FreeListList - { - public: - BufferState *_head; - - FreeListList() : _head(nullptr) { } - ~FreeListList(); - }; - - using FreeList = vespalib::Array<EntryRef>; - enum class State : uint8_t { FREE, ACTIVE, @@ -58,13 +48,8 @@ private: // Number of bytes that are heap allocated by elements that are stored in this buffer and is now on hold. // For simple types this is 0. std::atomic<size_t> _extraHoldBytes; - FreeList _freeList; - FreeListList *_freeListList; // non-nullptr if free lists are enabled - - // nullptr if not on circular list of buffer states with free elems - BufferState *_nextHasFree; - BufferState *_prevHasFree; + BufferFreeList _free_list; std::atomic<BufferTypeBase*> _typeHandler; Alloc _buffer; uint32_t _arraySize; @@ -106,24 +91,6 @@ public: */ void onFree(std::atomic<void*>& buffer); - /** - * Set list of buffer states with nonempty free lists. - * - * @param freeListList List of buffer states. If nullptr then free lists are disabled. - */ - void setFreeListList(FreeListList *freeListList); - - void disableFreeList() { setFreeListList(nullptr); } - - /** - * Add buffer state to list of buffer states with nonempty free lists. - */ - void addToFreeListList(); - - /** - * Remove buffer state from list of buffer states with nonempty free lists. - */ - void removeFromFreeListList(); /** * Disable hold of elements, just mark then as dead without cleanup. @@ -131,18 +98,8 @@ public: */ void disableElemHoldList(); - /** - * Pop element from free list. - */ - EntryRef popFreeList() { - EntryRef ret = _freeList.back(); - _freeList.pop_back(); - if (isFreeListEmpty()) { - removeFromFreeListList(); - } - _deadElems.store(getDeadElems() - _arraySize, std::memory_order_relaxed); - return ret; - } + BufferFreeList& free_list() { return _free_list; } + const BufferFreeList& free_list() const { return _free_list; } size_t size() const { return _usedElems.load(std::memory_order_relaxed); } size_t capacity() const { return _allocElems.load(std::memory_order_relaxed); } @@ -188,10 +145,6 @@ public: } bool hasDisabledElemHoldList() const { return _disableElemHoldList; } - bool isFreeListEmpty() const { return _freeList.empty();} - FreeList &freeList() { return _freeList; } - const FreeListList *freeListList() const { return _freeListList; } - FreeListList *freeListList() { return _freeListList; } void resume_primary_buffer(uint32_t buffer_id); }; diff --git a/vespalib/src/vespa/vespalib/datastore/datastore.h b/vespalib/src/vespa/vespalib/datastore/datastore.h index bb460900606..86c39b547d3 100644 --- a/vespalib/src/vespa/vespalib/datastore/datastore.h +++ b/vespalib/src/vespa/vespalib/datastore/datastore.h @@ -98,7 +98,6 @@ protected: typedef DataStoreT<RefT> ParentType; using ParentType::ensureBufferCapacity; using ParentType::_primary_buffer_ids; - using ParentType::_freeListLists; using ParentType::getEntry; using ParentType::dropBuffers; using ParentType::init_primary_buffers; diff --git a/vespalib/src/vespa/vespalib/datastore/datastore.hpp b/vespalib/src/vespa/vespalib/datastore/datastore.hpp index 72d08460eea..5b8df719915 100644 --- a/vespalib/src/vespa/vespalib/datastore/datastore.hpp +++ b/vespalib/src/vespa/vespalib/datastore/datastore.hpp @@ -27,11 +27,8 @@ DataStoreT<RefT>::free_elem_internal(EntryRef ref, size_t numElems, bool was_hel RefType intRef(ref); BufferState &state = getBufferState(intRef.bufferId()); if (state.isActive()) { - if (state.freeListList() != nullptr && numElems == state.getArraySize()) { - if (state.isFreeListEmpty()) { - state.addToFreeListList(); - } - state.freeList().push_back(ref); + if (state.free_list().enabled() && (numElems == state.getArraySize())) { + state.free_list().push_entry(ref); } } else { assert(state.isOnHold() && was_held); diff --git a/vespalib/src/vespa/vespalib/datastore/datastorebase.cpp b/vespalib/src/vespa/vespalib/datastore/datastorebase.cpp index 79113f76941..67749ee913d 100644 --- a/vespalib/src/vespa/vespalib/datastore/datastorebase.cpp +++ b/vespalib/src/vespa/vespalib/datastore/datastorebase.cpp @@ -85,7 +85,7 @@ DataStoreBase::DataStoreBase(uint32_t numBuffers, uint32_t offset_bits, size_t m _primary_buffer_ids(), _states(numBuffers), _typeHandlers(), - _freeListLists(), + _free_lists(), _freeListsEnabled(false), _initializing(false), _elemHold1List(), @@ -216,7 +216,7 @@ DataStoreBase::addType(BufferTypeBase *typeHandler) typeHandler->clampMaxArrays(_maxArrays); _primary_buffer_ids.push_back(0); _typeHandlers.push_back(typeHandler); - _freeListLists.push_back(BufferState::FreeListList()); + _free_lists.emplace_back(); return typeId; } @@ -300,7 +300,7 @@ DataStoreBase::enableFreeLists() if (!bState.isActive() || bState.getCompacting()) { continue; } - bState.setFreeListList(&_freeListLists[bState.getTypeId()]); + bState.free_list().enable(_free_lists[bState.getTypeId()]); } _freeListsEnabled = true; } @@ -309,7 +309,7 @@ void DataStoreBase::disableFreeLists() { for (BufferState & bState : _states) { - bState.setFreeListList(nullptr); + bState.free_list().disable(); } _freeListsEnabled = false; } @@ -321,14 +321,14 @@ DataStoreBase::enableFreeList(uint32_t bufferId) if (_freeListsEnabled && state.isActive() && !state.getCompacting()) { - state.setFreeListList(&_freeListLists[state.getTypeId()]); + state.free_list().enable(_free_lists[state.getTypeId()]); } } void DataStoreBase::disableFreeList(uint32_t bufferId) { - _states[bufferId].setFreeListList(nullptr); + _states[bufferId].free_list().disable(); } void @@ -527,7 +527,7 @@ DataStoreBase::markCompacting(uint32_t bufferId) assert(!state.getCompacting()); state.setCompacting(); state.disableElemHoldList(); - state.setFreeListList(nullptr); + state.free_list().disable(); inc_compaction_count(); } diff --git a/vespalib/src/vespa/vespalib/datastore/datastorebase.h b/vespalib/src/vespa/vespalib/datastore/datastorebase.h index 40730252139..d83b3a84847 100644 --- a/vespalib/src/vespa/vespalib/datastore/datastorebase.h +++ b/vespalib/src/vespa/vespalib/datastore/datastorebase.h @@ -3,6 +3,7 @@ #pragma once #include "bufferstate.h" +#include "free_list.h" #include <vespa/vespalib/util/address_space.h> #include <vespa/vespalib/util/generationholder.h> #include <vespa/vespalib/util/memoryusage.h> @@ -152,7 +153,7 @@ private: protected: std::vector<BufferTypeBase *> _typeHandlers; // TypeId -> handler - std::vector<BufferState::FreeListList> _freeListLists; + std::vector<FreeList> _free_lists; bool _freeListsEnabled; bool _initializing; @@ -333,8 +334,8 @@ public: /** * Returns the free list for the given type id. */ - BufferState::FreeListList &getFreeList(uint32_t typeId) { - return _freeListLists[typeId]; + FreeList &getFreeList(uint32_t typeId) { + return _free_lists[typeId]; } /** diff --git a/vespalib/src/vespa/vespalib/datastore/free_list.h b/vespalib/src/vespa/vespalib/datastore/free_list.h index 39e1713e47d..20d4a6b96df 100644 --- a/vespalib/src/vespa/vespalib/datastore/free_list.h +++ b/vespalib/src/vespa/vespalib/datastore/free_list.h @@ -21,11 +21,16 @@ private: public: FreeList(); ~FreeList(); + FreeList(FreeList&&) = default; // Needed for emplace_back() during setup. + FreeList(const FreeList&) = delete; + FreeList& operator=(const FreeList&) = delete; + FreeList& operator=(BufferFreeList&&) = delete; void attach(BufferFreeList& buf_list); void detach(BufferFreeList& buf_list); bool empty() const { return _free_lists.empty(); } size_t size() const { return _free_lists.size(); } + uint32_t array_size() const { return _free_lists.back()->array_size(); } EntryRef pop_entry() { return _free_lists.back()->pop_entry(); } diff --git a/vespalib/src/vespa/vespalib/datastore/free_list_allocator.hpp b/vespalib/src/vespa/vespalib/datastore/free_list_allocator.hpp index 3faae71427e..b793e4f77a2 100644 --- a/vespalib/src/vespa/vespalib/datastore/free_list_allocator.hpp +++ b/vespalib/src/vespa/vespalib/datastore/free_list_allocator.hpp @@ -52,13 +52,11 @@ template <typename ... Args> typename Allocator<EntryT, RefT>::HandleType FreeListAllocator<EntryT, RefT, ReclaimerT>::alloc(Args && ... args) { - BufferState::FreeListList &freeListList = _store.getFreeList(_typeId); - if (freeListList._head == nullptr) { + auto& free_list = _store.getFreeList(_typeId); + if (free_list.empty()) { return ParentType::alloc(std::forward<Args>(args)...); } - BufferState &state = *freeListList._head; - assert(state.isActive()); - RefT ref = state.popFreeList(); + RefT ref = free_list.pop_entry(); EntryT *entry = _store.template getEntry<EntryT>(ref); ReclaimerT::reclaim(entry); allocator::Assigner<EntryT, Args...>::assign(*entry, std::forward<Args>(args)...); @@ -69,14 +67,12 @@ template <typename EntryT, typename RefT, typename ReclaimerT> typename Allocator<EntryT, RefT>::HandleType FreeListAllocator<EntryT, RefT, ReclaimerT>::allocArray(ConstArrayRef array) { - BufferState::FreeListList &freeListList = _store.getFreeList(_typeId); - if (freeListList._head == nullptr) { + auto& free_list = _store.getFreeList(_typeId); + if (free_list.empty()) { return ParentType::allocArray(array); } - BufferState &state = *freeListList._head; - assert(state.isActive()); - assert(state.getArraySize() == array.size()); - RefT ref(state.popFreeList()); + assert(free_list.array_size() == array.size()); + RefT ref = free_list.pop_entry(); EntryT *buf = _store.template getEntryArray<EntryT>(ref, array.size()); for (size_t i = 0; i < array.size(); ++i) { *(buf + i) = array[i]; @@ -88,14 +84,12 @@ template <typename EntryT, typename RefT, typename ReclaimerT> typename Allocator<EntryT, RefT>::HandleType FreeListAllocator<EntryT, RefT, ReclaimerT>::allocArray(size_t size) { - BufferState::FreeListList &freeListList = _store.getFreeList(_typeId); - if (freeListList._head == nullptr) { + auto& free_list = _store.getFreeList(_typeId); + if (free_list.empty()) { return ParentType::allocArray(size); } - BufferState &state = *freeListList._head; - assert(state.isActive()); - assert(state.getArraySize() == size); - RefT ref(state.popFreeList()); + assert(free_list.array_size() == size); + RefT ref = free_list.pop_entry(); EntryT *buf = _store.template getEntryArray<EntryT>(ref, size); return HandleType(ref, buf); } diff --git a/vespalib/src/vespa/vespalib/datastore/free_list_raw_allocator.hpp b/vespalib/src/vespa/vespalib/datastore/free_list_raw_allocator.hpp index c4689cd9e4a..af832955cb7 100644 --- a/vespalib/src/vespa/vespalib/datastore/free_list_raw_allocator.hpp +++ b/vespalib/src/vespa/vespalib/datastore/free_list_raw_allocator.hpp @@ -16,16 +16,14 @@ template <typename EntryT, typename RefT> typename FreeListRawAllocator<EntryT, RefT>::HandleType FreeListRawAllocator<EntryT, RefT>::alloc(size_t numElems) { - BufferState::FreeListList &freeListList = _store.getFreeList(_typeId); - if (freeListList._head == nullptr) { + auto& free_list = _store.getFreeList(_typeId); + if (free_list.empty()) { return ParentType::alloc(numElems); } - BufferState &state = *freeListList._head; - assert(state.isActive()); - assert(state.getArraySize() == numElems); - RefT ref = state.popFreeList(); + assert(free_list.array_size() == numElems); + RefT ref = free_list.pop_entry(); // We must scale the offset according to array size as it was divided when the entry ref was created. - EntryT *entry = _store.template getEntryArray<EntryT>(ref, state.getArraySize()); + EntryT *entry = _store.template getEntryArray<EntryT>(ref, numElems); return HandleType(ref, entry); } |