--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 <[email protected]> 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 <[email protected]> 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--
