xref: /openbmc/linux/lib/test_rhashtable.c (revision bdeeed09)
1 /*
2  * Resizable, Scalable, Concurrent Hash Table
3  *
4  * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
5  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
6  *
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>
19 #include <linux/kthread.h>
20 #include <linux/module.h>
21 #include <linux/rcupdate.h>
22 #include <linux/rhashtable.h>
23 #include <linux/semaphore.h>
24 #include <linux/slab.h>
25 #include <linux/sched.h>
26 #include <linux/random.h>
27 #include <linux/vmalloc.h>
28 
29 #define MAX_ENTRIES	1000000
30 #define TEST_INSERT_FAIL INT_MAX
31 
32 static int parm_entries = 50000;
33 module_param(parm_entries, int, 0);
34 MODULE_PARM_DESC(parm_entries, "Number of entries to add (default: 50000)");
35 
36 static int runs = 4;
37 module_param(runs, int, 0);
38 MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");
39 
40 static int max_size = 0;
41 module_param(max_size, int, 0);
42 MODULE_PARM_DESC(max_size, "Maximum table size (default: calculated)");
43 
44 static bool shrinking = false;
45 module_param(shrinking, bool, 0);
46 MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");
47 
48 static int size = 8;
49 module_param(size, int, 0);
50 MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");
51 
52 static int tcount = 10;
53 module_param(tcount, int, 0);
54 MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)");
55 
56 static bool enomem_retry = false;
57 module_param(enomem_retry, bool, 0);
58 MODULE_PARM_DESC(enomem_retry, "Retry insert even if -ENOMEM was returned (default: off)");
59 
60 struct test_obj_val {
61 	int	id;
62 	int	tid;
63 };
64 
65 struct test_obj {
66 	struct test_obj_val	value;
67 	struct rhash_head	node;
68 };
69 
70 struct test_obj_rhl {
71 	struct test_obj_val	value;
72 	struct rhlist_head	list_node;
73 };
74 
75 struct thread_data {
76 	unsigned int entries;
77 	int id;
78 	struct task_struct *task;
79 	struct test_obj *objs;
80 };
81 
82 static u32 my_hashfn(const void *data, u32 len, u32 seed)
83 {
84 	const struct test_obj_rhl *obj = data;
85 
86 	return (obj->value.id % 10) << RHT_HASH_RESERVED_SPACE;
87 }
88 
89 static int my_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
90 {
91 	const struct test_obj_rhl *test_obj = obj;
92 	const struct test_obj_val *val = arg->key;
93 
94 	return test_obj->value.id - val->id;
95 }
96 
97 static struct rhashtable_params test_rht_params = {
98 	.head_offset = offsetof(struct test_obj, node),
99 	.key_offset = offsetof(struct test_obj, value),
100 	.key_len = sizeof(struct test_obj_val),
101 	.hashfn = jhash,
102 	.nulls_base = (3U << RHT_BASE_SHIFT),
103 };
104 
105 static struct rhashtable_params test_rht_params_dup = {
106 	.head_offset = offsetof(struct test_obj_rhl, list_node),
107 	.key_offset = offsetof(struct test_obj_rhl, value),
108 	.key_len = sizeof(struct test_obj_val),
109 	.hashfn = jhash,
110 	.obj_hashfn = my_hashfn,
111 	.obj_cmpfn = my_cmpfn,
112 	.nelem_hint = 128,
113 	.automatic_shrinking = false,
114 };
115 
116 static struct semaphore prestart_sem;
117 static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);
118 
119 static int insert_retry(struct rhashtable *ht, struct test_obj *obj,
120                         const struct rhashtable_params params)
121 {
122 	int err, retries = -1, enomem_retries = 0;
123 
124 	do {
125 		retries++;
126 		cond_resched();
127 		err = rhashtable_insert_fast(ht, &obj->node, params);
128 		if (err == -ENOMEM && enomem_retry) {
129 			enomem_retries++;
130 			err = -EBUSY;
131 		}
132 	} while (err == -EBUSY);
133 
134 	if (enomem_retries)
135 		pr_info(" %u insertions retried after -ENOMEM\n",
136 			enomem_retries);
137 
138 	return err ? : retries;
139 }
140 
141 static int __init test_rht_lookup(struct rhashtable *ht, struct test_obj *array,
142 				  unsigned int entries)
143 {
144 	unsigned int i;
145 
146 	for (i = 0; i < entries; i++) {
147 		struct test_obj *obj;
148 		bool expected = !(i % 2);
149 		struct test_obj_val key = {
150 			.id = i,
151 		};
152 
153 		if (array[i / 2].value.id == TEST_INSERT_FAIL)
154 			expected = false;
155 
156 		obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
157 
158 		if (expected && !obj) {
159 			pr_warn("Test failed: Could not find key %u\n", key.id);
160 			return -ENOENT;
161 		} else if (!expected && obj) {
162 			pr_warn("Test failed: Unexpected entry found for key %u\n",
163 				key.id);
164 			return -EEXIST;
165 		} else if (expected && obj) {
166 			if (obj->value.id != i) {
167 				pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
168 					obj->value.id, i);
169 				return -EINVAL;
170 			}
171 		}
172 
173 		cond_resched_rcu();
174 	}
175 
176 	return 0;
177 }
178 
179 static void test_bucket_stats(struct rhashtable *ht, unsigned int entries)
180 {
181 	unsigned int err, total = 0, chain_len = 0;
182 	struct rhashtable_iter hti;
183 	struct rhash_head *pos;
184 
185 	err = rhashtable_walk_init(ht, &hti, GFP_KERNEL);
186 	if (err) {
187 		pr_warn("Test failed: allocation error");
188 		return;
189 	}
190 
191 	rhashtable_walk_start(&hti);
192 
193 	while ((pos = rhashtable_walk_next(&hti))) {
194 		if (PTR_ERR(pos) == -EAGAIN) {
195 			pr_info("Info: encountered resize\n");
196 			chain_len++;
197 			continue;
198 		} else if (IS_ERR(pos)) {
199 			pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
200 				PTR_ERR(pos));
201 			break;
202 		}
203 
204 		total++;
205 	}
206 
207 	rhashtable_walk_stop(&hti);
208 	rhashtable_walk_exit(&hti);
209 
210 	pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n",
211 		total, atomic_read(&ht->nelems), entries, chain_len);
212 
213 	if (total != atomic_read(&ht->nelems) || total != entries)
214 		pr_warn("Test failed: Total count mismatch ^^^");
215 }
216 
217 static s64 __init test_rhashtable(struct rhashtable *ht, struct test_obj *array,
218 				  unsigned int entries)
219 {
220 	struct test_obj *obj;
221 	int err;
222 	unsigned int i, insert_retries = 0;
223 	s64 start, end;
224 
225 	/*
226 	 * Insertion Test:
227 	 * Insert entries into table with all keys even numbers
228 	 */
229 	pr_info("  Adding %d keys\n", entries);
230 	start = ktime_get_ns();
231 	for (i = 0; i < entries; i++) {
232 		struct test_obj *obj = &array[i];
233 
234 		obj->value.id = i * 2;
235 		err = insert_retry(ht, obj, test_rht_params);
236 		if (err > 0)
237 			insert_retries += err;
238 		else if (err)
239 			return err;
240 	}
241 
242 	if (insert_retries)
243 		pr_info("  %u insertions retried due to memory pressure\n",
244 			insert_retries);
245 
246 	test_bucket_stats(ht, entries);
247 	rcu_read_lock();
248 	test_rht_lookup(ht, array, entries);
249 	rcu_read_unlock();
250 
251 	test_bucket_stats(ht, entries);
252 
253 	pr_info("  Deleting %d keys\n", entries);
254 	for (i = 0; i < entries; i++) {
255 		struct test_obj_val key = {
256 			.id = i * 2,
257 		};
258 
259 		if (array[i].value.id != TEST_INSERT_FAIL) {
260 			obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
261 			BUG_ON(!obj);
262 
263 			rhashtable_remove_fast(ht, &obj->node, test_rht_params);
264 		}
265 
266 		cond_resched();
267 	}
268 
269 	end = ktime_get_ns();
270 	pr_info("  Duration of test: %lld ns\n", end - start);
271 
272 	return end - start;
273 }
274 
275 static struct rhashtable ht;
276 static struct rhltable rhlt;
277 
278 static int __init test_rhltable(unsigned int entries)
279 {
280 	struct test_obj_rhl *rhl_test_objects;
281 	unsigned long *obj_in_table;
282 	unsigned int i, j, k;
283 	int ret, err;
284 
285 	if (entries == 0)
286 		entries = 1;
287 
288 	rhl_test_objects = vzalloc(sizeof(*rhl_test_objects) * entries);
289 	if (!rhl_test_objects)
290 		return -ENOMEM;
291 
292 	ret = -ENOMEM;
293 	obj_in_table = vzalloc(BITS_TO_LONGS(entries) * sizeof(unsigned long));
294 	if (!obj_in_table)
295 		goto out_free;
296 
297 	/* nulls_base not supported in rhlist interface */
298 	test_rht_params.nulls_base = 0;
299 	err = rhltable_init(&rhlt, &test_rht_params);
300 	if (WARN_ON(err))
301 		goto out_free;
302 
303 	k = prandom_u32();
304 	ret = 0;
305 	for (i = 0; i < entries; i++) {
306 		rhl_test_objects[i].value.id = k;
307 		err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
308 				      test_rht_params);
309 		if (WARN(err, "error %d on element %d\n", err, i))
310 			break;
311 		if (err == 0)
312 			set_bit(i, obj_in_table);
313 	}
314 
315 	if (err)
316 		ret = err;
317 
318 	pr_info("test %d add/delete pairs into rhlist\n", entries);
319 	for (i = 0; i < entries; i++) {
320 		struct rhlist_head *h, *pos;
321 		struct test_obj_rhl *obj;
322 		struct test_obj_val key = {
323 			.id = k,
324 		};
325 		bool found;
326 
327 		rcu_read_lock();
328 		h = rhltable_lookup(&rhlt, &key, test_rht_params);
329 		if (WARN(!h, "key not found during iteration %d of %d", i, entries)) {
330 			rcu_read_unlock();
331 			break;
332 		}
333 
334 		if (i) {
335 			j = i - 1;
336 			rhl_for_each_entry_rcu(obj, pos, h, list_node) {
337 				if (WARN(pos == &rhl_test_objects[j].list_node, "old element found, should be gone"))
338 					break;
339 			}
340 		}
341 
342 		cond_resched_rcu();
343 
344 		found = false;
345 
346 		rhl_for_each_entry_rcu(obj, pos, h, list_node) {
347 			if (pos == &rhl_test_objects[i].list_node) {
348 				found = true;
349 				break;
350 			}
351 		}
352 
353 		rcu_read_unlock();
354 
355 		if (WARN(!found, "element %d not found", i))
356 			break;
357 
358 		err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
359 		WARN(err, "rhltable_remove: err %d for iteration %d\n", err, i);
360 		if (err == 0)
361 			clear_bit(i, obj_in_table);
362 	}
363 
364 	if (ret == 0 && err)
365 		ret = err;
366 
367 	for (i = 0; i < entries; i++) {
368 		WARN(test_bit(i, obj_in_table), "elem %d allegedly still present", i);
369 
370 		err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
371 				      test_rht_params);
372 		if (WARN(err, "error %d on element %d\n", err, i))
373 			break;
374 		if (err == 0)
375 			set_bit(i, obj_in_table);
376 	}
377 
378 	pr_info("test %d random rhlist add/delete operations\n", entries);
379 	for (j = 0; j < entries; j++) {
380 		u32 i = prandom_u32_max(entries);
381 		u32 prand = prandom_u32();
382 
383 		cond_resched();
384 
385 		if (prand == 0)
386 			prand = prandom_u32();
387 
388 		if (prand & 1) {
389 			prand >>= 1;
390 			continue;
391 		}
392 
393 		err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
394 		if (test_bit(i, obj_in_table)) {
395 			clear_bit(i, obj_in_table);
396 			if (WARN(err, "cannot remove element at slot %d", i))
397 				continue;
398 		} else {
399 			if (WARN(err != -ENOENT, "removed non-existant element %d, error %d not %d",
400 			     i, err, -ENOENT))
401 				continue;
402 		}
403 
404 		if (prand & 1) {
405 			prand >>= 1;
406 			continue;
407 		}
408 
409 		err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
410 		if (err == 0) {
411 			if (WARN(test_and_set_bit(i, obj_in_table), "succeeded to insert same object %d", i))
412 				continue;
413 		} else {
414 			if (WARN(!test_bit(i, obj_in_table), "failed to insert object %d", i))
415 				continue;
416 		}
417 
418 		if (prand & 1) {
419 			prand >>= 1;
420 			continue;
421 		}
422 
423 		i = prandom_u32_max(entries);
424 		if (test_bit(i, obj_in_table)) {
425 			err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
426 			WARN(err, "cannot remove element at slot %d", i);
427 			if (err == 0)
428 				clear_bit(i, obj_in_table);
429 		} else {
430 			err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
431 			WARN(err, "failed to insert object %d", i);
432 			if (err == 0)
433 				set_bit(i, obj_in_table);
434 		}
435 	}
436 
437 	for (i = 0; i < entries; i++) {
438 		cond_resched();
439 		err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
440 		if (test_bit(i, obj_in_table)) {
441 			if (WARN(err, "cannot remove element at slot %d", i))
442 				continue;
443 		} else {
444 			if (WARN(err != -ENOENT, "removed non-existant element, error %d not %d",
445 				 err, -ENOENT))
446 			continue;
447 		}
448 	}
449 
450 	rhltable_destroy(&rhlt);
451 out_free:
452 	vfree(rhl_test_objects);
453 	vfree(obj_in_table);
454 	return ret;
455 }
456 
457 static int __init test_rhashtable_max(struct test_obj *array,
458 				      unsigned int entries)
459 {
460 	unsigned int i, insert_retries = 0;
461 	int err;
462 
463 	test_rht_params.max_size = roundup_pow_of_two(entries / 8);
464 	err = rhashtable_init(&ht, &test_rht_params);
465 	if (err)
466 		return err;
467 
468 	for (i = 0; i < ht.max_elems; i++) {
469 		struct test_obj *obj = &array[i];
470 
471 		obj->value.id = i * 2;
472 		err = insert_retry(&ht, obj, test_rht_params);
473 		if (err > 0)
474 			insert_retries += err;
475 		else if (err)
476 			return err;
477 	}
478 
479 	err = insert_retry(&ht, &array[ht.max_elems], test_rht_params);
480 	if (err == -E2BIG) {
481 		err = 0;
482 	} else {
483 		pr_info("insert element %u should have failed with %d, got %d\n",
484 				ht.max_elems, -E2BIG, err);
485 		if (err == 0)
486 			err = -1;
487 	}
488 
489 	rhashtable_destroy(&ht);
490 
491 	return err;
492 }
493 
494 static unsigned int __init print_ht(struct rhltable *rhlt)
495 {
496 	struct rhashtable *ht;
497 	const struct bucket_table *tbl;
498 	char buff[512] = "";
499 	unsigned int i, cnt = 0;
500 
501 	ht = &rhlt->ht;
502 	tbl = rht_dereference(ht->tbl, ht);
503 	for (i = 0; i < tbl->size; i++) {
504 		struct rhash_head *pos, *next;
505 		struct test_obj_rhl *p;
506 
507 		pos = rht_dereference(tbl->buckets[i], ht);
508 		next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;
509 
510 		if (!rht_is_a_nulls(pos)) {
511 			sprintf(buff, "%s\nbucket[%d] -> ", buff, i);
512 		}
513 
514 		while (!rht_is_a_nulls(pos)) {
515 			struct rhlist_head *list = container_of(pos, struct rhlist_head, rhead);
516 			sprintf(buff, "%s[[", buff);
517 			do {
518 				pos = &list->rhead;
519 				list = rht_dereference(list->next, ht);
520 				p = rht_obj(ht, pos);
521 
522 				sprintf(buff, "%s val %d (tid=%d)%s", buff, p->value.id, p->value.tid,
523 					list? ", " : " ");
524 				cnt++;
525 			} while (list);
526 
527 			pos = next,
528 			next = !rht_is_a_nulls(pos) ?
529 				rht_dereference(pos->next, ht) : NULL;
530 
531 			sprintf(buff, "%s]]%s", buff, !rht_is_a_nulls(pos) ? " -> " : "");
532 		}
533 	}
534 	printk(KERN_ERR "\n---- ht: ----%s\n-------------\n", buff);
535 
536 	return cnt;
537 }
538 
539 static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
540 				  int cnt, bool slow)
541 {
542 	struct rhltable rhlt;
543 	unsigned int i, ret;
544 	const char *key;
545 	int err = 0;
546 
547 	err = rhltable_init(&rhlt, &test_rht_params_dup);
548 	if (WARN_ON(err))
549 		return err;
550 
551 	for (i = 0; i < cnt; i++) {
552 		rhl_test_objects[i].value.tid = i;
553 		key = rht_obj(&rhlt.ht, &rhl_test_objects[i].list_node.rhead);
554 		key += test_rht_params_dup.key_offset;
555 
556 		if (slow) {
557 			err = PTR_ERR(rhashtable_insert_slow(&rhlt.ht, key,
558 							     &rhl_test_objects[i].list_node.rhead));
559 			if (err == -EAGAIN)
560 				err = 0;
561 		} else
562 			err = rhltable_insert(&rhlt,
563 					      &rhl_test_objects[i].list_node,
564 					      test_rht_params_dup);
565 		if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
566 			goto skip_print;
567 	}
568 
569 	ret = print_ht(&rhlt);
570 	WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");
571 
572 skip_print:
573 	rhltable_destroy(&rhlt);
574 
575 	return 0;
576 }
577 
578 static int __init test_insert_duplicates_run(void)
579 {
580 	struct test_obj_rhl rhl_test_objects[3] = {};
581 
582 	pr_info("test inserting duplicates\n");
583 
584 	/* two different values that map to same bucket */
585 	rhl_test_objects[0].value.id = 1;
586 	rhl_test_objects[1].value.id = 21;
587 
588 	/* and another duplicate with same as [0] value
589 	 * which will be second on the bucket list */
590 	rhl_test_objects[2].value.id = rhl_test_objects[0].value.id;
591 
592 	test_insert_dup(rhl_test_objects, 2, false);
593 	test_insert_dup(rhl_test_objects, 3, false);
594 	test_insert_dup(rhl_test_objects, 2, true);
595 	test_insert_dup(rhl_test_objects, 3, true);
596 
597 	return 0;
598 }
599 
600 static int thread_lookup_test(struct thread_data *tdata)
601 {
602 	unsigned int entries = tdata->entries;
603 	int i, err = 0;
604 
605 	for (i = 0; i < entries; i++) {
606 		struct test_obj *obj;
607 		struct test_obj_val key = {
608 			.id = i,
609 			.tid = tdata->id,
610 		};
611 
612 		obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
613 		if (obj && (tdata->objs[i].value.id == TEST_INSERT_FAIL)) {
614 			pr_err("  found unexpected object %d-%d\n", key.tid, key.id);
615 			err++;
616 		} else if (!obj && (tdata->objs[i].value.id != TEST_INSERT_FAIL)) {
617 			pr_err("  object %d-%d not found!\n", key.tid, key.id);
618 			err++;
619 		} else if (obj && memcmp(&obj->value, &key, sizeof(key))) {
620 			pr_err("  wrong object returned (got %d-%d, expected %d-%d)\n",
621 			       obj->value.tid, obj->value.id, key.tid, key.id);
622 			err++;
623 		}
624 
625 		cond_resched();
626 	}
627 	return err;
628 }
629 
630 static int threadfunc(void *data)
631 {
632 	int i, step, err = 0, insert_retries = 0;
633 	struct thread_data *tdata = data;
634 
635 	up(&prestart_sem);
636 	if (down_interruptible(&startup_sem))
637 		pr_err("  thread[%d]: down_interruptible failed\n", tdata->id);
638 
639 	for (i = 0; i < tdata->entries; i++) {
640 		tdata->objs[i].value.id = i;
641 		tdata->objs[i].value.tid = tdata->id;
642 		err = insert_retry(&ht, &tdata->objs[i], test_rht_params);
643 		if (err > 0) {
644 			insert_retries += err;
645 		} else if (err) {
646 			pr_err("  thread[%d]: rhashtable_insert_fast failed\n",
647 			       tdata->id);
648 			goto out;
649 		}
650 	}
651 	if (insert_retries)
652 		pr_info("  thread[%d]: %u insertions retried due to memory pressure\n",
653 			tdata->id, insert_retries);
654 
655 	err = thread_lookup_test(tdata);
656 	if (err) {
657 		pr_err("  thread[%d]: rhashtable_lookup_test failed\n",
658 		       tdata->id);
659 		goto out;
660 	}
661 
662 	for (step = 10; step > 0; step--) {
663 		for (i = 0; i < tdata->entries; i += step) {
664 			if (tdata->objs[i].value.id == TEST_INSERT_FAIL)
665 				continue;
666 			err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
667 			                             test_rht_params);
668 			if (err) {
669 				pr_err("  thread[%d]: rhashtable_remove_fast failed\n",
670 				       tdata->id);
671 				goto out;
672 			}
673 			tdata->objs[i].value.id = TEST_INSERT_FAIL;
674 
675 			cond_resched();
676 		}
677 		err = thread_lookup_test(tdata);
678 		if (err) {
679 			pr_err("  thread[%d]: rhashtable_lookup_test (2) failed\n",
680 			       tdata->id);
681 			goto out;
682 		}
683 	}
684 out:
685 	while (!kthread_should_stop()) {
686 		set_current_state(TASK_INTERRUPTIBLE);
687 		schedule();
688 	}
689 	return err;
690 }
691 
692 static int __init test_rht_init(void)
693 {
694 	unsigned int entries;
695 	int i, err, started_threads = 0, failed_threads = 0;
696 	u64 total_time = 0;
697 	struct thread_data *tdata;
698 	struct test_obj *objs;
699 
700 	if (parm_entries < 0)
701 		parm_entries = 1;
702 
703 	entries = min(parm_entries, MAX_ENTRIES);
704 
705 	test_rht_params.automatic_shrinking = shrinking;
706 	test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
707 	test_rht_params.nelem_hint = size;
708 
709 	objs = vzalloc((test_rht_params.max_size + 1) * sizeof(struct test_obj));
710 	if (!objs)
711 		return -ENOMEM;
712 
713 	pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
714 		size, max_size, shrinking);
715 
716 	for (i = 0; i < runs; i++) {
717 		s64 time;
718 
719 		pr_info("Test %02d:\n", i);
720 		memset(objs, 0, test_rht_params.max_size * sizeof(struct test_obj));
721 
722 		err = rhashtable_init(&ht, &test_rht_params);
723 		if (err < 0) {
724 			pr_warn("Test failed: Unable to initialize hashtable: %d\n",
725 				err);
726 			continue;
727 		}
728 
729 		time = test_rhashtable(&ht, objs, entries);
730 		rhashtable_destroy(&ht);
731 		if (time < 0) {
732 			vfree(objs);
733 			pr_warn("Test failed: return code %lld\n", time);
734 			return -EINVAL;
735 		}
736 
737 		total_time += time;
738 	}
739 
740 	pr_info("test if its possible to exceed max_size %d: %s\n",
741 			test_rht_params.max_size, test_rhashtable_max(objs, entries) == 0 ?
742 			"no, ok" : "YES, failed");
743 	vfree(objs);
744 
745 	do_div(total_time, runs);
746 	pr_info("Average test time: %llu\n", total_time);
747 
748 	test_insert_duplicates_run();
749 
750 	if (!tcount)
751 		return 0;
752 
753 	pr_info("Testing concurrent rhashtable access from %d threads\n",
754 	        tcount);
755 	sema_init(&prestart_sem, 1 - tcount);
756 	tdata = vzalloc(tcount * sizeof(struct thread_data));
757 	if (!tdata)
758 		return -ENOMEM;
759 	objs  = vzalloc(tcount * entries * sizeof(struct test_obj));
760 	if (!objs) {
761 		vfree(tdata);
762 		return -ENOMEM;
763 	}
764 
765 	test_rht_params.max_size = max_size ? :
766 	                           roundup_pow_of_two(tcount * entries);
767 	err = rhashtable_init(&ht, &test_rht_params);
768 	if (err < 0) {
769 		pr_warn("Test failed: Unable to initialize hashtable: %d\n",
770 			err);
771 		vfree(tdata);
772 		vfree(objs);
773 		return -EINVAL;
774 	}
775 	for (i = 0; i < tcount; i++) {
776 		tdata[i].id = i;
777 		tdata[i].entries = entries;
778 		tdata[i].objs = objs + i * entries;
779 		tdata[i].task = kthread_run(threadfunc, &tdata[i],
780 		                            "rhashtable_thrad[%d]", i);
781 		if (IS_ERR(tdata[i].task))
782 			pr_err(" kthread_run failed for thread %d\n", i);
783 		else
784 			started_threads++;
785 	}
786 	if (down_interruptible(&prestart_sem))
787 		pr_err("  down interruptible failed\n");
788 	for (i = 0; i < tcount; i++)
789 		up(&startup_sem);
790 	for (i = 0; i < tcount; i++) {
791 		if (IS_ERR(tdata[i].task))
792 			continue;
793 		if ((err = kthread_stop(tdata[i].task))) {
794 			pr_warn("Test failed: thread %d returned: %d\n",
795 			        i, err);
796 			failed_threads++;
797 		}
798 	}
799 	rhashtable_destroy(&ht);
800 	vfree(tdata);
801 	vfree(objs);
802 
803 	/*
804 	 * rhltable_remove is very expensive, default values can cause test
805 	 * to run for 2 minutes or more,  use a smaller number instead.
806 	 */
807 	err = test_rhltable(entries / 16);
808 	pr_info("Started %d threads, %d failed, rhltable test returns %d\n",
809 	        started_threads, failed_threads, err);
810 	return 0;
811 }
812 
813 static void __exit test_rht_exit(void)
814 {
815 }
816 
817 module_init(test_rht_init);
818 module_exit(test_rht_exit);
819 
820 MODULE_LICENSE("GPL v2");
821