Add pool based memory resource & allocator

A memory resource similar to std::pmr::unsynchronized_pool_resource, but
optimized for node-based containers.

Co-Authored-By: Pieter Wuille <pieter@wuille.net>

2 files changed, 285 insertions, 0 deletions

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