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

[hyc@symas.com]

Sergio.Gelato@astro.su.se wrote:
> 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.)

I see no patch nor URL.

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/