[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