diff options
author | Pieter Wuille <pieter@wuille.net> | 2021-09-29 16:22:44 -0400 |
---|---|---|
committer | Pieter Wuille <pieter@wuille.net> | 2021-10-05 11:48:09 -0400 |
commit | 632aad9e6d8369750f4327a886ca5b3d3fed89bd (patch) | |
tree | ac81634d4607183d7ecc8a3b21adcbb73f38ccea | |
parent | 113b863f0773999497f952daa6539a03a66a9de3 (diff) | |
download | bitcoin-632aad9e6d8369750f4327a886ca5b3d3fed89bd.tar.xz |
Make CAddrman::Select_ select buckets, not positions, first
The original CAddrMan behaviour (before commit
e6b343d880f50d52390c5af8623afa15fcbc65a2) was to pick a uniformly
random non-empty bucket, and then pick a random element from that
bucket. That commit, which introduced deterministic placement
of entries in buckets, changed this to picking a uniformly random
non-empty bucket position instead.
This commit reverts the original high-level behavior, but in the
deterministic placement model.
-rw-r--r-- | src/addrman.cpp | 32 |
1 files changed, 24 insertions, 8 deletions
diff --git a/src/addrman.cpp b/src/addrman.cpp index c364a7710b..08aae6f2a4 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -709,38 +709,54 @@ std::pair<CAddress, int64_t> AddrManImpl::Select_(bool newOnly) const // use a tried node double fChanceFactor = 1.0; while (1) { + // Pick a tried bucket, and an initial position in that bucket. int nKBucket = insecure_rand.randrange(ADDRMAN_TRIED_BUCKET_COUNT); int nKBucketPos = insecure_rand.randrange(ADDRMAN_BUCKET_SIZE); - while (vvTried[nKBucket][nKBucketPos] == -1) { - nKBucket = (nKBucket + insecure_rand.randbits(ADDRMAN_TRIED_BUCKET_COUNT_LOG2)) % ADDRMAN_TRIED_BUCKET_COUNT; - nKBucketPos = (nKBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; + // Iterate over the positions of that bucket, starting at the initial one, + // and looping around. + int i; + for (i = 0; i < ADDRMAN_BUCKET_SIZE; ++i) { + if (vvTried[nKBucket][(nKBucketPos + i) % ADDRMAN_BUCKET_SIZE] != -1) break; } - int nId = vvTried[nKBucket][nKBucketPos]; + // If the bucket is entirely empty, start over with a (likely) different one. + if (i == ADDRMAN_BUCKET_SIZE) continue; + // Find the entry to return. + int nId = vvTried[nKBucket][(nKBucketPos + i) % ADDRMAN_BUCKET_SIZE]; const auto it_found{mapInfo.find(nId)}; assert(it_found != mapInfo.end()); const AddrInfo& info{it_found->second}; + // With probability GetChance() * fChanceFactor, return the entry. if (insecure_rand.randbits(30) < fChanceFactor * info.GetChance() * (1 << 30)) { return {info, info.nLastTry}; } + // Otherwise start over with a (likely) different bucket, and increased chance factor. fChanceFactor *= 1.2; } } else { // use a new node double fChanceFactor = 1.0; while (1) { + // Pick a new bucket, and an initial position in that bucket. int nUBucket = insecure_rand.randrange(ADDRMAN_NEW_BUCKET_COUNT); int nUBucketPos = insecure_rand.randrange(ADDRMAN_BUCKET_SIZE); - while (vvNew[nUBucket][nUBucketPos] == -1) { - nUBucket = (nUBucket + insecure_rand.randbits(ADDRMAN_NEW_BUCKET_COUNT_LOG2)) % ADDRMAN_NEW_BUCKET_COUNT; - nUBucketPos = (nUBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; + // Iterate over the positions of that bucket, starting at the initial one, + // and looping around. + int i; + for (i = 0; i < ADDRMAN_BUCKET_SIZE; ++i) { + if (vvNew[nUBucket][(nUBucketPos + i) % ADDRMAN_BUCKET_SIZE] != -1) break; } - int nId = vvNew[nUBucket][nUBucketPos]; + // If the bucket is entirely empty, start over with a (likely) different one. + if (i == ADDRMAN_BUCKET_SIZE) continue; + // Find the entry to return. + int nId = vvNew[nUBucket][(nUBucketPos + i) % ADDRMAN_BUCKET_SIZE]; const auto it_found{mapInfo.find(nId)}; assert(it_found != mapInfo.end()); const AddrInfo& info{it_found->second}; + // With probability GetChance() * fChanceFactor, return the entry. if (insecure_rand.randbits(30) < fChanceFactor * info.GetChance() * (1 << 30)) { return {info, info.nLastTry}; } + // Otherwise start over with a (likely) different bucket, and increased chance factor. fChanceFactor *= 1.2; } } |