[urcu.git] / tests / test_urcu_rbtree.c

/*
 * test_urcu_rbtree.c
 *
 * Userspace RCU library - test program for RB tree
 *
 * Copyright February 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#define _GNU_SOURCE
#ifndef DYNAMIC_LINK_TEST
#define _LGPL_SOURCE
#else
#define debug_yield_read()
#endif
#include "../config.h"
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>
#include <sys/syscall.h>
#include <sched.h>
#include <errno.h>
#include <time.h>

#include <urcu/arch.h>

extern int __thread disable_debug;

/* hardcoded number of CPUs */
#define NR_CPUS 16384

/* 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)
#elif defined(__NR_gettid)
static inline pid_t gettid(void)
{
	return syscall(__NR_gettid);
}
#else
#warning "use pid as tid"
static inline pid_t gettid(void)
{
	return getpid();
}
#endif

#include <urcu.h>
#include <urcu/rcurbtree.h>
#include <urcu-defer.h>

int tree_comp(void *a, void *b)
{
	if ((unsigned long)a < (unsigned long)b)
		return -1;
	else if ((unsigned long)a > (unsigned long)b)
		return 1;
	else
		return 0;
}

static DEFINE_RCU_RBTREE(rbtree, tree_comp, malloc, free, call_rcu);

static volatile int test_go, test_stop;

static unsigned long wdelay;

static unsigned long duration;

/* read-side C.S. duration, in loops */
static unsigned long rduration;

/* 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)
		caa_cpu_relax();
}

static int verbose_mode;

#define printf_verbose(fmt, args...)		\
	do {					\
		if (verbose_mode)		\
			printf(fmt, args);	\
	} while (0)

static unsigned int cpu_affinities[NR_CPUS];
static unsigned int next_aff = 0;
static int use_affinity = 0;

pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;

#ifndef HAVE_CPU_SET_T
typedef unsigned long cpu_set_t;
# define CPU_ZERO(cpuset) do { *(cpuset) = 0; } while(0)
# define CPU_SET(cpu, cpuset) do { *(cpuset) |= (1UL << (cpu)); } while(0)
#endif

static void set_affinity(void)
{
	cpu_set_t mask;
	int cpu;
	int ret;

	if (!use_affinity)
		return;

#if HAVE_SCHED_SETAFFINITY
	ret = pthread_mutex_lock(&affinity_mutex);
	if (ret) {
		perror("Error in pthread mutex lock");
		exit(-1);
	}
	cpu = cpu_affinities[next_aff++];
	ret = pthread_mutex_unlock(&affinity_mutex);
	if (ret) {
		perror("Error in pthread mutex unlock");
		exit(-1);
	}

	CPU_ZERO(&mask);
	CPU_SET(cpu, &mask);
#if SCHED_SETAFFINITY_ARGS == 2
	sched_setaffinity(0, &mask);
#else
	sched_setaffinity(0, sizeof(mask), &mask);
#endif
#endif /* HAVE_SCHED_SETAFFINITY */
}

/*
 * returns 0 if test should end.
 */
static int test_duration_write(void)
{
	return !test_stop;
}

static int test_duration_read(void)
{
	return !test_stop;
}

static unsigned long long __thread nr_writes;
static unsigned long long __thread nr_reads;

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)
{
	int ret;
	ret = pthread_mutex_lock(&rcu_copy_mutex);
	if (ret) {
		perror("Error in pthread mutex lock");
		exit(-1);
	}
}

void rcu_copy_mutex_unlock(void)
{
	int ret;

	ret = pthread_mutex_unlock(&rcu_copy_mutex);
	if (ret) {
		perror("Error in pthread mutex unlock");
		exit(-1);
	}
}

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());

	set_affinity();

	rcu_register_thread();

	lookup_hit = malloc(sizeof(*lookup_hit) * global_items);

	while (!test_go)
	{
	}
	cmm_smp_mb();

	for (;;) {
		/* 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);
		if (unlikely(!test_duration_read()))
			break;
	}

	rcu_unregister_thread();

	/* test extra thread registration */
	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());
	return ((void*)1);

}

void *thr_writer(void *_count)
{
	unsigned long long *count = _count;
	struct rcu_rbtree_node *node;
	void **key;
	int i;

	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
			"writer", pthread_self(), (unsigned long)gettid());

	set_affinity();

	key = malloc(sizeof(*key) * nr_rand_items);
	assert(key);
	//disable_debug = 1;

	rcu_register_thread();

	while (!test_go)
	{
	}
	cmm_smp_mb();

	for (;;) {
		rcu_copy_mutex_lock();

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

		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(&rbtree, node)) {
				printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
					(unsigned long)node->key,
					node->p->key,
					node->right->key,
					node->left->key,
					node->color ? "red" : "black",
					node->pos ? "right" : "left",
					node->nil ? "nil" : "");
				node = rcu_rbtree_next(rbtree, node);
			}
			printf("\n");
#endif
			rcu_read_lock();
			node = rcu_rbtree_search(&rbtree, rbtree.root, key[i]);
			assert(!rcu_rbtree_is_nil(&rbtree, node));
			rcu_rbtree_remove(&rbtree, node);
			rcu_read_unlock();
			nr_writes++;
		}

		rcu_copy_mutex_unlock();
		if (unlikely(!test_duration_write()))
			break;
		if (unlikely(wdelay))
			loop_sleep(wdelay);
	}

	rcu_unregister_thread();

	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);
}

void show_usage(int argc, char **argv)
{
	printf("Usage : %s nr_readers nr_writers duration (s)", argv[0]);
#ifdef DEBUG_YIELD
	printf(" [-r] [-w] (yield reader and/or writer)");
#endif
	printf(" [-d delay] (writer period (us))");
	printf(" [-c duration] (reader C.S. duration (in loops))");
	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");
}

int main(int argc, char **argv)
{
	int err;
	pthread_t *tid_reader, *tid_writer;
	void *tret;
	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);
		return -1;
	}

	err = sscanf(argv[1], "%u", &nr_readers);
	if (err != 1) {
		show_usage(argc, argv);
		return -1;
	}

	err = sscanf(argv[2], "%u", &nr_writers);
	if (err != 1) {
		show_usage(argc, argv);
		return -1;
	}
	
	err = sscanf(argv[3], "%lu", &duration);
	if (err != 1) {
		show_usage(argc, argv);
		return -1;
	}

	for (i = 4; i < argc; i++) {
		if (argv[i][0] != '-')
			continue;
		switch (argv[i][1]) {
#ifdef DEBUG_YIELD
		case 'r':
			yield_active |= YIELD_READ;
			break;
		case 'w':
			yield_active |= YIELD_WRITE;
			break;
#endif
		case 'a':
			if (argc < i + 2) {
				show_usage(argc, argv);
				return -1;
			}
			a = atoi(argv[++i]);
			cpu_affinities[next_aff++] = a;
			use_affinity = 1;
			printf_verbose("Adding CPU %d affinity\n", a);
			break;
		case 'c':
			if (argc < i + 2) {
				show_usage(argc, argv);
				return -1;
			}
			rduration = atol(argv[++i]);
			break;
		case 'd':
			if (argc < i + 2) {
				show_usage(argc, argv);
				return -1;
			}
			wdelay = atol(argv[++i]);
			break;
		case 'e':
			if (argc < i + 2) {
				show_usage(argc, argv);
				return -1;
			}
			wduration = atol(argv[++i]);
			break;
		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;
		}
	}

	printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
		duration, nr_readers, nr_writers);
	printf_verbose("Writer delay : %lu loops.\n", wdelay);
	printf_verbose("Reader duration : %lu loops.\n", rduration);
	printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
			"main", pthread_self(), (unsigned long)gettid());

	tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
	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++) {
		err = pthread_create(&tid_reader[i], NULL, thr_reader,
				     &count_reader[i]);
		if (err != 0)
			exit(1);
	}
	for (i = 0; i < nr_writers; i++) {
		err = pthread_create(&tid_writer[i], NULL, thr_writer,
				     &count_writer[i]);
		if (err != 0)
			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;

	sleep(duration);

	test_stop = 1;

	for (i = 0; i < nr_readers; i++) {
		err = pthread_join(tid_reader[i], &tret);
		if (err != 0)
			exit(1);
		tot_reads += count_reader[i];
	}
	for (i = 0; i < nr_writers; i++) {
		err = pthread_join(tid_writer[i], &tret);
		if (err != 0)
			exit(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 "
		"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, global_items, nr_rand_items);
	free(tid_reader);
	free(tid_writer);
	free(count_reader);
	free(count_writer);
	free(global_key);
	return 0;
}
Commit	Line	Data
dff86257 MD	1	/*
	2	* test_urcu_rbtree.c
	3	*
	4	* Userspace RCU library - test program for RB tree
	5	*
	6	* Copyright February 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	7	*
	8	* This program is free software; you can redistribute it and/or modify
	9	* it under the terms of the GNU General Public License as published by
	10	* the Free Software Foundation; either version 2 of the License, or
	11	* (at your option) any later version.
	12	*
	13	* This program is distributed in the hope that it will be useful,
	14	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	* GNU General Public License for more details.
	17	*
	18	* You should have received a copy of the GNU General Public License along
	19	* with this program; if not, write to the Free Software Foundation, Inc.,
	20	* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
	21	*/
	22
	23	#define _GNU_SOURCE
	24	#ifndef DYNAMIC_LINK_TEST
	25	#define _LGPL_SOURCE
	26	#else
	27	#define debug_yield_read()
	28	#endif
	29	#include "../config.h"
	30	#include <stdio.h>
	31	#include <pthread.h>
	32	#include <stdlib.h>
	33	#include <string.h>
	34	#include <sys/types.h>
	35	#include <sys/wait.h>
	36	#include <unistd.h>
	37	#include <stdio.h>
	38	#include <assert.h>
	39	#include <sys/syscall.h>
	40	#include <sched.h>
	41	#include <errno.h>
	42	#include <time.h>
	43
	44	#include <urcu/arch.h>
	45
a84e8c8e MD	46	extern int __thread disable_debug;
a84e8c8e MD	47
dff86257 MD	48	/* hardcoded number of CPUs */
	49	#define NR_CPUS 16384
	50
fa67ba2e MD	51	/* Default number of insert/delete */
	52	#define DEFAULT_NR_RAND 6
	53
	54	/* Default number of global items (used by readers for lookups) */
	55	#define DEFAULT_NR_GLOBAL 10
dff86257 MD	56
	57	#if defined(_syscall0)
	58	_syscall0(pid_t, gettid)
	59	#elif defined(__NR_gettid)
	60	static inline pid_t gettid(void)
	61	{
	62	return syscall(__NR_gettid);
	63	}
	64	#else
	65	#warning "use pid as tid"
	66	static inline pid_t gettid(void)
	67	{
	68	return getpid();
	69	}
	70	#endif
	71
	72	#include <urcu.h>
	73	#include <urcu/rcurbtree.h>
	74	#include <urcu-defer.h>
	75
dff86257 MD	76	int tree_comp(void a, void b)
	77	{
	78	if ((unsigned long)a < (unsigned long)b)
	79	return -1;
	80	else if ((unsigned long)a > (unsigned long)b)
	81	return 1;
	82	else
	83	return 0;
	84	}
	85
1cdd423d	86	static DEFINE_RCU_RBTREE(rbtree, tree_comp, malloc, free, call_rcu);
dff86257 MD	87
	88	static volatile int test_go, test_stop;
	89
	90	static unsigned long wdelay;
	91
	92	static unsigned long duration;
	93
	94	/* read-side C.S. duration, in loops */
	95	static unsigned long rduration;
	96
	97	/* write-side C.S. duration, in loops */
	98	static unsigned long wduration;
	99
fa67ba2e MD	100	static unsigned long nr_rand_items = DEFAULT_NR_RAND;
	101
	102	static int opt_search_begin,
	103	opt_search_bottom,
	104	opt_search_end,
	105	opt_search_mid,
	106	opt_iter_min_max,
	107	opt_iter_max_min,
	108	opt_benchmark;
	109
dff86257 MD	110	static inline void loop_sleep(unsigned long l)
dff86257 MD	111	{
fa67ba2e	112	while (l-- != 0)
dff86257 MD	113	caa_cpu_relax();
	114	}
	115
	116	static int verbose_mode;
	117
	118	#define printf_verbose(fmt, args...) \
	119	do { \
	120	if (verbose_mode) \
	121	printf(fmt, args); \
	122	} while (0)
	123
	124	static unsigned int cpu_affinities[NR_CPUS];
	125	static unsigned int next_aff = 0;
	126	static int use_affinity = 0;
	127
	128	pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;
	129
	130	#ifndef HAVE_CPU_SET_T
	131	typedef unsigned long cpu_set_t;
	132	# define CPU_ZERO(cpuset) do { *(cpuset) = 0; } while(0)
	133	# define CPU_SET(cpu, cpuset) do { *(cpuset) \|= (1UL << (cpu)); } while(0)
	134	#endif
	135
	136	static void set_affinity(void)
	137	{
	138	cpu_set_t mask;
	139	int cpu;
	140	int ret;
	141
	142	if (!use_affinity)
	143	return;
	144
	145	#if HAVE_SCHED_SETAFFINITY
	146	ret = pthread_mutex_lock(&affinity_mutex);
	147	if (ret) {
	148	perror("Error in pthread mutex lock");
	149	exit(-1);
	150	}
	151	cpu = cpu_affinities[next_aff++];
	152	ret = pthread_mutex_unlock(&affinity_mutex);
	153	if (ret) {
	154	perror("Error in pthread mutex unlock");
	155	exit(-1);
	156	}
	157
	158	CPU_ZERO(&mask);
	159	CPU_SET(cpu, &mask);
	160	#if SCHED_SETAFFINITY_ARGS == 2
	161	sched_setaffinity(0, &mask);
	162	#else
	163	sched_setaffinity(0, sizeof(mask), &mask);
	164	#endif
	165	#endif /* HAVE_SCHED_SETAFFINITY */
	166	}
	167
	168	/*
	169	* returns 0 if test should end.
	170	*/
	171	static int test_duration_write(void)
	172	{
	173	return !test_stop;
	174	}
	175
	176	static int test_duration_read(void)
177	{
178	return !test_stop;
179	}
180
181	static unsigned long long __thread nr_writes;
182	static unsigned long long __thread nr_reads;
183
184	static unsigned int nr_readers;
185	static unsigned int nr_writers;
186
fa67ba2e	187	static unsigned long global_items = DEFAULT_NR_GLOBAL;
3f73f150 MD	188	static void **global_key = NULL;
3f73f150 MD	189
dff86257 MD	190	pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
	191
	192	void rcu_copy_mutex_lock(void)
	193	{
	194	int ret;
	195	ret = pthread_mutex_lock(&rcu_copy_mutex);
	196	if (ret) {
	197	perror("Error in pthread mutex lock");
	198	exit(-1);
	199	}
	200	}
	201
	202	void rcu_copy_mutex_unlock(void)
	203	{
	204	int ret;
	205
	206	ret = pthread_mutex_unlock(&rcu_copy_mutex);
	207	if (ret) {
	208	perror("Error in pthread mutex unlock");
	209	exit(-1);
	210	}
	211	}
	212
65715d0c	213	static
f6f32757 MD	214	void set_lookup_index(struct rcu_rbtree_node *node,
f6f32757 MD	215	char *lookup_hit)
65715d0c MD	216	{
	217	int i;
	218
	219	for (i = 0; i < global_items; i++) {
3366b9c0	220	if (node->begin == global_key[i]
f6f32757 MD	221	&& !lookup_hit[i]) {
	222	lookup_hit[i] = 1;
	223	break;
	224	}
65715d0c	225	}
65715d0c MD	226	}
65715d0c MD	227
dff86257 MD	228	void thr_reader(void _count)
	229	{
	230	unsigned long long *count = _count;
3f73f150	231	struct rcu_rbtree_node *node;
65715d0c MD	232	int i, index;
65715d0c MD	233	char *lookup_hit;
dff86257 MD	234
	235	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
	236	"reader", pthread_self(), (unsigned long)gettid());
	237
	238	set_affinity();
	239
	240	rcu_register_thread();
	241
65715d0c MD	242	lookup_hit = malloc(sizeof(lookup_hit) global_items);
65715d0c MD	243
dff86257 MD	244	while (!test_go)
	245	{
	246	}
	247	cmm_smp_mb();
	248
	249	for (;;) {
fa67ba2e MD	250	/* search begin key */
	251	if (opt_search_begin) {
	252	for (i = 0; i < global_items; i++) {
	253	rcu_read_lock();
	254	node = rcu_rbtree_search_begin_key(&rbtree,
	255	rcu_dereference(rbtree.root),
	256	global_key[i]);
	257	assert(!rcu_rbtree_is_nil(&rbtree, node));
	258	rcu_read_unlock();
	259	nr_reads++;
	260	}
	261	}
	262
20a104c3	263	/* search bottom of range */
fa67ba2e MD	264	if (opt_search_bottom) {
	265	for (i = 0; i < global_items; i++) {
	266	rcu_read_lock();
	267	node = rcu_rbtree_search(&rbtree,
	268	rcu_dereference(rbtree.root),
	269	global_key[i]);
	270	assert(!rcu_rbtree_is_nil(&rbtree, node));
	271	rcu_read_unlock();
	272	nr_reads++;
	273	}
3f73f150	274	}
6117fcbf	275
20a104c3	276	/* search end of range */
fa67ba2e MD	277	if (opt_search_end) {
	278	for (i = 0; i < global_items; i++) {
	279	rcu_read_lock();
	280	node = rcu_rbtree_search(&rbtree,
	281	rcu_dereference(rbtree.root),
	282	(void*) ((unsigned long) global_key[i] + 3));
	283	assert(!rcu_rbtree_is_nil(&rbtree, node));
	284	rcu_read_unlock();
	285	nr_reads++;
	286	}
20a104c3 MD	287	}
	288
	289	/* search range (middle) */
fa67ba2e MD	290	if (opt_search_mid) {
	291	for (i = 0; i < global_items; i++) {
	292	rcu_read_lock();
	293	node = rcu_rbtree_search_range(&rbtree,
	294	rcu_dereference(rbtree.root),
	295	(void*) ((unsigned long) global_key[i] + 1),
	296	(void*) ((unsigned long) global_key[i] + 2));
	297	assert(!rcu_rbtree_is_nil(&rbtree, node));
	298	rcu_read_unlock();
	299	nr_reads++;
	300	}
00539351	301	}
1c16a0d6	302
fa67ba2e MD	303	/* min + next */
	304	if (opt_iter_min_max) {
	305	memset(lookup_hit, 0, sizeof(lookup_hit) global_items);
	306
1c16a0d6	307	rcu_read_lock();
fa67ba2e MD	308	node = rcu_rbtree_min(&rbtree,
	309	rcu_dereference(rbtree.root));
	310	while (!rcu_rbtree_is_nil(&rbtree, node)) {
	311	if (!opt_benchmark)
	312	set_lookup_index(node, lookup_hit);
	313	node = rcu_rbtree_next(&rbtree, node);
	314	nr_reads++;
	315	}
1c16a0d6	316	rcu_read_unlock();
1c16a0d6	317
fa67ba2e MD	318	if (!opt_benchmark) {
	319	for (i = 0; i < global_items; i++)
	320	assert(lookup_hit[i]);
	321	}
65715d0c	322	}
65715d0c MD	323
65715d0c MD	324	/* max + prev */
fa67ba2e MD	325	if (opt_iter_max_min) {
	326	memset(lookup_hit, 0, sizeof(lookup_hit) global_items);
	327
	328	rcu_read_lock();
	329	node = rcu_rbtree_max(&rbtree,
	330	rcu_dereference(rbtree.root));
	331	while (!rcu_rbtree_is_nil(&rbtree, node)) {
	332	if (!opt_benchmark)
	333	set_lookup_index(node, lookup_hit);
	334	node = rcu_rbtree_prev(&rbtree, node);
	335	nr_reads++;
	336	}
	337	rcu_read_unlock();
65715d0c	338
fa67ba2e MD	339	if (!opt_benchmark) {
	340	for (i = 0; i < global_items; i++)
	341	assert(lookup_hit[i]);
	342	}
	343	}
65715d0c	344
dff86257 MD	345	debug_yield_read();
	346	if (unlikely(rduration))
	347	loop_sleep(rduration);
dff86257 MD	348	if (unlikely(!test_duration_read()))
	349	break;
	350	}
	351
	352	rcu_unregister_thread();
	353
	354	/* test extra thread registration */
	355	rcu_register_thread();
	356	rcu_unregister_thread();
	357
65715d0c MD	358	free(lookup_hit);
65715d0c MD	359
dff86257 MD	360	*count = nr_reads;
	361	printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
	362	"reader", pthread_self(), (unsigned long)gettid());
	363	return ((void*)1);
	364
	365	}
	366
	367	void thr_writer(void _count)
	368	{
	369	unsigned long long *count = _count;
	370	struct rcu_rbtree_node *node;
fa67ba2e	371	void **key;
dff86257 MD	372	int i;
	373
	374	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
	375	"writer", pthread_self(), (unsigned long)gettid());
	376
	377	set_affinity();
	378
fa67ba2e MD	379	key = malloc(sizeof(key) nr_rand_items);
fa67ba2e MD	380	assert(key);
a84e8c8e MD	381	//disable_debug = 1;
a84e8c8e MD	382
c479601c	383	rcu_register_thread();
dff86257 MD	384
	385	while (!test_go)
	386	{
	387	}
	388	cmm_smp_mb();
	389
	390	for (;;) {
	391	rcu_copy_mutex_lock();
	392
fa67ba2e	393	for (i = 0; i < nr_rand_items; i++) {
6117fcbf MD	394	//key[i] = (void *)(unsigned long)(rand() % 2048);
6117fcbf MD	395	key[i] = (void )(unsigned long)(((unsigned long) rand() 4) % 2048);
4310d6da MD	396	//For more collisions
4310d6da MD	397	//key[i] = (void *)(unsigned long)(rand() % 6);
3c672595	398	//node->begin = key[i];
6117fcbf	399	//node->end = (void *)((unsigned long) key[i] + 1);
3c672595	400	//node->end = (void *)((unsigned long) key[i] + 4);
230dd288	401	rcu_read_lock();
3c672595 MD	402	rcu_rbtree_insert(&rbtree, key[i],
3c672595 MD	403	(void *)((unsigned long) key[i] + 4));
230dd288	404	rcu_read_unlock();
fa67ba2e	405	nr_writes++;
dff86257	406	}
230dd288	407	rcu_copy_mutex_unlock();
dff86257 MD	408
	409	if (unlikely(wduration))
	410	loop_sleep(wduration);
	411
230dd288	412	rcu_copy_mutex_lock();
fa67ba2e	413	for (i = 0; i < nr_rand_items; i++) {
dff86257 MD	414	#if 0
dff86257 MD	415	node = rcu_rbtree_min(rbtree, rbtree->root);
8ded5fe9	416	while (!rcu_rbtree_is_nil(&rbtree, node)) {
dff86257 MD	417	printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ",
	418	(unsigned long)node->key,
	419	node->p->key,
	420	node->right->key,
	421	node->left->key,
	422	node->color ? "red" : "black",
	423	node->pos ? "right" : "left",
	424	node->nil ? "nil" : "");
	425	node = rcu_rbtree_next(rbtree, node);
	426	}
	427	printf("\n");
	428	#endif
230dd288	429	rcu_read_lock();
dff86257	430	node = rcu_rbtree_search(&rbtree, rbtree.root, key[i]);
8ded5fe9	431	assert(!rcu_rbtree_is_nil(&rbtree, node));
dff86257	432	rcu_rbtree_remove(&rbtree, node);
230dd288	433	rcu_read_unlock();
fa67ba2e	434	nr_writes++;
dff86257 MD	435	}
	436
	437	rcu_copy_mutex_unlock();
dff86257 MD	438	if (unlikely(!test_duration_write()))
	439	break;
	440	if (unlikely(wdelay))
	441	loop_sleep(wdelay);
	442	}
	443
c479601c	444	rcu_unregister_thread();
dff86257 MD	445
	446	printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
	447	"writer", pthread_self(), (unsigned long)gettid());
	448	*count = nr_writes;
fa67ba2e	449	free(key);
dff86257 MD	450	return ((void*)2);
	451	}
	452
	453	void show_usage(int argc, char **argv)
	454	{
	455	printf("Usage : %s nr_readers nr_writers duration (s)", argv[0]);
	456	#ifdef DEBUG_YIELD
	457	printf(" [-r] [-w] (yield reader and/or writer)");
	458	#endif
	459	printf(" [-d delay] (writer period (us))");
	460	printf(" [-c duration] (reader C.S. duration (in loops))");
	461	printf(" [-e duration] (writer C.S. duration (in loops))");
	462	printf(" [-v] (verbose output)");
	463	printf(" [-a cpu#] [-a cpu#]... (affinity)");
fa67ba2e MD	464	printf(" [-g items] Initially populate n items (for reader lookups)");
	465	printf(" [-f items] Writers add n random items and then remove these items");
	466	printf(" [-b] Reader: search begin key");
	467	printf(" [-n] Reader: search bottom of range");
	468	printf(" [-N] Reader: search end of range");
	469	printf(" [-m] Reader: search range (middle)");
	470	printf(" [-i] Reader: iterate from min to max");
	471	printf(" [-I] Reader: iterate from max to min");
	472	printf(" [-B] Benchmark mode (no validation)");
dff86257 MD	473	printf("\n");
	474	}
	475
	476	int main(int argc, char **argv)
	477	{
	478	int err;
	479	pthread_t tid_reader, tid_writer;
	480	void *tret;
	481	unsigned long long count_reader, count_writer;
	482	unsigned long long tot_reads = 0, tot_writes = 0;
	483	int i, a;
3f73f150	484	struct rcu_rbtree_node *node;
dff86257 MD	485
	486	if (argc < 4) {
	487	show_usage(argc, argv);
	488	return -1;
	489	}
	490
	491	err = sscanf(argv[1], "%u", &nr_readers);
	492	if (err != 1) {
	493	show_usage(argc, argv);
	494	return -1;
	495	}
	496
	497	err = sscanf(argv[2], "%u", &nr_writers);
	498	if (err != 1) {
	499	show_usage(argc, argv);
	500	return -1;
	501	}
	502
	503	err = sscanf(argv[3], "%lu", &duration);
	504	if (err != 1) {
	505	show_usage(argc, argv);
	506	return -1;
	507	}
	508
	509	for (i = 4; i < argc; i++) {
	510	if (argv[i][0] != '-')
	511	continue;
	512	switch (argv[i][1]) {
	513	#ifdef DEBUG_YIELD
	514	case 'r':
	515	yield_active \|= YIELD_READ;
	516	break;
	517	case 'w':
	518	yield_active \|= YIELD_WRITE;
	519	break;
	520	#endif
	521	case 'a':
	522	if (argc < i + 2) {
	523	show_usage(argc, argv);
	524	return -1;
	525	}
	526	a = atoi(argv[++i]);
	527	cpu_affinities[next_aff++] = a;
	528	use_affinity = 1;
	529	printf_verbose("Adding CPU %d affinity\n", a);
	530	break;
	531	case 'c':
	532	if (argc < i + 2) {
	533	show_usage(argc, argv);
	534	return -1;
	535	}
	536	rduration = atol(argv[++i]);
	537	break;
	538	case 'd':
	539	if (argc < i + 2) {
	540	show_usage(argc, argv);
	541	return -1;
	542	}
	543	wdelay = atol(argv[++i]);
	544	break;
	545	case 'e':
	546	if (argc < i + 2) {
	547	show_usage(argc, argv);
	548	return -1;
549	}
550	wduration = atol(argv[++i]);
551	break;
552	case 'v':
553	verbose_mode = 1;
554	break;
3f73f150 MD	555	case 'g':
	556	if (argc < i + 2) {
	557	show_usage(argc, argv);
	558	return -1;
	559	}
	560	global_items = atol(argv[++i]);
	561	break;
fa67ba2e MD	562	case 'b':
	563	opt_search_begin = 1;
	564	break;
	565	case 'n':
	566	opt_search_bottom = 1;
	567	break;
	568	case 'N':
	569	opt_search_end = 1;
	570	break;
	571	case 'm':
	572	opt_search_mid = 1;
	573	break;
	574	case 'i':
	575	opt_iter_min_max = 1;
	576	break;
	577	case 'I':
	578	opt_iter_max_min = 1;
	579	break;
	580	case 'B':
	581	opt_benchmark = 1;
	582	break;
	583	case 'f':
	584	if (argc < i + 2) {
	585	show_usage(argc, argv);
	586	return -1;
	587	}
	588	nr_rand_items = atol(argv[++i]);
	589	break;
dff86257 MD	590	}
	591	}
	592
	593	printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
	594	duration, nr_readers, nr_writers);
	595	printf_verbose("Writer delay : %lu loops.\n", wdelay);
	596	printf_verbose("Reader duration : %lu loops.\n", rduration);
	597	printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
	598	"main", pthread_self(), (unsigned long)gettid());
	599
	600	tid_reader = malloc(sizeof(tid_reader) nr_readers);
	601	tid_writer = malloc(sizeof(tid_writer) nr_writers);
	602	count_reader = malloc(sizeof(count_reader) nr_readers);
	603	count_writer = malloc(sizeof(count_writer) nr_writers);
3f73f150	604	global_key = malloc(sizeof(global_key) global_items);
dff86257 MD	605
	606	srand(time(NULL));
	607
f6885a1a MD	608	err = create_all_cpu_call_rcu_data(0);
	609	assert(!err);
	610
dff86257 MD	611	next_aff = 0;
	612
	613	for (i = 0; i < nr_readers; i++) {
	614	err = pthread_create(&tid_reader[i], NULL, thr_reader,
	615	&count_reader[i]);
	616	if (err != 0)
	617	exit(1);
	618	}
	619	for (i = 0; i < nr_writers; i++) {
	620	err = pthread_create(&tid_writer[i], NULL, thr_writer,
	621	&count_writer[i]);
	622	if (err != 0)
	623	exit(1);
	624	}
	625
806967f3 MD	626	rcu_register_thread();
806967f3 MD	627	rcu_read_lock();
3f73f150 MD	628	/* Insert items looked up by readers */
3f73f150 MD	629	for (i = 0; i < global_items; i++) {
6117fcbf MD	630	global_key[i] = (void )(unsigned long)(((unsigned long) rand() 4) % 2048);
6117fcbf MD	631	//global_key[i] = (void *)(unsigned long)(rand() % 2048);
4310d6da	632	//For more collisions
26b3847b	633	//global_key[i] = (void *)(unsigned long)(rand() % 6);
3c672595	634	//node->begin = global_key[i];
6117fcbf	635	//node->end = (void *)((unsigned long) global_key[i] + 1);
3c672595 MD	636	//node->end = (void *)((unsigned long) global_key[i] + 4);
	637	rcu_rbtree_insert(&rbtree, global_key[i],
	638	(void *)((unsigned long) global_key[i] + 4));
3f73f150	639	}
806967f3	640	rcu_read_unlock();
3f73f150	641
dff86257 MD	642	cmm_smp_mb();
	643
	644	test_go = 1;
	645
	646	sleep(duration);
	647
	648	test_stop = 1;
	649
	650	for (i = 0; i < nr_readers; i++) {
	651	err = pthread_join(tid_reader[i], &tret);
	652	if (err != 0)
	653	exit(1);
	654	tot_reads += count_reader[i];
	655	}
	656	for (i = 0; i < nr_writers; i++) {
	657	err = pthread_join(tid_writer[i], &tret);
	658	if (err != 0)
	659	exit(1);
	660	tot_writes += count_writer[i];
	661	}
	662
806967f3	663	rcu_read_lock();
3f73f150 MD	664	for (i = 0; i < global_items; i++) {
3f73f150 MD	665	node = rcu_rbtree_search(&rbtree, rbtree.root, global_key[i]);
8ded5fe9	666	assert(!rcu_rbtree_is_nil(&rbtree, node));
3f73f150	667	rcu_rbtree_remove(&rbtree, node);
3f73f150	668	}
806967f3 MD	669	rcu_read_unlock();
806967f3 MD	670	rcu_unregister_thread();
3f73f150	671
dff86257 MD	672	printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads,
	673	tot_writes);
	674	printf("SUMMARY %-25s testdur %4lu nr_readers %3u rdur %6lu wdur %6lu "
	675	"nr_writers %3u "
3f73f150	676	"wdelay %6lu nr_reads %12llu nr_writes %12llu nr_ops %12llu "
fa67ba2e	677	"global_items %6lu rand_items %6lu\n",
dff86257 MD	678	argv[0], duration, nr_readers, rduration, wduration,
dff86257 MD	679	nr_writers, wdelay, tot_reads, tot_writes,
fa67ba2e	680	tot_reads + tot_writes, global_items, nr_rand_items);
dff86257 MD	681	free(tid_reader);
	682	free(tid_writer);
	683	free(count_reader);
	684	free(count_writer);
3f73f150	685	free(global_key);
dff86257 MD	686	return 0;
dff86257 MD	687	}