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