addrman: use uniform sampling inside buckets #36449

sipa commented at 8:35 PM on October 6, 2026: member

The current way we sample from addresses within a bucket in addrman is randomized, but not perfectly random. It uses a linear scan, starting at a random position (out of the 64 positions in a bucket). This means that if for example only position 17 and 20 contain an address, 17 will be picked with probability 95.3% (whenever the initial position is 21..63 or 0..17) and 20 will be picked with probability 4.7% (whenever the initial position is 18..20).

Make this search perfectly uniform, regardless of distribution of addresses within the bucket, by first copying all non-empty positions to a temporary array, and then selecting uniformly randomly from that array.

Suggested by Crypt-iQ. Also pointed out earlier by mzumsande in #23140 (review).

DrahtBot added the label P2P on Oct 6, 2026

DrahtBot commented at 8:35 PM on October 6, 2026: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

External sites

Code coverage & benchmarks: https://corecheck.dev/bitcoin/bitcoin/pulls/36449
Ralph review <img src=https://review.fish.foo/assets/bitcoin/bitcoin/36449.png alt="Ralph review status"> https://git.fish.foo/bitcoin/bitcoin/pulls/36449#author-ralph

Reviews

See the guideline and AI policy for information on the review process.

Type	Reviewers
ACK	Crypt-iQ
Stale ACK	stratospher, 0xB10C, instagibbs, Grace-Ujah, darosior, Hamza1610

If your review is incorrectly listed, please copy-paste <code></code> into the comment that the bot should ignore.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#35750 <img src="https://drahtbot.space/ack_count/bitcoin/bitcoin/35750.svg"> (addrman: make m_last_good network-specific by mzumsande)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label CI failed on Oct 6, 2026

DrahtBot commented at 9:47 PM on October 6, 2026: contributor

🚧 At least one of the CI tasks failed. Task Alpine (musl): https://github.com/bitcoin/bitcoin/actions/runs/37527619279/job/112488519074 LLM reason (✨ experimental): CI failed because the addrman_tests CTest test failed; the test module reported one failure.

<details><summary>Hints</summary>

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

</details>

in src/addrman.cpp:748 in 8a93c8bc9a outdated

 743 | -        nid_type node_id;
 744 | -        for (i = 0; i < ADDRMAN_BUCKET_SIZE; ++i) {
 745 | -            position = (initial_position + i) % ADDRMAN_BUCKET_SIZE;
 746 | -            node_id = GetEntry(search_tried, bucket, position);
 747 | -            if (node_id != -1) {
 748 | -                if (!networks.empty()) {

Hamza1610 commented at 11:37 PM on October 6, 2026:

Aproach ACK 8a93c8b I think this is a good approach, but I noticed you omitted the network filtering block, and after I reviewing, it seems this is a very important part, omitting it might cause peers to be selected from unwanted network. Also partly the reason why the CI test is failing

sipa commented at 1:53 PM on October 7, 2026:

Thank you, fixed.

is9816998-byte commented at 5:51 PM on October 7, 2026:

Thanks 😊😊

mzumsande commented at 9:45 AM on October 7, 2026: contributor

Some old discussion about this in 23140.

sedited requested review from Crypt-iQ on Oct 7, 2026

sipa force-pushed on Oct 7, 2026

DrahtBot removed the label CI failed on Oct 7, 2026

darosior commented at 2:44 PM on October 7, 2026: member

Concept ACK

in src/addrman.cpp:740 in 5db07e1795

 755 | -        }
 756 |  
 757 | -        // If the bucket is entirely empty, start over with a (likely) different one.
 758 | -        if (i == ADDRMAN_BUCKET_SIZE) continue;
 759 | +        // Copy the buckets over to a temporary buffer, so we can pick a random one.
 760 | +        int copied_bucket[64];

darosior commented at 2:50 PM on October 7, 2026:

Can you use the ADDRMAN_BUCKET_SIZE constant instead of its value here?

0xB10C commented at 2:52 PM on October 7, 2026:

Why 64 here and not:

        int copied_bucket[ADDRMAN_BUCKET_SIZE];

darosior commented at 2:54 PM on October 7, 2026:

Also, these should be int64's since #30568

sipa commented at 2:55 PM on October 7, 2026:

Good catch, done.

sipa commented at 2:58 PM on October 7, 2026:

Indeed, why not? Done.

sipa commented at 3:01 PM on October 7, 2026:

Done (through nid_type).

Hamza1610 commented at 2:52 PM on October 7, 2026: none

Concept ACK

sipa force-pushed on Oct 7, 2026

in src/addrman.cpp:749 in 4c1db4ce28

 764 | +        for (int i = 0; i < ADDRMAN_BUCKET_SIZE; ++i) {
 765 | +            auto node_id = GetEntry(search_tried, bucket, i);
 766 | +            if (node_id != -1) copied_bucket[copied_count++] = node_id;
 767 | +        }
 768 | +        // Then try to find a random non-filtered one among them.
 769 | +        int node_id = -1;

0xB10C commented at 2:58 PM on October 7, 2026:

and

        nid_type node_id = -1;

sipa commented at 3:00 PM on October 7, 2026:

Beat you to it!

sipa force-pushed on Oct 7, 2026

DrahtBot added the label CI failed on Oct 7, 2026

DrahtBot removed the label CI failed on Oct 7, 2026

darosior approved

darosior commented at 5:14 PM on October 7, 2026: member

ACK 06f581cd2f8ff9e6db233a6d5c9494b5e8afabfa

DrahtBot requested review from Hamza1610 on Oct 7, 2026

instagibbs commented at 5:45 PM on October 7, 2026: member

concept ACK

Hamza1610 commented at 6:14 PM on October 7, 2026: none

ACK https://github.com/bitcoin/bitcoin/commit/06f581cd2f8ff9e6db233a6d5c9494b5e8afabfa

DrahtBot requested review from instagibbs on Oct 7, 2026

in src/addrman.cpp:736 in 06f581cd2f

 734 | @@ -735,27 +735,35 @@ std::pair<CAddress, NodeSeconds> AddrManImpl::Select_(bool new_only, const std::
 735 |      while (1) {
 736 |          // Pick a bucket, and an initial position in that bucket.

0xB10C commented at 6:22 PM on October 7, 2026:

nit if you retouch

        // Pick a bucket.

0xB10C commented at 6:42 PM on October 7, 2026: contributor

ACK 06f581cd2f8ff9e6db233a6d5c9494b5e8afabfa

sipa force-pushed on Oct 7, 2026

DrahtBot added the label CI failed on Oct 7, 2026

stratospher commented at 7:25 PM on October 7, 2026: contributor

ACK 6c8ea01. nice! checked this in the addrman of a long running node and it helped sampling the addresses from the tried table buckets better (but not the new table since it's buckets was already full). it also helped in a newly spawned node's new table.

<details> <summary>rough benchmarks in case anyone is interested. it's only a few nanoseconds slower which is alright.</summary>

PR

$ build-bench/bin/bench_bitcoin -filter='AddrManSelect.*' -min-time=2000

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|              192.62 |        5,191,583.79 |    1.1% |      2.22 | `AddrManSelect`
|          526,764.92 |            1,898.38 |    4.3% |      2.19 | `AddrManSelectByNetwork`
|           51,666.37 |           19,354.95 |    2.4% |      2.23 | `AddrManSelectFromAlmostEmpty`

master

$ build-bench/bin/bench_bitcoin -filter='AddrManSelect.*' -min-time=2000

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               75.81 |       13,190,870.46 |    0.1% |      2.20 | `AddrManSelect`
|          494,987.06 |            2,020.25 |    1.2% |      2.14 | `AddrManSelectByNetwork`
|           59,090.16 |           16,923.29 |    2.0% |      2.20 | `AddrManSelectFromAlmostEmpty`

</details>

addrman: use uniform sampling inside buckets 9a0e095c68

DrahtBot requested review from Hamza1610 on Oct 7, 2026

DrahtBot requested review from 0xB10C on Oct 7, 2026

DrahtBot requested review from darosior on Oct 7, 2026

0xB10C commented at 7:37 PM on October 7, 2026: contributor

re-ACK 6c8ea014e8df09e486ca803db86f962110dd932a

sipa force-pushed on Oct 7, 2026

DrahtBot requested review from stratospher on Oct 7, 2026

sipa commented at 7:43 PM on October 7, 2026: member

Added an (LLM written) test for the statistical properties too now, as I've actually broken it briefly while addressing a nit.

Not planning any further changes or nit addressing unless I need to retouch for other reasons.

instagibbs commented at 8:41 PM on October 7, 2026: member

ACK 9b5fb8802aab329c1be3637dc1dca5897a9b60bf

Check test failed on master and with the bug from earlier push.

unit test is a bit slow but im unsure if that's an issue

DrahtBot removed the label CI failed on Oct 7, 2026

Grace-Ujah commented at 11:49 AM on October 8, 2026: none

ACK 9b5fb8802aab329c1be3637dc1dca5897a9b60bf

Hamza1610 commented at 12:56 PM on October 8, 2026: none

reACK 9b5fb88

darosior approved

darosior commented at 6:45 PM on October 9, 2026: member

reACK 9b5fb8802aab329c1be3637dc1dca5897a9b60bf

sedited commented at 7:44 PM on October 9, 2026: contributor

unit test is a bit slow but im unsure if that's an issue

Taken from the alpine musl job (which has debug on): On master: Test #225: addrman_tests .............................................................. Passed 0.44 sec This PR: Test #225: addrman_tests .............................................................. Passed 137.75 sec

That might be a bit excessive.

sipa force-pushed on Oct 9, 2026

sipa commented at 8:29 PM on October 9, 2026: member

@sedited Ugh, should be better now. But I don't actually see the addrman_tests runtime appear in the musl CI log. In a debug build it's around 8s now for me.

sipa force-pushed on Oct 9, 2026

DrahtBot added the label CI failed on Oct 9, 2026

sedited commented at 8:44 PM on October 9, 2026: contributor

But I don't actually see the addrman_tests runtime appear in the musl CI log. In a debug build it's around 8s now for me.

It is here in the current CI run wth a similar run time: https://github.com/bitcoin/bitcoin/actions/runs/37987436392/job/114013245860?pr=36449#step:11:3013

DrahtBot removed the label CI failed on Oct 9, 2026

darosior approved

darosior commented at 10:37 PM on October 11, 2026: member

reACK bb7b5613de7af2ac9f5fc3e6641f5afbf8397407

DrahtBot requested review from Grace-Ujah on Oct 11, 2026

fanquake added this to the milestone 33.0 on Oct 12, 2026

Hamza1610 commented at 12:42 PM on October 12, 2026: none

ACK bb7b5613de7af2ac9f5fc3e6641f5afbf8397407

in src/test/fuzz/addrman.cpp:191 in bb7b5613de outdated

 185 | @@ -186,7 +186,9 @@ FUZZ_TARGET(addrman, .init = initialize_addrman)
 186 |              nets.insert(net);
 187 |          }
 188 |      }
 189 | -    (void)const_addr_man.Select(fuzzed_data_provider.ConsumeBool(), nets);
 190 | +    const CAddress selected{const_addr_man.Select(fuzzed_data_provider.ConsumeBool(), nets).first};
 191 | +    // If a network filter was provided, the selected address (if any) must match it.
 192 | +    if (!nets.empty() && selected.IsValid()) assert(nets.contains(selected.GetNetwork()));

Crypt-iQ commented at 2:25 PM on October 14, 2026:

q: does every address returned from Select pass IsValid?

sipa commented at 12:59 AM on October 15, 2026:

Good point. I've changed the test.

in src/test/addrman_tests.cpp:375 in bb7b5613de

 370 | +            ++counts[it - matching.begin()];
 371 | +        }
 372 | +        // Compare the counts with a uniform distribution using a chi-square test. The critical
 373 | +        // values correspond to a false positive probability of 1e-9, for 1, 2, and 3 degrees of
 374 | +        // freedom respectively.
 375 | +        constexpr std::array<double, 3> CHI_SQUARE_CRITICAL{37.32, 41.45, 44.84};

Crypt-iQ commented at 3:17 PM on October 14, 2026:

nit: middle value unused?

sipa commented at 1:00 AM on October 15, 2026:

Rewritten without the middle value.

test: check network filtering and uniformity of addrman Select

Add a unit test that places IPv4 and IPv6 addresses at chosen positions
within a single new bucket, and verifies (using a chi-square test) that
Select() returns only entries matching the requested networks, each with
equal probability.

Also make the addrman fuzz target assert that Select() returns an address
if and only if there are entries matching the filters, and that the
returned address matches the network filter, if one is provided.

5aaaf7b8d1

sipa force-pushed on Oct 15, 2026

Crypt-iQ commented at 1:13 PM on October 15, 2026: contributor

crACK 5aaaf7b8d1ed72b7ab9eee117204f4c4346eb235

DrahtBot requested review from darosior on Oct 15, 2026