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, 0 insertions, 92 deletions

diff --git a/src/txmempool.h b/src/txmempool.h
index 8ea3373cb4..cbeabb31fa 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -848,96 +848,4 @@ public:
     /** Clear m_temp_added and m_non_base_coins. */
     void Reset();
 };
-
-/**
- * DisconnectedBlockTransactions
-
- * During the reorg, it's desirable to re-add previously confirmed transactions
- * to the mempool, so that anything not re-confirmed in the new chain is
- * available to be mined. However, it's more efficient to wait until the reorg
- * is complete and process all still-unconfirmed transactions at that time,
- * since we expect most confirmed transactions to (typically) still be
- * confirmed in the new chain, and re-accepting to the memory pool is expensive
- * (and therefore better to not do in the middle of reorg-processing).
- * Instead, store the disconnected transactions (in order!) as we go, remove any
- * that are included in blocks in the new chain, and then process the remaining
- * still-unconfirmed transactions at the end.
- */
-
-// multi_index tag names
-struct txid_index {};
-struct insertion_order {};
-
-struct DisconnectedBlockTransactions {
-    typedef boost::multi_index_container<
-        CTransactionRef,
-        boost::multi_index::indexed_by<
-            // sorted by txid
-            boost::multi_index::hashed_unique<
-                boost::multi_index::tag<txid_index>,
-                mempoolentry_txid,
-                SaltedTxidHasher
-            >,
-            // sorted by order in the blockchain
-            boost::multi_index::sequenced<
-                boost::multi_index::tag<insertion_order>
-            >
-        >
-    > indexed_disconnected_transactions;
-
-    // It's almost certainly a logic bug if we don't clear out queuedTx before
-    // destruction, as we add to it while disconnecting blocks, and then we
-    // need to re-process remaining transactions to ensure mempool consistency.
-    // For now, assert() that we've emptied out this object on destruction.
-    // This assert() can always be removed if the reorg-processing code were
-    // to be refactored such that this assumption is no longer true (for
-    // instance if there was some other way we cleaned up the mempool after a
-    // reorg, besides draining this object).
-    ~DisconnectedBlockTransactions() { assert(queuedTx.empty()); }
-
-    indexed_disconnected_transactions queuedTx;
-    uint64_t cachedInnerUsage = 0;
-
-    // Estimate the overhead of queuedTx to be 6 pointers + an allocation, as
-    // no exact formula for boost::multi_index_contained is implemented.
-    size_t DynamicMemoryUsage() const {
-        return memusage::MallocUsage(sizeof(CTransactionRef) + 6 * sizeof(void*)) * queuedTx.size() + cachedInnerUsage;
-    }
-
-    void addTransaction(const CTransactionRef& tx)
-    {
-        queuedTx.insert(tx);
-        cachedInnerUsage += RecursiveDynamicUsage(tx);
-    }
-
-    // Remove entries based on txid_index, and update memory usage.
-    void removeForBlock(const std::vector<CTransactionRef>& vtx)
-    {
-        // Short-circuit in the common case of a block being added to the tip
-        if (queuedTx.empty()) {
-            return;
-        }
-        for (auto const &tx : vtx) {
-            auto it = queuedTx.find(tx->GetHash());
-            if (it != queuedTx.end()) {
-                cachedInnerUsage -= RecursiveDynamicUsage(*it);
-                queuedTx.erase(it);
-            }
-        }
-    }
-
-    // Remove an entry by insertion_order index, and update memory usage.
-    void removeEntry(indexed_disconnected_transactions::index<insertion_order>::type::iterator entry)
-    {
-        cachedInnerUsage -= RecursiveDynamicUsage(*entry);
-        queuedTx.get<insertion_order>().erase(entry);
-    }
-
-    void clear()
-    {
-        cachedInnerUsage = 0;
-        queuedTx.clear();
-    }
-};
-
 #endif // BITCOIN_TXMEMPOOL_H