src/addrman.cpp

   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 #include "addrman.h"
   6
   7 #include "hash.h"
   8 #include "serialize.h"
   9 #include "streams.h"
  10
  11 int CAddrInfo::GetTriedBucket(const uint256& nKey) const
  12 {
  13     uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetKey()).GetHash().GetCheapHash();
  14     uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP)).GetHash().GetCheapHash();
  15     return hash2 % ADDRMAN_TRIED_BUCKET_COUNT;
  16 }
  17
  18 int CAddrInfo::GetNewBucket(const uint256& nKey, const CNetAddr& src) const
  19 {
  20     std::vector<unsigned char> vchSourceGroupKey = src.GetGroup();
  21     uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << vchSourceGroupKey).GetHash().GetCheapHash();
  22     uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP)).GetHash().GetCheapHash();
  23     return hash2 % ADDRMAN_NEW_BUCKET_COUNT;
  24 }
  25
  26 int CAddrInfo::GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const
  27 {
  28     uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << (fNew ? 'N' : 'K') << nBucket << GetKey()).GetHash().GetCheapHash();
  29     return hash1 % ADDRMAN_BUCKET_SIZE;
  30 }
  31
  32 bool CAddrInfo::IsTerrible(int64_t nNow) const
  33 {
  34     if (nLastTry && nLastTry >= nNow - 60) // never remove things tried in the last minute
  35         return false;
  36
  37     if (nTime > nNow + 10 * 60) // came in a flying DeLorean
  38         return true;
  39
  40     if (nTime == 0 || nNow - nTime > ADDRMAN_HORIZON_DAYS * 24 * 60 * 60) // not seen in recent history
  41         return true;
  42
  43     if (nLastSuccess == 0 && nAttempts >= ADDRMAN_RETRIES) // tried N times and never a success
  44         return true;
  45
  46     if (nNow - nLastSuccess > ADDRMAN_MIN_FAIL_DAYS * 24 * 60 * 60 && nAttempts >= ADDRMAN_MAX_FAILURES) // N successive failures in the last week
  47         return true;
  48
  49     return false;
  50 }
  51
  52 double CAddrInfo::GetChance(int64_t nNow) const
  53 {
  54     double fChance = 1.0;
  55
  56     int64_t nSinceLastSeen = nNow - nTime;
  57     int64_t nSinceLastTry = nNow - nLastTry;
  58
  59     if (nSinceLastSeen < 0)
  60         nSinceLastSeen = 0;
  61     if (nSinceLastTry < 0)
  62         nSinceLastTry = 0;
  63
  64     // deprioritize very recent attempts away
  65     if (nSinceLastTry < 60 * 10)
  66         fChance *= 0.01;
  67
  68     // deprioritize 66% after each failed attempt, but at most 1/28th to avoid the search taking forever or overly penalizing outages.
  69     fChance *= pow(0.66, std::min(nAttempts, 8));
  70
  71     return fChance;
  72 }
  73
  74 CAddrInfo* CAddrMan::Find(const CNetAddr& addr, int* pnId)
  75 {
  76     std::map<CNetAddr, int>::iterator it = mapAddr.find(addr);
  77     if (it == mapAddr.end())
  78         return NULL;
  79     if (pnId)
  80         *pnId = (*it).second;
  81     std::map<int, CAddrInfo>::iterator it2 = mapInfo.find((*it).second);
  82     if (it2 != mapInfo.end())
  83         return &(*it2).second;
  84     return NULL;
  85 }
  86
  87 CAddrInfo* CAddrMan::Create(const CAddress& addr, const CNetAddr& addrSource, int* pnId)
  88 {
  89     int nId = nIdCount++;
  90     mapInfo[nId] = CAddrInfo(addr, addrSource);
  91     mapAddr[addr] = nId;
  92     mapInfo[nId].nRandomPos = vRandom.size();
  93     vRandom.push_back(nId);
  94     if (pnId)
  95         *pnId = nId;
  96     return &mapInfo[nId];
  97 }
  98
  99 void CAddrMan::SwapRandom(unsigned int nRndPos1, unsigned int nRndPos2)
 100 {
 101     if (nRndPos1 == nRndPos2)
 102         return;
 103
 104     assert(nRndPos1 < vRandom.size() && nRndPos2 < vRandom.size());
 105
 106     int nId1 = vRandom[nRndPos1];
 107     int nId2 = vRandom[nRndPos2];
 108
 109     assert(mapInfo.count(nId1) == 1);
 110     assert(mapInfo.count(nId2) == 1);
 111
 112     mapInfo[nId1].nRandomPos = nRndPos2;
 113     mapInfo[nId2].nRandomPos = nRndPos1;
 114
 115     vRandom[nRndPos1] = nId2;
 116     vRandom[nRndPos2] = nId1;
 117 }
 118
 119 void CAddrMan::Delete(int nId)
 120 {
 121     assert(mapInfo.count(nId) != 0);
 122     CAddrInfo& info = mapInfo[nId];
 123     assert(!info.fInTried);
 124     assert(info.nRefCount == 0);
 125
 126     SwapRandom(info.nRandomPos, vRandom.size() - 1);
 127     vRandom.pop_back();
 128     mapAddr.erase(info);
 129     mapInfo.erase(nId);
 130     nNew--;
 131 }
 132
 133 void CAddrMan::ClearNew(int nUBucket, int nUBucketPos)
 134 {
 135     // if there is an entry in the specified bucket, delete it.
 136     if (vvNew[nUBucket][nUBucketPos] != -1) {
 137         int nIdDelete = vvNew[nUBucket][nUBucketPos];
 138         CAddrInfo& infoDelete = mapInfo[nIdDelete];
 139         assert(infoDelete.nRefCount > 0);
 140         infoDelete.nRefCount--;
 141         vvNew[nUBucket][nUBucketPos] = -1;
 142         if (infoDelete.nRefCount == 0) {
 143             Delete(nIdDelete);
 144         }
 145     }
 146 }
 147
 148 void CAddrMan::MakeTried(CAddrInfo& info, int nId)
 149 {
 150     // remove the entry from all new buckets
 151     for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
 152         int pos = info.GetBucketPosition(nKey, true, bucket);
 153         if (vvNew[bucket][pos] == nId) {
 154             vvNew[bucket][pos] = -1;
 155             info.nRefCount--;
 156         }
 157     }
 158     nNew--;
 159
 160     assert(info.nRefCount == 0);
 161
 162     // which tried bucket to move the entry to
 163     int nKBucket = info.GetTriedBucket(nKey);
 164     int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket);
 165
 166     // first make space to add it (the existing tried entry there is moved to new, deleting whatever is there).
 167     if (vvTried[nKBucket][nKBucketPos] != -1) {
 168         // find an item to evict
 169         int nIdEvict = vvTried[nKBucket][nKBucketPos];
 170         assert(mapInfo.count(nIdEvict) == 1);
 171         CAddrInfo& infoOld = mapInfo[nIdEvict];
 172
 173         // Remove the to-be-evicted item from the tried set.
 174         infoOld.fInTried = false;
 175         vvTried[nKBucket][nKBucketPos] = -1;
 176         nTried--;
 177
 178         // find which new bucket it belongs to
 179         int nUBucket = infoOld.GetNewBucket(nKey);
 180         int nUBucketPos = infoOld.GetBucketPosition(nKey, true, nUBucket);
 181         ClearNew(nUBucket, nUBucketPos);
 182         assert(vvNew[nUBucket][nUBucketPos] == -1);
 183
 184         // Enter it into the new set again.
 185         infoOld.nRefCount = 1;
 186         vvNew[nUBucket][nUBucketPos] = nIdEvict;
 187         nNew++;
 188     }
 189     assert(vvTried[nKBucket][nKBucketPos] == -1);
 190
 191     vvTried[nKBucket][nKBucketPos] = nId;
 192     nTried++;
 193     info.fInTried = true;
 194 }
 195
 196 void CAddrMan::Good_(const CService& addr, int64_t nTime)
 197 {
 198     int nId;
 199     CAddrInfo* pinfo = Find(addr, &nId);
 200
 201     // if not found, bail out
 202     if (!pinfo)
 203         return;
 204
 205     CAddrInfo& info = *pinfo;
 206
 207     // check whether we are talking about the exact same CService (including same port)
 208     if (info != addr)
 209         return;
 210
 211     // update info
 212     info.nLastSuccess = nTime;
 213     info.nLastTry = nTime;
 214     info.nAttempts = 0;
 215     // nTime is not updated here, to avoid leaking information about
 216     // currently-connected peers.
 217
 218     // if it is already in the tried set, don't do anything else
 219     if (info.fInTried)
 220         return;
 221
 222     // find a bucket it is in now
 223     int nRnd = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
 224     int nUBucket = -1;
 225     for (unsigned int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
 226         int nB = (n + nRnd) % ADDRMAN_NEW_BUCKET_COUNT;
 227         int nBpos = info.GetBucketPosition(nKey, true, nB);
 228         if (vvNew[nB][nBpos] == nId) {
 229             nUBucket = nB;
 230             break;
 231         }
 232     }
 233
 234     // if no bucket is found, something bad happened;
 235     // TODO: maybe re-add the node, but for now, just bail out
 236     if (nUBucket == -1)
 237         return;
 238
 239     LogPrint("addrman", "Moving %s to tried\n", addr.ToString());
 240
 241     // move nId to the tried tables
 242     MakeTried(info, nId);
 243 }
 244
 245 bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty)
 246 {
 247     if (!addr.IsRoutable())
 248         return false;
 249
 250     bool fNew = false;
 251     int nId;
 252     CAddrInfo* pinfo = Find(addr, &nId);
 253
 254     if (pinfo) {
 255         // periodically update nTime
 256         bool fCurrentlyOnline = (GetAdjustedTime() - addr.nTime < 24 * 60 * 60);
 257         int64_t nUpdateInterval = (fCurrentlyOnline ? 60 * 60 : 24 * 60 * 60);
 258         if (addr.nTime && (!pinfo->nTime || pinfo->nTime < addr.nTime - nUpdateInterval - nTimePenalty))
 259             pinfo->nTime = std::max((int64_t)0, addr.nTime - nTimePenalty);
 260
 261         // add services
 262         pinfo->nServices |= addr.nServices;
 263
 264         // do not update if no new information is present
 265         if (!addr.nTime || (pinfo->nTime && addr.nTime <= pinfo->nTime))
 266             return false;
 267
 268         // do not update if the entry was already in the "tried" table
 269         if (pinfo->fInTried)
 270             return false;
 271
 272         // do not update if the max reference count is reached
 273         if (pinfo->nRefCount == ADDRMAN_NEW_BUCKETS_PER_ADDRESS)
 274             return false;
 275
 276         // stochastic test: previous nRefCount == N: 2^N times harder to increase it
 277         int nFactor = 1;
 278         for (int n = 0; n < pinfo->nRefCount; n++)
 279             nFactor *= 2;
 280         if (nFactor > 1 && (RandomInt(nFactor) != 0))
 281             return false;
 282     } else {
 283         pinfo = Create(addr, source, &nId);
 284         pinfo->nTime = std::max((int64_t)0, (int64_t)pinfo->nTime - nTimePenalty);
 285         nNew++;
 286         fNew = true;
 287     }
 288
 289     int nUBucket = pinfo->GetNewBucket(nKey, source);
 290     int nUBucketPos = pinfo->GetBucketPosition(nKey, true, nUBucket);
 291     if (vvNew[nUBucket][nUBucketPos] != nId) {
 292         bool fInsert = vvNew[nUBucket][nUBucketPos] == -1;
 293         if (!fInsert) {
 294             CAddrInfo& infoExisting = mapInfo[vvNew[nUBucket][nUBucketPos]];
 295             if (infoExisting.IsTerrible() || (infoExisting.nRefCount > 1 && pinfo->nRefCount == 0)) {
 296                 // Overwrite the existing new table entry.
 297                 fInsert = true;
 298             }
 299         }
 300         if (fInsert) {
 301             ClearNew(nUBucket, nUBucketPos);
 302             pinfo->nRefCount++;
 303             vvNew[nUBucket][nUBucketPos] = nId;
 304         } else {
 305             if (pinfo->nRefCount == 0) {
 306                 Delete(nId);
 307             }
 308         }
 309     }
 310     return fNew;
 311 }
 312
 313 void CAddrMan::Attempt_(const CService& addr, int64_t nTime)
 314 {
 315     CAddrInfo* pinfo = Find(addr);
 316
 317     // if not found, bail out
 318     if (!pinfo)
 319         return;
 320
 321     CAddrInfo& info = *pinfo;
 322
 323     // check whether we are talking about the exact same CService (including same port)
 324     if (info != addr)
 325         return;
 326
 327     // update info
 328     info.nLastTry = nTime;
 329     info.nAttempts++;
 330 }
 331
 332 CAddrInfo CAddrMan::Select_(bool newOnly)
 333 {
 334     if (size() == 0)
 335         return CAddrInfo();
 336
 337     // Track number of attempts to find a table entry, before giving up to avoid infinite loop
 338     const int kMaxRetries = 200000;         // magic number so unit tests can pass
 339     const int kRetriesBetweenSleep = 1000;
 340     const int kRetrySleepInterval = 100;    // milliseconds
 341
 342     if (newOnly && nNew == 0)
 343         return CAddrInfo();
 344
 345     // Use a 50% chance for choosing between tried and new table entries.
 346     if (!newOnly &&
 347        (nTried > 0 && (nNew == 0 || RandomInt(2) == 0))) {
 348         // use a tried node
 349         double fChanceFactor = 1.0;
 350         while (1) {
 351             int i = 0;
 352             int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT);
 353             int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
 354             while (vvTried[nKBucket][nKBucketPos] == -1) {
 355                 nKBucket = (nKBucket + insecure_rand()) % ADDRMAN_TRIED_BUCKET_COUNT;
 356                 nKBucketPos = (nKBucketPos + insecure_rand()) % ADDRMAN_BUCKET_SIZE;
 357                 if (i++ > kMaxRetries)
 358                     return CAddrInfo();
 359                 if (i % kRetriesBetweenSleep == 0 && !nKey.IsNull())
 360                     MilliSleep(kRetrySleepInterval);
 361             }
 362             int nId = vvTried[nKBucket][nKBucketPos];
 363             assert(mapInfo.count(nId) == 1);
 364             CAddrInfo& info = mapInfo[nId];
 365             if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
 366                 return info;
 367             fChanceFactor *= 1.2;
 368         }
 369     } else {
 370         // use a new node
 371         double fChanceFactor = 1.0;
 372         while (1) {
 373             int i = 0;
 374             int nUBucket = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
 375             int nUBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
 376             while (vvNew[nUBucket][nUBucketPos] == -1) {
 377                 nUBucket = (nUBucket + insecure_rand()) % ADDRMAN_NEW_BUCKET_COUNT;
 378                 nUBucketPos = (nUBucketPos + insecure_rand()) % ADDRMAN_BUCKET_SIZE;
 379                 if (i++ > kMaxRetries)
 380                     return CAddrInfo();
 381                 if (i % kRetriesBetweenSleep == 0 && !nKey.IsNull())
 382                     MilliSleep(kRetrySleepInterval);
 383             }
 384             int nId = vvNew[nUBucket][nUBucketPos];
 385             assert(mapInfo.count(nId) == 1);
 386             CAddrInfo& info = mapInfo[nId];
 387             if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
 388                 return info;
 389             fChanceFactor *= 1.2;
 390         }
 391     }
 392
 393     return CAddrInfo();
 394 }
 395
 396 #ifdef DEBUG_ADDRMAN
 397 int CAddrMan::Check_()
 398 {
 399     std::set<int> setTried;
 400     std::map<int, int> mapNew;
 401
 402     if (vRandom.size() != nTried + nNew)
 403         return -7;
 404
 405     for (std::map<int, CAddrInfo>::iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
 406         int n = (*it).first;
 407         CAddrInfo& info = (*it).second;
 408         if (info.fInTried) {
 409             if (!info.nLastSuccess)
 410                 return -1;
 411             if (info.nRefCount)
 412                 return -2;
 413             setTried.insert(n);
 414         } else {
 415             if (info.nRefCount < 0 || info.nRefCount > ADDRMAN_NEW_BUCKETS_PER_ADDRESS)
 416                 return -3;
 417             if (!info.nRefCount)
 418                 return -4;
 419             mapNew[n] = info.nRefCount;
 420         }
 421         if (mapAddr[info] != n)
 422             return -5;
 423         if (info.nRandomPos < 0 || info.nRandomPos >= vRandom.size() || vRandom[info.nRandomPos] != n)
 424             return -14;
 425         if (info.nLastTry < 0)
 426             return -6;
 427         if (info.nLastSuccess < 0)
 428             return -8;
 429     }
 430
 431     if (setTried.size() != nTried)
 432         return -9;
 433     if (mapNew.size() != nNew)
 434         return -10;
 435
 436     for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) {
 437         for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 438              if (vvTried[n][i] != -1) {
 439                  if (!setTried.count(vvTried[n][i]))
 440                      return -11;
 441                  if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n)
 442                      return -17;
 443                  if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i)
 444                      return -18;
 445                  setTried.erase(vvTried[n][i]);
 446              }
 447         }
 448     }
 449
 450     for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
 451         for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 452             if (vvNew[n][i] != -1) {
 453                 if (!mapNew.count(vvNew[n][i]))
 454                     return -12;
 455                 if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i)
 456                     return -19;
 457                 if (--mapNew[vvNew[n][i]] == 0)
 458                     mapNew.erase(vvNew[n][i]);
 459             }
 460         }
 461     }
 462
 463     if (setTried.size())
 464         return -13;
 465     if (mapNew.size())
 466         return -15;
 467     if (nKey.IsNull())
 468         return -16;
 469
 470     return 0;
 471 }
 472 #endif
 473
 474 void CAddrMan::GetAddr_(std::vector<CAddress>& vAddr)
 475 {
 476     unsigned int nNodes = ADDRMAN_GETADDR_MAX_PCT * vRandom.size() / 100;
 477     if (nNodes > ADDRMAN_GETADDR_MAX)
 478         nNodes = ADDRMAN_GETADDR_MAX;
 479
 480     // gather a list of random nodes, skipping those of low quality
 481     for (unsigned int n = 0; n < vRandom.size(); n++) {
 482         if (vAddr.size() >= nNodes)
 483             break;
 484
 485         int nRndPos = RandomInt(vRandom.size() - n) + n;
 486         SwapRandom(n, nRndPos);
 487         assert(mapInfo.count(vRandom[n]) == 1);
 488
 489         const CAddrInfo& ai = mapInfo[vRandom[n]];
 490         if (!ai.IsTerrible())
 491             vAddr.push_back(ai);
 492     }
 493 }
 494
 495 void CAddrMan::Connected_(const CService& addr, int64_t nTime)
 496 {
 497     CAddrInfo* pinfo = Find(addr);
 498
 499     // if not found, bail out
 500     if (!pinfo)
 501         return;
 502
 503     CAddrInfo& info = *pinfo;
 504
 505     // check whether we are talking about the exact same CService (including same port)
 506     if (info != addr)
 507         return;
 508
 509     // update info
 510     int64_t nUpdateInterval = 20 * 60;
 511     if (nTime - info.nTime > nUpdateInterval)
 512         info.nTime = nTime;
 513 }
 514
 515 int CAddrMan::RandomInt(int nMax){
 516     return GetRandInt(nMax);
 517 }