lib/test_rhashtable.c

   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");