projects / userspace-rcu.git / blob
? search:


8c7e7277019edfe33570e5e9df897eebbeff5f68
[userspace-rcu.git] / tests / test_urcu_ja.c
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 #define _GNU_SOURCE
24 #include "test_urcu_ja.h"
25 #include <inttypes.h>
26 #include <stdint.h>
27
28 DEFINE_URCU_TLS(unsigned int, rand_lookup);
29 DEFINE_URCU_TLS(unsigned long, nr_add);
30 DEFINE_URCU_TLS(unsigned long, nr_addexist);
31 DEFINE_URCU_TLS(unsigned long, nr_del);
32 DEFINE_URCU_TLS(unsigned long, nr_delnoent);
33 DEFINE_URCU_TLS(unsigned long, lookup_fail);
34 DEFINE_URCU_TLS(unsigned long, lookup_ok);
35
36 struct cds_ja *test_ja;
37
38 volatile int test_go, test_stop;
39
40 unsigned long wdelay;
41
42 unsigned long duration;
43
44 /* read-side C.S. duration, in loops */
45 unsigned long rduration;
46
47 unsigned long init_populate;
48 int add_only;
49
50 unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
51 unsigned long init_pool_size = DEFAULT_RAND_POOL,
52 lookup_pool_size = DEFAULT_RAND_POOL,
53 write_pool_size = DEFAULT_RAND_POOL;
54 int validate_lookup;
55 int sanity_test;
56 unsigned int key_bits = 32;
57
58 int count_pipe[2];
59
60 int verbose_mode;
61
62 unsigned int cpu_affinities[NR_CPUS];
63 unsigned int next_aff = 0;
64 int use_affinity = 0;
65
66 pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;
67
68 DEFINE_URCU_TLS(unsigned long long, nr_writes);
69 DEFINE_URCU_TLS(unsigned long long, nr_reads);
70
71 unsigned int nr_readers;
72 unsigned int nr_writers;
73
74 static unsigned int add_ratio = 50;
75 static uint64_t key_mul = 1ULL;
76
77 static int add_unique, add_replace;
78
79 static pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
80
81 static int leak_detection;
82 static unsigned long test_nodes_allocated, test_nodes_freed;
83
84 void 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
115 void 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
125 void 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
136 static
137 struct 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
147 static
148 void 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
155 static
156 void 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
163 static
164 void rcu_free_test_node(struct ja_test_node *test_node)
165 {
166 call_rcu(&test_node->head, free_test_node_cb);
167 }
168
169 static
170 void 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
178 static
179 void 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
197 void 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");
209 printf(" [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
226 static
227 int 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 }
247 end:
248 rcu_read_unlock();
249 return ret;
250 }
251
252 static
253 int 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
444 static
445 int 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 */
646 static
647 int 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
783 static
784 int 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
819 enum urcu_ja_addremove {
820 AR_RANDOM = 0,
821 AR_ADD = 1,
822 AR_REMOVE = -1,
823 }; /* 1: add, -1 remove, 0: random */
824
825 static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
826
827 static
828 void 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
846 static
847 void *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, thread id : %lx, tid %lu\n",
854 "reader", pthread_self(), (unsigned long) gettid());
855
856 set_affinity();
857
858 rcu_register_thread();
859
860 while (!test_go)
861 {
862 }
863 cmm_smp_mb();
864
865 for (;;) {
866 rcu_read_lock();
867
868 /* note: only looking up ulong keys */
869 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
870 key *= key_mul;
871 ja_node = cds_ja_lookup(test_ja, key);
872 if (!ja_node) {
873 if (validate_lookup) {
874 printf("[ERROR] Lookup cannot find initial node.\n");
875 exit(-1);
876 }
877 URCU_TLS(lookup_fail)++;
878 } else {
879 URCU_TLS(lookup_ok)++;
880 }
881 rcu_debug_yield_read();
882 if (caa_unlikely(rduration))
883 loop_sleep(rduration);
884 rcu_read_unlock();
885 URCU_TLS(nr_reads)++;
886 if (caa_unlikely(!test_duration_read()))
887 break;
888 if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
889 rcu_quiescent_state();
890 }
891
892 rcu_unregister_thread();
893
894 *count = URCU_TLS(nr_reads);
895 printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
896 "reader", pthread_self(), (unsigned long) gettid());
897 printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
898 pthread_self(), URCU_TLS(lookup_fail),
899 URCU_TLS(lookup_ok));
900 return ((void*)1);
901 }
902
903 static
904 int is_add(void)
905 {
906 return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
907 }
908
909 static
910 void *test_ja_rw_thr_writer(void *_count)
911 {
912 struct wr_count *count = _count;
913 uint64_t key;
914 int ret;
915
916 printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
917 "writer", pthread_self(), (unsigned long) gettid());
918
919 set_affinity();
920
921 rcu_register_thread();
922
923 while (!test_go)
924 {
925 }
926 cmm_smp_mb();
927
928 for (;;) {
929 if ((addremove == AR_ADD)
930 || (addremove == AR_RANDOM && is_add())) {
931 struct ja_test_node *node = node_alloc();
932 struct cds_ja_node *ret_node;
933
934 /* note: only inserting ulong keys */
935 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
936 key *= key_mul;
937 ja_test_node_init(node, key);
938 rcu_read_lock();
939 if (add_unique) {
940 ret_node = cds_ja_add_unique(test_ja, key, &node->node);
941 if (ret_node != &node->node) {
942 free_test_node(node);
943 URCU_TLS(nr_addexist)++;
944 } else {
945 URCU_TLS(nr_add)++;
946 }
947 } else if (add_replace) {
948 assert(0); /* not implemented yet. */
949 } else {
950 ret = cds_ja_add(test_ja, key, &node->node);
951 if (ret) {
952 fprintf(stderr, "Error in cds_ja_add: %d\n", ret);
953 free_test_node(node);
954 } else {
955 URCU_TLS(nr_add)++;
956 }
957 }
958 rcu_read_unlock();
959 } else {
960 struct cds_ja_node *ja_node;
961 struct ja_test_node *node;
962
963 /* May delete */
964 /* note: only deleting ulong keys */
965 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
966 key *= key_mul;
967
968 rcu_read_lock();
969
970 ja_node = cds_ja_lookup(test_ja, key);
971 /* Remove first entry */
972 if (ja_node) {
973 node = caa_container_of(ja_node,
974 struct ja_test_node, node);
975 ret = cds_ja_del(test_ja, key, &node->node);
976 if (!ret) {
977 rcu_free_test_node(node);
978 URCU_TLS(nr_del)++;
979 } else {
980 URCU_TLS(nr_delnoent)++;
981 }
982 } else {
983 URCU_TLS(nr_delnoent)++;
984 }
985 rcu_read_unlock();
986 }
987
988 URCU_TLS(nr_writes)++;
989 if (caa_unlikely(!test_duration_write()))
990 break;
991 if (caa_unlikely(wdelay))
992 loop_sleep(wdelay);
993 if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
994 rcu_quiescent_state();
995 }
996
997 rcu_unregister_thread();
998
999 printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
1000 "writer", pthread_self(), (unsigned long) gettid());
1001 printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
1002 "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
1003 URCU_TLS(nr_addexist), URCU_TLS(nr_del),
1004 URCU_TLS(nr_delnoent));
1005 count->update_ops = URCU_TLS(nr_writes);
1006 count->add = URCU_TLS(nr_add);
1007 count->add_exist = URCU_TLS(nr_addexist);
1008 count->remove = URCU_TLS(nr_del);
1009 return ((void*)2);
1010 }
1011
1012 static
1013 int do_mt_populate_ja(void)
1014 {
1015 uint64_t iter;
1016 int ret;
1017
1018 if (!init_populate)
1019 return 0;
1020
1021 printf("Starting rw test\n");
1022
1023 for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
1024 struct ja_test_node *node = node_alloc();
1025 uint64_t key;
1026
1027 /* note: only inserting ulong keys */
1028 key = (unsigned long) iter;
1029 key *= key_mul;
1030 ja_test_node_init(node, key);
1031 rcu_read_lock();
1032 ret = cds_ja_add(test_ja, key, &node->node);
1033 URCU_TLS(nr_add)++;
1034 URCU_TLS(nr_writes)++;
1035 rcu_read_unlock();
1036 /* Hash table resize only occurs in call_rcu thread */
1037 if (!(iter % 100))
1038 rcu_quiescent_state();
1039 if (ret) {
1040 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
1041 ret, key);
1042 assert(0);
1043 }
1044 }
1045 return 0;
1046 }
1047
1048 static
1049 int do_mt_test(void)
1050 {
1051 pthread_t *tid_reader, *tid_writer;
1052 void *tret;
1053 int ret, i, err;
1054 unsigned long long *count_reader;
1055 struct wr_count *count_writer;
1056 unsigned long long tot_reads = 0, tot_writes = 0,
1057 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
1058 unsigned int remain;
1059
1060 tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
1061 tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
1062 count_reader = malloc(sizeof(*count_reader) * nr_readers);
1063 count_writer = malloc(sizeof(*count_writer) * nr_writers);
1064
1065 printf("Allocating Judy Array for %u-bit keys\n", key_bits);
1066 test_ja = cds_ja_new(key_bits);
1067 if (!test_ja) {
1068 printf("Error allocating judy array.\n");
1069 ret = -1;
1070 goto end;
1071 }
1072
1073 do_mt_populate_ja();
1074
1075 next_aff = 0;
1076
1077 for (i = 0; i < nr_readers; i++) {
1078 err = pthread_create(&tid_reader[i],
1079 NULL, test_ja_rw_thr_reader,
1080 &count_reader[i]);
1081 if (err != 0)
1082 exit(1);
1083 }
1084 for (i = 0; i < nr_writers; i++) {
1085 err = pthread_create(&tid_writer[i],
1086 NULL, test_ja_rw_thr_writer,
1087 &count_writer[i]);
1088 if (err != 0)
1089 exit(1);
1090 }
1091
1092 cmm_smp_mb();
1093
1094 test_go = 1;
1095
1096 rcu_thread_offline_qsbr();
1097
1098 remain = duration;
1099 do {
1100 remain = sleep(remain);
1101 } while (remain > 0);
1102
1103 test_stop = 1;
1104
1105 for (i = 0; i < nr_readers; i++) {
1106 err = pthread_join(tid_reader[i], &tret);
1107 if (err != 0)
1108 exit(1);
1109 tot_reads += count_reader[i];
1110 }
1111 for (i = 0; i < nr_writers; i++) {
1112 err = pthread_join(tid_writer[i], &tret);
1113 if (err != 0)
1114 exit(1);
1115 tot_writes += count_writer[i].update_ops;
1116 tot_add += count_writer[i].add;
1117 tot_add_exist += count_writer[i].add_exist;
1118 tot_remove += count_writer[i].remove;
1119 }
1120 rcu_thread_online_qsbr();
1121
1122 ret = test_free_all_nodes(test_ja);
1123 if (ret) {
1124 fprintf(stderr, "Error freeing all nodes\n");
1125 return -1;
1126 }
1127
1128 ret = cds_ja_destroy(test_ja);
1129 if (ret) {
1130 fprintf(stderr, "Error destroying judy array\n");
1131 goto end;
1132 }
1133
1134 free(tid_reader);
1135 free(tid_writer);
1136 free(count_reader);
1137 free(count_writer);
1138 ret = 0;
1139 end:
1140 return ret;
1141 }
1142
1143 static
1144 int check_memory_leaks(void)
1145 {
1146 unsigned long na, nf;
1147
1148 na = uatomic_read(&test_nodes_allocated);
1149 nf = uatomic_read(&test_nodes_freed);
1150 if (na != nf) {
1151 fprintf(stderr, "Memory leak of %ld test nodes detected. Allocated: %lu, freed: %lu\n",
1152 na - nf, na, nf);
1153 return -1;
1154 }
1155 return 0;
1156 }
1157
1158 int main(int argc, char **argv)
1159 {
1160 int i, j, a, ret, err;
1161 uint64_t key;
1162 struct sigaction act;
1163
1164 if (argc < 4) {
1165 show_usage(argc, argv);
1166 return -1;
1167 }
1168
1169 err = sscanf(argv[1], "%u", &nr_readers);
1170 if (err != 1) {
1171 show_usage(argc, argv);
1172 return -1;
1173 }
1174
1175 err = sscanf(argv[2], "%u", &nr_writers);
1176 if (err != 1) {
1177 show_usage(argc, argv);
1178 return -1;
1179 }
1180
1181 err = sscanf(argv[3], "%lu", &duration);
1182 if (err != 1) {
1183 show_usage(argc, argv);
1184 return -1;
1185 }
1186
1187 for (i = 4; i < argc; i++) {
1188 if (argv[i][0] != '-')
1189 continue;
1190 switch (argv[i][1]) {
1191 #ifdef DEBUG_YIELD
1192 case 'r':
1193 yield_active |= YIELD_READ;
1194 break;
1195 case 'w':
1196 yield_active |= YIELD_WRITE;
1197 break;
1198 #endif
1199 case 'a':
1200 if (argc < i + 2) {
1201 show_usage(argc, argv);
1202 return -1;
1203 }
1204 a = atoi(argv[++i]);
1205 cpu_affinities[next_aff++] = a;
1206 use_affinity = 1;
1207 printf_verbose("Adding CPU %d affinity\n", a);
1208 break;
1209 case 'c':
1210 if (argc < i + 2) {
1211 show_usage(argc, argv);
1212 return -1;
1213 }
1214 rduration = atol(argv[++i]);
1215 break;
1216 case 'd':
1217 if (argc < i + 2) {
1218 show_usage(argc, argv);
1219 return -1;
1220 }
1221 wdelay = atol(argv[++i]);
1222 break;
1223 case 'v':
1224 verbose_mode = 1;
1225 break;
1226 case 'r':
1227 add_ratio = atoi(argv[++i]);
1228 break;
1229 case 'k':
1230 init_populate = 1;
1231 break;
1232 case 'R':
1233 lookup_pool_offset = atol(argv[++i]);
1234 break;
1235 case 'S':
1236 write_pool_offset = atol(argv[++i]);
1237 break;
1238 case 'T':
1239 init_pool_offset = atol(argv[++i]);
1240 break;
1241 case 'M':
1242 lookup_pool_size = atol(argv[++i]);
1243 break;
1244 case 'N':
1245 write_pool_size = atol(argv[++i]);
1246 break;
1247 case 'O':
1248 init_pool_size = atol(argv[++i]);
1249 break;
1250 case 'V':
1251 validate_lookup = 1;
1252 break;
1253 case 't':
1254 sanity_test = 1;
1255 break;
1256 case 'B':
1257 key_bits = atol(argv[++i]);
1258 break;
1259 case 'm':
1260 key_mul = atoll(argv[++i]);
1261 break;
1262 case 'u':
1263 add_unique = 1;
1264 break;
1265 case 's':
1266 add_replace = 1;
1267 break;
1268 case 'l':
1269 leak_detection = 1;
1270 break;
1271 }
1272 }
1273
1274 printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
1275 duration, nr_readers, nr_writers);
1276 printf_verbose("Writer delay : %lu loops.\n", wdelay);
1277 printf_verbose("Reader duration : %lu loops.\n", rduration);
1278 printf_verbose("Add ratio: %u%%.\n", add_ratio);
1279 printf_verbose("Mode:%s%s.\n",
1280 " add/remove",
1281 add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
1282 printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
1283 printf_verbose("Init pool size offset %lu size %lu.\n",
1284 init_pool_offset, init_pool_size);
1285 printf_verbose("Lookup pool size offset %lu size %lu.\n",
1286 lookup_pool_offset, lookup_pool_size);
1287 printf_verbose("Update pool size offset %lu size %lu.\n",
1288 write_pool_offset, write_pool_size);
1289 if (validate_lookup)
1290 printf_verbose("Validating lookups.\n");
1291 if (leak_detection)
1292 printf_verbose("Memory leak dection activated.\n");
1293 printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
1294 "main", pthread_self(), (unsigned long)gettid());
1295
1296 memset(&act, 0, sizeof(act));
1297 ret = sigemptyset(&act.sa_mask);
1298 if (ret == -1) {
1299 perror("sigemptyset");
1300 return -1;
1301 }
1302 act.sa_handler = test_ja_rw_sigusr1_handler;
1303 act.sa_flags = SA_RESTART;
1304 ret = sigaction(SIGUSR1, &act, NULL);
1305 if (ret == -1) {
1306 perror("sigaction");
1307 return -1;
1308 }
1309
1310 err = create_all_cpu_call_rcu_data(0);
1311 if (err) {
1312 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
1313 }
1314
1315 rcu_register_thread();
1316
1317 if (sanity_test) {
1318 ret = do_sanity_test();
1319 } else {
1320 ret = do_mt_test();
1321 }
1322
1323 /* Wait for in-flight call_rcu free to complete for leak detection */
1324 rcu_barrier();
1325
1326 ret |= check_memory_leaks();
1327
1328 rcu_unregister_thread();
1329 free_all_cpu_call_rcu_data();
1330
1331 if (ret) {
1332 printf("Test ended with error: %d\n", ret);
1333 }
1334 return ret;
1335 }
Userspace RCU (urcu) for Linux
This page took 0.055236 seconds and 3 git commands to generate.