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