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.
11 int CAddrInfo::GetTriedBucket(const uint256
& nKey
) const
13 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetKey()).GetHash().GetCheapHash();
14 uint64_t hash2
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetGroup() << (hash1
% ADDRMAN_TRIED_BUCKETS_PER_GROUP
)).GetHash().GetCheapHash();
15 return hash2
% ADDRMAN_TRIED_BUCKET_COUNT
;
18 int CAddrInfo::GetNewBucket(const uint256
& nKey
, const CNetAddr
& src
) const
20 std::vector
<unsigned char> vchSourceGroupKey
= src
.GetGroup();
21 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetGroup() << vchSourceGroupKey
).GetHash().GetCheapHash();
22 uint64_t hash2
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< vchSourceGroupKey
<< (hash1
% ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP
)).GetHash().GetCheapHash();
23 return hash2
% ADDRMAN_NEW_BUCKET_COUNT
;
26 int CAddrInfo::GetBucketPosition(const uint256
&nKey
, bool fNew
, int nBucket
) const
28 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< (fNew
? 'N' : 'K') << nBucket
<< GetKey()).GetHash().GetCheapHash();
29 return hash1
% ADDRMAN_BUCKET_SIZE
;
32 bool CAddrInfo::IsTerrible(int64_t nNow
) const
34 if (nLastTry
&& nLastTry
>= nNow
- 60) // never remove things tried in the last minute
37 if (nTime
> nNow
+ 10 * 60) // came in a flying DeLorean
40 if (nTime
== 0 || nNow
- nTime
> ADDRMAN_HORIZON_DAYS
* 24 * 60 * 60) // not seen in recent history
43 if (nLastSuccess
== 0 && nAttempts
>= ADDRMAN_RETRIES
) // tried N times and never a success
46 if (nNow
- nLastSuccess
> ADDRMAN_MIN_FAIL_DAYS
* 24 * 60 * 60 && nAttempts
>= ADDRMAN_MAX_FAILURES
) // N successive failures in the last week
52 double CAddrInfo::GetChance(int64_t nNow
) const
56 int64_t nSinceLastSeen
= nNow
- nTime
;
57 int64_t nSinceLastTry
= nNow
- nLastTry
;
59 if (nSinceLastSeen
< 0)
61 if (nSinceLastTry
< 0)
64 // deprioritize very recent attempts away
65 if (nSinceLastTry
< 60 * 10)
68 // deprioritize 66% after each failed attempt, but at most 1/28th to avoid the search taking forever or overly penalizing outages.
69 fChance
*= pow(0.66, std::min(nAttempts
, 8));
74 CAddrInfo
* CAddrMan::Find(const CNetAddr
& addr
, int* pnId
)
76 std::map
<CNetAddr
, int>::iterator it
= mapAddr
.find(addr
);
77 if (it
== mapAddr
.end())
81 std::map
<int, CAddrInfo
>::iterator it2
= mapInfo
.find((*it
).second
);
82 if (it2
!= mapInfo
.end())
83 return &(*it2
).second
;
87 CAddrInfo
* CAddrMan::Create(const CAddress
& addr
, const CNetAddr
& addrSource
, int* pnId
)
90 mapInfo
[nId
] = CAddrInfo(addr
, addrSource
);
92 mapInfo
[nId
].nRandomPos
= vRandom
.size();
93 vRandom
.push_back(nId
);
99 void CAddrMan::SwapRandom(unsigned int nRndPos1
, unsigned int nRndPos2
)
101 if (nRndPos1
== nRndPos2
)
104 assert(nRndPos1
< vRandom
.size() && nRndPos2
< vRandom
.size());
106 int nId1
= vRandom
[nRndPos1
];
107 int nId2
= vRandom
[nRndPos2
];
109 assert(mapInfo
.count(nId1
) == 1);
110 assert(mapInfo
.count(nId2
) == 1);
112 mapInfo
[nId1
].nRandomPos
= nRndPos2
;
113 mapInfo
[nId2
].nRandomPos
= nRndPos1
;
115 vRandom
[nRndPos1
] = nId2
;
116 vRandom
[nRndPos2
] = nId1
;
119 void CAddrMan::Delete(int nId
)
121 assert(mapInfo
.count(nId
) != 0);
122 CAddrInfo
& info
= mapInfo
[nId
];
123 assert(!info
.fInTried
);
124 assert(info
.nRefCount
== 0);
126 SwapRandom(info
.nRandomPos
, vRandom
.size() - 1);
133 void CAddrMan::ClearNew(int nUBucket
, int nUBucketPos
)
135 // if there is an entry in the specified bucket, delete it.
136 if (vvNew
[nUBucket
][nUBucketPos
] != -1) {
137 int nIdDelete
= vvNew
[nUBucket
][nUBucketPos
];
138 CAddrInfo
& infoDelete
= mapInfo
[nIdDelete
];
139 assert(infoDelete
.nRefCount
> 0);
140 infoDelete
.nRefCount
--;
141 vvNew
[nUBucket
][nUBucketPos
] = -1;
142 if (infoDelete
.nRefCount
== 0) {
148 void CAddrMan::MakeTried(CAddrInfo
& info
, int nId
)
150 // remove the entry from all new buckets
151 for (int bucket
= 0; bucket
< ADDRMAN_NEW_BUCKET_COUNT
; bucket
++) {
152 int pos
= info
.GetBucketPosition(nKey
, true, bucket
);
153 if (vvNew
[bucket
][pos
] == nId
) {
154 vvNew
[bucket
][pos
] = -1;
160 assert(info
.nRefCount
== 0);
162 // which tried bucket to move the entry to
163 int nKBucket
= info
.GetTriedBucket(nKey
);
164 int nKBucketPos
= info
.GetBucketPosition(nKey
, false, nKBucket
);
166 // first make space to add it (the existing tried entry there is moved to new, deleting whatever is there).
167 if (vvTried
[nKBucket
][nKBucketPos
] != -1) {
168 // find an item to evict
169 int nIdEvict
= vvTried
[nKBucket
][nKBucketPos
];
170 assert(mapInfo
.count(nIdEvict
) == 1);
171 CAddrInfo
& infoOld
= mapInfo
[nIdEvict
];
173 // Remove the to-be-evicted item from the tried set.
174 infoOld
.fInTried
= false;
175 vvTried
[nKBucket
][nKBucketPos
] = -1;
178 // find which new bucket it belongs to
179 int nUBucket
= infoOld
.GetNewBucket(nKey
);
180 int nUBucketPos
= infoOld
.GetBucketPosition(nKey
, true, nUBucket
);
181 ClearNew(nUBucket
, nUBucketPos
);
182 assert(vvNew
[nUBucket
][nUBucketPos
] == -1);
184 // Enter it into the new set again.
185 infoOld
.nRefCount
= 1;
186 vvNew
[nUBucket
][nUBucketPos
] = nIdEvict
;
189 assert(vvTried
[nKBucket
][nKBucketPos
] == -1);
191 vvTried
[nKBucket
][nKBucketPos
] = nId
;
193 info
.fInTried
= true;
196 void CAddrMan::Good_(const CService
& addr
, int64_t nTime
)
199 CAddrInfo
* pinfo
= Find(addr
, &nId
);
201 // if not found, bail out
205 CAddrInfo
& info
= *pinfo
;
207 // check whether we are talking about the exact same CService (including same port)
212 info
.nLastSuccess
= nTime
;
213 info
.nLastTry
= nTime
;
215 // nTime is not updated here, to avoid leaking information about
216 // currently-connected peers.
218 // if it is already in the tried set, don't do anything else
222 // find a bucket it is in now
223 int nRnd
= GetRandInt(ADDRMAN_NEW_BUCKET_COUNT
);
225 for (unsigned int n
= 0; n
< ADDRMAN_NEW_BUCKET_COUNT
; n
++) {
226 int nB
= (n
+ nRnd
) % ADDRMAN_NEW_BUCKET_COUNT
;
227 int nBpos
= info
.GetBucketPosition(nKey
, true, nB
);
228 if (vvNew
[nB
][nBpos
] == nId
) {
234 // if no bucket is found, something bad happened;
235 // TODO: maybe re-add the node, but for now, just bail out
239 LogPrint("addrman", "Moving %s to tried\n", addr
.ToString());
241 // move nId to the tried tables
242 MakeTried(info
, nId
);
245 bool CAddrMan::Add_(const CAddress
& addr
, const CNetAddr
& source
, int64_t nTimePenalty
)
247 if (!addr
.IsRoutable())
252 CAddrInfo
* pinfo
= Find(addr
, &nId
);
255 // periodically update nTime
256 bool fCurrentlyOnline
= (GetAdjustedTime() - addr
.nTime
< 24 * 60 * 60);
257 int64_t nUpdateInterval
= (fCurrentlyOnline
? 60 * 60 : 24 * 60 * 60);
258 if (addr
.nTime
&& (!pinfo
->nTime
|| pinfo
->nTime
< addr
.nTime
- nUpdateInterval
- nTimePenalty
))
259 pinfo
->nTime
= std::max((int64_t)0, addr
.nTime
- nTimePenalty
);
262 pinfo
->nServices
|= addr
.nServices
;
264 // do not update if no new information is present
265 if (!addr
.nTime
|| (pinfo
->nTime
&& addr
.nTime
<= pinfo
->nTime
))
268 // do not update if the entry was already in the "tried" table
272 // do not update if the max reference count is reached
273 if (pinfo
->nRefCount
== ADDRMAN_NEW_BUCKETS_PER_ADDRESS
)
276 // stochastic test: previous nRefCount == N: 2^N times harder to increase it
278 for (int n
= 0; n
< pinfo
->nRefCount
; n
++)
280 if (nFactor
> 1 && (GetRandInt(nFactor
) != 0))
283 pinfo
= Create(addr
, source
, &nId
);
284 pinfo
->nTime
= std::max((int64_t)0, (int64_t)pinfo
->nTime
- nTimePenalty
);
289 int nUBucket
= pinfo
->GetNewBucket(nKey
, source
);
290 int nUBucketPos
= pinfo
->GetBucketPosition(nKey
, true, nUBucket
);
291 if (vvNew
[nUBucket
][nUBucketPos
] != nId
) {
292 bool fInsert
= vvNew
[nUBucket
][nUBucketPos
] == -1;
294 CAddrInfo
& infoExisting
= mapInfo
[vvNew
[nUBucket
][nUBucketPos
]];
295 if (infoExisting
.IsTerrible() || (infoExisting
.nRefCount
> 1 && pinfo
->nRefCount
== 0)) {
296 // Overwrite the existing new table entry.
301 ClearNew(nUBucket
, nUBucketPos
);
303 vvNew
[nUBucket
][nUBucketPos
] = nId
;
305 if (pinfo
->nRefCount
== 0) {
313 void CAddrMan::Attempt_(const CService
& addr
, int64_t nTime
)
315 CAddrInfo
* pinfo
= Find(addr
);
317 // if not found, bail out
321 CAddrInfo
& info
= *pinfo
;
323 // check whether we are talking about the exact same CService (including same port)
328 info
.nLastTry
= nTime
;
332 CAddrInfo
CAddrMan::Select_(bool newOnly
)
337 if (newOnly
&& nNew
== 0)
340 // Use a 50% chance for choosing between tried and new table entries.
342 (nTried
> 0 && (nNew
== 0 || GetRandInt(2) == 0))) {
344 double fChanceFactor
= 1.0;
346 int nKBucket
= GetRandInt(ADDRMAN_TRIED_BUCKET_COUNT
);
347 int nKBucketPos
= GetRandInt(ADDRMAN_BUCKET_SIZE
);
348 while (vvTried
[nKBucket
][nKBucketPos
] == -1) {
349 nKBucket
= (nKBucket
+ insecure_rand()) % ADDRMAN_TRIED_BUCKET_COUNT
;
350 nKBucketPos
= (nKBucketPos
+ insecure_rand()) % ADDRMAN_BUCKET_SIZE
;
352 int nId
= vvTried
[nKBucket
][nKBucketPos
];
353 assert(mapInfo
.count(nId
) == 1);
354 CAddrInfo
& info
= mapInfo
[nId
];
355 if (GetRandInt(1 << 30) < fChanceFactor
* info
.GetChance() * (1 << 30))
357 fChanceFactor
*= 1.2;
361 double fChanceFactor
= 1.0;
363 int nUBucket
= GetRandInt(ADDRMAN_NEW_BUCKET_COUNT
);
364 int nUBucketPos
= GetRandInt(ADDRMAN_BUCKET_SIZE
);
365 while (vvNew
[nUBucket
][nUBucketPos
] == -1) {
366 nUBucket
= (nUBucket
+ insecure_rand()) % ADDRMAN_NEW_BUCKET_COUNT
;
367 nUBucketPos
= (nUBucketPos
+ insecure_rand()) % ADDRMAN_BUCKET_SIZE
;
369 int nId
= vvNew
[nUBucket
][nUBucketPos
];
370 assert(mapInfo
.count(nId
) == 1);
371 CAddrInfo
& info
= mapInfo
[nId
];
372 if (GetRandInt(1 << 30) < fChanceFactor
* info
.GetChance() * (1 << 30))
374 fChanceFactor
*= 1.2;
380 int CAddrMan::Check_()
382 std::set
<int> setTried
;
383 std::map
<int, int> mapNew
;
385 if (vRandom
.size() != nTried
+ nNew
)
388 for (std::map
<int, CAddrInfo
>::iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); it
++) {
390 CAddrInfo
& info
= (*it
).second
;
392 if (!info
.nLastSuccess
)
398 if (info
.nRefCount
< 0 || info
.nRefCount
> ADDRMAN_NEW_BUCKETS_PER_ADDRESS
)
402 mapNew
[n
] = info
.nRefCount
;
404 if (mapAddr
[info
] != n
)
406 if (info
.nRandomPos
< 0 || info
.nRandomPos
>= vRandom
.size() || vRandom
[info
.nRandomPos
] != n
)
408 if (info
.nLastTry
< 0)
410 if (info
.nLastSuccess
< 0)
414 if (setTried
.size() != nTried
)
416 if (mapNew
.size() != nNew
)
419 for (int n
= 0; n
< ADDRMAN_TRIED_BUCKET_COUNT
; n
++) {
420 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
421 if (vvTried
[n
][i
] != -1) {
422 if (!setTried
.count(vvTried
[n
][i
]))
424 if (mapInfo
[vvTried
[n
][i
]].GetTriedBucket(nKey
) != n
)
426 if (mapInfo
[vvTried
[n
][i
]].GetBucketPosition(nKey
, false, n
) != i
)
428 setTried
.erase(vvTried
[n
][i
]);
433 for (int n
= 0; n
< ADDRMAN_NEW_BUCKET_COUNT
; n
++) {
434 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
435 if (vvNew
[n
][i
] != -1) {
436 if (!mapNew
.count(vvNew
[n
][i
]))
438 if (mapInfo
[vvNew
[n
][i
]].GetBucketPosition(nKey
, true, n
) != i
)
440 if (--mapNew
[vvNew
[n
][i
]] == 0)
441 mapNew
.erase(vvNew
[n
][i
]);
457 void CAddrMan::GetAddr_(std::vector
<CAddress
>& vAddr
)
459 unsigned int nNodes
= ADDRMAN_GETADDR_MAX_PCT
* vRandom
.size() / 100;
460 if (nNodes
> ADDRMAN_GETADDR_MAX
)
461 nNodes
= ADDRMAN_GETADDR_MAX
;
463 // gather a list of random nodes, skipping those of low quality
464 for (unsigned int n
= 0; n
< vRandom
.size(); n
++) {
465 if (vAddr
.size() >= nNodes
)
468 int nRndPos
= GetRandInt(vRandom
.size() - n
) + n
;
469 SwapRandom(n
, nRndPos
);
470 assert(mapInfo
.count(vRandom
[n
]) == 1);
472 const CAddrInfo
& ai
= mapInfo
[vRandom
[n
]];
473 if (!ai
.IsTerrible())
478 void CAddrMan::Connected_(const CService
& addr
, int64_t nTime
)
480 CAddrInfo
* pinfo
= Find(addr
);
482 // if not found, bail out
486 CAddrInfo
& info
= *pinfo
;
488 // check whether we are talking about the exact same CService (including same port)
493 int64_t nUpdateInterval
= 20 * 60;
494 if (nTime
- info
.nTime
> nUpdateInterval
)