Merge bitcoin/bitcoin#25325: Add pool based memory resource

9f947fc3d4b779f017332135323b34e8f216f613 Use PoolAllocator for CCoinsMap (Martin Leitner-Ankerl)
5e4ac5abf54f8e6d6330df0c73119aa0cca4c103 Call ReallocateCache() on each Flush() (Martin Leitner-Ankerl)
1afca6b663bb54022afff193fd9d83856606b189 Add PoolResource fuzzer (Martin Leitner-Ankerl)
e19943f049ed8aa4f32a1d8440a9fbf160367f0f Calculate memory usage correctly for unordered_maps that use PoolAllocator (Martin Leitner-Ankerl)
b8401c3281978beed6198b2f9782b6a8dd35cbd7 Add pool based memory resource & allocator (Martin Leitner-Ankerl)

Pull request description:

  A memory resource similar to `std::pmr::unsynchronized_pool_resource`, but optimized for node-based containers. The goal is to be able to cache more coins with the same memory usage, and allocate/deallocate faster.

  This is a reimplementation of #22702. The goal was to implement it in a way that is simpler to review & test

  * There is now a generic `PoolResource` for allocating/deallocating memory. This has practically the same API as `std::pmr::memory_resource`. (Unfortunately I cannot use std::pmr because libc++ simply doesn't implement that API).
  * Thanks to sipa there is now a fuzzer for PoolResource! On a fast machine I ran it for ~770 million executions without finding any issue.

  * The estimation of the correct node size is now gone, PoolResource now has multiple pools and just needs to be created large enough to have space for the unordered_map nodes.

  I ran benchmarks with #22702, mergebase, and this PR. Frequency locked Intel i7-8700, clang++ 13.0.1 to reindex up to block 690000.

  ```sh
  bitcoind -dbcache=5000 -assumevalid=00000000000000000002a23d6df20eecec15b21d32c75833cce28f113de888b7 -reindex-chainstate -printtoconsole=0 -stopatheight=690000
  ```

  The performance is practically identical with #22702, just 0.4% slower. It's ~21% faster than master:

  ![Progress in Million Transactions over Time(2)](https://user-images.githubusercontent.com/14386/173288685-91952ade-f304-4825-8bfb-0725a71ca17b.png)

  ![Size of Cache in MiB over Time](https://user-images.githubusercontent.com/14386/173291421-e6b410be-ac77-479b-ad24-5fafcebf81eb.png)
  Note that on cache drops mergebase's memory doesnt go so far down because it does not free the `CCoinsMap` bucket array.

  ![Size of Cache in Million tx over Time(1)](https://user-images.githubusercontent.com/14386/173288703-a80c9c9e-93c8-4a16-9df8-610c89c61cc4.png)

ACKs for top commit:
  LarryRuane:
    ACK 9f947fc3d4b779f017332135323b34e8f216f613
  achow101:
    re-ACK 9f947fc3d4b779f017332135323b34e8f216f613
  john-moffett:
    ACK 9f947fc3d4b779f017332135323b34e8f216f613
  jonatack:
    re-ACK 9f947fc3d4b779f017332135323b34e8f216f613

Tree-SHA512: 48caf57d1775875a612b54388ef64c53952cd48741cacfe20d89049f2fb35301b5c28e69264b7d659a3ca33d4c714d47bafad6fd547c4075f08b45acc87c0f45

6 files changed, 551 insertions, 17 deletions

diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp
index e082800fc3..853dc6dc1e 100644
--- a/src/test/coins_tests.cpp
+++ b/src/test/coins_tests.cpp
@@ -6,6 +6,7 @@
 #include <coins.h>
 #include <script/standard.h>
 #include <streams.h>
+#include <test/util/poolresourcetester.h>
 #include <test/util/random.h>
 #include <test/util/setup_common.h>
 #include <txdb.h>
@@ -612,7 +613,8 @@ void GetCoinsMapEntry(const CCoinsMap& map, CAmount& value, char& flags, const C
 
 void WriteCoinsViewEntry(CCoinsView& view, CAmount value, char flags)
 {
-    CCoinsMap map;
+    CCoinsMapMemoryResource resource;
+    CCoinsMap map{0, CCoinsMap::hasher{}, CCoinsMap::key_equal{}, &resource};
     InsertCoinsMapEntry(map, value, flags);
     BOOST_CHECK(view.BatchWrite(map, {}));
 }
@@ -911,6 +913,7 @@ void TestFlushBehavior(
     CAmount value;
     char flags;
     size_t cache_usage;
+    size_t cache_size;
 
     auto flush_all = [&all_caches](bool erase) {
         // Flush in reverse order to ensure that flushes happen from children up.
@@ -935,6 +938,8 @@ void TestFlushBehavior(
     view->AddCoin(outp, Coin(coin), false);
 
     cache_usage = view->DynamicMemoryUsage();
+    cache_size = view->map().size();
+
     // `base` shouldn't have coin (no flush yet) but `view` should have cached it.
     BOOST_CHECK(!base.HaveCoin(outp));
     BOOST_CHECK(view->HaveCoin(outp));
@@ -949,6 +954,7 @@ void TestFlushBehavior(
 
     // CoinsMap usage should be unchanged since we didn't erase anything.
     BOOST_CHECK_EQUAL(cache_usage, view->DynamicMemoryUsage());
+    BOOST_CHECK_EQUAL(cache_size, view->map().size());
 
     // --- 3. Ensuring the entry still exists in the cache and has been written to parent
     //
@@ -965,8 +971,10 @@ void TestFlushBehavior(
         //
         flush_all(/*erase=*/ true);
 
-        // Memory usage should have gone down.
-        BOOST_CHECK(view->DynamicMemoryUsage() < cache_usage);
+        // Memory does not necessarily go down due to the map using a memory pool
+        BOOST_TEST(view->DynamicMemoryUsage() <= cache_usage);
+        // Size of the cache must go down though
+        BOOST_TEST(view->map().size() < cache_size);
 
         // --- 5. Ensuring the entry is no longer in the cache
         //
@@ -1076,4 +1084,29 @@ BOOST_AUTO_TEST_CASE(ccoins_flush_behavior)
     }
 }
 
+BOOST_AUTO_TEST_CASE(coins_resource_is_used)
+{
+    CCoinsMapMemoryResource resource;
+    PoolResourceTester::CheckAllDataAccountedFor(resource);
+
+    {
+        CCoinsMap map{0, CCoinsMap::hasher{}, CCoinsMap::key_equal{}, &resource};
+        BOOST_TEST(memusage::DynamicUsage(map) >= resource.ChunkSizeBytes());
+
+        map.reserve(1000);
+
+        // The resource has preallocated a chunk, so we should have space for at several nodes without the need to allocate anything else.
+        const auto usage_before = memusage::DynamicUsage(map);
+
+        COutPoint out_point{};
+        for (size_t i = 0; i < 1000; ++i) {
+            out_point.n = i;
+            map[out_point];
+        }
+        BOOST_TEST(usage_before == memusage::DynamicUsage(map));
+    }
+
+    PoolResourceTester::CheckAllDataAccountedFor(resource);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/fuzz/coins_view.cpp b/src/test/fuzz/coins_view.cpp
index e80c772aa4..5843b80c0a 100644
--- a/src/test/fuzz/coins_view.cpp
+++ b/src/test/fuzz/coins_view.cpp
@@ -115,7 +115,8 @@ FUZZ_TARGET_INIT(coins_view, initialize_coins_view)
                 random_mutable_transaction = *opt_mutable_transaction;
             },
             [&] {
-                CCoinsMap coins_map;
+                CCoinsMapMemoryResource resource;
+                CCoinsMap coins_map{0, SaltedOutpointHasher{/*deterministic=*/true}, CCoinsMap::key_equal{}, &resource};
                 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000) {
                     CCoinsCacheEntry coins_cache_entry;
                     coins_cache_entry.flags = fuzzed_data_provider.ConsumeIntegral<unsigned char>();
diff --git a/src/test/fuzz/poolresource.cpp b/src/test/fuzz/poolresource.cpp
new file mode 100644
index 0000000000..ce64ef6472
--- /dev/null
+++ b/src/test/fuzz/poolresource.cpp
@@ -0,0 +1,174 @@
+// 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 <span.h>
+#include <support/allocators/pool.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <test/util/poolresourcetester.h>
+#include <test/util/xoroshiro128plusplus.h>
+
+#include <cstdint>
+#include <tuple>
+#include <vector>
+
+namespace {
+
+template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
+class PoolResourceFuzzer
+{
+    FuzzedDataProvider& m_provider;
+    PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES> m_test_resource;
+    uint64_t m_sequence{0};
+    size_t m_total_allocated{};
+
+    struct Entry {
+        Span<std::byte> span;
+        size_t alignment;
+        uint64_t seed;
+
+        Entry(Span<std::byte> s, size_t a, uint64_t se) : span(s), alignment(a), seed(se) {}
+    };
+
+    std::vector<Entry> m_entries;
+
+public:
+    PoolResourceFuzzer(FuzzedDataProvider& provider)
+        : m_provider{provider},
+          m_test_resource{provider.ConsumeIntegralInRange<size_t>(MAX_BLOCK_SIZE_BYTES, 262144)}
+    {
+    }
+
+    void Allocate(size_t size, size_t alignment)
+    {
+        assert(size > 0);                           // Must allocate at least 1 byte.
+        assert(alignment > 0);                      // Alignment must be at least 1.
+        assert((alignment & (alignment - 1)) == 0); // Alignment must be power of 2.
+        assert((size & (alignment - 1)) == 0);      // Size must be a multiple of alignment.
+
+        auto span = Span(static_cast<std::byte*>(m_test_resource.Allocate(size, alignment)), size);
+        m_total_allocated += size;
+
+        auto ptr_val = reinterpret_cast<std::uintptr_t>(span.data());
+        assert((ptr_val & (alignment - 1)) == 0);
+
+        uint64_t seed = m_sequence++;
+        RandomContentFill(m_entries.emplace_back(span, alignment, seed));
+    }
+
+    void
+    Allocate()
+    {
+        if (m_total_allocated > 0x1000000) return;
+        size_t alignment_bits = m_provider.ConsumeIntegralInRange<size_t>(0, 7);
+        size_t alignment = 1 << alignment_bits;
+        size_t size_bits = m_provider.ConsumeIntegralInRange<size_t>(0, 16 - alignment_bits);
+        size_t size = m_provider.ConsumeIntegralInRange<size_t>(1U << size_bits, (1U << (size_bits + 1)) - 1U) << alignment_bits;
+        Allocate(size, alignment);
+    }
+
+    void RandomContentFill(Entry& entry)
+    {
+        XoRoShiRo128PlusPlus rng(entry.seed);
+        auto ptr = entry.span.data();
+        auto size = entry.span.size();
+
+        while (size >= 8) {
+            auto r = rng();
+            std::memcpy(ptr, &r, 8);
+            size -= 8;
+            ptr += 8;
+        }
+        if (size > 0) {
+            auto r = rng();
+            std::memcpy(ptr, &r, size);
+        }
+    }
+
+    void RandomContentCheck(const Entry& entry)
+    {
+        XoRoShiRo128PlusPlus rng(entry.seed);
+        auto ptr = entry.span.data();
+        auto size = entry.span.size();
+
+        std::byte buf[8];
+        while (size >= 8) {
+            auto r = rng();
+            std::memcpy(buf, &r, 8);
+            assert(std::memcmp(buf, ptr, 8) == 0);
+            size -= 8;
+            ptr += 8;
+        }
+        if (size > 0) {
+            auto r = rng();
+            std::memcpy(buf, &r, size);
+            assert(std::memcmp(buf, ptr, size) == 0);
+        }
+    }
+
+    void Deallocate(const Entry& entry)
+    {
+        auto ptr_val = reinterpret_cast<std::uintptr_t>(entry.span.data());
+        assert((ptr_val & (entry.alignment - 1)) == 0);
+        RandomContentCheck(entry);
+        m_total_allocated -= entry.span.size();
+        m_test_resource.Deallocate(entry.span.data(), entry.span.size(), entry.alignment);
+    }
+
+    void Deallocate()
+    {
+        if (m_entries.empty()) {
+            return;
+        }
+
+        size_t idx = m_provider.ConsumeIntegralInRange<size_t>(0, m_entries.size() - 1);
+        Deallocate(m_entries[idx]);
+        if (idx != m_entries.size() - 1) {
+            m_entries[idx] = std::move(m_entries.back());
+        }
+        m_entries.pop_back();
+    }
+
+    void Clear()
+    {
+        while (!m_entries.empty()) {
+            Deallocate();
+        }
+
+        PoolResourceTester::CheckAllDataAccountedFor(m_test_resource);
+    }
+
+    void Fuzz()
+    {
+        LIMITED_WHILE(m_provider.ConsumeBool(), 10000)
+        {
+            CallOneOf(
+                m_provider,
+                [&] { Allocate(); },
+                [&] { Deallocate(); });
+        }
+        Clear();
+    }
+};
+
+
+} // namespace
+
+FUZZ_TARGET(pool_resource)
+{
+    FuzzedDataProvider provider(buffer.data(), buffer.size());
+    CallOneOf(
+        provider,
+        [&] { PoolResourceFuzzer<128, 1>{provider}.Fuzz(); },
+        [&] { PoolResourceFuzzer<128, 2>{provider}.Fuzz(); },
+        [&] { PoolResourceFuzzer<128, 4>{provider}.Fuzz(); },
+        [&] { PoolResourceFuzzer<128, 8>{provider}.Fuzz(); },
+
+        [&] { PoolResourceFuzzer<8, 8>{provider}.Fuzz(); },
+        [&] { PoolResourceFuzzer<16, 16>{provider}.Fuzz(); },
+
+        [&] { PoolResourceFuzzer<256, alignof(max_align_t)>{provider}.Fuzz(); },
+        [&] { PoolResourceFuzzer<256, 64>{provider}.Fuzz(); });
+}
diff --git a/src/test/pool_tests.cpp b/src/test/pool_tests.cpp
new file mode 100644
index 0000000000..8a07e09a44
--- /dev/null
+++ b/src/test/pool_tests.cpp
@@ -0,0 +1,190 @@
+// 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 <memusage.h>
+#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_CASE(memusage_test)
+{
+    auto std_map = std::unordered_map<int, int>{};
+
+    using Map = std::unordered_map<int,
+                                   int,
+                                   std::hash<int>,
+                                   std::equal_to<int>,
+                                   PoolAllocator<std::pair<const int, int>,
+                                                 sizeof(std::pair<const int, int>) + sizeof(void*) * 4,
+                                                 alignof(void*)>>;
+    auto resource = Map::allocator_type::ResourceType(1024);
+
+    PoolResourceTester::CheckAllDataAccountedFor(resource);
+
+    {
+        auto resource_map = Map{0, std::hash<int>{}, std::equal_to<int>{}, &resource};
+
+        // can't have the same resource usage
+        BOOST_TEST(memusage::DynamicUsage(std_map) != memusage::DynamicUsage(resource_map));
+
+        for (size_t i = 0; i < 10000; ++i) {
+            std_map[i];
+            resource_map[i];
+        }
+
+        // Eventually the resource_map should have a much lower memory usage because it has less malloc overhead
+        BOOST_TEST(memusage::DynamicUsage(resource_map) <= memusage::DynamicUsage(std_map) * 90 / 100);
+    }
+
+    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
diff --git a/src/test/validation_flush_tests.cpp b/src/test/validation_flush_tests.cpp
index 26c48eb0e0..7398091215 100644
--- a/src/test/validation_flush_tests.cpp
+++ b/src/test/validation_flush_tests.cpp
@@ -36,12 +36,12 @@ BOOST_AUTO_TEST_CASE(getcoinscachesizestate)
         BOOST_TEST_MESSAGE("CCoinsViewCache memory usage: " << view.DynamicMemoryUsage());
     };
 
-    constexpr size_t MAX_COINS_CACHE_BYTES = 1024;
+    // PoolResource defaults to 256 KiB that will be allocated, so we'll take that and make it a bit larger.
+    constexpr size_t MAX_COINS_CACHE_BYTES = 262144 + 512;
 
     // Without any coins in the cache, we shouldn't need to flush.
-    BOOST_CHECK_EQUAL(
-        chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/0),
-        CoinsCacheSizeState::OK);
+    BOOST_TEST(
+        chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/ 0) != CoinsCacheSizeState::CRITICAL);
 
     // If the initial memory allocations of cacheCoins don't match these common
     // cases, we can't really continue to make assertions about memory usage.
@@ -71,13 +71,21 @@ BOOST_AUTO_TEST_CASE(getcoinscachesizestate)
     // cacheCoins (unordered_map) preallocates.
     constexpr int COINS_UNTIL_CRITICAL{3};
 
+    // no coin added, so we have plenty of space left.
+    BOOST_CHECK_EQUAL(
+        chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes*/ 0),
+        CoinsCacheSizeState::OK);
+
     for (int i{0}; i < COINS_UNTIL_CRITICAL; ++i) {
         const COutPoint res = AddTestCoin(view);
         print_view_mem_usage(view);
         BOOST_CHECK_EQUAL(view.AccessCoin(res).DynamicMemoryUsage(), COIN_SIZE);
+
+        // adding first coin causes the MemoryResource to allocate one 256 KiB chunk of memory,
+        // pushing us immediately over to LARGE
         BOOST_CHECK_EQUAL(
-            chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/0),
-            CoinsCacheSizeState::OK);
+            chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/ 0),
+            CoinsCacheSizeState::LARGE);
     }
 
     // Adding some additional coins will push us over the edge to CRITICAL.
@@ -94,16 +102,16 @@ BOOST_AUTO_TEST_CASE(getcoinscachesizestate)
         chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/0),
         CoinsCacheSizeState::CRITICAL);
 
-    // Passing non-zero max mempool usage should allow us more headroom.
+    // Passing non-zero max mempool usage (512 KiB) should allow us more headroom.
     BOOST_CHECK_EQUAL(
-        chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/1 << 10),
+        chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/ 1 << 19),
         CoinsCacheSizeState::OK);
 
     for (int i{0}; i < 3; ++i) {
         AddTestCoin(view);
         print_view_mem_usage(view);
         BOOST_CHECK_EQUAL(
-            chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/1 << 10),
+            chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes=*/ 1 << 19),
             CoinsCacheSizeState::OK);
     }
 
@@ -119,7 +127,7 @@ BOOST_AUTO_TEST_CASE(getcoinscachesizestate)
         BOOST_CHECK(usage_percentage >= 0.9);
         BOOST_CHECK(usage_percentage < 1);
         BOOST_CHECK_EQUAL(
-            chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, 1 << 10),
+            chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes*/ 1 << 10), // 1024
             CoinsCacheSizeState::LARGE);
     }
 
@@ -131,8 +139,7 @@ BOOST_AUTO_TEST_CASE(getcoinscachesizestate)
             CoinsCacheSizeState::OK);
     }
 
-    // Flushing the view doesn't take us back to OK because cacheCoins has
-    // preallocated memory that doesn't get reclaimed even after flush.
+    // Flushing the view does take us back to OK because ReallocateCache() is called
 
     BOOST_CHECK_EQUAL(
         chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, 0),
@@ -144,7 +151,7 @@ BOOST_AUTO_TEST_CASE(getcoinscachesizestate)
 
     BOOST_CHECK_EQUAL(
         chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, 0),
-        CoinsCacheSizeState::CRITICAL);
+        CoinsCacheSizeState::OK);
 }
 
 BOOST_AUTO_TEST_SUITE_END()