tests/test_urcu_ja.c

   1 /*
   2  * test_urcu_ja.c
   3  *
   4  * Userspace RCU library - test program
   5  *
   6  * Copyright 2009-2012 - Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License along
  19  * with this program; if not, write to the Free Software Foundation, Inc.,
  20  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22
  23 #define _GNU_SOURCE
  24 #include "test_urcu_ja.h"
  25 #include <inttypes.h>
  26 #include <stdint.h>
  27
  28 DEFINE_URCU_TLS(unsigned int, rand_lookup);
  29 DEFINE_URCU_TLS(unsigned long, nr_add);
  30 DEFINE_URCU_TLS(unsigned long, nr_addexist);
  31 DEFINE_URCU_TLS(unsigned long, nr_del);
  32 DEFINE_URCU_TLS(unsigned long, nr_delnoent);
  33 DEFINE_URCU_TLS(unsigned long, lookup_fail);
  34 DEFINE_URCU_TLS(unsigned long, lookup_ok);
  35
  36 struct cds_ja *test_ja;
  37
  38 volatile int test_go, test_stop;
  39
  40 unsigned long wdelay;
  41
  42 unsigned long duration;
  43
  44 /* read-side C.S. duration, in loops */
  45 unsigned long rduration;
  46
  47 unsigned long init_populate;
  48 int add_only;
  49
  50 unsigned long init_pool_offset, lookup_pool_offset, write_pool_offset;
  51 unsigned long init_pool_size = DEFAULT_RAND_POOL,
  52         lookup_pool_size = DEFAULT_RAND_POOL,
  53         write_pool_size = DEFAULT_RAND_POOL;
  54 int validate_lookup;
  55 int sanity_test;
  56 unsigned int key_bits = 32;
  57
  58 int count_pipe[2];
  59
  60 int verbose_mode;
  61
  62 unsigned int cpu_affinities[NR_CPUS];
  63 unsigned int next_aff = 0;
  64 int use_affinity = 0;
  65
  66 pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER;
  67
  68 DEFINE_URCU_TLS(unsigned long long, nr_writes);
  69 DEFINE_URCU_TLS(unsigned long long, nr_reads);
  70
  71 unsigned int nr_readers;
  72 unsigned int nr_writers;
  73
  74 static unsigned int add_ratio = 50;
  75 static uint64_t key_mul = 1ULL;
  76
  77 static int add_unique, add_replace;
  78
  79 static pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER;
  80
  81 static int leak_detection;
  82 static unsigned long test_nodes_allocated, test_nodes_freed;
  83
  84 void set_affinity(void)
  85 {
  86         cpu_set_t mask;
  87         int cpu;
  88         int ret;
  89
  90         if (!use_affinity)
  91                 return;
  92
  93 #if HAVE_SCHED_SETAFFINITY
  94         ret = pthread_mutex_lock(&affinity_mutex);
  95         if (ret) {
  96                 perror("Error in pthread mutex lock");
  97                 exit(-1);
  98         }
  99         cpu = cpu_affinities[next_aff++];
 100         ret = pthread_mutex_unlock(&affinity_mutex);
 101         if (ret) {
 102                 perror("Error in pthread mutex unlock");
 103                 exit(-1);
 104         }
 105         CPU_ZERO(&mask);
 106         CPU_SET(cpu, &mask);
 107 #if SCHED_SETAFFINITY_ARGS == 2
 108         sched_setaffinity(0, &mask);
 109 #else
 110         sched_setaffinity(0, sizeof(mask), &mask);
 111 #endif
 112 #endif /* HAVE_SCHED_SETAFFINITY */
 113 }
 114
 115 void rcu_copy_mutex_lock(void)
 116 {
 117         int ret;
 118         ret = pthread_mutex_lock(&rcu_copy_mutex);
 119         if (ret) {
 120                 perror("Error in pthread mutex lock");
 121                 exit(-1);
 122         }
 123 }
 124
 125 void rcu_copy_mutex_unlock(void)
 126 {
 127         int ret;
 128
 129         ret = pthread_mutex_unlock(&rcu_copy_mutex);
 130         if (ret) {
 131                 perror("Error in pthread mutex unlock");
 132                 exit(-1);
 133         }
 134 }
 135
 136 static
 137 struct ja_test_node *node_alloc(void)
 138 {
 139         struct ja_test_node *node;
 140
 141         node = calloc(sizeof(*node), 1);
 142         if (leak_detection && node)
 143                 uatomic_inc(&test_nodes_allocated);
 144         return node;
 145 }
 146
 147 static
 148 void free_node(struct ja_test_node *node)
 149 {
 150         poison_free(node);
 151         if (leak_detection)
 152                 uatomic_inc(&test_nodes_freed);
 153 }
 154
 155 static
 156 void free_node_cb(struct rcu_head *head)
 157 {
 158         struct ja_test_node *node =
 159                 caa_container_of(head, struct ja_test_node, head);
 160         free_node(node);
 161 }
 162
 163 static
 164 void rcu_free_test_node(struct ja_test_node *test_node)
 165 {
 166         call_rcu(&test_node->head, free_node_cb);
 167 }
 168
 169 static
 170 void rcu_free_node(struct cds_ja_node *node)
 171 {
 172         struct ja_test_node *test_node = to_test_node(node);
 173
 174         rcu_free_test_node(test_node);
 175 }
 176
 177 #if 0
 178 static
 179 void test_delete_all_nodes(struct cds_lfht *ht)
 180 {
 181         struct cds_lfht_iter iter;
 182         struct lfht_test_node *node;
 183         unsigned long count = 0;
 184
 185         cds_lfht_for_each_entry(ht, &iter, node, node) {
 186                 int ret;
 187
 188                 ret = cds_lfht_del(test_ht, cds_lfht_iter_get_node(&iter));
 189                 assert(!ret);
 190                 call_rcu(&node->head, free_node_cb);
 191                 count++;
 192         }
 193         printf("deleted %lu nodes.\n", count);
 194 }
 195 #endif
 196
 197 void show_usage(int argc, char **argv)
 198 {
 199         printf("Usage : %s nr_readers nr_writers duration (s)\n", argv[0]);
 200 #ifdef DEBUG_YIELD
 201         printf("        [-r] [-w] (yield reader and/or writer)\n");
 202 #endif
 203         printf("        [-d delay] (writer period (us))\n");
 204         printf("        [-c duration] (reader C.S. duration (in loops))\n");
 205         printf("        [-v] (verbose output)\n");
 206         printf("        [-a cpu#] [-a cpu#]... (affinity)\n");
 207         printf("        [-u] Add unique keys.\n");
 208         printf("        [-s] Replace existing keys.\n");
 209 printf("        [not -u nor -s] Add entries (supports redundant keys).\n");
 210         printf("        [-r ratio] Add ratio (in %% of add+removal).\n");
 211         printf("        [-k] Populate init nodes.\n");
 212         printf("        [-R offset] Lookup pool offset.\n");
 213         printf("        [-S offset] Write pool offset.\n");
 214         printf("        [-T offset] Init pool offset.\n");
 215         printf("        [-M size] Lookup pool size.\n");
 216         printf("        [-N size] Write pool size.\n");
 217         printf("        [-O size] Init pool size.\n");
 218         printf("        [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
 219         printf("        [-t] Do sanity test.\n");
 220         printf("        [-B] Key bits for multithread test (default: 32).\n");
 221         printf("        [-m factor] Key multiplication factor.\n");
 222         printf("        [-l] Memory leak detection.\n");
 223         printf("\n\n");
 224 }
 225
 226 static
 227 int test_8bit_key(void)
 228 {
 229         int ret, i;
 230         uint64_t key;
 231         uint64_t ka[] = { 4, 17, 100, 222 };
 232         uint64_t ka_test_offset = 5;
 233
 234         /* Test with 8-bit key */
 235         test_ja = cds_ja_new(8);
 236         if (!test_ja) {
 237                 printf("Error allocating judy array.\n");
 238                 return -1;
 239         }
 240
 241         /* Add keys */
 242         printf("Test #1: add keys (8-bit).\n");
 243         for (key = 0; key < 200; key++) {
 244                 struct ja_test_node *node = node_alloc();
 245
 246                 ja_test_node_init(node, key);
 247                 rcu_read_lock();
 248                 ret = cds_ja_add(test_ja, key, &node->node);
 249                 rcu_read_unlock();
 250                 if (ret) {
 251                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 252                                 ret, key);
 253                         assert(0);
 254                 }
 255         }
 256         printf("OK\n");
 257
 258         printf("Test #2: successful key lookup (8-bit).\n");
 259         for (key = 0; key < 200; key++) {
 260                 struct cds_hlist_head head;
 261
 262                 rcu_read_lock();
 263                 head = cds_ja_lookup(test_ja, key);
 264                 if (cds_hlist_empty(&head)) {
 265                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 266                         assert(0);
 267                 }
 268                 rcu_read_unlock();
 269         }
 270         printf("OK\n");
 271         printf("Test #3: unsuccessful key lookup (8-bit).\n");
 272         for (key = 200; key < 240; key++) {
 273                 struct cds_hlist_head head;
 274
 275                 rcu_read_lock();
 276                 head = cds_ja_lookup(test_ja, key);
 277                 if (!cds_hlist_empty(&head)) {
 278                         fprintf(stderr,
 279                                 "Error unexpected lookup node %" PRIu64 "\n",
 280                                 key);
 281                         assert(0);
 282                 }
 283                 rcu_read_unlock();
 284         }
 285         printf("OK\n");
 286         printf("Test #4: remove keys (8-bit).\n");
 287         for (key = 0; key < 200; key++) {
 288                 struct cds_hlist_head head;
 289                 struct ja_test_node *node;
 290
 291                 rcu_read_lock();
 292                 head = cds_ja_lookup(test_ja, key);
 293                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 294                 if (!node) {
 295                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 296                         assert(0);
 297                 }
 298                 ret = cds_ja_del(test_ja, key, &node->node);
 299                 if (ret) {
 300                         fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 301                         assert(0);
 302                 }
 303                 rcu_free_test_node(node);
 304                 head = cds_ja_lookup(test_ja, key);
 305                 if (!cds_hlist_empty(&head)) {
 306                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next);
 307                         assert(0);
 308                 }
 309                 rcu_read_unlock();
 310         }
 311         printf("OK\n");
 312
 313         printf("Test #5: lookup lower equal (8-bit).\n");
 314
 315         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 316                 struct ja_test_node *node = node_alloc();
 317
 318                 key = ka[i];
 319                 ja_test_node_init(node, key);
 320                 rcu_read_lock();
 321                 ret = cds_ja_add(test_ja, key, &node->node);
 322                 rcu_read_unlock();
 323                 if (ret) {
 324                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 325                                 ret, key);
 326                         assert(0);
 327                 }
 328         }
 329
 330         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 331                 struct cds_hlist_head head;
 332                 struct ja_test_node *node;
 333
 334                 key = ka[i] + ka_test_offset;
 335                 rcu_read_lock();
 336                 head = cds_ja_lookup_lower_equal(test_ja, key);
 337                 if (cds_hlist_empty(&head)) {
 338                         fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 339                                 ka[i], key);
 340                         assert(0);
 341                 }
 342                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 343                 if (node->key != ka[i]) {
 344                         fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 345                                 ka[i], key, node->key);
 346                         assert(0);
 347                 }
 348                 rcu_read_unlock();
 349         }
 350
 351         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 352                 struct cds_hlist_head head;
 353                 struct ja_test_node *node;
 354
 355                 key = ka[i];    /* without offset */
 356                 rcu_read_lock();
 357                 head = cds_ja_lookup_lower_equal(test_ja, key);
 358                 if (cds_hlist_empty(&head)) {
 359                         fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 360                                 ka[i], key);
 361                         assert(0);
 362                 }
 363                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 364                 if (node->key != ka[i]) {
 365                         fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 366                                 ka[i], key, node->key);
 367                         assert(0);
 368                 }
 369                 rcu_read_unlock();
 370         }
 371
 372         printf("OK\n");
 373
 374         ret = cds_ja_destroy(test_ja, rcu_free_node);
 375         if (ret) {
 376                 fprintf(stderr, "Error destroying judy array\n");
 377                 return -1;
 378         }
 379         return 0;
 380 }
 381
 382 static
 383 int test_16bit_key(void)
 384 {
 385         int ret, i;
 386         uint64_t key;
 387         uint64_t ka[] = { 4, 105, 222, 4000, 4111, 59990, 65435 };
 388         uint64_t ka_test_offset = 100;
 389
 390         /* Test with 16-bit key */
 391         test_ja = cds_ja_new(16);
 392         if (!test_ja) {
 393                 printf("Error allocating judy array.\n");
 394                 return -1;
 395         }
 396
 397         /* Add keys */
 398         printf("Test #1: add keys (16-bit).\n");
 399         for (key = 0; key < 10000; key++) {
 400         //for (key = 0; key < 65536; key+=256) {
 401                 struct ja_test_node *node = node_alloc();
 402
 403                 ja_test_node_init(node, key);
 404                 rcu_read_lock();
 405                 ret = cds_ja_add(test_ja, key, &node->node);
 406                 rcu_read_unlock();
 407                 if (ret) {
 408                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 409                                 ret, key);
 410                         assert(0);
 411                 }
 412         }
 413         printf("OK\n");
 414
 415         printf("Test #2: successful key lookup (16-bit).\n");
 416         for (key = 0; key < 10000; key++) {
 417         //for (key = 0; key < 65536; key+=256) {
 418                 struct cds_hlist_head head;
 419
 420                 rcu_read_lock();
 421                 head = cds_ja_lookup(test_ja, key);
 422                 if (cds_hlist_empty(&head)) {
 423                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 424                         assert(0);
 425                 }
 426                 rcu_read_unlock();
 427         }
 428         printf("OK\n");
 429         printf("Test #3: unsuccessful key lookup (16-bit).\n");
 430         for (key = 11000; key <= 11002; key++) {
 431                 struct cds_hlist_head head;
 432
 433                 rcu_read_lock();
 434                 head = cds_ja_lookup(test_ja, key);
 435                 if (!cds_hlist_empty(&head)) {
 436                         fprintf(stderr,
 437                                 "Error unexpected lookup node %" PRIu64 "\n",
 438                                 key);
 439                         assert(0);
 440                 }
 441                 rcu_read_unlock();
 442         }
 443         printf("OK\n");
 444         printf("Test #4: remove keys (16-bit).\n");
 445         for (key = 0; key < 10000; key++) {
 446         //for (key = 0; key < 65536; key+=256) {
 447                 struct cds_hlist_head head;
 448                 struct ja_test_node *node;
 449
 450                 rcu_read_lock();
 451                 head = cds_ja_lookup(test_ja, key);
 452                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 453                 if (!node) {
 454                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 455                         assert(0);
 456                 }
 457                 ret = cds_ja_del(test_ja, key, &node->node);
 458                 if (ret) {
 459                         fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 460                         assert(0);
 461                 }
 462                 rcu_free_test_node(node);
 463                 head = cds_ja_lookup(test_ja, key);
 464                 if (!cds_hlist_empty(&head)) {
 465                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next);
 466                         assert(0);
 467                 }
 468                 rcu_read_unlock();
 469         }
 470         printf("OK\n");
 471
 472         printf("Test #5: lookup lower equal (16-bit).\n");
 473
 474         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 475                 struct ja_test_node *node = node_alloc();
 476
 477                 key = ka[i];
 478                 ja_test_node_init(node, key);
 479                 rcu_read_lock();
 480                 ret = cds_ja_add(test_ja, key, &node->node);
 481                 rcu_read_unlock();
 482                 if (ret) {
 483                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 484                                 ret, key);
 485                         assert(0);
 486                 }
 487         }
 488
 489         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 490                 struct cds_hlist_head head;
 491                 struct ja_test_node *node;
 492
 493                 key = ka[i] + ka_test_offset;
 494                 rcu_read_lock();
 495                 head = cds_ja_lookup_lower_equal(test_ja, key);
 496                 if (cds_hlist_empty(&head)) {
 497                         fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 498                                 ka[i], key);
 499                         assert(0);
 500                 }
 501                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 502                 if (node->key != ka[i]) {
 503                         fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 504                                 ka[i], key, node->key);
 505                         assert(0);
 506                 }
 507                 rcu_read_unlock();
 508         }
 509
 510         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 511                 struct cds_hlist_head head;
 512                 struct ja_test_node *node;
 513
 514                 key = ka[i];    /* without offset */
 515                 rcu_read_lock();
 516                 head = cds_ja_lookup_lower_equal(test_ja, key);
 517                 if (cds_hlist_empty(&head)) {
 518                         fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 519                                 ka[i], key);
 520                         assert(0);
 521                 }
 522                 node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 523                 if (node->key != ka[i]) {
 524                         fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 525                                 ka[i], key, node->key);
 526                         assert(0);
 527                 }
 528                 rcu_read_unlock();
 529         }
 530
 531         printf("OK\n");
 532
 533         ret = cds_ja_destroy(test_ja, rcu_free_node);
 534         if (ret) {
 535                 fprintf(stderr, "Error destroying judy array\n");
 536                 return -1;
 537         }
 538         return 0;
 539 }
 540
 541 /*
 542  * nr_dup is number of nodes per key.
 543  */
 544 static
 545 int test_sparse_key(unsigned int bits, int nr_dup)
 546 {
 547         uint64_t key, max_key;
 548         int zerocount, i, ret;
 549
 550         if (bits == 64)
 551                 max_key = UINT64_MAX;
 552         else
 553                 max_key = (1ULL << bits) - 1;
 554
 555         printf("Sparse key test begins for %u-bit keys\n", bits);
 556         /* Test with 16-bit key */
 557         test_ja = cds_ja_new(bits);
 558         if (!test_ja) {
 559                 printf("Error allocating judy array.\n");
 560                 return -1;
 561         }
 562
 563         /* Add keys */
 564         printf("Test #1: add keys (%u-bit).\n", bits);
 565         for (i = 0; i < nr_dup; i++) {
 566                 zerocount = 0;
 567                 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 568                         struct ja_test_node *node = node_alloc();
 569
 570                         ja_test_node_init(node, key);
 571                         rcu_read_lock();
 572                         ret = cds_ja_add(test_ja, key, &node->node);
 573                         rcu_read_unlock();
 574                         if (ret) {
 575                                 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 576                                         ret, key);
 577                                 assert(0);
 578                         }
 579                         if (key == 0)
 580                                 zerocount++;
 581                 }
 582         }
 583         printf("OK\n");
 584
 585         printf("Test #2: successful key lookup (%u-bit).\n", bits);
 586         zerocount = 0;
 587         for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 588                 struct cds_hlist_head head;
 589                 struct ja_test_node *node;
 590                 struct cds_hlist_node *pos;
 591                 int count = 0;
 592
 593                 rcu_read_lock();
 594                 head = cds_ja_lookup(test_ja, key);
 595                 if (cds_hlist_empty(&head)) {
 596                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 597                         assert(0);
 598                 }
 599                 cds_hlist_for_each_entry_rcu(node, pos, &head, node.list) {
 600                         count++;
 601                 }
 602                 if (count != nr_dup) {
 603                         fprintf(stderr, "Unexpected number of match for key %" PRIu64 ", expected %d, got %d.\n", key, nr_dup, count);
 604                 }
 605                 rcu_read_unlock();
 606                 if (key == 0)
 607                         zerocount++;
 608         }
 609         printf("OK\n");
 610         if (bits > 8) {
 611                 printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits);
 612                 zerocount = 0;
 613                 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 614                         struct cds_hlist_head head;
 615
 616                         rcu_read_lock();
 617                         head = cds_ja_lookup(test_ja, key + 42);
 618                         if (!cds_hlist_empty(&head)) {
 619                                 fprintf(stderr,
 620                                         "Error unexpected lookup node %" PRIu64 "\n",
 621                                         key + 42);
 622                                 assert(0);
 623                         }
 624                         rcu_read_unlock();
 625                         if (key == 0)
 626                                 zerocount++;
 627                 }
 628                 printf("OK\n");
 629         }
 630         printf("Test #4: remove keys (%u-bit).\n", bits);
 631         zerocount = 0;
 632         for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 633                 struct cds_hlist_head head;
 634                 struct ja_test_node *node;
 635                 struct cds_hlist_node *pos;
 636                 int count = 0;
 637
 638                 rcu_read_lock();
 639                 head = cds_ja_lookup(test_ja, key);
 640
 641
 642                 cds_hlist_for_each_entry_rcu(node, pos, &head, node.list) {
 643                         struct cds_hlist_head testhead;
 644
 645                         count++;
 646                         if (!node) {
 647                                 fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 648                                 assert(0);
 649                         }
 650                         ret = cds_ja_del(test_ja, key, &node->node);
 651                         if (ret) {
 652                                 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 653                                 assert(0);
 654                         }
 655                         rcu_free_test_node(node);
 656                         testhead = cds_ja_lookup(test_ja, key);
 657                         if (count < nr_dup && cds_hlist_empty(&testhead)) {
 658                                 fprintf(stderr, "Error: no node found after deletion of some nodes of a key\n");
 659                                 assert(0);
 660                         }
 661                 }
 662                 head = cds_ja_lookup(test_ja, key);
 663                 if (!cds_hlist_empty(&head)) {
 664                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, head.next);
 665                         assert(0);
 666                 }
 667                 rcu_read_unlock();
 668                 if (key == 0)
 669                         zerocount++;
 670         }
 671         printf("OK\n");
 672
 673         ret = cds_ja_destroy(test_ja, rcu_free_node);
 674         if (ret) {
 675                 fprintf(stderr, "Error destroying judy array\n");
 676                 return -1;
 677         }
 678         printf("Test ends\n");
 679
 680         return 0;
 681 }
 682
 683 static
 684 int do_sanity_test(void)
 685 {
 686         int i, j, ret;
 687
 688         printf("Sanity test start.\n");
 689
 690         for (i = 0; i < 3; i++) {
 691                 ret = test_8bit_key();
 692                 if (ret) {
 693                         return ret;
 694                 }
 695                 rcu_quiescent_state();
 696         }
 697         ret = test_16bit_key();
 698         if (ret) {
 699                 return ret;
 700         }
 701         rcu_quiescent_state();
 702
 703         /* key bits */
 704         for (i = 8; i <= 64; i *= 2) {
 705                 /* nr of nodes per key */
 706                 for (j = 1; j < 4; j++) {
 707                         ret = test_sparse_key(i, j);
 708                         if (ret) {
 709                                 return ret;
 710                         }
 711                         rcu_quiescent_state();
 712                 }
 713         }
 714         printf("Sanity test end.\n");
 715
 716         return 0;
 717 }
 718
 719 enum urcu_ja_addremove {
 720         AR_RANDOM = 0,
 721         AR_ADD = 1,
 722         AR_REMOVE = -1,
 723 };      /* 1: add, -1 remove, 0: random */
 724
 725 static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
 726
 727 static
 728 void test_ja_rw_sigusr1_handler(int signo)
 729 {
 730         switch (addremove) {
 731         case AR_ADD:
 732                 printf("Add/Remove: random.\n");
 733                 addremove = AR_RANDOM;
 734                 break;
 735         case AR_RANDOM:
 736                 printf("Add/Remove: remove only.\n");
 737                 addremove = AR_REMOVE;
 738                 break;
 739         case AR_REMOVE:
 740                 printf("Add/Remove: add only.\n");
 741                 addremove = AR_ADD;
 742                 break;
 743         }
 744 }
 745
 746 static
 747 void *test_ja_rw_thr_reader(void *_count)
 748 {
 749         unsigned long long *count = _count;
 750         struct cds_hlist_head head;
 751         uint64_t key;
 752
 753         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 754                         "reader", pthread_self(), (unsigned long) gettid());
 755
 756         set_affinity();
 757
 758         rcu_register_thread();
 759
 760         while (!test_go)
 761         {
 762         }
 763         cmm_smp_mb();
 764
 765         for (;;) {
 766                 rcu_read_lock();
 767
 768                 /* note: only looking up ulong keys */
 769                 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
 770                 key *= key_mul;
 771                 head = cds_ja_lookup(test_ja, key);
 772                 if (cds_hlist_empty(&head)) {
 773                         if (validate_lookup) {
 774                                 printf("[ERROR] Lookup cannot find initial node.\n");
 775                                 exit(-1);
 776                         }
 777                         URCU_TLS(lookup_fail)++;
 778                 } else {
 779                         URCU_TLS(lookup_ok)++;
 780                 }
 781                 rcu_debug_yield_read();
 782                 if (caa_unlikely(rduration))
 783                         loop_sleep(rduration);
 784                 rcu_read_unlock();
 785                 URCU_TLS(nr_reads)++;
 786                 if (caa_unlikely(!test_duration_read()))
 787                         break;
 788                 if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
 789                         rcu_quiescent_state();
 790         }
 791
 792         rcu_unregister_thread();
 793
 794         *count = URCU_TLS(nr_reads);
 795         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 796                         "reader", pthread_self(), (unsigned long) gettid());
 797         printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
 798                         pthread_self(), URCU_TLS(lookup_fail),
 799                         URCU_TLS(lookup_ok));
 800         return ((void*)1);
 801 }
 802
 803 static
 804 int is_add(void)
 805 {
 806         return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
 807 }
 808
 809 static
 810 void *test_ja_rw_thr_writer(void *_count)
 811 {
 812         struct wr_count *count = _count;
 813         struct cds_hlist_head head;
 814         uint64_t key;
 815         int ret;
 816
 817         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 818                         "writer", pthread_self(), (unsigned long) gettid());
 819
 820         set_affinity();
 821
 822         rcu_register_thread();
 823
 824         while (!test_go)
 825         {
 826         }
 827         cmm_smp_mb();
 828
 829         for (;;) {
 830                 if ((addremove == AR_ADD)
 831                                 || (addremove == AR_RANDOM && is_add())) {
 832                         struct ja_test_node *node = node_alloc();
 833                         struct cds_ja_node *ret_node;
 834
 835                         /* note: only inserting ulong keys */
 836                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 837                         key *= key_mul;
 838                         ja_test_node_init(node, key);
 839                         rcu_read_lock();
 840                         if (add_unique) {
 841                                 ret_node = cds_ja_add_unique(test_ja, key, &node->node);
 842                                 if (ret_node != &node->node) {
 843                                         free_node(node);
 844                                         URCU_TLS(nr_addexist)++;
 845                                 } else {
 846                                         URCU_TLS(nr_add)++;
 847                                 }
 848                         } else if (add_replace) {
 849                                 assert(0);      /* not implemented yet. */
 850                         } else {
 851                                 ret = cds_ja_add(test_ja, key, &node->node);
 852                                 if (ret) {
 853                                         fprintf(stderr, "Error in cds_ja_add: %d\n", ret);
 854                                         free_node(node);
 855                                 } else {
 856                                         URCU_TLS(nr_add)++;
 857                                 }
 858                         }
 859                         rcu_read_unlock();
 860                 } else {
 861                         struct ja_test_node *node;
 862
 863                         /* May delete */
 864                         /* note: only deleting ulong keys */
 865                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 866                         key *= key_mul;
 867
 868                         rcu_read_lock();
 869
 870                         head = cds_ja_lookup(test_ja, key);
 871                         node = cds_hlist_first_entry_rcu(&head, struct ja_test_node, node.list);
 872                         if (node) {
 873                                 ret = cds_ja_del(test_ja, key, &node->node);
 874                                 if (!ret) {
 875                                         rcu_free_test_node(node);
 876                                         URCU_TLS(nr_del)++;
 877                                 } else {
 878                                         URCU_TLS(nr_delnoent)++;
 879                                 }
 880                         } else {
 881                                 URCU_TLS(nr_delnoent)++;
 882                         }
 883                         rcu_read_unlock();
 884                 }
 885
 886                 URCU_TLS(nr_writes)++;
 887                 if (caa_unlikely(!test_duration_write()))
 888                         break;
 889                 if (caa_unlikely(wdelay))
 890                         loop_sleep(wdelay);
 891                 if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
 892                         rcu_quiescent_state();
 893         }
 894
 895         rcu_unregister_thread();
 896
 897         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 898                         "writer", pthread_self(), (unsigned long) gettid());
 899         printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
 900                         "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
 901                         URCU_TLS(nr_addexist), URCU_TLS(nr_del),
 902                         URCU_TLS(nr_delnoent));
 903         count->update_ops = URCU_TLS(nr_writes);
 904         count->add = URCU_TLS(nr_add);
 905         count->add_exist = URCU_TLS(nr_addexist);
 906         count->remove = URCU_TLS(nr_del);
 907         return ((void*)2);
 908 }
 909
 910 static
 911 int do_mt_populate_ja(void)
 912 {
 913         struct cds_hlist_head head;
 914         uint64_t iter;
 915         int ret;
 916
 917         if (!init_populate)
 918                 return 0;
 919
 920         printf("Starting rw test\n");
 921
 922         for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
 923                 struct ja_test_node *node = node_alloc();
 924                 uint64_t key;
 925
 926                 /* note: only inserting ulong keys */
 927                 key = (unsigned long) iter;
 928                 key *= key_mul;
 929                 ja_test_node_init(node, key);
 930                 rcu_read_lock();
 931                 ret = cds_ja_add(test_ja, key, &node->node);
 932                 URCU_TLS(nr_add)++;
 933                 URCU_TLS(nr_writes)++;
 934                 rcu_read_unlock();
 935                 if (ret) {
 936                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 937                                 ret, key);
 938                         assert(0);
 939                 }
 940         }
 941         return 0;
 942 }
 943
 944 static
 945 int do_mt_test(void)
 946 {
 947         pthread_t *tid_reader, *tid_writer;
 948         void *tret;
 949         int ret, i, err;
 950         unsigned long long *count_reader;
 951         struct wr_count *count_writer;
 952         unsigned long long tot_reads = 0, tot_writes = 0,
 953                 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
 954         unsigned int remain;
 955
 956         tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
 957         tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
 958         count_reader = malloc(sizeof(*count_reader) * nr_readers);
 959         count_writer = malloc(sizeof(*count_writer) * nr_writers);
 960
 961         printf("Allocating Judy Array for %u-bit keys\n", key_bits);
 962         test_ja = cds_ja_new(key_bits);
 963         if (!test_ja) {
 964                 printf("Error allocating judy array.\n");
 965                 ret = -1;
 966                 goto end;
 967         }
 968
 969         do_mt_populate_ja();
 970
 971         next_aff = 0;
 972
 973         for (i = 0; i < nr_readers; i++) {
 974                 err = pthread_create(&tid_reader[i],
 975                                      NULL, test_ja_rw_thr_reader,
 976                                      &count_reader[i]);
 977                 if (err != 0)
 978                         exit(1);
 979         }
 980         for (i = 0; i < nr_writers; i++) {
 981                 err = pthread_create(&tid_writer[i],
 982                                      NULL, test_ja_rw_thr_writer,
 983                                      &count_writer[i]);
 984                 if (err != 0)
 985                         exit(1);
 986         }
 987
 988         cmm_smp_mb();
 989
 990         test_go = 1;
 991
 992         rcu_thread_offline_qsbr();
 993
 994         remain = duration;
 995         do {
 996                 remain = sleep(remain);
 997         } while (remain > 0);
 998
 999         test_stop = 1;
1000
1001         for (i = 0; i < nr_readers; i++) {
1002                 err = pthread_join(tid_reader[i], &tret);
1003                 if (err != 0)
1004                         exit(1);
1005                 tot_reads += count_reader[i];
1006         }
1007         for (i = 0; i < nr_writers; i++) {
1008                 err = pthread_join(tid_writer[i], &tret);
1009                 if (err != 0)
1010                         exit(1);
1011                 tot_writes += count_writer[i].update_ops;
1012                 tot_add += count_writer[i].add;
1013                 tot_add_exist += count_writer[i].add_exist;
1014                 tot_remove += count_writer[i].remove;
1015         }
1016         rcu_thread_online_qsbr();
1017
1018         ret = cds_ja_destroy(test_ja, rcu_free_node);
1019         if (ret) {
1020                 fprintf(stderr, "Error destroying judy array\n");
1021                 goto end;
1022         }
1023
1024         free(tid_reader);
1025         free(tid_writer);
1026         free(count_reader);
1027         free(count_writer);
1028         ret = 0;
1029 end:
1030         return ret;
1031 }
1032
1033 static
1034 int check_memory_leaks(void)
1035 {
1036         unsigned long na, nf;
1037
1038         na = uatomic_read(&test_nodes_allocated);
1039         nf = uatomic_read(&test_nodes_freed);
1040         if (na != nf) {
1041                 fprintf(stderr, "Memory leak of %ld test nodes detected. Allocated: %lu, freed: %lu\n",
1042                         na - nf, na, nf);
1043                 return -1;
1044         }
1045         return 0;
1046 }
1047
1048 int main(int argc, char **argv)
1049 {
1050         int i, j, a, ret, err;
1051         uint64_t key;
1052         struct sigaction act;
1053
1054         if (argc < 4) {
1055                 show_usage(argc, argv);
1056                 return -1;
1057         }
1058
1059         err = sscanf(argv[1], "%u", &nr_readers);
1060         if (err != 1) {
1061                 show_usage(argc, argv);
1062                 return -1;
1063         }
1064
1065         err = sscanf(argv[2], "%u", &nr_writers);
1066         if (err != 1) {
1067                 show_usage(argc, argv);
1068                 return -1;
1069         }
1070
1071         err = sscanf(argv[3], "%lu", &duration);
1072         if (err != 1) {
1073                 show_usage(argc, argv);
1074                 return -1;
1075         }
1076
1077         for (i = 4; i < argc; i++) {
1078                 if (argv[i][0] != '-')
1079                         continue;
1080                 switch (argv[i][1]) {
1081 #ifdef DEBUG_YIELD
1082                 case 'r':
1083                         yield_active |= YIELD_READ;
1084                         break;
1085                 case 'w':
1086                         yield_active |= YIELD_WRITE;
1087                         break;
1088 #endif
1089                 case 'a':
1090                         if (argc < i + 2) {
1091                                 show_usage(argc, argv);
1092                                 return -1;
1093                         }
1094                         a = atoi(argv[++i]);
1095                         cpu_affinities[next_aff++] = a;
1096                         use_affinity = 1;
1097                         printf_verbose("Adding CPU %d affinity\n", a);
1098                         break;
1099                 case 'c':
1100                         if (argc < i + 2) {
1101                                 show_usage(argc, argv);
1102                                 return -1;
1103                         }
1104                         rduration = atol(argv[++i]);
1105                         break;
1106                 case 'd':
1107                         if (argc < i + 2) {
1108                                 show_usage(argc, argv);
1109                                 return -1;
1110                         }
1111                         wdelay = atol(argv[++i]);
1112                         break;
1113                 case 'v':
1114                         verbose_mode = 1;
1115                         break;
1116                 case 'r':
1117                         add_ratio = atoi(argv[++i]);
1118                         break;
1119                 case 'k':
1120                         init_populate = 1;
1121                         break;
1122                 case 'R':
1123                         lookup_pool_offset = atol(argv[++i]);
1124                         break;
1125                 case 'S':
1126                         write_pool_offset = atol(argv[++i]);
1127                         break;
1128                 case 'T':
1129                         init_pool_offset = atol(argv[++i]);
1130                         break;
1131                 case 'M':
1132                         lookup_pool_size = atol(argv[++i]);
1133                         break;
1134                 case 'N':
1135                         write_pool_size = atol(argv[++i]);
1136                         break;
1137                 case 'O':
1138                         init_pool_size = atol(argv[++i]);
1139                         break;
1140                 case 'V':
1141                         validate_lookup = 1;
1142                         break;
1143                 case 't':
1144                         sanity_test = 1;
1145                         break;
1146                 case 'B':
1147                         key_bits = atol(argv[++i]);
1148                         break;
1149                 case 'm':
1150                         key_mul = atoll(argv[++i]);
1151                         break;
1152                 case 'u':
1153                         add_unique = 1;
1154                         break;
1155                 case 's':
1156                         add_replace = 1;
1157                         break;
1158                 case 'l':
1159                         leak_detection = 1;
1160                         break;
1161                 }
1162         }
1163
1164         printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
1165                 duration, nr_readers, nr_writers);
1166         printf_verbose("Writer delay : %lu loops.\n", wdelay);
1167         printf_verbose("Reader duration : %lu loops.\n", rduration);
1168         printf_verbose("Add ratio: %u%%.\n", add_ratio);
1169         printf_verbose("Mode:%s%s.\n",
1170                 " add/remove",
1171                 add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
1172         printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
1173         printf_verbose("Init pool size offset %lu size %lu.\n",
1174                 init_pool_offset, init_pool_size);
1175         printf_verbose("Lookup pool size offset %lu size %lu.\n",
1176                 lookup_pool_offset, lookup_pool_size);
1177         printf_verbose("Update pool size offset %lu size %lu.\n",
1178                 write_pool_offset, write_pool_size);
1179         if (validate_lookup)
1180                 printf_verbose("Validating lookups.\n");
1181         if (leak_detection)
1182                 printf_verbose("Memory leak dection activated.\n");
1183         printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
1184                         "main", pthread_self(), (unsigned long)gettid());
1185
1186         memset(&act, 0, sizeof(act));
1187         ret = sigemptyset(&act.sa_mask);
1188         if (ret == -1) {
1189                 perror("sigemptyset");
1190                 return -1;
1191         }
1192         act.sa_handler = test_ja_rw_sigusr1_handler;
1193         act.sa_flags = SA_RESTART;
1194         ret = sigaction(SIGUSR1, &act, NULL);
1195         if (ret == -1) {
1196                 perror("sigaction");
1197                 return -1;
1198         }
1199
1200         err = create_all_cpu_call_rcu_data(0);
1201         if (err) {
1202                 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
1203         }
1204
1205         rcu_register_thread();
1206
1207         if (sanity_test) {
1208                 ret = do_sanity_test();
1209         } else {
1210                 ret = do_mt_test();
1211         }
1212
1213         /* Wait for in-flight call_rcu free to complete for leak detection */
1214         rcu_barrier();
1215
1216         ret |= check_memory_leaks();
1217
1218         rcu_unregister_thread();
1219         free_all_cpu_call_rcu_data();
1220
1221         if (ret) {
1222                 printf("Test ended with error: %d\n", ret);
1223         }
1224         return ret;
1225 }