[userspace-rcu.git] / tests / test_urcu_ja_range.c

/*
 * test_urcu_ja_range.c
 *
 * Userspace RCU library - test program
 *
 * Copyright 2009-2012 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
 *
 * 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
#include "test_urcu_ja_range.h"
#include <inttypes.h>
#include <stdint.h>

DEFINE_URCU_TLS(unsigned int, rand_lookup);
DEFINE_URCU_TLS(unsigned long, nr_add);
DEFINE_URCU_TLS(unsigned long, nr_addexist);
DEFINE_URCU_TLS(unsigned long, nr_del);
DEFINE_URCU_TLS(unsigned long, nr_delnoent);
DEFINE_URCU_TLS(unsigned long, lookup_fail);
DEFINE_URCU_TLS(unsigned long, lookup_ok);

struct cds_ja *test_ja;

volatile int test_go, test_stop;

unsigned long wdelay;

unsigned long duration;

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

unsigned long init_populate;
int add_only;

unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
unsigned long init_pool_size = DEFAULT_RAND_POOL,
	lookup_pool_size = DEFAULT_RAND_POOL,
	write_pool_size = DEFAULT_RAND_POOL;
int validate_lookup;
int sanity_test;
unsigned int key_bits = 32;

int count_pipe[2];

int verbose_mode;

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

pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;

DEFINE_URCU_TLS(unsigned long long, nr_writes);
DEFINE_URCU_TLS(unsigned long long, nr_reads);

unsigned int nr_readers;
unsigned int nr_writers;

static unsigned int add_ratio = 50;
static uint64_t key_mul = 1ULL;

static int add_unique, add_replace;

static pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;

static int leak_detection;
static unsigned long test_nodes_allocated, test_nodes_freed;

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 */
}

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

void show_usage(int argc, char **argv)
{
	printf("Usage : %s nr_readers nr_writers duration (s)\n", argv[0]);
#ifdef DEBUG_YIELD
	printf("        [-r] [-w] (yield reader and/or writer)\n");
#endif
	printf("        [-d delay] (writer period (us))\n");
	printf("        [-c duration] (reader C.S. duration (in loops))\n");
	printf("        [-v] (verbose output)\n");
	printf("        [-a cpu#] [-a cpu#]... (affinity)\n");
	printf("        [-u] Add unique keys.\n");
	printf("        [-s] Replace existing keys.\n");
printf("        [not -u nor -s] Add entries (supports redundant keys).\n");
	printf("        [-r ratio] Add ratio (in %% of add+removal).\n");
	printf("        [-k] Populate init nodes.\n");
	printf("        [-R offset] Lookup pool offset.\n");
	printf("        [-S offset] Write pool offset.\n");
	printf("        [-T offset] Init pool offset.\n");
	printf("        [-M size] Lookup pool size.\n");
	printf("        [-N size] Write pool size.\n");
	printf("        [-O size] Init pool size.\n");
	printf("        [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
	printf("        [-t] Do sanity test.\n");
	printf("        [-B] Key bits for multithread test (default: 32).\n");
	printf("        [-m factor] Key multiplication factor.\n");
	printf("	[-l] Memory leak detection.\n");
	printf("\n\n");
}

enum urcu_ja_addremove {
	AR_RANDOM = 0,
	AR_ADD = 1,
	AR_REMOVE = -1,
};	/* 1: add, -1 remove, 0: random */

static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */

static
void test_ja_rw_sigusr1_handler(int signo)
{
	switch (addremove) {
	case AR_ADD:
		printf("Add/Remove: random.\n");
		addremove = AR_RANDOM;
		break;
	case AR_RANDOM:
		printf("Add/Remove: remove only.\n");
		addremove = AR_REMOVE;
		break;
	case AR_REMOVE:
		printf("Add/Remove: add only.\n");
		addremove = AR_ADD;
		break;
	}
}

static
void *test_ja_rw_thr_reader(void *_count)
{
	unsigned long long *count = _count;
	struct cds_ja_range *range;
	uint64_t key;

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

	set_affinity();

	rcu_register_thread();

	while (!test_go)
	{
	}
	cmm_smp_mb();

	for (;;) {
		rcu_read_lock();

		/* note: only looking up ulong keys */
		key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
		key *= key_mul;
		range = cds_ja_range_lookup(test_ja, key);
		if (!range) {
			if (validate_lookup) {
				printf("[ERROR] Lookup cannot find initial node.\n");
				exit(-1);
			}
			URCU_TLS(lookup_fail)++;
		} else {
			range = cds_ja_range_lock(range);
			if (!range) {
				if (validate_lookup) {
					printf("[ERROR] Lookup cannot find initial node.\n");
					exit(-1);
				}
			} else {
				URCU_TLS(lookup_ok)++;
				cds_ja_range_unlock(range);
			}
		}
		rcu_debug_yield_read();
		if (caa_unlikely(rduration))
			loop_sleep(rduration);
		rcu_read_unlock();
		URCU_TLS(nr_reads)++;
		if (caa_unlikely(!test_duration_read()))
			break;
		if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
			rcu_quiescent_state();
	}

	rcu_unregister_thread();

	*count = URCU_TLS(nr_reads);
	printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
			"reader", pthread_self(), (unsigned long) gettid());
	printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
			pthread_self(), URCU_TLS(lookup_fail),
			URCU_TLS(lookup_ok));
	return ((void*)1);
}

static
int is_add(void)
{
	return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
}

static
void *test_ja_rw_thr_writer(void *_count)
{
	struct wr_count *count = _count;
	int ret;

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

	set_affinity();

	rcu_register_thread();

	while (!test_go)
	{
	}
	cmm_smp_mb();

	for (;;) {
		if ((addremove == AR_ADD)
				|| (addremove == AR_RANDOM && is_add())) {
			struct cds_ja_range *range;
			uint64_t start, end, tmp;

			/* note: only inserting ulong keys */
			start = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
			end = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
			start *= key_mul;
			end *= key_mul;
			if (start > end) {
				tmp = start;
				start = end;
				end = tmp;
			}
			rcu_read_lock();
			ret = cds_ja_range_add(test_ja, start, end, NULL);
			if (ret) {
				if (ret == -EEXIST) {
					URCU_TLS(nr_addexist)++;
				} else {
					assert(0);
				}
			} else {
				URCU_TLS(nr_add)++;
			}
			rcu_read_unlock();
		} else {
			struct cds_ja_range *range;
			uint64_t key;

			/* May delete */
			/* note: only deleting ulong keys */
			key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
			key *= key_mul;

			rcu_read_lock();

			range = cds_ja_range_lookup(test_ja, key);
			if (range) {
				ret = cds_ja_range_del(test_ja, range);
				if (!ret) {
					URCU_TLS(nr_del)++;
				} else {
					URCU_TLS(nr_delnoent)++;
				}
			} else {
				URCU_TLS(nr_delnoent)++;
			}
			rcu_read_unlock();
		}

		URCU_TLS(nr_writes)++;
		if (caa_unlikely(!test_duration_write()))
			break;
		if (caa_unlikely(wdelay))
			loop_sleep(wdelay);
		if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
			rcu_quiescent_state();
	}

	rcu_unregister_thread();

	printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
			"writer", pthread_self(), (unsigned long) gettid());
	printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
			"nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
			URCU_TLS(nr_addexist), URCU_TLS(nr_del),
			URCU_TLS(nr_delnoent));
	count->update_ops = URCU_TLS(nr_writes);
	count->add = URCU_TLS(nr_add);
	count->add_exist = URCU_TLS(nr_addexist);
	count->remove = URCU_TLS(nr_del);
	return ((void*)2);
}

static
int do_mt_populate_ja(void)
{
	uint64_t iter;
	int ret;

	if (!init_populate)
		return 0;

	printf("Starting rw test\n");

	for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
		struct cds_ja_range *range;
		uint64_t key;

		/* note: only inserting ulong keys */
		key = (unsigned long) iter;
		key *= key_mul;
		rcu_read_lock();
		ret = cds_ja_range_add(test_ja, key, key, NULL);
		URCU_TLS(nr_add)++;
		URCU_TLS(nr_writes)++;
		rcu_read_unlock();
		if (ret) {
			fprintf(stderr, "Error (%d) adding range %" PRIu64 "\n",
				ret, key);
			assert(0);
		}
	}
	return 0;
}

static
int do_mt_test(void)
{
	pthread_t *tid_reader, *tid_writer;
	void *tret;
	int ret, i, err;
	unsigned long long *count_reader;
	struct wr_count *count_writer;
	unsigned long long tot_reads = 0, tot_writes = 0,
		tot_add = 0, tot_add_exist = 0, tot_remove = 0;
	unsigned int remain;

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

	printf("Allocating Judy Array for ranges\n");
	test_ja = cds_ja_range_new();
	if (!test_ja) {
		printf("Error allocating judy array.\n");
		ret = -1;
		goto end;
	}

	do_mt_populate_ja();

	next_aff = 0;

	for (i = 0; i < nr_readers; i++) {
		err = pthread_create(&tid_reader[i],
				     NULL, test_ja_rw_thr_reader,
				     &count_reader[i]);
		if (err != 0)
			exit(1);
	}
	for (i = 0; i < nr_writers; i++) {
		err = pthread_create(&tid_writer[i],
				     NULL, test_ja_rw_thr_writer,
				     &count_writer[i]);
		if (err != 0)
			exit(1);
	}

	cmm_smp_mb();

	test_go = 1;

	rcu_thread_offline_qsbr();

	remain = duration;
	do {
		remain = sleep(remain);
	} while (remain > 0);

	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].update_ops;
		tot_add += count_writer[i].add;
		tot_add_exist += count_writer[i].add_exist;
		tot_remove += count_writer[i].remove;
	}
	rcu_thread_online_qsbr();

	ret = cds_ja_range_destroy(test_ja, NULL);
	if (ret) {
		fprintf(stderr, "Error destroying judy array\n");
		goto end;
	}

	free(tid_reader);
	free(tid_writer);
	free(count_reader);
	free(count_writer);
	ret = 0;
end:
	return ret;
}

int main(int argc, char **argv)
{
	int i, j, a, ret, err;
	uint64_t key;
	struct sigaction act;

	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 'v':
			verbose_mode = 1;
			break;
		case 'r':
			add_ratio = atoi(argv[++i]);
			break;
		case 'k':
			init_populate = 1;
			break;
		case 'R':
			lookup_pool_offset = atol(argv[++i]);
			break;
		case 'S':
			write_pool_offset = atol(argv[++i]);
			break;
		case 'T':
			init_pool_offset = atol(argv[++i]);
			break;
		case 'M':
			lookup_pool_size = atol(argv[++i]);
			break;
		case 'N':
			write_pool_size = atol(argv[++i]);
			break;
		case 'O':
			init_pool_size = atol(argv[++i]);
			break;
		case 'V':
			validate_lookup = 1;
			break;
		case 't':
			sanity_test = 1;
			break;
		case 'B':
			key_bits = atol(argv[++i]);
			break;
		case 'm':
			key_mul = atoll(argv[++i]);
			break;
		case 'u':
			add_unique = 1;
			break;
		case 's':
			add_replace = 1;
			break;
		case 'l':
			leak_detection = 1;
			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("Add ratio: %u%%.\n", add_ratio);
	printf_verbose("Mode:%s%s.\n",
		" add/remove",
		add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
	printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
	printf_verbose("Init pool size offset %lu size %lu.\n",
		init_pool_offset, init_pool_size);
	printf_verbose("Lookup pool size offset %lu size %lu.\n",
		lookup_pool_offset, lookup_pool_size);
	printf_verbose("Update pool size offset %lu size %lu.\n",
		write_pool_offset, write_pool_size);
	if (validate_lookup)
		printf_verbose("Validating lookups.\n");
	if (leak_detection)
		printf_verbose("Memory leak dection activated.\n");
	printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
			"main", pthread_self(), (unsigned long)gettid());

	memset(&act, 0, sizeof(act));
	ret = sigemptyset(&act.sa_mask);
	if (ret == -1) {
		perror("sigemptyset");
		return -1;
	}
	act.sa_handler = test_ja_rw_sigusr1_handler;
	act.sa_flags = SA_RESTART;
	ret = sigaction(SIGUSR1, &act, NULL);
	if (ret == -1) {
		perror("sigaction");
		return -1;
	}

	err = create_all_cpu_call_rcu_data(0);
	if (err) {
		printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
	}

	rcu_register_thread();

	ret = do_mt_test();

	/* Wait for in-flight call_rcu free to complete for leak detection */
	rcu_barrier();

	rcu_unregister_thread();
	free_all_cpu_call_rcu_data();

	if (ret) {
		printf("Test ended with error: %d\n", ret);
	}
	return ret;
}
Commit	Line	Data
91233b5b MD	1	/*
	2	* test_urcu_ja_range.c
	3	*
	4	* Userspace RCU library - test program
	5	*
	6	* Copyright 2009-2012 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
	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	#include "test_urcu_ja_range.h"
	25	#include <inttypes.h>
	26	#include <stdint.h>
	27
	28	DEFINE_URCU_TLS(unsigned int, rand_lookup);
	29	DEFINE_URCU_TLS(unsigned long, nr_add);
	30	DEFINE_URCU_TLS(unsigned long, nr_addexist);
	31	DEFINE_URCU_TLS(unsigned long, nr_del);
	32	DEFINE_URCU_TLS(unsigned long, nr_delnoent);
	33	DEFINE_URCU_TLS(unsigned long, lookup_fail);
	34	DEFINE_URCU_TLS(unsigned long, lookup_ok);
	35
	36	struct cds_ja *test_ja;
	37
	38	volatile int test_go, test_stop;
	39
	40	unsigned long wdelay;
	41
	42	unsigned long duration;
	43
	44	/* read-side C.S. duration, in loops */
	45	unsigned long rduration;
	46
	47	unsigned long init_populate;
	48	int add_only;
	49
	50	unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
	51	unsigned long init_pool_size = DEFAULT_RAND_POOL,
	52	lookup_pool_size = DEFAULT_RAND_POOL,
	53	write_pool_size = DEFAULT_RAND_POOL;
	54	int validate_lookup;
	55	int sanity_test;
	56	unsigned int key_bits = 32;
	57
	58	int count_pipe[2];
	59
	60	int verbose_mode;
	61
	62	unsigned int cpu_affinities[NR_CPUS];
	63	unsigned int next_aff = 0;
	64	int use_affinity = 0;
65
66	pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;
67
68	DEFINE_URCU_TLS(unsigned long long, nr_writes);
69	DEFINE_URCU_TLS(unsigned long long, nr_reads);
70
71	unsigned int nr_readers;
72	unsigned int nr_writers;
73
74	static unsigned int add_ratio = 50;
75	static uint64_t key_mul = 1ULL;
76
77	static int add_unique, add_replace;
78
79	static pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
80
81	static int leak_detection;
82	static unsigned long test_nodes_allocated, test_nodes_freed;
83
84	void set_affinity(void)
85	{
86	cpu_set_t mask;
87	int cpu;
88	int ret;
89
90	if (!use_affinity)
91	return;
92
93	#if HAVE_SCHED_SETAFFINITY
94	ret = pthread_mutex_lock(&affinity_mutex);
95	if (ret) {
96	perror("Error in pthread mutex lock");
97	exit(-1);
98	}
99	cpu = cpu_affinities[next_aff++];
100	ret = pthread_mutex_unlock(&affinity_mutex);
101	if (ret) {
102	perror("Error in pthread mutex unlock");
103	exit(-1);
104	}
105	CPU_ZERO(&mask);
106	CPU_SET(cpu, &mask);
107	#if SCHED_SETAFFINITY_ARGS == 2
108	sched_setaffinity(0, &mask);
109	#else
110	sched_setaffinity(0, sizeof(mask), &mask);
111	#endif
112	#endif /* HAVE_SCHED_SETAFFINITY */
113	}
114
115	void rcu_copy_mutex_lock(void)
116	{
117	int ret;
118	ret = pthread_mutex_lock(&rcu_copy_mutex);
119	if (ret) {
120	perror("Error in pthread mutex lock");
121	exit(-1);
122	}
123	}
124
125	void rcu_copy_mutex_unlock(void)
126	{
127	int ret;
128
129	ret = pthread_mutex_unlock(&rcu_copy_mutex);
130	if (ret) {
131	perror("Error in pthread mutex unlock");
132	exit(-1);
133	}
134	}
135
136	void show_usage(int argc, char **argv)
137	{
138	printf("Usage : %s nr_readers nr_writers duration (s)\n", argv[0]);
139	#ifdef DEBUG_YIELD
140	printf(" [-r] [-w] (yield reader and/or writer)\n");
141	#endif
142	printf(" [-d delay] (writer period (us))\n");
143	printf(" [-c duration] (reader C.S. duration (in loops))\n");
144	printf(" [-v] (verbose output)\n");
145	printf(" [-a cpu#] [-a cpu#]... (affinity)\n");
146	printf(" [-u] Add unique keys.\n");
147	printf(" [-s] Replace existing keys.\n");
148	printf(" [not -u nor -s] Add entries (supports redundant keys).\n");
149	printf(" [-r ratio] Add ratio (in %% of add+removal).\n");
150	printf(" [-k] Populate init nodes.\n");
151	printf(" [-R offset] Lookup pool offset.\n");
152	printf(" [-S offset] Write pool offset.\n");
153	printf(" [-T offset] Init pool offset.\n");
154	printf(" [-M size] Lookup pool size.\n");
155	printf(" [-N size] Write pool size.\n");
156	printf(" [-O size] Init pool size.\n");
157	printf(" [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
158	printf(" [-t] Do sanity test.\n");
159	printf(" [-B] Key bits for multithread test (default: 32).\n");
160	printf(" [-m factor] Key multiplication factor.\n");
161	printf(" [-l] Memory leak detection.\n");
162	printf("\n\n");
163	}
164
165	enum urcu_ja_addremove {
166	AR_RANDOM = 0,
167	AR_ADD = 1,
168	AR_REMOVE = -1,
169	}; /* 1: add, -1 remove, 0: random */
170
171	static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
172
173	static
174	void test_ja_rw_sigusr1_handler(int signo)
175	{
176	switch (addremove) {
177	case AR_ADD:
178	printf("Add/Remove: random.\n");
179	addremove = AR_RANDOM;
180	break;
181	case AR_RANDOM:
182	printf("Add/Remove: remove only.\n");
183	addremove = AR_REMOVE;
184	break;
185	case AR_REMOVE:
186	printf("Add/Remove: add only.\n");
187	addremove = AR_ADD;
188	break;
189	}
190	}
191
192	static
193	void test_ja_rw_thr_reader(void _count)
194	{
195	unsigned long long *count = _count;
196	struct cds_ja_range *range;
197	uint64_t key;
198
199	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
200	"reader", pthread_self(), (unsigned long) gettid());
201
202	set_affinity();
203
204	rcu_register_thread();
205
206	while (!test_go)
207	{
208	}
209	cmm_smp_mb();
210
211	for (;;) {
212	rcu_read_lock();
213
214	/* note: only looking up ulong keys */
215	key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
216	key *= key_mul;
217	range = cds_ja_range_lookup(test_ja, key);
218	if (!range) {
219	if (validate_lookup) {
220	printf("[ERROR] Lookup cannot find initial node.\n");
221	exit(-1);
222	}
223	URCU_TLS(lookup_fail)++;
224	} else {
225	range = cds_ja_range_lock(range);
226	if (!range) {
227	if (validate_lookup) {
228	printf("[ERROR] Lookup cannot find initial node.\n");
229	exit(-1);
230	}
231	} else {
232	URCU_TLS(lookup_ok)++;
233	cds_ja_range_unlock(range);
234	}
235	}
236	rcu_debug_yield_read();
237	if (caa_unlikely(rduration))
238	loop_sleep(rduration);
239	rcu_read_unlock();
240	URCU_TLS(nr_reads)++;
241	if (caa_unlikely(!test_duration_read()))
242	break;
243	if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
244	rcu_quiescent_state();
245	}
246
247	rcu_unregister_thread();
248
249	*count = URCU_TLS(nr_reads);
250	printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
251	"reader", pthread_self(), (unsigned long) gettid());
252	printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
253	pthread_self(), URCU_TLS(lookup_fail),
254	URCU_TLS(lookup_ok));
255	return ((void*)1);
256	}
257
258	static
259	int is_add(void)
260	{
261	return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
262	}
263
264	static
265	void test_ja_rw_thr_writer(void _count)
266	{
267	struct wr_count *count = _count;
268	int ret;
269
270	printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
271	"writer", pthread_self(), (unsigned long) gettid());
272
273	set_affinity();
274
275	rcu_register_thread();
276
277	while (!test_go)
278	{
279	}
280	cmm_smp_mb();
281
282	for (;;) {
283	if ((addremove == AR_ADD)
284	\|\| (addremove == AR_RANDOM && is_add())) {
285	struct cds_ja_range *range;
286	uint64_t start, end, tmp;
287
288	/* note: only inserting ulong keys */
289	start = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
290	end = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
291	start *= key_mul;
292	end *= key_mul;
293	if (start > end) {
294	tmp = start;
295	start = end;
296	end = tmp;
297	}
298	rcu_read_lock();
cd7eb7a3 MD	299	ret = cds_ja_range_add(test_ja, start, end, NULL);
	300	if (ret) {
	301	if (ret == -EEXIST) {
	302	URCU_TLS(nr_addexist)++;
	303	} else {
	304	assert(0);
	305	}
91233b5b MD	306	} else {
	307	URCU_TLS(nr_add)++;
	308	}
	309	rcu_read_unlock();
	310	} else {
	311	struct cds_ja_range *range;
	312	uint64_t key;
	313
	314	/* May delete */
	315	/* note: only deleting ulong keys */
	316	key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
	317	key *= key_mul;
	318
	319	rcu_read_lock();
	320
	321	range = cds_ja_range_lookup(test_ja, key);
	322	if (range) {
	323	ret = cds_ja_range_del(test_ja, range);
	324	if (!ret) {
	325	URCU_TLS(nr_del)++;
	326	} else {
	327	URCU_TLS(nr_delnoent)++;
	328	}
	329	} else {
	330	URCU_TLS(nr_delnoent)++;
	331	}
	332	rcu_read_unlock();
	333	}
	334
	335	URCU_TLS(nr_writes)++;
	336	if (caa_unlikely(!test_duration_write()))
	337	break;
	338	if (caa_unlikely(wdelay))
	339	loop_sleep(wdelay);
	340	if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
	341	rcu_quiescent_state();
	342	}
	343
	344	rcu_unregister_thread();
	345
	346	printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
	347	"writer", pthread_self(), (unsigned long) gettid());
	348	printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
	349	"nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
	350	URCU_TLS(nr_addexist), URCU_TLS(nr_del),
	351	URCU_TLS(nr_delnoent));
	352	count->update_ops = URCU_TLS(nr_writes);
	353	count->add = URCU_TLS(nr_add);
	354	count->add_exist = URCU_TLS(nr_addexist);
	355	count->remove = URCU_TLS(nr_del);
	356	return ((void*)2);
	357	}
	358
	359	static
	360	int do_mt_populate_ja(void)
	361	{
	362	uint64_t iter;
	363	int ret;
	364
	365	if (!init_populate)
	366	return 0;
	367
	368	printf("Starting rw test\n");
	369
370	for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
371	struct cds_ja_range *range;
372	uint64_t key;
373
374	/* note: only inserting ulong keys */
375	key = (unsigned long) iter;
376	key *= key_mul;
377	rcu_read_lock();
cd7eb7a3	378	ret = cds_ja_range_add(test_ja, key, key, NULL);
91233b5b MD	379	URCU_TLS(nr_add)++;
	380	URCU_TLS(nr_writes)++;
	381	rcu_read_unlock();
cd7eb7a3 MD	382	if (ret) {
	383	fprintf(stderr, "Error (%d) adding range %" PRIu64 "\n",
	384	ret, key);
91233b5b MD	385	assert(0);
	386	}
	387	}
	388	return 0;
	389	}
	390
	391	static
	392	int do_mt_test(void)
	393	{
	394	pthread_t tid_reader, tid_writer;
	395	void *tret;
	396	int ret, i, err;
	397	unsigned long long *count_reader;
	398	struct wr_count *count_writer;
	399	unsigned long long tot_reads = 0, tot_writes = 0,
	400	tot_add = 0, tot_add_exist = 0, tot_remove = 0;
	401	unsigned int remain;
	402
	403	tid_reader = malloc(sizeof(tid_reader) nr_readers);
	404	tid_writer = malloc(sizeof(tid_writer) nr_writers);
	405	count_reader = malloc(sizeof(count_reader) nr_readers);
	406	count_writer = malloc(sizeof(count_writer) nr_writers);
	407
	408	printf("Allocating Judy Array for ranges\n");
	409	test_ja = cds_ja_range_new();
	410	if (!test_ja) {
	411	printf("Error allocating judy array.\n");
	412	ret = -1;
	413	goto end;
	414	}
	415
	416	do_mt_populate_ja();
	417
	418	next_aff = 0;
	419
	420	for (i = 0; i < nr_readers; i++) {
	421	err = pthread_create(&tid_reader[i],
	422	NULL, test_ja_rw_thr_reader,
	423	&count_reader[i]);
	424	if (err != 0)
	425	exit(1);
	426	}
	427	for (i = 0; i < nr_writers; i++) {
	428	err = pthread_create(&tid_writer[i],
	429	NULL, test_ja_rw_thr_writer,
	430	&count_writer[i]);
	431	if (err != 0)
	432	exit(1);
	433	}
	434
	435	cmm_smp_mb();
	436
	437	test_go = 1;
	438
	439	rcu_thread_offline_qsbr();
	440
	441	remain = duration;
	442	do {
	443	remain = sleep(remain);
	444	} while (remain > 0);
	445
	446	test_stop = 1;
	447
	448	for (i = 0; i < nr_readers; i++) {
449	err = pthread_join(tid_reader[i], &tret);
450	if (err != 0)
451	exit(1);
452	tot_reads += count_reader[i];
453	}
454	for (i = 0; i < nr_writers; i++) {
455	err = pthread_join(tid_writer[i], &tret);
456	if (err != 0)
457	exit(1);
458	tot_writes += count_writer[i].update_ops;
459	tot_add += count_writer[i].add;
460	tot_add_exist += count_writer[i].add_exist;
461	tot_remove += count_writer[i].remove;
462	}
463	rcu_thread_online_qsbr();
464
465	ret = cds_ja_range_destroy(test_ja, NULL);
466	if (ret) {
467	fprintf(stderr, "Error destroying judy array\n");
468	goto end;
469	}
470
471	free(tid_reader);
472	free(tid_writer);
473	free(count_reader);
474	free(count_writer);
475	ret = 0;
476	end:
477	return ret;
478	}
479
480	int main(int argc, char **argv)
481	{
482	int i, j, a, ret, err;
483	uint64_t key;
484	struct sigaction act;
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 'v':
546	verbose_mode = 1;
547	break;
548	case 'r':
549	add_ratio = atoi(argv[++i]);
550	break;
551	case 'k':
552	init_populate = 1;
553	break;
554	case 'R':
555	lookup_pool_offset = atol(argv[++i]);
556	break;
557	case 'S':
558	write_pool_offset = atol(argv[++i]);
559	break;
560	case 'T':
561	init_pool_offset = atol(argv[++i]);
562	break;
563	case 'M':
564	lookup_pool_size = atol(argv[++i]);
565	break;
566	case 'N':
567	write_pool_size = atol(argv[++i]);
568	break;
569	case 'O':
570	init_pool_size = atol(argv[++i]);
571	break;
572	case 'V':
573	validate_lookup = 1;
574	break;
575	case 't':
576	sanity_test = 1;
577	break;
578	case 'B':
579	key_bits = atol(argv[++i]);
580	break;
581	case 'm':
582	key_mul = atoll(argv[++i]);
583	break;
584	case 'u':
585	add_unique = 1;
586	break;
587	case 's':
588	add_replace = 1;
589	break;
590	case 'l':
591	leak_detection = 1;
592	break;
593	}
594	}
595
596	printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
597	duration, nr_readers, nr_writers);
598	printf_verbose("Writer delay : %lu loops.\n", wdelay);
599	printf_verbose("Reader duration : %lu loops.\n", rduration);
600	printf_verbose("Add ratio: %u%%.\n", add_ratio);
601	printf_verbose("Mode:%s%s.\n",
602	" add/remove",
603	add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
604	printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
605	printf_verbose("Init pool size offset %lu size %lu.\n",
606	init_pool_offset, init_pool_size);
607	printf_verbose("Lookup pool size offset %lu size %lu.\n",
608	lookup_pool_offset, lookup_pool_size);
609	printf_verbose("Update pool size offset %lu size %lu.\n",
610	write_pool_offset, write_pool_size);
611	if (validate_lookup)
612	printf_verbose("Validating lookups.\n");
613	if (leak_detection)
614	printf_verbose("Memory leak dection activated.\n");
615	printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
616	"main", pthread_self(), (unsigned long)gettid());
617
618	memset(&act, 0, sizeof(act));
619	ret = sigemptyset(&act.sa_mask);
620	if (ret == -1) {
621	perror("sigemptyset");
622	return -1;
623	}
624	act.sa_handler = test_ja_rw_sigusr1_handler;
625	act.sa_flags = SA_RESTART;
626	ret = sigaction(SIGUSR1, &act, NULL);
627	if (ret == -1) {
628	perror("sigaction");
629	return -1;
630	}
631
632	err = create_all_cpu_call_rcu_data(0);
633	if (err) {
634	printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
635	}
636
637	rcu_register_thread();
638
639	ret = do_mt_test();
640
641	/* Wait for in-flight call_rcu free to complete for leak detection */
642	rcu_barrier();
643
644	rcu_unregister_thread();
645	free_all_cpu_call_rcu_data();
646
647	if (ret) {
648	printf("Test ended with error: %d\n", ret);
649	}
650	return ret;
651	}