1  // Copyright (c) 2020-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 <addrman.h>
  6  #include <bench/bench.h>
  7  #include <compat/compat.h>
  8  #include <netaddress.h>
  9  #include <netbase.h>
 10  #include <netgroup.h>
 11  #include <protocol.h>
 12  #include <random.h>
 13  #include <span.h>
 14  #include <uint256.h>
 15  #include <util/check.h>
 16  #include <util/time.h>
 17  
 18  #include <cstring>
 19  #include <optional>
 20  #include <vector>
 21  
 22  /* A "source" is a source address from which we have received a bunch of other addresses. */
 23  
 24  static constexpr size_t NUM_SOURCES = 64;
 25  static constexpr size_t NUM_ADDRESSES_PER_SOURCE = 256;
 26  
 27  static auto EMPTY_NETGROUPMAN{NetGroupManager::NoAsmap()};
 28  static constexpr uint32_t ADDRMAN_CONSISTENCY_CHECK_RATIO{0};
 29  
 30  static std::vector<CAddress> g_sources;
 31  static std::vector<std::vector<CAddress>> g_addresses;
 32  
 33  static void CreateAddresses()
 34  {
 35      if (g_sources.size() > 0) { // already created
 36          return;
 37      }
 38  
 39      FastRandomContext rng(uint256(std::vector<unsigned char>(32, 123)));
 40  
 41      auto randAddr = [&rng]() {
 42          in6_addr addr;
 43          memcpy(&addr, rng.randbytes(sizeof(addr)).data(), sizeof(addr));
 44  
 45          uint16_t port;
 46          memcpy(&port, rng.randbytes(sizeof(port)).data(), sizeof(port));
 47          if (port == 0) {
 48              port = 1;
 49          }
 50  
 51          CAddress ret(CService(addr, port), NODE_NETWORK);
 52  
 53          ret.nTime = Now<NodeSeconds>();
 54  
 55          return ret;
 56      };
 57  
 58      for (size_t source_i = 0; source_i < NUM_SOURCES; ++source_i) {
 59          g_sources.emplace_back(randAddr());
 60          g_addresses.emplace_back();
 61          for (size_t addr_i = 0; addr_i < NUM_ADDRESSES_PER_SOURCE; ++addr_i) {
 62              g_addresses[source_i].emplace_back(randAddr());
 63          }
 64      }
 65  }
 66  
 67  static void AddAddressesToAddrMan(AddrMan& addrman)
 68  {
 69      for (size_t source_i = 0; source_i < NUM_SOURCES; ++source_i) {
 70          addrman.Add(g_addresses[source_i], g_sources[source_i]);
 71      }
 72  }
 73  
 74  static void FillAddrMan(AddrMan& addrman)
 75  {
 76      CreateAddresses();
 77  
 78      AddAddressesToAddrMan(addrman);
 79  }
 80  
 81  /* Benchmarks */
 82  
 83  static void AddrManAdd(benchmark::Bench& bench)
 84  {
 85      CreateAddresses();
 86  
 87      bench.run([&] {
 88          AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
 89          AddAddressesToAddrMan(addrman);
 90      });
 91  }
 92  
 93  static void AddrManSelect(benchmark::Bench& bench)
 94  {
 95      AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
 96  
 97      FillAddrMan(addrman);
 98  
 99      bench.run([&] {
100          const auto& address = addrman.Select();
101          assert(address.first.GetPort() > 0);
102      });
103  }
104  
105  // The worst case performance of the Select() function is when there is only
106  // one address on the table, because it linearly searches every position of
107  // several buckets before identifying the correct bucket
108  static void AddrManSelectFromAlmostEmpty(benchmark::Bench& bench)
109  {
110      AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
111  
112      // Add one address to the new table
113      CService addr = Lookup("250.3.1.1", 8333, false).value();
114      addrman.Add({CAddress(addr, NODE_NONE)}, addr);
115  
116      bench.run([&] {
117          (void)addrman.Select();
118      });
119  }
120  
121  static void AddrManSelectByNetwork(benchmark::Bench& bench)
122  {
123      AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
124  
125      // add single I2P address to new table
126      CService i2p_service;
127      i2p_service.SetSpecial("udhdrtrcetjm5sxzskjyr5ztpeszydbh4dpl3pl4utgqqw2v4jna.b32.i2p");
128      CAddress i2p_address(i2p_service, NODE_NONE);
129      i2p_address.nTime = Now<NodeSeconds>();
130      const CNetAddr source{LookupHost("252.2.2.2", false).value()};
131      addrman.Add({i2p_address}, source);
132  
133      FillAddrMan(addrman);
134  
135      bench.run([&] {
136          (void)addrman.Select(/*new_only=*/false, {NET_I2P});
137      });
138  }
139  
140  static void AddrManGetAddr(benchmark::Bench& bench)
141  {
142      AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
143  
144      FillAddrMan(addrman);
145  
146      bench.run([&] {
147          const auto& addresses = addrman.GetAddr(/*max_addresses=*/2500, /*max_pct=*/23, /*network=*/std::nullopt);
148          assert(addresses.size() > 0);
149      });
150  }
151  
152  static void AddrManAddThenGood(benchmark::Bench& bench)
153  {
154      auto markSomeAsGood = [](AddrMan& addrman) {
155          for (size_t source_i = 0; source_i < NUM_SOURCES; ++source_i) {
156              for (size_t addr_i = 0; addr_i < NUM_ADDRESSES_PER_SOURCE; ++addr_i) {
157                  addrman.Good(g_addresses[source_i][addr_i]);
158              }
159          }
160      };
161  
162      CreateAddresses();
163  
164      bench.run([&] {
165          // To make the benchmark independent of the number of evaluations, we always prepare a new addrman.
166          // This is necessary because AddrMan::Good() method modifies the object, affecting the timing of subsequent calls
167          // to the same method and we want to do the same amount of work in every loop iteration.
168          //
169          // This has some overhead (exactly the result of AddrManAdd benchmark), but that overhead is constant so improvements in
170          // AddrMan::Good() will still be noticeable.
171          AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
172          AddAddressesToAddrMan(addrman);
173  
174          markSomeAsGood(addrman);
175      });
176  }
177  
178  BENCHMARK(AddrManAdd);
179  BENCHMARK(AddrManSelect);
180  BENCHMARK(AddrManSelectFromAlmostEmpty);
181  BENCHMARK(AddrManSelectByNetwork);
182  BENCHMARK(AddrManGetAddr);
183  BENCHMARK(AddrManAddThenGood);