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