[linux-2.6-block.git] / lib / test_rhashtable.c

/*
 * Resizable, Scalable, Concurrent Hash Table
 *
 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */

/**************************************************************************
 * Self Test
 **************************************************************************/

#include <linux/init.h>
#include <linux/jhash.h>
#include <linux/kernel.h>
#include <linux/kthread.h>
#include <linux/module.h>
#include <linux/rcupdate.h>
#include <linux/rhashtable.h>
#include <linux/semaphore.h>
#include <linux/slab.h>
#include <linux/sched.h>
#include <linux/vmalloc.h>

#define MAX_ENTRIES	1000000
#define TEST_INSERT_FAIL INT_MAX

static int entries = 50000;
module_param(entries, int, 0);
MODULE_PARM_DESC(entries, "Number of entries to add (default: 50000)");

static int runs = 4;
module_param(runs, int, 0);
MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");

static int max_size = 0;
module_param(max_size, int, 0);
MODULE_PARM_DESC(runs, "Maximum table size (default: calculated)");

static bool shrinking = false;
module_param(shrinking, bool, 0);
MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");

static int size = 8;
module_param(size, int, 0);
MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");

static int tcount = 10;
module_param(tcount, int, 0);
MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)");

static bool enomem_retry = false;
module_param(enomem_retry, bool, 0);
MODULE_PARM_DESC(enomem_retry, "Retry insert even if -ENOMEM was returned (default: off)");

struct test_obj {
	int			value;
	struct rhash_head	node;
};

struct thread_data {
	int id;
	struct task_struct *task;
	struct test_obj *objs;
};

static struct test_obj array[MAX_ENTRIES];

static struct rhashtable_params test_rht_params = {
	.head_offset = offsetof(struct test_obj, node),
	.key_offset = offsetof(struct test_obj, value),
	.key_len = sizeof(int),
	.hashfn = jhash,
	.nulls_base = (3U << RHT_BASE_SHIFT),
};

static struct semaphore prestart_sem;
static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);

static int insert_retry(struct rhashtable *ht, struct rhash_head *obj,
                        const struct rhashtable_params params)
{
	int err, retries = -1, enomem_retries = 0;

	do {
		retries++;
		cond_resched();
		err = rhashtable_insert_fast(ht, obj, params);
		if (err == -ENOMEM && enomem_retry) {
			enomem_retries++;
			err = -EBUSY;
		}
	} while (err == -EBUSY);

	if (enomem_retries)
		pr_info(" %u insertions retried after -ENOMEM\n",
			enomem_retries);

	return err ? : retries;
}

static int __init test_rht_lookup(struct rhashtable *ht)
{
	unsigned int i;

	for (i = 0; i < entries * 2; i++) {
		struct test_obj *obj;
		bool expected = !(i % 2);
		u32 key = i;

		if (array[i / 2].value == TEST_INSERT_FAIL)
			expected = false;

		obj = rhashtable_lookup_fast(ht, &key, test_rht_params);

		if (expected && !obj) {
			pr_warn("Test failed: Could not find key %u\n", key);
			return -ENOENT;
		} else if (!expected && obj) {
			pr_warn("Test failed: Unexpected entry found for key %u\n",
				key);
			return -EEXIST;
		} else if (expected && obj) {
			if (obj->value != i) {
				pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
					obj->value, i);
				return -EINVAL;
			}
		}

		cond_resched_rcu();
	}

	return 0;
}

static void test_bucket_stats(struct rhashtable *ht)
{
	unsigned int err, total = 0, chain_len = 0;
	struct rhashtable_iter hti;
	struct rhash_head *pos;

	err = rhashtable_walk_init(ht, &hti);
	if (err) {
		pr_warn("Test failed: allocation error");
		return;
	}

	err = rhashtable_walk_start(&hti);
	if (err && err != -EAGAIN) {
		pr_warn("Test failed: iterator failed: %d\n", err);
		return;
	}

	while ((pos = rhashtable_walk_next(&hti))) {
		if (PTR_ERR(pos) == -EAGAIN) {
			pr_info("Info: encountered resize\n");
			chain_len++;
			continue;
		} else if (IS_ERR(pos)) {
			pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
				PTR_ERR(pos));
			break;
		}

		total++;
	}

	rhashtable_walk_stop(&hti);
	rhashtable_walk_exit(&hti);

	pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n",
		total, atomic_read(&ht->nelems), entries, chain_len);

	if (total != atomic_read(&ht->nelems) || total != entries)
		pr_warn("Test failed: Total count mismatch ^^^");
}

static s64 __init test_rhashtable(struct rhashtable *ht)
{
	struct test_obj *obj;
	int err;
	unsigned int i, insert_retries = 0;
	s64 start, end;

	/*
	 * Insertion Test:
	 * Insert entries into table with all keys even numbers
	 */
	pr_info("  Adding %d keys\n", entries);
	start = ktime_get_ns();
	for (i = 0; i < entries; i++) {
		struct test_obj *obj = &array[i];

		obj->value = i * 2;
		err = insert_retry(ht, &obj->node, test_rht_params);
		if (err > 0)
			insert_retries += err;
		else if (err)
			return err;
	}

	if (insert_retries)
		pr_info("  %u insertions retried due to memory pressure\n",
			insert_retries);

	test_bucket_stats(ht);
	rcu_read_lock();
	test_rht_lookup(ht);
	rcu_read_unlock();

	test_bucket_stats(ht);

	pr_info("  Deleting %d keys\n", entries);
	for (i = 0; i < entries; i++) {
		u32 key = i * 2;

		if (array[i].value != TEST_INSERT_FAIL) {
			obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
			BUG_ON(!obj);

			rhashtable_remove_fast(ht, &obj->node, test_rht_params);
		}

		cond_resched();
	}

	end = ktime_get_ns();
	pr_info("  Duration of test: %lld ns\n", end - start);

	return end - start;
}

static struct rhashtable ht;

static int thread_lookup_test(struct thread_data *tdata)
{
	int i, err = 0;

	for (i = 0; i < entries; i++) {
		struct test_obj *obj;
		int key = (tdata->id << 16) | i;

		obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
		if (obj && (tdata->objs[i].value == TEST_INSERT_FAIL)) {
			pr_err("  found unexpected object %d\n", key);
			err++;
		} else if (!obj && (tdata->objs[i].value != TEST_INSERT_FAIL)) {
			pr_err("  object %d not found!\n", key);
			err++;
		} else if (obj && (obj->value != key)) {
			pr_err("  wrong object returned (got %d, expected %d)\n",
			       obj->value, key);
			err++;
		}

		cond_resched();
	}
	return err;
}

static int threadfunc(void *data)
{
	int i, step, err = 0, insert_retries = 0;
	struct thread_data *tdata = data;

	up(&prestart_sem);
	if (down_interruptible(&startup_sem))
		pr_err("  thread[%d]: down_interruptible failed\n", tdata->id);

	for (i = 0; i < entries; i++) {
		tdata->objs[i].value = (tdata->id << 16) | i;
		err = insert_retry(&ht, &tdata->objs[i].node, test_rht_params);
		if (err > 0) {
			insert_retries += err;
		} else if (err) {
			pr_err("  thread[%d]: rhashtable_insert_fast failed\n",
			       tdata->id);
			goto out;
		}
	}
	if (insert_retries)
		pr_info("  thread[%d]: %u insertions retried due to memory pressure\n",
			tdata->id, insert_retries);

	err = thread_lookup_test(tdata);
	if (err) {
		pr_err("  thread[%d]: rhashtable_lookup_test failed\n",
		       tdata->id);
		goto out;
	}

	for (step = 10; step > 0; step--) {
		for (i = 0; i < entries; i += step) {
			if (tdata->objs[i].value == TEST_INSERT_FAIL)
				continue;
			err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
			                             test_rht_params);
			if (err) {
				pr_err("  thread[%d]: rhashtable_remove_fast failed\n",
				       tdata->id);
				goto out;
			}
			tdata->objs[i].value = TEST_INSERT_FAIL;

			cond_resched();
		}
		err = thread_lookup_test(tdata);
		if (err) {
			pr_err("  thread[%d]: rhashtable_lookup_test (2) failed\n",
			       tdata->id);
			goto out;
		}
	}
out:
	while (!kthread_should_stop()) {
		set_current_state(TASK_INTERRUPTIBLE);
		schedule();
	}
	return err;
}

static int __init test_rht_init(void)
{
	int i, err, started_threads = 0, failed_threads = 0;
	u64 total_time = 0;
	struct thread_data *tdata;
	struct test_obj *objs;

	entries = min(entries, MAX_ENTRIES);

	test_rht_params.automatic_shrinking = shrinking;
	test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
	test_rht_params.nelem_hint = size;

	pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
		size, max_size, shrinking);

	for (i = 0; i < runs; i++) {
		s64 time;

		pr_info("Test %02d:\n", i);
		memset(&array, 0, sizeof(array));
		err = rhashtable_init(&ht, &test_rht_params);
		if (err < 0) {
			pr_warn("Test failed: Unable to initialize hashtable: %d\n",
				err);
			continue;
		}

		time = test_rhashtable(&ht);
		rhashtable_destroy(&ht);
		if (time < 0) {
			pr_warn("Test failed: return code %lld\n", time);
			return -EINVAL;
		}

		total_time += time;
	}

	do_div(total_time, runs);
	pr_info("Average test time: %llu\n", total_time);

	if (!tcount)
		return 0;

	pr_info("Testing concurrent rhashtable access from %d threads\n",
	        tcount);
	sema_init(&prestart_sem, 1 - tcount);
	tdata = vzalloc(tcount * sizeof(struct thread_data));
	if (!tdata)
		return -ENOMEM;
	objs  = vzalloc(tcount * entries * sizeof(struct test_obj));
	if (!objs) {
		vfree(tdata);
		return -ENOMEM;
	}

	test_rht_params.max_size = max_size ? :
	                           roundup_pow_of_two(tcount * entries);
	err = rhashtable_init(&ht, &test_rht_params);
	if (err < 0) {
		pr_warn("Test failed: Unable to initialize hashtable: %d\n",
			err);
		vfree(tdata);
		vfree(objs);
		return -EINVAL;
	}
	for (i = 0; i < tcount; i++) {
		tdata[i].id = i;
		tdata[i].objs = objs + i * entries;
		tdata[i].task = kthread_run(threadfunc, &tdata[i],
		                            "rhashtable_thrad[%d]", i);
		if (IS_ERR(tdata[i].task))
			pr_err(" kthread_run failed for thread %d\n", i);
		else
			started_threads++;
	}
	if (down_interruptible(&prestart_sem))
		pr_err("  down interruptible failed\n");
	for (i = 0; i < tcount; i++)
		up(&startup_sem);
	for (i = 0; i < tcount; i++) {
		if (IS_ERR(tdata[i].task))
			continue;
		if ((err = kthread_stop(tdata[i].task))) {
			pr_warn("Test failed: thread %d returned: %d\n",
			        i, err);
			failed_threads++;
		}
	}
	pr_info("Started %d threads, %d failed\n",
	        started_threads, failed_threads);
	rhashtable_destroy(&ht);
	vfree(tdata);
	vfree(objs);
	return 0;
}

static void __exit test_rht_exit(void)
{
}

module_init(test_rht_init);
module_exit(test_rht_exit);

MODULE_LICENSE("GPL v2");
Commit	Line	Data
9d6dbe1b GU	1	/*
	2	* Resizable, Scalable, Concurrent Hash Table
	3	*
1aa661f5	4	* Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
9d6dbe1b GU	5	* Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
9d6dbe1b GU	6	*
9d6dbe1b GU	7	* This program is free software; you can redistribute it and/or modify
	8	* it under the terms of the GNU General Public License version 2 as
	9	* published by the Free Software Foundation.
	10	*/
	11
	12	/**************************************************************************
	13	* Self Test
	14	**************************************************************************/
	15
	16	#include <linux/init.h>
	17	#include <linux/jhash.h>
	18	#include <linux/kernel.h>
f4a3e90b	19	#include <linux/kthread.h>
9d6dbe1b GU	20	#include <linux/module.h>
	21	#include <linux/rcupdate.h>
	22	#include <linux/rhashtable.h>
f4a3e90b	23	#include <linux/semaphore.h>
9d6dbe1b	24	#include <linux/slab.h>
685a015e	25	#include <linux/sched.h>
f4a3e90b	26	#include <linux/vmalloc.h>
9d6dbe1b	27
1aa661f5	28	#define MAX_ENTRIES 1000000
67b7cbf4	29	#define TEST_INSERT_FAIL INT_MAX
1aa661f5 TG	30
	31	static int entries = 50000;
	32	module_param(entries, int, 0);
	33	MODULE_PARM_DESC(entries, "Number of entries to add (default: 50000)");
	34
	35	static int runs = 4;
	36	module_param(runs, int, 0);
	37	MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");
	38
95e435af	39	static int max_size = 0;
1aa661f5	40	module_param(max_size, int, 0);
95e435af	41	MODULE_PARM_DESC(runs, "Maximum table size (default: calculated)");
1aa661f5 TG	42
	43	static bool shrinking = false;
	44	module_param(shrinking, bool, 0);
	45	MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");
	46
	47	static int size = 8;
	48	module_param(size, int, 0);
	49	MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");
9d6dbe1b	50
f4a3e90b PS	51	static int tcount = 10;
	52	module_param(tcount, int, 0);
	53	MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)");
	54
d662e037 PS	55	static bool enomem_retry = false;
	56	module_param(enomem_retry, bool, 0);
	57	MODULE_PARM_DESC(enomem_retry, "Retry insert even if -ENOMEM was returned (default: off)");
	58
9d6dbe1b	59	struct test_obj {
9d6dbe1b GU	60	int value;
	61	struct rhash_head node;
	62	};
	63
f4a3e90b PS	64	struct thread_data {
	65	int id;
	66	struct task_struct *task;
	67	struct test_obj *objs;
	68	};
	69
fcc57020 TG	70	static struct test_obj array[MAX_ENTRIES];
fcc57020 TG	71
1aa661f5	72	static struct rhashtable_params test_rht_params = {
b182aa6e HX	73	.head_offset = offsetof(struct test_obj, node),
	74	.key_offset = offsetof(struct test_obj, value),
	75	.key_len = sizeof(int),
	76	.hashfn = jhash,
b182aa6e HX	77	.nulls_base = (3U << RHT_BASE_SHIFT),
	78	};
	79
f4a3e90b PS	80	static struct semaphore prestart_sem;
	81	static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);
	82
9e9089e5 PS	83	static int insert_retry(struct rhashtable ht, struct rhash_head obj,
	84	const struct rhashtable_params params)
	85	{
d662e037	86	int err, retries = -1, enomem_retries = 0;
9e9089e5 PS	87
	88	do {
	89	retries++;
	90	cond_resched();
	91	err = rhashtable_insert_fast(ht, obj, params);
d662e037 PS	92	if (err == -ENOMEM && enomem_retry) {
	93	enomem_retries++;
	94	err = -EBUSY;
	95	}
9e9089e5 PS	96	} while (err == -EBUSY);
9e9089e5 PS	97
d662e037 PS	98	if (enomem_retries)
	99	pr_info(" %u insertions retried after -ENOMEM\n",
	100	enomem_retries);
	101
9e9089e5 PS	102	return err ? : retries;
	103	}
	104
9d6dbe1b GU	105	static int __init test_rht_lookup(struct rhashtable *ht)
	106	{
	107	unsigned int i;
	108
1aa661f5	109	for (i = 0; i < entries * 2; i++) {
9d6dbe1b GU	110	struct test_obj *obj;
	111	bool expected = !(i % 2);
	112	u32 key = i;
	113
67b7cbf4 TG	114	if (array[i / 2].value == TEST_INSERT_FAIL)
	115	expected = false;
	116
b182aa6e	117	obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
9d6dbe1b GU	118
	119	if (expected && !obj) {
	120	pr_warn("Test failed: Could not find key %u\n", key);
	121	return -ENOENT;
	122	} else if (!expected && obj) {
	123	pr_warn("Test failed: Unexpected entry found for key %u\n",
	124	key);
	125	return -EEXIST;
	126	} else if (expected && obj) {
c2c8a901 TG	127	if (obj->value != i) {
	128	pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
	129	obj->value, i);
9d6dbe1b GU	130	return -EINVAL;
	131	}
	132	}
685a015e TG	133
685a015e TG	134	cond_resched_rcu();
9d6dbe1b GU	135	}
	136
	137	return 0;
	138	}
	139
246b23a7	140	static void test_bucket_stats(struct rhashtable *ht)
9d6dbe1b	141	{
246b23a7 TG	142	unsigned int err, total = 0, chain_len = 0;
246b23a7 TG	143	struct rhashtable_iter hti;
9d6dbe1b	144	struct rhash_head *pos;
9d6dbe1b	145
246b23a7 TG	146	err = rhashtable_walk_init(ht, &hti);
	147	if (err) {
	148	pr_warn("Test failed: allocation error");
	149	return;
	150	}
9d6dbe1b	151
246b23a7 TG	152	err = rhashtable_walk_start(&hti);
	153	if (err && err != -EAGAIN) {
	154	pr_warn("Test failed: iterator failed: %d\n", err);
	155	return;
	156	}
9d6dbe1b	157
246b23a7 TG	158	while ((pos = rhashtable_walk_next(&hti))) {
	159	if (PTR_ERR(pos) == -EAGAIN) {
	160	pr_info("Info: encountered resize\n");
	161	chain_len++;
	162	continue;
	163	} else if (IS_ERR(pos)) {
	164	pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
	165	PTR_ERR(pos));
	166	break;
9d6dbe1b GU	167	}
9d6dbe1b GU	168
246b23a7	169	total++;
9d6dbe1b GU	170	}
9d6dbe1b GU	171
246b23a7 TG	172	rhashtable_walk_stop(&hti);
	173	rhashtable_walk_exit(&hti);
	174
	175	pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n",
	176	total, atomic_read(&ht->nelems), entries, chain_len);
9d6dbe1b	177
1aa661f5	178	if (total != atomic_read(&ht->nelems) \|\| total != entries)
9d6dbe1b GU	179	pr_warn("Test failed: Total count mismatch ^^^");
	180	}
	181
1aa661f5	182	static s64 __init test_rhashtable(struct rhashtable *ht)
9d6dbe1b	183	{
9d6dbe1b	184	struct test_obj *obj;
9d6dbe1b	185	int err;
9e9089e5	186	unsigned int i, insert_retries = 0;
1aa661f5	187	s64 start, end;
9d6dbe1b GU	188
	189	/*
	190	* Insertion Test:
1aa661f5	191	* Insert entries into table with all keys even numbers
9d6dbe1b	192	*/
1aa661f5 TG	193	pr_info(" Adding %d keys\n", entries);
	194	start = ktime_get_ns();
	195	for (i = 0; i < entries; i++) {
fcc57020	196	struct test_obj *obj = &array[i];
9d6dbe1b	197
9d6dbe1b	198	obj->value = i * 2;
9e9089e5 PS	199	err = insert_retry(ht, &obj->node, test_rht_params);
	200	if (err > 0)
	201	insert_retries += err;
	202	else if (err)
fcc57020	203	return err;
9d6dbe1b GU	204	}
9d6dbe1b GU	205
9e9089e5 PS	206	if (insert_retries)
	207	pr_info(" %u insertions retried due to memory pressure\n",
	208	insert_retries);
67b7cbf4	209
246b23a7	210	test_bucket_stats(ht);
9d6dbe1b	211	rcu_read_lock();
9d6dbe1b GU	212	test_rht_lookup(ht);
	213	rcu_read_unlock();
	214
246b23a7	215	test_bucket_stats(ht);
9d6dbe1b	216
1aa661f5 TG	217	pr_info(" Deleting %d keys\n", entries);
1aa661f5 TG	218	for (i = 0; i < entries; i++) {
9d6dbe1b GU	219	u32 key = i * 2;
9d6dbe1b GU	220
67b7cbf4 TG	221	if (array[i].value != TEST_INSERT_FAIL) {
	222	obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
	223	BUG_ON(!obj);
9d6dbe1b	224
67b7cbf4 TG	225	rhashtable_remove_fast(ht, &obj->node, test_rht_params);
67b7cbf4 TG	226	}
685a015e TG	227
685a015e TG	228	cond_resched();
9d6dbe1b GU	229	}
9d6dbe1b GU	230
1aa661f5 TG	231	end = ktime_get_ns();
	232	pr_info(" Duration of test: %lld ns\n", end - start);
	233
	234	return end - start;
9d6dbe1b GU	235	}
9d6dbe1b GU	236
b7f5e5c7 DB	237	static struct rhashtable ht;
b7f5e5c7 DB	238
f4a3e90b PS	239	static int thread_lookup_test(struct thread_data *tdata)
	240	{
	241	int i, err = 0;
	242
	243	for (i = 0; i < entries; i++) {
	244	struct test_obj *obj;
	245	int key = (tdata->id << 16) \| i;
	246
	247	obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
	248	if (obj && (tdata->objs[i].value == TEST_INSERT_FAIL)) {
	249	pr_err(" found unexpected object %d\n", key);
	250	err++;
	251	} else if (!obj && (tdata->objs[i].value != TEST_INSERT_FAIL)) {
	252	pr_err(" object %d not found!\n", key);
	253	err++;
	254	} else if (obj && (obj->value != key)) {
	255	pr_err(" wrong object returned (got %d, expected %d)\n",
	256	obj->value, key);
	257	err++;
	258	}
cd5b318d PS	259
cd5b318d PS	260	cond_resched();
f4a3e90b PS	261	}
	262	return err;
	263	}
	264
	265	static int threadfunc(void *data)
	266	{
9e9089e5	267	int i, step, err = 0, insert_retries = 0;
f4a3e90b PS	268	struct thread_data *tdata = data;
	269
	270	up(&prestart_sem);
	271	if (down_interruptible(&startup_sem))
	272	pr_err(" thread[%d]: down_interruptible failed\n", tdata->id);
	273
	274	for (i = 0; i < entries; i++) {
	275	tdata->objs[i].value = (tdata->id << 16) \| i;
9e9089e5 PS	276	err = insert_retry(&ht, &tdata->objs[i].node, test_rht_params);
	277	if (err > 0) {
	278	insert_retries += err;
f4a3e90b PS	279	} else if (err) {
	280	pr_err(" thread[%d]: rhashtable_insert_fast failed\n",
	281	tdata->id);
	282	goto out;
	283	}
	284	}
9e9089e5 PS	285	if (insert_retries)
	286	pr_info(" thread[%d]: %u insertions retried due to memory pressure\n",
	287	tdata->id, insert_retries);
f4a3e90b PS	288
	289	err = thread_lookup_test(tdata);
	290	if (err) {
	291	pr_err(" thread[%d]: rhashtable_lookup_test failed\n",
	292	tdata->id);
	293	goto out;
	294	}
	295
	296	for (step = 10; step > 0; step--) {
	297	for (i = 0; i < entries; i += step) {
	298	if (tdata->objs[i].value == TEST_INSERT_FAIL)
	299	continue;
	300	err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
	301	test_rht_params);
	302	if (err) {
	303	pr_err(" thread[%d]: rhashtable_remove_fast failed\n",
	304	tdata->id);
	305	goto out;
	306	}
	307	tdata->objs[i].value = TEST_INSERT_FAIL;
cd5b318d PS	308
cd5b318d PS	309	cond_resched();
f4a3e90b PS	310	}
	311	err = thread_lookup_test(tdata);
	312	if (err) {
	313	pr_err(" thread[%d]: rhashtable_lookup_test (2) failed\n",
	314	tdata->id);
	315	goto out;
	316	}
	317	}
	318	out:
	319	while (!kthread_should_stop()) {
	320	set_current_state(TASK_INTERRUPTIBLE);
	321	schedule();
	322	}
	323	return err;
	324	}
	325
9d6dbe1b GU	326	static int __init test_rht_init(void)
9d6dbe1b GU	327	{
f4a3e90b	328	int i, err, started_threads = 0, failed_threads = 0;
1aa661f5	329	u64 total_time = 0;
f4a3e90b PS	330	struct thread_data *tdata;
f4a3e90b PS	331	struct test_obj *objs;
9d6dbe1b	332
1aa661f5	333	entries = min(entries, MAX_ENTRIES);
9d6dbe1b	334
1aa661f5	335	test_rht_params.automatic_shrinking = shrinking;
95e435af	336	test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
1aa661f5	337	test_rht_params.nelem_hint = size;
9d6dbe1b	338
1aa661f5 TG	339	pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
1aa661f5 TG	340	size, max_size, shrinking);
9d6dbe1b	341
1aa661f5 TG	342	for (i = 0; i < runs; i++) {
1aa661f5 TG	343	s64 time;
9d6dbe1b	344
1aa661f5	345	pr_info("Test %02d:\n", i);
fcc57020	346	memset(&array, 0, sizeof(array));
1aa661f5 TG	347	err = rhashtable_init(&ht, &test_rht_params);
	348	if (err < 0) {
	349	pr_warn("Test failed: Unable to initialize hashtable: %d\n",
	350	err);
	351	continue;
	352	}
	353
	354	time = test_rhashtable(&ht);
	355	rhashtable_destroy(&ht);
	356	if (time < 0) {
	357	pr_warn("Test failed: return code %lld\n", time);
	358	return -EINVAL;
	359	}
	360
	361	total_time += time;
	362	}
	363
6decd63a TG	364	do_div(total_time, runs);
6decd63a TG	365	pr_info("Average test time: %llu\n", total_time);
1aa661f5	366
f4a3e90b PS	367	if (!tcount)
	368	return 0;
	369
	370	pr_info("Testing concurrent rhashtable access from %d threads\n",
	371	tcount);
	372	sema_init(&prestart_sem, 1 - tcount);
	373	tdata = vzalloc(tcount * sizeof(struct thread_data));
	374	if (!tdata)
	375	return -ENOMEM;
	376	objs = vzalloc(tcount * entries * sizeof(struct test_obj));
	377	if (!objs) {
	378	vfree(tdata);
	379	return -ENOMEM;
	380	}
	381
95e435af PS	382	test_rht_params.max_size = max_size ? :
95e435af PS	383	roundup_pow_of_two(tcount * entries);
f4a3e90b PS	384	err = rhashtable_init(&ht, &test_rht_params);
	385	if (err < 0) {
	386	pr_warn("Test failed: Unable to initialize hashtable: %d\n",
	387	err);
	388	vfree(tdata);
	389	vfree(objs);
	390	return -EINVAL;
	391	}
	392	for (i = 0; i < tcount; i++) {
	393	tdata[i].id = i;
	394	tdata[i].objs = objs + i * entries;
	395	tdata[i].task = kthread_run(threadfunc, &tdata[i],
	396	"rhashtable_thrad[%d]", i);
	397	if (IS_ERR(tdata[i].task))
	398	pr_err(" kthread_run failed for thread %d\n", i);
	399	else
	400	started_threads++;
	401	}
	402	if (down_interruptible(&prestart_sem))
	403	pr_err(" down interruptible failed\n");
	404	for (i = 0; i < tcount; i++)
	405	up(&startup_sem);
	406	for (i = 0; i < tcount; i++) {
	407	if (IS_ERR(tdata[i].task))
	408	continue;
	409	if ((err = kthread_stop(tdata[i].task))) {
	410	pr_warn("Test failed: thread %d returned: %d\n",
	411	i, err);
	412	failed_threads++;
	413	}
	414	}
	415	pr_info("Started %d threads, %d failed\n",
	416	started_threads, failed_threads);
	417	rhashtable_destroy(&ht);
	418	vfree(tdata);
	419	vfree(objs);
1aa661f5	420	return 0;
9d6dbe1b GU	421	}
9d6dbe1b GU	422
6dd0c165 DB	423	static void __exit test_rht_exit(void)
	424	{
	425	}
	426
9d6dbe1b	427	module_init(test_rht_init);
6dd0c165	428	module_exit(test_rht_exit);
9d6dbe1b GU	429
9d6dbe1b GU	430	MODULE_LICENSE("GPL v2");