https://bugs.openldap.org/show_bug.cgi?id=8204

Quanah Gibson-Mount quanah@openldap.org changed:

What |Removed |Added ---------------------------------------------------------------------------- Resolution|--- |TEST Keywords|OL_2_5_REQ | Status|IN_PROGRESS |RESOLVED

--- Comment #5 from Quanah Gibson-Mount quanah@openldap.org --- • ee7502ac by Sergio Gelato at 2020-06-22T17:27:30+00:00 ITS#8204 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.

• 8006ee58 by Sergio Gelato at 2020-06-22T17:27:30+00:00 ITS#8204 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).