Re: (ITS#8204) rfc2782 shuffle implementation doesn't treat equal-weight records equally

[Sergio.Gelato@astro.su.se]

--tThc/1wpZn/ma/RB
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Sorry for the delay in submitting the patch. I wanted to double-check that
no third party would lay a credible claim to it.

For good measure, I have split the patch in two: the first only addresses
the primary issue, and is obviously too simple to be copyrightable. The
second addresses the need for falling back to straight Fisher-Yates in the
middle of the shuffle, and may or may not be copyrightable so I'll say this:

The attached patch files are derived from OpenLDAP Software. All of the
modifications to OpenLDAP Software represented therein were developed by
me, Sergio Gelato. I have not assigned rights and/or interest in this work
to any party. The modifications are subject to the following notice:

Copyright 2015 Sergio Gelato
Redistribution and use in source and binary forms, with or without
modification, are permitted according to the terms of the OpenLDAP
Public License.

--tThc/1wpZn/ma/RB
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment; filename="0001-Remove-bias-towards-the-first-record-in-RFC2782-shuf.patch"

>From adb64c957308e5aee08a2f8aa893992a262d3243 Mon Sep 17 00:00:00 2001
From: Sergio Gelato <Sergio.Gelato@astro.su.se>
Date: Sun, 6 Dec 2015 12:57:46 +0100
Subject: [PATCH 1/2] Remove bias towards the first record in RFC2782 shuffle
 implementation.

Prior to this change, given two records of weight 1 the algorithm would
return them in the order (0,1) with 100% probability instead of the
desired 50%. This was due to an off-by-one error in the range test.

srv_rand() returns a float in the range [0.0, 1.0[, so r is an integer in the
range [0, total[. The correct probability for record 0 to be chosen is
a[0].weight/total, not (a[0].weight+1)/total.
---
 libraries/libldap/dnssrv.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/libraries/libldap/dnssrv.c b/libraries/libldap/dnssrv.c
index da89b4a..8d30552 100644
--- a/libraries/libldap/dnssrv.c
+++ b/libraries/libldap/dnssrv.c
@@ -234,7 +234,7 @@ static void srv_shuffle(srv_record *a, int n) {
 		r = srv_rand() * total;
 		for (j=0; j<p; j++) {
 			r -= a[j].weight;
-			if (r <= 0) {
+			if (r < 0) {
 				if (j) {
 					srv_record t = a[0];
 					a[0] = a[j];
-- 
2.1.4


--tThc/1wpZn/ma/RB
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment; filename="0002-Improved-RFC2782-shuffle-when-several-but-not-all-re.patch"

>From 6a03d17188964db50a1e8fa4b1a4f24b9db7d33e Mon Sep 17 00:00:00 2001
From: Sergio Gelato <Sergio.Gelato@astro.su.se>
Date: Sun, 6 Dec 2015 13:33:17 +0100
Subject: [PATCH 2/2] Improved RFC2782 shuffle when several, but not all,
 records have weight 0.

The fallback to a straight Fisher-Yates shuffle needs to occur whenever the
sum of the *remaining* weights is zero, or else the remaining records will
not be reordered. Testing only once at the beginning covers the case when
all weights are zero, and obviously no shuffling is needed when only one
weight is zero; but other weight combinations are possible, such as (1, 0, 0).
---
 libraries/libldap/dnssrv.c | 43 +++++++++++++++++--------------------------
 1 file changed, 17 insertions(+), 26 deletions(-)

diff --git a/libraries/libldap/dnssrv.c b/libraries/libldap/dnssrv.c
index 8d30552..63a920c 100644
--- a/libraries/libldap/dnssrv.c
+++ b/libraries/libldap/dnssrv.c
@@ -216,36 +216,27 @@ static void srv_shuffle(srv_record *a, int n) {
 	for (i=0; i<n; i++)
 		total += a[i].weight;
 
-	/* all weights are zero, do a straight Fisher-Yates shuffle */
-	if (!total) {
-		while (n) {
-			srv_record t;
-			i = srv_rand() * n--;
-			t = a[n];
-			a[n] = a[i];
-			a[i] = t;
-		}
-		return;
-	}
-
 	/* Do a shuffle per RFC2782 Page 4 */
-	p = n;
-	for (i=0; i<n-1; i++) {
-		r = srv_rand() * total;
-		for (j=0; j<p; j++) {
-			r -= a[j].weight;
-			if (r < 0) {
-				if (j) {
-					srv_record t = a[0];
-					a[0] = a[j];
-					a[j] = t;
+	for (p=n; p>1; a++, p--) {
+		if (!total) {
+			/* all remaining weights are zero,
+			   do a straight Fisher-Yates shuffle */
+			j = srv_rand() * p;
+		} else {
+			r = srv_rand() * total;
+			for (j=0; j<p; j++) {
+				r -= a[j].weight;
+				if (r < 0) {
+					total -= a[j].weight;
+					break;
 				}
-				total -= a[0].weight;
-				a++;
-				p--;
-				break;
 			}
 		}
+		if (j && j<p) {
+			srv_record t = a[0];
+			a[0] = a[j];
+			a[j] = t;
+		}
 	}
 }
 #endif /* HAVE_RES_QUERY */
-- 
2.1.4


--tThc/1wpZn/ma/RB--