improve MallocUsage() accuracy

LarryRuane commented at 10:17 pm on September 25, 2023: contributor

The MallocUsage() function takes an allocation size as an argument and returns the amount of physical memory consumed, which is greater due to memory allocator overhead and alignment. It was first added in 2015 (first commit of #6102), but its accuracy has degraded as memory allocation libraries have evolved. It’s used when it’s important that large data structures, such as the coins cache and mempool, should use a predictable, configurable (limited) amount of physical memory (see the -dbcache and -maxmempool configuration options), as well as a few other places.

sipa figured out a concise, efficient expression that this function can use, and that’s what’s implemented here.

Also add a unit test, which is more helpful than usual in this case since platforms, operating systems, and libraries vary significantly in this area.

DrahtBot commented at 10:17 pm on September 25, 2023: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

No conflicts as of last run.

LarryRuane commented at 10:17 pm on September 25, 2023: contributor

The results of the old and new versions of this function should differ only slightly; it would be bad if the new one gave very different results, because node operators might find too much memory being consumed, or (not as bad) not enough. To manually test this, I ran -reindex-chainstate on Ubuntu, and watched memory usage by printing /proc/pid/statm and watching the data (6th) field. On master, the value settled to 315140 (units are 4k pages); with this PR it was 315606, which indicates that the new version produces slightly smaller results, but they’re close.

DrahtBot added the label CI failed on Sep 25, 2023

LarryRuane commented at 3:11 pm on September 27, 2023: contributor

Changing to draft because CI on a couple of the platforms failed the new test, so the physical memory calculation will need to be different on those platforms, I try to figure that out.

LarryRuane marked this as a draft on Sep 27, 2023

martinus commented at 8:24 am on November 20, 2023: contributor

I can reproduce the same results with glibc 2.31 and 2.38, in 32bit and 64bit. I don’t think it needs to be perfect on all platforms, I think your new calculation is fine.

I played a bit with a reproducer, here is mine: https://godbolt.org/z/s971sbnhG I refactored your MallocUsage formula a bit, but it’s basically the same

DrahtBot commented at 11:58 am on February 29, 2024: contributor

🤔 There hasn’t been much activity lately and the CI seems to be failing.

If no one reviewed the current pull request by commit hash, a rebase can be considered. While the CI failure may be a false positive, the CI hasn’t been running for some time, so there may be a real issue hiding as well. A rebase triggers the latest CI and makes sure that no silent merge conflicts have snuck in.

LarryRuane marked this as ready for review on Feb 29, 2024

LarryRuane force-pushed on Feb 29, 2024

LarryRuane commented at 8:28 pm on February 29, 2024: contributor

Force-pushed to 04f3fbe308728d2fb18fad418603cab97f0b9f59 - rebase only. (CI is still expected to fail, I’m working on that now.)

LarryRuane force-pushed on Mar 1, 2024

LarryRuane force-pushed on Mar 14, 2024

LarryRuane force-pushed on Mar 15, 2024

LarryRuane commented at 10:34 pm on March 15, 2024: contributor

@martinus Can you think of why the macOS and Win64 are failing (I have only Ubuntu, which passes)? As an experiment, I changed the memory usage ratio needed to pass to the resource map being just less than std_map, but not even that passes (that is, the resource map uses more space). Both of those platforms fail the same way (you can see this in the CI results, this is Win64):

0D:/a/bitcoin/bitcoin/src/test/pool_tests.cpp(183): error: in "pool_tests/memusage_test": 
1  check memusage::DynamicUsage(resource_map) <= memusage::DynamicUsage(std_map) * 100 / 100 
2  has failed [466624 > 451088]

On earlier runs, some other tests have failed, but I’m not sure if those are spurious failures.

I’m not sure what to do now, any thoughts or suggestions are welcome!

sipa commented at 6:57 pm on March 16, 2024: member

@LarryRuane There is no reason to assume that the memory allocation overhead on those platforms, with substantially different C libraries, would match the formula we inferred on x86_64 and arm Linux.

If our goal is actually accurate memory usage calculations on all systems, we will need to derive a formula for each supported system separately.

LarryRuane force-pushed on Mar 19, 2024

LarryRuane commented at 5:40 pm on March 19, 2024: contributor

@sipa - I don’t think the test failures could be due to differences in memory allocation overhead across platforms. The actual memory allocation overhead isn’t being tested at all. To do that would probably require a test that uses /proc/meminfo (which doesn’t exist on all platforms) or similar.

I don’t mind giving up and closing this PR, but as @martinus said in an earlier comment, this calculation doesn’t need to be perfect, just better.

I think this test failure must be due to differences in std::unordered_map implementations. That container does various allocations for different reasons, and it must be that with this PR’s change in memory usage calculation, the std::unordered_map on macOS and Win64 (at least) are doing more a kind of allocation that the new calculation thinks has higher overhead. Something like that.

[UPDATE: the following discussion about std::unordered_map::reserve() is incorrect, calling reserve() doesn’t prevent the bucket array from being reallocated multiple times within the pool resource – rather, it’s reallocated using regular memory. Only allocations up to 128 bytes come from the pool allocator. (I’ll probably remove these comments later.)

I thought I had it figured out; I verified with the debugger that as the test adds the 10k entries to the two maps, it has to repeatedly grow the bucket array. The allocation sizes (in bytes) for the bucket array that I saw here on Ubuntu were: 104, 232, 472, 1026, 2056, 4328, 8872, 18856, 40696, 82184…. The tradeoff one makes when using the pool resource allocator is that memory allocations that are freed but then those same sizes not allocated again, those allocations are, in effect, leaked (until the resource is destroyed). The pool resource works great when freeing and allocating the same sizes (rounded up to the alignment, usually 8 bytes) repeatedly. This is, of course, the case for the individual map entries.

So the latest force-push simply calls reserve() initially on both maps (this is only really needed for the pool resource map). Debugging verifies that this does prevent the bucket array from being reallocated, here on Ubuntu. But it didn’t fix the problem on at least macOS and Win64. Maybe those platforms’ implementations of std::unordered_map ignore the reserve() hint?

It’s difficult when CI fails on platforms that I don’t have access to. Do others have a solution to that? Can I install macOS on Ubuntu or Windows 10 (I have both) as a VM? Maybe I can set up my Windows laptop to build and run the debugger, but that seems like a lot of work.

martinus commented at 9:32 am on March 20, 2024: contributor

@LarryRuane The problem here is that the DynamicUsage(const std::unordered_map<X, Y, Z>& m) just estimates the memory usage by thinking that internally it uses a node with a single pointer (see struct unordered_node : private X in memusage.h). This estimation is probably not correct on all platforms, e.g. windows seems to use a double linked list, so this underestimates actual memory usage.

The inconcsistency now comes when using DynamicUsage with a pool resource. Here the actual real world memory usage is counted (because it uses a custom allocator, there’s no need for estimating node size), and here the different implementations actually effect the result.

So, with your new MallocUsage the numbers are most likely more correct, but this seems to trigger the incorrect underestimation for DynamicUsage(const std::unordered_map<X, Y, Z>& m)

LarryRuane commented at 5:37 pm on March 21, 2024: contributor

@martinus - thanks, that makes perfect sense! I hadn’t thought of the possibility of the nodes having two pointers instead of one (double instead of single linked list). Seems like a bad design, but anyway.

I don’t think there would be much benefit to fixing DynamicUsage(const std::unordered_map<X, Y, Z>& m) to account for this (make it dependent on platform), because this function is no longer important since we’re using the pool resource. It’s probably really used only in the test. So it’s really just a test problem. I’ll see what I can do to fix this.

LarryRuane force-pushed on Mar 22, 2024

LarryRuane force-pushed on Apr 8, 2024

DrahtBot added the label Needs rebase on Apr 11, 2024

LarryRuane force-pushed on May 3, 2024

DrahtBot removed the label Needs rebase on May 3, 2024

DrahtBot marked this as a draft on May 13, 2024

DrahtBot commented at 8:02 am on May 13, 2024: contributor

Turned into draft for now, due to failing CI. If this is no longer a WIP, you can move it out of draft.

LarryRuane marked this as ready for review on May 21, 2024

LarryRuane force-pushed on May 21, 2024

DrahtBot added the label Needs rebase on May 21, 2024

LarryRuane force-pushed on May 22, 2024

DrahtBot removed the label Needs rebase on May 22, 2024

DrahtBot removed the label CI failed on May 22, 2024

LarryRuane commented at 7:12 pm on May 22, 2024: contributor

NOTE, this PR isn’t ready to merge; at the very least it has some debug prints that need to be removed.

CI was failing on some platforms (Windows and macOS), in test/functional/mempool_limit.py: test_mid_package_eviction(). I think this test is fragile; this very-unrelated PR shouldn’t be able to cause it to fail IMO. The problem turned out to be the following:

This test calls the test utility function fill_mempool(). This function creates independent physically-large (around 65kb) transactions at varying fee rates until the one with the lowest feerate is evicted due to the mempool becoming full. The functional tests run with -maxmempool=5 (MB), so that requires about 72 transactions.

After fill_mempool() returns, the mempool likely won’t be completely full, because these were large transactions, so there’s some space left but not enough for another transaction. The test, test_mid_package_eviction, then submits a smaller transaction (weight around 8k) called mempool_evicted_tx with a fee just barely high enough to be accepted, and expects that transaction to be accepted. (It has this name, mempool_evicted_tx, because the test expects it to be evicted later.)

With this PR, that transaction was not accepted on Windows and macOS. Some debug prints show that on those platforms, when fill_mempool() returns, there are only 1200 bytes of free space in the mempool. This is because the std::unordered_map library implementations are different on these platforms, and this causes the memory usage calculation (for the entire map) to be slightly different in this PR. So it’s really just bad luck. This is why I think the test is fragile.

After trying a few fixes to the test that didn’t work, what finally worked (the current branch) is, to have fill_mempool(), just before it returns, submit another transaction that replaces (RBF) an existing one in the mempool, but is slightly smaller. This frees up about 10kb of additional space, which allows room for the 8k transaction to be reliably accepted. This doesn’t break the other tests that call fill_mempool().

This attempt didn’t work the first time, however, because the mempools wouldn’t reliably sync in test/functional/p2p_1p1c_network.py. This test starts 4 nodes, and calls fill_mempool() on node 0 then waits for all 4 mempools to become synced. Sometimes they do but other times this never happens. I wonder if there might be an unrelated bug (I can investigate later), but what often happens (it’s timing dependent and thus random) is that the replacement tx (added by this PR) does appear on all nodes, but a low-feerate tx that was evicted on node 0 remains on nodes 1-3. I can explain what I’m seeing in more detail later if needed. What ended up fixing this is to delay a few seconds before submitting the RBF transaction. It’s ugly, maybe there’s a better way, but syncing mempools is kind of non-deterministic anyway, so I don’t think it’s terribly bad. @glozow and @theStack, can you let me know your opinion? You two have worked a lot in this area.

theStack commented at 0:24 am on May 23, 2024: contributor

@LarryRuane: Interesting problem (and very creative solution with the RBF tx :)). Fwiw, on one of my machines running OpenBSD 7.5, the same behaviour as you described occurs on commit 663e5012d318a7e80a42385ac4e6f71dec46814e: after fill_mempool, mempool usage is very close to the max ('usage': 4998768), and the subtest test_mid_package_eviction fails on the first MiniWallet tx submission with a "mempool full" error.

One idea I had to solve this at the fill_mempool side is to submit an extra tx at the end of fill_mempool that is smaller (I chose half the size) than the filler txs. Given that this causes eviction, a large filler tx is removed, and the smaller-sized tx is getting in, freeing up some space (around ~32.5KB in terms of bytes). It’s still very ugly, especially since this code is only ever executed for edge cases (note that we can’t unconditionally submit the smaller tx, as this could cause the problem rather than solve it, if no eviction happens), but passes all the tests that use fill_mempool for me: https://github.com/theStack/bitcoin/commit/f758e73a943b8e45acac1ab8834305f7f0bfbf14

However, is this even necessary to be solved in fill_mempool? Haven’t looked closer at the failing test yet, but maybe it’s just a bug in the fee calculation (or MiniWallet’s treatment of target_weight).

LarryRuane force-pushed on May 23, 2024

LarryRuane commented at 8:58 pm on May 23, 2024: contributor

Your patch is much better, @theStack, thanks! It’s simpler and doesn’t need that weird sleep. Force-pushed your patch. If it passes CI, I think this is the way to go. I had tried something similar, but I didn’t think to make the sending of that extra (smaller) transaction conditional based on available mempool space.

test: ensure that `fill_mempool` leaves some room in mempool 9c89fb4cc1

improve MallocUsage() accuracy

Co-authored-by: Pieter Wuille <pieter@wuille.net>
Co-authored-by: Martin Leitner-Ankerl <martin.ankerl@gmail.com>

1fcbebcae0

LarryRuane force-pushed on May 24, 2024

LarryRuane commented at 6:31 pm on May 24, 2024: contributor

CI passed, thanks @theStack. I just force-pushed swapping of the two commits, the test commit has to be first for each commit to pass CI.

DrahtBot added the label CI failed on Sep 12, 2024

DrahtBot removed the label CI failed on Sep 15, 2024

achow101 requested review from sipa on Oct 15, 2024

improve MallocUsage() accuracy #28531

Code Coverage

Reviews

Conflicts