addrman.cpp
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 <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 NetGroupManager EMPTY_NETGROUPMAN{std::vector<bool>()}; 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, benchmark::PriorityLevel::HIGH); 179 BENCHMARK(AddrManSelect, benchmark::PriorityLevel::HIGH); 180 BENCHMARK(AddrManSelectFromAlmostEmpty, benchmark::PriorityLevel::HIGH); 181 BENCHMARK(AddrManSelectByNetwork, benchmark::PriorityLevel::HIGH); 182 BENCHMARK(AddrManGetAddr, benchmark::PriorityLevel::HIGH); 183 BENCHMARK(AddrManAddThenGood, benchmark::PriorityLevel::HIGH);