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.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--174a7506f384e20aa4161008e828411d-->
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.
Don't you need to make TxLinks sets use accounting allocators in this patch too?
@JeremyRubin Ah, that seems reasonable. My priority was the things that use a boost multiindex as guessing memory usage there is very hard, but no reason why it can't be extended to also the sets there.
Do you know if we were over or underestimating before?
In mapTx we were overestimating slightly for realistic mempool size, but underestimating for near-empty ones.
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.
Yes, they're failing because the mempool limits now work slightly differently. The test makes rather silly assumptions on the menory usage of transaction entries.
Concept ACK, I think this is an elegant way to track accurate usage.
Concept ACK.
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
Shouldn't be documented here that the accounting variable must be atomic or protected by mutex?
I've added a bunch of comments.
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.
Mind looking into https://github.com/hebasto/bitcoin/commits/test18086 ? In that branch the first two commits eliminate the influence of memory allocated amount for the empty memory pool in unit tests. Then all the unit and functional tests passed.
@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
* 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:
* Any containers using such an allocator, and containers move constructed or
* 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
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'
65fc229fabbc7889baca9c50ee35507543a6682e ~nit - dedicated constructors could be used:~
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.
<!--cf906140f33d8803c4a75a2196329ecb-->
🐙 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.
<details><summary>Error</summary>
./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 *'
template<typename P> void destroy(P* ptr) { m_base.destroy(ptr); }
^~~
/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
{__a.destroy(__p);}
^
/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
{__destroy(__has_destroy<allocator_type, _Tp*>(), __a, __p);}
^
/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
__alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
^
/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
__ptr_.second()(__tmp);
^
/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
~unique_ptr() { reset(); }
^
/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
__node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
^
/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
return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
^
/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
__table_.__insert_unique(*__first);
^
/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
insert(__il.begin(), __il.end());
^
test/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
container_type container1({}, 2, std::hash<int>(), std::equal_to<int>(), memusage::AccountingAllocator<int>(dummy)); // container1 is accounted for in 'dummy'
^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1880:52: note: passing argument to parameter '__p' here
_LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}
^
1 error generated.
</details>
@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.
I'll get back to this after the 0.21 branching.
<!--13523179cfe9479db18ec6c5d236f789-->There hasn't been much activity lately and the patch still needs rebase. What is the status here?
<!--13523179cfe9479db18ec6c5d236f789-->There hasn't been much activity lately and the patch still needs rebase. What is the status here?
