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