]> git.ipfire.org Git - thirdparty/bind9.git/commit
Implement Fisher-Yates shuffle for nameserver selection
authorOndřej Surý <ondrej@sury.org>
Wed, 25 Feb 2026 15:46:40 +0000 (16:46 +0100)
committerOndřej Surý <ondrej@isc.org>
Thu, 26 Feb 2026 07:17:23 +0000 (08:17 +0100)
commit8ddab7f0b830ba1d67f7f284f11b4ef04ff6708f
tree1a9403816bfee34e2556647f1f05149f9c4e78d9
parent9901ca97a42fba4974f30217453450e867a507c3
Implement Fisher-Yates shuffle for nameserver selection

Replace the two-pass "random start index and wrap around" logic in
fctx_getaddresses_nameservers() with a statistically sound Fisher-Yates
shuffle.

The previous implementation picked a random starting node and did two
passes over the linked list to find query candidates.  The new logic
extracts the available nameservers into a bounded, stack-allocated array
of dns_rdata_t structures.

This array is then randomized in-place using a Fisher-Yates shuffle.
Finally, the shuffled array is traversed sequentially to launch fetches
until the dynamic quota (fctx->pending_running >= fetches_allowed) is
reached.

This guarantees a fair random distribution for outbound queries while
properly respecting dynamic query limits, entirely within O(1) memory
and without the overhead of linked-list pointer shuffling or multiple
dataset traversals.

(cherry picked from commit 3c33e7d9370006b1599e3d99c0d5fa6a6dad7979)
lib/dns/resolver.c