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     CAddrInfo* pinfo = Find(addr, &nId);
 201
 202     // if not found, bail out
 203     if (!pinfo)
 204         return;
 205
 206     CAddrInfo& info = *pinfo;
 207
 208     // check whether we are talking about the exact same CService (including same port)
 209     if (info != addr)
 210         return;
 211
 212     // update info
 213     info.nLastSuccess = nTime;
 214     info.nLastTry = nTime;
 215     info.nAttempts = 0;
 216     // nTime is not updated here, to avoid leaking information about
 217     // currently-connected peers.
 218
 219     // if it is already in the tried set, don't do anything else
 220     if (info.fInTried)
 221         return;
 222
 223     // find a bucket it is in now
 224     int nRnd = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
 225     int nUBucket = -1;
 226     for (unsigned int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
 227         int nB = (n + nRnd) % ADDRMAN_NEW_BUCKET_COUNT;
 228         int nBpos = info.GetBucketPosition(nKey, true, nB);
 229         if (vvNew[nB][nBpos] == nId) {
 230             nUBucket = nB;
 231             break;
 232         }
 233     }
 234
 235     // if no bucket is found, something bad happened;
 236     // TODO: maybe re-add the node, but for now, just bail out
 237     if (nUBucket == -1)
 238         return;
 239
 240     LogPrint("addrman", "Moving %s to tried\n", addr.ToString());
 241
 242     // move nId to the tried tables
 243     MakeTried(info, nId);
 244 }
 245
 246 bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty)
 247 {
 248     if (!addr.IsRoutable())
 249         return false;
 250
 251     bool fNew = false;
 252     int nId;
 253     CAddrInfo* pinfo = Find(addr, &nId);
 254
 255     if (pinfo) {
 256         // periodically update nTime
 257         bool fCurrentlyOnline = (GetAdjustedTime() - addr.nTime < 24 * 60 * 60);
 258         int64_t nUpdateInterval = (fCurrentlyOnline ? 60 * 60 : 24 * 60 * 60);
 259         if (addr.nTime && (!pinfo->nTime || pinfo->nTime < addr.nTime - nUpdateInterval - nTimePenalty))
 260             pinfo->nTime = std::max((int64_t)0, addr.nTime - nTimePenalty);
 261
 262         // add services
 263         pinfo->nServices |= addr.nServices;
 264
 265         // do not update if no new information is present
 266         if (!addr.nTime || (pinfo->nTime && addr.nTime <= pinfo->nTime))
 267             return false;
 268
 269         // do not update if the entry was already in the "tried" table
 270         if (pinfo->fInTried)
 271             return false;
 272
 273         // do not update if the max reference count is reached
 274         if (pinfo->nRefCount == ADDRMAN_NEW_BUCKETS_PER_ADDRESS)
 275             return false;
 276
 277         // stochastic test: previous nRefCount == N: 2^N times harder to increase it
 278         int nFactor = 1;
 279         for (int n = 0; n < pinfo->nRefCount; n++)
 280             nFactor *= 2;
 281         if (nFactor > 1 && (RandomInt(nFactor) != 0))
 282             return false;
 283     } else {
 284         pinfo = Create(addr, source, &nId);
 285         pinfo->nTime = std::max((int64_t)0, (int64_t)pinfo->nTime - nTimePenalty);
 286         nNew++;
 287         fNew = true;
 288     }
 289
 290     int nUBucket = pinfo->GetNewBucket(nKey, source);
 291     int nUBucketPos = pinfo->GetBucketPosition(nKey, true, nUBucket);
 292     if (vvNew[nUBucket][nUBucketPos] != nId) {
 293         bool fInsert = vvNew[nUBucket][nUBucketPos] == -1;
 294         if (!fInsert) {
 295             CAddrInfo& infoExisting = mapInfo[vvNew[nUBucket][nUBucketPos]];
 296             if (infoExisting.IsTerrible() || (infoExisting.nRefCount > 1 && pinfo->nRefCount == 0)) {
 297                 // Overwrite the existing new table entry.
 298                 fInsert = true;
 299             }
 300         }
 301         if (fInsert) {
 302             ClearNew(nUBucket, nUBucketPos);
 303             pinfo->nRefCount++;
 304             vvNew[nUBucket][nUBucketPos] = nId;
 305         } else {
 306             if (pinfo->nRefCount == 0) {
 307                 Delete(nId);
 308             }
 309         }
 310     }
 311     return fNew;
 312 }
 313
 314 void CAddrMan::Attempt_(const CService& addr, int64_t nTime)
 315 {
 316     CAddrInfo* pinfo = Find(addr);
 317
 318     // if not found, bail out
 319     if (!pinfo)
 320         return;
 321
 322     CAddrInfo& info = *pinfo;
 323
 324     // check whether we are talking about the exact same CService (including same port)
 325     if (info != addr)
 326         return;
 327
 328     // update info
 329     info.nLastTry = nTime;
 330     info.nAttempts++;
 331 }
 332
 333 CAddrInfo CAddrMan::Select_(bool newOnly)
 334 {
 335     if (size() == 0)
 336         return CAddrInfo();
 337
 338     if (newOnly && nNew == 0)
 339         return CAddrInfo();
 340
 341     // Use a 50% chance for choosing between tried and new table entries.
 342     if (!newOnly &&
 343        (nTried > 0 && (nNew == 0 || RandomInt(2) == 0))) {
 344         // use a tried node
 345         double fChanceFactor = 1.0;
 346         while (1) {
 347             int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT);
 348             int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
 349             while (vvTried[nKBucket][nKBucketPos] == -1) {
 350                 nKBucket = (nKBucket + insecure_rand()) % ADDRMAN_TRIED_BUCKET_COUNT;
 351                 nKBucketPos = (nKBucketPos + insecure_rand()) % ADDRMAN_BUCKET_SIZE;
 352             }
 353             int nId = vvTried[nKBucket][nKBucketPos];
 354             assert(mapInfo.count(nId) == 1);
 355             CAddrInfo& info = mapInfo[nId];
 356             if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
 357                 return info;
 358             fChanceFactor *= 1.2;
 359         }
 360     } else {
 361         // use a new node
 362         double fChanceFactor = 1.0;
 363         while (1) {
 364             int nUBucket = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
 365             int nUBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
 366             while (vvNew[nUBucket][nUBucketPos] == -1) {
 367                 nUBucket = (nUBucket + insecure_rand()) % ADDRMAN_NEW_BUCKET_COUNT;
 368                 nUBucketPos = (nUBucketPos + insecure_rand()) % ADDRMAN_BUCKET_SIZE;
 369             }
 370             int nId = vvNew[nUBucket][nUBucketPos];
 371             assert(mapInfo.count(nId) == 1);
 372             CAddrInfo& info = mapInfo[nId];
 373             if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
 374                 return info;
 375             fChanceFactor *= 1.2;
 376         }
 377     }
 378 }
 379
 380 #ifdef DEBUG_ADDRMAN
 381 int CAddrMan::Check_()
 382 {
 383     std::set<int> setTried;
 384     std::map<int, int> mapNew;
 385
 386     if (vRandom.size() != nTried + nNew)
 387         return -7;
 388
 389     for (std::map<int, CAddrInfo>::iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
 390         int n = (*it).first;
 391         CAddrInfo& info = (*it).second;
 392         if (info.fInTried) {
 393             if (!info.nLastSuccess)
 394                 return -1;
 395             if (info.nRefCount)
 396                 return -2;
 397             setTried.insert(n);
 398         } else {
 399             if (info.nRefCount < 0 || info.nRefCount > ADDRMAN_NEW_BUCKETS_PER_ADDRESS)
 400                 return -3;
 401             if (!info.nRefCount)
 402                 return -4;
 403             mapNew[n] = info.nRefCount;
 404         }
 405         if (mapAddr[info] != n)
 406             return -5;
 407         if (info.nRandomPos < 0 || info.nRandomPos >= vRandom.size() || vRandom[info.nRandomPos] != n)
 408             return -14;
 409         if (info.nLastTry < 0)
 410             return -6;
 411         if (info.nLastSuccess < 0)
 412             return -8;
 413     }
 414
 415     if (setTried.size() != nTried)
 416         return -9;
 417     if (mapNew.size() != nNew)
 418         return -10;
 419
 420     for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) {
 421         for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 422              if (vvTried[n][i] != -1) {
 423                  if (!setTried.count(vvTried[n][i]))
 424                      return -11;
 425                  if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n)
 426                      return -17;
 427                  if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i)
 428                      return -18;
 429                  setTried.erase(vvTried[n][i]);
 430              }
 431         }
 432     }
 433
 434     for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
 435         for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 436             if (vvNew[n][i] != -1) {
 437                 if (!mapNew.count(vvNew[n][i]))
 438                     return -12;
 439                 if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i)
 440                     return -19;
 441                 if (--mapNew[vvNew[n][i]] == 0)
 442                     mapNew.erase(vvNew[n][i]);
 443             }
 444         }
 445     }
 446
 447     if (setTried.size())
 448         return -13;
 449     if (mapNew.size())
 450         return -15;
 451     if (nKey.IsNull())
 452         return -16;
 453
 454     return 0;
 455 }
 456 #endif
 457
 458 void CAddrMan::GetAddr_(std::vector<CAddress>& vAddr)
 459 {
 460     unsigned int nNodes = ADDRMAN_GETADDR_MAX_PCT * vRandom.size() / 100;
 461     if (nNodes > ADDRMAN_GETADDR_MAX)
 462         nNodes = ADDRMAN_GETADDR_MAX;
 463
 464     // gather a list of random nodes, skipping those of low quality
 465     for (unsigned int n = 0; n < vRandom.size(); n++) {
 466         if (vAddr.size() >= nNodes)
 467             break;
 468
 469         int nRndPos = RandomInt(vRandom.size() - n) + n;
 470         SwapRandom(n, nRndPos);
 471         assert(mapInfo.count(vRandom[n]) == 1);
 472
 473         const CAddrInfo& ai = mapInfo[vRandom[n]];
 474         if (!ai.IsTerrible())
 475             vAddr.push_back(ai);
 476     }
 477 }
 478
 479 void CAddrMan::Connected_(const CService& addr, int64_t nTime)
 480 {
 481     CAddrInfo* pinfo = Find(addr);
 482
 483     // if not found, bail out
 484     if (!pinfo)
 485         return;
 486
 487     CAddrInfo& info = *pinfo;
 488
 489     // check whether we are talking about the exact same CService (including same port)
 490     if (info != addr)
 491         return;
 492
 493     // update info
 494     int64_t nUpdateInterval = 20 * 60;
 495     if (nTime - info.nTime > nUpdateInterval)
 496         info.nTime = nTime;
 497 }
 498
 499 int CAddrMan::RandomInt(int nMax){
 500     return GetRandInt(nMax);
 501 }