mempool: Don't sort in entryAll #29019

TheCharlatan · 2023-12-07T09:24:57Z

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 (comment).

DrahtBot · 2023-12-07T09:25:00Z

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.

maflcko · 2023-12-07T09:35:31Z

lgtm ACK 87fa444

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 · 2023-12-07T14:57:14Z

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 · 2023-12-07T15:01:17Z

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

stickies-v · 2023-12-07T15:27:17Z

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 · 2023-12-07T16:30:37Z

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

ACK 87fa444

martinus · 2023-12-08T07:42:30Z

src/txmempool.cpp

@@ -832,8 +832,8 @@ std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const

    std::vector<CTxMemPoolEntryRef> ret;
    ret.reserve(mapTx.size());


nit: you could just write

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

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

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.

TheCharlatan · 2023-12-10T10:38:41Z

Updated 87fa444 -> f761f03 (entryAllNoOrder_0 -> entryAllNoOrder_1, compare)

Addressed @martinus nit.

stickies-v

re-ACK f761f03, very nice

dergoegge

utACK f761f03

glozow

~~ACK f761f03 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 · 2024-01-04T16:31:04Z

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 · 2024-01-05T12:28:50Z

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.

…d in mempool df30247 [test] import descriptor wallet with reorged parent + IsFromMe child in mempool (glozow) c3d02be [test] rescan legacy wallet with reorged parent + IsFromMe child in mempool (Gloria Zhao) Pull request description: Originally motivated by #29019, which reverts back to having `requestMempoolTransactions` emit `transactionAddedToMempool` in `mapTx` default order instead of `GetSortedDepthAndScore` order. It's important that these notifications happen in topological order, otherwise the wallet rescan may miss transactions that belong to it. Notably, checking whether a transaction `IsFromMe` requires knowing its inputs, which may be from a mempool parent. When using `mapTx` order, a parent may come later than its child if it was added from a block disconnected in a reorg. This PR adds a test for this case. ACKs for top commit: achow101: ACK df30247 furszy: Code review ACK df30247, nits can be disregarded. Tree-SHA512: 2f1d9ef92313228adbbef94e634e5f7a9ec6e6a2c88e16aa343bdc95ffc9b9f9c82a569b412c9a3841db9d789e52f9283e8b9385731668d59355903e26e58a5d

DrahtBot added the Mempool label Dec 7, 2023

TheCharlatan mentioned this pull request Dec 7, 2023

refactor: Simplify CTxMempool/BlockAssembler fields, remove some external mapTx access #28391

Merged

stickies-v approved these changes Dec 7, 2023

View reviewed changes

DrahtBot mentioned this pull request Dec 7, 2023

Cluster mempool implementation #28676

Open

8 tasks

martinus reviewed Dec 8, 2023

View reviewed changes

mempool: Don't sort in entryAll

f761f03

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.

TheCharlatan force-pushed the entryAllNoOrder branch from 87fa444 to f761f03 Compare December 10, 2023 10:38

stickies-v approved these changes Dec 11, 2023

View reviewed changes

DrahtBot requested a review from maflcko December 11, 2023 12:50

dergoegge approved these changes Jan 3, 2024

View reviewed changes

glozow reviewed Jan 3, 2024

View reviewed changes

glozow mentioned this pull request Jan 4, 2024

test: wallet rescan with reorged parent + IsFromMe child in mempool #29179

Merged

TheCharlatan closed this Jan 5, 2024

bitcoin locked and limited conversation to collaborators Jan 4, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

mempool: Don't sort in entryAll #29019

mempool: Don't sort in entryAll #29019

Uh oh!

TheCharlatan commented Dec 7, 2023

Uh oh!

DrahtBot commented Dec 7, 2023 •

edited

Loading

Uh oh!

maflcko commented Dec 7, 2023

Uh oh!

stickies-v commented Dec 7, 2023

Uh oh!

maflcko commented Dec 7, 2023

Uh oh!

stickies-v commented Dec 7, 2023

Uh oh!

sdaftuar commented Dec 7, 2023 •

edited

Loading

Uh oh!

stickies-v left a comment

Uh oh!

martinus Dec 8, 2023 •

edited

Loading

Uh oh!

TheCharlatan Dec 10, 2023

Uh oh!

TheCharlatan commented Dec 10, 2023

Uh oh!

stickies-v left a comment

Uh oh!

dergoegge left a comment

Uh oh!

glozow left a comment •

edited

Loading

Uh oh!

glozow commented Jan 4, 2024 •

edited

Loading

Uh oh!

TheCharlatan commented Jan 5, 2024

Uh oh!

Uh oh!

		@@ -832,8 +832,8 @@ std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const

		std::vector<CTxMemPoolEntryRef> ret;
		ret.reserve(mapTx.size());

mempool: Don't sort in entryAll #29019

mempool: Don't sort in entryAll #29019

Uh oh!

Conversation

TheCharlatan commented Dec 7, 2023

Uh oh!

DrahtBot commented Dec 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage

Reviews

Conflicts

Uh oh!

maflcko commented Dec 7, 2023

Uh oh!

stickies-v commented Dec 7, 2023

Uh oh!

maflcko commented Dec 7, 2023

Uh oh!

stickies-v commented Dec 7, 2023

Uh oh!

sdaftuar commented Dec 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

stickies-v left a comment

Choose a reason for hiding this comment

Uh oh!

martinus Dec 8, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

TheCharlatan Dec 10, 2023

Choose a reason for hiding this comment

Uh oh!

TheCharlatan commented Dec 10, 2023

Uh oh!

stickies-v left a comment

Choose a reason for hiding this comment

Uh oh!

dergoegge left a comment

Choose a reason for hiding this comment

Uh oh!

glozow left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

glozow commented Jan 4, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

TheCharlatan commented Jan 5, 2024

Uh oh!

Uh oh!

DrahtBot commented Dec 7, 2023 •

edited

Loading

sdaftuar commented Dec 7, 2023 •

edited

Loading

martinus Dec 8, 2023 •

edited

Loading

glozow left a comment •

edited

Loading

glozow commented Jan 4, 2024 •

edited

Loading