src/addrman.cpp

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