diff options
| -rw-r--r-- | src/Makefile.am | 1 | ||||
| -rw-r--r-- | src/Makefile.bench.include | 1 | ||||
| -rw-r--r-- | src/Makefile.test.include | 1 | ||||
| -rw-r--r-- | src/Makefile.test_util.include | 1 | ||||
| -rw-r--r-- | src/bench/pool.cpp | 50 | ||||
| -rw-r--r-- | src/support/allocators/pool.h | 349 | ||||
| -rw-r--r-- | src/test/pool_tests.cpp | 156 | ||||
| -rw-r--r-- | src/test/util/poolresourcetester.h | 129 |
8 files changed, 688 insertions, 0 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index 53c809c901..985a8e8915 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -261,6 +261,7 @@ BITCOIN_CORE_H = \ shutdown.h \ signet.h \ streams.h \ + support/allocators/pool.h \ support/allocators/secure.h \ support/allocators/zeroafterfree.h \ support/cleanse.h \ diff --git a/src/Makefile.bench.include b/src/Makefile.bench.include index f1e4e706a1..c230728a1c 100644 --- a/src/Makefile.bench.include +++ b/src/Makefile.bench.include @@ -42,6 +42,7 @@ bench_bench_bitcoin_SOURCES = \ bench/nanobench.h \ bench/peer_eviction.cpp \ bench/poly1305.cpp \ + bench/pool.cpp \ bench/prevector.cpp \ bench/rollingbloom.cpp \ bench/rpc_blockchain.cpp \ diff --git a/src/Makefile.test.include b/src/Makefile.test.include index a39b0abd9d..98ed3ba4ad 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -116,6 +116,7 @@ BITCOIN_TESTS =\ test/pmt_tests.cpp \ test/policy_fee_tests.cpp \ test/policyestimator_tests.cpp \ + test/pool_tests.cpp \ test/pow_tests.cpp \ test/prevector_tests.cpp \ test/raii_event_tests.cpp \ diff --git a/src/Makefile.test_util.include b/src/Makefile.test_util.include index aefefe789a..11b93ad13e 100644 --- a/src/Makefile.test_util.include +++ b/src/Makefile.test_util.include @@ -15,6 +15,7 @@ TEST_UTIL_H = \ test/util/logging.h \ test/util/mining.h \ test/util/net.h \ + test/util/poolresourcetester.h \ test/util/random.h \ test/util/script.h \ test/util/setup_common.h \ diff --git a/src/bench/pool.cpp b/src/bench/pool.cpp new file mode 100644 index 0000000000..b3e54d85a2 --- /dev/null +++ b/src/bench/pool.cpp @@ -0,0 +1,50 @@ +// Copyright (c) 2022 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include <bench/bench.h> +#include <support/allocators/pool.h> + +#include <unordered_map> + +template <typename Map> +void BenchFillClearMap(benchmark::Bench& bench, Map& map) +{ + size_t batch_size = 5000; + + // make sure each iteration of the benchmark contains exactly 5000 inserts and one clear. + // do this at least 10 times so we get reasonable accurate results + + bench.batch(batch_size).minEpochIterations(10).run([&] { + auto rng = ankerl::nanobench::Rng(1234); + for (size_t i = 0; i < batch_size; ++i) { + map[rng()]; + } + map.clear(); + }); +} + +static void PoolAllocator_StdUnorderedMap(benchmark::Bench& bench) +{ + auto map = std::unordered_map<uint64_t, uint64_t>(); + BenchFillClearMap(bench, map); +} + +static void PoolAllocator_StdUnorderedMapWithPoolResource(benchmark::Bench& bench) +{ + using Map = std::unordered_map<uint64_t, + uint64_t, + std::hash<uint64_t>, + std::equal_to<uint64_t>, + PoolAllocator<std::pair<const uint64_t, uint64_t>, + sizeof(std::pair<const uint64_t, uint64_t>) + 4 * sizeof(void*), + alignof(void*)>>; + + // make sure the resource supports large enough pools to hold the node. We do this by adding the size of a few pointers to it. + auto pool_resource = Map::allocator_type::ResourceType(); + auto map = Map{0, std::hash<uint64_t>{}, std::equal_to<uint64_t>{}, &pool_resource}; + BenchFillClearMap(bench, map); +} + +BENCHMARK(PoolAllocator_StdUnorderedMap, benchmark::PriorityLevel::HIGH); +BENCHMARK(PoolAllocator_StdUnorderedMapWithPoolResource, benchmark::PriorityLevel::HIGH); diff --git a/src/support/allocators/pool.h b/src/support/allocators/pool.h new file mode 100644 index 0000000000..c8e70ebacf --- /dev/null +++ b/src/support/allocators/pool.h @@ -0,0 +1,349 @@ +// Copyright (c) 2022 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_SUPPORT_ALLOCATORS_POOL_H +#define BITCOIN_SUPPORT_ALLOCATORS_POOL_H + +#include <array> +#include <cassert> +#include <cstddef> +#include <list> +#include <memory> +#include <new> +#include <type_traits> +#include <utility> + +/** + * A memory resource similar to std::pmr::unsynchronized_pool_resource, but + * optimized for node-based containers. It has the following properties: + * + * * Owns the allocated memory and frees it on destruction, even when deallocate + * has not been called on the allocated blocks. + * + * * Consists of a number of pools, each one for a different block size. + * Each pool holds blocks of uniform size in a freelist. + * + * * Exhausting memory in a freelist causes a new allocation of a fixed size chunk. + * This chunk is used to carve out blocks. + * + * * Block sizes or alignments that can not be served by the pools are allocated + * and deallocated by operator new(). + * + * PoolResource is not thread-safe. It is intended to be used by PoolAllocator. + * + * @tparam MAX_BLOCK_SIZE_BYTES Maximum size to allocate with the pool. If larger + * sizes are requested, allocation falls back to new(). + * + * @tparam ALIGN_BYTES Required alignment for the allocations. + * + * An example: If you create a PoolResource<128, 8>(262144) and perform a bunch of + * allocations and deallocate 2 blocks with size 8 bytes, and 3 blocks with size 16, + * the members will look like this: + * + * m_free_lists m_allocated_chunks + * ┌───┐ ┌───┐ ┌────────────-------──────┐ + * │ │ blocks │ ├─►│ 262144 B │ + * │ │ ┌─────┐ ┌─────┐ └─┬─┘ └────────────-------──────┘ + * │ 1 ├─►│ 8 B ├─►│ 8 B │ │ + * │ │ └─────┘ └─────┘ : + * │ │ │ + * │ │ ┌─────┐ ┌─────┐ ┌─────┐ ▼ + * │ 2 ├─►│16 B ├─►│16 B ├─►│16 B │ ┌───┐ ┌─────────────────────────┐ + * │ │ └─────┘ └─────┘ └─────┘ │ ├─►│ ▲ │ ▲ + * │ │ └───┘ └──────────┬──────────────┘ │ + * │ . │ │ m_available_memory_end + * │ . │ m_available_memory_it + * │ . │ + * │ │ + * │ │ + * │16 │ + * └───┘ + * + * Here m_free_lists[1] holds the 2 blocks of size 8 bytes, and m_free_lists[2] + * holds the 3 blocks of size 16. The blocks came from the data stored in the + * m_allocated_chunks list. Each chunk has bytes 262144. The last chunk has still + * some memory available for the blocks, and when m_available_memory_it is at the + * end, a new chunk will be allocated and added to the list. + */ +template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> +class PoolResource final +{ + static_assert(ALIGN_BYTES > 0, "ALIGN_BYTES must be nonzero"); + static_assert((ALIGN_BYTES & (ALIGN_BYTES - 1)) == 0, "ALIGN_BYTES must be a power of two"); + + /** + * In-place linked list of the allocations, used for the freelist. + */ + struct ListNode { + ListNode* m_next; + + explicit ListNode(ListNode* next) : m_next(next) {} + }; + static_assert(std::is_trivially_destructible_v<ListNode>, "Make sure we don't need to manually call a destructor"); + + /** + * Internal alignment value. The larger of the requested ALIGN_BYTES and alignof(FreeList). + */ + static constexpr std::size_t ELEM_ALIGN_BYTES = std::max(alignof(ListNode), ALIGN_BYTES); + static_assert((ELEM_ALIGN_BYTES & (ELEM_ALIGN_BYTES - 1)) == 0, "ELEM_ALIGN_BYTES must be a power of two"); + static_assert(sizeof(ListNode) <= ELEM_ALIGN_BYTES, "Units of size ELEM_SIZE_ALIGN need to be able to store a ListNode"); + static_assert((MAX_BLOCK_SIZE_BYTES & (ELEM_ALIGN_BYTES - 1)) == 0, "MAX_BLOCK_SIZE_BYTES needs to be a multiple of the alignment."); + + /** + * Size in bytes to allocate per chunk + */ + const size_t m_chunk_size_bytes; + + /** + * Contains all allocated pools of memory, used to free the data in the destructor. + */ + std::list<std::byte*> m_allocated_chunks{}; + + /** + * Single linked lists of all data that came from deallocating. + * m_free_lists[n] will serve blocks of size n*ELEM_ALIGN_BYTES. + */ + std::array<ListNode*, MAX_BLOCK_SIZE_BYTES / ELEM_ALIGN_BYTES + 1> m_free_lists{}; + + /** + * Points to the beginning of available memory for carving out allocations. + */ + std::byte* m_available_memory_it = nullptr; + + /** + * Points to the end of available memory for carving out allocations. + * + * That member variable is redundant, and is always equal to `m_allocated_chunks.back() + m_chunk_size_bytes` + * whenever it is accessed, but `m_available_memory_end` caches this for clarity and efficiency. + */ + std::byte* m_available_memory_end = nullptr; + + /** + * How many multiple of ELEM_ALIGN_BYTES are necessary to fit bytes. We use that result directly as an index + * into m_free_lists. Round up for the special case when bytes==0. + */ + [[nodiscard]] static constexpr std::size_t NumElemAlignBytes(std::size_t bytes) + { + return (bytes + ELEM_ALIGN_BYTES - 1) / ELEM_ALIGN_BYTES + (bytes == 0); + } + + /** + * True when it is possible to make use of the freelist + */ + [[nodiscard]] static constexpr bool IsFreeListUsable(std::size_t bytes, std::size_t alignment) + { + return alignment <= ELEM_ALIGN_BYTES && bytes <= MAX_BLOCK_SIZE_BYTES; + } + + /** + * Replaces node with placement constructed ListNode that points to the previous node + */ + void PlacementAddToList(void* p, ListNode*& node) + { + node = new (p) ListNode{node}; + } + + /** + * Allocate one full memory chunk which will be used to carve out allocations. + * Also puts any leftover bytes into the freelist. + * + * Precondition: leftover bytes are either 0 or few enough to fit into a place in the freelist + */ + void AllocateChunk() + { + // if there is still any available memory left, put it into the freelist. + size_t remaining_available_bytes = std::distance(m_available_memory_it, m_available_memory_end); + if (0 != remaining_available_bytes) { + PlacementAddToList(m_available_memory_it, m_free_lists[remaining_available_bytes / ELEM_ALIGN_BYTES]); + } + + void* storage = ::operator new (m_chunk_size_bytes, std::align_val_t{ELEM_ALIGN_BYTES}); + m_available_memory_it = new (storage) std::byte[m_chunk_size_bytes]; + m_available_memory_end = m_available_memory_it + m_chunk_size_bytes; + m_allocated_chunks.emplace_back(m_available_memory_it); + } + + /** + * Access to internals for testing purpose only + */ + friend class PoolResourceTester; + +public: + /** + * Construct a new PoolResource object which allocates the first chunk. + * chunk_size_bytes will be rounded up to next multiple of ELEM_ALIGN_BYTES. + */ + explicit PoolResource(std::size_t chunk_size_bytes) + : m_chunk_size_bytes(NumElemAlignBytes(chunk_size_bytes) * ELEM_ALIGN_BYTES) + { + assert(m_chunk_size_bytes >= MAX_BLOCK_SIZE_BYTES); + AllocateChunk(); + } + + /** + * Construct a new Pool Resource object, defaults to 2^18=262144 chunk size. + */ + PoolResource() : PoolResource(262144) {} + + /** + * Disable copy & move semantics, these are not supported for the resource. + */ + PoolResource(const PoolResource&) = delete; + PoolResource& operator=(const PoolResource&) = delete; + PoolResource(PoolResource&&) = delete; + PoolResource& operator=(PoolResource&&) = delete; + + /** + * Deallocates all memory allocated associated with the memory resource. + */ + ~PoolResource() + { + for (std::byte* chunk : m_allocated_chunks) { + std::destroy(chunk, chunk + m_chunk_size_bytes); + ::operator delete ((void*)chunk, std::align_val_t{ELEM_ALIGN_BYTES}); + } + } + + /** + * Allocates a block of bytes. If possible the freelist is used, otherwise allocation + * is forwarded to ::operator new(). + */ + void* Allocate(std::size_t bytes, std::size_t alignment) + { + if (IsFreeListUsable(bytes, alignment)) { + const std::size_t num_alignments = NumElemAlignBytes(bytes); + if (nullptr != m_free_lists[num_alignments]) { + // we've already got data in the pool's freelist, unlink one element and return the pointer + // to the unlinked memory. Since FreeList is trivially destructible we can just treat it as + // uninitialized memory. + return std::exchange(m_free_lists[num_alignments], m_free_lists[num_alignments]->m_next); + } + + // freelist is empty: get one allocation from allocated chunk memory. + const std::ptrdiff_t round_bytes = static_cast<std::ptrdiff_t>(num_alignments * ELEM_ALIGN_BYTES); + if (round_bytes > m_available_memory_end - m_available_memory_it) { + // slow path, only happens when a new chunk needs to be allocated + AllocateChunk(); + } + + // Make sure we use the right amount of bytes for that freelist (might be rounded up), + return std::exchange(m_available_memory_it, m_available_memory_it + round_bytes); + } + + // Can't use the pool => use operator new() + return ::operator new (bytes, std::align_val_t{alignment}); + } + + /** + * Returns a block to the freelists, or deletes the block when it did not come from the chunks. + */ + void Deallocate(void* p, std::size_t bytes, std::size_t alignment) noexcept + { + if (IsFreeListUsable(bytes, alignment)) { + const std::size_t num_alignments = NumElemAlignBytes(bytes); + // put the memory block into the linked list. We can placement construct the FreeList + // into the memory since we can be sure the alignment is correct. + PlacementAddToList(p, m_free_lists[num_alignments]); + } else { + // Can't use the pool => forward deallocation to ::operator delete(). + ::operator delete (p, std::align_val_t{alignment}); + } + } + + /** + * Number of allocated chunks + */ + [[nodiscard]] std::size_t NumAllocatedChunks() const + { + return m_allocated_chunks.size(); + } + + /** + * Size in bytes to allocate per chunk, currently hardcoded to a fixed size. + */ + [[nodiscard]] size_t ChunkSizeBytes() const + { + return m_chunk_size_bytes; + } +}; + + +/** + * Forwards all allocations/deallocations to the PoolResource. + */ +template <class T, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> +class PoolAllocator +{ + PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>* m_resource; + + template <typename U, std::size_t M, std::size_t A> + friend class PoolAllocator; + +public: + using value_type = T; + using ResourceType = PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>; + + /** + * Not explicit so we can easily construct it with the correct resource + */ + PoolAllocator(ResourceType* resource) noexcept + : m_resource(resource) + { + } + + PoolAllocator(const PoolAllocator& other) noexcept = default; + PoolAllocator& operator=(const PoolAllocator& other) noexcept = default; + + template <class U> + PoolAllocator(const PoolAllocator<U, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& other) noexcept + : m_resource(other.resource()) + { + } + + /** + * The rebind struct here is mandatory because we use non type template arguments for + * PoolAllocator. See https://en.cppreference.com/w/cpp/named_req/Allocator#cite_note-2 + */ + template <typename U> + struct rebind { + using other = PoolAllocator<U, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>; + }; + + /** + * Forwards each call to the resource. + */ + T* allocate(size_t n) + { + return static_cast<T*>(m_resource->Allocate(n * sizeof(T), alignof(T))); + } + + /** + * Forwards each call to the resource. + */ + void deallocate(T* p, size_t n) noexcept + { + m_resource->Deallocate(p, n * sizeof(T), alignof(T)); + } + + ResourceType* resource() const noexcept + { + return m_resource; + } +}; + +template <class T1, class T2, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> +bool operator==(const PoolAllocator<T1, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& a, + const PoolAllocator<T2, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& b) noexcept +{ + return a.resource() == b.resource(); +} + +template <class T1, class T2, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> +bool operator!=(const PoolAllocator<T1, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& a, + const PoolAllocator<T2, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& b) noexcept +{ + return !(a == b); +} + +#endif // BITCOIN_SUPPORT_ALLOCATORS_POOL_H diff --git a/src/test/pool_tests.cpp b/src/test/pool_tests.cpp new file mode 100644 index 0000000000..dfe857d05b --- /dev/null +++ b/src/test/pool_tests.cpp @@ -0,0 +1,156 @@ +// Copyright (c) 2022 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include <support/allocators/pool.h> +#include <test/util/poolresourcetester.h> +#include <test/util/random.h> +#include <test/util/setup_common.h> + +#include <boost/test/unit_test.hpp> + +#include <cstddef> +#include <cstdint> +#include <unordered_map> +#include <vector> + +BOOST_FIXTURE_TEST_SUITE(pool_tests, BasicTestingSetup) + +BOOST_AUTO_TEST_CASE(basic_allocating) +{ + auto resource = PoolResource<8, 8>(); + PoolResourceTester::CheckAllDataAccountedFor(resource); + + // first chunk is already allocated + size_t expected_bytes_available = resource.ChunkSizeBytes(); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + // chunk is used, no more allocation + void* block = resource.Allocate(8, 8); + expected_bytes_available -= 8; + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]); + resource.Deallocate(block, 8, 8); + PoolResourceTester::CheckAllDataAccountedFor(resource); + BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]); + + // alignment is too small, but the best fitting freelist is used. Nothing is allocated. + void* b = resource.Allocate(8, 1); + BOOST_TEST(b == block); // we got the same block of memory as before + BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + resource.Deallocate(block, 8, 1); + PoolResourceTester::CheckAllDataAccountedFor(resource); + BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + // can't use resource because alignment is too big, allocate system memory + b = resource.Allocate(8, 16); + BOOST_TEST(b != block); + block = b; + PoolResourceTester::CheckAllDataAccountedFor(resource); + BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + resource.Deallocate(block, 8, 16); + PoolResourceTester::CheckAllDataAccountedFor(resource); + BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + // can't use chunk because size is too big + block = resource.Allocate(16, 8); + PoolResourceTester::CheckAllDataAccountedFor(resource); + BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + resource.Deallocate(block, 16, 8); + PoolResourceTester::CheckAllDataAccountedFor(resource); + BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + // it's possible that 0 bytes are allocated, make sure this works. In that case the call is forwarded to operator new + // 0 bytes takes one entry from the first freelist + void* p = resource.Allocate(0, 1); + BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); + + resource.Deallocate(p, 0, 1); + PoolResourceTester::CheckAllDataAccountedFor(resource); + BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]); + BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource)); +} + +// Allocates from 0 to n bytes were n > the PoolResource's data, and each should work +BOOST_AUTO_TEST_CASE(allocate_any_byte) +{ + auto resource = PoolResource<128, 8>(1024); + + uint8_t num_allocs = 200; + + auto data = std::vector<Span<uint8_t>>(); + + // allocate an increasing number of bytes + for (uint8_t num_bytes = 0; num_bytes < num_allocs; ++num_bytes) { + uint8_t* bytes = new (resource.Allocate(num_bytes, 1)) uint8_t[num_bytes]; + BOOST_TEST(bytes != nullptr); + data.emplace_back(bytes, num_bytes); + + // set each byte to num_bytes + std::fill(bytes, bytes + num_bytes, num_bytes); + } + + // now that we got all allocated, test if all still have the correct values, and give everything back to the allocator + uint8_t val = 0; + for (auto const& span : data) { + for (auto x : span) { + BOOST_TEST(val == x); + } + std::destroy(span.data(), span.data() + span.size()); + resource.Deallocate(span.data(), span.size(), 1); + ++val; + } + + PoolResourceTester::CheckAllDataAccountedFor(resource); +} + +BOOST_AUTO_TEST_CASE(random_allocations) +{ + struct PtrSizeAlignment { + void* ptr; + size_t bytes; + size_t alignment; + }; + + // makes a bunch of random allocations and gives all of them back in random order. + auto resource = PoolResource<128, 8>(65536); + std::vector<PtrSizeAlignment> ptr_size_alignment{}; + for (size_t i = 0; i < 1000; ++i) { + // make it a bit more likely to allocate than deallocate + if (ptr_size_alignment.empty() || 0 != InsecureRandRange(4)) { + // allocate a random item + std::size_t alignment = std::size_t{1} << InsecureRandRange(8); // 1, 2, ..., 128 + std::size_t size = (InsecureRandRange(200) / alignment + 1) * alignment; // multiple of alignment + void* ptr = resource.Allocate(size, alignment); + BOOST_TEST(ptr != nullptr); + BOOST_TEST((reinterpret_cast<uintptr_t>(ptr) & (alignment - 1)) == 0); + ptr_size_alignment.push_back({ptr, size, alignment}); + } else { + // deallocate a random item + auto& x = ptr_size_alignment[InsecureRandRange(ptr_size_alignment.size())]; + resource.Deallocate(x.ptr, x.bytes, x.alignment); + x = ptr_size_alignment.back(); + ptr_size_alignment.pop_back(); + } + } + + // deallocate all the rest + for (auto const& x : ptr_size_alignment) { + resource.Deallocate(x.ptr, x.bytes, x.alignment); + } + + PoolResourceTester::CheckAllDataAccountedFor(resource); +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/util/poolresourcetester.h b/src/test/util/poolresourcetester.h new file mode 100644 index 0000000000..93f62eb2a9 --- /dev/null +++ b/src/test/util/poolresourcetester.h @@ -0,0 +1,129 @@ +// Copyright (c) 2022 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H +#define BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H + +#include <support/allocators/pool.h> + +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <cstdint> +#include <vector> + +/** + * Helper to get access to private parts of PoolResource. Used in unit tests and in the fuzzer + */ +class PoolResourceTester +{ + struct PtrAndBytes { + uintptr_t ptr; + std::size_t size; + + PtrAndBytes(const void* p, std::size_t s) + : ptr(reinterpret_cast<uintptr_t>(p)), size(s) + { + } + + /** + * defines a sort ordering by the pointer value + */ + friend bool operator<(PtrAndBytes const& a, PtrAndBytes const& b) + { + return a.ptr < b.ptr; + } + }; + +public: + /** + * Extracts the number of elements per freelist + */ + template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> + static std::vector<std::size_t> FreeListSizes(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource) + { + auto sizes = std::vector<std::size_t>(); + for (const auto* ptr : resource.m_free_lists) { + size_t size = 0; + while (ptr != nullptr) { + ++size; + ptr = ptr->m_next; + } + sizes.push_back(size); + } + return sizes; + } + + /** + * How many bytes are still available from the last allocated chunk + */ + template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> + static std::size_t AvailableMemoryFromChunk(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource) + { + return resource.m_available_memory_end - resource.m_available_memory_it; + } + + /** + * Once all blocks are given back to the resource, tests that the freelists are consistent: + * + * * All data in the freelists must come from the chunks + * * Memory doesn't overlap + * * Each byte in the chunks can be accounted for in either the freelist or as available bytes. + */ + template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES> + static void CheckAllDataAccountedFor(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource) + { + // collect all free blocks by iterating all freelists + std::vector<PtrAndBytes> free_blocks; + for (std::size_t freelist_idx = 0; freelist_idx < resource.m_free_lists.size(); ++freelist_idx) { + std::size_t bytes = freelist_idx * resource.ELEM_ALIGN_BYTES; + auto* ptr = resource.m_free_lists[freelist_idx]; + while (ptr != nullptr) { + free_blocks.emplace_back(ptr, bytes); + ptr = ptr->m_next; + } + } + // also add whatever has not yet been used for blocks + auto num_available_bytes = resource.m_available_memory_end - resource.m_available_memory_it; + if (num_available_bytes > 0) { + free_blocks.emplace_back(resource.m_available_memory_it, num_available_bytes); + } + + // collect all chunks + std::vector<PtrAndBytes> chunks; + for (const std::byte* ptr : resource.m_allocated_chunks) { + chunks.emplace_back(ptr, resource.ChunkSizeBytes()); + } + + // now we have all the data from all freelists on the one hand side, and all chunks on the other hand side. + // To check if all of them match, sort by address and iterate. + std::sort(free_blocks.begin(), free_blocks.end()); + std::sort(chunks.begin(), chunks.end()); + + auto chunk_it = chunks.begin(); + auto chunk_ptr_remaining = chunk_it->ptr; + auto chunk_size_remaining = chunk_it->size; + for (const auto& free_block : free_blocks) { + if (chunk_size_remaining == 0) { + assert(chunk_it != chunks.end()); + ++chunk_it; + assert(chunk_it != chunks.end()); + chunk_ptr_remaining = chunk_it->ptr; + chunk_size_remaining = chunk_it->size; + } + assert(free_block.ptr == chunk_ptr_remaining); // ensure addresses match + assert(free_block.size <= chunk_size_remaining); // ensure no overflow + assert((free_block.ptr & (resource.ELEM_ALIGN_BYTES - 1)) == 0); // ensure correct alignment + chunk_ptr_remaining += free_block.size; + chunk_size_remaining -= free_block.size; + } + // ensure we are at the end of the chunks + assert(chunk_ptr_remaining == chunk_it->ptr + chunk_it->size); + ++chunk_it; + assert(chunk_it == chunks.end()); + assert(chunk_size_remaining == 0); + } +}; + +#endif // BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H |