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 = GetRandInt(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 && (GetRandInt(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     if (newOnly && nNew == 0)
 338         return CAddrInfo();
 339
 340     // Use a 50% chance for choosing between tried and new table entries.
 341     if (!newOnly &&
 342        (nTried > 0 && (nNew == 0 || GetRandInt(2) == 0))) {
 343         // use a tried node
 344         double fChanceFactor = 1.0;
 345         while (1) {
 346             int nKBucket = GetRandInt(ADDRMAN_TRIED_BUCKET_COUNT);
 347             int nKBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE);
 348             while (vvTried[nKBucket][nKBucketPos] == -1) {
 349                 nKBucket = (nKBucket + insecure_rand()) % ADDRMAN_TRIED_BUCKET_COUNT;
 350                 nKBucketPos = (nKBucketPos + insecure_rand()) % ADDRMAN_BUCKET_SIZE;
 351             }
 352             int nId = vvTried[nKBucket][nKBucketPos];
 353             assert(mapInfo.count(nId) == 1);
 354             CAddrInfo& info = mapInfo[nId];
 355             if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
 356                 return info;
 357             fChanceFactor *= 1.2;
 358         }
 359     } else {
 360         // use a new node
 361         double fChanceFactor = 1.0;
 362         while (1) {
 363             int nUBucket = GetRandInt(ADDRMAN_NEW_BUCKET_COUNT);
 364             int nUBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE);
 365             while (vvNew[nUBucket][nUBucketPos] == -1) {
 366                 nUBucket = (nUBucket + insecure_rand()) % ADDRMAN_NEW_BUCKET_COUNT;
 367                 nUBucketPos = (nUBucketPos + insecure_rand()) % ADDRMAN_BUCKET_SIZE;
 368             }
 369             int nId = vvNew[nUBucket][nUBucketPos];
 370             assert(mapInfo.count(nId) == 1);
 371             CAddrInfo& info = mapInfo[nId];
 372             if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
 373                 return info;
 374             fChanceFactor *= 1.2;
 375         }
 376     }
 377 }
 378
 379 #ifdef DEBUG_ADDRMAN
 380 int CAddrMan::Check_()
 381 {
 382     std::set<int> setTried;
 383     std::map<int, int> mapNew;
 384
 385     if (vRandom.size() != nTried + nNew)
 386         return -7;
 387
 388     for (std::map<int, CAddrInfo>::iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
 389         int n = (*it).first;
 390         CAddrInfo& info = (*it).second;
 391         if (info.fInTried) {
 392             if (!info.nLastSuccess)
 393                 return -1;
 394             if (info.nRefCount)
 395                 return -2;
 396             setTried.insert(n);
 397         } else {
 398             if (info.nRefCount < 0 || info.nRefCount > ADDRMAN_NEW_BUCKETS_PER_ADDRESS)
 399                 return -3;
 400             if (!info.nRefCount)
 401                 return -4;
 402             mapNew[n] = info.nRefCount;
 403         }
 404         if (mapAddr[info] != n)
 405             return -5;
 406         if (info.nRandomPos < 0 || info.nRandomPos >= vRandom.size() || vRandom[info.nRandomPos] != n)
 407             return -14;
 408         if (info.nLastTry < 0)
 409             return -6;
 410         if (info.nLastSuccess < 0)
 411             return -8;
 412     }
 413
 414     if (setTried.size() != nTried)
 415         return -9;
 416     if (mapNew.size() != nNew)
 417         return -10;
 418
 419     for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) {
 420         for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 421              if (vvTried[n][i] != -1) {
 422                  if (!setTried.count(vvTried[n][i]))
 423                      return -11;
 424                  if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n)
 425                      return -17;
 426                  if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i)
 427                      return -18;
 428                  setTried.erase(vvTried[n][i]);
 429              }
 430         }
 431     }
 432
 433     for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
 434         for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
 435             if (vvNew[n][i] != -1) {
 436                 if (!mapNew.count(vvNew[n][i]))
 437                     return -12;
 438                 if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i)
 439                     return -19;
 440                 if (--mapNew[vvNew[n][i]] == 0)
 441                     mapNew.erase(vvNew[n][i]);
 442             }
 443         }
 444     }
 445
 446     if (setTried.size())
 447         return -13;
 448     if (mapNew.size())
 449         return -15;
 450     if (nKey.IsNull())
 451         return -16;
 452
 453     return 0;
 454 }
 455 #endif
 456
 457 void CAddrMan::GetAddr_(std::vector<CAddress>& vAddr)
 458 {
 459     unsigned int nNodes = ADDRMAN_GETADDR_MAX_PCT * vRandom.size() / 100;
 460     if (nNodes > ADDRMAN_GETADDR_MAX)
 461         nNodes = ADDRMAN_GETADDR_MAX;
 462
 463     // gather a list of random nodes, skipping those of low quality
 464     for (unsigned int n = 0; n < vRandom.size(); n++) {
 465         if (vAddr.size() >= nNodes)
 466             break;
 467
 468         int nRndPos = GetRandInt(vRandom.size() - n) + n;
 469         SwapRandom(n, nRndPos);
 470         assert(mapInfo.count(vRandom[n]) == 1);
 471
 472         const CAddrInfo& ai = mapInfo[vRandom[n]];
 473         if (!ai.IsTerrible())
 474             vAddr.push_back(ai);
 475     }
 476 }
 477
 478 void CAddrMan::Connected_(const CService& addr, int64_t nTime)
 479 {
 480     CAddrInfo* pinfo = Find(addr);
 481
 482     // if not found, bail out
 483     if (!pinfo)
 484         return;
 485
 486     CAddrInfo& info = *pinfo;
 487
 488     // check whether we are talking about the exact same CService (including same port)
 489     if (info != addr)
 490         return;
 491
 492     // update info
 493     int64_t nUpdateInterval = 20 * 60;
 494     if (nTime - info.nTime > nUpdateInterval)
 495         info.nTime = nTime;
 496 }