1  // Copyright (c) 2021-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  #ifndef BITCOIN_ADDRMAN_IMPL_H
  6  #define BITCOIN_ADDRMAN_IMPL_H
  7  
  8  #include <logging.h>
  9  #include <logging/timer.h>
 10  #include <netaddress.h>
 11  #include <protocol.h>
 12  #include <serialize.h>
 13  #include <sync.h>
 14  #include <timedata.h>
 15  #include <uint256.h>
 16  #include <util/time.h>
 17  
 18  #include <cstdint>
 19  #include <optional>
 20  #include <set>
 21  #include <unordered_map>
 22  #include <unordered_set>
 23  #include <utility>
 24  #include <vector>
 25  
 26  /** Total number of buckets for tried addresses */
 27  static constexpr int32_t ADDRMAN_TRIED_BUCKET_COUNT_LOG2{8};
 28  static constexpr int ADDRMAN_TRIED_BUCKET_COUNT{1 << ADDRMAN_TRIED_BUCKET_COUNT_LOG2};
 29  /** Total number of buckets for new addresses */
 30  static constexpr int32_t ADDRMAN_NEW_BUCKET_COUNT_LOG2{10};
 31  static constexpr int ADDRMAN_NEW_BUCKET_COUNT{1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2};
 32  /** Maximum allowed number of entries in buckets for new and tried addresses */
 33  static constexpr int32_t ADDRMAN_BUCKET_SIZE_LOG2{6};
 34  static constexpr int ADDRMAN_BUCKET_SIZE{1 << ADDRMAN_BUCKET_SIZE_LOG2};
 35  
 36  /**
 37   * Extended statistics about a CAddress
 38   */
 39  class AddrInfo : public CAddress
 40  {
 41  public:
 42      //! last try whatsoever by us (memory only)
 43      NodeSeconds m_last_try{0s};
 44  
 45      //! last counted attempt (memory only)
 46      NodeSeconds m_last_count_attempt{0s};
 47  
 48      //! where knowledge about this address first came from
 49      CNetAddr source;
 50  
 51      //! last successful connection by us
 52      NodeSeconds m_last_success{0s};
 53  
 54      //! connection attempts since last successful attempt
 55      int nAttempts{0};
 56  
 57      //! reference count in new sets (memory only)
 58      int nRefCount{0};
 59  
 60      //! in tried set? (memory only)
 61      bool fInTried{false};
 62  
 63      //! position in vRandom
 64      mutable int nRandomPos{-1};
 65  
 66      SERIALIZE_METHODS(AddrInfo, obj)
 67      {
 68          READWRITE(AsBase<CAddress>(obj), obj.source, Using<ChronoFormatter<int64_t>>(obj.m_last_success), obj.nAttempts);
 69      }
 70  
 71      AddrInfo(const CAddress &addrIn, const CNetAddr &addrSource) : CAddress(addrIn), source(addrSource)
 72      {
 73      }
 74  
 75      AddrInfo() : CAddress(), source()
 76      {
 77      }
 78  
 79      //! Calculate in which "tried" bucket this entry belongs
 80      int GetTriedBucket(const uint256& nKey, const NetGroupManager& netgroupman) const;
 81  
 82      //! Calculate in which "new" bucket this entry belongs, given a certain source
 83      int GetNewBucket(const uint256& nKey, const CNetAddr& src, const NetGroupManager& netgroupman) const;
 84  
 85      //! Calculate in which "new" bucket this entry belongs, using its default source
 86      int GetNewBucket(const uint256& nKey, const NetGroupManager& netgroupman) const
 87      {
 88          return GetNewBucket(nKey, source, netgroupman);
 89      }
 90  
 91      //! Calculate in which position of a bucket to store this entry.
 92      int GetBucketPosition(const uint256 &nKey, bool fNew, int bucket) const;
 93  
 94      //! Determine whether the statistics about this entry are bad enough so that it can just be deleted
 95      bool IsTerrible(NodeSeconds now = Now<NodeSeconds>()) const;
 96  
 97      //! Calculate the relative chance this entry should be given when selecting nodes to connect to
 98      double GetChance(NodeSeconds now = Now<NodeSeconds>()) const;
 99  };
100  
101  class AddrManImpl
102  {
103  public:
104      AddrManImpl(const NetGroupManager& netgroupman, bool deterministic, int32_t consistency_check_ratio);
105  
106      ~AddrManImpl();
107  
108      template <typename Stream>
109      void Serialize(Stream& s_) const EXCLUSIVE_LOCKS_REQUIRED(!cs);
110  
111      template <typename Stream>
112      void Unserialize(Stream& s_) EXCLUSIVE_LOCKS_REQUIRED(!cs);
113  
114      size_t Size(std::optional<Network> net, std::optional<bool> in_new) const EXCLUSIVE_LOCKS_REQUIRED(!cs);
115  
116      bool Add(const std::vector<CAddress>& vAddr, const CNetAddr& source, std::chrono::seconds time_penalty)
117          EXCLUSIVE_LOCKS_REQUIRED(!cs);
118  
119      bool Good(const CService& addr, NodeSeconds time)
120          EXCLUSIVE_LOCKS_REQUIRED(!cs);
121  
122      void Attempt(const CService& addr, bool fCountFailure, NodeSeconds time)
123          EXCLUSIVE_LOCKS_REQUIRED(!cs);
124  
125      void ResolveCollisions() EXCLUSIVE_LOCKS_REQUIRED(!cs);
126  
127      std::pair<CAddress, NodeSeconds> SelectTriedCollision() EXCLUSIVE_LOCKS_REQUIRED(!cs);
128  
129      std::pair<CAddress, NodeSeconds> Select(bool new_only, std::optional<Network> network) const
130          EXCLUSIVE_LOCKS_REQUIRED(!cs);
131  
132      std::vector<CAddress> GetAddr(size_t max_addresses, size_t max_pct, std::optional<Network> network, const bool filtered = true) const
133          EXCLUSIVE_LOCKS_REQUIRED(!cs);
134  
135      std::vector<std::pair<AddrInfo, AddressPosition>> GetEntries(bool from_tried) const
136          EXCLUSIVE_LOCKS_REQUIRED(!cs);
137  
138      void Connected(const CService& addr, NodeSeconds time)
139          EXCLUSIVE_LOCKS_REQUIRED(!cs);
140  
141      void SetServices(const CService& addr, ServiceFlags nServices)
142          EXCLUSIVE_LOCKS_REQUIRED(!cs);
143  
144      std::optional<AddressPosition> FindAddressEntry(const CAddress& addr)
145          EXCLUSIVE_LOCKS_REQUIRED(!cs);
146  
147      friend class AddrManDeterministic;
148  
149  private:
150      //! A mutex to protect the inner data structures.
151      mutable Mutex cs;
152  
153      //! Source of random numbers for randomization in inner loops
154      mutable FastRandomContext insecure_rand GUARDED_BY(cs);
155  
156      //! secret key to randomize bucket select with
157      uint256 nKey;
158  
159      //! Serialization versions.
160      enum Format : uint8_t {
161          V0_HISTORICAL = 0,    //!< historic format, before commit e6b343d88
162          V1_DETERMINISTIC = 1, //!< for pre-asmap files
163          V2_ASMAP = 2,         //!< for files including asmap version
164          V3_BIP155 = 3,        //!< same as V2_ASMAP plus addresses are in BIP155 format
165          V4_MULTIPORT = 4,     //!< adds support for multiple ports per IP
166      };
167  
168      //! The maximum format this software knows it can unserialize. Also, we always serialize
169      //! in this format.
170      //! The format (first byte in the serialized stream) can be higher than this and
171      //! still this software may be able to unserialize the file - if the second byte
172      //! (see `lowest_compatible` in `Unserialize()`) is less or equal to this.
173      static constexpr Format FILE_FORMAT = Format::V4_MULTIPORT;
174  
175      //! The initial value of a field that is incremented every time an incompatible format
176      //! change is made (such that old software versions would not be able to parse and
177      //! understand the new file format). This is 32 because we overtook the "key size"
178      //! field which was 32 historically.
179      //! @note Don't increment this. Increment `lowest_compatible` in `Serialize()` instead.
180      static constexpr uint8_t INCOMPATIBILITY_BASE = 32;
181  
182      //! last used nId
183      int nIdCount GUARDED_BY(cs){0};
184  
185      //! table with information about all nIds
186      std::unordered_map<int, AddrInfo> mapInfo GUARDED_BY(cs);
187  
188      //! find an nId based on its network address and port.
189      std::unordered_map<CService, int, CServiceHash> mapAddr GUARDED_BY(cs);
190  
191      //! randomly-ordered vector of all nIds
192      //! This is mutable because it is unobservable outside the class, so any
193      //! changes to it (even in const methods) are also unobservable.
194      mutable std::vector<int> vRandom GUARDED_BY(cs);
195  
196      // number of "tried" entries
197      int nTried GUARDED_BY(cs){0};
198  
199      //! list of "tried" buckets
200      int vvTried[ADDRMAN_TRIED_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE] GUARDED_BY(cs);
201  
202      //! number of (unique) "new" entries
203      int nNew GUARDED_BY(cs){0};
204  
205      //! list of "new" buckets
206      int vvNew[ADDRMAN_NEW_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE] GUARDED_BY(cs);
207  
208      //! last time Good was called (memory only). Initially set to 1 so that "never" is strictly worse.
209      NodeSeconds m_last_good GUARDED_BY(cs){1s};
210  
211      //! Holds addrs inserted into tried table that collide with existing entries. Test-before-evict discipline used to resolve these collisions.
212      std::set<int> m_tried_collisions;
213  
214      /** Perform consistency checks every m_consistency_check_ratio operations (if non-zero). */
215      const int32_t m_consistency_check_ratio;
216  
217      /** Reference to the netgroup manager. netgroupman must be constructed before addrman and destructed after. */
218      const NetGroupManager& m_netgroupman;
219  
220      struct NewTriedCount {
221          size_t n_new;
222          size_t n_tried;
223      };
224  
225      /** Number of entries in addrman per network and new/tried table. */
226      std::unordered_map<Network, NewTriedCount> m_network_counts GUARDED_BY(cs);
227  
228      //! Find an entry.
229      AddrInfo* Find(const CService& addr, int* pnId = nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs);
230  
231      //! Create a new entry and add it to the internal data structures mapInfo, mapAddr and vRandom.
232      AddrInfo* Create(const CAddress& addr, const CNetAddr& addrSource, int* pnId = nullptr) EXCLUSIVE_LOCKS_REQUIRED(cs);
233  
234      //! Swap two elements in vRandom.
235      void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2) const EXCLUSIVE_LOCKS_REQUIRED(cs);
236  
237      //! Delete an entry. It must not be in tried, and have refcount 0.
238      void Delete(int nId) EXCLUSIVE_LOCKS_REQUIRED(cs);
239  
240      //! Clear a position in a "new" table. This is the only place where entries are actually deleted.
241      void ClearNew(int nUBucket, int nUBucketPos) EXCLUSIVE_LOCKS_REQUIRED(cs);
242  
243      //! Move an entry from the "new" table(s) to the "tried" table
244      void MakeTried(AddrInfo& info, int nId) EXCLUSIVE_LOCKS_REQUIRED(cs);
245  
246      /** Attempt to add a single address to addrman's new table.
247       *  @see AddrMan::Add() for parameters. */
248      bool AddSingle(const CAddress& addr, const CNetAddr& source, std::chrono::seconds time_penalty) EXCLUSIVE_LOCKS_REQUIRED(cs);
249  
250      bool Good_(const CService& addr, bool test_before_evict, NodeSeconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
251  
252      bool Add_(const std::vector<CAddress>& vAddr, const CNetAddr& source, std::chrono::seconds time_penalty) EXCLUSIVE_LOCKS_REQUIRED(cs);
253  
254      void Attempt_(const CService& addr, bool fCountFailure, NodeSeconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
255  
256      std::pair<CAddress, NodeSeconds> Select_(bool new_only, std::optional<Network> network) const EXCLUSIVE_LOCKS_REQUIRED(cs);
257  
258      /** Helper to generalize looking up an addrman entry from either table.
259       *
260       *  @return  int The nid of the entry. If the addrman position is empty or not found, returns -1.
261       * */
262      int GetEntry(bool use_tried, size_t bucket, size_t position) const EXCLUSIVE_LOCKS_REQUIRED(cs);
263  
264      std::vector<CAddress> GetAddr_(size_t max_addresses, size_t max_pct, std::optional<Network> network, const bool filtered = true) const EXCLUSIVE_LOCKS_REQUIRED(cs);
265  
266      std::vector<std::pair<AddrInfo, AddressPosition>> GetEntries_(bool from_tried) const EXCLUSIVE_LOCKS_REQUIRED(cs);
267  
268      void Connected_(const CService& addr, NodeSeconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
269  
270      void SetServices_(const CService& addr, ServiceFlags nServices) EXCLUSIVE_LOCKS_REQUIRED(cs);
271  
272      void ResolveCollisions_() EXCLUSIVE_LOCKS_REQUIRED(cs);
273  
274      std::pair<CAddress, NodeSeconds> SelectTriedCollision_() EXCLUSIVE_LOCKS_REQUIRED(cs);
275  
276      std::optional<AddressPosition> FindAddressEntry_(const CAddress& addr) EXCLUSIVE_LOCKS_REQUIRED(cs);
277  
278      size_t Size_(std::optional<Network> net, std::optional<bool> in_new) const EXCLUSIVE_LOCKS_REQUIRED(cs);
279  
280      //! Consistency check, taking into account m_consistency_check_ratio.
281      //! Will std::abort if an inconsistency is detected.
282      void Check() const EXCLUSIVE_LOCKS_REQUIRED(cs);
283  
284      //! Perform consistency check, regardless of m_consistency_check_ratio.
285      //! @returns an error code or zero.
286      int CheckAddrman() const EXCLUSIVE_LOCKS_REQUIRED(cs);
287  };
288  
289  #endif // BITCOIN_ADDRMAN_IMPL_H