test_rhashtable.c 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * Resizable, Scalable, Concurrent Hash Table
  4. *
  5. * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
  6. * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
  7. */
  8. /**************************************************************************
  9. * Self Test
  10. **************************************************************************/
  11. #include <linux/init.h>
  12. #include <linux/jhash.h>
  13. #include <linux/kernel.h>
  14. #include <linux/kthread.h>
  15. #include <linux/module.h>
  16. #include <linux/rcupdate.h>
  17. #include <linux/rhashtable.h>
  18. #include <linux/slab.h>
  19. #include <linux/sched.h>
  20. #include <linux/random.h>
  21. #include <linux/vmalloc.h>
  22. #include <linux/wait.h>
  23. #define MAX_ENTRIES 1000000
  24. #define TEST_INSERT_FAIL INT_MAX
  25. static int parm_entries = 50000;
  26. module_param(parm_entries, int, 0);
  27. MODULE_PARM_DESC(parm_entries, "Number of entries to add (default: 50000)");
  28. static int runs = 4;
  29. module_param(runs, int, 0);
  30. MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)");
  31. static int max_size = 0;
  32. module_param(max_size, int, 0);
  33. MODULE_PARM_DESC(max_size, "Maximum table size (default: calculated)");
  34. static bool shrinking = false;
  35. module_param(shrinking, bool, 0);
  36. MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)");
  37. static int size = 8;
  38. module_param(size, int, 0);
  39. MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)");
  40. static int tcount = 10;
  41. module_param(tcount, int, 0);
  42. MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)");
  43. static bool enomem_retry = false;
  44. module_param(enomem_retry, bool, 0);
  45. MODULE_PARM_DESC(enomem_retry, "Retry insert even if -ENOMEM was returned (default: off)");
  46. struct test_obj_val {
  47. int id;
  48. int tid;
  49. };
  50. struct test_obj {
  51. struct test_obj_val value;
  52. struct rhash_head node;
  53. };
  54. struct test_obj_rhl {
  55. struct test_obj_val value;
  56. struct rhlist_head list_node;
  57. };
  58. struct thread_data {
  59. unsigned int entries;
  60. int id;
  61. struct task_struct *task;
  62. struct test_obj *objs;
  63. };
  64. static u32 my_hashfn(const void *data, u32 len, u32 seed)
  65. {
  66. const struct test_obj_rhl *obj = data;
  67. return (obj->value.id % 10);
  68. }
  69. static int my_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
  70. {
  71. const struct test_obj_rhl *test_obj = obj;
  72. const struct test_obj_val *val = arg->key;
  73. return test_obj->value.id - val->id;
  74. }
  75. static struct rhashtable_params test_rht_params = {
  76. .head_offset = offsetof(struct test_obj, node),
  77. .key_offset = offsetof(struct test_obj, value),
  78. .key_len = sizeof(struct test_obj_val),
  79. .hashfn = jhash,
  80. };
  81. static struct rhashtable_params test_rht_params_dup = {
  82. .head_offset = offsetof(struct test_obj_rhl, list_node),
  83. .key_offset = offsetof(struct test_obj_rhl, value),
  84. .key_len = sizeof(struct test_obj_val),
  85. .hashfn = jhash,
  86. .obj_hashfn = my_hashfn,
  87. .obj_cmpfn = my_cmpfn,
  88. .nelem_hint = 128,
  89. .automatic_shrinking = false,
  90. };
  91. static atomic_t startup_count;
  92. static DECLARE_WAIT_QUEUE_HEAD(startup_wait);
  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. do {
  98. retries++;
  99. cond_resched();
  100. err = rhashtable_insert_fast(ht, &obj->node, params);
  101. if (err == -ENOMEM && enomem_retry) {
  102. enomem_retries++;
  103. err = -EBUSY;
  104. }
  105. } while (err == -EBUSY);
  106. if (enomem_retries)
  107. pr_info(" %u insertions retried after -ENOMEM\n",
  108. enomem_retries);
  109. return err ? : retries;
  110. }
  111. static int __init test_rht_lookup(struct rhashtable *ht, struct test_obj *array,
  112. unsigned int entries)
  113. {
  114. unsigned int i;
  115. for (i = 0; i < entries; i++) {
  116. struct test_obj *obj;
  117. bool expected = !(i % 2);
  118. struct test_obj_val key = {
  119. .id = i,
  120. };
  121. if (array[i / 2].value.id == TEST_INSERT_FAIL)
  122. expected = false;
  123. obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
  124. if (expected && !obj) {
  125. pr_warn("Test failed: Could not find key %u\n", key.id);
  126. return -ENOENT;
  127. } else if (!expected && obj) {
  128. pr_warn("Test failed: Unexpected entry found for key %u\n",
  129. key.id);
  130. return -EEXIST;
  131. } else if (expected && obj) {
  132. if (obj->value.id != i) {
  133. pr_warn("Test failed: Lookup value mismatch %u!=%u\n",
  134. obj->value.id, i);
  135. return -EINVAL;
  136. }
  137. }
  138. cond_resched_rcu();
  139. }
  140. return 0;
  141. }
  142. static void test_bucket_stats(struct rhashtable *ht, unsigned int entries)
  143. {
  144. unsigned int total = 0, chain_len = 0;
  145. struct rhashtable_iter hti;
  146. struct rhash_head *pos;
  147. rhashtable_walk_enter(ht, &hti);
  148. rhashtable_walk_start(&hti);
  149. while ((pos = rhashtable_walk_next(&hti))) {
  150. if (PTR_ERR(pos) == -EAGAIN) {
  151. pr_info("Info: encountered resize\n");
  152. chain_len++;
  153. continue;
  154. } else if (IS_ERR(pos)) {
  155. pr_warn("Test failed: rhashtable_walk_next() error: %ld\n",
  156. PTR_ERR(pos));
  157. break;
  158. }
  159. total++;
  160. }
  161. rhashtable_walk_stop(&hti);
  162. rhashtable_walk_exit(&hti);
  163. pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n",
  164. total, atomic_read(&ht->nelems), entries, chain_len);
  165. if (total != atomic_read(&ht->nelems) || total != entries)
  166. pr_warn("Test failed: Total count mismatch ^^^");
  167. }
  168. static s64 __init test_rhashtable(struct rhashtable *ht, struct test_obj *array,
  169. unsigned int entries)
  170. {
  171. struct test_obj *obj;
  172. int err;
  173. unsigned int i, insert_retries = 0;
  174. s64 start, end;
  175. /*
  176. * Insertion Test:
  177. * Insert entries into table with all keys even numbers
  178. */
  179. pr_info(" Adding %d keys\n", entries);
  180. start = ktime_get_ns();
  181. for (i = 0; i < entries; i++) {
  182. struct test_obj *obj = &array[i];
  183. obj->value.id = i * 2;
  184. err = insert_retry(ht, obj, test_rht_params);
  185. if (err > 0)
  186. insert_retries += err;
  187. else if (err)
  188. return err;
  189. }
  190. if (insert_retries)
  191. pr_info(" %u insertions retried due to memory pressure\n",
  192. insert_retries);
  193. test_bucket_stats(ht, entries);
  194. rcu_read_lock();
  195. test_rht_lookup(ht, array, entries);
  196. rcu_read_unlock();
  197. test_bucket_stats(ht, entries);
  198. pr_info(" Deleting %d keys\n", entries);
  199. for (i = 0; i < entries; i++) {
  200. struct test_obj_val key = {
  201. .id = i * 2,
  202. };
  203. if (array[i].value.id != TEST_INSERT_FAIL) {
  204. obj = rhashtable_lookup_fast(ht, &key, test_rht_params);
  205. BUG_ON(!obj);
  206. rhashtable_remove_fast(ht, &obj->node, test_rht_params);
  207. }
  208. cond_resched();
  209. }
  210. end = ktime_get_ns();
  211. pr_info(" Duration of test: %lld ns\n", end - start);
  212. return end - start;
  213. }
  214. static struct rhashtable ht;
  215. static struct rhltable rhlt;
  216. static int __init test_rhltable(unsigned int entries)
  217. {
  218. struct test_obj_rhl *rhl_test_objects;
  219. unsigned long *obj_in_table;
  220. unsigned int i, j, k;
  221. int ret, err;
  222. if (entries == 0)
  223. entries = 1;
  224. rhl_test_objects = vzalloc(array_size(entries,
  225. sizeof(*rhl_test_objects)));
  226. if (!rhl_test_objects)
  227. return -ENOMEM;
  228. ret = -ENOMEM;
  229. obj_in_table = vzalloc(array_size(sizeof(unsigned long),
  230. BITS_TO_LONGS(entries)));
  231. if (!obj_in_table)
  232. goto out_free;
  233. err = rhltable_init(&rhlt, &test_rht_params);
  234. if (WARN_ON(err))
  235. goto out_free;
  236. k = prandom_u32();
  237. ret = 0;
  238. for (i = 0; i < entries; i++) {
  239. rhl_test_objects[i].value.id = k;
  240. err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
  241. test_rht_params);
  242. if (WARN(err, "error %d on element %d\n", err, i))
  243. break;
  244. if (err == 0)
  245. set_bit(i, obj_in_table);
  246. }
  247. if (err)
  248. ret = err;
  249. pr_info("test %d add/delete pairs into rhlist\n", entries);
  250. for (i = 0; i < entries; i++) {
  251. struct rhlist_head *h, *pos;
  252. struct test_obj_rhl *obj;
  253. struct test_obj_val key = {
  254. .id = k,
  255. };
  256. bool found;
  257. rcu_read_lock();
  258. h = rhltable_lookup(&rhlt, &key, test_rht_params);
  259. if (WARN(!h, "key not found during iteration %d of %d", i, entries)) {
  260. rcu_read_unlock();
  261. break;
  262. }
  263. if (i) {
  264. j = i - 1;
  265. rhl_for_each_entry_rcu(obj, pos, h, list_node) {
  266. if (WARN(pos == &rhl_test_objects[j].list_node, "old element found, should be gone"))
  267. break;
  268. }
  269. }
  270. cond_resched_rcu();
  271. found = false;
  272. rhl_for_each_entry_rcu(obj, pos, h, list_node) {
  273. if (pos == &rhl_test_objects[i].list_node) {
  274. found = true;
  275. break;
  276. }
  277. }
  278. rcu_read_unlock();
  279. if (WARN(!found, "element %d not found", i))
  280. break;
  281. err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
  282. WARN(err, "rhltable_remove: err %d for iteration %d\n", err, i);
  283. if (err == 0)
  284. clear_bit(i, obj_in_table);
  285. }
  286. if (ret == 0 && err)
  287. ret = err;
  288. for (i = 0; i < entries; i++) {
  289. WARN(test_bit(i, obj_in_table), "elem %d allegedly still present", i);
  290. err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node,
  291. test_rht_params);
  292. if (WARN(err, "error %d on element %d\n", err, i))
  293. break;
  294. if (err == 0)
  295. set_bit(i, obj_in_table);
  296. }
  297. pr_info("test %d random rhlist add/delete operations\n", entries);
  298. for (j = 0; j < entries; j++) {
  299. u32 i = prandom_u32_max(entries);
  300. u32 prand = prandom_u32();
  301. cond_resched();
  302. if (prand == 0)
  303. prand = prandom_u32();
  304. if (prand & 1) {
  305. prand >>= 1;
  306. continue;
  307. }
  308. err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
  309. if (test_bit(i, obj_in_table)) {
  310. clear_bit(i, obj_in_table);
  311. if (WARN(err, "cannot remove element at slot %d", i))
  312. continue;
  313. } else {
  314. if (WARN(err != -ENOENT, "removed non-existent element %d, error %d not %d",
  315. i, err, -ENOENT))
  316. continue;
  317. }
  318. if (prand & 1) {
  319. prand >>= 1;
  320. continue;
  321. }
  322. err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
  323. if (err == 0) {
  324. if (WARN(test_and_set_bit(i, obj_in_table), "succeeded to insert same object %d", i))
  325. continue;
  326. } else {
  327. if (WARN(!test_bit(i, obj_in_table), "failed to insert object %d", i))
  328. continue;
  329. }
  330. if (prand & 1) {
  331. prand >>= 1;
  332. continue;
  333. }
  334. i = prandom_u32_max(entries);
  335. if (test_bit(i, obj_in_table)) {
  336. err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
  337. WARN(err, "cannot remove element at slot %d", i);
  338. if (err == 0)
  339. clear_bit(i, obj_in_table);
  340. } else {
  341. err = rhltable_insert(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
  342. WARN(err, "failed to insert object %d", i);
  343. if (err == 0)
  344. set_bit(i, obj_in_table);
  345. }
  346. }
  347. for (i = 0; i < entries; i++) {
  348. cond_resched();
  349. err = rhltable_remove(&rhlt, &rhl_test_objects[i].list_node, test_rht_params);
  350. if (test_bit(i, obj_in_table)) {
  351. if (WARN(err, "cannot remove element at slot %d", i))
  352. continue;
  353. } else {
  354. if (WARN(err != -ENOENT, "removed non-existent element, error %d not %d",
  355. err, -ENOENT))
  356. continue;
  357. }
  358. }
  359. rhltable_destroy(&rhlt);
  360. out_free:
  361. vfree(rhl_test_objects);
  362. vfree(obj_in_table);
  363. return ret;
  364. }
  365. static int __init test_rhashtable_max(struct test_obj *array,
  366. unsigned int entries)
  367. {
  368. unsigned int i, insert_retries = 0;
  369. int err;
  370. test_rht_params.max_size = roundup_pow_of_two(entries / 8);
  371. err = rhashtable_init(&ht, &test_rht_params);
  372. if (err)
  373. return err;
  374. for (i = 0; i < ht.max_elems; i++) {
  375. struct test_obj *obj = &array[i];
  376. obj->value.id = i * 2;
  377. err = insert_retry(&ht, obj, test_rht_params);
  378. if (err > 0)
  379. insert_retries += err;
  380. else if (err)
  381. return err;
  382. }
  383. err = insert_retry(&ht, &array[ht.max_elems], test_rht_params);
  384. if (err == -E2BIG) {
  385. err = 0;
  386. } else {
  387. pr_info("insert element %u should have failed with %d, got %d\n",
  388. ht.max_elems, -E2BIG, err);
  389. if (err == 0)
  390. err = -1;
  391. }
  392. rhashtable_destroy(&ht);
  393. return err;
  394. }
  395. static unsigned int __init print_ht(struct rhltable *rhlt)
  396. {
  397. struct rhashtable *ht;
  398. const struct bucket_table *tbl;
  399. char buff[512] = "";
  400. unsigned int i, cnt = 0;
  401. ht = &rhlt->ht;
  402. /* Take the mutex to avoid RCU warning */
  403. mutex_lock(&ht->mutex);
  404. tbl = rht_dereference(ht->tbl, ht);
  405. for (i = 0; i < tbl->size; i++) {
  406. struct rhash_head *pos, *next;
  407. struct test_obj_rhl *p;
  408. pos = rht_ptr_exclusive(tbl->buckets + i);
  409. next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;
  410. if (!rht_is_a_nulls(pos)) {
  411. sprintf(buff, "%s\nbucket[%d] -> ", buff, i);
  412. }
  413. while (!rht_is_a_nulls(pos)) {
  414. struct rhlist_head *list = container_of(pos, struct rhlist_head, rhead);
  415. sprintf(buff, "%s[[", buff);
  416. do {
  417. pos = &list->rhead;
  418. list = rht_dereference(list->next, ht);
  419. p = rht_obj(ht, pos);
  420. sprintf(buff, "%s val %d (tid=%d)%s", buff, p->value.id, p->value.tid,
  421. list? ", " : " ");
  422. cnt++;
  423. } while (list);
  424. pos = next,
  425. next = !rht_is_a_nulls(pos) ?
  426. rht_dereference(pos->next, ht) : NULL;
  427. sprintf(buff, "%s]]%s", buff, !rht_is_a_nulls(pos) ? " -> " : "");
  428. }
  429. }
  430. printk(KERN_ERR "\n---- ht: ----%s\n-------------\n", buff);
  431. mutex_unlock(&ht->mutex);
  432. return cnt;
  433. }
  434. static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
  435. int cnt, bool slow)
  436. {
  437. struct rhltable *rhlt;
  438. unsigned int i, ret;
  439. const char *key;
  440. int err = 0;
  441. rhlt = kmalloc(sizeof(*rhlt), GFP_KERNEL);
  442. if (WARN_ON(!rhlt))
  443. return -EINVAL;
  444. err = rhltable_init(rhlt, &test_rht_params_dup);
  445. if (WARN_ON(err)) {
  446. kfree(rhlt);
  447. return err;
  448. }
  449. for (i = 0; i < cnt; i++) {
  450. rhl_test_objects[i].value.tid = i;
  451. key = rht_obj(&rhlt->ht, &rhl_test_objects[i].list_node.rhead);
  452. key += test_rht_params_dup.key_offset;
  453. if (slow) {
  454. err = PTR_ERR(rhashtable_insert_slow(&rhlt->ht, key,
  455. &rhl_test_objects[i].list_node.rhead));
  456. if (err == -EAGAIN)
  457. err = 0;
  458. } else
  459. err = rhltable_insert(rhlt,
  460. &rhl_test_objects[i].list_node,
  461. test_rht_params_dup);
  462. if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
  463. goto skip_print;
  464. }
  465. ret = print_ht(rhlt);
  466. WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");
  467. skip_print:
  468. rhltable_destroy(rhlt);
  469. kfree(rhlt);
  470. return 0;
  471. }
  472. static int __init test_insert_duplicates_run(void)
  473. {
  474. struct test_obj_rhl rhl_test_objects[3] = {};
  475. pr_info("test inserting duplicates\n");
  476. /* two different values that map to same bucket */
  477. rhl_test_objects[0].value.id = 1;
  478. rhl_test_objects[1].value.id = 21;
  479. /* and another duplicate with same as [0] value
  480. * which will be second on the bucket list */
  481. rhl_test_objects[2].value.id = rhl_test_objects[0].value.id;
  482. test_insert_dup(rhl_test_objects, 2, false);
  483. test_insert_dup(rhl_test_objects, 3, false);
  484. test_insert_dup(rhl_test_objects, 2, true);
  485. test_insert_dup(rhl_test_objects, 3, true);
  486. return 0;
  487. }
  488. static int thread_lookup_test(struct thread_data *tdata)
  489. {
  490. unsigned int entries = tdata->entries;
  491. int i, err = 0;
  492. for (i = 0; i < entries; i++) {
  493. struct test_obj *obj;
  494. struct test_obj_val key = {
  495. .id = i,
  496. .tid = tdata->id,
  497. };
  498. obj = rhashtable_lookup_fast(&ht, &key, test_rht_params);
  499. if (obj && (tdata->objs[i].value.id == TEST_INSERT_FAIL)) {
  500. pr_err(" found unexpected object %d-%d\n", key.tid, key.id);
  501. err++;
  502. } else if (!obj && (tdata->objs[i].value.id != TEST_INSERT_FAIL)) {
  503. pr_err(" object %d-%d not found!\n", key.tid, key.id);
  504. err++;
  505. } else if (obj && memcmp(&obj->value, &key, sizeof(key))) {
  506. pr_err(" wrong object returned (got %d-%d, expected %d-%d)\n",
  507. obj->value.tid, obj->value.id, key.tid, key.id);
  508. err++;
  509. }
  510. cond_resched();
  511. }
  512. return err;
  513. }
  514. static int threadfunc(void *data)
  515. {
  516. int i, step, err = 0, insert_retries = 0;
  517. struct thread_data *tdata = data;
  518. if (atomic_dec_and_test(&startup_count))
  519. wake_up(&startup_wait);
  520. if (wait_event_interruptible(startup_wait, atomic_read(&startup_count) == -1)) {
  521. pr_err(" thread[%d]: interrupted\n", tdata->id);
  522. goto out;
  523. }
  524. for (i = 0; i < tdata->entries; i++) {
  525. tdata->objs[i].value.id = i;
  526. tdata->objs[i].value.tid = tdata->id;
  527. err = insert_retry(&ht, &tdata->objs[i], test_rht_params);
  528. if (err > 0) {
  529. insert_retries += err;
  530. } else if (err) {
  531. pr_err(" thread[%d]: rhashtable_insert_fast failed\n",
  532. tdata->id);
  533. goto out;
  534. }
  535. }
  536. if (insert_retries)
  537. pr_info(" thread[%d]: %u insertions retried due to memory pressure\n",
  538. tdata->id, insert_retries);
  539. err = thread_lookup_test(tdata);
  540. if (err) {
  541. pr_err(" thread[%d]: rhashtable_lookup_test failed\n",
  542. tdata->id);
  543. goto out;
  544. }
  545. for (step = 10; step > 0; step--) {
  546. for (i = 0; i < tdata->entries; i += step) {
  547. if (tdata->objs[i].value.id == TEST_INSERT_FAIL)
  548. continue;
  549. err = rhashtable_remove_fast(&ht, &tdata->objs[i].node,
  550. test_rht_params);
  551. if (err) {
  552. pr_err(" thread[%d]: rhashtable_remove_fast failed\n",
  553. tdata->id);
  554. goto out;
  555. }
  556. tdata->objs[i].value.id = TEST_INSERT_FAIL;
  557. cond_resched();
  558. }
  559. err = thread_lookup_test(tdata);
  560. if (err) {
  561. pr_err(" thread[%d]: rhashtable_lookup_test (2) failed\n",
  562. tdata->id);
  563. goto out;
  564. }
  565. }
  566. out:
  567. while (!kthread_should_stop()) {
  568. set_current_state(TASK_INTERRUPTIBLE);
  569. schedule();
  570. }
  571. return err;
  572. }
  573. static int __init test_rht_init(void)
  574. {
  575. unsigned int entries;
  576. int i, err, started_threads = 0, failed_threads = 0;
  577. u64 total_time = 0;
  578. struct thread_data *tdata;
  579. struct test_obj *objs;
  580. if (parm_entries < 0)
  581. parm_entries = 1;
  582. entries = min(parm_entries, MAX_ENTRIES);
  583. test_rht_params.automatic_shrinking = shrinking;
  584. test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries);
  585. test_rht_params.nelem_hint = size;
  586. objs = vzalloc(array_size(sizeof(struct test_obj),
  587. test_rht_params.max_size + 1));
  588. if (!objs)
  589. return -ENOMEM;
  590. pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n",
  591. size, max_size, shrinking);
  592. for (i = 0; i < runs; i++) {
  593. s64 time;
  594. pr_info("Test %02d:\n", i);
  595. memset(objs, 0, test_rht_params.max_size * sizeof(struct test_obj));
  596. err = rhashtable_init(&ht, &test_rht_params);
  597. if (err < 0) {
  598. pr_warn("Test failed: Unable to initialize hashtable: %d\n",
  599. err);
  600. continue;
  601. }
  602. time = test_rhashtable(&ht, objs, entries);
  603. rhashtable_destroy(&ht);
  604. if (time < 0) {
  605. vfree(objs);
  606. pr_warn("Test failed: return code %lld\n", time);
  607. return -EINVAL;
  608. }
  609. total_time += time;
  610. }
  611. pr_info("test if its possible to exceed max_size %d: %s\n",
  612. test_rht_params.max_size, test_rhashtable_max(objs, entries) == 0 ?
  613. "no, ok" : "YES, failed");
  614. vfree(objs);
  615. do_div(total_time, runs);
  616. pr_info("Average test time: %llu\n", total_time);
  617. test_insert_duplicates_run();
  618. if (!tcount)
  619. return 0;
  620. pr_info("Testing concurrent rhashtable access from %d threads\n",
  621. tcount);
  622. atomic_set(&startup_count, tcount);
  623. tdata = vzalloc(array_size(tcount, sizeof(struct thread_data)));
  624. if (!tdata)
  625. return -ENOMEM;
  626. objs = vzalloc(array3_size(sizeof(struct test_obj), tcount, entries));
  627. if (!objs) {
  628. vfree(tdata);
  629. return -ENOMEM;
  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. atomic_dec(&startup_count);
  650. } else {
  651. started_threads++;
  652. }
  653. }
  654. if (wait_event_interruptible(startup_wait, atomic_read(&startup_count) == 0))
  655. pr_err(" wait_event interruptible failed\n");
  656. /* count is 0 now, set it to -1 and wake up all threads together */
  657. atomic_dec(&startup_count);
  658. wake_up_all(&startup_wait);
  659. for (i = 0; i < tcount; i++) {
  660. if (IS_ERR(tdata[i].task))
  661. continue;
  662. if ((err = kthread_stop(tdata[i].task))) {
  663. pr_warn("Test failed: thread %d returned: %d\n",
  664. i, err);
  665. failed_threads++;
  666. }
  667. }
  668. rhashtable_destroy(&ht);
  669. vfree(tdata);
  670. vfree(objs);
  671. /*
  672. * rhltable_remove is very expensive, default values can cause test
  673. * to run for 2 minutes or more, use a smaller number instead.
  674. */
  675. err = test_rhltable(entries / 16);
  676. pr_info("Started %d threads, %d failed, rhltable test returns %d\n",
  677. started_threads, failed_threads, err);
  678. return 0;
  679. }
  680. static void __exit test_rht_exit(void)
  681. {
  682. }
  683. module_init(test_rht_init);
  684. module_exit(test_rht_exit);
  685. MODULE_LICENSE("GPL v2");