[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]

*From*: "Daniel P. Berrange" <berrange redhat com>*To*: Eric Blake <eblake redhat com>*Cc*: libvir-list redhat com, jgh freebsd org*Subject*: Re: [libvirt] [PATCH] random: don't mix RAND_MAX with random_r*Date*: Fri, 30 Aug 2013 10:36:45 +0100

On Thu, Aug 29, 2013 at 05:19:21PM -0600, Eric Blake wrote: > FreeBSD 10 recently changed their definition of RAND_MAX, to try > and cover the fact that their evenly distributed results really are > a smaller range than a full power of 2. As a result, I did some > investigation, and learned: > > 1. POSIX requires random() to be evenly distributed across exactly > 31 bits. glibc also guarantees this for rand(), but the two are > unrelated, and POSIX only associates RAND_MAX with rand(). > Avoiding RAND_MAX altogether thus avoids a build failure on > FreeBSD 10. > > 2. Concatenating random bits from a PRNG will NOT provide uniform > coverage over the larger value UNLESS the period of the original > PRNG is at least as large as the number of bits being concatenated. > Simple example: suppose that RAND_MAX were 1 with a period of 2**1 > (which means that the PRNG merely alternates between 0 and 1). > Concatenating two successive rand() calls would then invariably > result in 01 or 10, which is a rather non-uniform distribution > (00 and 11 are impossible) and an even worse period (2**0, since > our second attempt will get the same number as our first attempt). > But a RAND_MAX of 1 with a period of 2**2 (alternating between > 0, 1, 1, 0) provides sane coverage of all four values, if properly > tempered. (Back-to-back calls would still only see half the values > if we don't do some tempering). We therefore want to guarantee a > period of at least 2**64, preferably larger (as a tempering factor); > POSIX only makes this guarantee for random() with 256 bytes of info. > > * src/util/virrandom.c (virRandomBits): Use constants that are > accurate for the PRNG we are using, not an unrelated PRNG. > (randomState): Ensure the period of our PRNG exceeds our usage. > > Signed-off-by: Eric Blake <eblake redhat com> > --- > > I debated pushing this under the build-breaker rule, but would > like to get feedback from an actual FreeBSD build first if possible. > > src/util/virrandom.c | 28 +++++++++++++++++++--------- > 1 file changed, 19 insertions(+), 9 deletions(-) > > diff --git a/src/util/virrandom.c b/src/util/virrandom.c > index c233732..37d1a82 100644 > --- a/src/util/virrandom.c > +++ b/src/util/virrandom.c > @@ -1,5 +1,5 @@ > /* > - * Copyright (C) 2012 Red Hat, Inc. > + * Copyright (C) 2012-2013 Red Hat, Inc. > * > * This library is free software; you can redistribute it and/or > * modify it under the terms of the GNU Lesser General Public > @@ -36,7 +36,7 @@ > > #define VIR_FROM_THIS VIR_FROM_NONE > > -static char randomState[128]; > +static char randomState[256]; > static struct random_data randomData; > static virMutex randomLock; > > @@ -70,9 +70,20 @@ virRandomOnceInit(void) > > VIR_ONCE_GLOBAL_INIT(virRandom) > > -/* The algorithm of virRandomBits requires that RAND_MAX == 2^n-1 for > - * some n; gnulib's random_r meets this property. */ > -verify(((RAND_MAX + 1U) & RAND_MAX) == 0); > +/* The algorithm of virRandomBits relies on gnulib's guarantee that > + * random_r() matches the POSIX requirements on random() of being > + * evenly distributed among exactly [0, 2**31) (that is, we always get > + * exactly 31 bits). While this happens to be the value of RAND_MAX > + * on glibc, note that POSIX only requires RAND_MAX to be tied to the > + * weaker rand(), so there are platforms where RAND_MAX is smaller > + * than the range of random_r(). For the results to be evenly > + * distributed among up to 64 bits, we also rely on the period of > + * random_r() to be at least 2**64, which POSIX only guarantees for > + * random() if you use 256 bytes of state. */ > +enum { > + RANDOM_BITS_PER_ITER = 31, > + RANDOM_BITS_MASK = (1U << RANDOM_BITS_PER_ITER) - 1, > +}; Using an enum feels a bit wierd for this. Seems like these are simply 2 constants to #define. > > /** > * virRandomBits: > @@ -85,7 +96,6 @@ verify(((RAND_MAX + 1U) & RAND_MAX) == 0); > */ > uint64_t virRandomBits(int nbits) > { > - int bits_per_iter = count_one_bits(RAND_MAX); > uint64_t ret = 0; > int32_t bits; > > @@ -98,10 +108,10 @@ uint64_t virRandomBits(int nbits) > > virMutexLock(&randomLock); > > - while (nbits > bits_per_iter) { > + while (nbits > RANDOM_BITS_PER_ITER) { > random_r(&randomData, &bits); > - ret = (ret << bits_per_iter) | (bits & RAND_MAX); > - nbits -= bits_per_iter; > + ret = (ret << RANDOM_BITS_PER_ITER) | (bits & RANDOM_BITS_MASK); > + nbits -= RANDOM_BITS_PER_ITER; > } > > random_r(&randomData, &bits); ACK whether you change the enum or not. Daniel -- |: http://berrange.com -o- http://www.flickr.com/photos/dberrange/ :| |: http://libvirt.org -o- http://virt-manager.org :| |: http://autobuild.org -o- http://search.cpan.org/~danberr/ :| |: http://entangle-photo.org -o- http://live.gnome.org/gtk-vnc :|

**Follow-Ups**:**Re: [libvirt] [PATCH] random: don't mix RAND_MAX with random_r***From:*Eric Blake

**References**:**[libvirt] [PATCH] random: don't mix RAND_MAX with random_r***From:*Eric Blake