LCOV - code coverage report
Current view: top level - src/node - eviction.cpp (source / functions) Coverage Total Hit
Test: total_coverage.info Lines: 99.1 % 107 106
Test Date: 2024-11-04 05:10:19 Functions: 100.0 % 13 13
Branches: 75.0 % 176 132

             Branch data     Line data    Source code
       1                 :             : // Copyright (c) 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 <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                 :     1184903 : static bool ReverseCompareNodeMinPingTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
      17                 :             : {
      18                 :     1184903 :     return a.m_min_ping_time > b.m_min_ping_time;
      19                 :             : }
      20                 :             : 
      21                 :      719696 : static bool ReverseCompareNodeTimeConnected(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
      22                 :             : {
      23                 :      719696 :     return a.m_connected > b.m_connected;
      24                 :             : }
      25                 :             : 
      26                 :     1268990 : static bool CompareNetGroupKeyed(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b) {
      27                 :     1268990 :     return a.nKeyedNetGroup < b.nKeyedNetGroup;
      28                 :             : }
      29                 :             : 
      30                 :     1243762 : 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         [ +  + ]:     1243762 :     if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time;
      34         [ +  + ]:       43378 :     if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices;
      35                 :       23335 :     return a.m_connected > b.m_connected;
      36                 :             : }
      37                 :             : 
      38                 :     1113547 : 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         [ +  + ]:     1113547 :     if (a.m_last_tx_time != b.m_last_tx_time) return a.m_last_tx_time < b.m_last_tx_time;
      42         [ +  + ]:       70824 :     if (a.m_relay_txs != b.m_relay_txs) return b.m_relay_txs;
      43         [ +  + ]:       38094 :     if (a.fBloomFilter != b.fBloomFilter) return a.fBloomFilter;
      44                 :       19740 :     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                 :     1085927 : static bool CompareNodeBlockRelayOnlyTime(const NodeEvictionCandidate &a, const NodeEvictionCandidate &b)
      49                 :             : {
      50         [ +  + ]:     1085927 :     if (a.m_relay_txs != b.m_relay_txs) return a.m_relay_txs;
      51         [ +  + ]:      927392 :     if (a.m_last_block_time != b.m_last_block_time) return a.m_last_block_time < b.m_last_block_time;
      52         [ +  + ]:       23476 :     if (a.fRelevantServices != b.fRelevantServices) return b.fRelevantServices;
      53                 :       12045 :     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         [ +  - ]:        7223 :     CompareNodeNetworkTime(bool is_local, Network network) : m_is_local(is_local), m_network(network) {}
      68                 :     4341220 :     bool operator()(const NodeEvictionCandidate& a, const NodeEvictionCandidate& b) const
      69                 :             :     {
      70   [ +  +  +  + ]:     4341220 :         if (m_is_local && a.m_is_local != b.m_is_local) return b.m_is_local;
      71         [ +  + ]:     4236064 :         if ((a.m_network == m_network) != (b.m_network == m_network)) return b.m_network == m_network;
      72                 :     3915705 :         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                 :       16813 : 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         [ +  + ]:       16813 :     std::sort(elements.begin(), elements.end(), comparator);
      83         [ +  + ]:       33005 :     size_t eraseSize = std::min(k, elements.size());
      84         [ +  - ]:       16813 :     elements.erase(std::remove_if(elements.end() - eraseSize, elements.end(), predicate), elements.end());
      85                 :       16813 : }
      86                 :             : 
      87                 :        1593 : void ProtectNoBanConnections(std::vector<NodeEvictionCandidate>& eviction_candidates)
      88                 :             : {
      89                 :        1593 :     eviction_candidates.erase(std::remove_if(eviction_candidates.begin(), eviction_candidates.end(),
      90                 :      159025 :                                              [](NodeEvictionCandidate const& n) {
      91   [ -  +  -  +  :       41548 :                                                  return n.m_noban;
          -  +  -  +  -  
          +  -  +  -  +  
                   -  - ]
      92                 :             :                                              }),
      93                 :        1593 :                               eviction_candidates.end());
      94                 :        1593 : }
      95                 :             : 
      96                 :        1593 : void ProtectOutboundConnections(std::vector<NodeEvictionCandidate>& eviction_candidates)
      97                 :             : {
      98                 :        1593 :     eviction_candidates.erase(std::remove_if(eviction_candidates.begin(), eviction_candidates.end(),
      99                 :      159025 :                                              [](NodeEvictionCandidate const& n) {
     100   [ -  +  -  +  :       41548 :                                                  return n.m_conn_type != ConnectionType::INBOUND;
          -  +  -  +  -  
          +  -  +  -  +  
                   -  - ]
     101                 :             :                                              }),
     102                 :        1593 :                               eviction_candidates.end());
     103                 :        1593 : }
     104                 :             : 
     105                 :        1625 : void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& eviction_candidates)
     106                 :             : {
     107                 :             :     // Protect the half of the remaining nodes which have been connected the longest.
     108                 :             :     // This replicates the non-eviction implicit behavior, and precludes attacks that start later.
     109                 :             :     // To favorise the diversity of our peer connections, reserve up to half of these protected
     110                 :             :     // spots for Tor/onion, localhost, I2P, and CJDNS peers, even if they're not longest uptime
     111                 :             :     // overall. This helps protect these higher-latency peers that tend to be otherwise
     112                 :             :     // disadvantaged under our eviction criteria.
     113                 :        1625 :     const size_t initial_size = eviction_candidates.size();
     114                 :        1625 :     const size_t total_protect_size{initial_size / 2};
     115                 :             : 
     116                 :             :     // Disadvantaged networks to protect. In the case of equal counts, earlier array members
     117                 :             :     // have the first opportunity to recover unused slots from the previous iteration.
     118                 :        1625 :     struct Net { bool is_local; Network id; size_t count; };
     119                 :        1625 :     std::array<Net, 4> networks{
     120                 :             :         {{false, NET_CJDNS, 0}, {false, NET_I2P, 0}, {/*localhost=*/true, NET_MAX, 0}, {false, NET_ONION, 0}}};
     121                 :             : 
     122                 :             :     // Count and store the number of eviction candidates per network.
     123         [ +  + ]:        8125 :     for (Net& n : networks) {
     124                 :        6500 :         n.count = std::count_if(eviction_candidates.cbegin(), eviction_candidates.cend(),
     125                 :      490084 :                                 [&n](const NodeEvictionCandidate& c) {
     126         [ +  + ]:      490084 :                                     return n.is_local ? c.m_is_local : c.m_network == n.id;
     127                 :             :                                 });
     128                 :             :     }
     129                 :             :     // Sort `networks` by ascending candidate count, to give networks having fewer candidates
     130                 :             :     // the first opportunity to recover unused protected slots from the previous iteration.
     131   [ -  -  -  -  :       10213 :     std::stable_sort(networks.begin(), networks.end(), [](Net a, Net b) { return a.count < b.count; });
          -  -  -  +  -  
          -  +  +  -  -  
                   +  + ]
     132                 :             : 
     133                 :             :     // Protect up to 25% of the eviction candidates by disadvantaged network.
     134                 :        1625 :     const size_t max_protect_by_network{total_protect_size / 2};
     135                 :        1625 :     size_t num_protected{0};
     136                 :             : 
     137         [ +  + ]:        3994 :     while (num_protected < max_protect_by_network) {
     138                 :             :         // Count the number of disadvantaged networks from which we have peers to protect.
     139         [ +  + ]:        9484 :         auto num_networks = std::count_if(networks.begin(), networks.end(), [](const Net& n) { return n.count; });
     140         [ +  + ]:        2371 :         if (num_networks == 0) {
     141                 :             :             break;
     142                 :             :         }
     143                 :        2369 :         const size_t disadvantaged_to_protect{max_protect_by_network - num_protected};
     144         [ +  + ]:        2369 :         const size_t protect_per_network{std::max(disadvantaged_to_protect / num_networks, static_cast<size_t>(1))};
     145                 :             :         // Early exit flag if there are no remaining candidates by disadvantaged network.
     146                 :        2369 :         bool protected_at_least_one{false};
     147                 :             : 
     148         [ +  + ]:        8451 :         for (Net& n : networks) {
     149         [ +  + ]:        7488 :             if (n.count == 0) continue;
     150         [ +  - ]:        7223 :             const size_t before = eviction_candidates.size();
     151                 :           0 :             EraseLastKElements(eviction_candidates, CompareNodeNetworkTime(n.is_local, n.id),
     152         [ +  - ]:        7223 :                                protect_per_network, [&n](const NodeEvictionCandidate& c) {
     153         [ +  + ]:       30114 :                                    return n.is_local ? c.m_is_local : c.m_network == n.id;
     154                 :             :                                });
     155         [ +  + ]:        7223 :             const size_t after = eviction_candidates.size();
     156         [ +  + ]:        7223 :             if (before > after) {
     157                 :        7222 :                 protected_at_least_one = true;
     158                 :        7222 :                 const size_t delta{before - after};
     159                 :        7222 :                 num_protected += delta;
     160         [ +  + ]:        7222 :                 if (num_protected >= max_protect_by_network) {
     161                 :             :                     break;
     162                 :             :                 }
     163                 :        5816 :                 n.count -= delta;
     164                 :             :             }
     165                 :             :         }
     166         [ +  - ]:        2369 :         if (!protected_at_least_one) {
     167                 :             :             break;
     168                 :             :         }
     169                 :             :     }
     170                 :             : 
     171                 :             :     // Calculate how many we removed, and update our total number of peers that
     172                 :             :     // we want to protect based on uptime accordingly.
     173         [ -  + ]:        1625 :     assert(num_protected == initial_size - eviction_candidates.size());
     174                 :        1625 :     const size_t remaining_to_protect{total_protect_size - num_protected};
     175         [ +  - ]:        1625 :     EraseLastKElements(eviction_candidates, ReverseCompareNodeTimeConnected, remaining_to_protect);
     176                 :        1625 : }
     177                 :             : 
     178                 :        1593 : [[nodiscard]] std::optional<NodeId> SelectNodeToEvict(std::vector<NodeEvictionCandidate>&& vEvictionCandidates)
     179                 :             : {
     180                 :             :     // Protect connections with certain characteristics
     181                 :             : 
     182                 :        1593 :     ProtectNoBanConnections(vEvictionCandidates);
     183                 :             : 
     184                 :        1593 :     ProtectOutboundConnections(vEvictionCandidates);
     185                 :             : 
     186                 :             :     // Deterministically select 4 peers to protect by netgroup.
     187                 :             :     // An attacker cannot predict which netgroups will be protected
     188         [ +  - ]:        1593 :     EraseLastKElements(vEvictionCandidates, CompareNetGroupKeyed, 4);
     189                 :             :     // Protect the 8 nodes with the lowest minimum ping time.
     190                 :             :     // An attacker cannot manipulate this metric without physically moving nodes closer to the target.
     191         [ +  - ]:        1593 :     EraseLastKElements(vEvictionCandidates, ReverseCompareNodeMinPingTime, 8);
     192                 :             :     // Protect 4 nodes that most recently sent us novel transactions accepted into our mempool.
     193                 :             :     // An attacker cannot manipulate this metric without performing useful work.
     194         [ +  - ]:        1593 :     EraseLastKElements(vEvictionCandidates, CompareNodeTXTime, 4);
     195                 :             :     // Protect up to 8 non-tx-relay peers that have sent us novel blocks.
     196         [ +  - ]:        1593 :     EraseLastKElements(vEvictionCandidates, CompareNodeBlockRelayOnlyTime, 8,
     197   [ +  +  +  + ]:       11435 :                        [](const NodeEvictionCandidate& n) { return !n.m_relay_txs && n.fRelevantServices; });
     198                 :             : 
     199                 :             :     // Protect 4 nodes that most recently sent us novel blocks.
     200                 :             :     // An attacker cannot manipulate this metric without performing useful work.
     201         [ +  - ]:        1593 :     EraseLastKElements(vEvictionCandidates, CompareNodeBlockTime, 4);
     202                 :             : 
     203                 :             :     // Protect some of the remaining eviction candidates by ratios of desirable
     204                 :             :     // or disadvantaged characteristics.
     205                 :        1593 :     ProtectEvictionCandidatesByRatio(vEvictionCandidates);
     206                 :             : 
     207         [ +  + ]:        1593 :     if (vEvictionCandidates.empty()) return std::nullopt;
     208                 :             : 
     209                 :             :     // If any remaining peers are preferred for eviction consider only them.
     210                 :             :     // This happens after the other preferences since if a peer is really the best by other criteria (esp relaying blocks)
     211                 :             :     //  then we probably don't want to evict it no matter what.
     212   [ +  +  +  +  :        2897 :     if (std::any_of(vEvictionCandidates.begin(),vEvictionCandidates.end(),[](NodeEvictionCandidate const &n){return n.prefer_evict;})) {
          +  +  +  +  +  
          +  +  +  +  +  
                   +  + ]
     213                 :        1384 :         vEvictionCandidates.erase(std::remove_if(vEvictionCandidates.begin(),vEvictionCandidates.end(),
     214   [ +  +  +  +  :       61541 :                                   [](NodeEvictionCandidate const &n){return !n.prefer_evict;}),vEvictionCandidates.end());
          +  +  +  +  +  
          +  +  +  +  +  
                   +  + ]
     215                 :             :     }
     216                 :             : 
     217                 :             :     // Identify the network group with the most connections and youngest member.
     218                 :             :     // (vEvictionCandidates is already sorted by reverse connect time)
     219                 :        1405 :     uint64_t naMostConnections;
     220                 :        1405 :     unsigned int nMostConnections = 0;
     221                 :        1405 :     std::chrono::seconds nMostConnectionsTime{0};
     222                 :        1405 :     std::map<uint64_t, std::vector<NodeEvictionCandidate> > mapNetGroupNodes;
     223         [ +  + ]:       32087 :     for (const NodeEvictionCandidate &node : vEvictionCandidates) {
     224         [ +  - ]:       30682 :         std::vector<NodeEvictionCandidate> &group = mapNetGroupNodes[node.nKeyedNetGroup];
     225         [ +  - ]:       30682 :         group.push_back(node);
     226         [ +  + ]:       30682 :         const auto grouptime{group[0].m_connected};
     227                 :             : 
     228   [ +  +  +  +  :       30682 :         if (group.size() > nMostConnections || (group.size() == nMostConnections && grouptime > nMostConnectionsTime)) {
                   +  + ]
     229                 :        2701 :             nMostConnections = group.size();
     230                 :        2701 :             nMostConnectionsTime = grouptime;
     231                 :        2701 :             naMostConnections = node.nKeyedNetGroup;
     232                 :             :         }
     233                 :             :     }
     234                 :             : 
     235                 :             :     // Reduce to the network group with the most connections
     236         [ +  - ]:        1405 :     vEvictionCandidates = std::move(mapNetGroupNodes[naMostConnections]);
     237                 :             : 
     238                 :             :     // Disconnect from the network group with the most connections
     239                 :        1405 :     return vEvictionCandidates.front().id;
     240                 :        1405 : }
        

Generated by: LCOV version 2.0-1