Branch data Line data Source code
1 : : // Copyright (c) 2022-present 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 <node/eviction.h>
6 : :
7 : : #include <algorithm>
8 : : #include <array>
9 : : #include <chrono>
10 : : #include <cstdint>
11 : : #include <functional>
12 : : #include <map>
13 : : #include <vector>
14 : :
15 : :
16 : 16245613 : static bool ReverseCompareNodeMinPingTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
17 : : {
18 : 16245613 : return a.m_min_ping_time > b.m_min_ping_time;
19 : : }
20 : :
21 : 12452173 : static bool ReverseCompareNodeTimeConnected(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
22 : : {
23 : 12452173 : return a.m_connected > b.m_connected;
24 : : }
25 : :
26 : 20107751 : static bool CompareNetGroupKeyed(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) {
27 : 20107751 : return a.nKeyedNetGroup < b.nKeyedNetGroup;
28 : : }
29 : :
30 : 15931292 : static bool CompareNodeBlockTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
31 : : {
32 : : // There is a fall-through here because it is common for a node to have many peers which have not yet relayed a block.
33 [ + + ]: 15931292 : if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time;
34 [ + + ]: 12723044 : if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices;
35 : 12714727 : return a.m_connected > b.m_connected;
36 : : }
37 : :
38 : 15302188 : static bool CompareNodeTXTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
39 : : {
40 : : // There is a fall-through here because it is common for a node to have more than a few peers that have not yet relayed txn.
41 [ + + ]: 15302188 : if (a.m_last_tx_time != b.m_last_tx_time) return a.m_last_tx_time < b.m_last_tx_time;
42 [ + + ]: 13208370 : if (a.m_relay_txs != b.m_relay_txs) return b.m_relay_txs;
43 [ + + ]: 13203980 : if (a.fBloomFilter != b.fBloomFilter) return a.fBloomFilter;
44 : 13191438 : return a.m_connected > b.m_connected;
45 : : }
46 : :
47 : : // Pick out the potential block-relay only peers, and sort them by last block time.
48 : 14745778 : static bool CompareNodeBlockRelayOnlyTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
49 : : {
50 [ + + ]: 14745778 : if (a.m_relay_txs != b.m_relay_txs) return a.m_relay_txs;
51 [ + + ]: 14731267 : if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time;
52 [ + + ]: 12737578 : if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices;
53 : 12731130 : return a.m_connected > b.m_connected;
54 : : }
55 : :
56 : : /**
57 : : * Sort eviction candidates by network/localhost and connection uptime.
58 : : * Candidates near the beginning are more likely to be evicted, and those
59 : : * near the end are more likely to be protected, e.g. less likely to be evicted.
60 : : * - First, nodes that are not `is_local` and that do not belong to `network`,
61 : : * sorted by increasing uptime (from most recently connected to connected longer).
62 : : * - Then, nodes that are `is_local` or belong to `network`, sorted by increasing uptime.
63 : : */
64 : : struct CompareNodeNetworkTime {
65 : : const bool m_is_local;
66 : : const Network m_network;
67 [ + - ]: 67851 : CompareNodeNetworkTime(bool is_local, Network network) : m_is_local(is_local), m_network(network) {}
68 : 82319257 : bool operator()(const NodeEvictionCandidate& a, const NodeEvictionCandidate& b) const
69 : : {
70 [ + + + + ]: 82319257 : if (m_is_local && a.m_is_local != b.m_is_local) return b.m_is_local;
71 [ + + ]: 81634552 : if ((a.m_network == m_network) != (b.m_network == m_network)) return b.m_network == m_network;
72 : 78832106 : return a.m_connected > b.m_connected;
73 : : };
74 : : };
75 : :
76 : : //! Sort an array by the specified comparator, then erase the last K elements where predicate is true.
77 : : template <typename T, typename Comparator>
78 : 204597 : static void EraseLastKElements(
79 : : std::vector<T>& elements, Comparator comparator, size_t k,
80 : : std::function<bool(const NodeEvictionCandidate&)> predicate = [](const NodeEvictionCandidate& n) { return true; })
81 : : {
82 [ - + ]: 204597 : std::sort(elements.begin(), elements.end(), comparator);
83 [ + + ]: 395899 : size_t eraseSize = std::min(k, elements.size());
84 [ + - ]: 204597 : elements.erase(std::remove_if(elements.end() - eraseSize, elements.end(), predicate), elements.end());
85 : 204597 : }
86 : :
87 : 22791 : void ProtectNoBanConnections(std::vector<NodeEvictionCandidate>& eviction_candidates)
88 : : {
89 [ + + + + ]: 3578910 : std::erase_if(eviction_candidates, [](const NodeEvictionCandidate& n) { return n.m_noban; });
90 : 22791 : }
91 : :
92 : 22791 : void ProtectOutboundConnections(std::vector<NodeEvictionCandidate>& eviction_candidates)
93 : : {
94 [ + + + + ]: 3369409 : std::erase_if(eviction_candidates, [](const NodeEvictionCandidate& n) { return n.m_conn_type != ConnectionType::INBOUND; });
95 : 22791 : }
96 : :
97 : 22791 : void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& eviction_candidates)
98 : : {
99 : : // Protect the half of the remaining nodes which have been connected the longest.
100 : : // This replicates the non-eviction implicit behavior, and precludes attacks that start later.
101 : : // To favorise the diversity of our peer connections, reserve up to half of these protected
102 : : // spots for Tor/onion, localhost, I2P, and CJDNS peers, even if they're not longest uptime
103 : : // overall. This helps protect these higher-latency peers that tend to be otherwise
104 : : // disadvantaged under our eviction criteria.
105 [ - + ]: 22791 : const size_t initial_size = eviction_candidates.size();
106 : 22791 : const size_t total_protect_size{initial_size / 2};
107 : :
108 : : // Disadvantaged networks to protect. In the case of equal counts, earlier array members
109 : : // have the first opportunity to recover unused slots from the previous iteration.
110 : 22791 : struct Net { bool is_local; Network id; size_t count; };
111 : 22791 : std::array<Net, 4> networks{
112 : : {{false, NET_CJDNS, 0}, {false, NET_I2P, 0}, {/*localhost=*/true, NET_MAX, 0}, {false, NET_ONION, 0}}};
113 : :
114 : : // Count and store the number of eviction candidates per network.
115 [ + + ]: 113955 : for (Net& n : networks) {
116 : 91164 : n.count = std::count_if(eviction_candidates.cbegin(), eviction_candidates.cend(),
117 : 9619092 : [&n](const NodeEvictionCandidate& c) {
118 [ + + ]: 9619092 : return n.is_local ? c.m_is_local : c.m_network == n.id;
119 : : });
120 : : }
121 : : // Sort `networks` by ascending candidate count, to give networks having fewer candidates
122 : : // the first opportunity to recover unused protected slots from the previous iteration.
123 : 159483 : std::stable_sort(networks.begin(), networks.end(), [](Net a, Net b) { return a.count < b.count; });
[ - - - -
- - - + -
- + + - -
+ + ]
124 : :
125 : : // Protect up to 25% of the eviction candidates by disadvantaged network.
126 : 22791 : const size_t max_protect_by_network{total_protect_size / 2};
127 : 22791 : size_t num_protected{0};
128 : :
129 [ + + ]: 53113 : while (num_protected < max_protect_by_network) {
130 : : // Count the number of disadvantaged networks from which we have peers to protect.
131 [ + + ]: 160456 : auto num_networks = std::count_if(networks.begin(), networks.end(), [](const Net& n) { return n.count; });
132 [ + + ]: 40114 : if (num_networks == 0) {
133 : : break;
134 : : }
135 : 34254 : const size_t disadvantaged_to_protect{max_protect_by_network - num_protected};
136 [ + + ]: 34254 : const size_t protect_per_network{std::max(disadvantaged_to_protect / num_networks, static_cast<size_t>(1))};
137 : : // Early exit flag if there are no remaining candidates by disadvantaged network.
138 : 34254 : bool protected_at_least_one{false};
139 : :
140 [ + + ]: 159287 : for (Net& n : networks) {
141 [ + + ]: 134945 : if (n.count == 0) continue;
142 [ - + ]: 67851 : const size_t before = eviction_candidates.size();
143 : 67851 : EraseLastKElements(eviction_candidates, CompareNodeNetworkTime(n.is_local, n.id),
144 [ + - ]: 67851 : protect_per_network, [&n](const NodeEvictionCandidate& c) {
145 [ + + ]: 786236 : return n.is_local ? c.m_is_local : c.m_network == n.id;
146 : : });
147 [ - + ]: 67851 : const size_t after = eviction_candidates.size();
148 [ + + ]: 67851 : if (before > after) {
149 : 60497 : protected_at_least_one = true;
150 : 60497 : const size_t delta{before - after};
151 : 60497 : num_protected += delta;
152 [ + + ]: 60497 : if (num_protected >= max_protect_by_network) {
153 : : break;
154 : : }
155 : 50585 : n.count -= delta;
156 : : }
157 : : }
158 [ + + ]: 34254 : if (!protected_at_least_one) {
159 : : break;
160 : : }
161 : : }
162 : :
163 : : // Calculate how many we removed, and update our total number of peers that
164 : : // we want to protect based on uptime accordingly.
165 [ - + - + ]: 22791 : assert(num_protected == initial_size - eviction_candidates.size());
166 : 22791 : const size_t remaining_to_protect{total_protect_size - num_protected};
167 [ + - ]: 22791 : EraseLastKElements(eviction_candidates, ReverseCompareNodeTimeConnected, remaining_to_protect);
168 : 22791 : }
169 : :
170 : 22791 : [[nodiscard]] std::optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates)
171 : : {
172 : : // Protect connections with certain characteristics
173 : :
174 : 22791 : ProtectNoBanConnections(vEvictionCandidates);
175 : :
176 : 22791 : ProtectOutboundConnections(vEvictionCandidates);
177 : :
178 : : // Deterministically select 4 peers to protect by netgroup.
179 : : // An attacker cannot predict which netgroups will be protected
180 [ + - ]: 22791 : EraseLastKElements(vEvictionCandidates, CompareNetGroupKeyed, 4);
181 : : // Protect the 8 nodes with the lowest minimum ping time.
182 : : // An attacker cannot manipulate this metric without physically moving nodes closer to the target.
183 [ + - ]: 22791 : EraseLastKElements(vEvictionCandidates, ReverseCompareNodeMinPingTime, 8);
184 : : // Protect 4 nodes that most recently sent us novel transactions accepted into our mempool.
185 : : // An attacker cannot manipulate this metric without performing useful work.
186 [ + - ]: 22791 : EraseLastKElements(vEvictionCandidates, CompareNodeTXTime, 4);
187 : : // Protect up to 8 non-tx-relay peers that have sent us novel blocks.
188 [ + - ]: 22791 : EraseLastKElements(vEvictionCandidates, CompareNodeBlockRelayOnlyTime, 8,
189 [ + + + + : 182101 : [](const NodeEvictionCandidate& n) { return !n.m_relay_txs && n.fRelevantServices; });
+ - ]
190 : :
191 : : // Protect 4 nodes that most recently sent us novel blocks.
192 : : // An attacker cannot manipulate this metric without performing useful work.
193 [ + - ]: 22791 : EraseLastKElements(vEvictionCandidates, CompareNodeBlockTime, 4);
194 : :
195 : : // Protect some of the remaining eviction candidates by ratios of desirable
196 : : // or disadvantaged characteristics.
197 : 22791 : ProtectEvictionCandidatesByRatio(vEvictionCandidates);
198 : :
199 [ + + ]: 22791 : if (vEvictionCandidates.empty()) return std::nullopt;
200 : :
201 : : // If any remaining peers are preferred for eviction consider only them.
202 : : // This happens after the other preferences since if a peer is really the best by other criteria (esp relaying blocks)
203 : : // then we probably don't want to evict it no matter what.
204 [ + + + + ]: 1177627 : if (std::any_of(vEvictionCandidates.begin(),vEvictionCandidates.end(),[](NodeEvictionCandidate const &n){return n.prefer_evict;})) {
205 [ + + + + ]: 107937 : std::erase_if(vEvictionCandidates, [](const NodeEvictionCandidate& n) { return !n.prefer_evict; });
206 : : }
207 : :
208 : : // Identify the network group with the most connections and youngest member.
209 : : // (vEvictionCandidates is already sorted by reverse connect time)
210 : 19924 : uint64_t naMostConnections;
211 : 19924 : unsigned int nMostConnections = 0;
212 : 19924 : NodeClock::time_point nMostConnectionsTime{NodeClock::epoch};
213 : 19924 : std::map<uint64_t, std::vector<NodeEvictionCandidate> > mapNetGroupNodes;
214 [ + + ]: 1125328 : for (const NodeEvictionCandidate &node : vEvictionCandidates) {
215 [ + - ]: 1105404 : std::vector<NodeEvictionCandidate> &group = mapNetGroupNodes[node.nKeyedNetGroup];
216 [ + - ]: 1105404 : group.push_back(node);
217 [ - + ]: 1105404 : const auto grouptime{group[0].m_connected};
218 : :
219 [ - + + + : 1105404 : if (group.size() > nMostConnections || (group.size() == nMostConnections && grouptime > nMostConnectionsTime)) {
+ + + + ]
220 : 595146 : nMostConnections = group.size();
221 : 595146 : nMostConnectionsTime = grouptime;
222 : 595146 : naMostConnections = node.nKeyedNetGroup;
223 : : }
224 : : }
225 : :
226 : : // Reduce to the network group with the most connections
227 [ + - ]: 19924 : vEvictionCandidates = std::move(mapNetGroupNodes[naMostConnections]);
228 : :
229 : : // Disconnect from the network group with the most connections
230 : 19924 : return vEvictionCandidates.front().id;
231 : 19924 : }
|
