HomePhabricator

Add Epoch Guards to CTXMemPoolEntry and CTxMemPool, make…

Description

Add Epoch Guards to CTXMemPoolEntry and CTxMemPool, make UpdateTransactionsFromBlock use Epochs

Summary:

UpdateTransactionsFromBlock is called during a re-org. When a re-org occurs, all of the transactions in the mempool may be descendants from a transaction which is in the pre-reorg block. This can cause us to propagate updates, worst case, to every transaction in the mempool.

Because we construct a setEntries setChildren, which is backed by a std::set, it is possible that this algorithm is O(N log N).

By using an Epoch visitor pattern, we can limit this to O(N) worst case behavior.

Epochs are also less resource intensive than almost any set option (e.g., hash set) because they are allocation free.

This is a backport of Core PR17925

Test Plan: ninja && ninja check

Reviewers: #bitcoin_abc, majcosta

Reviewed By: #bitcoin_abc, majcosta

Subscribers: majcosta

Differential Revision: https://reviews.bitcoinabc.org/D8733

Details

Provenance
Jeremy Rubin <j@rubin.io>Authored on Dec 22 2020, 07:34
PiRKCommitted on Dec 22 2020, 07:35
abc-botPushed on Dec 22 2020, 07:41
Reviewer
Restricted Project
Differential Revision
D8733: Add Epoch Guards to CTXMemPoolEntry and CTxMemPool, make UpdateTransactionsFromBlock use Epochs
Parents
rABCaa5b13600c21: [test] Add test for NODE_COMPACT_FILTER.
Branches
Unknown
Tags
Unknown