src/addrman.cpp

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