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