[libvirt] [PATCH] random: don't mix RAND_MAX with random_r

[Daniel P. Berrange]

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 at 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 :|