1  // Copyright (c) 2023-present 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  #include <bench/bench.h>
  6  #include <kernel/disconnected_transactions.h>
  7  #include <primitives/block.h>
  8  #include <primitives/transaction.h>
  9  #include <script/script.h>
 10  #include <test/util/setup_common.h>
 11  
 12  #include <algorithm>
 13  #include <cassert>
 14  #include <cstddef>
 15  #include <cstdint>
 16  #include <iterator>
 17  #include <memory>
 18  #include <vector>
 19  
 20  constexpr size_t BLOCK_VTX_COUNT{4000};
 21  constexpr size_t BLOCK_VTX_COUNT_10PERCENT{400};
 22  
 23  using BlockTxns = decltype(CBlock::vtx);
 24  
 25  /** Reorg where 1 block is disconnected and 2 blocks are connected. */
 26  struct ReorgTxns {
 27      /** Disconnected block. */
 28      BlockTxns disconnected_txns;
 29      /** First connected block. */
 30      BlockTxns connected_txns_1;
 31      /** Second connected block, new chain tip. Has no overlap with disconnected_txns. */
 32      BlockTxns connected_txns_2;
 33      /** Transactions shared between disconnected_txns and connected_txns_1. */
 34      size_t num_shared;
 35  };
 36  
 37  static BlockTxns CreateRandomTransactions(size_t num_txns)
 38  {
 39      // Ensure every transaction has a different txid by having each one spend the previous one.
 40      static Txid prevout_hash{};
 41  
 42      BlockTxns txns;
 43      txns.reserve(num_txns);
 44      // Simplest spk for every tx
 45      CScript spk = CScript() << OP_TRUE;
 46      for (uint32_t i = 0; i < num_txns; ++i) {
 47          CMutableTransaction tx;
 48          tx.vin.emplace_back(COutPoint{prevout_hash, 0});
 49          tx.vout.emplace_back(CENT, spk);
 50          auto ptx{MakeTransactionRef(tx)};
 51          txns.emplace_back(ptx);
 52          prevout_hash = ptx->GetHash();
 53      }
 54      return txns;
 55  }
 56  
 57  /** Creates blocks for a Reorg, each with BLOCK_VTX_COUNT transactions. Between the disconnected
 58   * block and the first connected block, there will be num_not_shared transactions that are
 59   * different, and all other transactions the exact same. The second connected block has all unique
 60   * transactions. This is to simulate a reorg in which all but num_not_shared transactions are
 61   * confirmed in the new chain. */
 62  static ReorgTxns CreateBlocks(size_t num_not_shared)
 63  {
 64      auto num_shared{BLOCK_VTX_COUNT - num_not_shared};
 65      const auto shared_txns{CreateRandomTransactions(/*num_txns=*/num_shared)};
 66  
 67      // Create different sets of transactions...
 68      auto disconnected_block_txns{CreateRandomTransactions(/*num_txns=*/num_not_shared)};
 69      std::copy(shared_txns.begin(), shared_txns.end(), std::back_inserter(disconnected_block_txns));
 70  
 71      auto connected_block_txns{CreateRandomTransactions(/*num_txns=*/num_not_shared)};
 72      std::copy(shared_txns.begin(), shared_txns.end(), std::back_inserter(connected_block_txns));
 73  
 74      assert(disconnected_block_txns.size() == BLOCK_VTX_COUNT);
 75      assert(connected_block_txns.size() == BLOCK_VTX_COUNT);
 76  
 77      return ReorgTxns{/*disconnected_txns=*/disconnected_block_txns,
 78                       /*connected_txns_1=*/connected_block_txns,
 79                       /*connected_txns_2=*/CreateRandomTransactions(BLOCK_VTX_COUNT),
 80                       /*num_shared=*/num_shared};
 81  }
 82  
 83  static void Reorg(const ReorgTxns& reorg)
 84  {
 85      DisconnectedBlockTransactions disconnectpool{MAX_DISCONNECTED_TX_POOL_BYTES};
 86      // Disconnect block
 87      const auto evicted = disconnectpool.AddTransactionsFromBlock(reorg.disconnected_txns);
 88      assert(evicted.empty());
 89  
 90      // Connect first block
 91      disconnectpool.removeForBlock(reorg.connected_txns_1);
 92      // Connect new tip
 93      disconnectpool.removeForBlock(reorg.connected_txns_2);
 94  
 95      // Sanity Check
 96      assert(disconnectpool.size() == BLOCK_VTX_COUNT - reorg.num_shared);
 97  
 98      disconnectpool.clear();
 99  }
100  
101  /** Add transactions from DisconnectedBlockTransactions, remove all but one (the disconnected
102   * block's coinbase transaction) of them, and then pop from the front until empty. This is a reorg
103   * in which all of the non-coinbase transactions in the disconnected chain also exist in the new
104   * chain. */
105  static void AddAndRemoveDisconnectedBlockTransactionsAll(benchmark::Bench& bench)
106  {
107      const auto chains{CreateBlocks(/*num_not_shared=*/1)};
108      assert(chains.num_shared == BLOCK_VTX_COUNT - 1);
109  
110      bench.minEpochIterations(10).run([&]() {
111          Reorg(chains);
112      });
113  }
114  
115  /** Add transactions from DisconnectedBlockTransactions, remove 90% of them, and then pop from the front until empty. */
116  static void AddAndRemoveDisconnectedBlockTransactions90(benchmark::Bench& bench)
117  {
118      const auto chains{CreateBlocks(/*num_not_shared=*/BLOCK_VTX_COUNT_10PERCENT)};
119      assert(chains.num_shared == BLOCK_VTX_COUNT - BLOCK_VTX_COUNT_10PERCENT);
120  
121      bench.minEpochIterations(10).run([&]() {
122          Reorg(chains);
123      });
124  }
125  
126  /** Add transactions from DisconnectedBlockTransactions, remove 10% of them, and then pop from the front until empty. */
127  static void AddAndRemoveDisconnectedBlockTransactions10(benchmark::Bench& bench)
128  {
129      const auto chains{CreateBlocks(/*num_not_shared=*/BLOCK_VTX_COUNT - BLOCK_VTX_COUNT_10PERCENT)};
130      assert(chains.num_shared == BLOCK_VTX_COUNT_10PERCENT);
131  
132      bench.minEpochIterations(10).run([&]() {
133          Reorg(chains);
134      });
135  }
136  
137  BENCHMARK(AddAndRemoveDisconnectedBlockTransactionsAll);
138  BENCHMARK(AddAndRemoveDisconnectedBlockTransactions90);
139  BENCHMARK(AddAndRemoveDisconnectedBlockTransactions10);