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