[userspace-rcu.git] / tests / benchmark / test_urcu_hash_unique.c

/*
 * test_urcu_hash_unique.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.
 */

#include "test_urcu_hash.h"

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

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

void test_hash_unique_sigusr1_handler(int signo __attribute__((unused)))
{
	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;
	}
}

void test_hash_unique_sigusr2_handler(int signo __attribute__((unused)))
{
	char msg[1] = { 0x42 };
	ssize_t ret;

	do {
		ret = write(count_pipe[1], msg, 1);	/* wakeup thread */
	} while (ret == -1L && errno == EINTR);
}

void *test_hash_unique_thr_reader(void *_count)
{
	unsigned long long *count = _count;

	printf_verbose("thread_begin %s, tid %lu\n",
			"reader", urcu_get_thread_id());

	URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);

	set_affinity();

	rcu_register_thread();

	while (!test_go)
	{
	}
	cmm_smp_mb();

	for (;;) {
		struct lfht_test_node *node;
		struct cds_lfht_iter iter;
		/*
		 * iterate on whole table, ensuring that no duplicate is
		 * found.
		 */
		rcu_read_lock();
		cds_lfht_for_each_entry(test_ht, &iter, node, node) {
			struct cds_lfht_iter dup_iter;

			dup_iter = iter;
			cds_lfht_next_duplicate(test_ht, test_match,
				node->key, &dup_iter);
			if (dup_iter.node != NULL) {
				printf("[ERROR] Duplicate key %p found\n", node->key);
			}
		}
		rcu_read_unlock();

		rcu_debug_yield_read();
		if (caa_unlikely(rduration))
			loop_sleep(rduration);
		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, tid %lu\n",
			"reader", urcu_get_thread_id());
	printf_verbose("read tid : %lu, lookupfail %lu, lookupok %lu\n",
			urcu_get_thread_id(), URCU_TLS(lookup_fail),
			URCU_TLS(lookup_ok));
	return ((void*)1);

}

void *test_hash_unique_thr_writer(void *_count)
{
	struct lfht_test_node *node;
	struct cds_lfht_node *ret_node;
	struct cds_lfht_iter iter;
	struct wr_count *count = _count;
	int ret;
	int loc_add_unique;

	printf_verbose("thread_begin %s, tid %lu\n",
			"writer", urcu_get_thread_id());

	URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);

	set_affinity();

	rcu_register_thread();

	while (!test_go)
	{
	}
	cmm_smp_mb();

	for (;;) {
		/*
		 * add unique/add replace with new node key from range.
		 */
		if (1 || (addremove == AR_ADD || add_only)
				|| (addremove == AR_RANDOM && rand_r(&URCU_TLS(rand_lookup)) & 1)) {
			node = malloc(sizeof(struct lfht_test_node));
			lfht_test_node_init(node,
				(void *)(((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset),
				sizeof(void *));
			rcu_read_lock();
			loc_add_unique = rand_r(&URCU_TLS(rand_lookup)) & 1;
			if (loc_add_unique) {
				ret_node = cds_lfht_add_unique(test_ht,
					test_hash(node->key, node->key_len, TEST_HASH_SEED),
					test_match, node->key, &node->node);
			} else {
				ret_node = cds_lfht_add_replace(test_ht,
						test_hash(node->key, node->key_len, TEST_HASH_SEED),
						test_match, node->key, &node->node);
#if 0 //generate an error on purpose
				cds_lfht_add(test_ht,
						test_hash(node->key, node->key_len, TEST_HASH_SEED),
						&node->node);
				ret_node = NULL;
#endif //0
			}
			rcu_read_unlock();
			if (loc_add_unique) {
				if (ret_node != &node->node) {
					free(node);
					URCU_TLS(nr_addexist)++;
				} else {
					URCU_TLS(nr_add)++;
				}
			} else {
				if (ret_node) {
					call_rcu(&to_test_node(ret_node)->head,
							free_node_cb);
					URCU_TLS(nr_addexist)++;
				} else {
					URCU_TLS(nr_add)++;
				}
			}
		} else {
			/* May delete */
			rcu_read_lock();
			cds_lfht_test_lookup(test_ht,
				(void *)(((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset),
				sizeof(void *), &iter);
			ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter));
			rcu_read_unlock();
			if (ret == 0) {
				node = cds_lfht_iter_get_test_node(&iter);
				call_rcu(&node->head, free_node_cb);
				URCU_TLS(nr_del)++;
			} else
				URCU_TLS(nr_delnoent)++;
		}
#if 0
		//if (URCU_TLS(nr_writes) % 100000 == 0) {
		if (URCU_TLS(nr_writes) % 1000 == 0) {
			rcu_read_lock();
			if (rand_r(&URCU_TLS(rand_lookup)) & 1) {
				ht_resize(test_ht, 1);
			} else {
				ht_resize(test_ht, -1);
			}
			rcu_read_unlock();
		}
#endif //0
		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, tid %lu\n",
			"writer", urcu_get_thread_id());
	printf_verbose("info tid %lu: nr_add %lu, nr_addexist %lu, nr_del %lu, "
			"nr_delnoent %lu\n", urcu_get_thread_id(),
			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);
}

int test_hash_unique_populate_hash(void)
{
	struct lfht_test_node *node;
	struct cds_lfht_node *ret_node;

	printf("Starting uniqueness test.\n");

	URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);

	if (!init_populate)
		return 0;

	if (init_populate * 10 > init_pool_size) {
		printf("WARNING: required to populate %lu nodes (-k), but random "
"pool is quite small (%lu values) and we are in add_unique (-u) or add_replace (-s) mode. Try with a "
"larger random pool (-p option). This may take a while...\n", init_populate, init_pool_size);
	}

	while (URCU_TLS(nr_add) < init_populate) {
		node = malloc(sizeof(struct lfht_test_node));
		lfht_test_node_init(node,
			(void *)(((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % init_pool_size) + init_pool_offset),
			sizeof(void *));
		rcu_read_lock();
		ret_node = cds_lfht_add_replace(test_ht,
				test_hash(node->key, node->key_len, TEST_HASH_SEED),
				test_match, node->key, &node->node);
		rcu_read_unlock();
		if (ret_node) {
			call_rcu(&to_test_node(ret_node)->head, free_node_cb);
			URCU_TLS(nr_addexist)++;
		} else {
			URCU_TLS(nr_add)++;
		}
		URCU_TLS(nr_writes)++;
	}
	return 0;
}
Commit	Line	Data
	1	/*
	2	* test_urcu_hash_unique.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	#include "test_urcu_hash.h"
	24
	25	enum urcu_hash_addremove {
	26	AR_RANDOM = 0,
	27	AR_ADD = 1,
	28	AR_REMOVE = -1,
	29	}; /* 1: add, -1 remove, 0: random */
	30
	31	static enum urcu_hash_addremove addremove; /* 1: add, -1 remove, 0: random */
	32
	33	void test_hash_unique_sigusr1_handler(int signo __attribute__((unused)))
	34	{
	35	switch (addremove) {
	36	case AR_ADD:
	37	printf("Add/Remove: random.\n");
	38	addremove = AR_RANDOM;
	39	break;
	40	case AR_RANDOM:
	41	printf("Add/Remove: remove only.\n");
	42	addremove = AR_REMOVE;
	43	break;
	44	case AR_REMOVE:
	45	printf("Add/Remove: add only.\n");
	46	addremove = AR_ADD;
	47	break;
	48	}
	49	}
	50
	51	void test_hash_unique_sigusr2_handler(int signo __attribute__((unused)))
	52	{
	53	char msg[1] = { 0x42 };
	54	ssize_t ret;
	55
	56	do {
	57	ret = write(count_pipe[1], msg, 1); /* wakeup thread */
	58	} while (ret == -1L && errno == EINTR);
	59	}
	60
	61	void test_hash_unique_thr_reader(void _count)
	62	{
	63	unsigned long long *count = _count;
	64
	65	printf_verbose("thread_begin %s, tid %lu\n",
	66	"reader", urcu_get_thread_id());
	67
	68	URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);
	69
	70	set_affinity();
	71
	72	rcu_register_thread();
	73
	74	while (!test_go)
	75	{
	76	}
	77	cmm_smp_mb();
	78
	79	for (;;) {
	80	struct lfht_test_node *node;
	81	struct cds_lfht_iter iter;
	82	/*
	83	* iterate on whole table, ensuring that no duplicate is
	84	* found.
	85	*/
	86	rcu_read_lock();
	87	cds_lfht_for_each_entry(test_ht, &iter, node, node) {
	88	struct cds_lfht_iter dup_iter;
	89
	90	dup_iter = iter;
	91	cds_lfht_next_duplicate(test_ht, test_match,
	92	node->key, &dup_iter);
	93	if (dup_iter.node != NULL) {
	94	printf("[ERROR] Duplicate key %p found\n", node->key);
	95	}
	96	}
	97	rcu_read_unlock();
	98
	99	rcu_debug_yield_read();
	100	if (caa_unlikely(rduration))
	101	loop_sleep(rduration);
	102	URCU_TLS(nr_reads)++;
	103	if (caa_unlikely(!test_duration_read()))
	104	break;
	105	if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
	106	rcu_quiescent_state();
	107	}
	108
	109	rcu_unregister_thread();
	110
	111	*count = URCU_TLS(nr_reads);
	112	printf_verbose("thread_end %s, tid %lu\n",
	113	"reader", urcu_get_thread_id());
	114	printf_verbose("read tid : %lu, lookupfail %lu, lookupok %lu\n",
	115	urcu_get_thread_id(), URCU_TLS(lookup_fail),
	116	URCU_TLS(lookup_ok));
	117	return ((void*)1);
	118
	119	}
	120
	121	void test_hash_unique_thr_writer(void _count)
	122	{
	123	struct lfht_test_node *node;
	124	struct cds_lfht_node *ret_node;
	125	struct cds_lfht_iter iter;
	126	struct wr_count *count = _count;
	127	int ret;
	128	int loc_add_unique;
	129
	130	printf_verbose("thread_begin %s, tid %lu\n",
	131	"writer", urcu_get_thread_id());
	132
	133	URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);
	134
	135	set_affinity();
	136
	137	rcu_register_thread();
	138
	139	while (!test_go)
	140	{
	141	}
	142	cmm_smp_mb();
	143
	144	for (;;) {
	145	/*
	146	* add unique/add replace with new node key from range.
	147	*/
	148	if (1 \|\| (addremove == AR_ADD \|\| add_only)
	149	\|\| (addremove == AR_RANDOM && rand_r(&URCU_TLS(rand_lookup)) & 1)) {
	150	node = malloc(sizeof(struct lfht_test_node));
	151	lfht_test_node_init(node,
	152	(void *)(((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset),
	153	sizeof(void *));
	154	rcu_read_lock();
	155	loc_add_unique = rand_r(&URCU_TLS(rand_lookup)) & 1;
	156	if (loc_add_unique) {
	157	ret_node = cds_lfht_add_unique(test_ht,
	158	test_hash(node->key, node->key_len, TEST_HASH_SEED),
	159	test_match, node->key, &node->node);
	160	} else {
	161	ret_node = cds_lfht_add_replace(test_ht,
	162	test_hash(node->key, node->key_len, TEST_HASH_SEED),
	163	test_match, node->key, &node->node);
	164	#if 0 //generate an error on purpose
	165	cds_lfht_add(test_ht,
	166	test_hash(node->key, node->key_len, TEST_HASH_SEED),
	167	&node->node);
	168	ret_node = NULL;
	169	#endif //0
	170	}
	171	rcu_read_unlock();
	172	if (loc_add_unique) {
	173	if (ret_node != &node->node) {
	174	free(node);
	175	URCU_TLS(nr_addexist)++;
	176	} else {
	177	URCU_TLS(nr_add)++;
	178	}
	179	} else {
	180	if (ret_node) {
	181	call_rcu(&to_test_node(ret_node)->head,
	182	free_node_cb);
	183	URCU_TLS(nr_addexist)++;
	184	} else {
	185	URCU_TLS(nr_add)++;
	186	}
	187	}
	188	} else {
	189	/* May delete */
	190	rcu_read_lock();
	191	cds_lfht_test_lookup(test_ht,
	192	(void *)(((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset),
	193	sizeof(void *), &iter);
	194	ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter));
	195	rcu_read_unlock();
	196	if (ret == 0) {
	197	node = cds_lfht_iter_get_test_node(&iter);
	198	call_rcu(&node->head, free_node_cb);
	199	URCU_TLS(nr_del)++;
	200	} else
	201	URCU_TLS(nr_delnoent)++;
	202	}
	203	#if 0
	204	//if (URCU_TLS(nr_writes) % 100000 == 0) {
	205	if (URCU_TLS(nr_writes) % 1000 == 0) {
	206	rcu_read_lock();
	207	if (rand_r(&URCU_TLS(rand_lookup)) & 1) {
	208	ht_resize(test_ht, 1);
	209	} else {
	210	ht_resize(test_ht, -1);
	211	}
	212	rcu_read_unlock();
	213	}
	214	#endif //0
	215	URCU_TLS(nr_writes)++;
	216	if (caa_unlikely(!test_duration_write()))
	217	break;
	218	if (caa_unlikely(wdelay))
	219	loop_sleep(wdelay);
	220	if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
	221	rcu_quiescent_state();
	222	}
	223
	224	rcu_unregister_thread();
	225
	226	printf_verbose("thread_end %s, tid %lu\n",
	227	"writer", urcu_get_thread_id());
	228	printf_verbose("info tid %lu: nr_add %lu, nr_addexist %lu, nr_del %lu, "
	229	"nr_delnoent %lu\n", urcu_get_thread_id(),
	230	URCU_TLS(nr_add),
	231	URCU_TLS(nr_addexist),
	232	URCU_TLS(nr_del),
	233	URCU_TLS(nr_delnoent));
	234	count->update_ops = URCU_TLS(nr_writes);
	235	count->add = URCU_TLS(nr_add);
	236	count->add_exist = URCU_TLS(nr_addexist);
	237	count->remove = URCU_TLS(nr_del);
	238	return ((void*)2);
	239	}
	240
	241	int test_hash_unique_populate_hash(void)
	242	{
	243	struct lfht_test_node *node;
	244	struct cds_lfht_node *ret_node;
	245
	246	printf("Starting uniqueness test.\n");
	247
	248	URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);
	249
	250	if (!init_populate)
	251	return 0;
	252
	253	if (init_populate * 10 > init_pool_size) {
	254	printf("WARNING: required to populate %lu nodes (-k), but random "
	255	"pool is quite small (%lu values) and we are in add_unique (-u) or add_replace (-s) mode. Try with a "
	256	"larger random pool (-p option). This may take a while...\n", init_populate, init_pool_size);
	257	}
	258
	259	while (URCU_TLS(nr_add) < init_populate) {
	260	node = malloc(sizeof(struct lfht_test_node));
	261	lfht_test_node_init(node,
	262	(void *)(((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % init_pool_size) + init_pool_offset),
	263	sizeof(void *));
	264	rcu_read_lock();
	265	ret_node = cds_lfht_add_replace(test_ht,
	266	test_hash(node->key, node->key_len, TEST_HASH_SEED),
	267	test_match, node->key, &node->node);
	268	rcu_read_unlock();
	269	if (ret_node) {
	270	call_rcu(&to_test_node(ret_node)->head, free_node_cb);
	271	URCU_TLS(nr_addexist)++;
	272	} else {
	273	URCU_TLS(nr_add)++;
	274	}
	275	URCU_TLS(nr_writes)++;
	276	}
	277	return 0;
	278	}