#include <urcu/arch.h>
+extern int __thread disable_debug;
+
/* hardcoded number of CPUs */
#define NR_CPUS 16384
-/* number of insert/delete */
-#define NR_RAND 4
+/* Default number of insert/delete */
+#define DEFAULT_NR_RAND 6
+
+/* Default number of global items (used by readers for lookups) */
+#define DEFAULT_NR_GLOBAL 10
#if defined(_syscall0)
_syscall0(pid_t, gettid)
#include <urcu/rcurbtree.h>
#include <urcu-defer.h>
-/* TODO: error handling testing for -ENOMEM */
-struct rcu_rbtree_node *rbtree_alloc(void)
-{
- return calloc(1, sizeof(struct rcu_rbtree_node));
-}
-
-void rbtree_free(struct rcu_head *head)
-{
- struct rcu_rbtree_node *node =
- caa_container_of(head, struct rcu_rbtree_node, head);
- free(node);
-}
-
int tree_comp(void *a, void *b)
{
if ((unsigned long)a < (unsigned long)b)
return 0;
}
-static DEFINE_RCU_RBTREE(rbtree, tree_comp, rbtree_alloc, rbtree_free);
+static DEFINE_RCU_RBTREE(rbtree, tree_comp, malloc, free, call_rcu);
static volatile int test_go, test_stop;
/* write-side C.S. duration, in loops */
static unsigned long wduration;
+static unsigned long nr_rand_items = DEFAULT_NR_RAND;
+
+static int opt_search_begin,
+ opt_search_bottom,
+ opt_search_end,
+ opt_search_mid,
+ opt_iter_min_max,
+ opt_iter_max_min,
+ opt_benchmark;
+
static inline void loop_sleep(unsigned long l)
{
- while(l-- != 0)
+ while (l-- != 0)
caa_cpu_relax();
}
static unsigned int nr_readers;
static unsigned int nr_writers;
+static unsigned long global_items = DEFAULT_NR_GLOBAL;
+static void **global_key = NULL;
+
pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
void rcu_copy_mutex_lock(void)
}
}
+static
+void set_lookup_index(struct rcu_rbtree_node *node,
+ char *lookup_hit)
+{
+ int i;
+
+ for (i = 0; i < global_items; i++) {
+ if (node->begin == global_key[i]
+ && !lookup_hit[i]) {
+ lookup_hit[i] = 1;
+ break;
+ }
+ }
+}
+
void *thr_reader(void *_count)
{
unsigned long long *count = _count;
+ struct rcu_rbtree_node *node;
+ int i, index;
+ char *lookup_hit;
printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
"reader", pthread_self(), (unsigned long)gettid());
rcu_register_thread();
+ lookup_hit = malloc(sizeof(*lookup_hit) * global_items);
+
while (!test_go)
{
}
cmm_smp_mb();
for (;;) {
- rcu_read_lock();
+ /* search begin key */
+ if (opt_search_begin) {
+ for (i = 0; i < global_items; i++) {
+ rcu_read_lock();
+ node = rcu_rbtree_search_begin_key(&rbtree,
+ rcu_dereference(rbtree.root),
+ global_key[i]);
+ assert(!rcu_rbtree_is_nil(&rbtree, node));
+ rcu_read_unlock();
+ nr_reads++;
+ }
+ }
+
+ /* search bottom of range */
+ if (opt_search_bottom) {
+ for (i = 0; i < global_items; i++) {
+ rcu_read_lock();
+ node = rcu_rbtree_search(&rbtree,
+ rcu_dereference(rbtree.root),
+ global_key[i]);
+ assert(!rcu_rbtree_is_nil(&rbtree, node));
+ rcu_read_unlock();
+ nr_reads++;
+ }
+ }
+
+ /* search end of range */
+ if (opt_search_end) {
+ for (i = 0; i < global_items; i++) {
+ rcu_read_lock();
+ node = rcu_rbtree_search(&rbtree,
+ rcu_dereference(rbtree.root),
+ (void*) ((unsigned long) global_key[i] + 3));
+ assert(!rcu_rbtree_is_nil(&rbtree, node));
+ rcu_read_unlock();
+ nr_reads++;
+ }
+ }
+
+ /* search range (middle) */
+ if (opt_search_mid) {
+ for (i = 0; i < global_items; i++) {
+ rcu_read_lock();
+ node = rcu_rbtree_search_range(&rbtree,
+ rcu_dereference(rbtree.root),
+ (void*) ((unsigned long) global_key[i] + 1),
+ (void*) ((unsigned long) global_key[i] + 2));
+ assert(!rcu_rbtree_is_nil(&rbtree, node));
+ rcu_read_unlock();
+ nr_reads++;
+ }
+ }
+
+ /* min + next */
+ if (opt_iter_min_max) {
+ memset(lookup_hit, 0, sizeof(*lookup_hit) * global_items);
+
+ rcu_read_lock();
+ node = rcu_rbtree_min(&rbtree,
+ rcu_dereference(rbtree.root));
+ while (!rcu_rbtree_is_nil(&rbtree, node)) {
+ if (!opt_benchmark)
+ set_lookup_index(node, lookup_hit);
+ node = rcu_rbtree_next(&rbtree, node);
+ nr_reads++;
+ }
+ rcu_read_unlock();
+
+ if (!opt_benchmark) {
+ for (i = 0; i < global_items; i++)
+ assert(lookup_hit[i]);
+ }
+ }
+
+ /* max + prev */
+ if (opt_iter_max_min) {
+ memset(lookup_hit, 0, sizeof(*lookup_hit) * global_items);
+
+ rcu_read_lock();
+ node = rcu_rbtree_max(&rbtree,
+ rcu_dereference(rbtree.root));
+ while (!rcu_rbtree_is_nil(&rbtree, node)) {
+ if (!opt_benchmark)
+ set_lookup_index(node, lookup_hit);
+ node = rcu_rbtree_prev(&rbtree, node);
+ nr_reads++;
+ }
+ rcu_read_unlock();
+
+ if (!opt_benchmark) {
+ for (i = 0; i < global_items; i++)
+ assert(lookup_hit[i]);
+ }
+ }
debug_yield_read();
if (unlikely(rduration))
loop_sleep(rduration);
- rcu_read_unlock();
- nr_reads++;
if (unlikely(!test_duration_read()))
break;
}
rcu_register_thread();
rcu_unregister_thread();
+ free(lookup_hit);
+
*count = nr_reads;
printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
"reader", pthread_self(), (unsigned long)gettid());
{
unsigned long long *count = _count;
struct rcu_rbtree_node *node;
- void *key[NR_RAND];
+ void **key;
int i;
printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
set_affinity();
+ key = malloc(sizeof(*key) * nr_rand_items);
+ assert(key);
+ //disable_debug = 1;
+
rcu_register_thread();
while (!test_go)
for (;;) {
rcu_copy_mutex_lock();
- rcu_read_lock();
- for (i = 0; i < NR_RAND; i++) {
- node = rbtree_alloc();
- key[i] = (void *)(unsigned long)(rand() % 2048);
- node->key = key[i];
- rcu_rbtree_insert(&rbtree, node);
+ for (i = 0; i < nr_rand_items; i++) {
+ //key[i] = (void *)(unsigned long)(rand() % 2048);
+ key[i] = (void *)(unsigned long)(((unsigned long) rand() * 4) % 2048);
+ //For more collisions
+ //key[i] = (void *)(unsigned long)(rand() % 6);
+ //node->begin = key[i];
+ //node->end = (void *)((unsigned long) key[i] + 1);
+ //node->end = (void *)((unsigned long) key[i] + 4);
+ rcu_read_lock();
+ rcu_rbtree_insert(&rbtree, key[i],
+ (void *)((unsigned long) key[i] + 4));
+ rcu_read_unlock();
+ nr_writes++;
}
+ rcu_copy_mutex_unlock();
if (unlikely(wduration))
loop_sleep(wduration);
- for (i = 0; i < NR_RAND; i++) {
+ rcu_copy_mutex_lock();
+ for (i = 0; i < nr_rand_items; i++) {
#if 0
node = rcu_rbtree_min(rbtree, rbtree->root);
- while (!rcu_rbtree_is_nil(node)) {
+ while (!rcu_rbtree_is_nil(&rbtree, node)) {
printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
(unsigned long)node->key,
node->p->key,
}
printf("\n");
#endif
+ rcu_read_lock();
node = rcu_rbtree_search(&rbtree, rbtree.root, key[i]);
- assert(!rcu_rbtree_is_nil(node));
+ assert(!rcu_rbtree_is_nil(&rbtree, node));
rcu_rbtree_remove(&rbtree, node);
- call_rcu(&node->head, rbtree_free);
+ rcu_read_unlock();
+ nr_writes++;
}
- rcu_read_unlock();
rcu_copy_mutex_unlock();
- nr_writes++;
if (unlikely(!test_duration_write()))
break;
if (unlikely(wdelay))
printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
"writer", pthread_self(), (unsigned long)gettid());
*count = nr_writes;
+ free(key);
return ((void*)2);
}
printf(" [-e duration] (writer C.S. duration (in loops))");
printf(" [-v] (verbose output)");
printf(" [-a cpu#] [-a cpu#]... (affinity)");
+ printf(" [-g items] Initially populate n items (for reader lookups)");
+ printf(" [-f items] Writers add n random items and then remove these items");
+ printf(" [-b] Reader: search begin key");
+ printf(" [-n] Reader: search bottom of range");
+ printf(" [-N] Reader: search end of range");
+ printf(" [-m] Reader: search range (middle)");
+ printf(" [-i] Reader: iterate from min to max");
+ printf(" [-I] Reader: iterate from max to min");
+ printf(" [-B] Benchmark mode (no validation)");
printf("\n");
}
unsigned long long *count_reader, *count_writer;
unsigned long long tot_reads = 0, tot_writes = 0;
int i, a;
+ struct rcu_rbtree_node *node;
if (argc < 4) {
show_usage(argc, argv);
case 'v':
verbose_mode = 1;
break;
+ case 'g':
+ if (argc < i + 2) {
+ show_usage(argc, argv);
+ return -1;
+ }
+ global_items = atol(argv[++i]);
+ break;
+ case 'b':
+ opt_search_begin = 1;
+ break;
+ case 'n':
+ opt_search_bottom = 1;
+ break;
+ case 'N':
+ opt_search_end = 1;
+ break;
+ case 'm':
+ opt_search_mid = 1;
+ break;
+ case 'i':
+ opt_iter_min_max = 1;
+ break;
+ case 'I':
+ opt_iter_max_min = 1;
+ break;
+ case 'B':
+ opt_benchmark = 1;
+ break;
+ case 'f':
+ if (argc < i + 2) {
+ show_usage(argc, argv);
+ return -1;
+ }
+ nr_rand_items = atol(argv[++i]);
+ break;
}
}
tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
count_reader = malloc(sizeof(*count_reader) * nr_readers);
count_writer = malloc(sizeof(*count_writer) * nr_writers);
+ global_key = malloc(sizeof(*global_key) * global_items);
srand(time(NULL));
+ err = create_all_cpu_call_rcu_data(0);
+ assert(!err);
+
next_aff = 0;
for (i = 0; i < nr_readers; i++) {
exit(1);
}
+ rcu_register_thread();
+ rcu_read_lock();
+ /* Insert items looked up by readers */
+ for (i = 0; i < global_items; i++) {
+ global_key[i] = (void *)(unsigned long)(((unsigned long) rand() * 4) % 2048);
+ //global_key[i] = (void *)(unsigned long)(rand() % 2048);
+ //For more collisions
+ //global_key[i] = (void *)(unsigned long)(rand() % 6);
+ //node->begin = global_key[i];
+ //node->end = (void *)((unsigned long) global_key[i] + 1);
+ //node->end = (void *)((unsigned long) global_key[i] + 4);
+ rcu_rbtree_insert(&rbtree, global_key[i],
+ (void *)((unsigned long) global_key[i] + 4));
+ }
+ rcu_read_unlock();
+
cmm_smp_mb();
test_go = 1;
tot_writes += count_writer[i];
}
+ rcu_read_lock();
+ for (i = 0; i < global_items; i++) {
+ node = rcu_rbtree_search(&rbtree, rbtree.root, global_key[i]);
+ assert(!rcu_rbtree_is_nil(&rbtree, node));
+ rcu_rbtree_remove(&rbtree, node);
+ }
+ rcu_read_unlock();
+ rcu_unregister_thread();
+
printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads,
tot_writes);
printf("SUMMARY %-25s testdur %4lu nr_readers %3u rdur %6lu wdur %6lu "
"nr_writers %3u "
- "wdelay %6lu nr_reads %12llu nr_writes %12llu nr_ops %12llu\n",
+ "wdelay %6lu nr_reads %12llu nr_writes %12llu nr_ops %12llu "
+ "global_items %6lu rand_items %6lu\n",
argv[0], duration, nr_readers, rduration, wduration,
nr_writers, wdelay, tot_reads, tot_writes,
- tot_reads + tot_writes);
+ tot_reads + tot_writes, global_items, nr_rand_items);
+ free_all_cpu_call_rcu_data();
free(tid_reader);
free(tid_writer);
free(count_reader);
free(count_writer);
+ free(global_key);
return 0;
}
projects / userspace-rcu.git / blobdiff