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