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