Merge #17925: Improve UpdateTransactionsFromBlock with Epochs

bd5a02692853f7240a4fdc593d7d0123d7916e45 Make UpdateTransactionsFromBlock use Epochs (Jeremy Rubin)
2ccb7cca4ac67198ac89bd58f5b4ae41a5163ceb Add Epoch Guards to CTXMemPoolEntry and CTxMemPool (Jeremy Rubin)

Pull request description:

  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 PR is related to https://github.com/bitcoin/bitcoin/pull/17268, it is a small subset of the changes which have been refactored slightly to ease review. If this PR gets review & merge, I will follow up with more PRs (similar to #17268) to improve the mempool

ACKs for top commit:
  sdaftuar:
    ACK bd5a02692853f7240a4fdc593d7d0123d7916e45
  adamjonas:
    Just to summarize for those looking to review - as of bd5a026 there are 3 ACKs (@sdaftuar, @ariard, and @hebasto) and one "looks good" from @ajtowns with no NACKs or any show-stopping concerns raised.
  ajtowns:
    ACK bd5a02692853f7240a4fdc593d7d0123d7916e45 (code review)
  ariard:
    Code review ACK bd5a026
  hebasto:
    ACK bd5a02692853f7240a4fdc593d7d0123d7916e45, modulo some nits and a typo.

Tree-SHA512: f0d2291085019ffb4e1119edeb9f4a89c1a572d1cb5b4bdf5743dd0152e721e1935f5155dcae84e1e5bda5ffdf6224c488c1e200bd33bedca9f5ca22d5f5139f

1 files changed, 35 insertions, 14 deletions

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 441255182e..5768219f3a 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -23,7 +23,7 @@ CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFe
                                  int64_t _nTime, unsigned int _entryHeight,
                                  bool _spendsCoinbase, int64_t _sigOpsCost, LockPoints lp)
     : tx(_tx), nFee(_nFee), nTxWeight(GetTransactionWeight(*tx)), nUsageSize(RecursiveDynamicUsage(tx)), nTime(_nTime), entryHeight(_entryHeight),
-    spendsCoinbase(_spendsCoinbase), sigOpCost(_sigOpsCost), lockPoints(lp)
+    spendsCoinbase(_spendsCoinbase), sigOpCost(_sigOpsCost), lockPoints(lp), m_epoch(0)
 {
     nCountWithDescendants = 1;
     nSizeWithDescendants = GetTxSize();
@@ -122,8 +122,6 @@ void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashes
     // setMemPoolChildren will be updated, an assumption made in
     // UpdateForDescendants.
     for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) {
-        // we cache the in-mempool children to avoid duplicate updates
-        setEntries setChildren;
         // calculate children from mapNextTx
         txiter it = mapTx.find(hash);
         if (it == mapTx.end()) {
@@ -132,17 +130,21 @@ void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashes
         auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
         // First calculate the children, and update setMemPoolChildren to
         // include them, and update their setMemPoolParents to include this tx.
-        for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
-            const uint256 &childHash = iter->second->GetHash();
-            txiter childIter = mapTx.find(childHash);
-            assert(childIter != mapTx.end());
-            // We can skip updating entries we've encountered before or that
-            // are in the block (which are already accounted for).
-            if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) {
-                UpdateChild(it, childIter, true);
-                UpdateParent(childIter, it, true);
+        // we cache the in-mempool children to avoid duplicate updates
+        {
+            const auto epoch = GetFreshEpoch();
+            for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
+                const uint256 &childHash = iter->second->GetHash();
+                txiter childIter = mapTx.find(childHash);
+                assert(childIter != mapTx.end());
+                // We can skip updating entries we've encountered before or that
+                // are in the block (which are already accounted for).
+                if (!visited(childIter) && !setAlreadyIncluded.count(childHash)) {
+                    UpdateChild(it, childIter, true);
+                    UpdateParent(childIter, it, true);
+                }
             }
-        }
+        } // release epoch guard for UpdateForDescendants
         UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded);
     }
 }
@@ -325,7 +327,7 @@ void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee,
 }
 
 CTxMemPool::CTxMemPool(CBlockPolicyEstimator* estimator)
-    : nTransactionsUpdated(0), minerPolicyEstimator(estimator)
+    : nTransactionsUpdated(0), minerPolicyEstimator(estimator), m_epoch(0), m_has_epoch_guard(false)
 {
     _clear(); //lock free clear
 
@@ -1105,4 +1107,23 @@ void CTxMemPool::SetIsLoaded(bool loaded)
     m_is_loaded = loaded;
 }
 
+
+CTxMemPool::EpochGuard CTxMemPool::GetFreshEpoch() const
+{
+    return EpochGuard(*this);
+}
+CTxMemPool::EpochGuard::EpochGuard(const CTxMemPool& in) : pool(in)
+{
+    assert(!pool.m_has_epoch_guard);
+    ++pool.m_epoch;
+    pool.m_has_epoch_guard = true;
+}
+
+CTxMemPool::EpochGuard::~EpochGuard()
+{
+    // prevents stale results being used
+    ++pool.m_epoch;
+    pool.m_has_epoch_guard = false;
+}
+
 SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}