source: mainline/kernel/test/cht/cht1.c@ 9c75a99d

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

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