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_node_cb(struct rcu_head *head)
 149 {
 150         struct ja_test_node *node =
 151                 caa_container_of(head, struct ja_test_node, node.head);
 152         poison_free(node);
 153         if (leak_detection)
 154                 uatomic_inc(&test_nodes_freed);
 155 }
 156
 157 #if 0
 158 static
 159 void test_delete_all_nodes(struct cds_lfht *ht)
 160 {
 161         struct cds_lfht_iter iter;
 162         struct lfht_test_node *node;
 163         unsigned long count = 0;
 164
 165         cds_lfht_for_each_entry(ht, &iter, node, node) {
 166                 int ret;
 167
 168                 ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter));
 169                 assert(!ret);
 170                 call_rcu(&node->head, free_node_cb);
 171                 count++;
 172         }
 173         printf("deleted %lu nodes.\n", count);
 174 }
 175 #endif
 176
 177 void show_usage(int argc, char **argv)
 178 {
 179         printf("Usage : %s nr_readers nr_writers duration (s)\n", argv[0]);
 180 #ifdef DEBUG_YIELD
 181         printf("        [-r] [-w] (yield reader and/or writer)\n");
 182 #endif
 183         printf("        [-d delay] (writer period (us))\n");
 184         printf("        [-c duration] (reader C.S. duration (in loops))\n");
 185         printf("        [-v] (verbose output)\n");
 186         printf("        [-a cpu#] [-a cpu#]... (affinity)\n");
 187         printf("        [-u] Add unique keys.\n");
 188         printf("        [-s] Replace existing keys.\n");
 189 printf("        [not -u nor -s] Add entries (supports redundant keys).\n");
 190         printf("        [-r ratio] Add ratio (in %% of add+removal).\n");
 191         printf("        [-k] Populate init nodes.\n");
 192         printf("        [-R offset] Lookup pool offset.\n");
 193         printf("        [-S offset] Write pool offset.\n");
 194         printf("        [-T offset] Init pool offset.\n");
 195         printf("        [-M size] Lookup pool size.\n");
 196         printf("        [-N size] Write pool size.\n");
 197         printf("        [-O size] Init pool size.\n");
 198         printf("        [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
 199         printf("        [-t] Do sanity test.\n");
 200         printf("        [-B] Key bits for multithread test (default: 32).\n");
 201         printf("        [-m factor] Key multiplication factor.\n");
 202         printf("        [-l] Memory leak detection.\n");
 203         printf("\n\n");
 204 }
 205
 206
 207 static
 208 int test_8bit_key(void)
 209 {
 210         int ret;
 211         uint64_t key;
 212
 213         /* Test with 8-bit key */
 214         test_ja = cds_ja_new(8);
 215         if (!test_ja) {
 216                 printf("Error allocating judy array.\n");
 217                 return -1;
 218         }
 219
 220         /* Add keys */
 221         printf("Test #1: add keys (8-bit).\n");
 222         for (key = 0; key < 200; key++) {
 223                 struct ja_test_node *node = node_alloc();
 224
 225                 ja_test_node_init(node, key);
 226                 rcu_read_lock();
 227                 ret = cds_ja_add(test_ja, key, &node->node);
 228                 rcu_read_unlock();
 229                 if (ret) {
 230                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 231                                 ret, key);
 232                         assert(0);
 233                 }
 234         }
 235         printf("OK\n");
 236
 237         printf("Test #2: successful key lookup (8-bit).\n");
 238         for (key = 0; key < 200; key++) {
 239                 struct cds_hlist_head head;
 240
 241                 rcu_read_lock();
 242                 head = cds_ja_lookup(test_ja, key);
 243                 if (cds_hlist_empty(&head)) {
 244                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 245                         assert(0);
 246                 }
 247                 rcu_read_unlock();
 248         }
 249         printf("OK\n");
 250         printf("Test #3: unsuccessful key lookup (8-bit).\n");
 251         for (key = 200; key < 240; key++) {
 252                 struct cds_hlist_head head;
 253
 254                 rcu_read_lock();
 255                 head = cds_ja_lookup(test_ja, key);
 256                 if (!cds_hlist_empty(&head)) {
 257                         fprintf(stderr,
 258                                 "Error unexpected lookup node %" PRIu64 "\n",
 259                                 key);
 260                         assert(0);
 261                 }
 262                 rcu_read_unlock();
 263         }
 264         printf("OK\n");
 265         printf("Test #4: remove keys (8-bit).\n");
 266         for (key = 0; key < 200; key++) {
 267                 struct cds_hlist_head head;
 268                 struct ja_test_node *node;
 269
 270                 rcu_read_lock();
 271                 head = cds_ja_lookup(test_ja, key);
 272                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 273                 if (!node) {
 274                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 275                         assert(0);
 276                 }
 277                 ret = cds_ja_del(test_ja, key, &node->node);
 278                 if (ret) {
 279                         fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 280                         assert(0);
 281                 }
 282                 call_rcu(&node->node.head, free_node_cb);
 283                 head = cds_ja_lookup(test_ja, key);
 284                 if (!cds_hlist_empty(&head)) {
 285                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next);
 286                         assert(0);
 287                 }
 288                 rcu_read_unlock();
 289         }
 290         printf("OK\n");
 291
 292         ret = cds_ja_destroy(test_ja, free_node_cb);
 293         if (ret) {
 294                 fprintf(stderr, "Error destroying judy array\n");
 295                 return -1;
 296         }
 297         return 0;
 298 }
 299
 300 static
 301 int test_16bit_key(void)
 302 {
 303         int ret;
 304         uint64_t key;
 305
 306         /* Test with 16-bit key */
 307         test_ja = cds_ja_new(16);
 308         if (!test_ja) {
 309                 printf("Error allocating judy array.\n");
 310                 return -1;
 311         }
 312
 313         /* Add keys */
 314         printf("Test #1: add keys (16-bit).\n");
 315         for (key = 0; key < 10000; key++) {
 316         //for (key = 0; key < 65536; key+=256) {
 317                 struct ja_test_node *node = node_alloc();
 318
 319                 ja_test_node_init(node, key);
 320                 rcu_read_lock();
 321                 ret = cds_ja_add(test_ja, key, &node->node);
 322                 rcu_read_unlock();
 323                 if (ret) {
 324                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 325                                 ret, key);
 326                         assert(0);
 327                 }
 328         }
 329         printf("OK\n");
 330
 331         printf("Test #2: successful key lookup (16-bit).\n");
 332         for (key = 0; key < 10000; key++) {
 333         //for (key = 0; key < 65536; key+=256) {
 334                 struct cds_hlist_head head;
 335
 336                 rcu_read_lock();
 337                 head = cds_ja_lookup(test_ja, key);
 338                 if (cds_hlist_empty(&head)) {
 339                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 340                         assert(0);
 341                 }
 342                 rcu_read_unlock();
 343         }
 344         printf("OK\n");
 345         printf("Test #3: unsuccessful key lookup (16-bit).\n");
 346         for (key = 11000; key <= 11002; key++) {
 347                 struct cds_hlist_head head;
 348
 349                 rcu_read_lock();
 350                 head = cds_ja_lookup(test_ja, key);
 351                 if (!cds_hlist_empty(&head)) {
 352                         fprintf(stderr,
 353                                 "Error unexpected lookup node %" PRIu64 "\n",
 354                                 key);
 355                         assert(0);
 356                 }
 357                 rcu_read_unlock();
 358         }
 359         printf("OK\n");
 360         printf("Test #4: remove keys (16-bit).\n");
 361         for (key = 0; key < 10000; key++) {
 362         //for (key = 0; key < 65536; key+=256) {
 363                 struct cds_hlist_head head;
 364                 struct ja_test_node *node;
 365
 366                 rcu_read_lock();
 367                 head = cds_ja_lookup(test_ja, key);
 368                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 369                 if (!node) {
 370                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 371                         assert(0);
 372                 }
 373                 ret = cds_ja_del(test_ja, key, &node->node);
 374                 if (ret) {
 375                         fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 376                         assert(0);
 377                 }
 378                 call_rcu(&node->node.head, free_node_cb);
 379                 head = cds_ja_lookup(test_ja, key);
 380                 if (!cds_hlist_empty(&head)) {
 381                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next);
 382                         assert(0);
 383                 }
 384                 rcu_read_unlock();
 385         }
 386         printf("OK\n");
 387
 388         ret = cds_ja_destroy(test_ja, free_node_cb);
 389         if (ret) {
 390                 fprintf(stderr, "Error destroying judy array\n");
 391                 return -1;
 392         }
 393         return 0;
 394 }
 395
 396 /*
 397  * nr_dup is number of nodes per key.
 398  */
 399 static
 400 int test_sparse_key(unsigned int bits, int nr_dup)
 401 {
 402         uint64_t key, max_key;
 403         int zerocount, i, ret;
 404
 405         if (bits == 64)
 406                 max_key = UINT64_MAX;
 407         else
 408                 max_key = (1ULL << bits) - 1;
 409
 410         printf("Sparse key test begins for %u-bit keys\n", bits);
 411         /* Test with 16-bit key */
 412         test_ja = cds_ja_new(bits);
 413         if (!test_ja) {
 414                 printf("Error allocating judy array.\n");
 415                 return -1;
 416         }
 417
 418         /* Add keys */
 419         printf("Test #1: add keys (%u-bit).\n", bits);
 420         for (i = 0; i < nr_dup; i++) {
 421                 zerocount = 0;
 422                 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 423                         struct ja_test_node *node = node_alloc();
 424
 425                         ja_test_node_init(node, key);
 426                         rcu_read_lock();
 427                         ret = cds_ja_add(test_ja, key, &node->node);
 428                         rcu_read_unlock();
 429                         if (ret) {
 430                                 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 431                                         ret, key);
 432                                 assert(0);
 433                         }
 434                         if (key == 0)
 435                                 zerocount++;
 436                 }
 437         }
 438         printf("OK\n");
 439
 440         printf("Test #2: successful key lookup (%u-bit).\n", bits);
 441         zerocount = 0;
 442         for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 443                 struct cds_hlist_head head;
 444                 struct ja_test_node *node;
 445                 struct cds_hlist_node *pos;
 446                 int count = 0;
 447
 448                 rcu_read_lock();
 449                 head = cds_ja_lookup(test_ja, key);
 450                 if (cds_hlist_empty(&head)) {
 451                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 452                         assert(0);
 453                 }
 454                 cds_hlist_for_each_entry_rcu(node, pos, &head, node.list) {
 455                         count++;
 456                 }
 457                 if (count != nr_dup) {
 458                         fprintf(stderr, "Unexpected number of match for key %" PRIu64 ", expected %d, got %d.\n", key, nr_dup, count);
 459                 }
 460                 rcu_read_unlock();
 461                 if (key == 0)
 462                         zerocount++;
 463         }
 464         printf("OK\n");
 465         if (bits > 8) {
 466                 printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits);
 467                 zerocount = 0;
 468                 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 469                         struct cds_hlist_head head;
 470
 471                         rcu_read_lock();
 472                         head = cds_ja_lookup(test_ja, key + 42);
 473                         if (!cds_hlist_empty(&head)) {
 474                                 fprintf(stderr,
 475                                         "Error unexpected lookup node %" PRIu64 "\n",
 476                                         key + 42);
 477                                 assert(0);
 478                         }
 479                         rcu_read_unlock();
 480                         if (key == 0)
 481                                 zerocount++;
 482                 }
 483                 printf("OK\n");
 484         }
 485         printf("Test #4: remove keys (16-bit).\n");
 486         zerocount = 0;
 487         for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 488                 struct cds_hlist_head head;
 489                 struct ja_test_node *node;
 490                 struct cds_hlist_node *pos;
 491                 int count = 0;
 492
 493                 rcu_read_lock();
 494                 head = cds_ja_lookup(test_ja, key);
 495
 496
 497                 cds_hlist_for_each_entry_rcu(node, pos, &head, node.list) {
 498                         struct cds_hlist_head testhead;
 499
 500                         count++;
 501                         if (!node) {
 502                                 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 503                                 assert(0);
 504                         }
 505                         ret = cds_ja_del(test_ja, key, &node->node);
 506                         if (ret) {
 507                                 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 508                                 assert(0);
 509                         }
 510                         call_rcu(&node->node.head, free_node_cb);
 511                         testhead = cds_ja_lookup(test_ja, key);
 512                         if (count < nr_dup && cds_hlist_empty(&testhead)) {
 513                                 fprintf(stderr, "Error: no node found after deletion of some nodes of a key\n");
 514                                 assert(0);
 515                         }
 516                 }
 517                 head = cds_ja_lookup(test_ja, key);
 518                 if (!cds_hlist_empty(&head)) {
 519                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next);
 520                         assert(0);
 521                 }
 522                 rcu_read_unlock();
 523                 if (key == 0)
 524                         zerocount++;
 525         }
 526         printf("OK\n");
 527
 528         ret = cds_ja_destroy(test_ja, free_node_cb);
 529         if (ret) {
 530                 fprintf(stderr, "Error destroying judy array\n");
 531                 return -1;
 532         }
 533         printf("Test ends\n");
 534
 535         return 0;
 536 }
 537
 538 static
 539 int do_sanity_test(void)
 540 {
 541         int i, j, ret;
 542
 543         printf("Sanity test start.\n");
 544
 545         for (i = 0; i < 3; i++) {
 546                 ret = test_8bit_key();
 547                 if (ret) {
 548                         return ret;
 549                 }
 550                 rcu_quiescent_state();
 551         }
 552         ret = test_16bit_key();
 553         if (ret) {
 554                 return ret;
 555         }
 556         rcu_quiescent_state();
 557
 558         /* key bits */
 559         for (i = 8; i <= 64; i *= 2) {
 560                 /* nr of nodes per key */
 561                 for (j = 1; j < 4; j++) {
 562                         ret = test_sparse_key(i, j);
 563                         if (ret) {
 564                                 return ret;
 565                         }
 566                         rcu_quiescent_state();
 567                 }
 568         }
 569         printf("Sanity test end.\n");
 570
 571         return 0;
 572 }
 573
 574 enum urcu_ja_addremove {
 575         AR_RANDOM = 0,
 576         AR_ADD = 1,
 577         AR_REMOVE = -1,
 578 };      /* 1: add, -1 remove, 0: random */
 579
 580 static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
 581
 582 static
 583 void test_ja_rw_sigusr1_handler(int signo)
 584 {
 585         switch (addremove) {
 586         case AR_ADD:
 587                 printf("Add/Remove: random.\n");
 588                 addremove = AR_RANDOM;
 589                 break;
 590         case AR_RANDOM:
 591                 printf("Add/Remove: remove only.\n");
 592                 addremove = AR_REMOVE;
 593                 break;
 594         case AR_REMOVE:
 595                 printf("Add/Remove: add only.\n");
 596                 addremove = AR_ADD;
 597                 break;
 598         }
 599 }
 600
 601 static
 602 void *test_ja_rw_thr_reader(void *_count)
 603 {
 604         unsigned long long *count = _count;
 605         struct cds_hlist_head head;
 606         uint64_t key;
 607
 608         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 609                         "reader", pthread_self(), (unsigned long) gettid());
 610
 611         set_affinity();
 612
 613         rcu_register_thread();
 614
 615         while (!test_go)
 616         {
 617         }
 618         cmm_smp_mb();
 619
 620         for (;;) {
 621                 rcu_read_lock();
 622
 623                 /* note: only looking up ulong keys */
 624                 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
 625                 key *= key_mul;
 626                 head = cds_ja_lookup(test_ja, key);
 627                 if (cds_hlist_empty(&head)) {
 628                         if (validate_lookup) {
 629                                 printf("[ERROR] Lookup cannot find initial node.\n");
 630                                 exit(-1);
 631                         }
 632                         URCU_TLS(lookup_fail)++;
 633                 } else {
 634                         URCU_TLS(lookup_ok)++;
 635                 }
 636                 rcu_debug_yield_read();
 637                 if (caa_unlikely(rduration))
 638                         loop_sleep(rduration);
 639                 rcu_read_unlock();
 640                 URCU_TLS(nr_reads)++;
 641                 if (caa_unlikely(!test_duration_read()))
 642                         break;
 643                 if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
 644                         rcu_quiescent_state();
 645         }
 646
 647         rcu_unregister_thread();
 648
 649         *count = URCU_TLS(nr_reads);
 650         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 651                         "reader", pthread_self(), (unsigned long) gettid());
 652         printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
 653                         pthread_self(), URCU_TLS(lookup_fail),
 654                         URCU_TLS(lookup_ok));
 655         return ((void*)1);
 656 }
 657
 658 static
 659 int is_add(void)
 660 {
 661         return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
 662 }
 663
 664 static
 665 void *test_ja_rw_thr_writer(void *_count)
 666 {
 667         struct wr_count *count = _count;
 668         struct cds_hlist_head head;
 669         uint64_t key;
 670         int ret;
 671
 672         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 673                         "writer", pthread_self(), (unsigned long) gettid());
 674
 675         set_affinity();
 676
 677         rcu_register_thread();
 678
 679         while (!test_go)
 680         {
 681         }
 682         cmm_smp_mb();
 683
 684         for (;;) {
 685                 if ((addremove == AR_ADD)
 686                                 || (addremove == AR_RANDOM && is_add())) {
 687                         struct ja_test_node *node = node_alloc();
 688                         struct cds_ja_node *ret_node;
 689
 690                         /* note: only inserting ulong keys */
 691                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 692                         key *= key_mul;
 693                         ja_test_node_init(node, key);
 694                         rcu_read_lock();
 695                         if (add_unique) {
 696                                 ret_node = cds_ja_add_unique(test_ja, key, &node->node);
 697                                 if (ret_node != &node->node) {
 698                                         free(node);
 699                                         URCU_TLS(nr_addexist)++;
 700                                 } else {
 701                                         URCU_TLS(nr_add)++;
 702                                 }
 703                         } else if (add_replace) {
 704                                 assert(0);      /* not implemented yet. */
 705                         } else {
 706                                 ret = cds_ja_add(test_ja, key, &node->node);
 707                                 if (ret) {
 708                                         fprintf(stderr, "Error in cds_ja_add: %d\n", ret);
 709                                         free(node);
 710                                 } else {
 711                                         URCU_TLS(nr_add)++;
 712                                 }
 713                         }
 714                         rcu_read_unlock();
 715                 } else {
 716                         struct ja_test_node *node;
 717
 718                         /* May delete */
 719                         /* note: only deleting ulong keys */
 720                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 721                         key *= key_mul;
 722
 723                         rcu_read_lock();
 724
 725                         head = cds_ja_lookup(test_ja, key);
 726                         node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 727                         if (node) {
 728                                 ret = cds_ja_del(test_ja, key, &node->node);
 729                                 if (!ret) {
 730                                         call_rcu(&node->node.head, free_node_cb);
 731                                         URCU_TLS(nr_del)++;
 732                                 } else {
 733                                         URCU_TLS(nr_delnoent)++;
 734                                 }
 735                         } else {
 736                                 URCU_TLS(nr_delnoent)++;
 737                         }
 738                         rcu_read_unlock();
 739                 }
 740
 741                 URCU_TLS(nr_writes)++;
 742                 if (caa_unlikely(!test_duration_write()))
 743                         break;
 744                 if (caa_unlikely(wdelay))
 745                         loop_sleep(wdelay);
 746                 if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
 747                         rcu_quiescent_state();
 748         }
 749
 750         rcu_unregister_thread();
 751
 752         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 753                         "writer", pthread_self(), (unsigned long) gettid());
 754         printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
 755                         "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
 756                         URCU_TLS(nr_addexist), URCU_TLS(nr_del),
 757                         URCU_TLS(nr_delnoent));
 758         count->update_ops = URCU_TLS(nr_writes);
 759         count->add = URCU_TLS(nr_add);
 760         count->add_exist = URCU_TLS(nr_addexist);
 761         count->remove = URCU_TLS(nr_del);
 762         return ((void*)2);
 763 }
 764
 765 static
 766 int do_mt_populate_ja(void)
 767 {
 768         struct cds_hlist_head head;
 769         uint64_t iter;
 770         int ret;
 771
 772         if (!init_populate)
 773                 return 0;
 774
 775         printf("Starting rw test\n");
 776
 777         for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
 778                 struct ja_test_node *node = node_alloc();
 779                 uint64_t key;
 780
 781                 /* note: only inserting ulong keys */
 782                 key = (unsigned long) iter;
 783                 key *= key_mul;
 784                 ja_test_node_init(node, key);
 785                 rcu_read_lock();
 786                 ret = cds_ja_add(test_ja, key, &node->node);
 787                 URCU_TLS(nr_add)++;
 788                 URCU_TLS(nr_writes)++;
 789                 rcu_read_unlock();
 790                 if (ret) {
 791                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 792                                 ret, key);
 793                         assert(0);
 794                 }
 795         }
 796         return 0;
 797 }
 798
 799 static
 800 int do_mt_test(void)
 801 {
 802         pthread_t *tid_reader, *tid_writer;
 803         void *tret;
 804         int ret, i, err;
 805         unsigned long long *count_reader;
 806         struct wr_count *count_writer;
 807         unsigned long long tot_reads = 0, tot_writes = 0,
 808                 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
 809         unsigned int remain;
 810
 811         tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
 812         tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
 813         count_reader = malloc(sizeof(*count_reader) * nr_readers);
 814         count_writer = malloc(sizeof(*count_writer) * nr_writers);
 815
 816         printf("Allocating Judy Array for %u-bit keys\n", key_bits);
 817         test_ja = cds_ja_new(key_bits);
 818         if (!test_ja) {
 819                 printf("Error allocating judy array.\n");
 820                 ret = -1;
 821                 goto end;
 822         }
 823
 824         do_mt_populate_ja();
 825
 826         next_aff = 0;
 827
 828         for (i = 0; i < nr_readers; i++) {
 829                 err = pthread_create(&tid_reader[i],
 830                                      NULL, test_ja_rw_thr_reader,
 831                                      &count_reader[i]);
 832                 if (err != 0)
 833                         exit(1);
 834         }
 835         for (i = 0; i < nr_writers; i++) {
 836                 err = pthread_create(&tid_writer[i],
 837                                      NULL, test_ja_rw_thr_writer,
 838                                      &count_writer[i]);
 839                 if (err != 0)
 840                         exit(1);
 841         }
 842
 843         cmm_smp_mb();
 844
 845         test_go = 1;
 846
 847         rcu_thread_offline_qsbr();
 848
 849         remain = duration;
 850         do {
 851                 remain = sleep(remain);
 852         } while (remain > 0);
 853
 854         test_stop = 1;
 855
 856         for (i = 0; i < nr_readers; i++) {
 857                 err = pthread_join(tid_reader[i], &tret);
 858                 if (err != 0)
 859                         exit(1);
 860                 tot_reads += count_reader[i];
 861         }
 862         for (i = 0; i < nr_writers; i++) {
 863                 err = pthread_join(tid_writer[i], &tret);
 864                 if (err != 0)
 865                         exit(1);
 866                 tot_writes += count_writer[i].update_ops;
 867                 tot_add += count_writer[i].add;
 868                 tot_add_exist += count_writer[i].add_exist;
 869                 tot_remove += count_writer[i].remove;
 870         }
 871         rcu_thread_online_qsbr();
 872
 873         ret = cds_ja_destroy(test_ja, free_node_cb);
 874         if (ret) {
 875                 fprintf(stderr, "Error destroying judy array\n");
 876                 goto end;
 877         }
 878
 879         free(tid_reader);
 880         free(tid_writer);
 881         free(count_reader);
 882         free(count_writer);
 883         ret = 0;
 884 end:
 885         return ret;
 886 }
 887
 888 static
 889 int check_memory_leaks(void)
 890 {
 891         unsigned long na, nf;
 892
 893         na = uatomic_read(&test_nodes_allocated);
 894         nf = uatomic_read(&test_nodes_freed);
 895         if (na != nf) {
 896                 fprintf(stderr, "Memory leak of %ld test nodes detected. Allocated: %lu, freed: %lu\n",
 897                         na - nf, na, nf);
 898                 return -1;
 899         }
 900         return 0;
 901 }
 902
 903 int main(int argc, char **argv)
 904 {
 905         int i, j, a, ret, err;
 906         uint64_t key;
 907         struct sigaction act;
 908
 909         if (argc < 4) {
 910                 show_usage(argc, argv);
 911                 return -1;
 912         }
 913
 914         err = sscanf(argv[1], "%u", &nr_readers);
 915         if (err != 1) {
 916                 show_usage(argc, argv);
 917                 return -1;
 918         }
 919
 920         err = sscanf(argv[2], "%u", &nr_writers);
 921         if (err != 1) {
 922                 show_usage(argc, argv);
 923                 return -1;
 924         }
 925
 926         err = sscanf(argv[3], "%lu", &duration);
 927         if (err != 1) {
 928                 show_usage(argc, argv);
 929                 return -1;
 930         }
 931
 932         for (i = 4; i < argc; i++) {
 933                 if (argv[i][0] != '-')
 934                         continue;
 935                 switch (argv[i][1]) {
 936 #ifdef DEBUG_YIELD
 937                 case 'r':
 938                         yield_active |= YIELD_READ;
 939                         break;
 940                 case 'w':
 941                         yield_active |= YIELD_WRITE;
 942                         break;
 943 #endif
 944                 case 'a':
 945                         if (argc < i + 2) {
 946                                 show_usage(argc, argv);
 947                                 return -1;
 948                         }
 949                         a = atoi(argv[++i]);
 950                         cpu_affinities[next_aff++] = a;
 951                         use_affinity = 1;
 952                         printf_verbose("Adding CPU %d affinity\n", a);
 953                         break;
 954                 case 'c':
 955                         if (argc < i + 2) {
 956                                 show_usage(argc, argv);
 957                                 return -1;
 958                         }
 959                         rduration = atol(argv[++i]);
 960                         break;
 961                 case 'd':
 962                         if (argc < i + 2) {
 963                                 show_usage(argc, argv);
 964                                 return -1;
 965                         }
 966                         wdelay = atol(argv[++i]);
 967                         break;
 968                 case 'v':
 969                         verbose_mode = 1;
 970                         break;
 971                 case 'r':
 972                         add_ratio = atoi(argv[++i]);
 973                         break;
 974                 case 'k':
 975                         init_populate = 1;
 976                         break;
 977                 case 'R':
 978                         lookup_pool_offset = atol(argv[++i]);
 979                         break;
 980                 case 'S':
 981                         write_pool_offset = atol(argv[++i]);
 982                         break;
 983                 case 'T':
 984                         init_pool_offset = atol(argv[++i]);
 985                         break;
 986                 case 'M':
 987                         lookup_pool_size = atol(argv[++i]);
 988                         break;
 989                 case 'N':
 990                         write_pool_size = atol(argv[++i]);
 991                         break;
 992                 case 'O':
 993                         init_pool_size = atol(argv[++i]);
 994                         break;
 995                 case 'V':
 996                         validate_lookup = 1;
 997                         break;
 998                 case 't':
 999                         sanity_test = 1;
1000                         break;
1001                 case 'B':
1002                         key_bits = atol(argv[++i]);
1003                         break;
1004                 case 'm':
1005                         key_mul = atoll(argv[++i]);
1006                         break;
1007                 case 'u':
1008                         add_unique = 1;
1009                         break;
1010                 case 's':
1011                         add_replace = 1;
1012                         break;
1013                 case 'l':
1014                         leak_detection = 1;
1015                         break;
1016                 }
1017         }
1018
1019         printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
1020                 duration, nr_readers, nr_writers);
1021         printf_verbose("Writer delay : %lu loops.\n", wdelay);
1022         printf_verbose("Reader duration : %lu loops.\n", rduration);
1023         printf_verbose("Add ratio: %u%%.\n", add_ratio);
1024         printf_verbose("Mode:%s%s.\n",
1025                 " add/remove",
1026                 add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
1027         printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
1028         printf_verbose("Init pool size offset %lu size %lu.\n",
1029                 init_pool_offset, init_pool_size);
1030         printf_verbose("Lookup pool size offset %lu size %lu.\n",
1031                 lookup_pool_offset, lookup_pool_size);
1032         printf_verbose("Update pool size offset %lu size %lu.\n",
1033                 write_pool_offset, write_pool_size);
1034         if (validate_lookup)
1035                 printf_verbose("Validating lookups.\n");
1036         if (leak_detection)
1037                 printf_verbose("Memory leak dection activated.\n");
1038         printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
1039                         "main", pthread_self(), (unsigned long)gettid());
1040
1041         memset(&act, 0, sizeof(act));
1042         ret = sigemptyset(&act.sa_mask);
1043         if (ret == -1) {
1044                 perror("sigemptyset");
1045                 return -1;
1046         }
1047         act.sa_handler = test_ja_rw_sigusr1_handler;
1048         act.sa_flags = SA_RESTART;
1049         ret = sigaction(SIGUSR1, &act, NULL);
1050         if (ret == -1) {
1051                 perror("sigaction");
1052                 return -1;
1053         }
1054
1055         err = create_all_cpu_call_rcu_data(0);
1056         if (err) {
1057                 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
1058         }
1059
1060         rcu_register_thread();
1061
1062         if (sanity_test) {
1063                 ret = do_sanity_test();
1064         } else {
1065                 ret = do_mt_test();
1066         }
1067
1068         /* Wait for in-flight call_rcu free to complete for leak detection */
1069         rcu_barrier();
1070
1071         ret |= check_memory_leaks();
1072
1073         rcu_unregister_thread();
1074         free_all_cpu_call_rcu_data();
1075
1076         if (ret) {
1077                 printf("Test ended with error: %d\n", ret);
1078         }
1079         return ret;
1080 }