From mboxrd@z Thu Jan 1 00:00:00 1970 From: mathieu.desnoyers@efficios.com (Mathieu Desnoyers) Date: Tue, 15 Nov 2011 06:17:47 -0500 Subject: [ltt-dev] [PATCH 4/9] new random generator In-Reply-To: <1321246259-21223-5-git-send-email-laijs@cn.fujitsu.com> References: <1321246259-21223-1-git-send-email-laijs@cn.fujitsu.com> <1321246259-21223-5-git-send-email-laijs@cn.fujitsu.com> Message-ID: <20111115111747.GC16701@Krystal> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote: > Signed-off-by: Lai Jiangshan > --- > 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 > #include > #include > +#include > +#include > > #ifdef __linux__ > #include > @@ -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)<>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