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.
12 int CAddrInfo::GetTriedBucket(const uint256
& nKey
) const
14 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetKey()).GetHash().GetCheapHash();
15 uint64_t hash2
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetGroup() << (hash1
% ADDRMAN_TRIED_BUCKETS_PER_GROUP
)).GetHash().GetCheapHash();
16 return hash2
% ADDRMAN_TRIED_BUCKET_COUNT
;
19 int CAddrInfo::GetNewBucket(const uint256
& nKey
, const CNetAddr
& src
) const
21 std::vector
<unsigned char> vchSourceGroupKey
= src
.GetGroup();
22 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetGroup() << vchSourceGroupKey
).GetHash().GetCheapHash();
23 uint64_t hash2
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< vchSourceGroupKey
<< (hash1
% ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP
)).GetHash().GetCheapHash();
24 return hash2
% ADDRMAN_NEW_BUCKET_COUNT
;
27 int CAddrInfo::GetBucketPosition(const uint256
&nKey
, bool fNew
, int nBucket
) const
29 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< (fNew
? 'N' : 'K') << nBucket
<< GetKey()).GetHash().GetCheapHash();
30 return hash1
% ADDRMAN_BUCKET_SIZE
;
33 bool CAddrInfo::IsTerrible(int64_t nNow
) const
35 if (nLastTry
&& nLastTry
>= nNow
- 60) // never remove things tried in the last minute
38 if (nTime
> nNow
+ 10 * 60) // came in a flying DeLorean
41 if (nTime
== 0 || nNow
- nTime
> ADDRMAN_HORIZON_DAYS
* 24 * 60 * 60) // not seen in recent history
44 if (nLastSuccess
== 0 && nAttempts
>= ADDRMAN_RETRIES
) // tried N times and never a success
47 if (nNow
- nLastSuccess
> ADDRMAN_MIN_FAIL_DAYS
* 24 * 60 * 60 && nAttempts
>= ADDRMAN_MAX_FAILURES
) // N successive failures in the last week
53 double CAddrInfo::GetChance(int64_t nNow
) const
57 int64_t nSinceLastSeen
= nNow
- nTime
;
58 int64_t nSinceLastTry
= nNow
- nLastTry
;
60 if (nSinceLastSeen
< 0)
62 if (nSinceLastTry
< 0)
65 // deprioritize very recent attempts away
66 if (nSinceLastTry
< 60 * 10)
69 // deprioritize 66% after each failed attempt, but at most 1/28th to avoid the search taking forever or overly penalizing outages.
70 fChance
*= pow(0.66, std::min(nAttempts
, 8));
75 CAddrInfo
* CAddrMan::Find(const CNetAddr
& addr
, int* pnId
)
77 std::map
<CNetAddr
, int>::iterator it
= mapAddr
.find(addr
);
78 if (it
== mapAddr
.end())
82 std::map
<int, CAddrInfo
>::iterator it2
= mapInfo
.find((*it
).second
);
83 if (it2
!= mapInfo
.end())
84 return &(*it2
).second
;
88 CAddrInfo
* CAddrMan::Create(const CAddress
& addr
, const CNetAddr
& addrSource
, int* pnId
)
91 mapInfo
[nId
] = CAddrInfo(addr
, addrSource
);
93 mapInfo
[nId
].nRandomPos
= vRandom
.size();
94 vRandom
.push_back(nId
);
100 void CAddrMan::SwapRandom(unsigned int nRndPos1
, unsigned int nRndPos2
)
102 if (nRndPos1
== nRndPos2
)
105 assert(nRndPos1
< vRandom
.size() && nRndPos2
< vRandom
.size());
107 int nId1
= vRandom
[nRndPos1
];
108 int nId2
= vRandom
[nRndPos2
];
110 assert(mapInfo
.count(nId1
) == 1);
111 assert(mapInfo
.count(nId2
) == 1);
113 mapInfo
[nId1
].nRandomPos
= nRndPos2
;
114 mapInfo
[nId2
].nRandomPos
= nRndPos1
;
116 vRandom
[nRndPos1
] = nId2
;
117 vRandom
[nRndPos2
] = nId1
;
120 void CAddrMan::Delete(int nId
)
122 assert(mapInfo
.count(nId
) != 0);
123 CAddrInfo
& info
= mapInfo
[nId
];
124 assert(!info
.fInTried
);
125 assert(info
.nRefCount
== 0);
127 SwapRandom(info
.nRandomPos
, vRandom
.size() - 1);
134 void CAddrMan::ClearNew(int nUBucket
, int nUBucketPos
)
136 // if there is an entry in the specified bucket, delete it.
137 if (vvNew
[nUBucket
][nUBucketPos
] != -1) {
138 int nIdDelete
= vvNew
[nUBucket
][nUBucketPos
];
139 CAddrInfo
& infoDelete
= mapInfo
[nIdDelete
];
140 assert(infoDelete
.nRefCount
> 0);
141 infoDelete
.nRefCount
--;
142 vvNew
[nUBucket
][nUBucketPos
] = -1;
143 if (infoDelete
.nRefCount
== 0) {
149 void CAddrMan::MakeTried(CAddrInfo
& info
, int nId
)
151 // remove the entry from all new buckets
152 for (int bucket
= 0; bucket
< ADDRMAN_NEW_BUCKET_COUNT
; bucket
++) {
153 int pos
= info
.GetBucketPosition(nKey
, true, bucket
);
154 if (vvNew
[bucket
][pos
] == nId
) {
155 vvNew
[bucket
][pos
] = -1;
161 assert(info
.nRefCount
== 0);
163 // which tried bucket to move the entry to
164 int nKBucket
= info
.GetTriedBucket(nKey
);
165 int nKBucketPos
= info
.GetBucketPosition(nKey
, false, nKBucket
);
167 // first make space to add it (the existing tried entry there is moved to new, deleting whatever is there).
168 if (vvTried
[nKBucket
][nKBucketPos
] != -1) {
169 // find an item to evict
170 int nIdEvict
= vvTried
[nKBucket
][nKBucketPos
];
171 assert(mapInfo
.count(nIdEvict
) == 1);
172 CAddrInfo
& infoOld
= mapInfo
[nIdEvict
];
174 // Remove the to-be-evicted item from the tried set.
175 infoOld
.fInTried
= false;
176 vvTried
[nKBucket
][nKBucketPos
] = -1;
179 // find which new bucket it belongs to
180 int nUBucket
= infoOld
.GetNewBucket(nKey
);
181 int nUBucketPos
= infoOld
.GetBucketPosition(nKey
, true, nUBucket
);
182 ClearNew(nUBucket
, nUBucketPos
);
183 assert(vvNew
[nUBucket
][nUBucketPos
] == -1);
185 // Enter it into the new set again.
186 infoOld
.nRefCount
= 1;
187 vvNew
[nUBucket
][nUBucketPos
] = nIdEvict
;
190 assert(vvTried
[nKBucket
][nKBucketPos
] == -1);
192 vvTried
[nKBucket
][nKBucketPos
] = nId
;
194 info
.fInTried
= true;
197 void CAddrMan::Good_(const CService
& addr
, int64_t nTime
)
200 CAddrInfo
* pinfo
= Find(addr
, &nId
);
202 // if not found, bail out
206 CAddrInfo
& info
= *pinfo
;
208 // check whether we are talking about the exact same CService (including same port)
213 info
.nLastSuccess
= nTime
;
214 info
.nLastTry
= nTime
;
216 // nTime is not updated here, to avoid leaking information about
217 // currently-connected peers.
219 // if it is already in the tried set, don't do anything else
223 // find a bucket it is in now
224 int nRnd
= RandomInt(ADDRMAN_NEW_BUCKET_COUNT
);
226 for (unsigned int n
= 0; n
< ADDRMAN_NEW_BUCKET_COUNT
; n
++) {
227 int nB
= (n
+ nRnd
) % ADDRMAN_NEW_BUCKET_COUNT
;
228 int nBpos
= info
.GetBucketPosition(nKey
, true, nB
);
229 if (vvNew
[nB
][nBpos
] == nId
) {
235 // if no bucket is found, something bad happened;
236 // TODO: maybe re-add the node, but for now, just bail out
240 LogPrint("addrman", "Moving %s to tried\n", addr
.ToString());
242 // move nId to the tried tables
243 MakeTried(info
, nId
);
246 bool CAddrMan::Add_(const CAddress
& addr
, const CNetAddr
& source
, int64_t nTimePenalty
)
248 if (!addr
.IsRoutable())
253 CAddrInfo
* pinfo
= Find(addr
, &nId
);
256 // periodically update nTime
257 bool fCurrentlyOnline
= (GetAdjustedTime() - addr
.nTime
< 24 * 60 * 60);
258 int64_t nUpdateInterval
= (fCurrentlyOnline
? 60 * 60 : 24 * 60 * 60);
259 if (addr
.nTime
&& (!pinfo
->nTime
|| pinfo
->nTime
< addr
.nTime
- nUpdateInterval
- nTimePenalty
))
260 pinfo
->nTime
= std::max((int64_t)0, addr
.nTime
- nTimePenalty
);
263 pinfo
->nServices
|= addr
.nServices
;
265 // do not update if no new information is present
266 if (!addr
.nTime
|| (pinfo
->nTime
&& addr
.nTime
<= pinfo
->nTime
))
269 // do not update if the entry was already in the "tried" table
273 // do not update if the max reference count is reached
274 if (pinfo
->nRefCount
== ADDRMAN_NEW_BUCKETS_PER_ADDRESS
)
277 // stochastic test: previous nRefCount == N: 2^N times harder to increase it
279 for (int n
= 0; n
< pinfo
->nRefCount
; n
++)
281 if (nFactor
> 1 && (RandomInt(nFactor
) != 0))
284 pinfo
= Create(addr
, source
, &nId
);
285 pinfo
->nTime
= std::max((int64_t)0, (int64_t)pinfo
->nTime
- nTimePenalty
);
290 int nUBucket
= pinfo
->GetNewBucket(nKey
, source
);
291 int nUBucketPos
= pinfo
->GetBucketPosition(nKey
, true, nUBucket
);
292 if (vvNew
[nUBucket
][nUBucketPos
] != nId
) {
293 bool fInsert
= vvNew
[nUBucket
][nUBucketPos
] == -1;
295 CAddrInfo
& infoExisting
= mapInfo
[vvNew
[nUBucket
][nUBucketPos
]];
296 if (infoExisting
.IsTerrible() || (infoExisting
.nRefCount
> 1 && pinfo
->nRefCount
== 0)) {
297 // Overwrite the existing new table entry.
302 ClearNew(nUBucket
, nUBucketPos
);
304 vvNew
[nUBucket
][nUBucketPos
] = nId
;
306 if (pinfo
->nRefCount
== 0) {
314 void CAddrMan::Attempt_(const CService
& addr
, int64_t nTime
)
316 CAddrInfo
* pinfo
= Find(addr
);
318 // if not found, bail out
322 CAddrInfo
& info
= *pinfo
;
324 // check whether we are talking about the exact same CService (including same port)
329 info
.nLastTry
= nTime
;
333 CAddrInfo
CAddrMan::Select_(bool newOnly
)
338 if (newOnly
&& nNew
== 0)
341 // Use a 50% chance for choosing between tried and new table entries.
343 (nTried
> 0 && (nNew
== 0 || RandomInt(2) == 0))) {
345 double fChanceFactor
= 1.0;
347 int nKBucket
= RandomInt(ADDRMAN_TRIED_BUCKET_COUNT
);
348 int nKBucketPos
= RandomInt(ADDRMAN_BUCKET_SIZE
);
349 while (vvTried
[nKBucket
][nKBucketPos
] == -1) {
350 nKBucket
= (nKBucket
+ insecure_rand()) % ADDRMAN_TRIED_BUCKET_COUNT
;
351 nKBucketPos
= (nKBucketPos
+ insecure_rand()) % ADDRMAN_BUCKET_SIZE
;
353 int nId
= vvTried
[nKBucket
][nKBucketPos
];
354 assert(mapInfo
.count(nId
) == 1);
355 CAddrInfo
& info
= mapInfo
[nId
];
356 if (RandomInt(1 << 30) < fChanceFactor
* info
.GetChance() * (1 << 30))
358 fChanceFactor
*= 1.2;
362 double fChanceFactor
= 1.0;
364 int nUBucket
= RandomInt(ADDRMAN_NEW_BUCKET_COUNT
);
365 int nUBucketPos
= RandomInt(ADDRMAN_BUCKET_SIZE
);
366 while (vvNew
[nUBucket
][nUBucketPos
] == -1) {
367 nUBucket
= (nUBucket
+ insecure_rand()) % ADDRMAN_NEW_BUCKET_COUNT
;
368 nUBucketPos
= (nUBucketPos
+ insecure_rand()) % ADDRMAN_BUCKET_SIZE
;
370 int nId
= vvNew
[nUBucket
][nUBucketPos
];
371 assert(mapInfo
.count(nId
) == 1);
372 CAddrInfo
& info
= mapInfo
[nId
];
373 if (RandomInt(1 << 30) < fChanceFactor
* info
.GetChance() * (1 << 30))
375 fChanceFactor
*= 1.2;
381 int CAddrMan::Check_()
383 std::set
<int> setTried
;
384 std::map
<int, int> mapNew
;
386 if (vRandom
.size() != nTried
+ nNew
)
389 for (std::map
<int, CAddrInfo
>::iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); it
++) {
391 CAddrInfo
& info
= (*it
).second
;
393 if (!info
.nLastSuccess
)
399 if (info
.nRefCount
< 0 || info
.nRefCount
> ADDRMAN_NEW_BUCKETS_PER_ADDRESS
)
403 mapNew
[n
] = info
.nRefCount
;
405 if (mapAddr
[info
] != n
)
407 if (info
.nRandomPos
< 0 || info
.nRandomPos
>= vRandom
.size() || vRandom
[info
.nRandomPos
] != n
)
409 if (info
.nLastTry
< 0)
411 if (info
.nLastSuccess
< 0)
415 if (setTried
.size() != nTried
)
417 if (mapNew
.size() != nNew
)
420 for (int n
= 0; n
< ADDRMAN_TRIED_BUCKET_COUNT
; n
++) {
421 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
422 if (vvTried
[n
][i
] != -1) {
423 if (!setTried
.count(vvTried
[n
][i
]))
425 if (mapInfo
[vvTried
[n
][i
]].GetTriedBucket(nKey
) != n
)
427 if (mapInfo
[vvTried
[n
][i
]].GetBucketPosition(nKey
, false, n
) != i
)
429 setTried
.erase(vvTried
[n
][i
]);
434 for (int n
= 0; n
< ADDRMAN_NEW_BUCKET_COUNT
; n
++) {
435 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
436 if (vvNew
[n
][i
] != -1) {
437 if (!mapNew
.count(vvNew
[n
][i
]))
439 if (mapInfo
[vvNew
[n
][i
]].GetBucketPosition(nKey
, true, n
) != i
)
441 if (--mapNew
[vvNew
[n
][i
]] == 0)
442 mapNew
.erase(vvNew
[n
][i
]);
458 void CAddrMan::GetAddr_(std::vector
<CAddress
>& vAddr
)
460 unsigned int nNodes
= ADDRMAN_GETADDR_MAX_PCT
* vRandom
.size() / 100;
461 if (nNodes
> ADDRMAN_GETADDR_MAX
)
462 nNodes
= ADDRMAN_GETADDR_MAX
;
464 // gather a list of random nodes, skipping those of low quality
465 for (unsigned int n
= 0; n
< vRandom
.size(); n
++) {
466 if (vAddr
.size() >= nNodes
)
469 int nRndPos
= RandomInt(vRandom
.size() - n
) + n
;
470 SwapRandom(n
, nRndPos
);
471 assert(mapInfo
.count(vRandom
[n
]) == 1);
473 const CAddrInfo
& ai
= mapInfo
[vRandom
[n
]];
474 if (!ai
.IsTerrible())
479 void CAddrMan::Connected_(const CService
& addr
, int64_t nTime
)
481 CAddrInfo
* pinfo
= Find(addr
);
483 // if not found, bail out
487 CAddrInfo
& info
= *pinfo
;
489 // check whether we are talking about the exact same CService (including same port)
494 int64_t nUpdateInterval
= 20 * 60;
495 if (nTime
- info
.nTime
> nUpdateInterval
)
499 int CAddrMan::RandomInt(int nMax
){
500 return GetRandInt(nMax
);