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