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