source: mainline/kernel/test/cht/cht1.c@ 0b7bcb8

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 0b7bcb8 was 0b7bcb8, checked in by Adam Hraska <adam.hraska+hos@…>, 13 years ago

cht: Slightly changed CHT interface. It now allows to specify the maximum desired load of the table before it resizes.
  • Property mode set to 100644
File size: 13.3 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 <test.h>
30#include <print.h>
31#include <debug.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, 0))
100 return "Found lazy in empty table.";
101
102 if (cht_find(h, 0))
103 return "Found in empty table.";
104
105 if (cht_remove_key(h, 0))
106 return "Removed from empty table.";
107
108 const int val_cnt = 6;
109 val_t *v[6] = {0};
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
128 if (!cht_insert_unique(h, &v[0]->link))
129 return "Duplicates in empty";
130
131 if (cht_insert_unique(h, &v[1]->link))
132 return "Inserted a duplicate";
133
134 if (!cht_insert_unique(h, &v[3]->link))
135 return "Refused non-equal item but with a hash in table.";
136
137 cht_insert(h, &v[1]->link);
138 cht_insert(h, &v[2]->link);
139
140 bool ok = true;
141 ok = ok && cht_insert_unique(h, &v[4]->link);
142 ok = ok && cht_insert_unique(h, &v[5]->link);
143
144 if (!ok)
145 return "Refused unique ins 4, 5.";
146
147 if (cht_find(h, (void*)0))
148 return "Fantom find.";
149
150 cht_link_t *item = cht_find(h, (void*)v[5]->unique_id);
151 if (!item || item != &v[5]->link)
152 return "Missing 5.";
153
154 item = cht_find_next(h, &v[5]->link);
155 if (item)
156 return "Found nonexisting duplicate 5";
157
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
168 item = cht_find(h, (void*)v[0]->unique_id);
169 ((val_t*)item)->mark = true;
170
171 for (int k = 1; k < 3; ++k) {
172 item = cht_find_next(h, item);
173 if (!item)
174 return "Did not find an inserted duplicate";
175
176 val_t *val = ((val_t*)item);
177
178 if (val->unique_id != v[0]->unique_id)
179 return "Found item with a different key.";
180 if (val->mark)
181 return "Found twice the same node.";
182 val->mark = true;
183 }
184
185 for (int i = 0; i < 3; ++i) {
186 if (!v[i]->mark)
187 return "Did not find all duplicates";
188
189 v[i]->mark = false;
190 }
191
192 if (cht_find_next(h, item))
193 return "Found non-existing duplicate.";
194
195 item = cht_find_next(h, cht_find(h, (void*)key[0]));
196
197 ((val_t*)item)->mark = true;
198 if (!cht_remove_item(h, item))
199 return "Failed to remove inserted item";
200
201 item = cht_find(h, (void*)key[0]);
202 if (!item || ((val_t*)item)->mark)
203 return "Did not find proper item.";
204
205 item = cht_find_next(h, item);
206 if (!item || ((val_t*)item)->mark)
207 return "Did not find proper duplicate.";
208
209 item = cht_find_next(h, item);
210 if (item)
211 return "Found removed duplicate";
212
213 if (2 != cht_remove_key(h, (void*)key[0]))
214 return "Failed to remove all duplicates";
215
216 if (cht_find(h, (void*)key[0]))
217 return "Found removed key";
218
219 if (!cht_find(h, (void*)key[3]))
220 return "Removed incorrect key";
221
222 for (size_t k = 0; k < sizeof(v)/sizeof(v[0]); ++k) {
223 cht_remove_key(h, (void*)key[k]);
224 }
225
226 for (size_t k = 0; k < sizeof(v)/sizeof(v[0]); ++k) {
227 if (cht_find(h, (void*)key[k]))
228 return "Found a key in a cleared table";
229 }
230
231 return 0;
232}
233
234static const char * sanity_test(void)
235{
236 cht_t h;
237 if (!cht_create(&h, 5, 0, 0, &val_ops))
238 return "Could not create the table.";
239
240 rcu_read_lock();
241 const char *err = do_sanity_test(&h);
242 rcu_read_unlock();
243
244 cht_destroy(&h);
245
246 return err;
247}
248
249/*-------------------------------------------------------------------*/
250
251static size_t next_rand(size_t seed)
252{
253 return (seed * 1103515245 + 12345) & ((1U << 31) - 1);
254}
255
256/*-------------------------------------------------------------------*/
257typedef struct {
258 cht_link_t link;
259 size_t key;
260 bool free;
261 bool inserted;
262 bool deleted;
263} stress_t;
264
265typedef struct {
266 cht_t *h;
267 int *stop;
268 stress_t *elem;
269 size_t elem_cnt;
270 size_t upd_prob;
271 size_t wave_cnt;
272 size_t wave_elems;
273 size_t id;
274 bool failed;
275} stress_work_t;
276
277static size_t stress_hash(const cht_link_t *item)
278{
279 return ((stress_t*)item)->key >> 8;
280}
281static size_t stress_key_hash(void *key)
282{
283 return ((size_t)key) >> 8;
284}
285static bool stress_equal(const cht_link_t *item1, const cht_link_t *item2)
286{
287 return ((stress_t*)item1)->key == ((stress_t*)item2)->key;
288}
289static bool stress_key_equal(void *key, const cht_link_t *item)
290{
291 return ((size_t)key) == ((stress_t*)item)->key;
292}
293static void stress_rm_callback(cht_link_t *item)
294{
295 if (((stress_t*)item)->free)
296 free(item);
297 else
298 ((stress_t*)item)->deleted = true;
299}
300
301cht_ops_t stress_ops = {
302 .hash = stress_hash,
303 .key_hash = stress_key_hash,
304 .equal = stress_equal,
305 .key_equal = stress_key_equal,
306 .remove_callback = stress_rm_callback
307};
308
309static void resize_stresser(void *arg)
310{
311 stress_work_t *work = (stress_work_t *)arg;
312
313 for (size_t k = 0; k < work->wave_cnt; ++k) {
314 TPRINTF("I{");
315 for (size_t i = 0; i < work->wave_elems; ++i) {
316 stress_t *s = malloc(sizeof(stress_t), FRAME_ATOMIC);
317 if (!s) {
318 TPRINTF("[out-of-mem]\n");
319 goto out_of_mem;
320 }
321
322 s->free = true;
323 s->key = (i << 8) + work->id;
324
325 cht_insert(work->h, &s->link);
326 }
327 TPRINTF("}");
328
329 thread_sleep(2);
330
331 TPRINTF("R<");
332 for (size_t i = 0; i < work->wave_elems; ++i) {
333 size_t key = (i << 8) + work->id;
334
335 if (1 != cht_remove_key(work->h, (void*)key)) {
336 TPRINTF("Err: Failed to remove inserted item\n");
337 goto failed;
338 }
339 }
340 TPRINTF(">");
341 }
342
343 /* Request that others stop. */
344 *work->stop = 1;
345 return;
346
347failed:
348 work->failed = true;
349
350out_of_mem:
351 /* Request that others stop. */
352 *work->stop = 1;
353
354 /* Remove anything we may have inserted. */
355 for (size_t i = 0; i < work->wave_elems; ++i) {
356 size_t key = (i << 8) + work->id;
357 cht_remove_key(work->h, (void*)key);
358 }
359}
360
361static void op_stresser(void *arg)
362{
363 stress_work_t *work = (stress_work_t *)arg;
364 ASSERT(0 == *work->stop);
365
366 size_t loops = 0;
367 size_t seed = work->id;
368
369 while (0 == *work->stop && !work->failed) {
370 seed = next_rand(seed);
371 bool upd = ((seed % 100) <= work->upd_prob);
372 seed = next_rand(seed);
373 size_t elem_idx = seed % work->elem_cnt;
374
375 ++loops;
376 if (0 == loops % (1024 * 1024)) {
377 /* Make the most current work->stop visible. */
378 read_barrier();
379 TPRINTF("*");
380 }
381
382 if (upd) {
383 seed = next_rand(seed);
384 bool item_op = seed & 1;
385
386 if (work->elem[elem_idx].inserted) {
387 if (item_op) {
388 cht_remove_item(work->h, &work->elem[elem_idx].link);
389 } else {
390 void *key = (void*)work->elem[elem_idx].key;
391 if (1 != cht_remove_key(work->h, key)) {
392 TPRINTF("Err: did not rm the key\n");
393 work->failed = true;
394 }
395 }
396 work->elem[elem_idx].inserted = false;
397 } else if (work->elem[elem_idx].deleted){
398 work->elem[elem_idx].deleted = false;
399
400 if (item_op) {
401 if (!cht_insert_unique(work->h, &work->elem[elem_idx].link)) {
402 TPRINTF("Err: already inserted\n");
403 work->failed = true;
404 }
405 } else {
406 cht_insert(work->h, &work->elem[elem_idx].link);
407 }
408
409 work->elem[elem_idx].inserted = true;
410 }
411 } else {
412 rcu_read_lock();
413 cht_link_t *item =
414 cht_find(work->h, (void*)work->elem[elem_idx].key);
415 rcu_read_unlock();
416
417 if (item) {
418 if (!work->elem[elem_idx].inserted) {
419 TPRINTF("Err: found but not inserted!");
420 work->failed = true;
421 }
422 if (item != &work->elem[elem_idx].link) {
423 TPRINTF("Err: found but incorrect item\n");
424 work->failed = true;
425 }
426 } else {
427 if (work->elem[elem_idx].inserted) {
428 TPRINTF("Err: inserted but not found!");
429 work->failed = true;
430 }
431 }
432 }
433 }
434
435
436 /* Remove anything we may have inserted. */
437 for (size_t i = 0; i < work->elem_cnt; ++i) {
438 void *key = (void*) work->elem[i].key;
439 cht_remove_key(work->h, key);
440 }
441}
442
443static bool do_stress(void)
444{
445 cht_t h;
446
447 if (!cht_create(&h, 0, 0, 0, &stress_ops)) {
448 TPRINTF("Failed to create the table\n");
449 return false;
450 }
451
452 const size_t wave_cnt = 10;
453 const size_t max_thread_cnt = 8;
454 const size_t resize_thread_cnt = 2;
455 size_t op_thread_cnt = min(max_thread_cnt, 2 * config.cpu_active);
456 size_t total_thr_cnt = op_thread_cnt + resize_thread_cnt;
457 size_t items_per_thread = 1024;
458
459 size_t work_cnt = op_thread_cnt + resize_thread_cnt;
460 size_t item_cnt = op_thread_cnt * items_per_thread;
461
462 /* Alloc hash table items. */
463 size_t size = item_cnt * sizeof(stress_t) + work_cnt * sizeof(stress_work_t)
464 + sizeof(int);
465
466 TPRINTF("Alloc and init table items. \n");
467 void *p = malloc(size, FRAME_ATOMIC);
468 if (!p) {
469 TPRINTF("Failed to alloc items\n");
470 cht_destroy(&h);
471 return false;
472 }
473
474 stress_t *pitem = p + work_cnt * sizeof(stress_work_t);
475 stress_work_t *pwork = p;
476 int *pstop = (int*)(pitem + item_cnt);
477
478 *pstop = 0;
479
480 /* Init work items. */
481 for (size_t i = 0; i < op_thread_cnt; ++i) {
482 pwork[i].h = &h;
483 pwork[i].stop = pstop;
484 pwork[i].elem = &pitem[i * items_per_thread];
485 pwork[i].upd_prob = (i + 1) * 100 / op_thread_cnt;
486 pwork[i].id = i;
487 pwork[i].elem_cnt = items_per_thread;
488 pwork[i].failed = false;
489 }
490
491 for (size_t i = op_thread_cnt; i < op_thread_cnt + resize_thread_cnt; ++i) {
492 pwork[i].h = &h;
493 pwork[i].stop = pstop;
494 pwork[i].wave_cnt = wave_cnt;
495 pwork[i].wave_elems = item_cnt * 4;
496 pwork[i].id = i;
497 pwork[i].failed = false;
498 }
499
500 /* Init table elements. */
501 for (size_t k = 0; k < op_thread_cnt; ++k) {
502 for (size_t i = 0; i < items_per_thread; ++i) {
503 pwork[k].elem[i].key = (i << 8) + k;
504 pwork[k].elem[i].free = false;
505 pwork[k].elem[i].inserted = false;
506 pwork[k].elem[i].deleted = true;
507 }
508 }
509
510 TPRINTF("Running %zu ins/del/find stress threads + %zu resizers.\n",
511 op_thread_cnt, resize_thread_cnt);
512
513 /* Create and run threads. */
514 thread_t *thr[max_thread_cnt + resize_thread_cnt];
515
516 for (size_t i = 0; i < total_thr_cnt; ++i) {
517 if (i < op_thread_cnt)
518 thr[i] = thread_create(op_stresser, &pwork[i], TASK, 0, "cht-op-stress");
519 else
520 thr[i] = thread_create(resize_stresser, &pwork[i], TASK, 0, "cht-resize");
521
522 ASSERT(thr[i]);
523 thread_wire(thr[i], &cpus[i % config.cpu_active]);
524 thread_ready(thr[i]);
525 }
526
527 bool failed = false;
528
529 /* Wait for all threads to return. */
530 TPRINTF("Joining resize stressers.\n");
531 for (size_t i = op_thread_cnt; i < total_thr_cnt; ++i) {
532 thread_join(thr[i]);
533 failed = pwork[i].failed || failed;
534 }
535
536 TPRINTF("Joining op stressers.\n");
537 for (int i = (int)op_thread_cnt - 1; i >= 0; --i) {
538 TPRINTF("%d threads remain\n", i);
539 thread_join(thr[i]);
540 failed = pwork[i].failed || failed;
541 }
542
543 cht_destroy(&h);
544 free(p);
545
546 return !failed;
547}
548
549/*-------------------------------------------------------------------*/
550
551
552const char *test_cht1(void)
553{
554 const char *err = sanity_test();
555 if (err)
556 return err;
557
558 if (!do_stress())
559 return "CHT stress test failed.";
560 else
561 return 0;
562}
Note: See TracBrowser for help on using the repository browser.