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