You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

addrman.cpp 16KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523
  1. // Copyright (c) 2012 Pieter Wuille
  2. // Copyright (c) 2012-2016 The Starwels developers
  3. // Distributed under the MIT software license, see the accompanying
  4. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5. #include "addrman.h"
  6. #include "hash.h"
  7. #include "serialize.h"
  8. #include "streams.h"
  9. int CAddrInfo::GetTriedBucket(const uint256& nKey) const
  10. {
  11. uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetKey()).GetHash().GetCheapHash();
  12. uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP)).GetHash().GetCheapHash();
  13. return hash2 % ADDRMAN_TRIED_BUCKET_COUNT;
  14. }
  15. int CAddrInfo::GetNewBucket(const uint256& nKey, const CNetAddr& src) const
  16. {
  17. std::vector<unsigned char> vchSourceGroupKey = src.GetGroup();
  18. uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << vchSourceGroupKey).GetHash().GetCheapHash();
  19. uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP)).GetHash().GetCheapHash();
  20. return hash2 % ADDRMAN_NEW_BUCKET_COUNT;
  21. }
  22. int CAddrInfo::GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const
  23. {
  24. uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << (fNew ? 'N' : 'K') << nBucket << GetKey()).GetHash().GetCheapHash();
  25. return hash1 % ADDRMAN_BUCKET_SIZE;
  26. }
  27. bool CAddrInfo::IsTerrible(int64_t nNow) const
  28. {
  29. if (nLastTry && nLastTry >= nNow - 60) // never remove things tried in the last minute
  30. return false;
  31. if (nTime > nNow + 10 * 60) // came in a flying DeLorean
  32. return true;
  33. if (nTime == 0 || nNow - nTime > ADDRMAN_HORIZON_DAYS * 24 * 60 * 60) // not seen in recent history
  34. return true;
  35. if (nLastSuccess == 0 && nAttempts >= ADDRMAN_RETRIES) // tried N times and never a success
  36. return true;
  37. if (nNow - nLastSuccess > ADDRMAN_MIN_FAIL_DAYS * 24 * 60 * 60 && nAttempts >= ADDRMAN_MAX_FAILURES) // N successive failures in the last week
  38. return true;
  39. return false;
  40. }
  41. double CAddrInfo::GetChance(int64_t nNow) const
  42. {
  43. double fChance = 1.0;
  44. int64_t nSinceLastTry = std::max<int64_t>(nNow - nLastTry, 0);
  45. // deprioritize very recent attempts away
  46. if (nSinceLastTry < 60 * 10)
  47. fChance *= 0.01;
  48. // deprioritize 66% after each failed attempt, but at most 1/28th to avoid the search taking forever or overly penalizing outages.
  49. fChance *= pow(0.66, std::min(nAttempts, 8));
  50. return fChance;
  51. }
  52. CAddrInfo* CAddrMan::Find(const CNetAddr& addr, int* pnId)
  53. {
  54. std::map<CNetAddr, int>::iterator it = mapAddr.find(addr);
  55. if (it == mapAddr.end())
  56. return nullptr;
  57. if (pnId)
  58. *pnId = (*it).second;
  59. std::map<int, CAddrInfo>::iterator it2 = mapInfo.find((*it).second);
  60. if (it2 != mapInfo.end())
  61. return &(*it2).second;
  62. return nullptr;
  63. }
  64. CAddrInfo* CAddrMan::Create(const CAddress& addr, const CNetAddr& addrSource, int* pnId)
  65. {
  66. int nId = nIdCount++;
  67. mapInfo[nId] = CAddrInfo(addr, addrSource);
  68. mapAddr[addr] = nId;
  69. mapInfo[nId].nRandomPos = vRandom.size();
  70. vRandom.push_back(nId);
  71. if (pnId)
  72. *pnId = nId;
  73. return &mapInfo[nId];
  74. }
  75. void CAddrMan::SwapRandom(unsigned int nRndPos1, unsigned int nRndPos2)
  76. {
  77. if (nRndPos1 == nRndPos2)
  78. return;
  79. assert(nRndPos1 < vRandom.size() && nRndPos2 < vRandom.size());
  80. int nId1 = vRandom[nRndPos1];
  81. int nId2 = vRandom[nRndPos2];
  82. assert(mapInfo.count(nId1) == 1);
  83. assert(mapInfo.count(nId2) == 1);
  84. mapInfo[nId1].nRandomPos = nRndPos2;
  85. mapInfo[nId2].nRandomPos = nRndPos1;
  86. vRandom[nRndPos1] = nId2;
  87. vRandom[nRndPos2] = nId1;
  88. }
  89. void CAddrMan::Delete(int nId)
  90. {
  91. assert(mapInfo.count(nId) != 0);
  92. CAddrInfo& info = mapInfo[nId];
  93. assert(!info.fInTried);
  94. assert(info.nRefCount == 0);
  95. SwapRandom(info.nRandomPos, vRandom.size() - 1);
  96. vRandom.pop_back();
  97. mapAddr.erase(info);
  98. mapInfo.erase(nId);
  99. nNew--;
  100. }
  101. void CAddrMan::ClearNew(int nUBucket, int nUBucketPos)
  102. {
  103. // if there is an entry in the specified bucket, delete it.
  104. if (vvNew[nUBucket][nUBucketPos] != -1) {
  105. int nIdDelete = vvNew[nUBucket][nUBucketPos];
  106. CAddrInfo& infoDelete = mapInfo[nIdDelete];
  107. assert(infoDelete.nRefCount > 0);
  108. infoDelete.nRefCount--;
  109. vvNew[nUBucket][nUBucketPos] = -1;
  110. if (infoDelete.nRefCount == 0) {
  111. Delete(nIdDelete);
  112. }
  113. }
  114. }
  115. void CAddrMan::MakeTried(CAddrInfo& info, int nId)
  116. {
  117. // remove the entry from all new buckets
  118. for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
  119. int pos = info.GetBucketPosition(nKey, true, bucket);
  120. if (vvNew[bucket][pos] == nId) {
  121. vvNew[bucket][pos] = -1;
  122. info.nRefCount--;
  123. }
  124. }
  125. nNew--;
  126. assert(info.nRefCount == 0);
  127. // which tried bucket to move the entry to
  128. int nKBucket = info.GetTriedBucket(nKey);
  129. int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket);
  130. // first make space to add it (the existing tried entry there is moved to new, deleting whatever is there).
  131. if (vvTried[nKBucket][nKBucketPos] != -1) {
  132. // find an item to evict
  133. int nIdEvict = vvTried[nKBucket][nKBucketPos];
  134. assert(mapInfo.count(nIdEvict) == 1);
  135. CAddrInfo& infoOld = mapInfo[nIdEvict];
  136. // Remove the to-be-evicted item from the tried set.
  137. infoOld.fInTried = false;
  138. vvTried[nKBucket][nKBucketPos] = -1;
  139. nTried--;
  140. // find which new bucket it belongs to
  141. int nUBucket = infoOld.GetNewBucket(nKey);
  142. int nUBucketPos = infoOld.GetBucketPosition(nKey, true, nUBucket);
  143. ClearNew(nUBucket, nUBucketPos);
  144. assert(vvNew[nUBucket][nUBucketPos] == -1);
  145. // Enter it into the new set again.
  146. infoOld.nRefCount = 1;
  147. vvNew[nUBucket][nUBucketPos] = nIdEvict;
  148. nNew++;
  149. }
  150. assert(vvTried[nKBucket][nKBucketPos] == -1);
  151. vvTried[nKBucket][nKBucketPos] = nId;
  152. nTried++;
  153. info.fInTried = true;
  154. }
  155. void CAddrMan::Good_(const CService& addr, int64_t nTime)
  156. {
  157. int nId;
  158. nLastGood = nTime;
  159. CAddrInfo* pinfo = Find(addr, &nId);
  160. // if not found, bail out
  161. if (!pinfo)
  162. return;
  163. CAddrInfo& info = *pinfo;
  164. // check whether we are talking about the exact same CService (including same port)
  165. if (info != addr)
  166. return;
  167. // update info
  168. info.nLastSuccess = nTime;
  169. info.nLastTry = nTime;
  170. info.nAttempts = 0;
  171. // nTime is not updated here, to avoid leaking information about
  172. // currently-connected peers.
  173. // if it is already in the tried set, don't do anything else
  174. if (info.fInTried)
  175. return;
  176. // find a bucket it is in now
  177. int nRnd = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
  178. int nUBucket = -1;
  179. for (unsigned int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
  180. int nB = (n + nRnd) % ADDRMAN_NEW_BUCKET_COUNT;
  181. int nBpos = info.GetBucketPosition(nKey, true, nB);
  182. if (vvNew[nB][nBpos] == nId) {
  183. nUBucket = nB;
  184. break;
  185. }
  186. }
  187. // if no bucket is found, something bad happened;
  188. // TODO: maybe re-add the node, but for now, just bail out
  189. if (nUBucket == -1)
  190. return;
  191. LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString());
  192. // move nId to the tried tables
  193. MakeTried(info, nId);
  194. }
  195. bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty)
  196. {
  197. if (!addr.IsRoutable())
  198. return false;
  199. bool fNew = false;
  200. int nId;
  201. CAddrInfo* pinfo = Find(addr, &nId);
  202. // Do not set a penalty for a source's self-announcement
  203. if (addr == source) {
  204. nTimePenalty = 0;
  205. }
  206. if (pinfo) {
  207. // periodically update nTime
  208. bool fCurrentlyOnline = (GetAdjustedTime() - addr.nTime < 24 * 60 * 60);
  209. int64_t nUpdateInterval = (fCurrentlyOnline ? 60 * 60 : 24 * 60 * 60);
  210. if (addr.nTime && (!pinfo->nTime || pinfo->nTime < addr.nTime - nUpdateInterval - nTimePenalty))
  211. pinfo->nTime = std::max((int64_t)0, addr.nTime - nTimePenalty);
  212. // add services
  213. pinfo->nServices = ServiceFlags(pinfo->nServices | addr.nServices);
  214. // do not update if no new information is present
  215. if (!addr.nTime || (pinfo->nTime && addr.nTime <= pinfo->nTime))
  216. return false;
  217. // do not update if the entry was already in the "tried" table
  218. if (pinfo->fInTried)
  219. return false;
  220. // do not update if the max reference count is reached
  221. if (pinfo->nRefCount == ADDRMAN_NEW_BUCKETS_PER_ADDRESS)
  222. return false;
  223. // stochastic test: previous nRefCount == N: 2^N times harder to increase it
  224. int nFactor = 1;
  225. for (int n = 0; n < pinfo->nRefCount; n++)
  226. nFactor *= 2;
  227. if (nFactor > 1 && (RandomInt(nFactor) != 0))
  228. return false;
  229. } else {
  230. pinfo = Create(addr, source, &nId);
  231. pinfo->nTime = std::max((int64_t)0, (int64_t)pinfo->nTime - nTimePenalty);
  232. nNew++;
  233. fNew = true;
  234. }
  235. int nUBucket = pinfo->GetNewBucket(nKey, source);
  236. int nUBucketPos = pinfo->GetBucketPosition(nKey, true, nUBucket);
  237. if (vvNew[nUBucket][nUBucketPos] != nId) {
  238. bool fInsert = vvNew[nUBucket][nUBucketPos] == -1;
  239. if (!fInsert) {
  240. CAddrInfo& infoExisting = mapInfo[vvNew[nUBucket][nUBucketPos]];
  241. if (infoExisting.IsTerrible() || (infoExisting.nRefCount > 1 && pinfo->nRefCount == 0)) {
  242. // Overwrite the existing new table entry.
  243. fInsert = true;
  244. }
  245. }
  246. if (fInsert) {
  247. ClearNew(nUBucket, nUBucketPos);
  248. pinfo->nRefCount++;
  249. vvNew[nUBucket][nUBucketPos] = nId;
  250. } else {
  251. if (pinfo->nRefCount == 0) {
  252. Delete(nId);
  253. }
  254. }
  255. }
  256. return fNew;
  257. }
  258. void CAddrMan::Attempt_(const CService& addr, bool fCountFailure, int64_t nTime)
  259. {
  260. CAddrInfo* pinfo = Find(addr);
  261. // if not found, bail out
  262. if (!pinfo)
  263. return;
  264. CAddrInfo& info = *pinfo;
  265. // check whether we are talking about the exact same CService (including same port)
  266. if (info != addr)
  267. return;
  268. // update info
  269. info.nLastTry = nTime;
  270. if (fCountFailure && info.nLastCountAttempt < nLastGood) {
  271. info.nLastCountAttempt = nTime;
  272. info.nAttempts++;
  273. }
  274. }
  275. CAddrInfo CAddrMan::Select_(bool newOnly)
  276. {
  277. if (size() == 0)
  278. return CAddrInfo();
  279. if (newOnly && nNew == 0)
  280. return CAddrInfo();
  281. // Use a 50% chance for choosing between tried and new table entries.
  282. if (!newOnly &&
  283. (nTried > 0 && (nNew == 0 || RandomInt(2) == 0))) {
  284. // use a tried node
  285. double fChanceFactor = 1.0;
  286. while (1) {
  287. int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT);
  288. int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
  289. while (vvTried[nKBucket][nKBucketPos] == -1) {
  290. nKBucket = (nKBucket + insecure_rand.randbits(ADDRMAN_TRIED_BUCKET_COUNT_LOG2)) % ADDRMAN_TRIED_BUCKET_COUNT;
  291. nKBucketPos = (nKBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE;
  292. }
  293. int nId = vvTried[nKBucket][nKBucketPos];
  294. assert(mapInfo.count(nId) == 1);
  295. CAddrInfo& info = mapInfo[nId];
  296. if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
  297. return info;
  298. fChanceFactor *= 1.2;
  299. }
  300. } else {
  301. // use a new node
  302. double fChanceFactor = 1.0;
  303. while (1) {
  304. int nUBucket = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
  305. int nUBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
  306. while (vvNew[nUBucket][nUBucketPos] == -1) {
  307. nUBucket = (nUBucket + insecure_rand.randbits(ADDRMAN_NEW_BUCKET_COUNT_LOG2)) % ADDRMAN_NEW_BUCKET_COUNT;
  308. nUBucketPos = (nUBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE;
  309. }
  310. int nId = vvNew[nUBucket][nUBucketPos];
  311. assert(mapInfo.count(nId) == 1);
  312. CAddrInfo& info = mapInfo[nId];
  313. if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
  314. return info;
  315. fChanceFactor *= 1.2;
  316. }
  317. }
  318. }
  319. #ifdef DEBUG_ADDRMAN
  320. int CAddrMan::Check_()
  321. {
  322. std::set<int> setTried;
  323. std::map<int, int> mapNew;
  324. if (vRandom.size() != nTried + nNew)
  325. return -7;
  326. for (std::map<int, CAddrInfo>::iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
  327. int n = (*it).first;
  328. CAddrInfo& info = (*it).second;
  329. if (info.fInTried) {
  330. if (!info.nLastSuccess)
  331. return -1;
  332. if (info.nRefCount)
  333. return -2;
  334. setTried.insert(n);
  335. } else {
  336. if (info.nRefCount < 0 || info.nRefCount > ADDRMAN_NEW_BUCKETS_PER_ADDRESS)
  337. return -3;
  338. if (!info.nRefCount)
  339. return -4;
  340. mapNew[n] = info.nRefCount;
  341. }
  342. if (mapAddr[info] != n)
  343. return -5;
  344. if (info.nRandomPos < 0 || info.nRandomPos >= vRandom.size() || vRandom[info.nRandomPos] != n)
  345. return -14;
  346. if (info.nLastTry < 0)
  347. return -6;
  348. if (info.nLastSuccess < 0)
  349. return -8;
  350. }
  351. if (setTried.size() != nTried)
  352. return -9;
  353. if (mapNew.size() != nNew)
  354. return -10;
  355. for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) {
  356. for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
  357. if (vvTried[n][i] != -1) {
  358. if (!setTried.count(vvTried[n][i]))
  359. return -11;
  360. if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n)
  361. return -17;
  362. if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i)
  363. return -18;
  364. setTried.erase(vvTried[n][i]);
  365. }
  366. }
  367. }
  368. for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
  369. for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
  370. if (vvNew[n][i] != -1) {
  371. if (!mapNew.count(vvNew[n][i]))
  372. return -12;
  373. if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i)
  374. return -19;
  375. if (--mapNew[vvNew[n][i]] == 0)
  376. mapNew.erase(vvNew[n][i]);
  377. }
  378. }
  379. }
  380. if (setTried.size())
  381. return -13;
  382. if (mapNew.size())
  383. return -15;
  384. if (nKey.IsNull())
  385. return -16;
  386. return 0;
  387. }
  388. #endif
  389. void CAddrMan::GetAddr_(std::vector<CAddress>& vAddr)
  390. {
  391. unsigned int nNodes = ADDRMAN_GETADDR_MAX_PCT * vRandom.size() / 100;
  392. if (nNodes > ADDRMAN_GETADDR_MAX)
  393. nNodes = ADDRMAN_GETADDR_MAX;
  394. // gather a list of random nodes, skipping those of low quality
  395. for (unsigned int n = 0; n < vRandom.size(); n++) {
  396. if (vAddr.size() >= nNodes)
  397. break;
  398. int nRndPos = RandomInt(vRandom.size() - n) + n;
  399. SwapRandom(n, nRndPos);
  400. assert(mapInfo.count(vRandom[n]) == 1);
  401. const CAddrInfo& ai = mapInfo[vRandom[n]];
  402. if (!ai.IsTerrible())
  403. vAddr.push_back(ai);
  404. }
  405. }
  406. void CAddrMan::Connected_(const CService& addr, int64_t nTime)
  407. {
  408. CAddrInfo* pinfo = Find(addr);
  409. // if not found, bail out
  410. if (!pinfo)
  411. return;
  412. CAddrInfo& info = *pinfo;
  413. // check whether we are talking about the exact same CService (including same port)
  414. if (info != addr)
  415. return;
  416. // update info
  417. int64_t nUpdateInterval = 20 * 60;
  418. if (nTime - info.nTime > nUpdateInterval)
  419. info.nTime = nTime;
  420. }
  421. void CAddrMan::SetServices_(const CService& addr, ServiceFlags nServices)
  422. {
  423. CAddrInfo* pinfo = Find(addr);
  424. // if not found, bail out
  425. if (!pinfo)
  426. return;
  427. CAddrInfo& info = *pinfo;
  428. // check whether we are talking about the exact same CService (including same port)
  429. if (info != addr)
  430. return;
  431. // update info
  432. info.nServices = nServices;
  433. }
  434. int CAddrMan::RandomInt(int nMax){
  435. return GetRandInt(nMax);
  436. }