From 4df30371eb6b8fa4674fbbac2524e62bc16278c8 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Vladim=C3=ADr=20=C4=8Cun=C3=A1t?= <vladimir.cunat@nic.cz>
Date: Tue, 24 Sep 2019 15:17:41 +0200
Subject: [PATCH] lib/nsrep: randomize the order of NS names

... as input into the *unchanged* algorithm (which is ugly).
This partially addresses the problem attempted by reverted commit,
and it also improves some other properties of the algorithm.
---
 NEWS        |  1 +
 lib/nsrep.c | 40 ++++++++++++++++++++++++++++++++--------
 2 files changed, 33 insertions(+), 8 deletions(-)

diff --git a/NEWS b/NEWS
index 9b08ef41f..6aa4f6ff3 100644
--- a/NEWS
+++ b/NEWS
@@ -8,6 +8,7 @@ Bugfixes
   (regression since 4.1.0 release, in less common cases)
 - prefill module: allow a different module-loading style (#506)
 - validation: trim TTLs by RRSIG's expiration and original TTL (#319, #504)
+- NS choice algorithm: fix a regression since 4.0.0 (#497, !868)
 
 Improvements
 ------------
diff --git a/lib/nsrep.c b/lib/nsrep.c
index c8181318f..4db86bced 100644
--- a/lib/nsrep.c
+++ b/lib/nsrep.c
@@ -333,19 +333,43 @@ int kr_nsrep_elect(struct kr_query *qry, struct kr_context *ctx)
 		return kr_error(EINVAL);
 	}
 
-	struct kr_nsrep *ns = &qry->ns;
-	ELECT_INIT(ns, ctx);
+	// First we dump the nsset into a temporary array
+	const int nsset_len = trie_weight(qry->zone_cut.nsset);
+	struct {
+		const knot_dname_t *name;
+		const pack_t *addrs;
+	} nsset[nsset_len];
 
-	int ret = kr_ok();
 	trie_it_t *it;
+	int i = 0;
 	for (it = trie_it_begin(qry->zone_cut.nsset); !trie_it_finished(it);
-							trie_it_next(it)) {
-		ret = eval_nsrep(/* we trust it's a correct dname */
-				 (const knot_dname_t *)trie_it_key(it, NULL),
-				 (const pack_t *)*trie_it_val(it), qry);
-		if (ret) break;
+							trie_it_next(it), ++i) {
+		/* we trust it's a correct dname */
+		nsset[i].name = (const knot_dname_t *)trie_it_key(it, NULL);
+		nsset[i].addrs = (const pack_t *)*trie_it_val(it);
 	}
 	trie_it_free(it);
+	assert(i == nsset_len);
+
+	// Now we sort it randomly, by select-sort.
+	for (i = 0; i < nsset_len - 1; ++i) {
+		// The winner for position i will be uniformly chosen from indices >= i
+		const int j = i + kr_rand_bytes(1) % (nsset_len - i);
+		// Now we swap the winner with index i
+		if (i == j) continue;
+		__typeof__((nsset[i])) tmp = nsset[i];
+		nsset[i] = nsset[j];
+		nsset[j] = tmp;
+	}
+
+	// Finally we run the original algorithm, in this randomized order.
+	struct kr_nsrep *ns = &qry->ns;
+	ELECT_INIT(ns, ctx);
+	int ret = kr_ok();
+	for (i = 0; i < nsset_len; ++i) {
+		ret = eval_nsrep(nsset[i].name, nsset[i].addrs, qry);
+		if (ret) break;
+	}
 
 	if (qry->ns.score <= KR_NS_MAX_SCORE && qry->ns.score >= KR_NS_LONG) {
 		/* This is a low-reliability probe,
-- 
2.47.3