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