test: Add unit testing of node eviction logic

bitcoin · Dec 5, 2020 · 071b4cd · 071b4cd
1 parent ae55444
commit 071b4cd
Showing 1 changed file with 123 additions and 0 deletions.
diff --git a/src/test/net_tests.cpp b/src/test/net_tests.cpp
@@ -9,6 +9,7 @@
 #include <cstdint>
 #include <net.h>
 #include <netbase.h>
+#include <optional.h>
 #include <serialize.h>
 #include <span.h>
 #include <streams.h>
@@ -21,6 +22,7 @@
 
 #include <boost/test/unit_test.hpp>
 
+#include <algorithm>
 #include <ios>
 #include <memory>
 #include <string>
@@ -771,4 +773,125 @@ BOOST_AUTO_TEST_CASE(PoissonNextSend)
     g_mock_deterministic_tests = false;
 }
 
+std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context)
+{
+    std::vector<NodeEvictionCandidate> candidates;
+    for (int id = 0; id < n_candidates; ++id) {
+        candidates.push_back({/* id */ id,
+                              /* nTimeConnected */ static_cast<int64_t>(random_context.randrange(100)),
+                              /* nMinPingUsecTime */ static_cast<int64_t>(random_context.randrange(100)),
+                              /* nLastBlockTime */ static_cast<int64_t>(random_context.randrange(100)),
+                              /* nLastTXTime */ static_cast<int64_t>(random_context.randrange(100)),
+                              /* fRelevantServices */ random_context.randbool(),
+                              /* fRelayTxes */ random_context.randbool(),
+                              /* fBloomFilter */ random_context.randbool(),
+                              /* nKeyedNetGroup */ random_context.randrange(100),
+                              /* prefer_evict */ random_context.randbool(),
+                              /* m_is_local */ random_context.randbool()});
+    }
+    return candidates;
+}
+
+bool IsEvicted(const std::vector<NodeEvictionCandidate>& candidates, const std::vector<NodeId> node_ids, FastRandomContext& random_context)
+{
+    std::vector<NodeEvictionCandidate> shuffled_candidates = candidates;
+    Shuffle(shuffled_candidates.begin(), shuffled_candidates.end(), random_context);
+    const Optional<NodeId> evicted_node_id = SelectNodeToEvict(std::move(shuffled_candidates));
+    if (!evicted_node_id) {
+        return false;
+    }
+    return std::find(node_ids.begin(), node_ids.end(), *evicted_node_id) != node_ids.end();
+}
+
+bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::vector<NodeId> node_ids, FastRandomContext& random_context)
+{
+    std::vector<NodeEvictionCandidate> candidates = GetRandomNodeEvictionCandidates(number_of_nodes, random_context);
+    for (size_t i = 0; i < candidates.size(); ++i) {
+        candidate_setup_fn(candidates[i]);
+    }
+    return IsEvicted(candidates, node_ids, random_context);
+}
+
+namespace {
+// The number of eviction candidates at (or above) which we are guaranteed that
+// the current eviction logic will find a node to evict no matter what eviction
+// candidates it is given. This constant may need to be adjusted if the eviction
+// logic changes.
+constexpr int GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE{29};
+
+// The number of eviction candidates at (or below) which we are guaranteed that
+// the current eviction logic won't find a node to evict no matter what eviction
+// candidates it is given. This constant may need to be adjusted if the eviction
+// logic changes.
+constexpr int GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW{20};
+
+constexpr int NODE_EVICTION_TEST_ROUNDS{10};
+
+constexpr int NODE_EVICTION_TEST_UP_TO_N_NODES{200};
+} // namespace
+
+static_assert(GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE > GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW);
+
+BOOST_AUTO_TEST_CASE(node_eviction_test)
+{
+    FastRandomContext random_context{true};
+
+    for (int i = 0; i < NODE_EVICTION_TEST_ROUNDS; ++i) {
+        for (int number_of_nodes = 0; number_of_nodes < NODE_EVICTION_TEST_UP_TO_N_NODES; ++number_of_nodes) {
+            // Verify correctness of GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE
+            // and GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW.
+            if (number_of_nodes <= GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW) {
+                BOOST_CHECK(!SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
+            }
+            if (number_of_nodes >= GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE) {
+                BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
+            } else {
+                continue;
+            }
+
+            // Four nodes with the highest keyed netgroup values should be
+            // protected from eviction.
+            BOOST_CHECK(!IsEvicted(
+                number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
+                    candidate.nKeyedNetGroup = number_of_nodes - candidate.id;
+                },
+                {0, 1, 2, 3}, random_context));
+
+            // Eight nodes with the lowest minimum ping time should be protected
+            // from eviction.
+            BOOST_CHECK(!IsEvicted(
+                number_of_nodes, [](NodeEvictionCandidate& candidate) {
+                    candidate.nMinPingUsecTime = candidate.id;
+                },
+                {0, 1, 2, 3, 4, 5, 6, 7}, random_context));
+
+            // Four nodes that most recently sent us novel transactions accepted
+            // into our mempool should be protected from eviction.
+            BOOST_CHECK(!IsEvicted(
+                number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
+                    candidate.nLastTXTime = number_of_nodes - candidate.id;
+                },
+                {0, 1, 2, 3}, random_context));
+
+            // Eight non-tx-relay peers that most recently sent us novel blocks
+            // should be protected from eviction.
+            BOOST_CHECK(!IsEvicted(
+                number_of_nodes, [number_of_nodes](NodeEvictionCandidate& candidate) {
+                    candidate.nLastBlockTime = number_of_nodes - candidate.id;
+                    if (candidate.id <= 7) {
+                        candidate.fRelayTxes = false;
+                        candidate.fRelevantServices = true;
+                    }
+                },
+                {0, 1, 2, 3, 4, 5, 6, 7}, random_context));
+
+            // Cases left to test:
+            // * "Protect the half of the remaining nodes which have been connected the longest. [...]"
+            // * "Pick out up to 1/4 peers that are localhost, sorted by longest uptime. [...]"
+            // * "If any remaining peers are preferred for eviction consider only them. [...]"
+            // * "Identify the network group with the most connections and youngest member. [...]"
+        }
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()