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@xxxxxxxxxx>
> ---
>
> 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 :|
--
libvir-list mailing list
libvir-list@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/libvir-list