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
   6 #define _BITCOIN_ADDRMAN
   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 private:
  26     //! where knowledge about this address first came from
  27     CNetAddr source;
  28
  29     //! last successful connection by us
  30     int64_t nLastSuccess;
  31
  32     //! last try whatsoever by us:
  33     // int64_t CAddress::nLastTry
  34
  35     //! connection attempts since last successful attempt
  36     int nAttempts;
  37
  38     //! reference count in new sets (memory only)
  39     int nRefCount;
  40
  41     //! in tried set? (memory only)
  42     bool fInTried;
  43
  44     //! position in vRandom
  45     int nRandomPos;
  46
  47     friend class CAddrMan;
  48
  49 public:
  50
  51     ADD_SERIALIZE_METHODS;
  52
  53     template <typename Stream, typename Operation>
  54     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
  55         READWRITE(*(CAddress*)this);
  56         READWRITE(source);
  57         READWRITE(nLastSuccess);
  58         READWRITE(nAttempts);
  59     }
  60
  61     void Init()
  62     {
  63         nLastSuccess = 0;
  64         nLastTry = 0;
  65         nAttempts = 0;
  66         nRefCount = 0;
  67         fInTried = false;
  68         nRandomPos = -1;
  69     }
  70
  71     CAddrInfo(const CAddress &addrIn, const CNetAddr &addrSource) : CAddress(addrIn), source(addrSource)
  72     {
  73         Init();
  74     }
  75
  76     CAddrInfo() : CAddress(), source()
  77     {
  78         Init();
  79     }
  80
  81     //! Calculate in which "tried" bucket this entry belongs
  82     int GetTriedBucket(const std::vector<unsigned char> &nKey) const;
  83
  84     //! Calculate in which "new" bucket this entry belongs, given a certain source
  85     int GetNewBucket(const std::vector<unsigned char> &nKey, const CNetAddr& src) const;
  86
  87     //! Calculate in which "new" bucket this entry belongs, using its default source
  88     int GetNewBucket(const std::vector<unsigned char> &nKey) const
  89     {
  90         return GetNewBucket(nKey, source);
  91     }
  92
  93     //! Determine whether the statistics about this entry are bad enough so that it can just be deleted
  94     bool IsTerrible(int64_t nNow = GetAdjustedTime()) const;
  95
  96     //! Calculate the relative chance this entry should be given when selecting nodes to connect to
  97     double GetChance(int64_t nNow = GetAdjustedTime()) const;
  98
  99 };
 100
 101 /** Stochastic address manager
 102  *
 103  * Design goals:
 104  *  * Keep the address tables in-memory, and asynchronously dump the entire to able in peers.dat.
 105  *  * Make sure no (localized) attacker can fill the entire table with his nodes/addresses.
 106  *
 107  * To that end:
 108  *  * Addresses are organized into buckets.
 109  *    * Address that have not yet been tried go into 256 "new" buckets.
 110  *      * Based on the address range (/16 for IPv4) of source of the information, 32 buckets are selected at random
 111  *      * The actual bucket is chosen from one of these, based on the range the address itself is located.
 112  *      * One single address can occur in up to 4 different buckets, to increase selection chances for addresses that
 113  *        are seen frequently. The chance for increasing this multiplicity decreases exponentially.
 114  *      * When adding a new address to a full bucket, a randomly chosen entry (with a bias favoring less recently seen
 115  *        ones) is removed from it first.
 116  *    * Addresses of nodes that are known to be accessible go into 64 "tried" buckets.
 117  *      * Each address range selects at random 4 of these buckets.
 118  *      * The actual bucket is chosen from one of these, based on the full address.
 119  *      * When adding a new good address to a full bucket, a randomly chosen entry (with a bias favoring less recently
 120  *        tried ones) is evicted from it, back to the "new" buckets.
 121  *    * Bucket selection is based on cryptographic hashing, using a randomly-generated 256-bit key, which should not
 122  *      be observable by adversaries.
 123  *    * Several indexes are kept for high performance. Defining DEBUG_ADDRMAN will introduce frequent (and expensive)
 124  *      consistency checks for the entire data structure.
 125  */
 126
 127 //! total number of buckets for tried addresses
 128 #define ADDRMAN_TRIED_BUCKET_COUNT 64
 129
 130 //! maximum allowed number of entries in buckets for tried addresses
 131 #define ADDRMAN_TRIED_BUCKET_SIZE 64
 132
 133 //! total number of buckets for new addresses
 134 #define ADDRMAN_NEW_BUCKET_COUNT 256
 135
 136 //! maximum allowed number of entries in buckets for new addresses
 137 #define ADDRMAN_NEW_BUCKET_SIZE 64
 138
 139 //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
 140 #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 4
 141
 142 //! over how many buckets entries with new addresses originating from a single group are spread
 143 #define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 32
 144
 145 //! in how many buckets for entries with new addresses a single address may occur
 146 #define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 4
 147
 148 //! how many entries in a bucket with tried addresses are inspected, when selecting one to replace
 149 #define ADDRMAN_TRIED_ENTRIES_INSPECT_ON_EVICT 4
 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     //! secret key to randomize bucket select with
 179     std::vector<unsigned char> nKey;
 180
 181     //! last used nId
 182     int nIdCount;
 183
 184     //! table with information about all nIds
 185     std::map<int, CAddrInfo> mapInfo;
 186
 187     //! find an nId based on its network address
 188     std::map<CNetAddr, int> mapAddr;
 189
 190     //! randomly-ordered vector of all nIds
 191     std::vector<int> vRandom;
 192
 193     // number of "tried" entries
 194     int nTried;
 195
 196     //! list of "tried" buckets
 197     std::vector<std::vector<int> > vvTried;
 198
 199     //! number of (unique) "new" entries
 200     int nNew;
 201
 202     //! list of "new" buckets
 203     std::vector<std::set<int> > vvNew;
 204
 205 protected:
 206
 207     //! Find an entry.
 208     CAddrInfo* Find(const CNetAddr& addr, int *pnId = NULL);
 209
 210     //! find an entry, creating it if necessary.
 211     //! nTime and nServices of the found node are updated, if necessary.
 212     CAddrInfo* Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId = NULL);
 213
 214     //! Swap two elements in vRandom.
 215     void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2);
 216
 217     //! Return position in given bucket to replace.
 218     int SelectTried(int nKBucket);
 219
 220     //! Remove an element from a "new" bucket.
 221     //! This is the only place where actual deletions occur.
 222     //! Elements are never deleted while in the "tried" table, only possibly evicted back to the "new" table.
 223     int ShrinkNew(int nUBucket);
 224
 225     //! Move an entry from the "new" table(s) to the "tried" table
 226     //! @pre vvUnkown[nOrigin].count(nId) != 0
 227     void MakeTried(CAddrInfo& info, int nId, int nOrigin);
 228
 229     //! Mark an entry "good", possibly moving it from "new" to "tried".
 230     void Good_(const CService &addr, int64_t nTime);
 231
 232     //! Add an entry to the "new" table.
 233     bool Add_(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty);
 234
 235     //! Mark an entry as attempted to connect.
 236     void Attempt_(const CService &addr, int64_t nTime);
 237
 238     //! Select an address to connect to.
 239     //! nUnkBias determines how much to favor new addresses over tried ones (min=0, max=100)
 240     CAddress Select_(int nUnkBias);
 241
 242 #ifdef DEBUG_ADDRMAN
 243     //! Perform consistency check. Returns an error code or zero.
 244     int Check_();
 245 #endif
 246
 247     //! Select several addresses at once.
 248     void GetAddr_(std::vector<CAddress> &vAddr);
 249
 250     //! Mark an entry as currently-connected-to.
 251     void Connected_(const CService &addr, int64_t nTime);
 252
 253 public:
 254     /**
 255      * serialized format:
 256      * * version byte (currently 0)
 257      * * nKey
 258      * * nNew
 259      * * nTried
 260      * * number of "new" buckets
 261      * * all nNew addrinfos in vvNew
 262      * * all nTried addrinfos in vvTried
 263      * * for each bucket:
 264      *   * number of elements
 265      *   * for each element: index
 266      *
 267      * Notice that vvTried, mapAddr and vVector are never encoded explicitly;
 268      * they are instead reconstructed from the other information.
 269      *
 270      * vvNew is serialized, but only used if ADDRMAN_UNKOWN_BUCKET_COUNT didn't change,
 271      * otherwise it is reconstructed as well.
 272      *
 273      * This format is more complex, but significantly smaller (at most 1.5 MiB), and supports
 274      * changes to the ADDRMAN_ parameters without breaking the on-disk structure.
 275      *
 276      * We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has
 277      * very little in common.
 278      *
 279      */
 280     template<typename Stream>
 281     void Serialize(Stream &s, int nType, int nVersionDummy) const
 282     {
 283         LOCK(cs);
 284
 285         unsigned char nVersion = 0;
 286         s << nVersion;
 287         s << nKey;
 288         s << nNew;
 289         s << nTried;
 290
 291         int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT;
 292         s << nUBuckets;
 293         std::map<int, int> mapUnkIds;
 294         int nIds = 0;
 295         for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
 296             if (nIds == nNew) break; // this means nNew was wrong, oh ow
 297             mapUnkIds[(*it).first] = nIds;
 298             const CAddrInfo &info = (*it).second;
 299             if (info.nRefCount) {
 300                 s << info;
 301                 nIds++;
 302             }
 303         }
 304         nIds = 0;
 305         for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
 306             if (nIds == nTried) break; // this means nTried was wrong, oh ow
 307             const CAddrInfo &info = (*it).second;
 308             if (info.fInTried) {
 309                 s << info;
 310                 nIds++;
 311             }
 312         }
 313         for (std::vector<std::set<int> >::const_iterator it = vvNew.begin(); it != vvNew.end(); it++) {
 314             const std::set<int> &vNew = (*it);
 315             int nSize = vNew.size();
 316             s << nSize;
 317             for (std::set<int>::const_iterator it2 = vNew.begin(); it2 != vNew.end(); it2++) {
 318                 int nIndex = mapUnkIds[*it2];
 319                 s << nIndex;
 320             }
 321         }
 322     }
 323
 324     template<typename Stream>
 325     void Unserialize(Stream& s, int nType, int nVersionDummy)
 326     {
 327         LOCK(cs);
 328
 329         unsigned char nVersion;
 330         s >> nVersion;
 331         s >> nKey;
 332         s >> nNew;
 333         s >> nTried;
 334
 335         int nUBuckets = 0;
 336         s >> nUBuckets;
 337         nIdCount = 0;
 338         mapInfo.clear();
 339         mapAddr.clear();
 340         vRandom.clear();
 341         vvTried = std::vector<std::vector<int> >(ADDRMAN_TRIED_BUCKET_COUNT, std::vector<int>(0));
 342         vvNew = std::vector<std::set<int> >(ADDRMAN_NEW_BUCKET_COUNT, std::set<int>());
 343         for (int n = 0; n < nNew; n++) {
 344             CAddrInfo &info = mapInfo[n];
 345             s >> info;
 346             mapAddr[info] = n;
 347             info.nRandomPos = vRandom.size();
 348             vRandom.push_back(n);
 349             if (nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) {
 350                 vvNew[info.GetNewBucket(nKey)].insert(n);
 351                 info.nRefCount++;
 352             }
 353         }
 354         nIdCount = nNew;
 355         int nLost = 0;
 356         for (int n = 0; n < nTried; n++) {
 357             CAddrInfo info;
 358             s >> info;
 359             std::vector<int> &vTried = vvTried[info.GetTriedBucket(nKey)];
 360             if (vTried.size() < ADDRMAN_TRIED_BUCKET_SIZE) {
 361                 info.nRandomPos = vRandom.size();
 362                 info.fInTried = true;
 363                 vRandom.push_back(nIdCount);
 364                 mapInfo[nIdCount] = info;
 365                 mapAddr[info] = nIdCount;
 366                 vTried.push_back(nIdCount);
 367                 nIdCount++;
 368             } else {
 369                 nLost++;
 370             }
 371         }
 372         nTried -= nLost;
 373         for (int b = 0; b < nUBuckets; b++) {
 374             std::set<int> &vNew = vvNew[b];
 375             int nSize = 0;
 376             s >> nSize;
 377             for (int n = 0; n < nSize; n++) {
 378                 int nIndex = 0;
 379                 s >> nIndex;
 380                 CAddrInfo &info = mapInfo[nIndex];
 381                 if (nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) {
 382                     info.nRefCount++;
 383                     vNew.insert(nIndex);
 384                 }
 385             }
 386         }
 387     }
 388
 389     unsigned int GetSerializeSize(int nType, int nVersion) const
 390     {
 391         return (CSizeComputer(nType, nVersion) << *this).size();
 392     }
 393
 394     CAddrMan() : vRandom(0), vvTried(ADDRMAN_TRIED_BUCKET_COUNT, std::vector<int>(0)), vvNew(ADDRMAN_NEW_BUCKET_COUNT, std::set<int>())
 395     {
 396          nKey.resize(32);
 397          GetRandBytes(&nKey[0], 32);
 398
 399          nIdCount = 0;
 400          nTried = 0;
 401          nNew = 0;
 402     }
 403
 404     //! Return the number of (unique) addresses in all tables.
 405     int size()
 406     {
 407         return vRandom.size();
 408     }
 409
 410     //! Consistency check
 411     void Check()
 412     {
 413 #ifdef DEBUG_ADDRMAN
 414         {
 415             LOCK(cs);
 416             int err;
 417             if ((err=Check_()))
 418                 LogPrintf("ADDRMAN CONSISTENCY CHECK FAILED!!! err=%i\n", err);
 419         }
 420 #endif
 421     }
 422
 423     //! Add a single address.
 424     bool Add(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty = 0)
 425     {
 426         bool fRet = false;
 427         {
 428             LOCK(cs);
 429             Check();
 430             fRet |= Add_(addr, source, nTimePenalty);
 431             Check();
 432         }
 433         if (fRet)
 434             LogPrint("addrman", "Added %s from %s: %i tried, %i new\n", addr.ToStringIPPort(), source.ToString(), nTried, nNew);
 435         return fRet;
 436     }
 437
 438     //! Add multiple addresses.
 439     bool Add(const std::vector<CAddress> &vAddr, const CNetAddr& source, int64_t nTimePenalty = 0)
 440     {
 441         int nAdd = 0;
 442         {
 443             LOCK(cs);
 444             Check();
 445             for (std::vector<CAddress>::const_iterator it = vAddr.begin(); it != vAddr.end(); it++)
 446                 nAdd += Add_(*it, source, nTimePenalty) ? 1 : 0;
 447             Check();
 448         }
 449         if (nAdd)
 450             LogPrint("addrman", "Added %i addresses from %s: %i tried, %i new\n", nAdd, source.ToString(), nTried, nNew);
 451         return nAdd > 0;
 452     }
 453
 454     //! Mark an entry as accessible.
 455     void Good(const CService &addr, int64_t nTime = GetAdjustedTime())
 456     {
 457         {
 458             LOCK(cs);
 459             Check();
 460             Good_(addr, nTime);
 461             Check();
 462         }
 463     }
 464
 465     //! Mark an entry as connection attempted to.
 466     void Attempt(const CService &addr, int64_t nTime = GetAdjustedTime())
 467     {
 468         {
 469             LOCK(cs);
 470             Check();
 471             Attempt_(addr, nTime);
 472             Check();
 473         }
 474     }
 475
 476     /**
 477      * Choose an address to connect to.
 478      * nUnkBias determines how much "new" entries are favored over "tried" ones (0-100).
 479      */
 480     CAddress Select(int nUnkBias = 50)
 481     {
 482         CAddress addrRet;
 483         {
 484             LOCK(cs);
 485             Check();
 486             addrRet = Select_(nUnkBias);
 487             Check();
 488         }
 489         return addrRet;
 490     }
 491
 492     //! Return a bunch of addresses, selected at random.
 493     std::vector<CAddress> GetAddr()
 494     {
 495         Check();
 496         std::vector<CAddress> vAddr;
 497         {
 498             LOCK(cs);
 499             GetAddr_(vAddr);
 500         }
 501         Check();
 502         return vAddr;
 503     }
 504
 505     //! Mark an entry as currently-connected-to.
 506     void Connected(const CService &addr, int64_t nTime = GetAdjustedTime())
 507     {
 508         {
 509             LOCK(cs);
 510             Check();
 511             Connected_(addr, nTime);
 512             Check();
 513         }
 514     }
 515 };
 516
 517 #endif // _BITCOIN_ADDRMAN