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.
13 int CAddrInfo::GetTriedBucket(const uint256
& nKey
) const
15 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetKey()).GetHash().GetCheapHash();
16 uint64_t hash2
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetGroup() << (hash1
% ADDRMAN_TRIED_BUCKETS_PER_GROUP
)).GetHash().GetCheapHash();
17 return hash2
% ADDRMAN_TRIED_BUCKET_COUNT
;
20 int CAddrInfo::GetNewBucket(const uint256
& nKey
, const CNetAddr
& src
) const
22 std::vector
<unsigned char> vchSourceGroupKey
= src
.GetGroup();
23 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< GetGroup() << vchSourceGroupKey
).GetHash().GetCheapHash();
24 uint64_t hash2
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< vchSourceGroupKey
<< (hash1
% ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP
)).GetHash().GetCheapHash();
25 return hash2
% ADDRMAN_NEW_BUCKET_COUNT
;
28 int CAddrInfo::GetBucketPosition(const uint256
&nKey
, bool fNew
, int nBucket
) const
30 uint64_t hash1
= (CHashWriter(SER_GETHASH
, 0) << nKey
<< (fNew
? 'N' : 'K') << nBucket
<< GetKey()).GetHash().GetCheapHash();
31 return hash1
% ADDRMAN_BUCKET_SIZE
;
34 bool CAddrInfo::IsTerrible(int64_t nNow
) const
36 if (nLastTry
&& nLastTry
>= nNow
- 60) // never remove things tried in the last minute
39 if (nTime
> nNow
+ 10 * 60) // came in a flying DeLorean
42 if (nTime
== 0 || nNow
- nTime
> ADDRMAN_HORIZON_DAYS
* 24 * 60 * 60) // not seen in recent history
45 if (nLastSuccess
== 0 && nAttempts
>= ADDRMAN_RETRIES
) // tried N times and never a success
48 if (nNow
- nLastSuccess
> ADDRMAN_MIN_FAIL_DAYS
* 24 * 60 * 60 && nAttempts
>= ADDRMAN_MAX_FAILURES
) // N successive failures in the last week
54 double CAddrInfo::GetChance(int64_t nNow
) const
58 int64_t nSinceLastSeen
= nNow
- nTime
;
59 int64_t nSinceLastTry
= nNow
- nLastTry
;
61 if (nSinceLastSeen
< 0)
63 if (nSinceLastTry
< 0)
66 // deprioritize very recent attempts away
67 if (nSinceLastTry
< 60 * 10)
70 // deprioritize 66% after each failed attempt, but at most 1/28th to avoid the search taking forever or overly penalizing outages.
71 fChance
*= pow(0.66, min(nAttempts
, 8));
76 CAddrInfo
* CAddrMan::Find(const CNetAddr
& addr
, int* pnId
)
78 std::map
<CNetAddr
, int>::iterator it
= mapAddr
.find(addr
);
79 if (it
== mapAddr
.end())
83 std::map
<int, CAddrInfo
>::iterator it2
= mapInfo
.find((*it
).second
);
84 if (it2
!= mapInfo
.end())
85 return &(*it2
).second
;
89 CAddrInfo
* CAddrMan::Create(const CAddress
& addr
, const CNetAddr
& addrSource
, int* pnId
)
92 mapInfo
[nId
] = CAddrInfo(addr
, addrSource
);
94 mapInfo
[nId
].nRandomPos
= vRandom
.size();
95 vRandom
.push_back(nId
);
101 void CAddrMan::SwapRandom(unsigned int nRndPos1
, unsigned int nRndPos2
)
103 if (nRndPos1
== nRndPos2
)
106 assert(nRndPos1
< vRandom
.size() && nRndPos2
< vRandom
.size());
108 int nId1
= vRandom
[nRndPos1
];
109 int nId2
= vRandom
[nRndPos2
];
111 assert(mapInfo
.count(nId1
) == 1);
112 assert(mapInfo
.count(nId2
) == 1);
114 mapInfo
[nId1
].nRandomPos
= nRndPos2
;
115 mapInfo
[nId2
].nRandomPos
= nRndPos1
;
117 vRandom
[nRndPos1
] = nId2
;
118 vRandom
[nRndPos2
] = nId1
;
121 void CAddrMan::Delete(int nId
)
123 assert(mapInfo
.count(nId
) != 0);
124 CAddrInfo
& info
= mapInfo
[nId
];
125 assert(!info
.fInTried
);
126 assert(info
.nRefCount
== 0);
128 SwapRandom(info
.nRandomPos
, vRandom
.size() - 1);
135 void CAddrMan::ClearNew(int nUBucket
, int nUBucketPos
)
137 // if there is an entry in the specified bucket, delete it.
138 if (vvNew
[nUBucket
][nUBucketPos
] != -1) {
139 int nIdDelete
= vvNew
[nUBucket
][nUBucketPos
];
140 CAddrInfo
& infoDelete
= mapInfo
[nIdDelete
];
141 assert(infoDelete
.nRefCount
> 0);
142 infoDelete
.nRefCount
--;
143 vvNew
[nUBucket
][nUBucketPos
] = -1;
144 if (infoDelete
.nRefCount
== 0) {
150 void CAddrMan::MakeTried(CAddrInfo
& info
, int nId
)
152 // remove the entry from all new buckets
153 for (int bucket
= 0; bucket
< ADDRMAN_NEW_BUCKET_COUNT
; bucket
++) {
154 int pos
= info
.GetBucketPosition(nKey
, true, bucket
);
155 if (vvNew
[bucket
][pos
] == nId
) {
156 vvNew
[bucket
][pos
] = -1;
162 assert(info
.nRefCount
== 0);
164 // which tried bucket to move the entry to
165 int nKBucket
= info
.GetTriedBucket(nKey
);
166 int nKBucketPos
= info
.GetBucketPosition(nKey
, false, nKBucket
);
168 // first make space to add it (the existing tried entry there is moved to new, deleting whatever is there).
169 if (vvTried
[nKBucket
][nKBucketPos
] != -1) {
170 // find an item to evict
171 int nIdEvict
= vvTried
[nKBucket
][nKBucketPos
];
172 assert(mapInfo
.count(nIdEvict
) == 1);
173 CAddrInfo
& infoOld
= mapInfo
[nIdEvict
];
175 // Remove the to-be-evicted item from the tried set.
176 infoOld
.fInTried
= false;
177 vvTried
[nKBucket
][nKBucketPos
] = -1;
180 // find which new bucket it belongs to
181 int nUBucket
= infoOld
.GetNewBucket(nKey
);
182 int nUBucketPos
= infoOld
.GetBucketPosition(nKey
, true, nUBucket
);
183 ClearNew(nUBucket
, nUBucketPos
);
184 assert(vvNew
[nUBucket
][nUBucketPos
] == -1);
186 // Enter it into the new set again.
187 infoOld
.nRefCount
= 1;
188 vvNew
[nUBucket
][nUBucketPos
] = nIdEvict
;
191 assert(vvTried
[nKBucket
][nKBucketPos
] == -1);
193 vvTried
[nKBucket
][nKBucketPos
] = nId
;
195 info
.fInTried
= true;
198 void CAddrMan::Good_(const CService
& addr
, int64_t nTime
)
201 CAddrInfo
* pinfo
= Find(addr
, &nId
);
203 // if not found, bail out
207 CAddrInfo
& info
= *pinfo
;
209 // check whether we are talking about the exact same CService (including same port)
214 info
.nLastSuccess
= nTime
;
215 info
.nLastTry
= nTime
;
217 // nTime is not updated here, to avoid leaking information about
218 // currently-connected peers.
220 // if it is already in the tried set, don't do anything else
224 // find a bucket it is in now
225 int nRnd
= GetRandInt(ADDRMAN_NEW_BUCKET_COUNT
);
227 for (unsigned int n
= 0; n
< ADDRMAN_NEW_BUCKET_COUNT
; n
++) {
228 int nB
= (n
+ nRnd
) % ADDRMAN_NEW_BUCKET_COUNT
;
229 int nBpos
= info
.GetBucketPosition(nKey
, true, nB
);
230 if (vvNew
[nB
][nBpos
] == nId
) {
236 // if no bucket is found, something bad happened;
237 // TODO: maybe re-add the node, but for now, just bail out
241 LogPrint("addrman", "Moving %s to tried\n", addr
.ToString());
243 // move nId to the tried tables
244 MakeTried(info
, nId
);
247 bool CAddrMan::Add_(const CAddress
& addr
, const CNetAddr
& source
, int64_t nTimePenalty
)
249 if (!addr
.IsRoutable())
254 CAddrInfo
* pinfo
= Find(addr
, &nId
);
257 // periodically update nTime
258 bool fCurrentlyOnline
= (GetAdjustedTime() - addr
.nTime
< 24 * 60 * 60);
259 int64_t nUpdateInterval
= (fCurrentlyOnline
? 60 * 60 : 24 * 60 * 60);
260 if (addr
.nTime
&& (!pinfo
->nTime
|| pinfo
->nTime
< addr
.nTime
- nUpdateInterval
- nTimePenalty
))
261 pinfo
->nTime
= max((int64_t)0, addr
.nTime
- nTimePenalty
);
264 pinfo
->nServices
|= addr
.nServices
;
266 // do not update if no new information is present
267 if (!addr
.nTime
|| (pinfo
->nTime
&& addr
.nTime
<= pinfo
->nTime
))
270 // do not update if the entry was already in the "tried" table
274 // do not update if the max reference count is reached
275 if (pinfo
->nRefCount
== ADDRMAN_NEW_BUCKETS_PER_ADDRESS
)
278 // stochastic test: previous nRefCount == N: 2^N times harder to increase it
280 for (int n
= 0; n
< pinfo
->nRefCount
; n
++)
282 if (nFactor
> 1 && (GetRandInt(nFactor
) != 0))
285 pinfo
= Create(addr
, source
, &nId
);
286 pinfo
->nTime
= max((int64_t)0, (int64_t)pinfo
->nTime
- nTimePenalty
);
291 int nUBucket
= pinfo
->GetNewBucket(nKey
, source
);
292 int nUBucketPos
= pinfo
->GetBucketPosition(nKey
, true, nUBucket
);
293 if (vvNew
[nUBucket
][nUBucketPos
] != nId
) {
294 bool fInsert
= vvNew
[nUBucket
][nUBucketPos
] == -1;
296 CAddrInfo
& infoExisting
= mapInfo
[vvNew
[nUBucket
][nUBucketPos
]];
297 if (infoExisting
.IsTerrible() || (infoExisting
.nRefCount
> 1 && pinfo
->nRefCount
== 0)) {
298 // Overwrite the existing new table entry.
303 ClearNew(nUBucket
, nUBucketPos
);
305 vvNew
[nUBucket
][nUBucketPos
] = nId
;
307 if (pinfo
->nRefCount
== 0) {
315 void CAddrMan::Attempt_(const CService
& addr
, int64_t nTime
)
317 CAddrInfo
* pinfo
= Find(addr
);
319 // if not found, bail out
323 CAddrInfo
& info
= *pinfo
;
325 // check whether we are talking about the exact same CService (including same port)
330 info
.nLastTry
= nTime
;
334 CAddrInfo
CAddrMan::Select_()
339 // Use a 50% chance for choosing between tried and new table entries.
340 if (nTried
> 0 && (nNew
== 0 || GetRandInt(2) == 0)) {
342 double fChanceFactor
= 1.0;
344 int nKBucket
= GetRandInt(ADDRMAN_TRIED_BUCKET_COUNT
);
345 int nKBucketPos
= GetRandInt(ADDRMAN_BUCKET_SIZE
);
346 if (vvTried
[nKBucket
][nKBucketPos
] == -1)
348 int nId
= vvTried
[nKBucket
][nKBucketPos
];
349 assert(mapInfo
.count(nId
) == 1);
350 CAddrInfo
& info
= mapInfo
[nId
];
351 if (GetRandInt(1 << 30) < fChanceFactor
* info
.GetChance() * (1 << 30))
353 fChanceFactor
*= 1.2;
357 double fChanceFactor
= 1.0;
359 int nUBucket
= GetRandInt(ADDRMAN_NEW_BUCKET_COUNT
);
360 int nUBucketPos
= GetRandInt(ADDRMAN_BUCKET_SIZE
);
361 if (vvNew
[nUBucket
][nUBucketPos
] == -1)
363 int nId
= vvNew
[nUBucket
][nUBucketPos
];
364 assert(mapInfo
.count(nId
) == 1);
365 CAddrInfo
& info
= mapInfo
[nId
];
366 if (GetRandInt(1 << 30) < fChanceFactor
* info
.GetChance() * (1 << 30))
368 fChanceFactor
*= 1.2;
374 int CAddrMan::Check_()
376 std::set
<int> setTried
;
377 std::map
<int, int> mapNew
;
379 if (vRandom
.size() != nTried
+ nNew
)
382 for (std::map
<int, CAddrInfo
>::iterator it
= mapInfo
.begin(); it
!= mapInfo
.end(); it
++) {
384 CAddrInfo
& info
= (*it
).second
;
386 if (!info
.nLastSuccess
)
392 if (info
.nRefCount
< 0 || info
.nRefCount
> ADDRMAN_NEW_BUCKETS_PER_ADDRESS
)
396 mapNew
[n
] = info
.nRefCount
;
398 if (mapAddr
[info
] != n
)
400 if (info
.nRandomPos
< 0 || info
.nRandomPos
>= vRandom
.size() || vRandom
[info
.nRandomPos
] != n
)
402 if (info
.nLastTry
< 0)
404 if (info
.nLastSuccess
< 0)
408 if (setTried
.size() != nTried
)
410 if (mapNew
.size() != nNew
)
413 for (int n
= 0; n
< ADDRMAN_TRIED_BUCKET_COUNT
; n
++) {
414 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
415 if (vvTried
[n
][i
] != -1) {
416 if (!setTried
.count(vvTried
[n
][i
]))
418 if (mapInfo
[vvTried
[n
][i
]].GetTriedBucket(nKey
) != n
)
420 if (mapInfo
[vvTried
[n
][i
]].GetBucketPosition(nKey
, false, n
) != i
)
422 setTried
.erase(vvTried
[n
][i
]);
427 for (int n
= 0; n
< ADDRMAN_NEW_BUCKET_COUNT
; n
++) {
428 for (int i
= 0; i
< ADDRMAN_BUCKET_SIZE
; i
++) {
429 if (vvNew
[n
][i
] != -1) {
430 if (!mapNew
.count(vvNew
[n
][i
]))
432 if (mapInfo
[vvNew
[n
][i
]].GetBucketPosition(nKey
, true, n
) != i
)
434 if (--mapNew
[vvNew
[n
][i
]] == 0)
435 mapNew
.erase(vvNew
[n
][i
]);
451 void CAddrMan::GetAddr_(std::vector
<CAddress
>& vAddr
)
453 unsigned int nNodes
= ADDRMAN_GETADDR_MAX_PCT
* vRandom
.size() / 100;
454 if (nNodes
> ADDRMAN_GETADDR_MAX
)
455 nNodes
= ADDRMAN_GETADDR_MAX
;
457 // gather a list of random nodes, skipping those of low quality
458 for (unsigned int n
= 0; n
< vRandom
.size(); n
++) {
459 if (vAddr
.size() >= nNodes
)
462 int nRndPos
= GetRandInt(vRandom
.size() - n
) + n
;
463 SwapRandom(n
, nRndPos
);
464 assert(mapInfo
.count(vRandom
[n
]) == 1);
466 const CAddrInfo
& ai
= mapInfo
[vRandom
[n
]];
467 if (!ai
.IsTerrible())
472 void CAddrMan::Connected_(const CService
& addr
, int64_t nTime
)
474 CAddrInfo
* pinfo
= Find(addr
);
476 // if not found, bail out
480 CAddrInfo
& info
= *pinfo
;
482 // check whether we are talking about the exact same CService (including same port)
487 int64_t nUpdateInterval
= 20 * 60;
488 if (nTime
- info
.nTime
> nUpdateInterval
)