[ltt-dev] [PATCH 4/9] new random generator
Lai Jiangshan
laijs at cn.fujitsu.com
Sun Nov 13 23:50:54 EST 2011
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
More information about the lttng-dev
mailing list