[ltt-dev] [PATCH 4/9] new random generator
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Tue Nov 15 06:17:47 EST 2011
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
> tests/test_urcu_hash.c | 131 +++++++++++++++++++++++++++++++++++++++++++++--
> 1 files changed, 125 insertions(+), 6 deletions(-)
>
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index bae6ed2..a1aa660 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -32,6 +32,8 @@
> #include <assert.h>
> #include <sched.h>
> #include <errno.h>
> +#include <sys/stat.h>
> +#include <fcntl.h>
>
> #ifdef __linux__
> #include <syscall.h>
> @@ -283,6 +285,120 @@ void rcu_copy_mutex_unlock(void)
> }
>
> /*
> + * Test random generator
> + *
> + * (copied from linux kernel)
> + *
> + * This is a maximally equidistributed combined Tausworthe generator
> + * based on code from GNU Scientific Library 1.5 (30 Jun 2004)
> + *
> + * x_n = (s1_n ^ s2_n ^ s3_n)
> + *
> + * s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
> + * s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
> + * s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
> + *
> + * The period of this generator is about 2^88.
> + *
> + * From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
> + * Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
> + *
> + * This is available on the net from L'Ecuyer's home page,
> + *
> + * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
> + * ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
> + *
> + * There is an erratum in the paper "Tables of Maximally
> + * Equidistributed Combined LFSR Generators", Mathematics of
> + * Computation, 68, 225 (1999), 261--269:
> + * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
> + *
> + * ... the k_j most significant bits of z_j must be non-
> + * zero, for each j. (Note: this restriction also applies to the
> + * computer code given in [4], but was mistakenly not mentioned in
> + * that paper.)
> + *
> + * This affects the seeding procedure by imposing the requirement
> + * s1 > 1, s2 > 7, s3 > 15.
> + *
> + */
> +
> +struct rand_state {
> + uint32_t s1, s2, s3;
> +};
> +
> +static __thread struct rand_state rand_state;
> +
> +static uint32_t test_rand_get32(void)
> +{
> + struct rand_state *state = &rand_state;
> +#define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
please add parenthesis around use of s, a, b, c, and d.
> +
> + state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
> + state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
> + state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
> +
#undef TAUSWORTHE
(if only meant to be used within this function scope)
> + return (state->s1 ^ state->s2 ^ state->s3);
> +}
> +
> +static void test_rand_init(void)
> +{
> + int urandom_fd;
> + struct rand_state *state = &rand_state;
> +
> + urandom_fd = open("/dev/urandom", O_RDONLY);
> + assert(urandom_fd > 2);
Instead of an assert, can we print a warning and fall-back on time(NULL)
instead ?
> +
> + do {
> + ssize_t size = sizeof(*state), ret;
> +
> + while (size > 0) {
> + ret = read(urandom_fd, state, size);
> + assert(ret >= 0);
> + size -= ret;
> + }
> + state->s1 ^= (uint32_t)(unsigned long)state;
> + } while (state->s1 <= 1 || state->s2 <= 7 || state->s3 <= 15);
> +
> + test_rand_get32();
> + close(urandom_fd);
> +}
> +
> +#if (CAA_BITS_PER_LONG == 32)
> +static inline unsigned long test_rand_get(void)
> +{
> + return test_rand_get32();
> +}
> +#else
> +static inline unsigned long test_rand_get(void)
> +{
> + return ((unsigned long)test_rand_get32() << 32) | test_rand_get32();
> +}
> +#endif
> +
> +static __thread uint32_t random_bits;
> +static __thread int nr_random_bits;
> +
> +static unsigned long test_rand_get_bits(int n)
I think this function should use test_rand_get(), and allow n to go up
to CAA_BITS_PER_LONG.
Thanks,
Mathieu
> +{
> + uint32_t result = random_bits;
> + int m = n;
> +
> + assert(n > 0 && n < 32);
> +
> + if (m > nr_random_bits) {
> + random_bits = test_rand_get32();
> + result |= random_bits << nr_random_bits;
> + m -= nr_random_bits;
> + nr_random_bits = 32;
> + }
> +
> + random_bits >>= m;
> + nr_random_bits -= m;
> + return result & ((1UL << n) - 1);
> +}
> +
> +/*
> * Hash function
> * Source: http://burtleburtle.net/bob/c/lookup3.c
> * Originally Public Domain
> @@ -495,6 +611,7 @@ void *thr_reader(void *_count)
> "reader", pthread_self(), (unsigned long)gettid());
>
> set_affinity();
> + test_rand_init();
>
> rcu_register_thread();
>
> @@ -506,7 +623,7 @@ void *thr_reader(void *_count)
> for (;;) {
> rcu_read_lock();
> cds_lfht_test_lookup(test_ht,
> - (void *)(((unsigned long) rand_r(&rand_lookup) % lookup_pool_size) + lookup_pool_offset),
> + (void *)((test_rand_get() % lookup_pool_size) + lookup_pool_offset),
> sizeof(void *), &iter);
> node = cds_lfht_iter_get_test_node(&iter);
> if (node == NULL) {
> @@ -560,6 +677,7 @@ void *thr_writer(void *_count)
> "writer", pthread_self(), (unsigned long)gettid());
>
> set_affinity();
> + test_rand_init();
>
> rcu_register_thread();
>
> @@ -570,10 +688,10 @@ void *thr_writer(void *_count)
>
> for (;;) {
> if ((addremove == AR_ADD || add_only)
> - || (addremove == AR_RANDOM && rand_r(&rand_lookup) & 1)) {
> + || (addremove == AR_RANDOM && test_rand_get_bits(1))) {
> node = malloc(sizeof(struct lfht_test_node));
> lfht_test_node_init(node,
> - (void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
> + (void *)((test_rand_get() % write_pool_size) + write_pool_offset),
> sizeof(void *));
> rcu_read_lock();
> if (add_unique) {
> @@ -607,7 +725,7 @@ void *thr_writer(void *_count)
> /* May delete */
> rcu_read_lock();
> cds_lfht_test_lookup(test_ht,
> - (void *)(((unsigned long) rand_r(&rand_lookup) % write_pool_size) + write_pool_offset),
> + (void *)((test_rand_get() % write_pool_size) + write_pool_offset),
> sizeof(void *), &iter);
> ret = cds_lfht_del(test_ht, &iter);
> rcu_read_unlock();
> @@ -622,7 +740,7 @@ void *thr_writer(void *_count)
> //if (nr_writes % 100000 == 0) {
> if (nr_writes % 1000 == 0) {
> rcu_read_lock();
> - if (rand_r(&rand_lookup) & 1) {
> + if (test_rand_get_bits(1)) {
> ht_resize(test_ht, 1);
> } else {
> ht_resize(test_ht, -1);
> @@ -660,6 +778,7 @@ static int populate_hash(void)
>
> if (!init_populate)
> return 0;
> + test_rand_init();
>
> if ((add_unique || add_replace) && init_populate * 10 > init_pool_size) {
> printf("WARNING: required to populate %lu nodes (-k), but random "
> @@ -670,7 +789,7 @@ static int populate_hash(void)
> while (nr_add < init_populate) {
> node = malloc(sizeof(struct lfht_test_node));
> lfht_test_node_init(node,
> - (void *)(((unsigned long) rand_r(&rand_lookup) % init_pool_size) + init_pool_offset),
> + (void *)((test_rand_get() % init_pool_size) + init_pool_offset),
> sizeof(void *));
> rcu_read_lock();
> if (add_unique) {
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list