]> git.ipfire.org Git - thirdparty/bind9.git/commit
[9.20] chg: dev: Implement Fisher-Yates shuffle for nameserver selection
authorOndřej Surý <ondrej@isc.org>
Thu, 26 Feb 2026 08:13:34 +0000 (09:13 +0100)
committerOndřej Surý <ondrej@isc.org>
Thu, 26 Feb 2026 08:13:34 +0000 (09:13 +0100)
commitdd453590a0e985dc2ea6af54b1907a2f1a9daca1
tree706277e0fb5b7a710ee70060c288c3520c35c65a
parent9901ca97a42fba4974f30217453450e867a507c3
parentd85889710baf7fd8b00f932562127a27a83bff00
[9.20] chg: dev: 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 partial
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
introduces fctx_getaddresses_nsorder() to perform an in-place
randomization of indices into a bounded, stack-allocated lookup array
(nsorder) representing the "winning" fetch slots.

The nameserver dataset is now traversed in exactly one sequential pass:
1. Every nameserver is evaluated for local cached data.
2. If the current nameserver's sequential index exists in the randomized
   nsorder array, it is permitted to launch an outgoing network fetch.
3. If not, it is restricted to local lookups via DNS_ADBFIND_NOFETCH.

This guarantees a fair random distribution for outbound queries while
maximizing local cache hits, entirely within O(1) memory and without
the overhead of linked-list pointer shuffling or dynamic allocation.

Closes #5695

Backport of MR !11604

Merge branch 'backport-5695-refactor-the-random-NS-selection-9.20' into 'bind-9.20'

See merge request isc-projects/bind9!11606