~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/test_rhashtable.c

Version: ~ [ linux-5.8-rc4 ] ~ [ linux-5.7.7 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.50 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.131 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.187 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.229 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.229 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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(array_size(entries,
289                                               sizeof(*rhl_test_objects)));
290         if (!rhl_test_objects)
291                 return -ENOMEM;
292 
293         ret = -ENOMEM;
294         obj_in_table = vzalloc(array_size(sizeof(unsigned long),
295                                           BITS_TO_LONGS(entries)));
296         if (!obj_in_table)
297                 goto out_free;
298 
299         /* nulls_base not supported in rhlist interface */
300         test_rht_params.nulls_base = 0;
301         err = rhltable_init(&rhlt, &test_rht_params);
302         if (WARN_ON(err))
303                 goto out_free;
304 
305         k = prandom_u32();
306         ret = 0;
307         for (i = 0; i < entries; i++) {
308                 rhl_test_objects[i].value.id = k;
309                 err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
310                                       test_rht_params);
311                 if (WARN(err, "error %d on element %d\n", err, i))
312                         break;
313                 if (err == 0)
314                         set_bit(i, obj_in_table);
315         }
316 
317         if (err)
318                 ret = err;
319 
320         pr_info("test %d add/delete pairs into rhlist\n", entries);
321         for (i = 0; i < entries; i++) {
322                 struct rhlist_head *h, *pos;
323                 struct test_obj_rhl *obj;
324                 struct test_obj_val key = {
325                         .id = k,
326                 };
327                 bool found;
328 
329                 rcu_read_lock();
330                 h = rhltable_lookup(&rhlt, &key, test_rht_params);
331                 if (WARN(!h, "key not found during iteration %d of %d", i, entries)) {
332                         rcu_read_unlock();
333                         break;
334                 }
335 
336                 if (i) {
337                         j = i - 1;
338                         rhl_for_each_entry_rcu(obj, pos, h, list_node) {
339                                 if (WARN(pos == &rhl_test_objects[j].list_node, "old element found, should be gone"))
340                                         break;
341                         }
342                 }
343 
344                 cond_resched_rcu();
345 
346                 found = false;
347 
348                 rhl_for_each_entry_rcu(obj, pos, h, list_node) {
349                         if (pos == &rhl_test_objects[i].list_node) {
350                                 found = true;
351                                 break;
352                         }
353                 }
354 
355                 rcu_read_unlock();
356 
357                 if (WARN(!found, "element %d not found", i))
358                         break;
359 
360                 err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
361                 WARN(err, "rhltable_remove: err %d for iteration %d\n", err, i);
362                 if (err == 0)
363                         clear_bit(i, obj_in_table);
364         }
365 
366         if (ret == 0 && err)
367                 ret = err;
368 
369         for (i = 0; i < entries; i++) {
370                 WARN(test_bit(i, obj_in_table), "elem %d allegedly still present", i);
371 
372                 err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
373                                       test_rht_params);
374                 if (WARN(err, "error %d on element %d\n", err, i))
375                         break;
376                 if (err == 0)
377                         set_bit(i, obj_in_table);
378         }
379 
380         pr_info("test %d random rhlist add/delete operations\n", entries);
381         for (j = 0; j < entries; j++) {
382                 u32 i = prandom_u32_max(entries);
383                 u32 prand = prandom_u32();
384 
385                 cond_resched();
386 
387                 if (prand == 0)
388                         prand = prandom_u32();
389 
390                 if (prand & 1) {
391                         prand >>= 1;
392                         continue;
393                 }
394 
395                 err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
396                 if (test_bit(i, obj_in_table)) {
397                         clear_bit(i, obj_in_table);
398                         if (WARN(err, "cannot remove element at slot %d", i))
399                                 continue;
400                 } else {
401                         if (WARN(err != -ENOENT, "removed non-existant element %d, error %d not %d",
402                              i, err, -ENOENT))
403                                 continue;
404                 }
405 
406                 if (prand & 1) {
407                         prand >>= 1;
408                         continue;
409                 }
410 
411                 err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
412                 if (err == 0) {
413                         if (WARN(test_and_set_bit(i, obj_in_table), "succeeded to insert same object %d", i))
414                                 continue;
415                 } else {
416                         if (WARN(!test_bit(i, obj_in_table), "failed to insert object %d", i))
417                                 continue;
418                 }
419 
420                 if (prand & 1) {
421                         prand >>= 1;
422                         continue;
423                 }
424 
425                 i = prandom_u32_max(entries);
426                 if (test_bit(i, obj_in_table)) {
427                         err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
428                         WARN(err, "cannot remove element at slot %d", i);
429                         if (err == 0)
430                                 clear_bit(i, obj_in_table);
431                 } else {
432                         err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
433                         WARN(err, "failed to insert object %d", i);
434                         if (err == 0)
435                                 set_bit(i, obj_in_table);
436                 }
437         }
438 
439         for (i = 0; i < entries; i++) {
440                 cond_resched();
441                 err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
442                 if (test_bit(i, obj_in_table)) {
443                         if (WARN(err, "cannot remove element at slot %d", i))
444                                 continue;
445                 } else {
446                         if (WARN(err != -ENOENT, "removed non-existant element, error %d not %d",
447                                  err, -ENOENT))
448                         continue;
449                 }
450         }
451 
452         rhltable_destroy(&rhlt);
453 out_free:
454         vfree(rhl_test_objects);
455         vfree(obj_in_table);
456         return ret;
457 }
458 
459 static int __init test_rhashtable_max(struct test_obj *array,
460                                       unsigned int entries)
461 {
462         unsigned int i, insert_retries = 0;
463         int err;
464 
465         test_rht_params.max_size = roundup_pow_of_two(entries / 8);
466         err = rhashtable_init(&ht, &test_rht_params);
467         if (err)
468                 return err;
469 
470         for (i = 0; i < ht.max_elems; i++) {
471                 struct test_obj *obj = &array[i];
472 
473                 obj->value.id = i * 2;
474                 err = insert_retry(&ht, obj, test_rht_params);
475                 if (err > 0)
476                         insert_retries += err;
477                 else if (err)
478                         return err;
479         }
480 
481         err = insert_retry(&ht, &array[ht.max_elems], test_rht_params);
482         if (err == -E2BIG) {
483                 err = 0;
484         } else {
485                 pr_info("insert element %u should have failed with %d, got %d\n",
486                                 ht.max_elems, -E2BIG, err);
487                 if (err == 0)
488                         err = -1;
489         }
490 
491         rhashtable_destroy(&ht);
492 
493         return err;
494 }
495 
496 static unsigned int __init print_ht(struct rhltable *rhlt)
497 {
498         struct rhashtable *ht;
499         const struct bucket_table *tbl;
500         char buff[512] = "";
501         unsigned int i, cnt = 0;
502 
503         ht = &rhlt->ht;
504         tbl = rht_dereference(ht->tbl, ht);
505         for (i = 0; i < tbl->size; i++) {
506                 struct rhash_head *pos, *next;
507                 struct test_obj_rhl *p;
508 
509                 pos = rht_dereference(tbl->buckets[i], ht);
510                 next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;
511 
512                 if (!rht_is_a_nulls(pos)) {
513                         sprintf(buff, "%s\nbucket[%d] -> ", buff, i);
514                 }
515 
516                 while (!rht_is_a_nulls(pos)) {
517                         struct rhlist_head *list = container_of(pos, struct rhlist_head, rhead);
518                         sprintf(buff, "%s[[", buff);
519                         do {
520                                 pos = &list->rhead;
521                                 list = rht_dereference(list->next, ht);
522                                 p = rht_obj(ht, pos);
523 
524                                 sprintf(buff, "%s val %d (tid=%d)%s", buff, p->value.id, p->value.tid,
525                                         list? ", " : " ");
526                                 cnt++;
527                         } while (list);
528 
529                         pos = next,
530                         next = !rht_is_a_nulls(pos) ?
531                                 rht_dereference(pos->next, ht) : NULL;
532 
533                         sprintf(buff, "%s]]%s", buff, !rht_is_a_nulls(pos) ? " -> " : "");
534                 }
535         }
536         printk(KERN_ERR "\n---- ht: ----%s\n-------------\n", buff);
537 
538         return cnt;
539 }
540 
541 static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
542                                   int cnt, bool slow)
543 {
544         struct rhltable rhlt;
545         unsigned int i, ret;
546         const char *key;
547         int err = 0;
548 
549         err = rhltable_init(&rhlt, &test_rht_params_dup);
550         if (WARN_ON(err))
551                 return err;
552 
553         for (i = 0; i < cnt; i++) {
554                 rhl_test_objects[i].value.tid = i;
555                 key = rht_obj(&rhlt.ht, &rhl_test_objects[i].list_node.rhead);
556                 key += test_rht_params_dup.key_offset;
557 
558                 if (slow) {
559                         err = PTR_ERR(rhashtable_insert_slow(&rhlt.ht, key,
560                                                              &rhl_test_objects[i].list_node.rhead));
561                         if (err == -EAGAIN)
562                                 err = 0;
563                 } else
564                         err = rhltable_insert(&rhlt,
565                                               &rhl_test_objects[i].list_node,
566                                               test_rht_params_dup);
567                 if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
568                         goto skip_print;
569         }
570 
571         ret = print_ht(&rhlt);
572         WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");
573 
574 skip_print:
575         rhltable_destroy(&rhlt);
576 
577         return 0;
578 }
579 
580 static int __init test_insert_duplicates_run(void)
581 {
582         struct test_obj_rhl rhl_test_objects[3] = {};
583 
584         pr_info("test inserting duplicates\n");
585 
586         /* two different values that map to same bucket */
587         rhl_test_objects[0].value.id = 1;
588         rhl_test_objects[1].value.id = 21;
589 
590         /* and another duplicate with same as [0] value
591          * which will be second on the bucket list */
592         rhl_test_objects[2].value.id = rhl_test_objects[0].value.id;
593 
594         test_insert_dup(rhl_test_objects, 2, false);
595         test_insert_dup(rhl_test_objects, 3, false);
596         test_insert_dup(rhl_test_objects, 2, true);
597         test_insert_dup(rhl_test_objects, 3, true);
598 
599         return 0;
600 }
601 
602 static int thread_lookup_test(struct thread_data *tdata)
603 {
604         unsigned int entries = tdata->entries;
605         int i, err = 0;
606 
607         for (i = 0; i < entries; i++) {
608                 struct test_obj *obj;
609                 struct test_obj_val key = {
610                         .id = i,
611                         .tid = tdata->id,
612                 };
613 
614                 obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
615                 if (obj && (tdata->objs[i].value.id == TEST_INSERT_FAIL)) {
616                         pr_err("  found unexpected object %d-%d\n", key.tid, key.id);
617                         err++;
618                 } else if (!obj && (tdata->objs[i].value.id != TEST_INSERT_FAIL)) {
619                         pr_err("  object %d-%d not found!\n", key.tid, key.id);
620                         err++;
621                 } else if (obj && memcmp(&obj->value, &key, sizeof(key))) {
622                         pr_err("  wrong object returned (got %d-%d, expected %d-%d)\n",
623                                obj->value.tid, obj->value.id, key.tid, key.id);
624                         err++;
625                 }
626 
627                 cond_resched();
628         }
629         return err;
630 }
631 
632 static int threadfunc(void *data)
633 {
634         int i, step, err = 0, insert_retries = 0;
635         struct thread_data *tdata = data;
636 
637         up(&prestart_sem);
638         if (down_interruptible(&startup_sem))
639                 pr_err("  thread[%d]: down_interruptible failed\n", tdata->id);
640 
641         for (i = 0; i < tdata->entries; i++) {
642                 tdata->objs[i].value.id = i;
643                 tdata->objs[i].value.tid = tdata->id;
644                 err = insert_retry(&ht, &tdata->objs[i], test_rht_params);
645                 if (err > 0) {
646                         insert_retries += err;
647                 } else if (err) {
648                         pr_err("  thread[%d]: rhashtable_insert_fast failed\n",
649                                tdata->id);
650                         goto out;
651                 }
652         }
653         if (insert_retries)
654                 pr_info("  thread[%d]: %u insertions retried due to memory pressure\n",
655                         tdata->id, insert_retries);
656 
657         err = thread_lookup_test(tdata);
658         if (err) {
659                 pr_err("  thread[%d]: rhashtable_lookup_test failed\n",
660                        tdata->id);
661                 goto out;
662         }
663 
664         for (step = 10; step > 0; step--) {
665                 for (i = 0; i < tdata->entries; i += step) {
666                         if (tdata->objs[i].value.id == TEST_INSERT_FAIL)
667                                 continue;
668                         err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
669                                                      test_rht_params);
670                         if (err) {
671                                 pr_err("  thread[%d]: rhashtable_remove_fast failed\n",
672                                        tdata->id);
673                                 goto out;
674                         }
675                         tdata->objs[i].value.id = TEST_INSERT_FAIL;
676 
677                         cond_resched();
678                 }
679                 err = thread_lookup_test(tdata);
680                 if (err) {
681                         pr_err("  thread[%d]: rhashtable_lookup_test (2) failed\n",
682                                tdata->id);
683                         goto out;
684                 }
685         }
686 out:
687         while (!kthread_should_stop()) {
688                 set_current_state(TASK_INTERRUPTIBLE);
689                 schedule();
690         }
691         return err;
692 }
693 
694 static int __init test_rht_init(void)
695 {
696         unsigned int entries;
697         int i, err, started_threads = 0, failed_threads = 0;
698         u64 total_time = 0;
699         struct thread_data *tdata;
700         struct test_obj *objs;
701 
702         if (parm_entries < 0)
703                 parm_entries = 1;
704 
705         entries = min(parm_entries, MAX_ENTRIES);
706 
707         test_rht_params.automatic_shrinking = shrinking;
708         test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
709         test_rht_params.nelem_hint = size;
710 
711         objs = vzalloc(array_size(sizeof(struct test_obj),
712                                   test_rht_params.max_size + 1));
713         if (!objs)
714                 return -ENOMEM;
715 
716         pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
717                 size, max_size, shrinking);
718 
719         for (i = 0; i < runs; i++) {
720                 s64 time;
721 
722                 pr_info("Test %02d:\n", i);
723                 memset(objs, 0, test_rht_params.max_size * sizeof(struct test_obj));
724 
725                 err = rhashtable_init(&ht, &test_rht_params);
726                 if (err < 0) {
727                         pr_warn("Test failed: Unable to initialize hashtable: %d\n",
728                                 err);
729                         continue;
730                 }
731 
732                 time = test_rhashtable(&ht, objs, entries);
733                 rhashtable_destroy(&ht);
734                 if (time < 0) {
735                         vfree(objs);
736                         pr_warn("Test failed: return code %lld\n", time);
737                         return -EINVAL;
738                 }
739 
740                 total_time += time;
741         }
742 
743         pr_info("test if its possible to exceed max_size %d: %s\n",
744                         test_rht_params.max_size, test_rhashtable_max(objs, entries) == 0 ?
745                         "no, ok" : "YES, failed");
746         vfree(objs);
747 
748         do_div(total_time, runs);
749         pr_info("Average test time: %llu\n", total_time);
750 
751         test_insert_duplicates_run();
752 
753         if (!tcount)
754                 return 0;
755 
756         pr_info("Testing concurrent rhashtable access from %d threads\n",
757                 tcount);
758         sema_init(&prestart_sem, 1 - tcount);
759         tdata = vzalloc(array_size(tcount, sizeof(struct thread_data)));
760         if (!tdata)
761                 return -ENOMEM;
762         objs  = vzalloc(array3_size(sizeof(struct test_obj), tcount, entries));
763         if (!objs) {
764                 vfree(tdata);
765                 return -ENOMEM;
766         }
767 
768         test_rht_params.max_size = max_size ? :
769                                    roundup_pow_of_two(tcount * entries);
770         err = rhashtable_init(&ht, &test_rht_params);
771         if (err < 0) {
772                 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
773                         err);
774                 vfree(tdata);
775                 vfree(objs);
776                 return -EINVAL;
777         }
778         for (i = 0; i < tcount; i++) {
779                 tdata[i].id = i;
780                 tdata[i].entries = entries;
781                 tdata[i].objs = objs + i * entries;
782                 tdata[i].task = kthread_run(threadfunc, &tdata[i],
783                                             "rhashtable_thrad[%d]", i);
784                 if (IS_ERR(tdata[i].task))
785                         pr_err(" kthread_run failed for thread %d\n", i);
786                 else
787                         started_threads++;
788         }
789         if (down_interruptible(&prestart_sem))
790                 pr_err("  down interruptible failed\n");
791         for (i = 0; i < tcount; i++)
792                 up(&startup_sem);
793         for (i = 0; i < tcount; i++) {
794                 if (IS_ERR(tdata[i].task))
795                         continue;
796                 if ((err = kthread_stop(tdata[i].task))) {
797                         pr_warn("Test failed: thread %d returned: %d\n",
798                                 i, err);
799                         failed_threads++;
800                 }
801         }
802         rhashtable_destroy(&ht);
803         vfree(tdata);
804         vfree(objs);
805 
806         /*
807          * rhltable_remove is very expensive, default values can cause test
808          * to run for 2 minutes or more,  use a smaller number instead.
809          */
810         err = test_rhltable(entries / 16);
811         pr_info("Started %d threads, %d failed, rhltable test returns %d\n",
812                 started_threads, failed_threads, err);
813         return 0;
814 }
815 
816 static void __exit test_rht_exit(void)
817 {
818 }
819 
820 module_init(test_rht_init);
821 module_exit(test_rht_exit);
822 
823 MODULE_LICENSE("GPL v2");
824 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp