mempool: Don't sort in entryAll #29019

pull TheCharlatan wants to merge 1 commits into bitcoin:master from TheCharlatan:entryAllNoOrder changing 1 files +1 −7

TheCharlatan commented at 9:24 AM on December 7, 2023: contributor

Current call sites of entryAll do not require the entries to be sorted, so iterate through mapTx directly to retrieve the entries instead of using SortedDepthAndScore.

This is a follow up to #28391 and was noted here #28391 (review).
DrahtBot commented at 9:25 AM on December 7, 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.

Type Reviewers

ACK stickies-v, dergoegge, glozow

Stale ACK maflcko

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.



Conflicts

No conflicts as of last run.
DrahtBot added the label Mempool on Dec 7, 2023
maflcko commented at 9:35 AM on December 7, 2023: member

lgtm ACK 87fa444a04854a5d3a9ff283a8b6c34587e8430f

Though, if the function will be removed either way, I wonder if this is worth it. Maybe wait for an OK by @sdaftuar to avoid a merge conflict with #28676 ?
stickies-v commented at 2:57 PM on December 7, 2023: contributor

Current call sites of entryAll do not require the entries to be sorted

Will this PR not cause issues here? In CWallet::transactionAddedToMempool, we eventually call CWallet::AddToWalletIfInvolvingMe where we have a dependency on CWallet::GetDebit which tries to find the input tx in mapWallet. If this happens in a random order, and not sorted by depth, I think we'd incorrectly miss transactions that are actually "mine" but just aren't in mapWallet yet?
maflcko commented at 3:01 PM on December 7, 2023: member

Well, if it is needed, then 453b4813ebc74859864803e9972b58e4be76a4d6 should not have been tagged "refactor", but "bugfix" and should be backported, along with a regression test?
stickies-v commented at 3:27 PM on December 7, 2023: contributor

That is a good point, I'd missed that this just reverts back to the behaviour pre-entryAll(). It seems that when iterating over a boost::multi_index_container without specifying an index, we default to the insertion order, so i think that would be sufficient guarantees that the CWallet::transactionAddedToMempool calls happen in a safe order too.
sdaftuar commented at 4:30 PM on December 7, 2023: member

Though, if the function will be removed either way, I wonder if this is worth it. Maybe wait for an OK by @sdaftuar to avoid a merge conflict with #28676 ?

I'm not necessarily planning to remove entryAll(), but I am planning to replace GetSortedDepthAndScore() with a different function that will iterate the mempool topologically based on cluster sort (ie a valid topological order in which the mempool is sorted by descending feerate chunks).

I think if the sorted order is not needed, probably best to remove it now so that we don't take the performance hit needlessly in the next release...? I mostly just wanted to know if I needed to replace it with the new topological sort I'm implementing or if it's fine to just revert back to the mapTx order.
stickies-v approved
stickies-v commented at 6:32 PM on December 7, 2023: contributor

ACK 87fa444a04854a5d3a9ff283a8b6c34587e8430f

Type	Reviewers
ACK	stickies-v, dergoegge, glozow
Stale ACK	maflcko

in src/txmempool.cpp:834 in 87fa444a04 outdated

 831 | @@ -832,8 +832,8 @@ std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const
 832 |  
 833 |      std::vector<CTxMemPoolEntryRef> ret;
 834 |      ret.reserve(mapTx.size());

martinus commented at 7:42 AM on December 8, 2023:

nit: you could just write

AssertLockHeld(cs);
return {mapTx.begin(), mapTx.end()};

TheCharlatan commented at 10:12 AM on December 10, 2023:

Thanks, seems easy enough to re-ACK, so will push this.

mempool: Don't sort in entryAll

Current call sites of entryAll do not require the entries to be sorted,
so iterate through mapTx directly to retrieve the entries instead of
using SortedDepthAndScore.

f761f0306b

TheCharlatan force-pushed on Dec 10, 2023
TheCharlatan commented at 10:38 AM on December 10, 2023: contributor
Updated 87fa444a04 -> f761f0306b092c06cecd239060b36cd0ba45fa2c (entryAllNoOrder_0 -> entryAllNoOrder_1, compare)
- Addressed @martinus nit.
stickies-v approved
stickies-v commented at 12:50 PM on December 11, 2023: contributor

re-ACK f761f0306b092c06cecd239060b36cd0ba45fa2c, very nice
DrahtBot requested review from maflcko on Dec 11, 2023
dergoegge approved
dergoegge commented at 2:43 PM on January 3, 2024: member

utACK f761f0306b092c06cecd239060b36cd0ba45fa2c
glozow commented at 3:26 PM on January 3, 2024: member

~ACK f761f0306b092c06cecd239060b36cd0ba45fa2c given this brings us back to what we had before~

It seems correct that none of the callsites need GetSortedDepthAndScore, though maybe topological is needed in wallet? I had the same question. I guess insertion order doesn't imply topological if a parent was inserted later than a child, i.e. if it's from a reorg?
glozow commented at 4:31 PM on January 4, 2024: member
Will this PR not cause issues here? In CWallet::transactionAddedToMempool, we eventually call CWallet::AddToWalletIfInvolvingMe where we have a dependency on CWallet::GetDebit which tries to find the input tx in mapWallet. If this happens in a random order, and not sorted by depth, I think we'd incorrectly miss transactions that are actually "mine" but just aren't in mapWallet yet?

Well, if it is needed, then 453b481 should not have been tagged "refactor", but "bugfix" and should be backported, along with a regression test?

I wrote a test and I think we actually do need a topological sort here. See #29179. Cherry-picking this on top, it fails with
```
Traceback (most recent call last):
  File "/home/gloria/bitcoin/test/functional/test_framework/test_framework.py", line 131, in main
    self.run_test()
  File "/home/gloria/bitcoin/test/functional/wallet_import_rescan.py", line 323, in run_test
    assert_equal(variant.node.gettransaction(variant.child_txid)['confirmations'], 0)
  File "/home/gloria/bitcoin/test/functional/test_framework/coverage.py", line 50, in __call__
    return_val = self.auth_service_proxy_instance.__call__(*args, **kwargs)
  File "/home/gloria/bitcoin/test/functional/test_framework/authproxy.py", line 129, in __call__
    raise JSONRPCException(response['error'], status)
test_framework.authproxy.JSONRPCException: Invalid or non-wallet transaction id (-5)
```
which indicates that the child wasn't identified as IsFromMe in the wallet (i.e. couldn't see the inputs because the parent hadn't been seen yet). Assuming I didn't write a bad test, it makes me wonder why this wasn't a problem before? I guess this is very unlikely?
TheCharlatan commented at 12:28 PM on January 5, 2024: contributor

Seems like the new behavior incidentally fixed a bug, so closing this again in favor of #29179. Could do a follow-up eventually to make the entryAll call when processing the getrawmempool RPC call more efficient by skipping the sorting.
TheCharlatan closed this on Jan 5, 2024
achow101 referenced this in commit 27d935f58b on Jan 16, 2024
bitcoin locked this on Jan 4, 2025