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