Branch data     Line data    Source code

       1                 :            : // Copyright (c) 2023 The Bitcoin Core developers
       2                 :            : // Distributed under the MIT software license, see the accompanying
       3                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :            : 
       5                 :            : #ifndef BITCOIN_KERNEL_DISCONNECTED_TRANSACTIONS_H
       6                 :            : #define BITCOIN_KERNEL_DISCONNECTED_TRANSACTIONS_H
       7                 :            : 
       8                 :            : #include <core_memusage.h>
       9                 :            : #include <memusage.h>
      10                 :            : #include <primitives/transaction.h>
      11                 :            : #include <util/hasher.h>
      12                 :            : 
      13                 :            : #include <list>
      14                 :            : #include <unordered_map>
      15                 :            : #include <vector>
      16                 :            : 
      17                 :            : /** Maximum kilobytes for transactions to store for processing during reorg */
      18                 :            : static const unsigned int MAX_DISCONNECTED_TX_POOL_SIZE = 20'000;
      19                 :            : /**
      20                 :            :  * DisconnectedBlockTransactions
      21                 :            : 
      22                 :            :  * During the reorg, it's desirable to re-add previously confirmed transactions
      23                 :            :  * to the mempool, so that anything not re-confirmed in the new chain is
      24                 :            :  * available to be mined. However, it's more efficient to wait until the reorg
      25                 :            :  * is complete and process all still-unconfirmed transactions at that time,
      26                 :            :  * since we expect most confirmed transactions to (typically) still be
      27                 :            :  * confirmed in the new chain, and re-accepting to the memory pool is expensive
      28                 :            :  * (and therefore better to not do in the middle of reorg-processing).
      29                 :            :  * Instead, store the disconnected transactions (in order!) as we go, remove any
      30                 :            :  * that are included in blocks in the new chain, and then process the remaining
      31                 :            :  * still-unconfirmed transactions at the end.
      32                 :            :  *
      33                 :            :  * Order of queuedTx:
      34                 :            :  * The front of the list should be the most recently-confirmed transactions (transactions at the
      35                 :            :  * end of vtx of blocks closer to the tip). If memory usage grows too large, we trim from the front
      36                 :            :  * of the list. After trimming, transactions can be re-added to the mempool from the back of the
      37                 :            :  * list to the front without running into missing inputs.
      38                 :            :  */
      39                 :            : class DisconnectedBlockTransactions {
      40                 :            : private:
      41                 :            :     /** Cached dynamic memory usage for the CTransactions (memory for the shared pointers is
      42                 :            :      * included in the container calculations). */
      43                 :        201 :     uint64_t cachedInnerUsage = 0;
      44                 :            :     const size_t m_max_mem_usage;
      45                 :            :     std::list<CTransactionRef> queuedTx;
      46                 :            :     using TxList = decltype(queuedTx);
      47                 :            :     std::unordered_map<uint256, TxList::iterator, SaltedTxidHasher> iters_by_txid;
      48                 :            : 
      49                 :            :     /** Trim the earliest-added entries until we are within memory bounds. */
      50                 :          0 :     std::vector<CTransactionRef> LimitMemoryUsage()
      51                 :            :     {
      52                 :          0 :         std::vector<CTransactionRef> evicted;
      53                 :            : 
      54 [ #  # ][ #  # ]:          0 :         while (!queuedTx.empty() && DynamicMemoryUsage() > m_max_mem_usage) {
                 [ #  # ]
      55         [ #  # ]:          0 :             evicted.emplace_back(queuedTx.front());
      56         [ #  # ]:          0 :             cachedInnerUsage -= RecursiveDynamicUsage(*queuedTx.front());
      57         [ #  # ]:          0 :             iters_by_txid.erase(queuedTx.front()->GetHash());
      58                 :          0 :             queuedTx.pop_front();
      59                 :            :         }
      60                 :          0 :         return evicted;
      61         [ #  # ]:          0 :     }
      62                 :            : 
      63                 :            : public:
      64 [ +  - ][ +  - ]:        402 :     DisconnectedBlockTransactions(size_t max_mem_usage) : m_max_mem_usage{max_mem_usage} {}
      65                 :            : 
      66                 :            :     // It's almost certainly a logic bug if we don't clear out queuedTx before
      67                 :            :     // destruction, as we add to it while disconnecting blocks, and then we
      68                 :            :     // need to re-process remaining transactions to ensure mempool consistency.
      69                 :            :     // For now, assert() that we've emptied out this object on destruction.
      70                 :            :     // This assert() can always be removed if the reorg-processing code were
      71                 :            :     // to be refactored such that this assumption is no longer true (for
      72                 :            :     // instance if there was some other way we cleaned up the mempool after a
      73                 :            :     // reorg, besides draining this object).
      74                 :        201 :     ~DisconnectedBlockTransactions() {
      75         [ +  - ]:        201 :         assert(queuedTx.empty());
      76         [ +  - ]:        201 :         assert(iters_by_txid.empty());
      77         [ +  - ]:        201 :         assert(cachedInnerUsage == 0);
      78                 :        201 :     }
      79                 :            : 
      80                 :          0 :     size_t DynamicMemoryUsage() const {
      81                 :          0 :         return cachedInnerUsage + memusage::DynamicUsage(iters_by_txid) + memusage::DynamicUsage(queuedTx);
      82                 :            :     }
      83                 :            : 
      84                 :            :     /** Add transactions from the block, iterating through vtx in reverse order. Callers should call
      85                 :            :      * this function for blocks in descending order by block height.
      86                 :            :      * We assume that callers never pass multiple transactions with the same txid, otherwise things
      87                 :            :      * can go very wrong in removeForBlock due to queuedTx containing an item without a
      88                 :            :      * corresponding entry in iters_by_txid.
      89                 :            :      * @returns vector of transactions that were evicted for size-limiting.
      90                 :            :      */
      91                 :          0 :     [[nodiscard]] std::vector<CTransactionRef> AddTransactionsFromBlock(const std::vector<CTransactionRef>& vtx)
      92                 :            :     {
      93                 :          0 :         iters_by_txid.reserve(iters_by_txid.size() + vtx.size());
      94         [ #  # ]:          0 :         for (auto block_it = vtx.rbegin(); block_it != vtx.rend(); ++block_it) {
      95                 :          0 :             auto it = queuedTx.insert(queuedTx.end(), *block_it);
      96                 :          0 :             iters_by_txid.emplace((*block_it)->GetHash(), it);
      97                 :          0 :             cachedInnerUsage += RecursiveDynamicUsage(**block_it);
      98                 :          0 :         }
      99                 :          0 :         return LimitMemoryUsage();
     100                 :            :     }
     101                 :            : 
     102                 :            :     /** Remove any entries that are in this block. */
     103                 :        201 :     void removeForBlock(const std::vector<CTransactionRef>& vtx)
     104                 :            :     {
     105                 :            :         // Short-circuit in the common case of a block being added to the tip
     106         [ +  - ]:        201 :         if (queuedTx.empty()) {
     107                 :        201 :             return;
     108                 :            :         }
     109         [ #  # ]:          0 :         for (const auto& tx : vtx) {
     110                 :          0 :             auto iter = iters_by_txid.find(tx->GetHash());
     111         [ #  # ]:          0 :             if (iter != iters_by_txid.end()) {
     112                 :          0 :                 auto list_iter = iter->second;
     113                 :          0 :                 iters_by_txid.erase(iter);
     114                 :          0 :                 cachedInnerUsage -= RecursiveDynamicUsage(**list_iter);
     115                 :          0 :                 queuedTx.erase(list_iter);
     116                 :          0 :             }
     117                 :            :         }
     118                 :        201 :     }
     119                 :            : 
     120                 :            :     size_t size() const { return queuedTx.size(); }
     121                 :            : 
     122                 :          0 :     void clear()
     123                 :            :     {
     124                 :          0 :         cachedInnerUsage = 0;
     125                 :          0 :         iters_by_txid.clear();
     126                 :          0 :         queuedTx.clear();
     127                 :          0 :     }
     128                 :            : 
     129                 :            :     /** Clear all data structures and return the list of transactions. */
     130                 :          0 :     std::list<CTransactionRef> take()
     131                 :            :     {
     132                 :          0 :         std::list<CTransactionRef> ret = std::move(queuedTx);
     133         [ #  # ]:          0 :         clear();
     134                 :          0 :         return ret;
     135         [ #  # ]:          0 :     }
     136                 :            : };
     137                 :            : #endif // BITCOIN_KERNEL_DISCONNECTED_TRANSACTIONS_H