Branch data Line data Source code
# 1 : : // Copyright (c) 2021 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 <net.h>
# 6 : : #include <test/util/setup_common.h>
# 7 : :
# 8 : : #include <boost/test/unit_test.hpp>
# 9 : :
# 10 : : #include <algorithm>
# 11 : : #include <functional>
# 12 : : #include <optional>
# 13 : : #include <unordered_set>
# 14 : : #include <vector>
# 15 : :
# 16 : : BOOST_FIXTURE_TEST_SUITE(net_peer_eviction_tests, BasicTestingSetup)
# 17 : :
# 18 : : namespace {
# 19 : : constexpr int NODE_EVICTION_TEST_ROUNDS{10};
# 20 : : constexpr int NODE_EVICTION_TEST_UP_TO_N_NODES{200};
# 21 : : } // namespace
# 22 : :
# 23 : : std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context)
# 24 : 31864 : {
# 25 : 31864 : std::vector<NodeEvictionCandidate> candidates;
# 26 [ + + ]: 3212220 : for (int id = 0; id < n_candidates; ++id) {
# 27 : 3180356 : candidates.push_back({
# 28 : 3180356 : /* id */ id,
# 29 : 3180356 : /* nTimeConnected */ static_cast<int64_t>(random_context.randrange(100)),
# 30 : 3180356 : /* m_min_ping_time */ std::chrono::microseconds{random_context.randrange(100)},
# 31 : 3180356 : /* nLastBlockTime */ static_cast<int64_t>(random_context.randrange(100)),
# 32 : 3180356 : /* nLastTXTime */ static_cast<int64_t>(random_context.randrange(100)),
# 33 : 3180356 : /* fRelevantServices */ random_context.randbool(),
# 34 : 3180356 : /* fRelayTxes */ random_context.randbool(),
# 35 : 3180356 : /* fBloomFilter */ random_context.randbool(),
# 36 : 3180356 : /* nKeyedNetGroup */ random_context.randrange(100),
# 37 : 3180356 : /* prefer_evict */ random_context.randbool(),
# 38 : 3180356 : /* m_is_local */ random_context.randbool(),
# 39 : 3180356 : /* m_is_onion */ random_context.randbool(),
# 40 : 3180356 : });
# 41 : 3180356 : }
# 42 : 31864 : return candidates;
# 43 : 31864 : }
# 44 : :
# 45 : : // Create `num_peers` random nodes, apply setup function `candidate_setup_fn`,
# 46 : : // call ProtectEvictionCandidatesByRatio() to apply protection logic, and then
# 47 : : // return true if all of `protected_peer_ids` and none of `unprotected_peer_ids`
# 48 : : // are protected from eviction, i.e. removed from the eviction candidates.
# 49 : : bool IsProtected(int num_peers,
# 50 : : std::function<void(NodeEvictionCandidate&)> candidate_setup_fn,
# 51 : : const std::unordered_set<NodeId>& protected_peer_ids,
# 52 : : const std::unordered_set<NodeId>& unprotected_peer_ids,
# 53 : : FastRandomContext& random_context)
# 54 : 24 : {
# 55 : 24 : std::vector<NodeEvictionCandidate> candidates{GetRandomNodeEvictionCandidates(num_peers, random_context)};
# 56 [ + + ]: 276 : for (NodeEvictionCandidate& candidate : candidates) {
# 57 : 276 : candidate_setup_fn(candidate);
# 58 : 276 : }
# 59 : 24 : Shuffle(candidates.begin(), candidates.end(), random_context);
# 60 : :
# 61 : 24 : const size_t size{candidates.size()};
# 62 : 24 : const size_t expected{size - size / 2}; // Expect half the candidates will be protected.
# 63 : 24 : ProtectEvictionCandidatesByRatio(candidates);
# 64 : 24 : BOOST_CHECK_EQUAL(candidates.size(), expected);
# 65 : :
# 66 : 24 : size_t unprotected_count{0};
# 67 [ + + ]: 138 : for (const NodeEvictionCandidate& candidate : candidates) {
# 68 [ - + ]: 138 : if (protected_peer_ids.count(candidate.id)) {
# 69 : : // this peer should have been removed from the eviction candidates
# 70 : 0 : BOOST_TEST_MESSAGE(strprintf("expected candidate to be protected: %d", candidate.id));
# 71 : 0 : return false;
# 72 : 0 : }
# 73 [ + + ]: 138 : if (unprotected_peer_ids.count(candidate.id)) {
# 74 : : // this peer remains in the eviction candidates, as expected
# 75 : 114 : ++unprotected_count;
# 76 : 114 : }
# 77 : 138 : }
# 78 : :
# 79 : 24 : const bool is_protected{unprotected_count == unprotected_peer_ids.size()};
# 80 [ - + ]: 24 : if (!is_protected) {
# 81 : 0 : BOOST_TEST_MESSAGE(strprintf("unprotected: expected %d, actual %d",
# 82 : 0 : unprotected_peer_ids.size(), unprotected_count));
# 83 : 0 : }
# 84 : 24 : return is_protected;
# 85 : 24 : }
# 86 : :
# 87 : : BOOST_AUTO_TEST_CASE(peer_protection_test)
# 88 : 2 : {
# 89 : 2 : FastRandomContext random_context{true};
# 90 : 2 : int num_peers{12};
# 91 : :
# 92 : : // Expect half of the peers with greatest uptime (the lowest nTimeConnected)
# 93 : : // to be protected from eviction.
# 94 : 2 : BOOST_CHECK(IsProtected(
# 95 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 96 : 2 : c.nTimeConnected = c.id;
# 97 : 2 : c.m_is_onion = c.m_is_local = false;
# 98 : 2 : },
# 99 : 2 : /* protected_peer_ids */ {0, 1, 2, 3, 4, 5},
# 100 : 2 : /* unprotected_peer_ids */ {6, 7, 8, 9, 10, 11},
# 101 : 2 : random_context));
# 102 : :
# 103 : : // Verify in the opposite direction.
# 104 : 2 : BOOST_CHECK(IsProtected(
# 105 : 2 : num_peers, [num_peers](NodeEvictionCandidate& c) {
# 106 : 2 : c.nTimeConnected = num_peers - c.id;
# 107 : 2 : c.m_is_onion = c.m_is_local = false;
# 108 : 2 : },
# 109 : 2 : /* protected_peer_ids */ {6, 7, 8, 9, 10, 11},
# 110 : 2 : /* unprotected_peer_ids */ {0, 1, 2, 3, 4, 5},
# 111 : 2 : random_context));
# 112 : :
# 113 : : // Test protection of onion and localhost peers...
# 114 : :
# 115 : : // Expect 1/4 onion peers to be protected from eviction,
# 116 : : // independently of other characteristics.
# 117 : 2 : BOOST_CHECK(IsProtected(
# 118 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 119 : 2 : c.m_is_onion = (c.id == 3 || c.id == 8 || c.id == 9);
# 120 : 2 : },
# 121 : 2 : /* protected_peer_ids */ {3, 8, 9},
# 122 : 2 : /* unprotected_peer_ids */ {},
# 123 : 2 : random_context));
# 124 : :
# 125 : : // Expect 1/4 onion peers and 1/4 of the others to be protected
# 126 : : // from eviction, sorted by longest uptime (lowest nTimeConnected).
# 127 : 2 : BOOST_CHECK(IsProtected(
# 128 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 129 : 2 : c.nTimeConnected = c.id;
# 130 : 2 : c.m_is_local = false;
# 131 : 2 : c.m_is_onion = (c.id == 3 || c.id > 7);
# 132 : 2 : },
# 133 : 2 : /* protected_peer_ids */ {0, 1, 2, 3, 8, 9},
# 134 : 2 : /* unprotected_peer_ids */ {4, 5, 6, 7, 10, 11},
# 135 : 2 : random_context));
# 136 : :
# 137 : : // Expect 1/4 localhost peers to be protected from eviction,
# 138 : : // if no onion peers.
# 139 : 2 : BOOST_CHECK(IsProtected(
# 140 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 141 : 2 : c.m_is_onion = false;
# 142 : 2 : c.m_is_local = (c.id == 1 || c.id == 9 || c.id == 11);
# 143 : 2 : },
# 144 : 2 : /* protected_peer_ids */ {1, 9, 11},
# 145 : 2 : /* unprotected_peer_ids */ {},
# 146 : 2 : random_context));
# 147 : :
# 148 : : // Expect 1/4 localhost peers and 1/4 of the other peers to be protected,
# 149 : : // sorted by longest uptime (lowest nTimeConnected), if no onion peers.
# 150 : 2 : BOOST_CHECK(IsProtected(
# 151 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 152 : 2 : c.nTimeConnected = c.id;
# 153 : 2 : c.m_is_onion = false;
# 154 : 2 : c.m_is_local = (c.id > 6);
# 155 : 2 : },
# 156 : 2 : /* protected_peer_ids */ {0, 1, 2, 7, 8, 9},
# 157 : 2 : /* unprotected_peer_ids */ {3, 4, 5, 6, 10, 11},
# 158 : 2 : random_context));
# 159 : :
# 160 : : // Combined test: expect 1/4 onion and 2 localhost peers to be protected
# 161 : : // from eviction, sorted by longest uptime.
# 162 : 2 : BOOST_CHECK(IsProtected(
# 163 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 164 : 2 : c.nTimeConnected = c.id;
# 165 : 2 : c.m_is_onion = (c.id == 0 || c.id == 5 || c.id == 10);
# 166 : 2 : c.m_is_local = (c.id == 1 || c.id == 9 || c.id == 11);
# 167 : 2 : },
# 168 : 2 : /* protected_peer_ids */ {0, 1, 2, 5, 9, 10},
# 169 : 2 : /* unprotected_peer_ids */ {3, 4, 6, 7, 8, 11},
# 170 : 2 : random_context));
# 171 : :
# 172 : : // Combined test: expect having only 1 onion to allow allocating the
# 173 : : // remaining 2 of the 1/4 to localhost peers, sorted by longest uptime.
# 174 : 2 : BOOST_CHECK(IsProtected(
# 175 : 2 : num_peers + 4, [](NodeEvictionCandidate& c) {
# 176 : 2 : c.nTimeConnected = c.id;
# 177 : 2 : c.m_is_onion = (c.id == 15);
# 178 : 2 : c.m_is_local = (c.id > 6 && c.id < 11);
# 179 : 2 : },
# 180 : 2 : /* protected_peer_ids */ {0, 1, 2, 3, 7, 8, 9, 15},
# 181 : 2 : /* unprotected_peer_ids */ {4, 5, 6, 10, 11, 12, 13, 14},
# 182 : 2 : random_context));
# 183 : :
# 184 : : // Combined test: expect 2 onions (< 1/4) to allow allocating the minimum 2
# 185 : : // localhost peers, sorted by longest uptime.
# 186 : 2 : BOOST_CHECK(IsProtected(
# 187 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 188 : 2 : c.nTimeConnected = c.id;
# 189 : 2 : c.m_is_onion = (c.id == 7 || c.id == 9);
# 190 : 2 : c.m_is_local = (c.id == 6 || c.id == 11);
# 191 : 2 : },
# 192 : 2 : /* protected_peer_ids */ {0, 1, 6, 7, 9, 11},
# 193 : 2 : /* unprotected_peer_ids */ {2, 3, 4, 5, 8, 10},
# 194 : 2 : random_context));
# 195 : :
# 196 : : // Combined test: when > 1/4, expect max 1/4 onion and 2 localhost peers
# 197 : : // to be protected from eviction, sorted by longest uptime.
# 198 : 2 : BOOST_CHECK(IsProtected(
# 199 : 2 : num_peers, [](NodeEvictionCandidate& c) {
# 200 : 2 : c.nTimeConnected = c.id;
# 201 : 2 : c.m_is_onion = (c.id > 3 && c.id < 8);
# 202 : 2 : c.m_is_local = (c.id > 7);
# 203 : 2 : },
# 204 : 2 : /* protected_peer_ids */ {0, 4, 5, 6, 8, 9},
# 205 : 2 : /* unprotected_peer_ids */ {1, 2, 3, 7, 10, 11},
# 206 : 2 : random_context));
# 207 : :
# 208 : : // Combined test: idem > 1/4 with only 8 peers: expect 2 onion and 2
# 209 : : // localhost peers (1/4 + 2) to be protected, sorted by longest uptime.
# 210 : 2 : BOOST_CHECK(IsProtected(
# 211 : 2 : 8, [](NodeEvictionCandidate& c) {
# 212 : 2 : c.nTimeConnected = c.id;
# 213 : 2 : c.m_is_onion = (c.id > 1 && c.id < 5);
# 214 : 2 : c.m_is_local = (c.id > 4);
# 215 : 2 : },
# 216 : 2 : /* protected_peer_ids */ {2, 3, 5, 6},
# 217 : 2 : /* unprotected_peer_ids */ {0, 1, 4, 7},
# 218 : 2 : random_context));
# 219 : :
# 220 : : // Combined test: idem > 1/4 with only 6 peers: expect 1 onion peer and no
# 221 : : // localhost peers (1/4 + 0) to be protected, sorted by longest uptime.
# 222 : 2 : BOOST_CHECK(IsProtected(
# 223 : 2 : 6, [](NodeEvictionCandidate& c) {
# 224 : 2 : c.nTimeConnected = c.id;
# 225 : 2 : c.m_is_onion = (c.id == 4 || c.id == 5);
# 226 : 2 : c.m_is_local = (c.id == 3);
# 227 : 2 : },
# 228 : 2 : /* protected_peer_ids */ {0, 1, 4},
# 229 : 2 : /* unprotected_peer_ids */ {2, 3, 5},
# 230 : 2 : random_context));
# 231 : 2 : }
# 232 : :
# 233 : : // Returns true if any of the node ids in node_ids are selected for eviction.
# 234 : : bool IsEvicted(std::vector<NodeEvictionCandidate> candidates, const std::unordered_set<NodeId>& node_ids, FastRandomContext& random_context)
# 235 : 28000 : {
# 236 : 28000 : Shuffle(candidates.begin(), candidates.end(), random_context);
# 237 : 28000 : const std::optional<NodeId> evicted_node_id = SelectNodeToEvict(std::move(candidates));
# 238 [ + + ]: 28000 : if (!evicted_node_id) {
# 239 : 3282 : return false;
# 240 : 3282 : }
# 241 : 24718 : return node_ids.count(*evicted_node_id);
# 242 : 24718 : }
# 243 : :
# 244 : : // Create number_of_nodes random nodes, apply setup function candidate_setup_fn,
# 245 : : // apply eviction logic and then return true if any of the node ids in node_ids
# 246 : : // are selected for eviction.
# 247 : : bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::unordered_set<NodeId>& node_ids, FastRandomContext& random_context)
# 248 : 28000 : {
# 249 : 28000 : std::vector<NodeEvictionCandidate> candidates = GetRandomNodeEvictionCandidates(number_of_nodes, random_context);
# 250 [ + + ]: 2786000 : for (NodeEvictionCandidate& candidate : candidates) {
# 251 : 2786000 : candidate_setup_fn(candidate);
# 252 : 2786000 : }
# 253 : 28000 : return IsEvicted(candidates, node_ids, random_context);
# 254 : 28000 : }
# 255 : :
# 256 : : BOOST_AUTO_TEST_CASE(peer_eviction_test)
# 257 : 2 : {
# 258 : 2 : FastRandomContext random_context{true};
# 259 : :
# 260 [ + + ]: 22 : for (int i = 0; i < NODE_EVICTION_TEST_ROUNDS; ++i) {
# 261 [ + + ]: 4020 : for (int number_of_nodes = 0; number_of_nodes < NODE_EVICTION_TEST_UP_TO_N_NODES; ++number_of_nodes) {
# 262 : : // Four nodes with the highest keyed netgroup values should be
# 263 : : // protected from eviction.
# 264 : 4000 : BOOST_CHECK(!IsEvicted(
# 265 : 4000 : number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
# 266 : 4000 : candidate.nKeyedNetGroup = number_of_nodes - candidate.id;
# 267 : 4000 : },
# 268 : 4000 : {0, 1, 2, 3}, random_context));
# 269 : :
# 270 : : // Eight nodes with the lowest minimum ping time should be protected
# 271 : : // from eviction.
# 272 : 4000 : BOOST_CHECK(!IsEvicted(
# 273 : 4000 : number_of_nodes, [](NodeEvictionCandidate& candidate) {
# 274 : 4000 : candidate.m_min_ping_time = std::chrono::microseconds{candidate.id};
# 275 : 4000 : },
# 276 : 4000 : {0, 1, 2, 3, 4, 5, 6, 7}, random_context));
# 277 : :
# 278 : : // Four nodes that most recently sent us novel transactions accepted
# 279 : : // into our mempool should be protected from eviction.
# 280 : 4000 : BOOST_CHECK(!IsEvicted(
# 281 : 4000 : number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
# 282 : 4000 : candidate.nLastTXTime = number_of_nodes - candidate.id;
# 283 : 4000 : },
# 284 : 4000 : {0, 1, 2, 3}, random_context));
# 285 : :
# 286 : : // Up to eight non-tx-relay peers that most recently sent us novel
# 287 : : // blocks should be protected from eviction.
# 288 : 4000 : BOOST_CHECK(!IsEvicted(
# 289 : 4000 : number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
# 290 : 4000 : candidate.nLastBlockTime = number_of_nodes - candidate.id;
# 291 : 4000 : if (candidate.id <= 7) {
# 292 : 4000 : candidate.fRelayTxes = false;
# 293 : 4000 : candidate.fRelevantServices = true;
# 294 : 4000 : }
# 295 : 4000 : },
# 296 : 4000 : {0, 1, 2, 3, 4, 5, 6, 7}, random_context));
# 297 : :
# 298 : : // Four peers that most recently sent us novel blocks should be
# 299 : : // protected from eviction.
# 300 : 4000 : BOOST_CHECK(!IsEvicted(
# 301 : 4000 : number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
# 302 : 4000 : candidate.nLastBlockTime = number_of_nodes - candidate.id;
# 303 : 4000 : },
# 304 : 4000 : {0, 1, 2, 3}, random_context));
# 305 : :
# 306 : : // Combination of the previous two tests.
# 307 : 4000 : BOOST_CHECK(!IsEvicted(
# 308 : 4000 : number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
# 309 : 4000 : candidate.nLastBlockTime = number_of_nodes - candidate.id;
# 310 : 4000 : if (candidate.id <= 7) {
# 311 : 4000 : candidate.fRelayTxes = false;
# 312 : 4000 : candidate.fRelevantServices = true;
# 313 : 4000 : }
# 314 : 4000 : },
# 315 : 4000 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, random_context));
# 316 : :
# 317 : : // Combination of all tests above.
# 318 : 4000 : BOOST_CHECK(!IsEvicted(
# 319 : 4000 : number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
# 320 : 4000 : candidate.nKeyedNetGroup = number_of_nodes - candidate.id; // 4 protected
# 321 : 4000 : candidate.m_min_ping_time = std::chrono::microseconds{candidate.id}; // 8 protected
# 322 : 4000 : candidate.nLastTXTime = number_of_nodes - candidate.id; // 4 protected
# 323 : 4000 : candidate.nLastBlockTime = number_of_nodes - candidate.id; // 4 protected
# 324 : 4000 : },
# 325 : 4000 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}, random_context));
# 326 : :
# 327 : : // An eviction is expected given >= 29 random eviction candidates. The eviction logic protects at most
# 328 : : // four peers by net group, eight by lowest ping time, four by last time of novel tx, up to eight non-tx-relay
# 329 : : // peers by last novel block time, and four more peers by last novel block time.
# 330 [ + + ]: 4000 : if (number_of_nodes >= 29) {
# 331 : 3420 : BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
# 332 : 3420 : }
# 333 : :
# 334 : : // No eviction is expected given <= 20 random eviction candidates. The eviction logic protects at least
# 335 : : // four peers by net group, eight by lowest ping time, four by last time of novel tx and four peers by last
# 336 : : // novel block time.
# 337 [ + + ]: 4000 : if (number_of_nodes <= 20) {
# 338 : 420 : BOOST_CHECK(!SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
# 339 : 420 : }
# 340 : :
# 341 : : // Cases left to test:
# 342 : : // * "If any remaining peers are preferred for eviction consider only them. [...]"
# 343 : : // * "Identify the network group with the most connections and youngest member. [...]"
# 344 : 4000 : }
# 345 : 20 : }
# 346 : 2 : }
# 347 : :
# 348 : : BOOST_AUTO_TEST_SUITE_END()
|
