Add allocator for node based containers #22702

last in first out?

gie -> give

Tested that IsMultiple() can be removed (Debian Clang 13)

test/node_allocator_tests.cpp:245:16: warning: unused function 'isMultiple' [-Wunused-function]
constexpr bool isMultiple(size_t a, size_t b)
               ^
1 warning generated.

Perhaps rule of 5 (https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rc-five, https://www.stroustrup.com/C++11FAQ.html#default)

     /**
-     * Copying a memory resource is not allowed, it is an immobile object.
+     * Copying/moving a memory resource is not allowed; it is an immobile object.
      */
     MemoryResource(const MemoryResource&) = delete;
     MemoryResource& operator=(const MemoryResource&) = delete;
+    MemoryResource(MemoryResource&&) = delete;
+    MemoryResource& operator=(MemoryResource&&) = delete;

This does not sound like a disadvantage when formulated this way?

yes I wanted to clarify that the linked list's can become relatively random access pattern into the memory, which can be slower due to lots of cache misses. I'll fix the comment

"A contains" ... what is A?

Should be just "Contains all allocated blocks of memory"

fixed in 89c62017f2a099de5353579b08f79037805ca70f

I think this comment is incorrect (this is the size of one chunk; blocks are a multiple of that).

thanks, I've updated the comment

Perhaps add a comment here explaining that the next pointer of in-use elements actually doesn't matter until it's deallocated, so it doesn't need initialization here.

I've updated the comment

As far as I can tell, this can remain 1 << 10 (1024).

In both cases, invoking the test with src/test/test_bitcoin -t validation_flush_tests -l test_suite prints CoinsTip usage percentage: 0.997634

            chainstate.GetCoinsCacheSizeState(MAX_COINS_CACHE_BYTES, /*max_mempool_size_bytes*/ 1 << 10), // 1024

Thanks again, I've squashed your review and rebased

            // map_a now uses mr_b, since propagate_on_container_move_assignment is std::true_type

will this be handled correctly in the case of overflow?

I think p.n cannot overflow here. It is initialized to 0, and since I've specified the number of iterations each measurement will have exactly 50000 iterations. I do this so I can be sure each measurement has exactly the same number of calls to map.clear();, which gives more stable benchmark results. Nanobench defaults to 11 measurements, so in total n will reach 550000.

typo: "puts p back into the free list if it was..."

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

m_untouched_memory_end is always m_allocated_blocks.back() + alloc_size. Seems like it would be safer and less confusing to drop this unnecessary variable. Safer to avoid possibility of bugs where object gets into an inconsistent state. Less confusing to need one less variable to understand this.

I'd prefer to keep that member variable because it is used in Allocate(size_t n) which should be really fast. I think it would be a bit slower with additional indirections. Also I currently don't need special handling for when nothing is allocated yet because both pointers are initialized to nullptr

If you prefer to keep this variable, I think for clarity it should have a comment like

// m_untouched_memory_end member variable is redundant, and is always equal to (m_allocated_pools.back().get() + POOL_SIZE_BYTES) whenever it is accessed, but m_untouched_memory_end caches this for clarity and efficiency.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

Why are individual allocations sometimes called "chunks" and sometimes called "nodes"? Can we drop "chunk" terminology and just refer to individual allocations consistently as nodes?

Personally I would love to drop the custom chunk/node/block terms entirely, just call the allocator a fixed size allocator, call the allocations allocations, and call the blocks pools. Just IMO, though.

I also wasn't really sure what terms to use. I'll try to clean that up.

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

Strictly speaking, keeping ChunkNode structs aligned shouldn't be required, because we could memcpy them to and from the empty spaces instead of static_casting them. But I guess not taking the max alignment is unlikely to save any space, if we already need to use the max size anyway?

In any case, it would be good to have sentence here to say why this is using ChunkNode alignment, since it seems like ChunkNode alignment shouldn't need to matter in principle.

I prefer to keep the alignment here, as far as I remember some systems can produce very slow code when using memcpy without the alignment requirement. It shouldn't matter for x86 though. I'll add a comment

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

It seems like it would be more ideal for chunk_size_bytes to be a compile time constant (template parameter) instead of a runtime constant (class member), since in all cases can be known at compile time, and the fact that it isn't mean that other things like size of a block can't be constant either. Not being able to easily compute size of the block (it requires runtime multiplication and division) I think indirectly led to m_untouched_memory_end being added unnecessarily. Not having a compile-time block size also appears to be a reason m_allocated_blocks is using void* and raw new/deletes instead of safer types like std::unique_ptr and std::array

Making this const would also have more minor benefit of improving clarity by being able to declare useful constants up front and not have things like / m_chunk_size_bytes * m_chunk_size_bytes various places in the code.

I've tried to make it a template argument before, but couldn't get it to compile. But I've tried it again and figured it out now, the main issue that I missed is that the Allocator then needs to have a struct rebind for this to work. (this is described in a little footnote here: https://en.cppreference.com/w/cpp/named_req/Allocator#cite_note-2 The rebind is not optional because the second template argument will be a size_t, and not a template type)

done in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

This could go away using std::unique_ptr

Right! I'll switch to using std::unique_ptr<char[]>.

Done in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

Exposing this method seems pretty dubious. Maybe do friend class MemoryResourceTester; instead and move it to test code. My concerns here are verbosity of this header, and temptation for someone to call this inappropriately in some performance counter or log statement. If this should be exposed publicly, maybe it should have a name like CountFreeChunks so it doesn't look like an innocuous accessor method.

That's a good idea, then I can move NumFreeChunks and NumBlocks to the test class because it shouldn't be needed anywhere else

done in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

Suggestion not for here, but I wouldn't mind some other PR adding simple CEIL_DIV, ROUND_UP util macros and using them places like this.

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

This should be removed since it's true by definition that sizeof returns char sized units and sizeof(char) is 1. Size of a char can vary (it is CHAR_BIT bits which is usually 8), but I don't think any code here depends on a particular char size.

done in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

I think this should be named MaxBlockSizeBytes instead of BlockSizeBytes since actual block size may be slightly less depending on alignment. Also convention is to use snake case for variable/constant names and camel case for type/function names, so maybe would be good MAX_BLOCK_SIZE_BYTES to also make it more obvious this is a compile-time constant.

When refactoring to use compile time NODE_SIZE_BYTES (renamed to ALLOCATION_SIZE_BYTES) I can now calculate the correct blocksize right here.

done in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

This doesn't doesn't really have anything to do with MemoryResource, and I'd think it should be part of the Allocator paragraph not the MemoryResource one. I'd reshuffle this design section a little bit and put MemoryResource paragraph first, Allocator paragraph second, and information about determining the node sizes third.

reshuffled in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

Curious, when does rebinding happen? Maybe say something about when/if this would happen in a sentence here.

The C++ API for allocators is a bit stupid, it actually happens all the time. No allocation actually ever happens with the std::pair<const Key, Value> type, the container's rebind to the internal node type, possibly to some control structure, and for unordered_map to the underlying array type. I'll add a comment

comment added in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

These construct methods seem sketchy and prone to misuse. Can we drop these? The one place these are called is in ReallocateCache and it should be possible to eliminate them there by keeping the existing placement new:

::new (&cacheCoinsMemoryResource) MemoryResource{CCoinsMapFactory::CreateMemoryResource()};
::new (&cacheCoins) CCoinsMap{CCoinsMapFactory::CreateContainer(&cacheCoinsMemoryResource)};

Good idea, I didn't think about writing it that way

done in 89c62017f2a099de5353579b08f79037805ca70f

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

I think it makes sense to add ReallocateCache cache (though I would be curious if someone knows a reason it wasn't added here initially).

But if we are going to add this here I think we should remove the other ReallocateCache() call in validation.h which is now redundant, and make the ReallocateCache method private so it is not uselessly confusing.

ReallocateCache is now necessary here, because Flush is triggered when memory is full, and with the node_allocator clear() does not free any memory the memory usage would stay constant. It was not necessary before because clear() already deallocated all of the nodes and only kept the memory for the unordered_map's internal indexing array.

Right! CoinsTip().ReallocateCache(); in validation.cpp is now unnecessary. Good catch.

Done that in a separate commit in 1e4a65b21c70ee745a8ae02c3af109f4f5e16422

In commit "Add allocator for node based containers" (952c37a31c39b7acdb5ab2634a354a1c548708a2)

Just so this information is easily accessible, can you add a comment about how this is tested for accuracy or where the tests can be found?

Added in a91b603

To confirm, replacing unordered_node<X> with std::pair<X, void*> is just a simplification for consistent style, not a change in behavior?

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

exactly, I found it simpler & less code to just use std::pair<...> than writing many unordered_node implementations.

Filling this fake transaction just to throw it all away and call tx.GetHash seems unnecessarily complicated. Could just construct the outpoint with any uint256 instead of a real transaction hash

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

right! I just copied that code without really thinking too much about it. I'll clean that up.

Done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Would be good to replace std::pair<const Key, Value> with ContainerType::value_type to make this more obvious.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Could be shortened to NodeSize<ContainerType>

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Split that code up into two methods in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Would s/destroyed by the Allocator/freed/ to be clear this happens independently of the allocator, and whether or not it is used.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Should drop "which is given in the constructor", since it's not true anymore and is not a really relevant detail describing the high level behavior here.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

It is unexpected to mention std::unordered_map here when everything above is talking about containers generally. Also unclear what "all cases" is referring to. Would drop last two sentences and just say something like:

Using node_allocator with a standard container types like std::list, std::unordered_map requires knowing node sizes of those containers which are non-standard implementation details. The \ref memusage::NodeSize trait and \ref node_allocator::Factory class can be used to help with this.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

It seems like it would be better to make this a static_assert than an if constexpr. I also don't see a reason for this method to take an n argument. Switching to static_assert and dropping n argument here would have the following advantages:

• It would simplify this method and remove footguns where calling it incorrectly could result in bad runtime behavior instead of a compile time errors.
• Moving the size and n checks to Allocator::allocate instead of MemoryResource::Allocate would allow more flexiblility like falling back to a nested allocator like std::allocator instead of global ::operator new (In theory this would even allow chaining different sized node_allocator::Allocator types together so an allocator could transparently direct diffferent sized allocations to different sized pools, and fall back to std::allocator if no pool fits)

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Hm, I don't really want to add a counter for m_free_allocations but also don't want to iterate through the freelist. I think it's ok to keep the MemoryResource::DynamicMemoryUsage as it is because all that memory is the responsibility of that class. I got rid of the if constexpr though in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5.

Would expect FreeList* instead of void*. void* could make sense if these were ever pointers to something besides FreeLists, but if next is ever non-null it is always pointing to a FreeList.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Reading through the code again I now think that I actually have undefined behavior: I'm basically reinterpret_casting T* to FreeList*, and both types are completely unrelated, so according to the type aliasing rules accessing this is undefined behavior:

Performing a class member access that designates a non-static data member or a non-static member function on a glvalue that does not actually designate an object of the appropriate type - such as one obtained through a reinterpret_cast - results in undefined behavior

See https://en.cppreference.com/w/cpp/language/reinterpret_cast

This can be fixed by using memcpy, and then I can also relax the alignment.

I guess I didn't have enough coffee yet. I can't use reinterpret_cast, but since the T was already destroyed, I can use placement new in that memory to create the FreeList. No reinterpret_cast needed at all.

MemoryResource::Deallocate now uses pacement new in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5, and uses the returned pointer.

Again seems like type should be FreeList* not void*

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5. I also changed the m_untouched_memory_iterator and m_untouched_memory_end from void* to char*.

Having this special case to handle shared memory resources seems clunky, especially because it adds a circular dependency between memusage and node_allocator types, instead of letting node_allocator have a one-way dependency on memusage.

Also it seems like awkward accounting to have dynamic usage of containers not actually include the memory they are using, and for all the cost of all memory be attributed to the memory resource with no distinction between allocated and unallocated memory.

Another way of doing the accounting would be to keep the containers attributed memory usage unchanged, and just attribute size of unallocated memory to MemoryResource, instead of size of allocated+unallocated memory.

Specifically the suggestion would be to:

• Drop the if constexpr special case code here and circular dependency of memusage on node_allocator
• Change definition of MemoryResource::DynamicMemoryUsage to only include unallocated space not total space by:
  • Subtracting POOL_SIZE_BYTES * m_allocated_pools.size() from current value
  • Adding m_untouched_memory_end - m_untouched_memory_iterator + (length of m_free_allocations list) * ALLOCATION_SIZE_BYTES
  • Maybe adding a counter variable to get length of m_free_allocations list efficiently

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

I've played with this for a while now, but it doesn't work that way because in memusage.h I still need to know if the node_allocator is used for a container, because the node sizes are different. For the standard std::unordered_map I need to use memusage::MallocUsage for the nodes, and for node_allocator I have use the node size directly. So I need at least a forward declaration of node_allocator::Allocator. But that is fine I guess, I'll create a forward declaration then there's no circular dependency any more.

Also I'll split up NodeSize calculation into a separate independent file that both memusage and the allocator can use, so there are no circular dependency for that too.

I don't see a reason to tie this to unordered_map. Would suggest renaming this from UnorderedMapFactory to just Factory, taking a typename Container template argument and calling NodeSize<Container>::Value() below

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

This CreateContainer method seems like a pretty superfluous wrapper around the ContainerType constructor. Maybe we don't need a factory class at all and can just provide some template typedefs for ccoins to use:

template<typename BaseContainer>
using MemoryResourceType = MemoryResource<NodeSize<BaseContainer>::Value()>;

template<typename BaseContainer>
using AllocatorType = Allocator<BaseContainer::value_type, NodeSize<BaseContainer>::Value()>;

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

I'd like to keep the CreateContainer here because otherwise constructing an unordered_map is quite a lot of non-obvious code, like first argument is always 0, then create a temporary hash of the correct typ, equals, and finally the Allocator.

Putting this comment next to this typedef is a little confusing, because the comment is describing simulating pairs which simulate nonstandard internal data structures, but this pair isn't really simulating anything, since it's actually part of standard container definition.

Would suggest either moving comment, or only using std::pair for simulated pairs, or doing both things. By only using std::pair for simulated pairs, I mean something like:

using ContainerType = std::unordered_map<Key, Value, Hash, Equals, Alloc>;
using ValueType = typename ContainerType::value_type;

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Moved comment in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Can you use #elif above to get rid of this nesting and just make a flat list of cases?

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

In practice, this is probably fine, but logically and in theory, it seems like there is a bug here because this is only using node size to determine allocation size, ignoring node alignment and FreeList size and alignment. It seems like this should be using the RequiredAllocationSizeBytes function to take these things into account, like:

diff --git a/src/support/allocators/node_allocator.h b/src/support/allocators/node_allocator.h
index 7ff94d39700..5b667ca99b8 100644
--- a/src/support/allocators/node_allocator.h
+++ b/src/support/allocators/node_allocator.h
@@ -385,7 +385,8 @@ template <typename Key, typename Value, typename Hash = std::hash<Key>, typename
 class UnorderedMapFactory
 {
 public:
-    static constexpr size_t ALLOCATION_SIZE_BYTES = memusage::NodeSize<std::unordered_map<Key, Value, Hash, Equals>>::Value();
+    static constexpr size_t ALLOCATION_SIZE_BYTES = detail::RequiredAllocationSizeBytes<typename
+                                                    memusage::NodeSize<std::unordered_map<Key, Value, Hash, Equals>>::NodeType>();
     using MemoryResourceType = MemoryResource<ALLOCATION_SIZE_BYTES>;
     using AllocatorType = Allocator<std::pair<const Key, Value>, ALLOCATION_SIZE_BYTES>;
     using ContainerType = std::unordered_map<Key, Value, Hash, Equals, AllocatorType>;
diff --git a/src/memusage.h b/src/memusage.h
index fd781f77bf5..af1f33963d6 100644
--- a/src/memusage.h
+++ b/src/memusage.h
@@ -163,35 +163,38 @@ struct NodeSize {
 // with multiple configurations (alignments, noexcept hash, node sizes).
 template <typename Key, typename V, typename Hash, typename Equals, typename Allocator>
 struct NodeSize<std::unordered_map<Key, V, Hash, Equals, Allocator>> {
-    [[nodiscard]] static constexpr size_t Value()
-    {
         // libstdc++, libc++, and MSVC implement the nodes differently. To get the correct size
         // with the correct alignment, we can simulate that with accordingly nested std::pairs.
         using ValueType = std::pair<const Key, V>;
+        using NodeType =
 
 #if defined(_MSC_VER)
         // list node contains 2 pointers and no hash; see
         // https://github.com/microsoft/STL/blob/main/stl/inc/unordered_map and
         // https://github.com/microsoft/STL/blob/main/stl/inc/list
-        return sizeof(std::pair<std::pair<void*, void*>, ValueType>);
+                      std::pair<std::pair<void*, void*>, ValueType>
 #else
 
 #if defined(_LIBCPP_VERSION) // defined in any C++ header from libc++
         // libc++ always stores hash and pointer in the node
         // see https://github.com/llvm/llvm-project/blob/release/13.x/libcxx/include/__hash_table#L92
-        return sizeof(std::pair<ValueType, std::pair<size_t, void*>>);
+                      std::pair<ValueType, std::pair<size_t, void*>>
 #else
+        std::conditional_t<
         // libstdc++ doesn't store hash when its operator() is noexcept;
         // see hashtable_policy.h, struct _Hash_node
         // https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a05689.html
-        if (noexcept(std::declval<Hash>()(std::declval<const Key&>()))) {
-            return sizeof(std::pair<void*, ValueType>);
-        } else {
+            noexcept(std::declval<Hash>()(std::declval<const Key&>())),
+                          std::pair<void*, ValueType>,
             // hash is stored along ValueType, and that is wrapped with the pointer.
-            return sizeof(std::pair<void*, std::pair<ValueType, size_t>>);
-        }
+                          std::pair<void*, std::pair<ValueType, size_t>>
+        >
 #endif
 #endif
+    ;
+    [[nodiscard]] static constexpr size_t Value()
+    {
+        return sizeof(NodeType);
     }
 };
 

Fix above is trying to be minimal but it could be cleaned up more by renaming NodeSize to something like ContainerTraits and dropping the Value() method.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Thanks, and I agree that is the correct way to do it. I don't think it was a bug though, at least the worst thing that could happen was that it falls back to default ::operator new, but for that there are unit tests too.

Done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

I'm curious why this is phrased negatively. Is there some downside to swapping allocators when containers are swapped? Swapping everything in the container when the container is swapped seems like the obvious and good thing to do.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

I'll reword my comment, I meant that the default for propagate_on_container_swap is std::false_type, which is bad because that's undefined behavior. I'll change the comment:

    /**
     * The default for propagate_on_container_swap is std::false_type. This is bad,because swapping
     * two containers with unequal allocators but not propagating the allocator is undefined
     * behavior! Obviously, we want so swap the allocator as well, so we set that to true.
     *
     * see https://www.foonathan.net/2015/10/allocatorawarecontainer-propagation-pitfalls/
     */

changed in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Again wondering why it's phrased like we "have to" do these things. Is there some downside, or some particular way this is not ideal for our use-case?

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

no real downside, it's just that because the allocator has a state it also has to be propagated.

This is interesting. It seems to suggest about the concern that if "the object size gets computed incorrectly by a future libstdc++ change... we'll silently fall back to old performance" that in theory we could detect at compile time, not runtime, whether a container implementation was calling Allocator::allocate with an unexpected T size for that implementation.

But it doesn't seem worth implementing this if it requires lots of template trickery or tracking down compile errors on different platforms, especially if NodeSize unit test coverage works OK practically.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Probably should use snake case variable names

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Might suggest calling this something like CHECK_NUMS_FREES_POOLS just so it's easier to remember what the arguments are to this guy below (and what it is doing).

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Writing this comment feels like reaching new depths of pedantry, but it doesn't seem guaranteed that void* is bigger than char. It can't be smaller, because sizeof(char) is always 1, but if they are the same size, then the test isn't really meaningful. I guess my suggestion would be to replace void* with a type guaranteed to be bigger like std::pair<char, char>.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Could do a stricter check?

BOOST_CHECK(node_allocator::MemoryResourceTester::NumFreeAllocations(mr) >=
                    num_free_allocations + 1000);

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

stricter check in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Can you add "because its contents were moved to m" to this comment? I was a little confused by what this was doing at first, and the extra hint would have helped.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Why only >50 here, not >=1000 again?

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

it sure can be made stricter :+1:

stricter in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

It seems like another thing these tests could be checking for aside from number of free allocations and number of pools is amount of slack space the last pool (untouched_end - untouched_iterator)/alloc size.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

I get that it makes sense to have test coverage for std::unordered_map, but I feel like it would be if ideal if unordered_map vagaries with IN_RANGE(1U, 2U) (101U, 102U) soft checks were confined to ~one test, and all other tests used a simpler container like std::list that was easier to think about and had better defined allocation behavior, so the tests would be easier to understand, less fragile, and in some places more meaningful.

Not saying you should rewrite all tests, but this might be something to think about doing selectively or for new tests.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Amount of code duplication between different_memoryresource_* tests is a little eye-watering. This seems like a place where BOOST_FIXTURE_TEST_CASE and a test fixture with unordered_map m_map_a and optional<unordered_map> m_map_b members and some helper methods would cut down duplication and make the checks more human readable.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

deduplicated in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

Could all of this just be

template<size_t SIZE, size_t ALIGN>
struct alignas(ALIGN) A {
    char data[SIZE];
};

?

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Ah, I didn't know that it's possible to use a template argument in alignas, that simplifies things :+1:

done in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5, and renamed the struct to AlignedSize

IMO would be good to move these A8 and bigger checks out of the preprocessor block to deduplicate and make it obvious these are all the same whether you have have 4 byte or 8 byte pointers.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

deduplicated in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5. Also I have added a

static_assert(__STDCPP_DEFAULT_NEW_ALIGNMENT__ >= std::alignment_of_v<T>, "make sure AllocatePool() aligns correctly");

Into Allocate, because actually the 16 byte alignments are not allowed when the pools are not correctly aligned as well.

Suggest writing /* not noexcept */ to make comment intent more plain.

Also, I have only the vaguest understanding of noexcept but could this be noexcept(false)?

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

noexcept(false) and writing nothing is equivalent

The hidden mystery of node_allocator_tests is revealed! This is reason for all the IN_RANGE(101, 102) stuff :arrow_up:. I wish there was a spoiler tag.

(Version: a91b6032f037ab1a26ac4baa761e809fbfeb1bdd)

Maybe I shouldn't have but that reveal at the very last place where that CHECK_IN_RANGE is used :sweat_smile:

Moved that comment up in e2a5547f12e5da2718ba17ebac5d5aeb5a2e24d5

In commit "Correctly calculate node size for std::unordered_map" (119c3b90d6b7e9b81915a09f5ca5370f2ef1ea57)

Might be good to replace this with a loop and verify there is exactly 1 entry with 123 allocations (and the expected size), instead of at least 1.

This is unfortunately not the case on Windows, there the allocator is used to allocate one control structure as well

In commit "Add allocator for node based containers" (96d8e33acaa079491403d8e8afa6709978dec205)

Would drop "which is given in constructor" (no longer true)

In commit "Add allocator for node based containers" (96d8e33acaa079491403d8e8afa6709978dec205)

Purpose of this test could be a made a little clearer with comment like "Verify that MemoryResource specialized for a larger char pair type will do smaller single char allocations as well"

In commit "Add allocator for node based containers" (96d8e33acaa079491403d8e8afa6709978dec205)

Test is no longer using void*. Probably would just say // freelist is used or drop comment.

In commit "Make use of node_allocator in CCoinsMap" (66f745394ddfb546b9d0d29fe764110944dea158)

Extra punctuation here s/cacheCoins' MemoryResource/cacheCoinsMemoryResource/

In commit "Add allocator for node based containers" (96d8e33acaa079491403d8e8afa6709978dec205)

It doesn't seem like this static_assert is verifying anything related to our code. It's not calling any of our own functions, just verifying a relationship between __STDCPP_DEFAULT_NEW_ALIGNMENT__ and std::alignment_of. Also assert message doesn't seem to make sense. Check might make more sense inside the RequiredAllocationSizeBytes function than outside here.

I think that check is necessary. In AllocatePool I'm doing new char[POOL_SIZE_BYTES], and this uses __STDCPP_DEFAULT_NEW_ALIGNMENT__ as the alignment for the pool's memory. So if you try to use the node_allocator with a type that has an alignment > __STDCPP_DEFAULT_NEW_ALIGNMENT__ this is a problem, even when detail::RequiredAllocationSizeBytes is done correctly. I had a test case that used 16 byte alignment, and with that static_assert that test failed on a 32bit machine.

re: #22702 (review)

I think that check is necessary. In AllocatePool I'm doing new char[POOL_SIZE_BYTES]

Maybe can move check closer to where it's needed

<details><summary>Diff</summary><p>

diff --git a/src/support/allocators/node_allocator/memory_resource.h b/src/support/allocators/node_allocator/memory_resource.h
index f4ba0138924..cf956da318f 100644
--- a/src/support/allocators/node_allocator/memory_resource.h
+++ b/src/support/allocators/node_allocator/memory_resource.h
@@ -101,7 +101,6 @@ public:
     [[nodiscard]] T* Allocate()
     {
         static_assert(ALLOCATION_SIZE_BYTES == detail::RequiredAllocationSizeBytes<T>());
-        static_assert(__STDCPP_DEFAULT_NEW_ALIGNMENT__ >= std::alignment_of_v<T>, "make sure AllocatePool() aligns correctly");
 
         if (m_free_allocations) {
             // we've already got data in the free list, unlink one element
@@ -120,7 +119,7 @@ public:
         // than what has been malloc'ed.
         if (m_untouched_memory_iterator == m_untouched_memory_end) {
             // slow path, only happens when a new pool needs to be allocated
-            AllocatePool();
+            AllocatePool<T>();
         }
 
         // peel off one allocation from the untouched memory. The next pointer of in-use
@@ -164,8 +163,10 @@ private:
     /**
      * Allocate one full memory pool which is used to carve out allocations.
      */
+    template <typename T>
     void AllocatePool()
     {
+        static_assert(__STDCPP_DEFAULT_NEW_ALIGNMENT__ >= std::alignment_of_v<T>, "make sure alignment is compatible with T");
         m_allocated_pools.emplace_back(new char[POOL_SIZE_BYTES]);
         m_untouched_memory_iterator = m_allocated_pools.back().get();
         m_untouched_memory_end = m_untouched_memory_iterator + POOL_SIZE_BYTES;

</p>

I think I'd prefer to keep the static_assert at the Allocate entry point, because currently AllocatePool doesn't need to know the type T. I guess it's more a matter of style :)

I'm somewhat surprised that the compiler/language doesn't automatically declare a function non-throwing if all its calls are declared to be noexcept. Are you sure that's not a risk here?

I think this is safe, the standard says that only a handful functions are implicitly nothrowing: default ctor and dtor, move & copy ctor, move & assignment operator. There has been a proposal for a noexcept(auto) to add implicitly nothrowing anywhere else, but it seems that there were too many problems.

In commit "Correctly calculate node size for std::unordered_map" (119c3b90d6b7e9b81915a09f5ca5370f2ef1ea57)

I think it would make more sense to move this class back to src/memusage.h, or to a new src/memusage_nodesize.h file, instead of making it part of node_allocator. This is a helper class for figuring out memory usage of a standard container, so functionally it is more related to memusage than node_allocator. Memusage needs this to function, while node_allocator::Allocator and node_allocator::MemoryResource are both usable without it. Also, In the future, we may also want to experiment with writing new allocators, and it would be nice if they could reuse this NodeSize class without having to reinvent it or depend on node_allocator themselves. Also, combined with other suggestions, moving this class out of node_allocator would allow us to break the node_allocator <-> memusage cyclic dependency and have node_allocator just depend on memusage in one direction.

(Moving this class out of node_allocator could also let you split off the first two commits of this PR into their own PR so this PR could be smaller, even though I do think this PR is small enough and wouldn't see a need for that.)

Nit: I think with C++17, this can be a constexpr static member variable, rather than a function (static constexpr size_t VALUE = sizeof(SimulatedNodeType);).

In commit "Add allocator for node based containers" (96d8e33acaa079491403d8e8afa6709978dec205)

I still think it's unfortunate to be adding this memusage specialization when it is not necessary. I don't like how it:

• Makes memusage.h depend node_allocator, when the job of memusage is just to tell us about memory usage of standard types, and it shouldn't need to be referencing a particular specialized allocator.
• Redefines the concept of memory usage for this one unordered_map+node_allocator container to not consider memory allocated by the container to be "used" by the container, even though the container allocated that memory, and is still responsible for deallocating (if not freeing) it.
• Will require new specializations of map+node_allocator or list+node_allocator to be added here if node_allocator is used with other map or list containers in the future.

I think code can be simpler, definition of "usage" can be more consistent, and cyclic dependencies and special cases can be removed using earlier suggestions from #22702 (review), and only downside would be adding a counter variable. On top of the current PR, changes would look like:

<details><summary>Diff</summary><p>

diff --git a/src/Makefile.am b/src/Makefile.am
index b39d03fe8cb..9d09682e243 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -217,7 +217,6 @@ BITCOIN_CORE_H = \
   shutdown.h \
   signet.h \
   streams.h \
-  support/allocators/node_allocator/allocator_fwd.h \
   support/allocators/node_allocator/allocator.h \
   support/allocators/node_allocator/factory.h \
   support/allocators/node_allocator/memory_resource.h \
@@ -575,7 +574,6 @@ libbitcoin_util_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
 libbitcoin_util_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 libbitcoin_util_a_SOURCES = \
   support/lockedpool.cpp \
-  support/allocators/node_allocator/memory_resource.cpp \
   chainparamsbase.cpp \
   clientversion.cpp \
   compat/glibcxx_sanity.cpp \
diff --git a/src/memusage.h b/src/memusage.h
index bc20ee4052c..b9faff9b2d9 100644
--- a/src/memusage.h
+++ b/src/memusage.h
@@ -7,7 +7,6 @@
 
 #include <indirectmap.h>
 #include <prevector.h>
-#include <support/allocators/node_allocator/allocator_fwd.h>
 #include <support/allocators/node_allocator/node_size.h>
 
 #include <stdlib.h>
@@ -163,21 +162,13 @@ static inline size_t DynamicUsage(const std::unordered_set<X, Y>& s)
     return MallocUsage(sizeof(unordered_node<X>)) * s.size() + MallocUsage(sizeof(void*) * s.bucket_count());
 }
 
-template <typename Key, typename Value, typename Hash, typename Equals>
-static inline size_t DynamicUsage(const std::unordered_map<Key, Value, Hash, Equals>& m)
+template <typename Key, typename Value, typename Hash, typename Equals, typename Alloc>
+static inline size_t DynamicUsage(const std::unordered_map<Key, Value, Hash, Equals, Alloc>& m)
 {
-    auto node_size = node_allocator::NodeSize<std::unordered_map<Key, Value, Hash, Equals>>::Value();
+    auto node_size = node_allocator::NodeSize<std::unordered_map<Key, Value, Hash, Equals, Alloc>>::Value();
     return MallocUsage(node_size) * m.size() + MallocUsage(sizeof(void*) * m.bucket_count());
 }
 
-template <typename Key, typename Value, typename Hash, typename Equals, typename AllocT, size_t AllocS>
-static inline size_t DynamicUsage(const std::unordered_map<Key, Value, Hash, Equals, node_allocator::Allocator<AllocT, AllocS>>& m)
-{
-    // Since node_allocator is used, the memory of the nodes are the MemoryResource's responsibility and
-    // won't be added here. Also multiple maps could use the same MemoryResource.
-    return MallocUsage(sizeof(void*) * m.bucket_count());
-}
-
 }
 
 #endif // BITCOIN_MEMUSAGE_H
diff --git a/src/support/allocators/node_allocator/allocator.h b/src/support/allocators/node_allocator/allocator.h
index 778471bb20b..c728ab8638a 100644
--- a/src/support/allocators/node_allocator/allocator.h
+++ b/src/support/allocators/node_allocator/allocator.h
@@ -5,7 +5,6 @@
 #ifndef BITCOIN_SUPPORT_ALLOCATORS_NODE_ALLOCATOR_ALLOCATOR_H
 #define BITCOIN_SUPPORT_ALLOCATORS_NODE_ALLOCATOR_ALLOCATOR_H
 
-#include <support/allocators/node_allocator/allocator_fwd.h>
 #include <support/allocators/node_allocator/memory_resource.h>
 
 #include <cstdint>
diff --git a/src/support/allocators/node_allocator/allocator_fwd.h b/src/support/allocators/node_allocator/allocator_fwd.h
deleted file mode 100644
index e3fa0ddd889..00000000000
--- a/src/support/allocators/node_allocator/allocator_fwd.h
+++ /dev/null
@@ -1,17 +0,0 @@
-// Copyright (c) 2021 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_NODE_ALLOCATOR_ALLOCATOR_FWD_H
-#define BITCOIN_SUPPORT_ALLOCATORS_NODE_ALLOCATOR_ALLOCATOR_FWD_H
-
-#include <cstddef>
-
-namespace node_allocator {
-
-template <typename T, size_t ALLOCATION_SIZE_BYTES>
-class Allocator;
-
-} // namespace node_allocator
-
-#endif // BITCOIN_SUPPORT_ALLOCATORS_NODE_ALLOCATOR_ALLOCATOR_FWD_H
diff --git a/src/support/allocators/node_allocator/memory_resource.cpp b/src/support/allocators/node_allocator/memory_resource.cpp
deleted file mode 100644
index 368752fa2b9..00000000000
--- a/src/support/allocators/node_allocator/memory_resource.cpp
+++ /dev/null
@@ -1,12 +0,0 @@
-#include <support/allocators/node_allocator/memory_resource.h>
-
-#include <memusage.h>
-
-namespace node_allocator::detail {
-
-size_t DynamicMemoryUsage(size_t pool_size_bytes, std::vector<std::unique_ptr<char[]>> const& allocated_pools)
-{
-    return memusage::MallocUsage(pool_size_bytes) * allocated_pools.size() + memusage::DynamicUsage(allocated_pools);
-}
-
-} // namespace node_allocator::detail
diff --git a/src/support/allocators/node_allocator/memory_resource.h b/src/support/allocators/node_allocator/memory_resource.h
index f4ba0138924..e60e847c86d 100644
--- a/src/support/allocators/node_allocator/memory_resource.h
+++ b/src/support/allocators/node_allocator/memory_resource.h
@@ -8,6 +8,8 @@
 #include <utility>
 #include <vector>
 
+#include <memusage.h>
+
 #ifndef BITCOIN_SUPPORT_ALLOCATORS_NODE_ALLOCATOR_MEMORY_RESOURCE_H
 #define BITCOIN_SUPPORT_ALLOCATORS_NODE_ALLOCATOR_MEMORY_RESOURCE_H
 
@@ -38,12 +40,6 @@ template <typename T>
     return ((size_max + alignment_max - 1U) / alignment_max) * alignment_max;
 }
 
-/**
- * Calculates dynamic memory usage of a MemoryResource. Not a member of MemoryResource so we can implement this
- * in a cpp and don't depend on memusage.h in the header.
- */
-[[nodiscard]] size_t DynamicMemoryUsage(size_t pool_size_bytes, std::vector<std::unique_ptr<char[]>> const& allocated_pools);
-
 } // namespace detail
 
 /**
@@ -102,6 +98,7 @@ public:
     {
         static_assert(ALLOCATION_SIZE_BYTES == detail::RequiredAllocationSizeBytes<T>());
         static_assert(__STDCPP_DEFAULT_NEW_ALIGNMENT__ >= std::alignment_of_v<T>, "make sure AllocatePool() aligns correctly");
+        ++m_allocations;
 
         if (m_free_allocations) {
             // we've already got data in the free list, unlink one element
@@ -138,6 +135,7 @@ public:
     void Deallocate(void* p) noexcept
     {
         static_assert(ALLOCATION_SIZE_BYTES == detail::RequiredAllocationSizeBytes<T>());
+        --m_allocations;
 
         // put it into the linked list.
         //
@@ -150,11 +148,11 @@ public:
     }
 
     /**
-     * Calculates bytes allocated by the memory resource.
+     * Calculates number of bytes allocated to the memory resource minus number of bytes allocated from the memory resource.
      */
     [[nodiscard]] size_t DynamicMemoryUsage() const noexcept
     {
-        return detail::DynamicMemoryUsage(POOL_SIZE_BYTES, m_allocated_pools);
+        return memusage::MallocUsage(POOL_SIZE_BYTES) * m_allocated_pools.size() + memusage::DynamicUsage(m_allocated_pools) - ALLOCATION_SIZE_BYTES * m_allocations;
     }
 
 private:
@@ -171,6 +169,9 @@ private:
         m_untouched_memory_end = m_untouched_memory_iterator + POOL_SIZE_BYTES;
     }
 
+    //! Number of current allocations.
+    size_t m_allocations = 0;
+
     //! Contains all allocated pools of memory, used to free the data in the destructor.
     std::vector<std::unique_ptr<char[]>> m_allocated_pools{};
 

</p></details>

Thanks for the patch! This makes discussion a lot easier. I think there's one bug in it, this now overestimates memory usage. In memusage.h all maps are now calculated like this:

return MallocUsage(node_size) * m.size() + MallocUsage(sizeof(void*) * m.bucket_count());

To correct for the incorrectly added MallocUsage(node_size) * m.size() it should be memoryusage::MallocUsage(ALLOCATION_SIZE_BYTES) * m_allocations. That should be correct in most cases, but it might not be when RequiredAllocationSizeBytes<typename NodeSize...> (in factory.h) gives a different result than the NodeSize. The only way to do this correctly is to also pass the result of NodeSize to the MemoryResource, but this complicates things.

I also don't like that in most cases memoryresource.DynamicMemoryUsage() will return a negative number (causing size_t underflow) to correct for the overestimation in memusage. This will happen whenever the overestimation is large enough.

re: #22702 (review)

Thanks for the patch! This makes discussion a lot easier. I think there's one bug in it [...]

That's a good catch, but there is an easier fix for for that bug. Space internally wasted by MemoryResource should count towards MemoryResource usage. The fix actually simplifies code even more

<details><summary>Diff</summary><p>

diff --git a/src/support/allocators/node_allocator/memory_resource.h b/src/support/allocators/node_allocator/memory_resource.h
index e60e847c86d..c1bf680e071 100644
--- a/src/support/allocators/node_allocator/memory_resource.h
+++ b/src/support/allocators/node_allocator/memory_resource.h
@@ -98,7 +98,7 @@ public:
     {
         static_assert(ALLOCATION_SIZE_BYTES == detail::RequiredAllocationSizeBytes<T>());
         static_assert(__STDCPP_DEFAULT_NEW_ALIGNMENT__ >= std::alignment_of_v<T>, "make sure AllocatePool() aligns correctly");
-        ++m_allocations;
+        m_allocated += sizeof(T);
 
         if (m_free_allocations) {
             // we've already got data in the free list, unlink one element
@@ -135,7 +135,7 @@ public:
     void Deallocate(void* p) noexcept
     {
         static_assert(ALLOCATION_SIZE_BYTES == detail::RequiredAllocationSizeBytes<T>());
-        --m_allocations;
+        m_allocated -= sizeof(T);
 
         // put it into the linked list.
         //
@@ -152,7 +152,7 @@ public:
      */
     [[nodiscard]] size_t DynamicMemoryUsage() const noexcept
     {
-        return memusage::MallocUsage(POOL_SIZE_BYTES) * m_allocated_pools.size() + memusage::DynamicUsage(m_allocated_pools) - ALLOCATION_SIZE_BYTES * m_allocations;
+        return memusage::MallocUsage(POOL_SIZE_BYTES) * m_allocated_pools.size() + memusage::DynamicUsage(m_allocated_pools) - m_allocated;
     }
 
 private:
@@ -169,8 +169,8 @@ private:
         m_untouched_memory_end = m_untouched_memory_iterator + POOL_SIZE_BYTES;
     }
 
-    //! Number of current allocations.
-    size_t m_allocations = 0;
+    //! Number of bytes allocated.
+    size_t m_allocated = 0;
 
     //! Contains all allocated pools of memory, used to free the data in the destructor.
     std::vector<std::unique_ptr<char[]>> m_allocated_pools{};

</p></details>

I also don't like that in most cases memoryresource.DynamicMemoryUsage() will return a negative number (causing size_t underflow) to correct for the overestimation in memusage. This will happen whenever the overestimation is large enough.

I don't understand this. The only negative term in the DynamicMemoryUsage calculation is the actual number of bytes allocated, not a memusage estimate. The result should always be positive, and higher with more memusage overestimation.

Here is a concrete example that I just tried with CCoinsMap. I created a CCoinsMap and added 100k entries. memusage::DynamicUsage calculates this:

return MallocUsage(node_size) * m.size() + MallocUsage(sizeof(void*) * m.bucket_count());
// return MallocUsage(104) * 100000 + MallocUsage(8 * 172933)  
// return 128 * 100000 + 1383488
// return 14183488

So DynamicUsage estimates 13.5MB memory usage. This is too much, because node_allocator doesn't have the overhead of malloc. MallocUsage uses 128 bytes per node, but when node_allocator the bytes per node are actually just 104. So when calculating MemoryResource::DynamicMemoryUsage we'd have to subtract the 128*100000 and not 104*100000 to get the correct memory usage:

return memusage::MallocUsage(POOL_SIZE_BYTES) * m_allocated_pools.size() + memusage::DynamicUsage(m_allocated_pools) - ALLOCATION_SIZE_BYTES * m_allocations;
// return MallocUsage(262080) * 40 + 528 - 104 * 100000 // <-- incorrect, has to be 128*100000
// return 262096 * 40 + 528 - 128*100000 // correct, but no easy way to get the correct 128 bytes within MemoryResource
// return -2315632