Blame view
lib/test_rhashtable.c
10.3 KB
9d6dbe1bb
|
1 2 3 |
/* * Resizable, Scalable, Concurrent Hash Table * |
1aa661f5c
|
4 |
* Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch> |
9d6dbe1bb
|
5 6 |
* Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net> * |
9d6dbe1bb
|
7 8 9 10 11 12 13 14 15 16 17 18 |
* This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License version 2 as * published by the Free Software Foundation. */ /************************************************************************** * Self Test **************************************************************************/ #include <linux/init.h> #include <linux/jhash.h> #include <linux/kernel.h> |
f4a3e90ba
|
19 |
#include <linux/kthread.h> |
9d6dbe1bb
|
20 21 22 |
#include <linux/module.h> #include <linux/rcupdate.h> #include <linux/rhashtable.h> |
f4a3e90ba
|
23 |
#include <linux/semaphore.h> |
9d6dbe1bb
|
24 |
#include <linux/slab.h> |
685a015e4
|
25 |
#include <linux/sched.h> |
f4a3e90ba
|
26 |
#include <linux/vmalloc.h> |
9d6dbe1bb
|
27 |
|
1aa661f5c
|
28 |
#define MAX_ENTRIES 1000000 |
67b7cbf42
|
29 |
#define TEST_INSERT_FAIL INT_MAX |
1aa661f5c
|
30 31 32 33 34 35 36 37 |
static int entries = 50000; module_param(entries, int, 0); MODULE_PARM_DESC(entries, "Number of entries to add (default: 50000)"); static int runs = 4; module_param(runs, int, 0); MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)"); |
95e435afe
|
38 |
static int max_size = 0; |
1aa661f5c
|
39 |
module_param(max_size, int, 0); |
3b3bf80b9
|
40 |
MODULE_PARM_DESC(max_size, "Maximum table size (default: calculated)"); |
1aa661f5c
|
41 42 43 44 45 46 47 48 |
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
|
49 |
|
f4a3e90ba
|
50 51 52 |
static int tcount = 10; module_param(tcount, int, 0); MODULE_PARM_DESC(tcount, "Number of threads to spawn (default: 10)"); |
d662e037f
|
53 54 55 |
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)"); |
9d6dbe1bb
|
56 |
struct test_obj { |
9d6dbe1bb
|
57 58 59 |
int value; struct rhash_head node; }; |
f4a3e90ba
|
60 61 62 63 64 |
struct thread_data { int id; struct task_struct *task; struct test_obj *objs; }; |
fcc570207
|
65 |
static struct test_obj array[MAX_ENTRIES]; |
1aa661f5c
|
66 |
static struct rhashtable_params test_rht_params = { |
b182aa6e9
|
67 68 69 70 |
.head_offset = offsetof(struct test_obj, node), .key_offset = offsetof(struct test_obj, value), .key_len = sizeof(int), .hashfn = jhash, |
b182aa6e9
|
71 72 |
.nulls_base = (3U << RHT_BASE_SHIFT), }; |
f4a3e90ba
|
73 74 |
static struct semaphore prestart_sem; static struct semaphore startup_sem = __SEMAPHORE_INITIALIZER(startup_sem, 0); |
9e9089e5a
|
75 76 77 |
static int insert_retry(struct rhashtable *ht, struct rhash_head *obj, const struct rhashtable_params params) { |
d662e037f
|
78 |
int err, retries = -1, enomem_retries = 0; |
9e9089e5a
|
79 80 81 82 83 |
do { retries++; cond_resched(); err = rhashtable_insert_fast(ht, obj, params); |
d662e037f
|
84 85 86 87 |
if (err == -ENOMEM && enomem_retry) { enomem_retries++; err = -EBUSY; } |
9e9089e5a
|
88 |
} while (err == -EBUSY); |
d662e037f
|
89 90 91 92 |
if (enomem_retries) pr_info(" %u insertions retried after -ENOMEM ", enomem_retries); |
9e9089e5a
|
93 94 |
return err ? : retries; } |
9d6dbe1bb
|
95 96 97 |
static int __init test_rht_lookup(struct rhashtable *ht) { unsigned int i; |
1aa661f5c
|
98 |
for (i = 0; i < entries * 2; i++) { |
9d6dbe1bb
|
99 100 101 |
struct test_obj *obj; bool expected = !(i % 2); u32 key = i; |
67b7cbf42
|
102 103 |
if (array[i / 2].value == TEST_INSERT_FAIL) expected = false; |
b182aa6e9
|
104 |
obj = rhashtable_lookup_fast(ht, &key, test_rht_params); |
9d6dbe1bb
|
105 106 107 108 109 110 111 112 113 114 115 |
if (expected && !obj) { pr_warn("Test failed: Could not find key %u ", key); return -ENOENT; } else if (!expected && obj) { pr_warn("Test failed: Unexpected entry found for key %u ", key); return -EEXIST; } else if (expected && obj) { |
c2c8a9016
|
116 117 118 119 |
if (obj->value != i) { pr_warn("Test failed: Lookup value mismatch %u!=%u ", obj->value, i); |
9d6dbe1bb
|
120 121 122 |
return -EINVAL; } } |
685a015e4
|
123 124 |
cond_resched_rcu(); |
9d6dbe1bb
|
125 126 127 128 |
} return 0; } |
246b23a76
|
129 |
static void test_bucket_stats(struct rhashtable *ht) |
9d6dbe1bb
|
130 |
{ |
246b23a76
|
131 132 |
unsigned int err, total = 0, chain_len = 0; struct rhashtable_iter hti; |
9d6dbe1bb
|
133 |
struct rhash_head *pos; |
9d6dbe1bb
|
134 |
|
8f6fd83c6
|
135 |
err = rhashtable_walk_init(ht, &hti, GFP_KERNEL); |
246b23a76
|
136 137 138 139 |
if (err) { pr_warn("Test failed: allocation error"); return; } |
9d6dbe1bb
|
140 |
|
246b23a76
|
141 142 143 144 145 146 |
err = rhashtable_walk_start(&hti); if (err && err != -EAGAIN) { pr_warn("Test failed: iterator failed: %d ", err); return; } |
9d6dbe1bb
|
147 |
|
246b23a76
|
148 149 150 151 152 153 154 155 156 157 158 |
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
|
159 |
} |
246b23a76
|
160 |
total++; |
9d6dbe1bb
|
161 |
} |
246b23a76
|
162 163 164 165 166 167 |
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
|
168 |
|
1aa661f5c
|
169 |
if (total != atomic_read(&ht->nelems) || total != entries) |
9d6dbe1bb
|
170 171 |
pr_warn("Test failed: Total count mismatch ^^^"); } |
1aa661f5c
|
172 |
static s64 __init test_rhashtable(struct rhashtable *ht) |
9d6dbe1bb
|
173 |
{ |
9d6dbe1bb
|
174 |
struct test_obj *obj; |
9d6dbe1bb
|
175 |
int err; |
9e9089e5a
|
176 |
unsigned int i, insert_retries = 0; |
1aa661f5c
|
177 |
s64 start, end; |
9d6dbe1bb
|
178 179 180 |
/* * Insertion Test: |
1aa661f5c
|
181 |
* Insert entries into table with all keys even numbers |
9d6dbe1bb
|
182 |
*/ |
1aa661f5c
|
183 184 185 186 |
pr_info(" Adding %d keys ", entries); start = ktime_get_ns(); for (i = 0; i < entries; i++) { |
fcc570207
|
187 |
struct test_obj *obj = &array[i]; |
9d6dbe1bb
|
188 |
|
9d6dbe1bb
|
189 |
obj->value = i * 2; |
9e9089e5a
|
190 191 192 193 |
err = insert_retry(ht, &obj->node, test_rht_params); if (err > 0) insert_retries += err; else if (err) |
fcc570207
|
194 |
return err; |
9d6dbe1bb
|
195 |
} |
9e9089e5a
|
196 197 198 199 |
if (insert_retries) pr_info(" %u insertions retried due to memory pressure ", insert_retries); |
67b7cbf42
|
200 |
|
246b23a76
|
201 |
test_bucket_stats(ht); |
9d6dbe1bb
|
202 |
rcu_read_lock(); |
9d6dbe1bb
|
203 204 |
test_rht_lookup(ht); rcu_read_unlock(); |
246b23a76
|
205 |
test_bucket_stats(ht); |
9d6dbe1bb
|
206 |
|
1aa661f5c
|
207 208 209 |
pr_info(" Deleting %d keys ", entries); for (i = 0; i < entries; i++) { |
9d6dbe1bb
|
210 |
u32 key = i * 2; |
67b7cbf42
|
211 212 213 |
if (array[i].value != TEST_INSERT_FAIL) { obj = rhashtable_lookup_fast(ht, &key, test_rht_params); BUG_ON(!obj); |
9d6dbe1bb
|
214 |
|
67b7cbf42
|
215 216 |
rhashtable_remove_fast(ht, &obj->node, test_rht_params); } |
685a015e4
|
217 218 |
cond_resched(); |
9d6dbe1bb
|
219 |
} |
1aa661f5c
|
220 221 222 223 224 |
end = ktime_get_ns(); pr_info(" Duration of test: %lld ns ", end - start); return end - start; |
9d6dbe1bb
|
225 |
} |
b7f5e5c7f
|
226 |
static struct rhashtable ht; |
f4a3e90ba
|
227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 |
static int thread_lookup_test(struct thread_data *tdata) { int i, err = 0; for (i = 0; i < entries; i++) { struct test_obj *obj; int key = (tdata->id << 16) | i; obj = rhashtable_lookup_fast(&ht, &key, test_rht_params); if (obj && (tdata->objs[i].value == TEST_INSERT_FAIL)) { pr_err(" found unexpected object %d ", key); err++; } else if (!obj && (tdata->objs[i].value != TEST_INSERT_FAIL)) { pr_err(" object %d not found! ", key); err++; } else if (obj && (obj->value != key)) { pr_err(" wrong object returned (got %d, expected %d) ", obj->value, key); err++; } |
cd5b318da
|
250 251 |
cond_resched(); |
f4a3e90ba
|
252 253 254 255 256 257 |
} return err; } static int threadfunc(void *data) { |
9e9089e5a
|
258 |
int i, step, err = 0, insert_retries = 0; |
f4a3e90ba
|
259 260 261 262 263 264 265 266 267 |
struct thread_data *tdata = data; up(&prestart_sem); if (down_interruptible(&startup_sem)) pr_err(" thread[%d]: down_interruptible failed ", tdata->id); for (i = 0; i < entries; i++) { tdata->objs[i].value = (tdata->id << 16) | i; |
9e9089e5a
|
268 269 270 |
err = insert_retry(&ht, &tdata->objs[i].node, test_rht_params); if (err > 0) { insert_retries += err; |
f4a3e90ba
|
271 272 273 274 275 276 277 |
} else if (err) { pr_err(" thread[%d]: rhashtable_insert_fast failed ", tdata->id); goto out; } } |
9e9089e5a
|
278 279 280 281 |
if (insert_retries) pr_info(" thread[%d]: %u insertions retried due to memory pressure ", tdata->id, insert_retries); |
f4a3e90ba
|
282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 |
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--) { for (i = 0; i < entries; i += step) { if (tdata->objs[i].value == TEST_INSERT_FAIL) 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; } tdata->objs[i].value = TEST_INSERT_FAIL; |
cd5b318da
|
304 305 |
cond_resched(); |
f4a3e90ba
|
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 |
} 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
|
322 323 |
static int __init test_rht_init(void) { |
f4a3e90ba
|
324 |
int i, err, started_threads = 0, failed_threads = 0; |
1aa661f5c
|
325 |
u64 total_time = 0; |
f4a3e90ba
|
326 327 |
struct thread_data *tdata; struct test_obj *objs; |
9d6dbe1bb
|
328 |
|
1aa661f5c
|
329 |
entries = min(entries, MAX_ENTRIES); |
9d6dbe1bb
|
330 |
|
1aa661f5c
|
331 |
test_rht_params.automatic_shrinking = shrinking; |
95e435afe
|
332 |
test_rht_params.max_size = max_size ? : roundup_pow_of_two(entries); |
1aa661f5c
|
333 |
test_rht_params.nelem_hint = size; |
9d6dbe1bb
|
334 |
|
1aa661f5c
|
335 336 337 |
pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d ", size, max_size, shrinking); |
9d6dbe1bb
|
338 |
|
1aa661f5c
|
339 340 |
for (i = 0; i < runs; i++) { s64 time; |
9d6dbe1bb
|
341 |
|
1aa661f5c
|
342 343 |
pr_info("Test %02d: ", i); |
fcc570207
|
344 |
memset(&array, 0, sizeof(array)); |
1aa661f5c
|
345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 |
err = rhashtable_init(&ht, &test_rht_params); if (err < 0) { pr_warn("Test failed: Unable to initialize hashtable: %d ", err); continue; } time = test_rhashtable(&ht); rhashtable_destroy(&ht); if (time < 0) { pr_warn("Test failed: return code %lld ", time); return -EINVAL; } total_time += time; } |
6decd63ac
|
363 364 365 |
do_div(total_time, runs); pr_info("Average test time: %llu ", total_time); |
1aa661f5c
|
366 |
|
f4a3e90ba
|
367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 |
if (!tcount) return 0; pr_info("Testing concurrent rhashtable access from %d threads ", tcount); sema_init(&prestart_sem, 1 - tcount); tdata = vzalloc(tcount * sizeof(struct thread_data)); if (!tdata) return -ENOMEM; objs = vzalloc(tcount * entries * sizeof(struct test_obj)); if (!objs) { vfree(tdata); return -ENOMEM; } |
95e435afe
|
382 383 |
test_rht_params.max_size = max_size ? : roundup_pow_of_two(tcount * entries); |
f4a3e90ba
|
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 |
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; tdata[i].objs = objs + i * entries; tdata[i].task = kthread_run(threadfunc, &tdata[i], "rhashtable_thrad[%d]", i); if (IS_ERR(tdata[i].task)) pr_err(" kthread_run failed for thread %d ", i); else started_threads++; } if (down_interruptible(&prestart_sem)) pr_err(" down interruptible failed "); for (i = 0; i < tcount; i++) up(&startup_sem); 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++; } } pr_info("Started %d threads, %d failed ", started_threads, failed_threads); rhashtable_destroy(&ht); vfree(tdata); vfree(objs); |
1aa661f5c
|
425 |
return 0; |
9d6dbe1bb
|
426 |
} |
6dd0c1655
|
427 428 429 |
static void __exit test_rht_exit(void) { } |
9d6dbe1bb
|
430 |
module_init(test_rht_init); |
6dd0c1655
|
431 |
module_exit(test_rht_exit); |
9d6dbe1bb
|
432 433 |
MODULE_LICENSE("GPL v2"); |