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.
5 #ifndef BITCOIN_ADDRMAN_H
6 #define BITCOIN_ADDRMAN_H
21 * Extended statistics about a CAddress
23 class CAddrInfo
: public CAddress
26 //! last try whatsoever by us (memory only)
30 //! where knowledge about this address first came from
33 //! last successful connection by us
36 //! connection attempts since last successful attempt
39 //! reference count in new sets (memory only)
42 //! in tried set? (memory only)
45 //! position in vRandom
48 friend class CAddrMan
;
52 ADD_SERIALIZE_METHODS
;
54 template <typename Stream
, typename Operation
>
55 inline void SerializationOp(Stream
& s
, Operation ser_action
, int nType
, int nVersion
) {
56 READWRITE(*(CAddress
*)this);
58 READWRITE(nLastSuccess
);
72 CAddrInfo(const CAddress
&addrIn
, const CNetAddr
&addrSource
) : CAddress(addrIn
), source(addrSource
)
77 CAddrInfo() : CAddress(), source()
82 //! Calculate in which "tried" bucket this entry belongs
83 int GetTriedBucket(const uint256
&nKey
) const;
85 //! Calculate in which "new" bucket this entry belongs, given a certain source
86 int GetNewBucket(const uint256
&nKey
, const CNetAddr
& src
) const;
88 //! Calculate in which "new" bucket this entry belongs, using its default source
89 int GetNewBucket(const uint256
&nKey
) const
91 return GetNewBucket(nKey
, source
);
94 //! Calculate in which position of a bucket to store this entry.
95 int GetBucketPosition(const uint256
&nKey
, bool fNew
, int nBucket
) const;
97 //! Determine whether the statistics about this entry are bad enough so that it can just be deleted
98 bool IsTerrible(int64_t nNow
= GetAdjustedTime()) const;
100 //! Calculate the relative chance this entry should be given when selecting nodes to connect to
101 double GetChance(int64_t nNow
= GetAdjustedTime()) const;
105 /** Stochastic address manager
108 * * Keep the address tables in-memory, and asynchronously dump the entire table to peers.dat.
109 * * Make sure no (localized) attacker can fill the entire table with his nodes/addresses.
112 * * Addresses are organized into buckets.
113 * * Addresses that have not yet been tried go into 1024 "new" buckets.
114 * * Based on the address range (/16 for IPv4) of the source of information, 64 buckets are selected at random.
115 * * The actual bucket is chosen from one of these, based on the range in which the address itself is located.
116 * * One single address can occur in up to 8 different buckets to increase selection chances for addresses that
117 * are seen frequently. The chance for increasing this multiplicity decreases exponentially.
118 * * When adding a new address to a full bucket, a randomly chosen entry (with a bias favoring less recently seen
119 * ones) is removed from it first.
120 * * Addresses of nodes that are known to be accessible go into 256 "tried" buckets.
121 * * Each address range selects at random 8 of these buckets.
122 * * The actual bucket is chosen from one of these, based on the full address.
123 * * When adding a new good address to a full bucket, a randomly chosen entry (with a bias favoring less recently
124 * tried ones) is evicted from it, back to the "new" buckets.
125 * * Bucket selection is based on cryptographic hashing, using a randomly-generated 256-bit key, which should not
126 * be observable by adversaries.
127 * * Several indexes are kept for high performance. Defining DEBUG_ADDRMAN will introduce frequent (and expensive)
128 * consistency checks for the entire data structure.
131 //! total number of buckets for tried addresses
132 #define ADDRMAN_TRIED_BUCKET_COUNT 256
134 //! total number of buckets for new addresses
135 #define ADDRMAN_NEW_BUCKET_COUNT 1024
137 //! maximum allowed number of entries in buckets for new and tried addresses
138 #define ADDRMAN_BUCKET_SIZE 64
140 //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
141 #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8
143 //! over how many buckets entries with new addresses originating from a single group are spread
144 #define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 64
146 //! in how many buckets for entries with new addresses a single address may occur
147 #define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 8
149 //! how old addresses can maximally be
150 #define ADDRMAN_HORIZON_DAYS 30
152 //! after how many failed attempts we give up on a new node
153 #define ADDRMAN_RETRIES 3
155 //! how many successive failures are allowed ...
156 #define ADDRMAN_MAX_FAILURES 10
158 //! ... in at least this many days
159 #define ADDRMAN_MIN_FAIL_DAYS 7
161 //! the maximum percentage of nodes to return in a getaddr call
162 #define ADDRMAN_GETADDR_MAX_PCT 23
164 //! the maximum number of nodes to return in a getaddr call
165 #define ADDRMAN_GETADDR_MAX 2500
168 * Stochastical (IP) address manager
173 //! critical section to protect the inner data structures
174 mutable CCriticalSection cs
;
176 //! secret key to randomize bucket select with
182 //! table with information about all nIds
183 std::map
<int, CAddrInfo
> mapInfo
;
185 //! find an nId based on its network address
186 std::map
<CNetAddr
, int> mapAddr
;
188 //! randomly-ordered vector of all nIds
189 std::vector
<int> vRandom
;
191 // number of "tried" entries
194 //! list of "tried" buckets
195 int vvTried
[ADDRMAN_TRIED_BUCKET_COUNT
][ADDRMAN_BUCKET_SIZE
];
197 //! number of (unique) "new" entries
200 //! list of "new" buckets
201 int vvNew
[ADDRMAN_NEW_BUCKET_COUNT
][ADDRMAN_BUCKET_SIZE
];
206 CAddrInfo
* Find(const CNetAddr
& addr
, int *pnId
= NULL
);
208 //! find an entry, creating it if necessary.
209 //! nTime and nServices of the found node are updated, if necessary.
210 CAddrInfo
* Create(const CAddress
&addr
, const CNetAddr
&addrSource
, int *pnId
= NULL
);
212 //! Swap two elements in vRandom.
213 void SwapRandom(unsigned int nRandomPos1
, unsigned int nRandomPos2
);
215 //! Move an entry from the "new" table(s) to the "tried" table
216 void MakeTried(CAddrInfo
& info
, int nId
);
218 //! Delete an entry. It must not be in tried, and have refcount 0.
219 void Delete(int nId
);
221 //! Clear a position in a "new" table. This is the only place where entries are actually deleted.
222 void ClearNew(int nUBucket
, int nUBucketPos
);
224 //! Mark an entry "good", possibly moving it from "new" to "tried".
225 void Good_(const CService
&addr
, int64_t nTime
);
227 //! Add an entry to the "new" table.
228 bool Add_(const CAddress
&addr
, const CNetAddr
& source
, int64_t nTimePenalty
);
230 //! Mark an entry as attempted to connect.
231 void Attempt_(const CService
&addr
, int64_t nTime
);
233 //! Select an address to connect to.
237 //! Perform consistency check. Returns an error code or zero.
241 //! Select several addresses at once.
242 void GetAddr_(std::vector
<CAddress
> &vAddr
);
244 //! Mark an entry as currently-connected-to.
245 void Connected_(const CService
&addr
, int64_t nTime
);
250 * * version byte (currently 1)
251 * * 0x20 + nKey (serialized as if it were a vector, for backward compatibility)
254 * * number of "new" buckets XOR 2**30
255 * * all nNew addrinfos in vvNew
256 * * all nTried addrinfos in vvTried
258 * * number of elements
259 * * for each element: index
261 * 2**30 is xorred with the number of buckets to make addrman deserializer v0 detect it
262 * as incompatible. This is necessary because it did not check the version number on
265 * Notice that vvTried, mapAddr and vVector are never encoded explicitly;
266 * they are instead reconstructed from the other information.
268 * vvNew is serialized, but only used if ADDRMAN_UNKNOWN_BUCKET_COUNT didn't change,
269 * otherwise it is reconstructed as well.
271 * This format is more complex, but significantly smaller (at most 1.5 MiB), and supports
272 * changes to the ADDRMAN_ parameters without breaking the on-disk structure.
274 * We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has
275 * very little in common.
277 template<typename Stream
>
278 void Serialize(Stream
&s
, int nType
, int nVersionDummy
) const
282 unsigned char nVersion
= 1;
284 s
<< ((unsigned char)32);
289 int nUBuckets
= ADDRMAN_NEW_BUCKET_COUNT
^ (1 << 30);
291 std::map
<int, int> mapUnkIds
;
293 for (std::map
<int, CAddrInfo
>::const_iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); it
++) {
294 mapUnkIds
[(*it
).first
] = nIds
;
295 const CAddrInfo
&info
= (*it
).second
;
296 if (info
.nRefCount
) {
297 assert(nIds
!= nNew
); // this means nNew was wrong, oh ow
303 for (std::map
<int, CAddrInfo
>::const_iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); it
++) {
304 const CAddrInfo
&info
= (*it
).second
;
306 assert(nIds
!= nTried
); // this means nTried was wrong, oh ow
311 for (int bucket
= 0; bucket
< ADDRMAN_NEW_BUCKET_COUNT
; bucket
++) {
313 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
314 if (vvNew
[bucket
][i
] != -1)
318 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
319 if (vvNew
[bucket
][i
] != -1) {
320 int nIndex
= mapUnkIds
[vvNew
[bucket
][i
]];
327 template<typename Stream
>
328 void Unserialize(Stream
& s
, int nType
, int nVersionDummy
)
334 unsigned char nVersion
;
336 unsigned char nKeySize
;
338 if (nKeySize
!= 32) throw std::ios_base::failure("Incorrect keysize in addrman deserialization");
345 nUBuckets
^= (1 << 30);
348 // Deserialize entries from the new table.
349 for (int n
= 0; n
< nNew
; n
++) {
350 CAddrInfo
&info
= mapInfo
[n
];
353 info
.nRandomPos
= vRandom
.size();
354 vRandom
.push_back(n
);
355 if (nVersion
!= 1 || nUBuckets
!= ADDRMAN_NEW_BUCKET_COUNT
) {
356 // In case the new table data cannot be used (nVersion unknown, or bucket count wrong),
357 // immediately try to give them a reference based on their primary source address.
358 int nUBucket
= info
.GetNewBucket(nKey
);
359 int nUBucketPos
= info
.GetBucketPosition(nKey
, true, nUBucket
);
360 if (vvNew
[nUBucket
][nUBucketPos
] == -1) {
361 vvNew
[nUBucket
][nUBucketPos
] = n
;
368 // Deserialize entries from the tried table.
370 for (int n
= 0; n
< nTried
; n
++) {
373 int nKBucket
= info
.GetTriedBucket(nKey
);
374 int nKBucketPos
= info
.GetBucketPosition(nKey
, false, nKBucket
);
375 if (vvTried
[nKBucket
][nKBucketPos
] == -1) {
376 info
.nRandomPos
= vRandom
.size();
377 info
.fInTried
= true;
378 vRandom
.push_back(nIdCount
);
379 mapInfo
[nIdCount
] = info
;
380 mapAddr
[info
] = nIdCount
;
381 vvTried
[nKBucket
][nKBucketPos
] = nIdCount
;
389 // Deserialize positions in the new table (if possible).
390 for (int bucket
= 0; bucket
< nUBuckets
; bucket
++) {
393 for (int n
= 0; n
< nSize
; n
++) {
396 if (nIndex
>= 0 && nIndex
< nNew
) {
397 CAddrInfo
&info
= mapInfo
[nIndex
];
398 int nUBucketPos
= info
.GetBucketPosition(nKey
, true, bucket
);
399 if (nVersion
== 1 && nUBuckets
== ADDRMAN_NEW_BUCKET_COUNT
&& vvNew
[bucket
][nUBucketPos
] == -1 && info
.nRefCount
< ADDRMAN_NEW_BUCKETS_PER_ADDRESS
) {
401 vvNew
[bucket
][nUBucketPos
] = nIndex
;
407 // Prune new entries with refcount 0 (as a result of collisions).
409 for (std::map
<int, CAddrInfo
>::const_iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); ) {
410 if (it
->second
.fInTried
== false && it
->second
.nRefCount
== 0) {
411 std::map
<int, CAddrInfo
>::const_iterator itCopy
= it
++;
412 Delete(itCopy
->first
);
418 if (nLost
+ nLostUnk
> 0) {
419 LogPrint("addrman", "addrman lost %i new and %i tried addresses due to collisions\n", nLostUnk
, nLost
);
425 unsigned int GetSerializeSize(int nType
, int nVersion
) const
427 return (CSizeComputer(nType
, nVersion
) << *this).size();
432 std::vector
<int>().swap(vRandom
);
433 nKey
= GetRandHash();
434 for (size_t bucket
= 0; bucket
< ADDRMAN_NEW_BUCKET_COUNT
; bucket
++) {
435 for (size_t entry
= 0; entry
< ADDRMAN_BUCKET_SIZE
; entry
++) {
436 vvNew
[bucket
][entry
] = -1;
439 for (size_t bucket
= 0; bucket
< ADDRMAN_TRIED_BUCKET_COUNT
; bucket
++) {
440 for (size_t entry
= 0; entry
< ADDRMAN_BUCKET_SIZE
; entry
++) {
441 vvTried
[bucket
][entry
] = -1;
460 //! Return the number of (unique) addresses in all tables.
463 return vRandom
.size();
466 //! Consistency check
474 LogPrintf("ADDRMAN CONSISTENCY CHECK FAILED!!! err=%i\n", err
);
479 //! Add a single address.
480 bool Add(const CAddress
&addr
, const CNetAddr
& source
, int64_t nTimePenalty
= 0)
486 fRet
|= Add_(addr
, source
, nTimePenalty
);
490 LogPrint("addrman", "Added %s from %s: %i tried, %i new\n", addr
.ToStringIPPort(), source
.ToString(), nTried
, nNew
);
494 //! Add multiple addresses.
495 bool Add(const std::vector
<CAddress
> &vAddr
, const CNetAddr
& source
, int64_t nTimePenalty
= 0)
501 for (std::vector
<CAddress
>::const_iterator it
= vAddr
.begin(); it
!= vAddr
.end(); it
++)
502 nAdd
+= Add_(*it
, source
, nTimePenalty
) ? 1 : 0;
506 LogPrint("addrman", "Added %i addresses from %s: %i tried, %i new\n", nAdd
, source
.ToString(), nTried
, nNew
);
510 //! Mark an entry as accessible.
511 void Good(const CService
&addr
, int64_t nTime
= GetAdjustedTime())
521 //! Mark an entry as connection attempted to.
522 void Attempt(const CService
&addr
, int64_t nTime
= GetAdjustedTime())
527 Attempt_(addr
, nTime
);
533 * Choose an address to connect to.
547 //! Return a bunch of addresses, selected at random.
548 std::vector
<CAddress
> GetAddr()
551 std::vector
<CAddress
> vAddr
;
560 //! Mark an entry as currently-connected-to.
561 void Connected(const CService
&addr
, int64_t nTime
= GetAdjustedTime())
566 Connected_(addr
, nTime
);
572 #endif // BITCOIN_ADDRMAN_H