projects / userspace-rcu.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
RCU Judy Array (rcuja) implementation
[userspace-rcu.git] / tests / regression / test_urcu_ja.c
CommitLineData
db61f215
MD		 1/*
2 * test_urcu_ja.c
3 *
4 * Userspace RCU library - test program
5 *
6 * Copyright 2009-2012 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 */
22
23#include "test_urcu_ja.h"
24#include "../common/debug-yield.h"
25#include <inttypes.h>
26#include <stdint.h>
27
28DEFINE_URCU_TLS(unsigned int, rand_lookup);
29DEFINE_URCU_TLS(unsigned long, nr_add);
30DEFINE_URCU_TLS(unsigned long, nr_addexist);
31DEFINE_URCU_TLS(unsigned long, nr_del);
32DEFINE_URCU_TLS(unsigned long, nr_delnoent);
33DEFINE_URCU_TLS(unsigned long, lookup_fail);
34DEFINE_URCU_TLS(unsigned long, lookup_ok);
35
36struct cds_ja *test_ja;
37
38volatile int test_go, test_stop;
39
40unsigned long wdelay;
41
42unsigned long duration;
43
44/* read-side C.S. duration, in loops */
45unsigned long rduration;
46
47unsigned long init_populate;
48int add_only;
49
50unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
51unsigned long init_pool_size = DEFAULT_RAND_POOL,
52 lookup_pool_size = DEFAULT_RAND_POOL,
53 write_pool_size = DEFAULT_RAND_POOL;
54int validate_lookup;
55int sanity_test;
56unsigned int key_bits = 32;
57
58int count_pipe[2];
59
60int verbose_mode;
61
62unsigned int cpu_affinities[NR_CPUS];
63unsigned int next_aff = 0;
64int use_affinity = 0;
65
66pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;
67
68DEFINE_URCU_TLS(unsigned long long, nr_writes);
69DEFINE_URCU_TLS(unsigned long long, nr_reads);
70
71unsigned int nr_readers;
72unsigned int nr_writers;
73
74static unsigned int add_ratio = 50;
75static uint64_t key_mul = 1ULL;
76
77static int add_unique, add_replace;
78
79static pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
80
81static int leak_detection;
82static unsigned long test_nodes_allocated, test_nodes_freed;
83
84void set_affinity(void)
85{
86 cpu_set_t mask;
87 int cpu;
88 int ret;
89
90 if (!use_affinity)
91 return;
92
93#if HAVE_SCHED_SETAFFINITY
94 ret = pthread_mutex_lock(&affinity_mutex);
95 if (ret) {
96 perror("Error in pthread mutex lock");
97 exit(-1);
98 }
99 cpu = cpu_affinities[next_aff++];
100 ret = pthread_mutex_unlock(&affinity_mutex);
101 if (ret) {
102 perror("Error in pthread mutex unlock");
103 exit(-1);
104 }
105 CPU_ZERO(&mask);
106 CPU_SET(cpu, &mask);
107#if SCHED_SETAFFINITY_ARGS == 2
108 sched_setaffinity(0, &mask);
109#else
110 sched_setaffinity(0, sizeof(mask), &mask);
111#endif
112#endif /* HAVE_SCHED_SETAFFINITY */
113}
114
115void rcu_copy_mutex_lock(void)
116{
117 int ret;
118 ret = pthread_mutex_lock(&rcu_copy_mutex);
119 if (ret) {
120 perror("Error in pthread mutex lock");
121 exit(-1);
122 }
123}
124
125void rcu_copy_mutex_unlock(void)
126{
127 int ret;
128
129 ret = pthread_mutex_unlock(&rcu_copy_mutex);
130 if (ret) {
131 perror("Error in pthread mutex unlock");
132 exit(-1);
133 }
134}
135
136static
137struct ja_test_node *node_alloc(void)
138{
139 struct ja_test_node *node;
140
141 node = calloc(sizeof(*node), 1);
142 if (leak_detection && node)
143 uatomic_inc(&test_nodes_allocated);
144 return node;
145}
146
147static
148void free_test_node(struct ja_test_node *node)
149{
150 poison_free(node);
151 if (leak_detection)
152 uatomic_inc(&test_nodes_freed);
153}
154
155static
156void free_test_node_cb(struct rcu_head *head)
157{
158 struct ja_test_node *node =
159 caa_container_of(head, struct ja_test_node, head);
160 free_test_node(node);
161}
162
163static
164void rcu_free_test_node(struct ja_test_node *test_node)
165{
166 call_rcu(&test_node->head, free_test_node_cb);
167}
168
169static
170void free_node(struct cds_ja_node *node)
171{
172 struct ja_test_node *test_node = to_test_node(node);
173
174 free_test_node(test_node);
175}
176
177#if 0
178static
179void test_delete_all_nodes(struct cds_lfht *ht)
180{
181 struct cds_lfht_iter iter;
182 struct lfht_test_node *node;
183 unsigned long count = 0;
184
185 cds_lfht_for_each_entry(ht, &iter, node, node) {
186 int ret;
187
188 ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter));
189 assert(!ret);
190 call_rcu(&node->head, free_node_cb);
191 count++;
192 }
193 printf("deleted %lu nodes.\n", count);
194}
195#endif
196
197void show_usage(int argc, char **argv)
198{
199 printf("Usage : %s nr_readers nr_writers duration (s)\n", argv[0]);
200#ifdef DEBUG_YIELD
201 printf(" [-r] [-w] (yield reader and/or writer)\n");
202#endif
203 printf(" [-d delay] (writer period (us))\n");
204 printf(" [-c duration] (reader C.S. duration (in loops))\n");
205 printf(" [-v] (verbose output)\n");
206 printf(" [-a cpu#] [-a cpu#]... (affinity)\n");
207 printf(" [-u] Add unique keys.\n");
208 printf(" [-s] Replace existing keys.\n");
209printf(" [not -u nor -s] Add entries (supports redundant keys).\n");
210 printf(" [-r ratio] Add ratio (in %% of add+removal).\n");
211 printf(" [-k] Populate init nodes.\n");
212 printf(" [-R offset] Lookup pool offset.\n");
213 printf(" [-S offset] Write pool offset.\n");
214 printf(" [-T offset] Init pool offset.\n");
215 printf(" [-M size] Lookup pool size.\n");
216 printf(" [-N size] Write pool size.\n");
217 printf(" [-O size] Init pool size.\n");
218 printf(" [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
219 printf(" [-t] Do sanity test.\n");
220 printf(" [-B] Key bits for multithread test (default: 32).\n");
221 printf(" [-m factor] Key multiplication factor.\n");
222 printf(" [-l] Memory leak detection.\n");
223 printf("\n\n");
224}
225
226static
227int test_free_all_nodes(struct cds_ja *ja)
228{
229 uint64_t key;
230 struct cds_ja_node *ja_node;
231 int ret = 0;
232
233 rcu_read_lock();
234 cds_ja_for_each_key_rcu(test_ja, key, ja_node) {
235 struct cds_ja_node *tmp_node;
236
237 cds_ja_for_each_duplicate_safe_rcu(ja_node, tmp_node) {
238 ret = cds_ja_del(test_ja, key, ja_node);
239 if (ret) {
240 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
241 goto end;
242 }
243 /* Alone using Judy array, OK to free now */
244 free_node(ja_node);
245 }
246 }
247end:
248 rcu_read_unlock();
249 return ret;
250}
251
252static
253int test_8bit_key(void)
254{
255 int ret, i;
256 uint64_t key;
257 uint64_t ka[] = { 5, 17, 100, 222 };
258 uint64_t ka_test_offset = 5;
259 struct cds_ja_node *ja_node;
260
261 /* Test with 8-bit key */
262 test_ja = cds_ja_new(8);
263 if (!test_ja) {
264 printf("Error allocating judy array.\n");
265 return -1;
266 }
267
268 /* Add keys */
269 printf("Test #1: add keys (8-bit).\n");
270 for (key = 0; key < 200; key++) {
271 struct ja_test_node *node = node_alloc();
272
273 ja_test_node_init(node, key);
274 rcu_read_lock();
275 ret = cds_ja_add(test_ja, key, &node->node);
276 rcu_read_unlock();
277 if (ret) {
278 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
279 ret, key);
280 assert(0);
281 }
282 }
283 printf("OK\n");
284
285 printf("Test #2: successful key lookup (8-bit).\n");
286 for (key = 0; key < 200; key++) {
287 rcu_read_lock();
288 ja_node = cds_ja_lookup(test_ja, key);
289 if (!ja_node) {
290 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
291 assert(0);
292 }
293 rcu_read_unlock();
294 }
295 printf("OK\n");
296 printf("Test #3: unsuccessful key lookup (8-bit).\n");
297 for (key = 200; key < 240; key++) {
298 rcu_read_lock();
299 ja_node = cds_ja_lookup(test_ja, key);
300 if (ja_node) {
301 fprintf(stderr,
302 "Error unexpected lookup node %" PRIu64 "\n",
303 key);
304 assert(0);
305 }
306 rcu_read_unlock();
307 }
308 printf("OK\n");
309 printf("Test #4: remove keys (8-bit).\n");
310 for (key = 0; key < 200; key++) {
311 struct ja_test_node *node;
312
313 rcu_read_lock();
314 ja_node = cds_ja_lookup(test_ja, key);
315 if (!ja_node) {
316 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
317 assert(0);
318 }
319 node = caa_container_of(ja_node, struct ja_test_node, node);
320 ret = cds_ja_del(test_ja, key, &node->node);
321 if (ret) {
322 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
323 assert(0);
324 }
325 rcu_free_test_node(node);
326 ja_node = cds_ja_lookup(test_ja, key);
327 if (ja_node) {
328 fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
329 assert(0);
330 }
331 rcu_read_unlock();
332 }
333 printf("OK\n");
334
335 printf("Test #5: lookup below/above equal (8-bit).\n");
336
337 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
338 struct ja_test_node *node = node_alloc();
339
340 key = ka[i];
341 ja_test_node_init(node, key);
342 rcu_read_lock();
343 ret = cds_ja_add(test_ja, key, &node->node);
344 rcu_read_unlock();
345 if (ret) {
346 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
347 ret, key);
348 assert(0);
349 }
350 }
351
352 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
353 struct ja_test_node *node;
354 uint64_t result_key;
355
356 key = ka[i] + ka_test_offset;
357 rcu_read_lock();
358 ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key);
359 if (!ja_node) {
360 fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
361 ka[i], key);
362 assert(0);
363 }
364 node = caa_container_of(ja_node, struct ja_test_node, node);
365 if (node->key != ka[i] || result_key != ka[i]) {
366 fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
367 ka[i], key, node->key, result_key);
368 assert(0);
369 }
370 rcu_read_unlock();
371 }
372
373 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
374 struct ja_test_node *node;
375 uint64_t result_key;
376
377 key = ka[i] - ka_test_offset;
378 rcu_read_lock();
379 ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key);
380 if (!ja_node) {
381 fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
382 ka[i], key);
383 assert(0);
384 }
385 node = caa_container_of(ja_node, struct ja_test_node, node);
386 if (node->key != ka[i] || result_key != ka[i]) {
387 fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
388 ka[i], key, node->key, result_key);
389 assert(0);
390 }
391 rcu_read_unlock();
392 }
393
394 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
395 struct ja_test_node *node;
396 uint64_t result_key;
397
398 key = ka[i]; /* without offset */
399 rcu_read_lock();
400 ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key);
401 if (!ja_node) {
402 fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
403 ka[i], key);
404 assert(0);
405 }
406 node = caa_container_of(ja_node, struct ja_test_node, node);
407 if (node->key != ka[i] || result_key != ka[i]) {
408 fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
409 ka[i], key, node->key, result_key);
410 assert(0);
411 }
412
413 ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key);
414 if (!ja_node) {
415 fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
416 ka[i], key);
417 assert(0);
418 }
419 node = caa_container_of(ja_node, struct ja_test_node, node);
420 if (node->key != ka[i] || result_key != ka[i]) {
421 fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
422 ka[i], key, node->key, result_key);
423 assert(0);
424 }
425 rcu_read_unlock();
426 }
427
428 printf("OK\n");
429
430 ret = test_free_all_nodes(test_ja);
431 if (ret) {
432 fprintf(stderr, "Error freeing all nodes\n");
433 return -1;
434 }
435
436 ret = cds_ja_destroy(test_ja);
437 if (ret) {
438 fprintf(stderr, "Error destroying judy array\n");
439 return -1;
440 }
441 return 0;
442}
443
444static
445int test_16bit_key(void)
446{
447 int ret, i;
448 uint64_t key;
449 uint64_t ka[] = { 105, 206, 4000, 4111, 59990, 65435 };
450 uint64_t ka_test_offset = 100;
451 struct cds_ja_node *ja_node;
452
453 /* Test with 16-bit key */
454 test_ja = cds_ja_new(16);
455 if (!test_ja) {
456 printf("Error allocating judy array.\n");
457 return -1;
458 }
459
460 /* Add keys */
461 printf("Test #1: add keys (16-bit).\n");
462 for (key = 0; key < 10000; key++) {
463 //for (key = 0; key < 65536; key+=256) {
464 struct ja_test_node *node = node_alloc();
465
466 ja_test_node_init(node, key);
467 rcu_read_lock();
468 ret = cds_ja_add(test_ja, key, &node->node);
469 rcu_read_unlock();
470 if (ret) {
471 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
472 ret, key);
473 assert(0);
474 }
475 }
476 printf("OK\n");
477
478 printf("Test #2: successful key lookup (16-bit).\n");
479 for (key = 0; key < 10000; key++) {
480 //for (key = 0; key < 65536; key+=256) {
481 struct cds_ja_node *ja_node;
482
483 rcu_read_lock();
484 ja_node = cds_ja_lookup(test_ja, key);
485 if (!ja_node) {
486 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
487 assert(0);
488 }
489 rcu_read_unlock();
490 }
491 printf("OK\n");
492 printf("Test #3: unsuccessful key lookup (16-bit).\n");
493 for (key = 11000; key <= 11002; key++) {
494 struct cds_ja_node *ja_node;
495
496 rcu_read_lock();
497 ja_node = cds_ja_lookup(test_ja, key);
498 if (ja_node) {
499 fprintf(stderr,
500 "Error unexpected lookup node %" PRIu64 "\n",
501 key);
502 assert(0);
503 }
504 rcu_read_unlock();
505 }
506 printf("OK\n");
507 printf("Test #4: remove keys (16-bit).\n");
508 for (key = 0; key < 10000; key++) {
509 //for (key = 0; key < 65536; key+=256) {
510 struct ja_test_node *node;
511
512 rcu_read_lock();
513 ja_node = cds_ja_lookup(test_ja, key);
514 if (!ja_node) {
515 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
516 assert(0);
517 }
518 node = caa_container_of(ja_node, struct ja_test_node, node);
519 ret = cds_ja_del(test_ja, key, &node->node);
520 if (ret) {
521 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
522 assert(0);
523 }
524 rcu_free_test_node(node);
525 ja_node = cds_ja_lookup(test_ja, key);
526 if (ja_node) {
527 fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
528 assert(0);
529 }
530 rcu_read_unlock();
531 }
532 printf("OK\n");
533
534 printf("Test #5: lookup below/above equal (16-bit).\n");
535
536 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
537 struct ja_test_node *node = node_alloc();
538
539 key = ka[i];
540 ja_test_node_init(node, key);
541 rcu_read_lock();
542 ret = cds_ja_add(test_ja, key, &node->node);
543 rcu_read_unlock();
544 if (ret) {
545 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
546 ret, key);
547 assert(0);
548 }
549 }
550
551 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
552 struct ja_test_node *node;
553 uint64_t result_key;
554
555 key = ka[i] + ka_test_offset;
556 rcu_read_lock();
557 ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key);
558 if (!ja_node) {
559 fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
560 ka[i], key);
561 assert(0);
562 }
563 node = caa_container_of(ja_node, struct ja_test_node, node);
564 if (node->key != ka[i] || result_key != ka[i]) {
565 fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
566 ka[i], key, node->key, result_key);
567 assert(0);
568 }
569 rcu_read_unlock();
570 }
571
572 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
573 struct ja_test_node *node;
574 uint64_t result_key;
575
576 key = ka[i] - ka_test_offset;
577 rcu_read_lock();
578 ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key);
579 if (!ja_node) {
580 fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n",
581 ka[i], key);
582 assert(0);
583 }
584 node = caa_container_of(ja_node, struct ja_test_node, node);
585 if (node->key != ka[i] || result_key != ka[i]) {
586 fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
587 ka[i], key, node->key, result_key);
588 assert(0);
589 }
590 rcu_read_unlock();
591 }
592
593 for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
594 struct ja_test_node *node;
595 uint64_t result_key;
596
597 key = ka[i]; /* without offset */
598 rcu_read_lock();
599 ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key);
600 if (!ja_node) {
601 fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
602 ka[i], key);
603 assert(0);
604 }
605 node = caa_container_of(ja_node, struct ja_test_node, node);
606 if (node->key != ka[i] || result_key != ka[i]) {
607 fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
608 ka[i], key, node->key, result_key);
609 assert(0);
610 }
611
612 ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key);
613 if (!ja_node) {
614 fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n",
615 ka[i], key);
616 assert(0);
617 }
618 node = caa_container_of(ja_node, struct ja_test_node, node);
619 if (node->key != ka[i] || result_key != ka[i]) {
620 fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n",
621 ka[i], key, node->key, result_key);
622 assert(0);
623 }
624 rcu_read_unlock();
625 }
626
627 printf("OK\n");
628
629 ret = test_free_all_nodes(test_ja);
630 if (ret) {
631 fprintf(stderr, "Error freeing all nodes\n");
632 return -1;
633 }
634
635 ret = cds_ja_destroy(test_ja);
636 if (ret) {
637 fprintf(stderr, "Error destroying judy array\n");
638 return -1;
639 }
640 return 0;
641}
642
643/*
644 * nr_dup is number of nodes per key.
645 */
646static
647int test_sparse_key(unsigned int bits, int nr_dup)
648{
649 uint64_t key, max_key;
650 int zerocount, i, ret;
651 struct cds_ja_node *ja_node;
652
653 if (bits == 64)
654 max_key = UINT64_MAX;
655 else
656 max_key = (1ULL << bits) - 1;
657
658 printf("Sparse key test begins for %u-bit keys\n", bits);
659 /* Test with 16-bit key */
660 test_ja = cds_ja_new(bits);
661 if (!test_ja) {
662 printf("Error allocating judy array.\n");
663 return -1;
664 }
665
666 /* Add keys */
667 printf("Test #1: add keys (%u-bit).\n", bits);
668 for (i = 0; i < nr_dup; i++) {
669 zerocount = 0;
670 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
671 struct ja_test_node *node = node_alloc();
672
673 ja_test_node_init(node, key);
674 rcu_read_lock();
675 ret = cds_ja_add(test_ja, key, &node->node);
676 rcu_read_unlock();
677 if (ret) {
678 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
679 ret, key);
680 assert(0);
681 }
682 if (key == 0)
683 zerocount++;
684 }
685 }
686 printf("OK\n");
687
688 printf("Test #2: successful key lookup (%u-bit).\n", bits);
689 zerocount = 0;
690 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
691 struct ja_test_node *node;
692 int count = 0;
693
694 rcu_read_lock();
695 ja_node = cds_ja_lookup(test_ja, key);
696 if (!ja_node) {
697 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
698 assert(0);
699 }
700 cds_ja_for_each_duplicate_rcu(ja_node) {
701 count++;
702 }
703 if (count != nr_dup) {
704 fprintf(stderr, "Unexpected number of match for key %" PRIu64 ", expected %d, got %d.\n", key, nr_dup, count);
705 }
706 rcu_read_unlock();
707 if (key == 0)
708 zerocount++;
709 }
710 printf("OK\n");
711 if (bits > 8) {
712 printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits);
713 zerocount = 0;
714 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
715 rcu_read_lock();
716 ja_node = cds_ja_lookup(test_ja, key + 42);
717 if (ja_node) {
718 fprintf(stderr,
719 "Error unexpected lookup node %" PRIu64 "\n",
720 key + 42);
721 assert(0);
722 }
723 rcu_read_unlock();
724 if (key == 0)
725 zerocount++;
726 }
727 printf("OK\n");
728 }
729 printf("Test #4: remove keys (%u-bit).\n", bits);
730 zerocount = 0;
731 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
732 int count = 0;
733
734 rcu_read_lock();
735 ja_node = cds_ja_lookup(test_ja, key);
736
737 cds_ja_for_each_duplicate_rcu(ja_node) {
738 struct cds_ja_node *test_ja_node;
739 struct ja_test_node *node;
740
741 count++;
742 node = caa_container_of(ja_node,
743 struct ja_test_node, node);
744 ret = cds_ja_del(test_ja, key, &node->node);
745 if (ret) {
746 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
747 assert(0);
748 }
749 rcu_free_test_node(node);
750 test_ja_node = cds_ja_lookup(test_ja, key);
751 if (count < nr_dup && !test_ja_node) {
752 fprintf(stderr, "Error: no node found after deletion of some nodes of a key\n");
753 assert(0);
754 }
755 }
756 ja_node = cds_ja_lookup(test_ja, key);
757 if (ja_node) {
758 fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
759 assert(0);
760 }
761 rcu_read_unlock();
762 if (key == 0)
763 zerocount++;
764 }
765 printf("OK\n");
766
767 ret = test_free_all_nodes(test_ja);
768 if (ret) {
769 fprintf(stderr, "Error freeing all nodes\n");
770 return -1;
771 }
772
773 ret = cds_ja_destroy(test_ja);
774 if (ret) {
775 fprintf(stderr, "Error destroying judy array\n");
776 return -1;
777 }
778 printf("Test ends\n");
779
780 return 0;
781}
782
783static
784int do_sanity_test(void)
785{
786 int i, j, ret;
787
788 printf("Sanity test start.\n");
789
790 for (i = 0; i < 3; i++) {
791 ret = test_8bit_key();
792 if (ret) {
793 return ret;
794 }
795 rcu_quiescent_state();
796 }
797 ret = test_16bit_key();
798 if (ret) {
799 return ret;
800 }
801 rcu_quiescent_state();
802
803 /* key bits */
804 for (i = 8; i <= 64; i *= 2) {
805 /* nr of nodes per key */
806 for (j = 1; j < 4; j++) {
807 ret = test_sparse_key(i, j);
808 if (ret) {
809 return ret;
810 }
811 rcu_quiescent_state();
812 }
813 }
814 printf("Sanity test end.\n");
815
816 return 0;
817}
818
819enum urcu_ja_addremove {
820 AR_RANDOM = 0,
821 AR_ADD = 1,
822 AR_REMOVE = -1,
823}; /* 1: add, -1 remove, 0: random */
824
825static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
826
827static
828void test_ja_rw_sigusr1_handler(int signo)
829{
830 switch (addremove) {
831 case AR_ADD:
832 printf("Add/Remove: random.\n");
833 addremove = AR_RANDOM;
834 break;
835 case AR_RANDOM:
836 printf("Add/Remove: remove only.\n");
837 addremove = AR_REMOVE;
838 break;
839 case AR_REMOVE:
840 printf("Add/Remove: add only.\n");
841 addremove = AR_ADD;
842 break;
843 }
844}
845
846static
847void *test_ja_rw_thr_reader(void *_count)
848{
849 unsigned long long *count = _count;
850 struct cds_ja_node *ja_node;
851 uint64_t key;
852
853 printf_verbose("thread_begin %s, tid %lu\n",
854 "reader", urcu_get_thread_id());
855
856 URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);
857
858 set_affinity();
859
860 rcu_register_thread();
861
862 while (!test_go)
863 {
864 }
865 cmm_smp_mb();
866
867 for (;;) {
868 rcu_read_lock();
869
870 /* note: only looking up ulong keys */
871 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
872 key *= key_mul;
873 ja_node = cds_ja_lookup(test_ja, key);
874 if (!ja_node) {
875 if (validate_lookup) {
876 printf("[ERROR] Lookup cannot find initial node.\n");
877 exit(-1);
878 }
879 URCU_TLS(lookup_fail)++;
880 } else {
881 URCU_TLS(lookup_ok)++;
882 }
883 rcu_debug_yield_read();
884 if (caa_unlikely(rduration))
885 loop_sleep(rduration);
886 rcu_read_unlock();
887 URCU_TLS(nr_reads)++;
888 if (caa_unlikely(!test_duration_read()))
889 break;
890 if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
891 rcu_quiescent_state();
892 }
893
894 rcu_unregister_thread();
895
896 *count = URCU_TLS(nr_reads);
897 printf_verbose("thread_end %s, tid %lu\n",
898 "reader", urcu_get_thread_id());
899 printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
900 pthread_self(), URCU_TLS(lookup_fail),
901 URCU_TLS(lookup_ok));
902 return ((void*)1);
903}
904
905static
906int is_add(void)
907{
908 return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
909}
910
911static
912void *test_ja_rw_thr_writer(void *_count)
913{
914 struct wr_count *count = _count;
915 uint64_t key;
916 int ret;
917
918 printf_verbose("thread_begin %s, tid %lu\n",
919 "writer", urcu_get_thread_id());
920
921 URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL);
922
923 set_affinity();
924
925 rcu_register_thread();
926
927 while (!test_go)
928 {
929 }
930 cmm_smp_mb();
931
932 for (;;) {
933 if ((addremove == AR_ADD)
934 || (addremove == AR_RANDOM && is_add())) {
935 struct ja_test_node *node = node_alloc();
936 struct cds_ja_node *ret_node;
937
938 /* note: only inserting ulong keys */
939 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
940 key *= key_mul;
941 ja_test_node_init(node, key);
942 rcu_read_lock();
943 if (add_unique) {
944 ret_node = cds_ja_add_unique(test_ja, key, &node->node);
945 if (ret_node != &node->node) {
946 free_test_node(node);
947 URCU_TLS(nr_addexist)++;
948 } else {
949 URCU_TLS(nr_add)++;
950 }
951 } else if (add_replace) {
952 assert(0); /* not implemented yet. */
953 } else {
954 ret = cds_ja_add(test_ja, key, &node->node);
955 if (ret) {
956 fprintf(stderr, "Error in cds_ja_add: %d\n", ret);
957 free_test_node(node);
958 } else {
959 URCU_TLS(nr_add)++;
960 }
961 }
962 rcu_read_unlock();
963 } else {
964 struct cds_ja_node *ja_node;
965 struct ja_test_node *node;
966
967 /* May delete */
968 /* note: only deleting ulong keys */
969 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
970 key *= key_mul;
971
972 rcu_read_lock();
973
974 ja_node = cds_ja_lookup(test_ja, key);
975 /* Remove first entry */
976 if (ja_node) {
977 node = caa_container_of(ja_node,
978 struct ja_test_node, node);
979 ret = cds_ja_del(test_ja, key, &node->node);
980 if (!ret) {
981 rcu_free_test_node(node);
982 URCU_TLS(nr_del)++;
983 } else {
984 URCU_TLS(nr_delnoent)++;
985 }
986 } else {
987 URCU_TLS(nr_delnoent)++;
988 }
989 rcu_read_unlock();
990 }
991
992 URCU_TLS(nr_writes)++;
993 if (caa_unlikely(!test_duration_write()))
994 break;
995 if (caa_unlikely(wdelay))
996 loop_sleep(wdelay);
997 if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
998 rcu_quiescent_state();
999 }
1000
1001 rcu_unregister_thread();
1002
1003 printf_verbose("thread_end %s, tid %lu\n",
1004 "writer", urcu_get_thread_id());
1005 printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
1006 "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
1007 URCU_TLS(nr_addexist), URCU_TLS(nr_del),
1008 URCU_TLS(nr_delnoent));
1009 count->update_ops = URCU_TLS(nr_writes);
1010 count->add = URCU_TLS(nr_add);
1011 count->add_exist = URCU_TLS(nr_addexist);
1012 count->remove = URCU_TLS(nr_del);
1013 return ((void*)2);
1014}
1015
1016static
1017int do_mt_populate_ja(void)
1018{
1019 uint64_t iter;
1020 int ret;
1021
1022 if (!init_populate)
1023 return 0;
1024
1025 printf("Starting rw test\n");
1026
1027 for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
1028 struct ja_test_node *node = node_alloc();
1029 uint64_t key;
1030
1031 /* note: only inserting ulong keys */
1032 key = (unsigned long) iter;
1033 key *= key_mul;
1034 ja_test_node_init(node, key);
1035 rcu_read_lock();
1036 ret = cds_ja_add(test_ja, key, &node->node);
1037 URCU_TLS(nr_add)++;
1038 URCU_TLS(nr_writes)++;
1039 rcu_read_unlock();
1040 /* Hash table resize only occurs in call_rcu thread */
1041 if (!(iter % 100))
1042 rcu_quiescent_state();
1043 if (ret) {
1044 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
1045 ret, key);
1046 assert(0);
1047 }
1048 }
1049 return 0;
1050}
1051
1052static
1053int do_mt_test(void)
1054{
1055 pthread_t *tid_reader, *tid_writer;
1056 void *tret;
1057 int ret, i, err;
1058 unsigned long long *count_reader;
1059 struct wr_count *count_writer;
1060 unsigned long long tot_reads = 0, tot_writes = 0,
1061 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
1062 unsigned int remain;
1063
1064 tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
1065 tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
1066 count_reader = malloc(sizeof(*count_reader) * nr_readers);
1067 count_writer = malloc(sizeof(*count_writer) * nr_writers);
1068
1069 printf("Allocating Judy Array for %u-bit keys\n", key_bits);
1070 test_ja = cds_ja_new(key_bits);
1071 if (!test_ja) {
1072 printf("Error allocating judy array.\n");
1073 ret = -1;
1074 goto end;
1075 }
1076
1077 do_mt_populate_ja();
1078
1079 next_aff = 0;
1080
1081 for (i = 0; i < nr_readers; i++) {
1082 err = pthread_create(&tid_reader[i],
1083 NULL, test_ja_rw_thr_reader,
1084 &count_reader[i]);
1085 if (err != 0)
1086 exit(1);
1087 }
1088 for (i = 0; i < nr_writers; i++) {
1089 err = pthread_create(&tid_writer[i],
1090 NULL, test_ja_rw_thr_writer,
1091 &count_writer[i]);
1092 if (err != 0)
1093 exit(1);
1094 }
1095
1096 cmm_smp_mb();
1097
1098 test_go = 1;
1099
1100 rcu_thread_offline_qsbr();
1101
1102 remain = duration;
1103 do {
1104 remain = sleep(remain);
1105 } while (remain > 0);
1106
1107 test_stop = 1;
1108
1109 for (i = 0; i < nr_readers; i++) {
1110 err = pthread_join(tid_reader[i], &tret);
1111 if (err != 0)
1112 exit(1);
1113 tot_reads += count_reader[i];
1114 }
1115 for (i = 0; i < nr_writers; i++) {
1116 err = pthread_join(tid_writer[i], &tret);
1117 if (err != 0)
1118 exit(1);
1119 tot_writes += count_writer[i].update_ops;
1120 tot_add += count_writer[i].add;
1121 tot_add_exist += count_writer[i].add_exist;
1122 tot_remove += count_writer[i].remove;
1123 }
1124 rcu_thread_online_qsbr();
1125
1126 ret = test_free_all_nodes(test_ja);
1127 if (ret) {
1128 fprintf(stderr, "Error freeing all nodes\n");
1129 return -1;
1130 }
1131
1132 ret = cds_ja_destroy(test_ja);
1133 if (ret) {
1134 fprintf(stderr, "Error destroying judy array\n");
1135 goto end;
1136 }
1137
1138 free(tid_reader);
1139 free(tid_writer);
1140 free(count_reader);
1141 free(count_writer);
1142 ret = 0;
1143end:
1144 return ret;
1145}
1146
1147static
1148int check_memory_leaks(void)
1149{
1150 unsigned long na, nf;
1151
1152 na = uatomic_read(&test_nodes_allocated);
1153 nf = uatomic_read(&test_nodes_freed);
1154 if (na != nf) {
1155 fprintf(stderr, "Memory leak of %ld test nodes detected. Allocated: %lu, freed: %lu\n",
1156 na - nf, na, nf);
1157 return -1;
1158 }
1159 return 0;
1160}
1161
1162int main(int argc, char **argv)
1163{
1164 int i, j, a, ret, err;
1165 uint64_t key;
1166 struct sigaction act;
1167
1168 if (argc < 4) {
1169 show_usage(argc, argv);
1170 return -1;
1171 }
1172
1173 err = sscanf(argv[1], "%u", &nr_readers);
1174 if (err != 1) {
1175 show_usage(argc, argv);
1176 return -1;
1177 }
1178
1179 err = sscanf(argv[2], "%u", &nr_writers);
1180 if (err != 1) {
1181 show_usage(argc, argv);
1182 return -1;
1183 }
1184
1185 err = sscanf(argv[3], "%lu", &duration);
1186 if (err != 1) {
1187 show_usage(argc, argv);
1188 return -1;
1189 }
1190
1191 for (i = 4; i < argc; i++) {
1192 if (argv[i][0] != '-')
1193 continue;
1194 switch (argv[i][1]) {
1195#ifdef DEBUG_YIELD
1196 case 'r':
1197 yield_active |= YIELD_READ;
1198 break;
1199 case 'w':
1200 yield_active |= YIELD_WRITE;
1201 break;
1202#endif
1203 case 'a':
1204 if (argc < i + 2) {
1205 show_usage(argc, argv);
1206 return -1;
1207 }
1208 a = atoi(argv[++i]);
1209 cpu_affinities[next_aff++] = a;
1210 use_affinity = 1;
1211 printf_verbose("Adding CPU %d affinity\n", a);
1212 break;
1213 case 'c':
1214 if (argc < i + 2) {
1215 show_usage(argc, argv);
1216 return -1;
1217 }
1218 rduration = atol(argv[++i]);
1219 break;
1220 case 'd':
1221 if (argc < i + 2) {
1222 show_usage(argc, argv);
1223 return -1;
1224 }
1225 wdelay = atol(argv[++i]);
1226 break;
1227 case 'v':
1228 verbose_mode = 1;
1229 break;
1230 case 'r':
1231 add_ratio = atoi(argv[++i]);
1232 break;
1233 case 'k':
1234 init_populate = 1;
1235 break;
1236 case 'R':
1237 lookup_pool_offset = atol(argv[++i]);
1238 break;
1239 case 'S':
1240 write_pool_offset = atol(argv[++i]);
1241 break;
1242 case 'T':
1243 init_pool_offset = atol(argv[++i]);
1244 break;
1245 case 'M':
1246 lookup_pool_size = atol(argv[++i]);
1247 break;
1248 case 'N':
1249 write_pool_size = atol(argv[++i]);
1250 break;
1251 case 'O':
1252 init_pool_size = atol(argv[++i]);
1253 break;
1254 case 'V':
1255 validate_lookup = 1;
1256 break;
1257 case 't':
1258 sanity_test = 1;
1259 break;
1260 case 'B':
1261 key_bits = atol(argv[++i]);
1262 break;
1263 case 'm':
1264 key_mul = atoll(argv[++i]);
1265 break;
1266 case 'u':
1267 add_unique = 1;
1268 break;
1269 case 's':
1270 add_replace = 1;
1271 break;
1272 case 'l':
1273 leak_detection = 1;
1274 break;
1275 }
1276 }
1277
1278 printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
1279 duration, nr_readers, nr_writers);
1280 printf_verbose("Writer delay : %lu loops.\n", wdelay);
1281 printf_verbose("Reader duration : %lu loops.\n", rduration);
1282 printf_verbose("Add ratio: %u%%.\n", add_ratio);
1283 printf_verbose("Mode:%s%s.\n",
1284 " add/remove",
1285 add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
1286 printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
1287 printf_verbose("Init pool size offset %lu size %lu.\n",
1288 init_pool_offset, init_pool_size);
1289 printf_verbose("Lookup pool size offset %lu size %lu.\n",
1290 lookup_pool_offset, lookup_pool_size);
1291 printf_verbose("Update pool size offset %lu size %lu.\n",
1292 write_pool_offset, write_pool_size);
1293 if (validate_lookup)
1294 printf_verbose("Validating lookups.\n");
1295 if (leak_detection)
1296 printf_verbose("Memory leak dection activated.\n");
1297 printf_verbose("thread %-6s, tid %lu\n",
1298 "main", urcu_get_thread_id());
1299
1300 memset(&act, 0, sizeof(act));
1301 ret = sigemptyset(&act.sa_mask);
1302 if (ret == -1) {
1303 perror("sigemptyset");
1304 return -1;
1305 }
1306 act.sa_handler = test_ja_rw_sigusr1_handler;
1307 act.sa_flags = SA_RESTART;
1308 ret = sigaction(SIGUSR1, &act, NULL);
1309 if (ret == -1) {
1310 perror("sigaction");
1311 return -1;
1312 }
1313
1314 err = create_all_cpu_call_rcu_data(0);
1315 if (err) {
1316 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
1317 }
1318
1319 rcu_register_thread();
1320
1321 if (sanity_test) {
1322 ret = do_sanity_test();
1323 } else {
1324 ret = do_mt_test();
1325 }
1326
1327 /* Wait for in-flight call_rcu free to complete for leak detection */
1328 rcu_barrier();
1329
1330 ret |= check_memory_leaks();
1331
1332 rcu_unregister_thread();
1333 free_all_cpu_call_rcu_data();
1334
1335 if (ret) {
1336 printf("Test ended with error: %d\n", ret);
1337 }
1338 return ret;
1339}
Userspace RCU (urcu) for Linux
This page took 0.069904 seconds and 4 git commands to generate.