From mboxrd@z Thu Jan 1 00:00:00 1970 From: laijs@cn.fujitsu.com (Lai Jiangshan) Date: Mon, 14 Nov 2011 12:50:54 +0800 Subject: [ltt-dev] [PATCH 4/9] new random generator In-Reply-To: <1321246259-21223-1-git-send-email-laijs@cn.fujitsu.com> References: <1321246259-21223-1-git-send-email-laijs@cn.fujitsu.com> Message-ID: <1321246259-21223-5-git-send-email-laijs@cn.fujitsu.com> 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) + + 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); + + 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); + + 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) +{ + 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