This introduces a C++ allocator class (memusage::AccountingAllocator) which enables containers that accurately account for all their memory allocations in a tracker variable.
This is then used to replace the heuristics in the mempool to guess memory usage.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
@sipa can you take a look at https://github.com/JeremyRubin/bitcoin/pull/7?
It looks like when we get rid of mapTxLinks we’d then want to use an accounting allocator on the new child sets and get some DynamicMemoryUsage added to the cached inner usage?
At some point I also want to better break down the cachedInnerUsage tracking into buckets as it makes it easier to trace bugs.
I’m happy to rebase this on top of a removal of mapLinks, if that’d go in first. It looks pretty like I’d just need to remove mapLinks from this as well.
I don’t know if breaking down cachedInnerUsage is all that meaningful, as the Check() function can verify its correctness in aggregate.
There are plenty more options of shuffling things with AccountingAllocators… I don’t have any particular preference apart from minimizing code changes.
Ok the near empty case doesn’t really matter… w.r.t. the realistic size one, here’s a question just to be detailed/pedantic with what this change does:
Given that we were previously overestimating, if I set my mempool to 100MB then I actually was getting (let’s say) 99 MB, if the “slightly” was by 1%. If after this change, I am now actually using a little bit more memory is this enough to be concerned? E.g., are we going to see a bunch of raspberry pi users complaining of OOMs?
Our memory accounting has never been more accurate than in the orders of 10s of MBs. A tiny change like this shouldn’t matter.
And probably on the long term, it helps: it’s likely the case that in some scenarios we were off more than others (e.g. many tiny transactions vs a few big ones) - better estimations means that experimentally-determined max memory limits need less margin.
The mempool tests happen to be very fragile – I’ve noticed that sometimes when I made the mempool more memory efficient (e.g., in removing mapLinks) there are a bunch of failures because the tests depend on evictions happening because it’s out of space.
I’m not positive that’s why your tests are failing, but it could be related.
31+ * memory.
32+ */
33+template<typename T>
34+class AccountingAllocator : public std::allocator<T>
35+{
36+ size_t* m_allocated; //!< Pointer to accounting variable, cannot be nullptr
In mapTx we were overestimating slightly for realistic mempool size, but underestimating for near-empty ones.
As unit tests are based on “near-empty” containers the difference of estimations seems broke them.
Testing ed1c5b1b98a19b6751d739f86cdc305bb3cff283 with mempool_tests/MempoolSizeLimitTest: the difference in CTxMemPool::DynamicMemoryUsage() is ~700 bytes.
@hebasto That looks great. I’ve included your test/annotation improvements.
I also added some comments, and made a change so that when a copy of a container is made, that copy is unaccounted. I think this makes sense conceptually (copies tend to be short-lived and not account for permanent storage), as well as reduce locking issues (otherwise you’d always need a lock on the original accounting variable when modifying the copy…).
45+ //! Default constructor constructs a non-accounting allocator.
46+ AccountingAllocator() noexcept : m_allocated(nullptr) {}
47+
48+ /** Construct an allocator that increments/decrements 'allocated' on allocate/free.
49+ *
50+ * In a multithreaded environment, the variable needs to be protected by the same
65fc229fabbc7889baca9c50ee35507543a6682e
0 * In a multithreaded environment, the accounting variable needs to be protected by the same
24@@ -25,6 +25,64 @@ namespace memusage
25 /** Compute the total memory used by allocating alloc bytes. */
26 static size_t MallocUsage(size_t alloc);
27
28+/** Wrapping allocator that accounts accurately.
29+ *
30+ * To use accounting, the AccountAllocator(size_t&) constructor must be used.
31+ * Any containers using such an allocator, and containers moved constructed or
32+ * assigned from such containers will then increment/decrement size_t when
65fc229fabbc7889baca9c50ee35507543a6682e nit:
0 * Any containers using such an allocator, and containers move constructed or
1 * move assigned from such containers will then increment/decrement size_t when
251+ container2.insert(3);
252+ container2.erase(2);
253+ BOOST_CHECK(total > 0);
254+ size_t old = total;
255+ container1 = std::move(container2); // container1 is now accounted for in 'total'
256+ BOOST_CHECK(total >= old);
65fc229fabbc7889baca9c50ee35507543a6682e
0 BOOST_CHECK(total == old);
243+ {
244+ typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>, memusage::AccountingAllocator<int>> container_type;
245+ container_type container1({}, 2, std::hash<int>(), std::equal_to<int>(), memusage::AccountingAllocator<int>(dummy)); // container1 is accounted for in 'dummy'
246+ container1.insert(6);
247+ {
248+ container_type container2(1, std::hash<int>(), std::equal_to<int>(), memusage::AccountingAllocator<int>(total)); // container2 is accounted for in 'total'
From the IRC discussion:
<cfields> sipa: I suppose the old gcc issue is that the propagate_on_container_* aren’t respected ? <sipa> cfields: possibly <sipa> but it looks like that <cfields> sipa: from libstdc++ 4.8 release docs “23.2.1 General container requirements Partial Only vector and forward_list meet the requirements relating to allocator use and propagation.” <sipa> cfields: ah <cfields> sipa: if it makes you feel any better, looks like support for all standard containers didn’t exist until 6.x. <sipa> cfields: seems i may just need to give up on the no-propagate-on-copy, and add a big disclaimer
50+ * In a multithreaded environment, the variable needs to be protected by the same
51+ * lock as the container(s) that use this allocator. */
52+ explicit AccountingAllocator(size_t& allocated) noexcept : m_allocated(&allocated) {}
53+
54+ //! A copy-constructed container will be non-accounting.
55+ static AccountingAllocator select_on_container_copy_construction() { return AccountingAllocator(); }
Includes thread safety annotations added by Hennadii Stepanov.
🐙 This pull request conflicts with the target branch and needs rebase.
Concept ACK, light pre-rebase ACK.
Feel free to ignore: commit message eace374a00a2 s/inherent/inherit/; the 2 test commits both do essentially the same thing in under 4 lines, could be squashed.
It looks like this will need a rebase anyway, but I’m having issues compiling eace374a0, which looks consistent with the CI.
0./memusage.h:92:64: error: cannot initialize a parameter of type 'std::__1::allocator<std::__1::__hash_node<int, void *> >::pointer' (aka 'std::__1::__hash_node<int, void *> *') with an lvalue of type 'int *'
1 template<typename P> void destroy(P* ptr) { m_base.destroy(ptr); }
2 ^~~
3/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1742:18: note: in instantiation of function template specialization 'memusage::AccountingAllocator<std::__1::__hash_node<int, void *> >::destroy<int>' requested here
4 {__a.destroy(__p);}
5 ^
6/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1595:14: note: in instantiation of function template specialization 'std::__1::allocator_traits<memusage::AccountingAllocator<std::__1::__hash_node<int, void *> > >::__destroy<int>' requested here
7 {__destroy(__has_destroy<allocator_type, _Tp*>(), __a, __p);}
8 ^
9/Library/Developer/CommandLineTools/usr/include/c++/v1/__hash_table:845:29: note: in instantiation of function template specialization 'std::__1::allocator_traits<memusage::AccountingAllocator<std::__1::__hash_node<int, void *> > >::destroy<int>' requested here
10 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
11 ^
12/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:2648:7: note: in instantiation of member function 'std::__1::__hash_node_destructor<memusage::AccountingAllocator<std::__1::__hash_node<int, void *> > >::operator()' requested here
13 __ptr_.second()(__tmp);
14 ^
15/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:2602:19: note: in instantiation of member function 'std::__1::unique_ptr<std::__1::__hash_node<int, void *>, std::__1::__hash_node_destructor<memusage::AccountingAllocator<std::__1::__hash_node<int, void *> > > >::reset' requested here
16 ~unique_ptr() { reset(); }
17 ^
18/Library/Developer/CommandLineTools/usr/include/c++/v1/__hash_table:2034:29: note: in instantiation of member function 'std::__1::unique_ptr<std::__1::__hash_node<int, void *>, std::__1::__hash_node_destructor<memusage::AccountingAllocator<std::__1::__hash_node<int, void *> > > >::~unique_ptr' requested here
19 __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
20 ^
21/Library/Developer/CommandLineTools/usr/include/c++/v1/__hash_table:1146:16: note: in instantiation of function template specialization 'std::__1::__hash_table<int, std::__1::hash<int>, std::__1::equal_to<int>, memusage::AccountingAllocator<int> >::__emplace_unique_key_args<int, const int &>' requested here
22 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
23 ^
24/Library/Developer/CommandLineTools/usr/include/c++/v1/unordered_set:864:18: note: in instantiation of member function 'std::__1::__hash_table<int, std::__1::hash<int>, std::__1::equal_to<int>, memusage::AccountingAllocator<int> >::__insert_unique' requested here
25 __table_.__insert_unique(*__first);
26 ^
27/Library/Developer/CommandLineTools/usr/include/c++/v1/unordered_set:831:5: note: in instantiation of function template specialization 'std::__1::unordered_set<int, std::__1::hash<int>, std::__1::equal_to<int>, memusage::AccountingAllocator<int> >::insert<const int *>' requested here
28 insert(__il.begin(), __il.end());
29 ^
30test/allocator_tests.cpp:245:24: note: in instantiation of member function 'std::__1::unordered_set<int, std::__1::hash<int>, std::__1::equal_to<int>, memusage::AccountingAllocator<int> >::unordered_set' requested here
31 container_type container1({}, 2, std::hash<int>(), std::equal_to<int>(), memusage::AccountingAllocator<int>(dummy)); // container1 is accounted for in 'dummy'
32 ^
33/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1880:52: note: passing argument to parameter '__p' here
34 _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}
35 ^
361 error generated.
@sipa @adamjonas Mind looking into https://github.com/hebasto/bitcoin/commits/201013-build18086 ?
That branch is rebased and:
BOOST_CHECK/BOOST_CHECK_EQUAL/ (was very useful for me during debugging)std::map as it is the container we actually use with the AccountingAllocator (among std::vector and boost::multi_index_container)CI CentOS build fails due to the old GCC 4.8 which, I think, just lacks support of the std::allocator_traits<Alloc>::select_on_container_copy_construction. It even lacks map( const Allocator& alloc ) constructor.
