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

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(a)redhat.com&gt; --- 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, +};

/** * 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);