rcuja: free all leaf nodes at destruction
[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
56 int count_pipe[2];
57
58 int verbose_mode;
59
60 unsigned int cpu_affinities[NR_CPUS];
61 unsigned int next_aff = 0;
62 int use_affinity = 0;
63
64 pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;
65
66 DEFINE_URCU_TLS(unsigned long long, nr_writes);
67 DEFINE_URCU_TLS(unsigned long long, nr_reads);
68
69 unsigned int nr_readers;
70 unsigned int nr_writers;
71
72 static pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
73
74 void set_affinity(void)
75 {
76 cpu_set_t mask;
77 int cpu;
78 int ret;
79
80 if (!use_affinity)
81 return;
82
83 #if HAVE_SCHED_SETAFFINITY
84 ret = pthread_mutex_lock(&affinity_mutex);
85 if (ret) {
86 perror("Error in pthread mutex lock");
87 exit(-1);
88 }
89 cpu = cpu_affinities[next_aff++];
90 ret = pthread_mutex_unlock(&affinity_mutex);
91 if (ret) {
92 perror("Error in pthread mutex unlock");
93 exit(-1);
94 }
95 CPU_ZERO(&mask);
96 CPU_SET(cpu, &mask);
97 #if SCHED_SETAFFINITY_ARGS == 2
98 sched_setaffinity(0, &mask);
99 #else
100 sched_setaffinity(0, sizeof(mask), &mask);
101 #endif
102 #endif /* HAVE_SCHED_SETAFFINITY */
103 }
104
105 void rcu_copy_mutex_lock(void)
106 {
107 int ret;
108 ret = pthread_mutex_lock(&rcu_copy_mutex);
109 if (ret) {
110 perror("Error in pthread mutex lock");
111 exit(-1);
112 }
113 }
114
115 void rcu_copy_mutex_unlock(void)
116 {
117 int ret;
118
119 ret = pthread_mutex_unlock(&rcu_copy_mutex);
120 if (ret) {
121 perror("Error in pthread mutex unlock");
122 exit(-1);
123 }
124 }
125
126 void free_node_cb(struct rcu_head *head)
127 {
128 struct ja_test_node *node =
129 caa_container_of(head, struct ja_test_node, node.head);
130 free(node);
131 }
132
133 #if 0
134 static
135 void test_delete_all_nodes(struct cds_lfht *ht)
136 {
137 struct cds_lfht_iter iter;
138 struct lfht_test_node *node;
139 unsigned long count = 0;
140
141 cds_lfht_for_each_entry(ht, &iter, node, node) {
142 int ret;
143
144 ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter));
145 assert(!ret);
146 call_rcu(&node->head, free_node_cb);
147 count++;
148 }
149 printf("deleted %lu nodes.\n", count);
150 }
151 #endif
152
153 void show_usage(int argc, char **argv)
154 {
155 printf("Usage : %s nr_readers nr_writers duration (s)\n", argv[0]);
156 #ifdef DEBUG_YIELD
157 printf(" [-r] [-w] (yield reader and/or writer)\n");
158 #endif
159 printf(" [-d delay] (writer period (us))\n");
160 printf(" [-c duration] (reader C.S. duration (in loops))\n");
161 printf(" [-v] (verbose output)\n");
162 printf(" [-a cpu#] [-a cpu#]... (affinity)\n");
163 printf(" [not -u nor -s] Add entries (supports redundant keys).\n");
164 printf(" [-i] Add only (no removal).\n");
165 printf(" [-k nr_nodes] Number of nodes to insert initially.\n");
166 printf(" [-R offset] Lookup pool offset.\n");
167 printf(" [-S offset] Write pool offset.\n");
168 printf(" [-T offset] Init pool offset.\n");
169 printf(" [-M size] Lookup pool size.\n");
170 printf(" [-N size] Write pool size.\n");
171 printf(" [-O size] Init pool size.\n");
172 printf(" [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
173 printf("\n\n");
174 }
175
176
177 static
178 int test_8bit_key(void)
179 {
180 int ret;
181 uint64_t key;
182
183 /* Test with 8-bit key */
184 test_ja = cds_ja_new(8);
185 if (!test_ja) {
186 printf("Error allocating judy array.\n");
187 return -1;
188 }
189
190 /* Add keys */
191 printf("Test #1: add keys (8-bit).\n");
192 for (key = 0; key < 200; key++) {
193 struct ja_test_node *node =
194 calloc(sizeof(*node), 1);
195
196 ja_test_node_init(node, key);
197 rcu_read_lock();
198 ret = cds_ja_add(test_ja, key, &node->node);
199 rcu_read_unlock();
200 if (ret) {
201 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
202 ret, key);
203 assert(0);
204 }
205 }
206 printf("OK\n");
207
208 printf("Test #2: successful key lookup (8-bit).\n");
209 for (key = 0; key < 200; key++) {
210 struct cds_hlist_head head;
211
212 rcu_read_lock();
213 head = cds_ja_lookup(test_ja, key);
214 if (cds_hlist_empty(&head)) {
215 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
216 assert(0);
217 }
218 rcu_read_unlock();
219 }
220 printf("OK\n");
221 printf("Test #3: unsuccessful key lookup (8-bit).\n");
222 for (key = 200; key < 240; key++) {
223 struct cds_hlist_head head;
224
225 rcu_read_lock();
226 head = cds_ja_lookup(test_ja, key);
227 if (!cds_hlist_empty(&head)) {
228 fprintf(stderr,
229 "Error unexpected lookup node %" PRIu64 "\n",
230 key);
231 assert(0);
232 }
233 rcu_read_unlock();
234 }
235 printf("OK\n");
236 printf("Test #4: remove keys (8-bit).\n");
237 for (key = 0; key < 200; key++) {
238 struct cds_hlist_head head;
239 struct ja_test_node *node;
240
241 rcu_read_lock();
242 head = cds_ja_lookup(test_ja, key);
243 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
244 if (!node) {
245 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
246 assert(0);
247 }
248 ret = cds_ja_del(test_ja, key, &node->node);
249 if (ret) {
250 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
251 assert(0);
252 }
253 call_rcu(&node->node.head, free_node_cb);
254 rcu_read_unlock();
255 }
256 printf("OK\n");
257
258 ret = cds_ja_destroy(test_ja, free_node_cb);
259 if (ret) {
260 fprintf(stderr, "Error destroying judy array\n");
261 return -1;
262 }
263 return 0;
264 }
265
266 static
267 int test_16bit_key(void)
268 {
269 int ret;
270 uint64_t key;
271
272 /* Test with 16-bit key */
273 test_ja = cds_ja_new(16);
274 if (!test_ja) {
275 printf("Error allocating judy array.\n");
276 return -1;
277 }
278
279 /* Add keys */
280 printf("Test #1: add keys (16-bit).\n");
281 //for (key = 0; key < 10000; key++) {
282 for (key = 0; key < 65536; key+=256) {
283 struct ja_test_node *node =
284 calloc(sizeof(*node), 1);
285
286 ja_test_node_init(node, key);
287 rcu_read_lock();
288 ret = cds_ja_add(test_ja, key, &node->node);
289 rcu_read_unlock();
290 if (ret) {
291 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
292 ret, key);
293 assert(0);
294 }
295 }
296 printf("OK\n");
297
298 printf("Test #2: successful key lookup (16-bit).\n");
299 //for (key = 0; key < 10000; key++) {
300 for (key = 0; key < 65536; key+=256) {
301 struct cds_hlist_head head;
302
303 rcu_read_lock();
304 head = cds_ja_lookup(test_ja, key);
305 if (cds_hlist_empty(&head)) {
306 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
307 assert(0);
308 }
309 rcu_read_unlock();
310 }
311 printf("OK\n");
312 printf("Test #3: unsuccessful key lookup (16-bit).\n");
313 for (key = 11000; key <= 11002; key++) {
314 struct cds_hlist_head head;
315
316 rcu_read_lock();
317 head = cds_ja_lookup(test_ja, key);
318 if (!cds_hlist_empty(&head)) {
319 fprintf(stderr,
320 "Error unexpected lookup node %" PRIu64 "\n",
321 key);
322 assert(0);
323 }
324 rcu_read_unlock();
325 }
326 printf("OK\n");
327
328 ret = cds_ja_destroy(test_ja, free_node_cb);
329 if (ret) {
330 fprintf(stderr, "Error destroying judy array\n");
331 return -1;
332 }
333 return 0;
334 }
335
336 static
337 int test_sparse_key(unsigned int bits)
338 {
339 int ret;
340 uint64_t key, max_key;
341 int zerocount;
342
343 if (bits == 64)
344 max_key = UINT64_MAX;
345 else
346 max_key = (1ULL << bits) - 1;
347
348 printf("Sparse key test begins for %u-bit keys\n", bits);
349 /* Test with 16-bit key */
350 test_ja = cds_ja_new(bits);
351 if (!test_ja) {
352 printf("Error allocating judy array.\n");
353 return -1;
354 }
355
356 /* Add keys */
357 printf("Test #1: add keys (%u-bit).\n", bits);
358 zerocount = 0;
359 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
360 struct ja_test_node *node =
361 calloc(sizeof(*node), 1);
362
363 ja_test_node_init(node, key);
364 rcu_read_lock();
365 ret = cds_ja_add(test_ja, key, &node->node);
366 rcu_read_unlock();
367 if (ret) {
368 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
369 ret, key);
370 assert(0);
371 }
372 if (key == 0)
373 zerocount++;
374 }
375 printf("OK\n");
376
377 printf("Test #2: successful key lookup (%u-bit).\n", bits);
378 zerocount = 0;
379 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
380 struct cds_hlist_head head;
381
382 rcu_read_lock();
383 head = cds_ja_lookup(test_ja, key);
384 if (cds_hlist_empty(&head)) {
385 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
386 assert(0);
387 }
388 rcu_read_unlock();
389 if (key == 0)
390 zerocount++;
391 }
392 printf("OK\n");
393 if (bits > 8) {
394 printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits);
395 zerocount = 0;
396 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
397 struct cds_hlist_head head;
398
399 rcu_read_lock();
400 head = cds_ja_lookup(test_ja, key + 42);
401 if (!cds_hlist_empty(&head)) {
402 fprintf(stderr,
403 "Error unexpected lookup node %" PRIu64 "\n",
404 key + 42);
405 assert(0);
406 }
407 rcu_read_unlock();
408 if (key == 0)
409 zerocount++;
410 }
411 printf("OK\n");
412 }
413
414 ret = cds_ja_destroy(test_ja, free_node_cb);
415 if (ret) {
416 fprintf(stderr, "Error destroying judy array\n");
417 return -1;
418 }
419 printf("Test ends\n");
420
421 return 0;
422 }
423
424
425 int main(int argc, char **argv)
426 {
427 int err;
428 pthread_t *tid_reader, *tid_writer;
429 void *tret;
430 unsigned long long *count_reader;
431 struct wr_count *count_writer;
432 unsigned long long tot_reads = 0, tot_writes = 0,
433 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
434 int i, a, ret;
435 unsigned int remain;
436 uint64_t key;
437
438 if (argc < 4) {
439 show_usage(argc, argv);
440 return -1;
441 }
442
443 err = sscanf(argv[1], "%u", &nr_readers);
444 if (err != 1) {
445 show_usage(argc, argv);
446 return -1;
447 }
448
449 err = sscanf(argv[2], "%u", &nr_writers);
450 if (err != 1) {
451 show_usage(argc, argv);
452 return -1;
453 }
454
455 err = sscanf(argv[3], "%lu", &duration);
456 if (err != 1) {
457 show_usage(argc, argv);
458 return -1;
459 }
460
461 for (i = 4; i < argc; i++) {
462 if (argv[i][0] != '-')
463 continue;
464 switch (argv[i][1]) {
465 #ifdef DEBUG_YIELD
466 case 'r':
467 yield_active |= YIELD_READ;
468 break;
469 case 'w':
470 yield_active |= YIELD_WRITE;
471 break;
472 #endif
473 case 'a':
474 if (argc < i + 2) {
475 show_usage(argc, argv);
476 return -1;
477 }
478 a = atoi(argv[++i]);
479 cpu_affinities[next_aff++] = a;
480 use_affinity = 1;
481 printf_verbose("Adding CPU %d affinity\n", a);
482 break;
483 case 'c':
484 if (argc < i + 2) {
485 show_usage(argc, argv);
486 return -1;
487 }
488 rduration = atol(argv[++i]);
489 break;
490 case 'd':
491 if (argc < i + 2) {
492 show_usage(argc, argv);
493 return -1;
494 }
495 wdelay = atol(argv[++i]);
496 break;
497 case 'v':
498 verbose_mode = 1;
499 break;
500 case 'i':
501 add_only = 1;
502 break;
503 case 'k':
504 init_populate = atol(argv[++i]);
505 break;
506 case 'R':
507 lookup_pool_offset = atol(argv[++i]);
508 break;
509 case 'S':
510 write_pool_offset = atol(argv[++i]);
511 break;
512 case 'T':
513 init_pool_offset = atol(argv[++i]);
514 break;
515 case 'M':
516 lookup_pool_size = atol(argv[++i]);
517 break;
518 case 'N':
519 write_pool_size = atol(argv[++i]);
520 break;
521 case 'O':
522 init_pool_size = atol(argv[++i]);
523 break;
524 case 'V':
525 validate_lookup = 1;
526 break;
527 }
528 }
529
530 printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
531 duration, nr_readers, nr_writers);
532 printf_verbose("Writer delay : %lu loops.\n", wdelay);
533 printf_verbose("Reader duration : %lu loops.\n", rduration);
534 printf_verbose("Mode:%s.\n",
535 add_only ? " add only" : " add/delete");
536 printf_verbose("Init pool size offset %lu size %lu.\n",
537 init_pool_offset, init_pool_size);
538 printf_verbose("Lookup pool size offset %lu size %lu.\n",
539 lookup_pool_offset, lookup_pool_size);
540 printf_verbose("Update pool size offset %lu size %lu.\n",
541 write_pool_offset, write_pool_size);
542 printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
543 "main", pthread_self(), (unsigned long)gettid());
544
545 tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
546 tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
547 count_reader = malloc(sizeof(*count_reader) * nr_readers);
548 count_writer = malloc(sizeof(*count_writer) * nr_writers);
549
550 err = create_all_cpu_call_rcu_data(0);
551 if (err) {
552 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
553 }
554
555 rcu_register_thread();
556
557 printf("Test start.\n");
558
559 for (i = 0; i < 3; i++) {
560 ret = test_8bit_key();
561 if (ret) {
562 return ret;
563 }
564 rcu_quiescent_state();
565 }
566 ret = test_16bit_key();
567 if (ret) {
568 return ret;
569 }
570 rcu_quiescent_state();
571
572 ret = test_sparse_key(8);
573 if (ret) {
574 return ret;
575 }
576 rcu_quiescent_state();
577
578 ret = test_sparse_key(16);
579 if (ret) {
580 return ret;
581 }
582 rcu_quiescent_state();
583
584 ret = test_sparse_key(32);
585 if (ret) {
586 return ret;
587 }
588 rcu_quiescent_state();
589
590 ret = test_sparse_key(64);
591 if (ret) {
592 return ret;
593 }
594 rcu_quiescent_state();
595
596 printf("Test end.\n");
597 rcu_unregister_thread();
598 return 0;
599
600 #if 0
601 /*
602 * Hash Population needs to be seen as a RCU reader
603 * thread from the point of view of resize.
604 */
605 rcu_register_thread();
606 ret = (get_populate_hash_cb())();
607 assert(!ret);
608
609 rcu_thread_offline();
610
611 next_aff = 0;
612
613 for (i = 0; i < nr_readers; i++) {
614 err = pthread_create(&tid_reader[i],
615 NULL, get_thr_reader_cb(),
616 &count_reader[i]);
617 if (err != 0)
618 exit(1);
619 }
620 for (i = 0; i < nr_writers; i++) {
621 err = pthread_create(&tid_writer[i],
622 NULL, get_thr_writer_cb(),
623 &count_writer[i]);
624 if (err != 0)
625 exit(1);
626 }
627
628 cmm_smp_mb();
629
630 test_go = 1;
631
632 remain = duration;
633 do {
634 remain = sleep(remain);
635 } while (remain > 0);
636
637 test_stop = 1;
638
639 for (i = 0; i < nr_readers; i++) {
640 err = pthread_join(tid_reader[i], &tret);
641 if (err != 0)
642 exit(1);
643 tot_reads += count_reader[i];
644 }
645 for (i = 0; i < nr_writers; i++) {
646 err = pthread_join(tid_writer[i], &tret);
647 if (err != 0)
648 exit(1);
649 tot_writes += count_writer[i].update_ops;
650 tot_add += count_writer[i].add;
651 tot_add_exist += count_writer[i].add_exist;
652 tot_remove += count_writer[i].remove;
653 }
654
655 /* teardown counter thread */
656 act.sa_handler = SIG_IGN;
657 act.sa_flags = SA_RESTART;
658 ret = sigaction(SIGUSR2, &act, NULL);
659 if (ret == -1) {
660 perror("sigaction");
661 return -1;
662 }
663 {
664 char msg[1] = { 0x42 };
665 ssize_t ret;
666
667 do {
668 ret = write(count_pipe[1], msg, 1); /* wakeup thread */
669 } while (ret == -1L && errno == EINTR);
670 }
671
672 fflush(stdout);
673 rcu_thread_online();
674 rcu_read_lock();
675 printf("Counting nodes... ");
676 cds_lfht_count_nodes(test_ht, &approx_before, &count, &approx_after);
677 printf("done.\n");
678 test_delete_all_nodes(test_ht);
679 rcu_read_unlock();
680 rcu_thread_offline();
681 if (count) {
682 printf("Approximation before node accounting: %ld nodes.\n",
683 approx_before);
684 printf("Nodes deleted from hash table before destroy: "
685 "%lu nodes.\n",
686 count);
687 printf("Approximation after node accounting: %ld nodes.\n",
688 approx_after);
689 }
690 ret = cds_lfht_destroy(test_ht, NULL);
691 if (ret)
692 printf_verbose("final delete aborted\n");
693 else
694 printf_verbose("final delete success\n");
695 printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads,
696 tot_writes);
697 printf("SUMMARY %-25s testdur %4lu nr_readers %3u rdur %6lu "
698 "nr_writers %3u "
699 "wdelay %6lu nr_reads %12llu nr_writes %12llu nr_ops %12llu "
700 "nr_add %12llu nr_add_fail %12llu nr_remove %12llu nr_leaked %12lld\n",
701 argv[0], duration, nr_readers, rduration,
702 nr_writers, wdelay, tot_reads, tot_writes,
703 tot_reads + tot_writes, tot_add, tot_add_exist, tot_remove,
704 (long long) tot_add + init_populate - tot_remove - count);
705 rcu_unregister_thread();
706 free_all_cpu_call_rcu_data();
707 free(tid_reader);
708 free(tid_writer);
709 free(count_reader);
710 free(count_writer);
711 #endif
712 return 0;
713 }
This page took 0.061048 seconds and 5 git commands to generate.