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 struct rhashtable_params test_rht_params = {
  83         .head_offset = offsetof(struct test_obj, node),
  84         .key_offset = offsetof(struct test_obj, value),
  85         .key_len = sizeof(struct test_obj_val),
  86         .hashfn = jhash,
  87         .nulls_base = (3U << RHT_BASE_SHIFT),
  88 };
  89
  90 static struct semaphore prestart_sem;
  91 static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0);
  92
  93 static int insert_retry(struct rhashtable *ht, struct test_obj *obj,
  94                         const struct rhashtable_params params)
  95 {
  96         int err, retries = -1, enomem_retries = 0;
  97
  98         do {
  99                 retries++;
 100                 cond_resched();
 101                 err = rhashtable_insert_fast(ht, &obj->node, params);
 102                 if (err == -ENOMEM && enomem_retry) {
 103                         enomem_retries++;
 104                         err = -EBUSY;
 105                 }
 106         } while (err == -EBUSY);
 107
 108         if (enomem_retries)
 109                 pr_info(" %u insertions retried after -ENOMEM\n",
 110                         enomem_retries);
 111
 112         return err ? : retries;
 113 }
 114
 115 static int __init test_rht_lookup(struct rhashtable *ht, struct test_obj *array,
 116                                   unsigned int entries)
 117 {
 118         unsigned int i;
 119
 120         for (i = 0; i < entries; i++) {
 121                 struct test_obj *obj;
 122                 bool expected = !(i % 2);
 123                 struct test_obj_val key = {
 124                         .id = i,
 125                 };
 126
 127                 if (array[i / 2].value.id == TEST_INSERT_FAIL)
 128                         expected = false;
 129
 130                 obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
 131
 132                 if (expected && !obj) {
 133                         pr_warn("Test failed: Could not find key %u\n", key.id);
 134                         return -ENOENT;
 135                 } else if (!expected && obj) {
 136                         pr_warn("Test failed: Unexpected entry found for key %u\n",
 137                                 key.id);
 138                         return -EEXIST;
 139                 } else if (expected && obj) {
 140                         if (obj->value.id != i) {
 141                                 pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
 142                                         obj->value.id, i);
 143                                 return -EINVAL;
 144                         }
 145                 }
 146
 147                 cond_resched_rcu();
 148         }
 149
 150         return 0;
 151 }
 152
 153 static void test_bucket_stats(struct rhashtable *ht, unsigned int entries)
 154 {
 155         unsigned int err, total = 0, chain_len = 0;
 156         struct rhashtable_iter hti;
 157         struct rhash_head *pos;
 158
 159         err = rhashtable_walk_init(ht, &hti, GFP_KERNEL);
 160         if (err) {
 161                 pr_warn("Test failed: allocation error");
 162                 return;
 163         }
 164
 165         rhashtable_walk_start(&hti);
 166
 167         while ((pos = rhashtable_walk_next(&hti))) {
 168                 if (PTR_ERR(pos) == -EAGAIN) {
 169                         pr_info("Info: encountered resize\n");
 170                         chain_len++;
 171                         continue;
 172                 } else if (IS_ERR(pos)) {
 173                         pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
 174                                 PTR_ERR(pos));
 175                         break;
 176                 }
 177
 178                 total++;
 179         }
 180
 181         rhashtable_walk_stop(&hti);
 182         rhashtable_walk_exit(&hti);
 183
 184         pr_info("  Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n",
 185                 total, atomic_read(&ht->nelems), entries, chain_len);
 186
 187         if (total != atomic_read(&ht->nelems) || total != entries)
 188                 pr_warn("Test failed: Total count mismatch ^^^");
 189 }
 190
 191 static s64 __init test_rhashtable(struct rhashtable *ht, struct test_obj *array,
 192                                   unsigned int entries)
 193 {
 194         struct test_obj *obj;
 195         int err;
 196         unsigned int i, insert_retries = 0;
 197         s64 start, end;
 198
 199         /*
 200          * Insertion Test:
 201          * Insert entries into table with all keys even numbers
 202          */
 203         pr_info("  Adding %d keys\n", entries);
 204         start = ktime_get_ns();
 205         for (i = 0; i < entries; i++) {
 206                 struct test_obj *obj = &array[i];
 207
 208                 obj->value.id = i * 2;
 209                 err = insert_retry(ht, obj, test_rht_params);
 210                 if (err > 0)
 211                         insert_retries += err;
 212                 else if (err)
 213                         return err;
 214         }
 215
 216         if (insert_retries)
 217                 pr_info("  %u insertions retried due to memory pressure\n",
 218                         insert_retries);
 219
 220         test_bucket_stats(ht, entries);
 221         rcu_read_lock();
 222         test_rht_lookup(ht, array, entries);
 223         rcu_read_unlock();
 224
 225         test_bucket_stats(ht, entries);
 226
 227         pr_info("  Deleting %d keys\n", entries);
 228         for (i = 0; i < entries; i++) {
 229                 struct test_obj_val key = {
 230                         .id = i * 2,
 231                 };
 232
 233                 if (array[i].value.id != TEST_INSERT_FAIL) {
 234                         obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
 235                         BUG_ON(!obj);
 236
 237                         rhashtable_remove_fast(ht, &obj->node, test_rht_params);
 238                 }
 239
 240                 cond_resched();
 241         }
 242
 243         end = ktime_get_ns();
 244         pr_info("  Duration of test: %lld ns\n", end - start);
 245
 246         return end - start;
 247 }
 248
 249 static struct rhashtable ht;
 250 static struct rhltable rhlt;
 251
 252 static int __init test_rhltable(unsigned int entries)
 253 {
 254         struct test_obj_rhl *rhl_test_objects;
 255         unsigned long *obj_in_table;
 256         unsigned int i, j, k;
 257         int ret, err;
 258
 259         if (entries == 0)
 260                 entries = 1;
 261
 262         rhl_test_objects = vzalloc(sizeof(*rhl_test_objects) * entries);
 263         if (!rhl_test_objects)
 264                 return -ENOMEM;
 265
 266         ret = -ENOMEM;
 267         obj_in_table = vzalloc(BITS_TO_LONGS(entries) * sizeof(unsigned long));
 268         if (!obj_in_table)
 269                 goto out_free;
 270
 271         /* nulls_base not supported in rhlist interface */
 272         test_rht_params.nulls_base = 0;
 273         err = rhltable_init(&rhlt, &test_rht_params);
 274         if (WARN_ON(err))
 275                 goto out_free;
 276
 277         k = prandom_u32();
 278         ret = 0;
 279         for (i = 0; i < entries; i++) {
 280                 rhl_test_objects[i].value.id = k;
 281                 err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
 282                                       test_rht_params);
 283                 if (WARN(err, "error %d on element %d\n", err, i))
 284                         break;
 285                 if (err == 0)
 286                         set_bit(i, obj_in_table);
 287         }
 288
 289         if (err)
 290                 ret = err;
 291
 292         pr_info("test %d add/delete pairs into rhlist\n", entries);
 293         for (i = 0; i < entries; i++) {
 294                 struct rhlist_head *h, *pos;
 295                 struct test_obj_rhl *obj;
 296                 struct test_obj_val key = {
 297                         .id = k,
 298                 };
 299                 bool found;
 300
 301                 rcu_read_lock();
 302                 h = rhltable_lookup(&rhlt, &key, test_rht_params);
 303                 if (WARN(!h, "key not found during iteration %d of %d", i, entries)) {
 304                         rcu_read_unlock();
 305                         break;
 306                 }
 307
 308                 if (i) {
 309                         j = i - 1;
 310                         rhl_for_each_entry_rcu(obj, pos, h, list_node) {
 311                                 if (WARN(pos == &rhl_test_objects[j].list_node, "old element found, should be gone"))
 312                                         break;
 313                         }
 314                 }
 315
 316                 cond_resched_rcu();
 317
 318                 found = false;
 319
 320                 rhl_for_each_entry_rcu(obj, pos, h, list_node) {
 321                         if (pos == &rhl_test_objects[i].list_node) {
 322                                 found = true;
 323                                 break;
 324                         }
 325                 }
 326
 327                 rcu_read_unlock();
 328
 329                 if (WARN(!found, "element %d not found", i))
 330                         break;
 331
 332                 err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
 333                 WARN(err, "rhltable_remove: err %d for iteration %d\n", err, i);
 334                 if (err == 0)
 335                         clear_bit(i, obj_in_table);
 336         }
 337
 338         if (ret == 0 && err)
 339                 ret = err;
 340
 341         for (i = 0; i < entries; i++) {
 342                 WARN(test_bit(i, obj_in_table), "elem %d allegedly still present", i);
 343
 344                 err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
 345                                       test_rht_params);
 346                 if (WARN(err, "error %d on element %d\n", err, i))
 347                         break;
 348                 if (err == 0)
 349                         set_bit(i, obj_in_table);
 350         }
 351
 352         pr_info("test %d random rhlist add/delete operations\n", entries);
 353         for (j = 0; j < entries; j++) {
 354                 u32 i = prandom_u32_max(entries);
 355                 u32 prand = prandom_u32();
 356
 357                 cond_resched();
 358
 359                 if (prand == 0)
 360                         prand = prandom_u32();
 361
 362                 if (prand & 1) {
 363                         prand >>= 1;
 364                         continue;
 365                 }
 366
 367                 err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
 368                 if (test_bit(i, obj_in_table)) {
 369                         clear_bit(i, obj_in_table);
 370                         if (WARN(err, "cannot remove element at slot %d", i))
 371                                 continue;
 372                 } else {
 373                         if (WARN(err != -ENOENT, "removed non-existant element %d, error %d not %d",
 374                              i, err, -ENOENT))
 375                                 continue;
 376                 }
 377
 378                 if (prand & 1) {
 379                         prand >>= 1;
 380                         continue;
 381                 }
 382
 383                 err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
 384                 if (err == 0) {
 385                         if (WARN(test_and_set_bit(i, obj_in_table), "succeeded to insert same object %d", i))
 386                                 continue;
 387                 } else {
 388                         if (WARN(!test_bit(i, obj_in_table), "failed to insert object %d", i))
 389                                 continue;
 390                 }
 391
 392                 if (prand & 1) {
 393                         prand >>= 1;
 394                         continue;
 395                 }
 396
 397                 i = prandom_u32_max(entries);
 398                 if (test_bit(i, obj_in_table)) {
 399                         err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
 400                         WARN(err, "cannot remove element at slot %d", i);
 401                         if (err == 0)
 402                                 clear_bit(i, obj_in_table);
 403                 } else {
 404                         err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
 405                         WARN(err, "failed to insert object %d", i);
 406                         if (err == 0)
 407                                 set_bit(i, obj_in_table);
 408                 }
 409         }
 410
 411         for (i = 0; i < entries; i++) {
 412                 cond_resched();
 413                 err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
 414                 if (test_bit(i, obj_in_table)) {
 415                         if (WARN(err, "cannot remove element at slot %d", i))
 416                                 continue;
 417                 } else {
 418                         if (WARN(err != -ENOENT, "removed non-existant element, error %d not %d",
 419                                  err, -ENOENT))
 420                         continue;
 421                 }
 422         }
 423
 424         rhltable_destroy(&rhlt);
 425 out_free:
 426         vfree(rhl_test_objects);
 427         vfree(obj_in_table);
 428         return ret;
 429 }
 430
 431 static int __init test_rhashtable_max(struct test_obj *array,
 432                                       unsigned int entries)
 433 {
 434         unsigned int i, insert_retries = 0;
 435         int err;
 436
 437         test_rht_params.max_size = roundup_pow_of_two(entries / 8);
 438         err = rhashtable_init(&ht, &test_rht_params);
 439         if (err)
 440                 return err;
 441
 442         for (i = 0; i < ht.max_elems; i++) {
 443                 struct test_obj *obj = &array[i];
 444
 445                 obj->value.id = i * 2;
 446                 err = insert_retry(&ht, obj, test_rht_params);
 447                 if (err > 0)
 448                         insert_retries += err;
 449                 else if (err)
 450                         return err;
 451         }
 452
 453         err = insert_retry(&ht, &array[ht.max_elems], test_rht_params);
 454         if (err == -E2BIG) {
 455                 err = 0;
 456         } else {
 457                 pr_info("insert element %u should have failed with %d, got %d\n",
 458                                 ht.max_elems, -E2BIG, err);
 459                 if (err == 0)
 460                         err = -1;
 461         }
 462
 463         rhashtable_destroy(&ht);
 464
 465         return err;
 466 }
 467
 468 static int thread_lookup_test(struct thread_data *tdata)
 469 {
 470         unsigned int entries = tdata->entries;
 471         int i, err = 0;
 472
 473         for (i = 0; i < entries; i++) {
 474                 struct test_obj *obj;
 475                 struct test_obj_val key = {
 476                         .id = i,
 477                         .tid = tdata->id,
 478                 };
 479
 480                 obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
 481                 if (obj && (tdata->objs[i].value.id == TEST_INSERT_FAIL)) {
 482                         pr_err("  found unexpected object %d-%d\n", key.tid, key.id);
 483                         err++;
 484                 } else if (!obj && (tdata->objs[i].value.id != TEST_INSERT_FAIL)) {
 485                         pr_err("  object %d-%d not found!\n", key.tid, key.id);
 486                         err++;
 487                 } else if (obj && memcmp(&obj->value, &key, sizeof(key))) {
 488                         pr_err("  wrong object returned (got %d-%d, expected %d-%d)\n",
 489                                obj->value.tid, obj->value.id, key.tid, key.id);
 490                         err++;
 491                 }
 492
 493                 cond_resched();
 494         }
 495         return err;
 496 }
 497
 498 static int threadfunc(void *data)
 499 {
 500         int i, step, err = 0, insert_retries = 0;
 501         struct thread_data *tdata = data;
 502
 503         up(&prestart_sem);
 504         if (down_interruptible(&startup_sem))
 505                 pr_err("  thread[%d]: down_interruptible failed\n", tdata->id);
 506
 507         for (i = 0; i < tdata->entries; i++) {
 508                 tdata->objs[i].value.id = i;
 509                 tdata->objs[i].value.tid = tdata->id;
 510                 err = insert_retry(&ht, &tdata->objs[i], test_rht_params);
 511                 if (err > 0) {
 512                         insert_retries += err;
 513                 } else if (err) {
 514                         pr_err("  thread[%d]: rhashtable_insert_fast failed\n",
 515                                tdata->id);
 516                         goto out;
 517                 }
 518         }
 519         if (insert_retries)
 520                 pr_info("  thread[%d]: %u insertions retried due to memory pressure\n",
 521                         tdata->id, insert_retries);
 522
 523         err = thread_lookup_test(tdata);
 524         if (err) {
 525                 pr_err("  thread[%d]: rhashtable_lookup_test failed\n",
 526                        tdata->id);
 527                 goto out;
 528         }
 529
 530         for (step = 10; step > 0; step--) {
 531                 for (i = 0; i < tdata->entries; i += step) {
 532                         if (tdata->objs[i].value.id == TEST_INSERT_FAIL)
 533                                 continue;
 534                         err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
 535                                                      test_rht_params);
 536                         if (err) {
 537                                 pr_err("  thread[%d]: rhashtable_remove_fast failed\n",
 538                                        tdata->id);
 539                                 goto out;
 540                         }
 541                         tdata->objs[i].value.id = TEST_INSERT_FAIL;
 542
 543                         cond_resched();
 544                 }
 545                 err = thread_lookup_test(tdata);
 546                 if (err) {
 547                         pr_err("  thread[%d]: rhashtable_lookup_test (2) failed\n",
 548                                tdata->id);
 549                         goto out;
 550                 }
 551         }
 552 out:
 553         while (!kthread_should_stop()) {
 554                 set_current_state(TASK_INTERRUPTIBLE);
 555                 schedule();
 556         }
 557         return err;
 558 }
 559
 560 static int __init test_rht_init(void)
 561 {
 562         unsigned int entries;
 563         int i, err, started_threads = 0, failed_threads = 0;
 564         u64 total_time = 0;
 565         struct thread_data *tdata;
 566         struct test_obj *objs;
 567
 568         if (parm_entries < 0)
 569                 parm_entries = 1;
 570
 571         entries = min(parm_entries, MAX_ENTRIES);
 572
 573         test_rht_params.automatic_shrinking = shrinking;
 574         test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
 575         test_rht_params.nelem_hint = size;
 576
 577         objs = vzalloc((test_rht_params.max_size + 1) * sizeof(struct test_obj));
 578         if (!objs)
 579                 return -ENOMEM;
 580
 581         pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
 582                 size, max_size, shrinking);
 583
 584         for (i = 0; i < runs; i++) {
 585                 s64 time;
 586
 587                 pr_info("Test %02d:\n", i);
 588                 memset(objs, 0, test_rht_params.max_size * sizeof(struct test_obj));
 589
 590                 err = rhashtable_init(&ht, &test_rht_params);
 591                 if (err < 0) {
 592                         pr_warn("Test failed: Unable to initialize hashtable: %d\n",
 593                                 err);
 594                         continue;
 595                 }
 596
 597                 time = test_rhashtable(&ht, objs, entries);
 598                 rhashtable_destroy(&ht);
 599                 if (time < 0) {
 600                         vfree(objs);
 601                         pr_warn("Test failed: return code %lld\n", time);
 602                         return -EINVAL;
 603                 }
 604
 605                 total_time += time;
 606         }
 607
 608         pr_info("test if its possible to exceed max_size %d: %s\n",
 609                         test_rht_params.max_size, test_rhashtable_max(objs, entries) == 0 ?
 610                         "no, ok" : "YES, failed");
 611         vfree(objs);
 612
 613         do_div(total_time, runs);
 614         pr_info("Average test time: %llu\n", total_time);
 615
 616         if (!tcount)
 617                 return 0;
 618
 619         pr_info("Testing concurrent rhashtable access from %d threads\n",
 620                 tcount);
 621         sema_init(&prestart_sem, 1 - tcount);
 622         tdata = vzalloc(tcount * sizeof(struct thread_data));
 623         if (!tdata)
 624                 return -ENOMEM;
 625         objs  = vzalloc(tcount * entries * sizeof(struct test_obj));
 626         if (!objs) {
 627                 vfree(tdata);
 628                 return -ENOMEM;
 629         }
 630
 631         test_rht_params.max_size = max_size ? :
 632                                    roundup_pow_of_two(tcount * entries);
 633         err = rhashtable_init(&ht, &test_rht_params);
 634         if (err < 0) {
 635                 pr_warn("Test failed: Unable to initialize hashtable: %d\n",
 636                         err);
 637                 vfree(tdata);
 638                 vfree(objs);
 639                 return -EINVAL;
 640         }
 641         for (i = 0; i < tcount; i++) {
 642                 tdata[i].id = i;
 643                 tdata[i].entries = entries;
 644                 tdata[i].objs = objs + i * entries;
 645                 tdata[i].task = kthread_run(threadfunc, &tdata[i],
 646                                             "rhashtable_thrad[%d]", i);
 647                 if (IS_ERR(tdata[i].task))
 648                         pr_err(" kthread_run failed for thread %d\n", i);
 649                 else
 650                         started_threads++;
 651         }
 652         if (down_interruptible(&prestart_sem))
 653                 pr_err("  down interruptible failed\n");
 654         for (i = 0; i < tcount; i++)
 655                 up(&startup_sem);
 656         for (i = 0; i < tcount; i++) {
 657                 if (IS_ERR(tdata[i].task))
 658                         continue;
 659                 if ((err = kthread_stop(tdata[i].task))) {
 660                         pr_warn("Test failed: thread %d returned: %d\n",
 661                                 i, err);
 662                         failed_threads++;
 663                 }
 664         }
 665         rhashtable_destroy(&ht);
 666         vfree(tdata);
 667         vfree(objs);
 668
 669         /*
 670          * rhltable_remove is very expensive, default values can cause test
 671          * to run for 2 minutes or more,  use a smaller number instead.
 672          */
 673         err = test_rhltable(entries / 16);
 674         pr_info("Started %d threads, %d failed, rhltable test returns %d\n",
 675                 started_threads, failed_threads, err);
 676         return 0;
 677 }
 678
 679 static void __exit test_rht_exit(void)
 680 {
 681 }
 682
 683 module_init(test_rht_init);
 684 module_exit(test_rht_exit);
 685
 686 MODULE_LICENSE("GPL v2");