src/addrman.h

   1 // Copyright (c) 2012 Pieter Wuille
   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_H
   6 #define BITCOIN_ADDRMAN_H
   7
   8 #include "netbase.h"
   9 #include "protocol.h"
  10 #include "random.h"
  11 #include "sync.h"
  12 #include "timedata.h"
  13 #include "util.h"
  14
  15 #include <map>
  16 #include <set>
  17 #include <stdint.h>
  18 #include <vector>
  19
  20 /**
  21  * Extended statistics about a CAddress
  22  */
  23 class CAddrInfo : public CAddress
  24 {
  25
  26
  27 public:
  28     //! last try whatsoever by us (memory only)
  29     int64_t nLastTry;
  30
  31 private:
  32     //! where knowledge about this address first came from
  33     CNetAddr source;
  34
  35     //! last successful connection by us
  36     int64_t nLastSuccess;
  37
  38     //! connection attempts since last successful attempt
  39     int nAttempts;
  40
  41     //! reference count in new sets (memory only)
  42     int nRefCount;
  43
  44     //! in tried set? (memory only)
  45     bool fInTried;
  46
  47     //! position in vRandom
  48     int nRandomPos;
  49
  50     friend class CAddrMan;
  51
  52 public:
  53
  54     ADD_SERIALIZE_METHODS;
  55
  56     template <typename Stream, typename Operation>
  57     inline void SerializationOp(Stream& s, Operation ser_action) {
  58         READWRITE(*(CAddress*)this);
  59         READWRITE(source);
  60         READWRITE(nLastSuccess);
  61         READWRITE(nAttempts);
  62     }
  63
  64     void Init()
  65     {
  66         nLastSuccess = 0;
  67         nLastTry = 0;
  68         nAttempts = 0;
  69         nRefCount = 0;
  70         fInTried = false;
  71         nRandomPos = -1;
  72     }
  73
  74     CAddrInfo(const CAddress &addrIn, const CNetAddr &addrSource) : CAddress(addrIn), source(addrSource)
  75     {
  76         Init();
  77     }
  78
  79     CAddrInfo() : CAddress(), source()
  80     {
  81         Init();
  82     }
  83
  84     //! Calculate in which "tried" bucket this entry belongs
  85     int GetTriedBucket(const uint256 &nKey) const;
  86
  87     //! Calculate in which "new" bucket this entry belongs, given a certain source
  88     int GetNewBucket(const uint256 &nKey, const CNetAddr& src) const;
  89
  90     //! Calculate in which "new" bucket this entry belongs, using its default source
  91     int GetNewBucket(const uint256 &nKey) const
  92     {
  93         return GetNewBucket(nKey, source);
  94     }
  95
  96     //! Calculate in which position of a bucket to store this entry.
  97     int GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const;
  98
  99     //! Determine whether the statistics about this entry are bad enough so that it can just be deleted
 100     bool IsTerrible(int64_t nNow = GetAdjustedTime()) const;
 101
 102     //! Calculate the relative chance this entry should be given when selecting nodes to connect to
 103     double GetChance(int64_t nNow = GetAdjustedTime()) const;
 104
 105 };
 106
 107 /** Stochastic address manager
 108  *
 109  * Design goals:
 110  *  * Keep the address tables in-memory, and asynchronously dump the entire table to peers.dat.
 111  *  * Make sure no (localized) attacker can fill the entire table with his nodes/addresses.
 112  *
 113  * To that end:
 114  *  * Addresses are organized into buckets.
 115  *    * Addresses that have not yet been tried go into 1024 "new" buckets.
 116  *      * Based on the address range (/16 for IPv4) of the source of information, 64 buckets are selected at random.
 117  *      * The actual bucket is chosen from one of these, based on the range in which the address itself is located.
 118  *      * One single address can occur in up to 8 different buckets to increase selection chances for addresses that
 119  *        are seen frequently. The chance for increasing this multiplicity decreases exponentially.
 120  *      * When adding a new address to a full bucket, a randomly chosen entry (with a bias favoring less recently seen
 121  *        ones) is removed from it first.
 122  *    * Addresses of nodes that are known to be accessible go into 256 "tried" buckets.
 123  *      * Each address range selects at random 8 of these buckets.
 124  *      * The actual bucket is chosen from one of these, based on the full address.
 125  *      * When adding a new good address to a full bucket, a randomly chosen entry (with a bias favoring less recently
 126  *        tried ones) is evicted from it, back to the "new" buckets.
 127  *    * Bucket selection is based on cryptographic hashing, using a randomly-generated 256-bit key, which should not
 128  *      be observable by adversaries.
 129  *    * Several indexes are kept for high performance. Defining DEBUG_ADDRMAN will introduce frequent (and expensive)
 130  *      consistency checks for the entire data structure.
 131  */
 132
 133 //! total number of buckets for tried addresses
 134 #define ADDRMAN_TRIED_BUCKET_COUNT 256
 135
 136 //! total number of buckets for new addresses
 137 #define ADDRMAN_NEW_BUCKET_COUNT 1024
 138
 139 //! maximum allowed number of entries in buckets for new and tried addresses
 140 #define ADDRMAN_BUCKET_SIZE 64
 141
 142 //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
 143 #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8
 144
 145 //! over how many buckets entries with new addresses originating from a single group are spread
 146 #define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 64
 147
 148 //! in how many buckets for entries with new addresses a single address may occur
 149 #define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 8
 150
 151 //! how old addresses can maximally be
 152 #define ADDRMAN_HORIZON_DAYS 30
 153
 154 //! after how many failed attempts we give up on a new node
 155 #define ADDRMAN_RETRIES 3
 156
 157 //! how many successive failures are allowed ...
 158 #define ADDRMAN_MAX_FAILURES 10
 159
 160 //! ... in at least this many days
 161 #define ADDRMAN_MIN_FAIL_DAYS 7
 162
 163 //! the maximum percentage of nodes to return in a getaddr call
 164 #define ADDRMAN_GETADDR_MAX_PCT 23
 165
 166 //! the maximum number of nodes to return in a getaddr call
 167 #define ADDRMAN_GETADDR_MAX 2500
 168
 169 /**
 170  * Stochastical (IP) address manager
 171  */
 172 class CAddrMan
 173 {
 174 private:
 175     //! critical section to protect the inner data structures
 176     mutable CCriticalSection cs;
 177
 178     //! last used nId
 179     int nIdCount;
 180
 181     //! table with information about all nIds
 182     std::map<int, CAddrInfo> mapInfo;
 183
 184     //! find an nId based on its network address
 185     std::map<CNetAddr, int> mapAddr;
 186
 187     //! randomly-ordered vector of all nIds
 188     std::vector<int> vRandom;
 189
 190     // number of "tried" entries
 191     int nTried;
 192
 193     //! list of "tried" buckets
 194     int vvTried[ADDRMAN_TRIED_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE];
 195
 196     //! number of (unique) "new" entries
 197     int nNew;
 198
 199     //! list of "new" buckets
 200     int vvNew[ADDRMAN_NEW_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE];
 201
 202 protected:
 203     //! secret key to randomize bucket select with
 204     uint256 nKey;
 205
 206     //! Find an entry.
 207     CAddrInfo* Find(const CNetAddr& addr, int *pnId = NULL);
 208
 209     //! find an entry, creating it if necessary.
 210     //! nTime and nServices of the found node are updated, if necessary.
 211     CAddrInfo* Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId = NULL);
 212
 213     //! Swap two elements in vRandom.
 214     void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2);
 215
 216     //! Move an entry from the "new" table(s) to the "tried" table
 217     void MakeTried(CAddrInfo& info, int nId);
 218
 219     //! Delete an entry. It must not be in tried, and have refcount 0.
 220     void Delete(int nId);
 221
 222     //! Clear a position in a "new" table. This is the only place where entries are actually deleted.
 223     void ClearNew(int nUBucket, int nUBucketPos);
 224
 225     //! Mark an entry "good", possibly moving it from "new" to "tried".
 226     void Good_(const CService &addr, int64_t nTime);
 227
 228     //! Add an entry to the "new" table.
 229     bool Add_(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty);
 230
 231     //! Mark an entry as attempted to connect.
 232     void Attempt_(const CService &addr, int64_t nTime);
 233
 234     //! Select an address to connect to, if newOnly is set to true, only the new table is selected from.
 235     CAddrInfo Select_(bool newOnly);
 236
 237     //! Wraps GetRandInt to allow tests to override RandomInt and make it deterministic.
 238     virtual int RandomInt(int nMax);
 239
 240 #ifdef DEBUG_ADDRMAN
 241     //! Perform consistency check. Returns an error code or zero.
 242     int Check_();
 243 #endif
 244
 245     //! Select several addresses at once.
 246     void GetAddr_(std::vector<CAddress> &vAddr);
 247
 248     //! Mark an entry as currently-connected-to.
 249     void Connected_(const CService &addr, int64_t nTime);
 250
 251 public:
 252     /**
 253      * serialized format:
 254      * * version byte (currently 1)
 255      * * 0x20 + nKey (serialized as if it were a vector, for backward compatibility)
 256      * * nNew
 257      * * nTried
 258      * * number of "new" buckets XOR 2**30
 259      * * all nNew addrinfos in vvNew
 260      * * all nTried addrinfos in vvTried
 261      * * for each bucket:
 262      *   * number of elements
 263      *   * for each element: index
 264      *
 265      * 2**30 is xorred with the number of buckets to make addrman deserializer v0 detect it
 266      * as incompatible. This is necessary because it did not check the version number on
 267      * deserialization.
 268      *
 269      * Notice that vvTried, mapAddr and vVector are never encoded explicitly;
 270      * they are instead reconstructed from the other information.
 271      *
 272      * vvNew is serialized, but only used if ADDRMAN_UNKNOWN_BUCKET_COUNT didn't change,
 273      * otherwise it is reconstructed as well.
 274      *
 275      * This format is more complex, but significantly smaller (at most 1.5 MiB), and supports
 276      * changes to the ADDRMAN_ parameters without breaking the on-disk structure.
 277      *
 278      * We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has
 279      * very little in common.
 280      */
 281     template<typename Stream>
 282     void Serialize(Stream &s) const
 283     {
 284         LOCK(cs);
 285
 286         unsigned char nVersion = 1;
 287         s << nVersion;
 288         s << ((unsigned char)32);
 289         s << nKey;
 290         s << nNew;
 291         s << nTried;
 292
 293         int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30);
 294         s << nUBuckets;
 295         std::map<int, int> mapUnkIds;
 296         int nIds = 0;
 297         for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
 298             mapUnkIds[(*it).first] = nIds;
 299             const CAddrInfo &info = (*it).second;
 300             if (info.nRefCount) {
 301                 assert(nIds != nNew); // this means nNew was wrong, oh ow
 302                 s << info;
 303                 nIds++;
 304             }
 305         }
 306         nIds = 0;
 307         for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
 308             const CAddrInfo &info = (*it).second;
 309             if (info.fInTried) {
 310                 assert(nIds != nTried); // this means nTried was wrong, oh ow
 311                 s << info;
 312                 nIds++;
 313             }
 314         }
 315         for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
 316             int nSize = 0;
 317             for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 318                 if (vvNew[bucket][i] != -1)
 319                     nSize++;
 320             }
 321             s << nSize;
 322             for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 323                 if (vvNew[bucket][i] != -1) {
 324                     int nIndex = mapUnkIds[vvNew[bucket][i]];
 325                     s << nIndex;
 326                 }
 327             }
 328         }
 329     }
 330
 331     template<typename Stream>
 332     void Unserialize(Stream& s)
 333     {
 334         LOCK(cs);
 335
 336         Clear();
 337
 338         unsigned char nVersion;
 339         s >> nVersion;
 340         unsigned char nKeySize;
 341         s >> nKeySize;
 342         if (nKeySize != 32) throw std::ios_base::failure("Incorrect keysize in addrman deserialization");
 343         s >> nKey;
 344         s >> nNew;
 345         s >> nTried;
 346         int nUBuckets = 0;
 347         s >> nUBuckets;
 348         if (nVersion != 0) {
 349             nUBuckets ^= (1 << 30);
 350         }
 351
 352         if (nNew > ADDRMAN_NEW_BUCKET_COUNT * ADDRMAN_BUCKET_SIZE) {
 353             throw std::ios_base::failure("Corrupt CAddrMan serialization, nNew exceeds limit.");
 354         }
 355
 356         if (nTried > ADDRMAN_TRIED_BUCKET_COUNT * ADDRMAN_BUCKET_SIZE) {
 357             throw std::ios_base::failure("Corrupt CAddrMan serialization, nTried exceeds limit.");
 358         }
 359
 360         // Deserialize entries from the new table.
 361         for (int n = 0; n < nNew; n++) {
 362             CAddrInfo &info = mapInfo[n];
 363             s >> info;
 364             mapAddr[info] = n;
 365             info.nRandomPos = vRandom.size();
 366             vRandom.push_back(n);
 367             if (nVersion != 1 || nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) {
 368                 // In case the new table data cannot be used (nVersion unknown, or bucket count wrong),
 369                 // immediately try to give them a reference based on their primary source address.
 370                 int nUBucket = info.GetNewBucket(nKey);
 371                 int nUBucketPos = info.GetBucketPosition(nKey, true, nUBucket);
 372                 if (vvNew[nUBucket][nUBucketPos] == -1) {
 373                     vvNew[nUBucket][nUBucketPos] = n;
 374                     info.nRefCount++;
 375                 }
 376             }
 377         }
 378         nIdCount = nNew;
 379
 380         // Deserialize entries from the tried table.
 381         int nLost = 0;
 382         for (int n = 0; n < nTried; n++) {
 383             CAddrInfo info;
 384             s >> info;
 385             int nKBucket = info.GetTriedBucket(nKey);
 386             int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket);
 387             if (vvTried[nKBucket][nKBucketPos] == -1) {
 388                 info.nRandomPos = vRandom.size();
 389                 info.fInTried = true;
 390                 vRandom.push_back(nIdCount);
 391                 mapInfo[nIdCount] = info;
 392                 mapAddr[info] = nIdCount;
 393                 vvTried[nKBucket][nKBucketPos] = nIdCount;
 394                 nIdCount++;
 395             } else {
 396                 nLost++;
 397             }
 398         }
 399         nTried -= nLost;
 400
 401         // Deserialize positions in the new table (if possible).
 402         for (int bucket = 0; bucket < nUBuckets; bucket++) {
 403             int nSize = 0;
 404             s >> nSize;
 405             for (int n = 0; n < nSize; n++) {
 406                 int nIndex = 0;
 407                 s >> nIndex;
 408                 if (nIndex >= 0 && nIndex < nNew) {
 409                     CAddrInfo &info = mapInfo[nIndex];
 410                     int nUBucketPos = info.GetBucketPosition(nKey, true, bucket);
 411                     if (nVersion == 1 && nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && vvNew[bucket][nUBucketPos] == -1 && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) {
 412                         info.nRefCount++;
 413                         vvNew[bucket][nUBucketPos] = nIndex;
 414                     }
 415                 }
 416             }
 417         }
 418
 419         // Prune new entries with refcount 0 (as a result of collisions).
 420         int nLostUnk = 0;
 421         for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); ) {
 422             if (it->second.fInTried == false && it->second.nRefCount == 0) {
 423                 std::map<int, CAddrInfo>::const_iterator itCopy = it++;
 424                 Delete(itCopy->first);
 425                 nLostUnk++;
 426             } else {
 427                 it++;
 428             }
 429         }
 430         if (nLost + nLostUnk > 0) {
 431             LogPrint("addrman", "addrman lost %i new and %i tried addresses due to collisions\n", nLostUnk, nLost);
 432         }
 433
 434         Check();
 435     }
 436
 437     void Clear()
 438     {
 439         std::vector<int>().swap(vRandom);
 440         nKey = GetRandHash();
 441         for (size_t bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
 442             for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) {
 443                 vvNew[bucket][entry] = -1;
 444             }
 445         }
 446         for (size_t bucket = 0; bucket < ADDRMAN_TRIED_BUCKET_COUNT; bucket++) {
 447             for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) {
 448                 vvTried[bucket][entry] = -1;
 449             }
 450         }
 451
 452         nIdCount = 0;
 453         nTried = 0;
 454         nNew = 0;
 455     }
 456
 457     CAddrMan()
 458     {
 459         Clear();
 460     }
 461
 462     ~CAddrMan()
 463     {
 464         nKey.SetNull();
 465     }
 466
 467     //! Return the number of (unique) addresses in all tables.
 468     size_t size() const
 469     {
 470         return vRandom.size();
 471     }
 472
 473     //! Consistency check
 474     void Check()
 475     {
 476 #ifdef DEBUG_ADDRMAN
 477         {
 478             LOCK(cs);
 479             int err;
 480             if ((err=Check_()))
 481                 LogPrintf("ADDRMAN CONSISTENCY CHECK FAILED!!! err=%i\n", err);
 482         }
 483 #endif
 484     }
 485
 486     //! Add a single address.
 487     bool Add(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty = 0)
 488     {
 489         bool fRet = false;
 490         {
 491             LOCK(cs);
 492             Check();
 493             fRet |= Add_(addr, source, nTimePenalty);
 494             Check();
 495         }
 496         if (fRet)
 497             LogPrint("addrman", "Added %s from %s: %i tried, %i new\n", addr.ToStringIPPort(), source.ToString(), nTried, nNew);
 498         return fRet;
 499     }
 500
 501     //! Add multiple addresses.
 502     bool Add(const std::vector<CAddress> &vAddr, const CNetAddr& source, int64_t nTimePenalty = 0)
 503     {
 504         int nAdd = 0;
 505         {
 506             LOCK(cs);
 507             Check();
 508             for (std::vector<CAddress>::const_iterator it = vAddr.begin(); it != vAddr.end(); it++)
 509                 nAdd += Add_(*it, source, nTimePenalty) ? 1 : 0;
 510             Check();
 511         }
 512         if (nAdd)
 513             LogPrint("addrman", "Added %i addresses from %s: %i tried, %i new\n", nAdd, source.ToString(), nTried, nNew);
 514         return nAdd > 0;
 515     }
 516
 517     //! Mark an entry as accessible.
 518     void Good(const CService &addr, int64_t nTime = GetAdjustedTime())
 519     {
 520         {
 521             LOCK(cs);
 522             Check();
 523             Good_(addr, nTime);
 524             Check();
 525         }
 526     }
 527
 528     //! Mark an entry as connection attempted to.
 529     void Attempt(const CService &addr, int64_t nTime = GetAdjustedTime())
 530     {
 531         {
 532             LOCK(cs);
 533             Check();
 534             Attempt_(addr, nTime);
 535             Check();
 536         }
 537     }
 538
 539     /**
 540      * Choose an address to connect to.
 541      */
 542     CAddrInfo Select(bool newOnly = false)
 543     {
 544         CAddrInfo addrRet;
 545         {
 546             LOCK(cs);
 547             Check();
 548             addrRet = Select_(newOnly);
 549             Check();
 550         }
 551         return addrRet;
 552     }
 553
 554     //! Return a bunch of addresses, selected at random.
 555     std::vector<CAddress> GetAddr()
 556     {
 557         Check();
 558         std::vector<CAddress> vAddr;
 559         {
 560             LOCK(cs);
 561             GetAddr_(vAddr);
 562         }
 563         Check();
 564         return vAddr;
 565     }
 566
 567     //! Mark an entry as currently-connected-to.
 568     void Connected(const CService &addr, int64_t nTime = GetAdjustedTime())
 569     {
 570         {
 571             LOCK(cs);
 572             Check();
 573             Connected_(addr, nTime);
 574             Check();
 575         }
 576     }
 577
 578 };
 579
 580 #endif // BITCOIN_ADDRMAN_H