source: mainline/kernel/test/cht/cht1.c@ df6ded8

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since df6ded8 was 63e27ef, checked in by Jiri Svoboda <jiri@…>, 8 years ago

ASSERT → assert
  • Property mode set to 100644
File size: 13.6 KB
Line 
1/*
2 * Copyright (c) 2012 Adam Hraska
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#include <assert.h>
30#include <test.h>
31#include <print.h>
32#include <adt/cht.h>
33#include <synch/rcu.h>
34
35typedef struct val {
36 /* Place at the top to simplify re-casting. */
37 cht_link_t link;
38 size_t hash;
39 size_t unique_id;
40 bool deleted;
41 bool mark;
42} val_t;
43
44static size_t val_hash(const cht_link_t *item)
45{
46 val_t *v = member_to_inst(item, val_t, link);
47 assert(v->hash == (v->unique_id % 10));
48 return v->hash;
49}
50
51static size_t val_key_hash(void *key)
52{
53 return (uintptr_t)key % 10;
54}
55
56static bool val_equal(const cht_link_t *item1, const cht_link_t *item2)
57{
58 val_t *v1 = member_to_inst(item1, val_t, link);
59 val_t *v2 = member_to_inst(item2, val_t, link);
60 return v1->unique_id == v2->unique_id;
61}
62
63static bool val_key_equal(void *key, const cht_link_t *item2)
64{
65 val_t *v2 = member_to_inst(item2, val_t, link);
66 return (uintptr_t)key == v2->unique_id;
67}
68
69static void val_rm_callback(cht_link_t *item)
70{
71 val_t *v = member_to_inst(item, val_t, link);
72 assert(!v->deleted);
73 v->deleted = true;
74 free(v);
75}
76
77
78static cht_ops_t val_ops = {
79 .hash = val_hash,
80 .key_hash = val_key_hash,
81 .equal = val_equal,
82 .key_equal = val_key_equal,
83 .remove_callback = val_rm_callback,
84};
85
86static void set_val(val_t *v, size_t h, size_t uid)
87{
88 v->hash = h;
89 v->unique_id = uid;
90 v->deleted = false;
91 v->mark = false;
92}
93
94/*-------------------------------------------------------------------*/
95
96
97static const char * do_sanity_test(cht_t *h)
98{
99 if (cht_find_lazy(h, (void*)0))
100 return "Found lazy in empty table.";
101
102 if (cht_find(h, (void*)0))
103 return "Found in empty table.";
104
105 if (cht_remove_key(h, (void*)0))
106 return "Removed from empty table.";
107
108 const int val_cnt = 6;
109 val_t *v[6] = { NULL };
110
111 for (int i = 0; i < val_cnt; ++i)
112 v[i] = malloc(sizeof(val_t), 0);
113
114 size_t key[] = { 1, 1, 1, 11, 12, 13 };
115
116 /* First three are identical */
117 for (int i = 0; i < 3; ++i)
118 set_val(v[i], 1, key[i]);
119
120 /* Same hash, different key.*/
121 set_val(v[3], 1, key[3]);
122
123 /* Different hashes and keys. */
124 set_val(v[4], 2, key[4]);
125 set_val(v[5], 3, key[5]);
126
127 cht_link_t *dup;
128
129 if (!cht_insert_unique(h, &v[0]->link, &dup))
130 return "Duplicates in empty";
131
132 if (cht_insert_unique(h, &v[1]->link, &dup))
133 return "Inserted a duplicate";
134
135 if (dup != &v[0]->link)
136 return "Returned wrong duplicate";
137
138 if (!cht_insert_unique(h, &v[3]->link, &dup))
139 return "Refused non-equal item but with a hash in table.";
140
141 cht_insert(h, &v[1]->link);
142 cht_insert(h, &v[2]->link);
143
144 bool ok = true;
145 ok = ok && cht_insert_unique(h, &v[4]->link, &dup);
146 ok = ok && cht_insert_unique(h, &v[5]->link, &dup);
147
148 if (!ok)
149 return "Refused unique ins 4, 5.";
150
151 if (cht_find(h, (void*)0))
152 return "Phantom find.";
153
154 cht_link_t *item = cht_find(h, (void*)v[5]->unique_id);
155 if (!item || item != &v[5]->link)
156 return "Missing 5.";
157
158 item = cht_find_next(h, &v[5]->link);
159 if (item)
160 return "Found nonexisting duplicate 5";
161
162 item = cht_find(h, (void*)v[3]->unique_id);
163 if (!item || item != &v[3]->link)
164 return "Missing 3.";
165
166 item = cht_find_next(h, &v[3]->link);
167 if (item)
168 return "Found nonexisting duplicate 3, same hash as others.";
169
170 item = cht_find(h, (void*)v[0]->unique_id);
171 ((val_t*)item)->mark = true;
172
173 for (int k = 1; k < 3; ++k) {
174 item = cht_find_next(h, item);
175 if (!item)
176 return "Did not find an inserted duplicate";
177
178 val_t *val = ((val_t*)item);
179
180 if (val->unique_id != v[0]->unique_id)
181 return "Found item with a different key.";
182 if (val->mark)
183 return "Found twice the same node.";
184 val->mark = true;
185 }
186
187 for (int i = 0; i < 3; ++i) {
188 if (!v[i]->mark)
189 return "Did not find all duplicates";
190
191 v[i]->mark = false;
192 }
193
194 if (cht_find_next(h, item))
195 return "Found non-existing duplicate.";
196
197 item = cht_find_next(h, cht_find(h, (void*)key[0]));
198
199 ((val_t*)item)->mark = true;
200 if (!cht_remove_item(h, item))
201 return "Failed to remove inserted item";
202
203 item = cht_find(h, (void*)key[0]);
204 if (!item || ((val_t*)item)->mark)
205 return "Did not find proper item.";
206
207 item = cht_find_next(h, item);
208 if (!item || ((val_t*)item)->mark)
209 return "Did not find proper duplicate.";
210
211 item = cht_find_next(h, item);
212 if (item)
213 return "Found removed duplicate";
214
215 if (2 != cht_remove_key(h, (void*)key[0]))
216 return "Failed to remove all duplicates";
217
218 if (cht_find(h, (void*)key[0]))
219 return "Found removed key";
220
221 if (!cht_find(h, (void*)key[3]))
222 return "Removed incorrect key";
223
224 for (size_t k = 0; k < sizeof(v) / sizeof(v[0]); ++k) {
225 cht_remove_key(h, (void*)key[k]);
226 }
227
228 for (size_t k = 0; k < sizeof(v) / sizeof(v[0]); ++k) {
229 if (cht_find(h, (void*)key[k]))
230 return "Found a key in a cleared table";
231 }
232
233 return NULL;
234}
235
236static const char * sanity_test(void)
237{
238 cht_t h;
239 if (!cht_create_simple(&h, &val_ops))
240 return "Could not create the table.";
241
242 rcu_read_lock();
243 const char *err = do_sanity_test(&h);
244 rcu_read_unlock();
245
246 cht_destroy(&h);
247
248 return err;
249}
250
251/*-------------------------------------------------------------------*/
252
253static size_t next_rand(size_t seed)
254{
255 return (seed * 1103515245 + 12345) & ((1U << 31) - 1);
256}
257
258/*-------------------------------------------------------------------*/
259typedef struct {
260 cht_link_t link;
261 size_t key;
262 bool free;
263 bool inserted;
264 bool deleted;
265} stress_t;
266
267typedef struct {
268 cht_t *h;
269 int *stop;
270 stress_t *elem;
271 size_t elem_cnt;
272 size_t upd_prob;
273 size_t wave_cnt;
274 size_t wave_elems;
275 size_t id;
276 bool failed;
277} stress_work_t;
278
279static size_t stress_hash(const cht_link_t *item)
280{
281 return ((stress_t*)item)->key >> 8;
282}
283static size_t stress_key_hash(void *key)
284{
285 return ((size_t)key) >> 8;
286}
287static bool stress_equal(const cht_link_t *item1, const cht_link_t *item2)
288{
289 return ((stress_t*)item1)->key == ((stress_t*)item2)->key;
290}
291static bool stress_key_equal(void *key, const cht_link_t *item)
292{
293 return ((size_t)key) == ((stress_t*)item)->key;
294}
295static void stress_rm_callback(cht_link_t *item)
296{
297 if (((stress_t*)item)->free)
298 free(item);
299 else
300 ((stress_t*)item)->deleted = true;
301}
302
303cht_ops_t stress_ops = {
304 .hash = stress_hash,
305 .key_hash = stress_key_hash,
306 .equal = stress_equal,
307 .key_equal = stress_key_equal,
308 .remove_callback = stress_rm_callback
309};
310
311static void resize_stresser(void *arg)
312{
313 stress_work_t *work = (stress_work_t *)arg;
314
315 for (size_t k = 0; k < work->wave_cnt; ++k) {
316 TPRINTF("I{");
317 for (size_t i = 0; i < work->wave_elems; ++i) {
318 stress_t *s = malloc(sizeof(stress_t), FRAME_ATOMIC);
319 if (!s) {
320 TPRINTF("[out-of-mem]\n");
321 goto out_of_mem;
322 }
323
324 s->free = true;
325 s->key = (i << 8) + work->id;
326
327 cht_insert(work->h, &s->link);
328 }
329 TPRINTF("}");
330
331 thread_sleep(2);
332
333 TPRINTF("R<");
334 for (size_t i = 0; i < work->wave_elems; ++i) {
335 size_t key = (i << 8) + work->id;
336
337 if (1 != cht_remove_key(work->h, (void*)key)) {
338 TPRINTF("Err: Failed to remove inserted item\n");
339 goto failed;
340 }
341 }
342 TPRINTF(">");
343 }
344
345 /* Request that others stop. */
346 *work->stop = 1;
347 return;
348
349failed:
350 work->failed = true;
351
352out_of_mem:
353 /* Request that others stop. */
354 *work->stop = 1;
355
356 /* Remove anything we may have inserted. */
357 for (size_t i = 0; i < work->wave_elems; ++i) {
358 size_t key = (i << 8) + work->id;
359 cht_remove_key(work->h, (void*)key);
360 }
361}
362
363static void op_stresser(void *arg)
364{
365 stress_work_t *work = (stress_work_t *)arg;
366 assert(0 == *work->stop);
367
368 size_t loops = 0;
369 size_t seed = work->id;
370
371 while (0 == *work->stop && !work->failed) {
372 seed = next_rand(seed);
373 bool upd = ((seed % 100) <= work->upd_prob);
374 seed = next_rand(seed);
375 size_t elem_idx = seed % work->elem_cnt;
376
377 ++loops;
378 if (0 == loops % (1024 * 1024)) {
379 /* Make the most current work->stop visible. */
380 read_barrier();
381 TPRINTF("*");
382 }
383
384 if (upd) {
385 seed = next_rand(seed);
386 bool item_op = seed & 1;
387
388 if (work->elem[elem_idx].inserted) {
389 if (item_op) {
390 rcu_read_lock();
391 cht_remove_item(work->h, &work->elem[elem_idx].link);
392 rcu_read_unlock();
393 } else {
394 void *key = (void*)work->elem[elem_idx].key;
395 if (1 != cht_remove_key(work->h, key)) {
396 TPRINTF("Err: did not rm the key\n");
397 work->failed = true;
398 }
399 }
400 work->elem[elem_idx].inserted = false;
401 } else if (work->elem[elem_idx].deleted) {
402 work->elem[elem_idx].deleted = false;
403
404 if (item_op) {
405 rcu_read_lock();
406 cht_link_t *dup;
407 if (!cht_insert_unique(work->h, &work->elem[elem_idx].link,
408 &dup)) {
409 TPRINTF("Err: already inserted\n");
410 work->failed = true;
411 }
412 rcu_read_unlock();
413 } else {
414 cht_insert(work->h, &work->elem[elem_idx].link);
415 }
416
417 work->elem[elem_idx].inserted = true;
418 }
419 } else {
420 rcu_read_lock();
421 cht_link_t *item =
422 cht_find(work->h, (void*)work->elem[elem_idx].key);
423 rcu_read_unlock();
424
425 if (item) {
426 if (!work->elem[elem_idx].inserted) {
427 TPRINTF("Err: found but not inserted!");
428 work->failed = true;
429 }
430 if (item != &work->elem[elem_idx].link) {
431 TPRINTF("Err: found but incorrect item\n");
432 work->failed = true;
433 }
434 } else {
435 if (work->elem[elem_idx].inserted) {
436 TPRINTF("Err: inserted but not found!");
437 work->failed = true;
438 }
439 }
440 }
441 }
442
443
444 /* Remove anything we may have inserted. */
445 for (size_t i = 0; i < work->elem_cnt; ++i) {
446 void *key = (void*) work->elem[i].key;
447 cht_remove_key(work->h, key);
448 }
449}
450
451static bool do_stress(void)
452{
453 cht_t h;
454
455 if (!cht_create_simple(&h, &stress_ops)) {
456 TPRINTF("Failed to create the table\n");
457 return false;
458 }
459
460 const size_t wave_cnt = 10;
461 const size_t max_thread_cnt = 8;
462 const size_t resize_thread_cnt = 2;
463 size_t op_thread_cnt = min(max_thread_cnt, 2 * config.cpu_active);
464 size_t total_thr_cnt = op_thread_cnt + resize_thread_cnt;
465 size_t items_per_thread = 1024;
466
467 size_t work_cnt = op_thread_cnt + resize_thread_cnt;
468 size_t item_cnt = op_thread_cnt * items_per_thread;
469
470 /* Alloc hash table items. */
471 size_t size = item_cnt * sizeof(stress_t) + work_cnt * sizeof(stress_work_t)
472 + sizeof(int);
473
474 TPRINTF("Alloc and init table items. \n");
475 void *p = malloc(size, FRAME_ATOMIC);
476 if (!p) {
477 TPRINTF("Failed to alloc items\n");
478 cht_destroy(&h);
479 return false;
480 }
481
482 stress_t *pitem = p + work_cnt * sizeof(stress_work_t);
483 stress_work_t *pwork = p;
484 int *pstop = (int*)(pitem + item_cnt);
485
486 *pstop = 0;
487
488 /* Init work items. */
489 for (size_t i = 0; i < op_thread_cnt; ++i) {
490 pwork[i].h = &h;
491 pwork[i].stop = pstop;
492 pwork[i].elem = &pitem[i * items_per_thread];
493 pwork[i].upd_prob = (i + 1) * 100 / op_thread_cnt;
494 pwork[i].id = i;
495 pwork[i].elem_cnt = items_per_thread;
496 pwork[i].failed = false;
497 }
498
499 for (size_t i = op_thread_cnt; i < op_thread_cnt + resize_thread_cnt; ++i) {
500 pwork[i].h = &h;
501 pwork[i].stop = pstop;
502 pwork[i].wave_cnt = wave_cnt;
503 pwork[i].wave_elems = item_cnt * 4;
504 pwork[i].id = i;
505 pwork[i].failed = false;
506 }
507
508 /* Init table elements. */
509 for (size_t k = 0; k < op_thread_cnt; ++k) {
510 for (size_t i = 0; i < items_per_thread; ++i) {
511 pwork[k].elem[i].key = (i << 8) + k;
512 pwork[k].elem[i].free = false;
513 pwork[k].elem[i].inserted = false;
514 pwork[k].elem[i].deleted = true;
515 }
516 }
517
518 TPRINTF("Running %zu ins/del/find stress threads + %zu resizers.\n",
519 op_thread_cnt, resize_thread_cnt);
520
521 /* Create and run threads. */
522 thread_t *thr[max_thread_cnt + resize_thread_cnt];
523
524 for (size_t i = 0; i < total_thr_cnt; ++i) {
525 if (i < op_thread_cnt)
526 thr[i] = thread_create(op_stresser, &pwork[i], TASK, 0, "cht-op-stress");
527 else
528 thr[i] = thread_create(resize_stresser, &pwork[i], TASK, 0, "cht-resize");
529
530 assert(thr[i]);
531 thread_wire(thr[i], &cpus[i % config.cpu_active]);
532 thread_ready(thr[i]);
533 }
534
535 bool failed = false;
536
537 /* Wait for all threads to return. */
538 TPRINTF("Joining resize stressers.\n");
539 for (size_t i = op_thread_cnt; i < total_thr_cnt; ++i) {
540 thread_join(thr[i]);
541 thread_detach(thr[i]);
542 failed = pwork[i].failed || failed;
543 }
544
545 TPRINTF("Joining op stressers.\n");
546 for (int i = (int)op_thread_cnt - 1; i >= 0; --i) {
547 TPRINTF("%d threads remain\n", i);
548 thread_join(thr[i]);
549 thread_detach(thr[i]);
550 failed = pwork[i].failed || failed;
551 }
552
553 cht_destroy(&h);
554 free(p);
555
556 return !failed;
557}
558
559/*-------------------------------------------------------------------*/
560
561
562const char *test_cht1(void)
563{
564 const char *err = sanity_test();
565 if (err)
566 return err;
567 printf("Basic sanity test: ok.\n");
568
569 if (!do_stress())
570 return "CHT stress test failed.";
571 else
572 return NULL;
573}
Note: See TracBrowser for help on using the repository browser.