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

[Sergio.Gelato@astro.su.se]

Full_Name: Sergio Gelato
Version: 2.4.40
OS: Linux
URL: ftp://ftp.openldap.org/incoming/
Submission from: (NULL) (85.225.123.9)


As currently implemented (since ITS#7027,
5de85b922aaa5bfa6eb53db6000adf01ebdb0736) the algorithm to shuffle DNS SRV
records of a given priority according to their weights is flawed: if all records
have the same weight, the implementation is biased towards the first record and
against the last. In the most extreme case of two records of weight 1, the
current implementation will never swap them (whereas one would have hoped for a
swap 50% of the time). The problem can be cured by changing (r <= 0) to (r < 0).
(The wording of the RFC may have contributed to this error; I suspect it was
written with real random deviates in mind, not integer ones. In any event, the
principle that records of equal weight should have the same probability of being
picked trumps the RFC since the latter only says what algorithm SHOULD be
used.)

I've written and tested a patch for this and found it to solve the above
problem. My patch also addresses another (operationally minor, which is why I'm
not reporting it separately) issue in the same piece of code: what if at least
two, but not all, of the records of a given priority have weight zero? One
should be prepared to switch to a Fisher-Yates shuffle if "total" becomes zero
during the iteration. 

(Yet another potential issue is overflow of "total" on platforms where
INT_MAX==32767 if the sum of the weights exceeds that value. Consider declaring
it uint32_t or u_long.)