Merge bitcoin/bitcoin#28385: [refactor] rewrite DisconnectedBlockTransactions to not use boost

4313c77400eb8eaa8586db39a7e29a861772ea80 make DisconnectedBlockTransactions responsible for its own memory management (glozow)
cf5f1faa037e9a40a5029cc7dd4ee61454b62466 MOVEONLY: DisconnectedBlockTransactions to its own file (glozow)
2765d6f3434c101fe2d46e9313e540aa680fbd77 rewrite DisconnectedBlockTransactions as a list + map (glozow)
79ce9f0aa46de8ff742be83fd6f68eab40e073ec add std::list to memusage (glozow)
59a35a7398f5bcb3e3805d1e4f363e4c2fb336b3 [bench] DisconnectedBlockTransactions (glozow)
925bb723ca71aa76380b769d8926c7c2ad9bbb7b [refactor] batch-add transactions to DisconnectedBlockTransactions (glozow)

Pull request description:

  Motivation
  - I think it's preferable to use stdlib data structures instead of depending on boost if we can achieve the same thing.
  - Also see #28335 for further context/motivation. This PR simplifies that one.

  Things done in this PR:
  - Add a bench for `DisconnectedBlockTransactions` where we reorg and the new chain has {100%, 90%, 10%} of the same transactions. AFAIU in practice, it's usually close to 100%.
  - Rewrite `DisconnectedBlockTransactions` as a `std::list` + `unordered_map` instead of a boost multi index container.
    - On my machine, the bench suggests the performance is very similar.
  - Move `DisconnectedBlockTransactions` from txmempool.h to its own kernel/disconnected_transactions.h. This struct isn't used by txmempool and doesn't have much to do with txmempool. My guess is that it's been living there for convenience since the boost includes are there.

ACKs for top commit:
  ismaelsadeeq:
    Tested ACK 4313c77400eb8eaa8586db39a7e29a861772ea80
  stickies-v:
    ACK 4313c77400eb8eaa8586db39a7e29a861772ea80
  TheCharlatan:
    ACK 4313c77400eb8eaa8586db39a7e29a861772ea80

Tree-SHA512: 273c80866bf3acd39b2a039dc082b7719d2d82e0940e1eb6c402f1c0992e997256722b85c7e310c9811238a770cfbdeb122ea4babbc23835d17128f214a1ef9e

1 files changed, 31 insertions, 35 deletions

diff --git a/src/validation.cpp b/src/validation.cpp
index db3310c2c3..0ce2902195 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -22,6 +22,7 @@
 #include <flatfile.h>
 #include <hash.h>
 #include <kernel/chainparams.h>
+#include <kernel/disconnected_transactions.h>
 #include <kernel/mempool_entry.h>
 #include <kernel/messagestartchars.h>
 #include <kernel/notifications_interface.h>
@@ -81,8 +82,6 @@ using node::CBlockIndexWorkComparator;
 using node::fReindex;
 using node::SnapshotMetadata;
 
-/** Maximum kilobytes for transactions to store for processing during reorg */
-static const unsigned int MAX_DISCONNECTED_TX_POOL_SIZE = 20000;
 /** Time to wait between writing blocks/block index to disk. */
 static constexpr std::chrono::hours DATABASE_WRITE_INTERVAL{1};
 /** Time to wait between flushing chainstate to disk. */
@@ -297,28 +296,30 @@ void Chainstate::MaybeUpdateMempoolForReorg(
     AssertLockHeld(cs_main);
     AssertLockHeld(m_mempool->cs);
     std::vector<uint256> vHashUpdate;
-    // disconnectpool's insertion_order index sorts the entries from
-    // oldest to newest, but the oldest entry will be the last tx from the
-    // latest mined block that was disconnected.
-    // Iterate disconnectpool in reverse, so that we add transactions
-    // back to the mempool starting with the earliest transaction that had
-    // been previously seen in a block.
-    auto it = disconnectpool.queuedTx.get<insertion_order>().rbegin();
-    while (it != disconnectpool.queuedTx.get<insertion_order>().rend()) {
-        // ignore validation errors in resurrected transactions
-        if (!fAddToMempool || (*it)->IsCoinBase() ||
-            AcceptToMemoryPool(*this, *it, GetTime(),
-                /*bypass_limits=*/true, /*test_accept=*/false).m_result_type !=
-                    MempoolAcceptResult::ResultType::VALID) {
-            // If the transaction doesn't make it in to the mempool, remove any
-            // transactions that depend on it (which would now be orphans).
-            m_mempool->removeRecursive(**it, MemPoolRemovalReason::REORG);
-        } else if (m_mempool->exists(GenTxid::Txid((*it)->GetHash()))) {
-            vHashUpdate.push_back((*it)->GetHash());
-        }
-        ++it;
-    }
-    disconnectpool.queuedTx.clear();
+    {
+        // disconnectpool is ordered so that the front is the most recently-confirmed
+        // transaction (the last tx of the block at the tip) in the disconnected chain.
+        // Iterate disconnectpool in reverse, so that we add transactions
+        // back to the mempool starting with the earliest transaction that had
+        // been previously seen in a block.
+        const auto queuedTx = disconnectpool.take();
+        auto it = queuedTx.rbegin();
+        while (it != queuedTx.rend()) {
+            // ignore validation errors in resurrected transactions
+            if (!fAddToMempool || (*it)->IsCoinBase() ||
+                AcceptToMemoryPool(*this, *it, GetTime(),
+                    /*bypass_limits=*/true, /*test_accept=*/false).m_result_type !=
+                        MempoolAcceptResult::ResultType::VALID) {
+                // If the transaction doesn't make it in to the mempool, remove any
+                // transactions that depend on it (which would now be orphans).
+                m_mempool->removeRecursive(**it, MemPoolRemovalReason::REORG);
+            } else if (m_mempool->exists(GenTxid::Txid((*it)->GetHash()))) {
+                vHashUpdate.push_back((*it)->GetHash());
+            }
+            ++it;
+        }
+    }
+
     // AcceptToMemoryPool/addUnchecked all assume that new mempool entries have
     // no in-mempool children, which is generally not true when adding
     // previously-confirmed transactions back to the mempool.
@@ -2795,15 +2796,10 @@ bool Chainstate::DisconnectTip(BlockValidationState& state, DisconnectedBlockTra
     }
 
     if (disconnectpool && m_mempool) {
-        // Save transactions to re-add to mempool at end of reorg
-        for (auto it = block.vtx.rbegin(); it != block.vtx.rend(); ++it) {
-            disconnectpool->addTransaction(*it);
-        }
-        while (disconnectpool->DynamicMemoryUsage() > MAX_DISCONNECTED_TX_POOL_SIZE * 1000) {
-            // Drop the earliest entry, and remove its children from the mempool.
-            auto it = disconnectpool->queuedTx.get<insertion_order>().begin();
-            m_mempool->removeRecursive(**it, MemPoolRemovalReason::REORG);
-            disconnectpool->removeEntry(it);
+        // Save transactions to re-add to mempool at end of reorg. If any entries are evicted for
+        // exceeding memory limits, remove them and their descendants from the mempool.
+        for (auto&& evicted_tx : disconnectpool->AddTransactionsFromBlock(block.vtx)) {
+            m_mempool->removeRecursive(*evicted_tx, MemPoolRemovalReason::REORG);
         }
     }
 
@@ -3053,7 +3049,7 @@ bool Chainstate::ActivateBestChainStep(BlockValidationState& state, CBlockIndex*
 
     // Disconnect active blocks which are no longer in the best chain.
     bool fBlocksDisconnected = false;
-    DisconnectedBlockTransactions disconnectpool;
+    DisconnectedBlockTransactions disconnectpool{MAX_DISCONNECTED_TX_POOL_SIZE * 1000};
     while (m_chain.Tip() && m_chain.Tip() != pindexFork) {
         if (!DisconnectTip(state, &disconnectpool)) {
             // This is likely a fatal error, but keep the mempool consistent,
@@ -3387,7 +3383,7 @@ bool Chainstate::InvalidateBlock(BlockValidationState& state, CBlockIndex* pinde
 
         // ActivateBestChain considers blocks already in m_chain
         // unconditionally valid already, so force disconnect away from it.
-        DisconnectedBlockTransactions disconnectpool;
+        DisconnectedBlockTransactions disconnectpool{MAX_DISCONNECTED_TX_POOL_SIZE * 1000};
         bool ret = DisconnectTip(state, &disconnectpool);
         // DisconnectTip will add transactions to disconnectpool.
         // Adjust the mempool to be consistent with the new tip, adding