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.h 19KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603
  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. #ifndef STARWELS_ADDRMAN_H
  6. #define STARWELS_ADDRMAN_H
  7. #include "netaddress.h"
  8. #include "protocol.h"
  9. #include "random.h"
  10. #include "sync.h"
  11. #include "timedata.h"
  12. #include "util.h"
  13. #include <map>
  14. #include <set>
  15. #include <stdint.h>
  16. #include <vector>
  17. /**
  18. * Extended statistics about a CAddress
  19. */
  20. class CAddrInfo : public CAddress
  21. {
  22. public:
  23. //! last try whatsoever by us (memory only)
  24. int64_t nLastTry;
  25. //! last counted attempt (memory only)
  26. int64_t nLastCountAttempt;
  27. private:
  28. //! where knowledge about this address first came from
  29. CNetAddr source;
  30. //! last successful connection by us
  31. int64_t nLastSuccess;
  32. //! connection attempts since last successful attempt
  33. int nAttempts;
  34. //! reference count in new sets (memory only)
  35. int nRefCount;
  36. //! in tried set? (memory only)
  37. bool fInTried;
  38. //! position in vRandom
  39. int nRandomPos;
  40. friend class CAddrMan;
  41. public:
  42. ADD_SERIALIZE_METHODS;
  43. template <typename Stream, typename Operation>
  44. inline void SerializationOp(Stream& s, Operation ser_action) {
  45. READWRITE(*(CAddress*)this);
  46. READWRITE(source);
  47. READWRITE(nLastSuccess);
  48. READWRITE(nAttempts);
  49. }
  50. void Init()
  51. {
  52. nLastSuccess = 0;
  53. nLastTry = 0;
  54. nLastCountAttempt = 0;
  55. nAttempts = 0;
  56. nRefCount = 0;
  57. fInTried = false;
  58. nRandomPos = -1;
  59. }
  60. CAddrInfo(const CAddress &addrIn, const CNetAddr &addrSource) : CAddress(addrIn), source(addrSource)
  61. {
  62. Init();
  63. }
  64. CAddrInfo() : CAddress(), source()
  65. {
  66. Init();
  67. }
  68. //! Calculate in which "tried" bucket this entry belongs
  69. int GetTriedBucket(const uint256 &nKey) const;
  70. //! Calculate in which "new" bucket this entry belongs, given a certain source
  71. int GetNewBucket(const uint256 &nKey, const CNetAddr& src) const;
  72. //! Calculate in which "new" bucket this entry belongs, using its default source
  73. int GetNewBucket(const uint256 &nKey) const
  74. {
  75. return GetNewBucket(nKey, source);
  76. }
  77. //! Calculate in which position of a bucket to store this entry.
  78. int GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const;
  79. //! Determine whether the statistics about this entry are bad enough so that it can just be deleted
  80. bool IsTerrible(int64_t nNow = GetAdjustedTime()) const;
  81. //! Calculate the relative chance this entry should be given when selecting nodes to connect to
  82. double GetChance(int64_t nNow = GetAdjustedTime()) const;
  83. };
  84. /** Stochastic address manager
  85. *
  86. * Design goals:
  87. * * Keep the address tables in-memory, and asynchronously dump the entire table to peers.dat.
  88. * * Make sure no (localized) attacker can fill the entire table with his nodes/addresses.
  89. *
  90. * To that end:
  91. * * Addresses are organized into buckets.
  92. * * Addresses that have not yet been tried go into 1024 "new" buckets.
  93. * * Based on the address range (/16 for IPv4) of the source of information, 64 buckets are selected at random.
  94. * * The actual bucket is chosen from one of these, based on the range in which the address itself is located.
  95. * * One single address can occur in up to 8 different buckets to increase selection chances for addresses that
  96. * are seen frequently. The chance for increasing this multiplicity decreases exponentially.
  97. * * When adding a new address to a full bucket, a randomly chosen entry (with a bias favoring less recently seen
  98. * ones) is removed from it first.
  99. * * Addresses of nodes that are known to be accessible go into 256 "tried" buckets.
  100. * * Each address range selects at random 8 of these buckets.
  101. * * The actual bucket is chosen from one of these, based on the full address.
  102. * * When adding a new good address to a full bucket, a randomly chosen entry (with a bias favoring less recently
  103. * tried ones) is evicted from it, back to the "new" buckets.
  104. * * Bucket selection is based on cryptographic hashing, using a randomly-generated 256-bit key, which should not
  105. * be observable by adversaries.
  106. * * Several indexes are kept for high performance. Defining DEBUG_ADDRMAN will introduce frequent (and expensive)
  107. * consistency checks for the entire data structure.
  108. */
  109. //! total number of buckets for tried addresses
  110. #define ADDRMAN_TRIED_BUCKET_COUNT_LOG2 8
  111. //! total number of buckets for new addresses
  112. #define ADDRMAN_NEW_BUCKET_COUNT_LOG2 10
  113. //! maximum allowed number of entries in buckets for new and tried addresses
  114. #define ADDRMAN_BUCKET_SIZE_LOG2 6
  115. //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
  116. #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8
  117. //! over how many buckets entries with new addresses originating from a single group are spread
  118. #define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 64
  119. //! in how many buckets for entries with new addresses a single address may occur
  120. #define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 8
  121. //! how old addresses can maximally be
  122. #define ADDRMAN_HORIZON_DAYS 30
  123. //! after how many failed attempts we give up on a new node
  124. #define ADDRMAN_RETRIES 3
  125. //! how many successive failures are allowed ...
  126. #define ADDRMAN_MAX_FAILURES 10
  127. //! ... in at least this many days
  128. #define ADDRMAN_MIN_FAIL_DAYS 7
  129. //! the maximum percentage of nodes to return in a getaddr call
  130. #define ADDRMAN_GETADDR_MAX_PCT 23
  131. //! the maximum number of nodes to return in a getaddr call
  132. #define ADDRMAN_GETADDR_MAX 2500
  133. //! Convenience
  134. #define ADDRMAN_TRIED_BUCKET_COUNT (1 << ADDRMAN_TRIED_BUCKET_COUNT_LOG2)
  135. #define ADDRMAN_NEW_BUCKET_COUNT (1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2)
  136. #define ADDRMAN_BUCKET_SIZE (1 << ADDRMAN_BUCKET_SIZE_LOG2)
  137. /**
  138. * Stochastical (IP) address manager
  139. */
  140. class CAddrMan
  141. {
  142. private:
  143. //! critical section to protect the inner data structures
  144. mutable CCriticalSection cs;
  145. //! last used nId
  146. int nIdCount;
  147. //! table with information about all nIds
  148. std::map<int, CAddrInfo> mapInfo;
  149. //! find an nId based on its network address
  150. std::map<CNetAddr, int> mapAddr;
  151. //! randomly-ordered vector of all nIds
  152. std::vector<int> vRandom;
  153. // number of "tried" entries
  154. int nTried;
  155. //! list of "tried" buckets
  156. int vvTried[ADDRMAN_TRIED_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE];
  157. //! number of (unique) "new" entries
  158. int nNew;
  159. //! list of "new" buckets
  160. int vvNew[ADDRMAN_NEW_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE];
  161. //! last time Good was called (memory only)
  162. int64_t nLastGood;
  163. protected:
  164. //! secret key to randomize bucket select with
  165. uint256 nKey;
  166. //! Source of random numbers for randomization in inner loops
  167. FastRandomContext insecure_rand;
  168. //! Find an entry.
  169. CAddrInfo* Find(const CNetAddr& addr, int *pnId = nullptr);
  170. //! find an entry, creating it if necessary.
  171. //! nTime and nServices of the found node are updated, if necessary.
  172. CAddrInfo* Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId = nullptr);
  173. //! Swap two elements in vRandom.
  174. void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2);
  175. //! Move an entry from the "new" table(s) to the "tried" table
  176. void MakeTried(CAddrInfo& info, int nId);
  177. //! Delete an entry. It must not be in tried, and have refcount 0.
  178. void Delete(int nId);
  179. //! Clear a position in a "new" table. This is the only place where entries are actually deleted.
  180. void ClearNew(int nUBucket, int nUBucketPos);
  181. //! Mark an entry "good", possibly moving it from "new" to "tried".
  182. void Good_(const CService &addr, int64_t nTime);
  183. //! Add an entry to the "new" table.
  184. bool Add_(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty);
  185. //! Mark an entry as attempted to connect.
  186. void Attempt_(const CService &addr, bool fCountFailure, int64_t nTime);
  187. //! Select an address to connect to, if newOnly is set to true, only the new table is selected from.
  188. CAddrInfo Select_(bool newOnly);
  189. //! Wraps GetRandInt to allow tests to override RandomInt and make it determinismistic.
  190. virtual int RandomInt(int nMax);
  191. #ifdef DEBUG_ADDRMAN
  192. //! Perform consistency check. Returns an error code or zero.
  193. int Check_();
  194. #endif
  195. //! Select several addresses at once.
  196. void GetAddr_(std::vector<CAddress> &vAddr);
  197. //! Mark an entry as currently-connected-to.
  198. void Connected_(const CService &addr, int64_t nTime);
  199. //! Update an entry's service bits.
  200. void SetServices_(const CService &addr, ServiceFlags nServices);
  201. public:
  202. /**
  203. * serialized format:
  204. * * version byte (currently 1)
  205. * * 0x20 + nKey (serialized as if it were a vector, for backward compatibility)
  206. * * nNew
  207. * * nTried
  208. * * number of "new" buckets XOR 2**30
  209. * * all nNew addrinfos in vvNew
  210. * * all nTried addrinfos in vvTried
  211. * * for each bucket:
  212. * * number of elements
  213. * * for each element: index
  214. *
  215. * 2**30 is xorred with the number of buckets to make addrman deserializer v0 detect it
  216. * as incompatible. This is necessary because it did not check the version number on
  217. * deserialization.
  218. *
  219. * Notice that vvTried, mapAddr and vVector are never encoded explicitly;
  220. * they are instead reconstructed from the other information.
  221. *
  222. * vvNew is serialized, but only used if ADDRMAN_UNKNOWN_BUCKET_COUNT didn't change,
  223. * otherwise it is reconstructed as well.
  224. *
  225. * This format is more complex, but significantly smaller (at most 1.5 MiB), and supports
  226. * changes to the ADDRMAN_ parameters without breaking the on-disk structure.
  227. *
  228. * We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has
  229. * very little in common.
  230. */
  231. template<typename Stream>
  232. void Serialize(Stream &s) const
  233. {
  234. LOCK(cs);
  235. unsigned char nVersion = 1;
  236. s << nVersion;
  237. s << ((unsigned char)32);
  238. s << nKey;
  239. s << nNew;
  240. s << nTried;
  241. int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30);
  242. s << nUBuckets;
  243. std::map<int, int> mapUnkIds;
  244. int nIds = 0;
  245. for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
  246. mapUnkIds[(*it).first] = nIds;
  247. const CAddrInfo &info = (*it).second;
  248. if (info.nRefCount) {
  249. assert(nIds != nNew); // this means nNew was wrong, oh ow
  250. s << info;
  251. nIds++;
  252. }
  253. }
  254. nIds = 0;
  255. for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) {
  256. const CAddrInfo &info = (*it).second;
  257. if (info.fInTried) {
  258. assert(nIds != nTried); // this means nTried was wrong, oh ow
  259. s << info;
  260. nIds++;
  261. }
  262. }
  263. for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
  264. int nSize = 0;
  265. for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
  266. if (vvNew[bucket][i] != -1)
  267. nSize++;
  268. }
  269. s << nSize;
  270. for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
  271. if (vvNew[bucket][i] != -1) {
  272. int nIndex = mapUnkIds[vvNew[bucket][i]];
  273. s << nIndex;
  274. }
  275. }
  276. }
  277. }
  278. template<typename Stream>
  279. void Unserialize(Stream& s)
  280. {
  281. LOCK(cs);
  282. Clear();
  283. unsigned char nVersion;
  284. s >> nVersion;
  285. unsigned char nKeySize;
  286. s >> nKeySize;
  287. if (nKeySize != 32) throw std::ios_base::failure("Incorrect keysize in addrman deserialization");
  288. s >> nKey;
  289. s >> nNew;
  290. s >> nTried;
  291. int nUBuckets = 0;
  292. s >> nUBuckets;
  293. if (nVersion != 0) {
  294. nUBuckets ^= (1 << 30);
  295. }
  296. if (nNew > ADDRMAN_NEW_BUCKET_COUNT * ADDRMAN_BUCKET_SIZE) {
  297. throw std::ios_base::failure("Corrupt CAddrMan serialization, nNew exceeds limit.");
  298. }
  299. if (nTried > ADDRMAN_TRIED_BUCKET_COUNT * ADDRMAN_BUCKET_SIZE) {
  300. throw std::ios_base::failure("Corrupt CAddrMan serialization, nTried exceeds limit.");
  301. }
  302. // Deserialize entries from the new table.
  303. for (int n = 0; n < nNew; n++) {
  304. CAddrInfo &info = mapInfo[n];
  305. s >> info;
  306. mapAddr[info] = n;
  307. info.nRandomPos = vRandom.size();
  308. vRandom.push_back(n);
  309. if (nVersion != 1 || nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) {
  310. // In case the new table data cannot be used (nVersion unknown, or bucket count wrong),
  311. // immediately try to give them a reference based on their primary source address.
  312. int nUBucket = info.GetNewBucket(nKey);
  313. int nUBucketPos = info.GetBucketPosition(nKey, true, nUBucket);
  314. if (vvNew[nUBucket][nUBucketPos] == -1) {
  315. vvNew[nUBucket][nUBucketPos] = n;
  316. info.nRefCount++;
  317. }
  318. }
  319. }
  320. nIdCount = nNew;
  321. // Deserialize entries from the tried table.
  322. int nLost = 0;
  323. for (int n = 0; n < nTried; n++) {
  324. CAddrInfo info;
  325. s >> info;
  326. int nKBucket = info.GetTriedBucket(nKey);
  327. int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket);
  328. if (vvTried[nKBucket][nKBucketPos] == -1) {
  329. info.nRandomPos = vRandom.size();
  330. info.fInTried = true;
  331. vRandom.push_back(nIdCount);
  332. mapInfo[nIdCount] = info;
  333. mapAddr[info] = nIdCount;
  334. vvTried[nKBucket][nKBucketPos] = nIdCount;
  335. nIdCount++;
  336. } else {
  337. nLost++;
  338. }
  339. }
  340. nTried -= nLost;
  341. // Deserialize positions in the new table (if possible).
  342. for (int bucket = 0; bucket < nUBuckets; bucket++) {
  343. int nSize = 0;
  344. s >> nSize;
  345. for (int n = 0; n < nSize; n++) {
  346. int nIndex = 0;
  347. s >> nIndex;
  348. if (nIndex >= 0 && nIndex < nNew) {
  349. CAddrInfo &info = mapInfo[nIndex];
  350. int nUBucketPos = info.GetBucketPosition(nKey, true, bucket);
  351. if (nVersion == 1 && nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && vvNew[bucket][nUBucketPos] == -1 && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) {
  352. info.nRefCount++;
  353. vvNew[bucket][nUBucketPos] = nIndex;
  354. }
  355. }
  356. }
  357. }
  358. // Prune new entries with refcount 0 (as a result of collisions).
  359. int nLostUnk = 0;
  360. for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); ) {
  361. if (it->second.fInTried == false && it->second.nRefCount == 0) {
  362. std::map<int, CAddrInfo>::const_iterator itCopy = it++;
  363. Delete(itCopy->first);
  364. nLostUnk++;
  365. } else {
  366. it++;
  367. }
  368. }
  369. if (nLost + nLostUnk > 0) {
  370. LogPrint(BCLog::ADDRMAN, "addrman lost %i new and %i tried addresses due to collisions\n", nLostUnk, nLost);
  371. }
  372. Check();
  373. }
  374. void Clear()
  375. {
  376. std::vector<int>().swap(vRandom);
  377. nKey = GetRandHash();
  378. for (size_t bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
  379. for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) {
  380. vvNew[bucket][entry] = -1;
  381. }
  382. }
  383. for (size_t bucket = 0; bucket < ADDRMAN_TRIED_BUCKET_COUNT; bucket++) {
  384. for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) {
  385. vvTried[bucket][entry] = -1;
  386. }
  387. }
  388. nIdCount = 0;
  389. nTried = 0;
  390. nNew = 0;
  391. nLastGood = 1; //Initially at 1 so that "never" is strictly worse.
  392. mapInfo.clear();
  393. mapAddr.clear();
  394. }
  395. CAddrMan()
  396. {
  397. Clear();
  398. }
  399. ~CAddrMan()
  400. {
  401. nKey.SetNull();
  402. }
  403. //! Return the number of (unique) addresses in all tables.
  404. size_t size() const
  405. {
  406. LOCK(cs); // TODO: Cache this in an atomic to avoid this overhead
  407. return vRandom.size();
  408. }
  409. //! Consistency check
  410. void Check()
  411. {
  412. #ifdef DEBUG_ADDRMAN
  413. {
  414. LOCK(cs);
  415. int err;
  416. if ((err=Check_()))
  417. LogPrintf("ADDRMAN CONSISTENCY CHECK FAILED!!! err=%i\n", err);
  418. }
  419. #endif
  420. }
  421. //! Add a single address.
  422. bool Add(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty = 0)
  423. {
  424. LOCK(cs);
  425. bool fRet = false;
  426. Check();
  427. fRet |= Add_(addr, source, nTimePenalty);
  428. Check();
  429. if (fRet) {
  430. LogPrint(BCLog::ADDRMAN, "Added %s from %s: %i tried, %i new\n", addr.ToStringIPPort(), source.ToString(), nTried, nNew);
  431. }
  432. return fRet;
  433. }
  434. //! Add multiple addresses.
  435. bool Add(const std::vector<CAddress> &vAddr, const CNetAddr& source, int64_t nTimePenalty = 0)
  436. {
  437. LOCK(cs);
  438. int nAdd = 0;
  439. Check();
  440. for (std::vector<CAddress>::const_iterator it = vAddr.begin(); it != vAddr.end(); it++)
  441. nAdd += Add_(*it, source, nTimePenalty) ? 1 : 0;
  442. Check();
  443. if (nAdd) {
  444. LogPrint(BCLog::ADDRMAN, "Added %i addresses from %s: %i tried, %i new\n", nAdd, source.ToString(), nTried, nNew);
  445. }
  446. return nAdd > 0;
  447. }
  448. //! Mark an entry as accessible.
  449. void Good(const CService &addr, int64_t nTime = GetAdjustedTime())
  450. {
  451. LOCK(cs);
  452. Check();
  453. Good_(addr, nTime);
  454. Check();
  455. }
  456. //! Mark an entry as connection attempted to.
  457. void Attempt(const CService &addr, bool fCountFailure, int64_t nTime = GetAdjustedTime())
  458. {
  459. LOCK(cs);
  460. Check();
  461. Attempt_(addr, fCountFailure, nTime);
  462. Check();
  463. }
  464. /**
  465. * Choose an address to connect to.
  466. */
  467. CAddrInfo Select(bool newOnly = false)
  468. {
  469. CAddrInfo addrRet;
  470. {
  471. LOCK(cs);
  472. Check();
  473. addrRet = Select_(newOnly);
  474. Check();
  475. }
  476. return addrRet;
  477. }
  478. //! Return a bunch of addresses, selected at random.
  479. std::vector<CAddress> GetAddr()
  480. {
  481. Check();
  482. std::vector<CAddress> vAddr;
  483. {
  484. LOCK(cs);
  485. GetAddr_(vAddr);
  486. }
  487. Check();
  488. return vAddr;
  489. }
  490. //! Mark an entry as currently-connected-to.
  491. void Connected(const CService &addr, int64_t nTime = GetAdjustedTime())
  492. {
  493. LOCK(cs);
  494. Check();
  495. Connected_(addr, nTime);
  496. Check();
  497. }
  498. void SetServices(const CService &addr, ServiceFlags nServices)
  499. {
  500. LOCK(cs);
  501. Check();
  502. SetServices_(addr, nServices);
  503. Check();
  504. }
  505. };
  506. #endif // STARWELS_ADDRMAN_H