[ltt-dev] [PATCH 4/9] new random generator

[laijs@cn.fujitsu.com (Lai Jiangshan)]

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)
+
+	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