Merge bitcoin/bitcoin#22284: p2p, refactor: performance improvements to ProtectEvictionCandidatesByRatio()

b1d905c225e87a4a289c0cd3593c6c21cea3fba7 p2p: earlier continuation when no remaining eviction candidates (Vasil Dimov)
c9e8d8f9b168dec2bc7b845da38449e96708cf8e p2p: process more candidates per protection iteration (Jon Atack)
02e411ec456af80d1da76085a814c68bb3aca6de p2p: iterate eviction protection only on networks having candidates (Jon Atack)
5adb06457403f8c1d874e9c6748ecbb78ef8fa2b bench: add peer eviction protection benchmarks (Jon Atack)
566357f8f7471f74729297868917aa32f6d3c390 refactor: move GetRandomNodeEvictionCandidates() to test utilities (Jon Atack)

Pull request description:

  This follow-up to #21261 improves `ProtectEvictionCandidatesByRatio()` for better performance.

  Benchmarks are added; the performance improvement is between 2x and 5x for the benchmarked cases (CPU 2.50GHz, Turbo off, performance mode, Debian Clang 11 non-debug build).

  ```
  $ ./src/bench/bench_bitcoin -filter="EvictionProtection*.*"
  ```

  The refactored code is well-covered by existing unit tests and also a fuzzer.

  - `$ ./src/test/test_bitcoin -t net_peer_eviction_tests`
  - `$ FUZZ=node_eviction ./src/test/fuzz/fuzz ../qa-assets/fuzz_seed_corpus/node_eviction`

ACKs for top commit:
  klementtan:
    Tested and code review ACK b1d905c2.
  vasild:
    ACK b1d905c225e87a4a289c0cd3593c6c21cea3fba7
  jarolrod:
    ACK b1d905c225e87a4a289c0cd3593c6c21cea3fba7

Tree-SHA512: a3a6607b9ea2fec138da9780c03f63e177b6712091c5a3ddc3804b896a7585216446310280791f5e20cc023d02d2f03a4139237e12b5c1d7f2a1fa1011610e96

6 files changed, 194 insertions, 27 deletions

diff --git a/src/Makefile.bench.include b/src/Makefile.bench.include
index 56b8ca8ce6..2a8e4a0aac 100644
--- a/src/Makefile.bench.include
+++ b/src/Makefile.bench.include
@@ -35,6 +35,7 @@ bench_bench_bitcoin_SOURCES = \
   bench/mempool_stress.cpp \
   bench/nanobench.h \
   bench/nanobench.cpp \
+  bench/peer_eviction.cpp \
   bench/rpc_blockchain.cpp \
   bench/rpc_mempool.cpp \
   bench/util_time.cpp \
diff --git a/src/bench/peer_eviction.cpp b/src/bench/peer_eviction.cpp
new file mode 100644
index 0000000000..0469f0cb4c
--- /dev/null
+++ b/src/bench/peer_eviction.cpp
@@ -0,0 +1,156 @@
+// Copyright (c) 2021 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <bench/bench.h>
+#include <net.h>
+#include <netaddress.h>
+#include <random.h>
+#include <test/util/net.h>
+#include <test/util/setup_common.h>
+
+#include <algorithm>
+#include <functional>
+#include <vector>
+
+static void EvictionProtectionCommon(
+    benchmark::Bench& bench,
+    int num_candidates,
+    std::function<void(NodeEvictionCandidate&)> candidate_setup_fn)
+{
+    using Candidates = std::vector<NodeEvictionCandidate>;
+    FastRandomContext random_context{true};
+    bench.warmup(100).epochIterations(1100);
+
+    Candidates candidates{GetRandomNodeEvictionCandidates(num_candidates, random_context)};
+    for (auto& c : candidates) {
+        candidate_setup_fn(c);
+    }
+
+    std::vector<Candidates> copies{bench.epochs() * bench.epochIterations(), candidates};
+    size_t i{0};
+    bench.run([&] {
+        ProtectEvictionCandidatesByRatio(copies.at(i));
+        ++i;
+    });
+}
+
+/* Benchmarks */
+
+static void EvictionProtection0Networks250Candidates(benchmark::Bench& bench)
+{
+    EvictionProtectionCommon(
+        bench,
+        250 /* num_candidates */,
+        [](NodeEvictionCandidate& c) {
+            c.nTimeConnected = c.id;
+            c.m_network = NET_IPV4;
+        });
+}
+
+static void EvictionProtection1Networks250Candidates(benchmark::Bench& bench)
+{
+    EvictionProtectionCommon(
+        bench,
+        250 /* num_candidates */,
+        [](NodeEvictionCandidate& c) {
+            c.nTimeConnected = c.id;
+            c.m_is_local = false;
+            if (c.id >= 130 && c.id < 240) { // 110 Tor
+                c.m_network = NET_ONION;
+            } else {
+                c.m_network = NET_IPV4;
+            }
+        });
+}
+
+static void EvictionProtection2Networks250Candidates(benchmark::Bench& bench)
+{
+    EvictionProtectionCommon(
+        bench,
+        250 /* num_candidates */,
+        [](NodeEvictionCandidate& c) {
+            c.nTimeConnected = c.id;
+            c.m_is_local = false;
+            if (c.id >= 90 && c.id < 160) { // 70 Tor
+                c.m_network = NET_ONION;
+            } else if (c.id >= 170 && c.id < 250) { // 80 I2P
+                c.m_network = NET_I2P;
+            } else {
+                c.m_network = NET_IPV4;
+            }
+        });
+}
+
+static void EvictionProtection3Networks050Candidates(benchmark::Bench& bench)
+{
+    EvictionProtectionCommon(
+        bench,
+        50 /* num_candidates */,
+        [](NodeEvictionCandidate& c) {
+            c.nTimeConnected = c.id;
+            c.m_is_local = (c.id == 28 || c.id == 47); //  2 localhost
+            if (c.id >= 30 && c.id < 47) {             // 17 I2P
+                c.m_network = NET_I2P;
+            } else if (c.id >= 24 && c.id < 28) { //  4 Tor
+                c.m_network = NET_ONION;
+            } else {
+                c.m_network = NET_IPV4;
+            }
+        });
+}
+
+static void EvictionProtection3Networks100Candidates(benchmark::Bench& bench)
+{
+    EvictionProtectionCommon(
+        bench,
+        100 /* num_candidates */,
+        [](NodeEvictionCandidate& c) {
+            c.nTimeConnected = c.id;
+            c.m_is_local = (c.id >= 55 && c.id < 60); //  5 localhost
+            if (c.id >= 70 && c.id < 80) {            // 10 I2P
+                c.m_network = NET_I2P;
+            } else if (c.id >= 80 && c.id < 96) { // 16 Tor
+                c.m_network = NET_ONION;
+            } else {
+                c.m_network = NET_IPV4;
+            }
+        });
+}
+
+static void EvictionProtection3Networks250Candidates(benchmark::Bench& bench)
+{
+    EvictionProtectionCommon(
+        bench,
+        250 /* num_candidates */,
+        [](NodeEvictionCandidate& c) {
+            c.nTimeConnected = c.id;
+            c.m_is_local = (c.id >= 140 && c.id < 160); // 20 localhost
+            if (c.id >= 170 && c.id < 180) {            // 10 I2P
+                c.m_network = NET_I2P;
+            } else if (c.id >= 190 && c.id < 240) { // 50 Tor
+                c.m_network = NET_ONION;
+            } else {
+                c.m_network = NET_IPV4;
+            }
+        });
+}
+
+// Candidate numbers used for the benchmarks:
+// -  50 candidates simulates a possible use of -maxconnections
+// - 100 candidates approximates an average node with default settings
+// - 250 candidates is the number of peers reported by operators of busy nodes
+
+// No disadvantaged networks, with 250 eviction candidates.
+BENCHMARK(EvictionProtection0Networks250Candidates);
+
+// 1 disadvantaged network (Tor) with 250 eviction candidates.
+BENCHMARK(EvictionProtection1Networks250Candidates);
+
+// 2 disadvantaged networks (I2P, Tor) with 250 eviction candidates.
+BENCHMARK(EvictionProtection2Networks250Candidates);
+
+// 3 disadvantaged networks (I2P/localhost/Tor) with 50/100/250 eviction candidates.
+BENCHMARK(EvictionProtection3Networks050Candidates);
+BENCHMARK(EvictionProtection3Networks100Candidates);
+BENCHMARK(EvictionProtection3Networks250Candidates);
diff --git a/src/net.cpp b/src/net.cpp
index 0078d71142..70ba875c4b 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -937,14 +937,17 @@ void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& evicti
     size_t num_protected{0};
 
     while (num_protected < max_protect_by_network) {
+        // Count the number of disadvantaged networks from which we have peers to protect.
+        auto num_networks = std::count_if(networks.begin(), networks.end(), [](const Net& n) { return n.count; });
+        if (num_networks == 0) {
+            break;
+        }
         const size_t disadvantaged_to_protect{max_protect_by_network - num_protected};
-        const size_t protect_per_network{
-            std::max(disadvantaged_to_protect / networks.size(), static_cast<size_t>(1))};
-
+        const size_t protect_per_network{std::max(disadvantaged_to_protect / num_networks, static_cast<size_t>(1))};
         // Early exit flag if there are no remaining candidates by disadvantaged network.
         bool protected_at_least_one{false};
 
-        for (const Net& n : networks) {
+        for (Net& n : networks) {
             if (n.count == 0) continue;
             const size_t before = eviction_candidates.size();
             EraseLastKElements(eviction_candidates, CompareNodeNetworkTime(n.is_local, n.id),
@@ -954,10 +957,12 @@ void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& evicti
             const size_t after = eviction_candidates.size();
             if (before > after) {
                 protected_at_least_one = true;
-                num_protected += before - after;
+                const size_t delta{before - after};
+                num_protected += delta;
                 if (num_protected >= max_protect_by_network) {
                     break;
                 }
+                n.count -= delta;
             }
         }
         if (!protected_at_least_one) {
diff --git a/src/test/net_peer_eviction_tests.cpp b/src/test/net_peer_eviction_tests.cpp
index 4bfd487b86..5eb280b498 100644
--- a/src/test/net_peer_eviction_tests.cpp
+++ b/src/test/net_peer_eviction_tests.cpp
@@ -17,28 +17,6 @@
 
 BOOST_FIXTURE_TEST_SUITE(net_peer_eviction_tests, BasicTestingSetup)
 
-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)),
-            /* m_min_ping_time */ std::chrono::microseconds{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(),
-            /* m_network */ ALL_NETWORKS[random_context.randrange(ALL_NETWORKS.size())],
-        });
-    }
-    return candidates;
-}
-
 // Create `num_peers` random nodes, apply setup function `candidate_setup_fn`,
 // call ProtectEvictionCandidatesByRatio() to apply protection logic, and then
 // return true if all of `protected_peer_ids` and none of `unprotected_peer_ids`
diff --git a/src/test/util/net.cpp b/src/test/util/net.cpp
index 847a490e03..28d7967078 100644
--- a/src/test/util/net.cpp
+++ b/src/test/util/net.cpp
@@ -6,6 +6,9 @@
 
 #include <chainparams.h>
 #include <net.h>
+#include <span.h>
+
+#include <vector>
 
 void ConnmanTestMsg::NodeReceiveMsgBytes(CNode& node, Span<const uint8_t> msg_bytes, bool& complete) const
 {
@@ -37,3 +40,25 @@ bool ConnmanTestMsg::ReceiveMsgFrom(CNode& node, CSerializedNetMsg& ser_msg) con
     NodeReceiveMsgBytes(node, ser_msg.data, complete);
     return complete;
 }
+
+std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(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)),
+            /* m_min_ping_time */ std::chrono::microseconds{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(),
+            /* m_network */ ALL_NETWORKS[random_context.randrange(ALL_NETWORKS.size())],
+        });
+    }
+    return candidates;
+}
diff --git a/src/test/util/net.h b/src/test/util/net.h
index 1b49a671bd..939ec322ed 100644
--- a/src/test/util/net.h
+++ b/src/test/util/net.h
@@ -141,4 +141,6 @@ private:
     mutable size_t m_consumed;
 };
 
+std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(int n_candidates, FastRandomContext& random_context);
+
 #endif // BITCOIN_TEST_UTIL_NET_H