1 // Copyright (c) 2012 Pieter Wuille
2 // Copyright (c) 2012-2015 The Bitcoin Core developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
6 #ifndef BITCOIN_ADDRMAN_H
7 #define BITCOIN_ADDRMAN_H
22 * Extended statistics about a CAddress
24 class CAddrInfo
: public CAddress
29 //! last try whatsoever by us (memory only)
33 //! where knowledge about this address first came from
36 //! last successful connection by us
39 //! connection attempts since last successful attempt
42 //! reference count in new sets (memory only)
45 //! in tried set? (memory only)
48 //! position in vRandom
51 friend class CAddrMan
;
55 ADD_SERIALIZE_METHODS
;
57 template <typename Stream
, typename Operation
>
58 inline void SerializationOp(Stream
& s
, Operation ser_action
, int nType
, int nVersion
) {
59 READWRITE(*(CAddress
*)this);
61 READWRITE(nLastSuccess
);
75 CAddrInfo(const CAddress
&addrIn
, const CNetAddr
&addrSource
) : CAddress(addrIn
), source(addrSource
)
80 CAddrInfo() : CAddress(), source()
85 //! Calculate in which "tried" bucket this entry belongs
86 int GetTriedBucket(const uint256
&nKey
) const;
88 //! Calculate in which "new" bucket this entry belongs, given a certain source
89 int GetNewBucket(const uint256
&nKey
, const CNetAddr
& src
) const;
91 //! Calculate in which "new" bucket this entry belongs, using its default source
92 int GetNewBucket(const uint256
&nKey
) const
94 return GetNewBucket(nKey
, source
);
97 //! Calculate in which position of a bucket to store this entry.
98 int GetBucketPosition(const uint256
&nKey
, bool fNew
, int nBucket
) const;
100 //! Determine whether the statistics about this entry are bad enough so that it can just be deleted
101 bool IsTerrible(int64_t nNow
= GetAdjustedTime()) const;
103 //! Calculate the relative chance this entry should be given when selecting nodes to connect to
104 double GetChance(int64_t nNow
= GetAdjustedTime()) const;
108 /** Stochastic address manager
111 * * Keep the address tables in-memory, and asynchronously dump the entire table to peers.dat.
112 * * Make sure no (localized) attacker can fill the entire table with his nodes/addresses.
115 * * Addresses are organized into buckets.
116 * * Addresses that have not yet been tried go into 1024 "new" buckets.
117 * * Based on the address range (/16 for IPv4) of the source of information, 64 buckets are selected at random.
118 * * The actual bucket is chosen from one of these, based on the range in which the address itself is located.
119 * * One single address can occur in up to 8 different buckets to increase selection chances for addresses that
120 * are seen frequently. The chance for increasing this multiplicity decreases exponentially.
121 * * When adding a new address to a full bucket, a randomly chosen entry (with a bias favoring less recently seen
122 * ones) is removed from it first.
123 * * Addresses of nodes that are known to be accessible go into 256 "tried" buckets.
124 * * Each address range selects at random 8 of these buckets.
125 * * The actual bucket is chosen from one of these, based on the full address.
126 * * When adding a new good address to a full bucket, a randomly chosen entry (with a bias favoring less recently
127 * tried ones) is evicted from it, back to the "new" buckets.
128 * * Bucket selection is based on cryptographic hashing, using a randomly-generated 256-bit key, which should not
129 * be observable by adversaries.
130 * * Several indexes are kept for high performance. Defining DEBUG_ADDRMAN will introduce frequent (and expensive)
131 * consistency checks for the entire data structure.
134 //! total number of buckets for tried addresses
135 #define ADDRMAN_TRIED_BUCKET_COUNT 256
137 //! total number of buckets for new addresses
138 #define ADDRMAN_NEW_BUCKET_COUNT 1024
140 //! maximum allowed number of entries in buckets for new and tried addresses
141 #define ADDRMAN_BUCKET_SIZE 64
143 //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
144 #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8
146 //! over how many buckets entries with new addresses originating from a single group are spread
147 #define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 64
149 //! in how many buckets for entries with new addresses a single address may occur
150 #define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 8
152 //! how old addresses can maximally be
153 #define ADDRMAN_HORIZON_DAYS 30
155 //! after how many failed attempts we give up on a new node
156 #define ADDRMAN_RETRIES 3
158 //! how many successive failures are allowed ...
159 #define ADDRMAN_MAX_FAILURES 10
161 //! ... in at least this many days
162 #define ADDRMAN_MIN_FAIL_DAYS 7
164 //! the maximum percentage of nodes to return in a getaddr call
165 #define ADDRMAN_GETADDR_MAX_PCT 23
167 //! the maximum number of nodes to return in a getaddr call
168 #define ADDRMAN_GETADDR_MAX 2500
171 * Stochastical (IP) address manager
176 //! critical section to protect the inner data structures
177 mutable CCriticalSection cs
;
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
];
204 //! secret key to randomize bucket select with
208 CAddrInfo
* Find(const CNetAddr
& addr
, int *pnId
= NULL
);
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
);
214 //! Swap two elements in vRandom.
215 void SwapRandom(unsigned int nRandomPos1
, unsigned int nRandomPos2
);
217 //! Move an entry from the "new" table(s) to the "tried" table
218 void MakeTried(CAddrInfo
& info
, int nId
);
220 //! Delete an entry. It must not be in tried, and have refcount 0.
221 void Delete(int nId
);
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
);
226 //! Mark an entry "good", possibly moving it from "new" to "tried".
227 void Good_(const CService
&addr
, int64_t nTime
);
229 //! Add an entry to the "new" table.
230 bool Add_(const CAddress
&addr
, const CNetAddr
& source
, int64_t nTimePenalty
);
232 //! Mark an entry as attempted to connect.
233 void Attempt_(const CService
&addr
, int64_t nTime
);
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
);
238 //! Wraps GetRandInt to allow tests to override RandomInt and make it determinismistic.
239 virtual int RandomInt(int nMax
);
242 //! Perform consistency check. Returns an error code or zero.
246 //! Select several addresses at once.
247 void GetAddr_(std::vector
<CAddress
> &vAddr
);
249 //! Mark an entry as currently-connected-to.
250 void Connected_(const CService
&addr
, int64_t nTime
);
255 * * version byte (currently 1)
256 * * 0x20 + nKey (serialized as if it were a vector, for backward compatibility)
259 * * number of "new" buckets XOR 2**30
260 * * all nNew addrinfos in vvNew
261 * * all nTried addrinfos in vvTried
263 * * number of elements
264 * * for each element: index
266 * 2**30 is xorred with the number of buckets to make addrman deserializer v0 detect it
267 * as incompatible. This is necessary because it did not check the version number on
270 * Notice that vvTried, mapAddr and vVector are never encoded explicitly;
271 * they are instead reconstructed from the other information.
273 * vvNew is serialized, but only used if ADDRMAN_UNKNOWN_BUCKET_COUNT didn't change,
274 * otherwise it is reconstructed as well.
276 * This format is more complex, but significantly smaller (at most 1.5 MiB), and supports
277 * changes to the ADDRMAN_ parameters without breaking the on-disk structure.
279 * We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has
280 * very little in common.
282 template<typename Stream
>
283 void Serialize(Stream
&s
, int nType
, int nVersionDummy
) const
287 unsigned char nVersion
= 1;
289 s
<< ((unsigned char)32);
294 int nUBuckets
= ADDRMAN_NEW_BUCKET_COUNT
^ (1 << 30);
296 std::map
<int, int> mapUnkIds
;
298 for (std::map
<int, CAddrInfo
>::const_iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); it
++) {
299 mapUnkIds
[(*it
).first
] = nIds
;
300 const CAddrInfo
&info
= (*it
).second
;
301 if (info
.nRefCount
) {
302 assert(nIds
!= nNew
); // this means nNew was wrong, oh ow
308 for (std::map
<int, CAddrInfo
>::const_iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); it
++) {
309 const CAddrInfo
&info
= (*it
).second
;
311 assert(nIds
!= nTried
); // this means nTried was wrong, oh ow
316 for (int bucket
= 0; bucket
< ADDRMAN_NEW_BUCKET_COUNT
; bucket
++) {
318 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
319 if (vvNew
[bucket
][i
] != -1)
323 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
324 if (vvNew
[bucket
][i
] != -1) {
325 int nIndex
= mapUnkIds
[vvNew
[bucket
][i
]];
332 template<typename Stream
>
333 void Unserialize(Stream
& s
, int nType
, int nVersionDummy
)
339 unsigned char nVersion
;
341 unsigned char nKeySize
;
343 if (nKeySize
!= 32) throw std::ios_base::failure("Incorrect keysize in addrman deserialization");
350 nUBuckets
^= (1 << 30);
353 // Deserialize entries from the new table.
354 for (int n
= 0; n
< nNew
; n
++) {
355 CAddrInfo
&info
= mapInfo
[n
];
358 info
.nRandomPos
= vRandom
.size();
359 vRandom
.push_back(n
);
360 if (nVersion
!= 1 || nUBuckets
!= ADDRMAN_NEW_BUCKET_COUNT
) {
361 // In case the new table data cannot be used (nVersion unknown, or bucket count wrong),
362 // immediately try to give them a reference based on their primary source address.
363 int nUBucket
= info
.GetNewBucket(nKey
);
364 int nUBucketPos
= info
.GetBucketPosition(nKey
, true, nUBucket
);
365 if (vvNew
[nUBucket
][nUBucketPos
] == -1) {
366 vvNew
[nUBucket
][nUBucketPos
] = n
;
373 // Deserialize entries from the tried table.
375 for (int n
= 0; n
< nTried
; n
++) {
378 int nKBucket
= info
.GetTriedBucket(nKey
);
379 int nKBucketPos
= info
.GetBucketPosition(nKey
, false, nKBucket
);
380 if (vvTried
[nKBucket
][nKBucketPos
] == -1) {
381 info
.nRandomPos
= vRandom
.size();
382 info
.fInTried
= true;
383 vRandom
.push_back(nIdCount
);
384 mapInfo
[nIdCount
] = info
;
385 mapAddr
[info
] = nIdCount
;
386 vvTried
[nKBucket
][nKBucketPos
] = nIdCount
;
394 // Deserialize positions in the new table (if possible).
395 for (int bucket
= 0; bucket
< nUBuckets
; bucket
++) {
398 for (int n
= 0; n
< nSize
; n
++) {
401 if (nIndex
>= 0 && nIndex
< nNew
) {
402 CAddrInfo
&info
= mapInfo
[nIndex
];
403 int nUBucketPos
= info
.GetBucketPosition(nKey
, true, bucket
);
404 if (nVersion
== 1 && nUBuckets
== ADDRMAN_NEW_BUCKET_COUNT
&& vvNew
[bucket
][nUBucketPos
] == -1 && info
.nRefCount
< ADDRMAN_NEW_BUCKETS_PER_ADDRESS
) {
406 vvNew
[bucket
][nUBucketPos
] = nIndex
;
412 // Prune new entries with refcount 0 (as a result of collisions).
414 for (std::map
<int, CAddrInfo
>::const_iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); ) {
415 if (it
->second
.fInTried
== false && it
->second
.nRefCount
== 0) {
416 std::map
<int, CAddrInfo
>::const_iterator itCopy
= it
++;
417 Delete(itCopy
->first
);
423 if (nLost
+ nLostUnk
> 0) {
424 LogPrint("addrman", "addrman lost %i new and %i tried addresses due to collisions\n", nLostUnk
, nLost
);
430 unsigned int GetSerializeSize(int nType
, int nVersion
) const
432 return (CSizeComputer(nType
, nVersion
) << *this).size();
437 std::vector
<int>().swap(vRandom
);
438 nKey
= GetRandHash();
439 for (size_t bucket
= 0; bucket
< ADDRMAN_NEW_BUCKET_COUNT
; bucket
++) {
440 for (size_t entry
= 0; entry
< ADDRMAN_BUCKET_SIZE
; entry
++) {
441 vvNew
[bucket
][entry
] = -1;
444 for (size_t bucket
= 0; bucket
< ADDRMAN_TRIED_BUCKET_COUNT
; bucket
++) {
445 for (size_t entry
= 0; entry
< ADDRMAN_BUCKET_SIZE
; entry
++) {
446 vvTried
[bucket
][entry
] = -1;
465 //! Return the number of (unique) addresses in all tables.
468 return vRandom
.size();
471 //! Consistency check
479 LogPrintf("ADDRMAN CONSISTENCY CHECK FAILED!!! err=%i\n", err
);
484 //! Add a single address.
485 bool Add(const CAddress
&addr
, const CNetAddr
& source
, int64_t nTimePenalty
= 0)
491 fRet
|= Add_(addr
, source
, nTimePenalty
);
495 LogPrint("addrman", "Added %s from %s: %i tried, %i new\n", addr
.ToStringIPPort(), source
.ToString(), nTried
, nNew
);
499 //! Add multiple addresses.
500 bool Add(const std::vector
<CAddress
> &vAddr
, const CNetAddr
& source
, int64_t nTimePenalty
= 0)
506 for (std::vector
<CAddress
>::const_iterator it
= vAddr
.begin(); it
!= vAddr
.end(); it
++)
507 nAdd
+= Add_(*it
, source
, nTimePenalty
) ? 1 : 0;
511 LogPrint("addrman", "Added %i addresses from %s: %i tried, %i new\n", nAdd
, source
.ToString(), nTried
, nNew
);
515 //! Mark an entry as accessible.
516 void Good(const CService
&addr
, int64_t nTime
= GetAdjustedTime())
526 //! Mark an entry as connection attempted to.
527 void Attempt(const CService
&addr
, int64_t nTime
= GetAdjustedTime())
532 Attempt_(addr
, nTime
);
538 * Choose an address to connect to.
540 CAddrInfo
Select(bool newOnly
= false)
546 addrRet
= Select_(newOnly
);
552 //! Return a bunch of addresses, selected at random.
553 std::vector
<CAddress
> GetAddr()
556 std::vector
<CAddress
> vAddr
;
565 //! Mark an entry as currently-connected-to.
566 void Connected(const CService
&addr
, int64_t nTime
= GetAdjustedTime())
571 Connected_(addr
, nTime
);
578 #endif // BITCOIN_ADDRMAN_H