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_test_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_test_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_test_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_test_node_cb);
 167 }
 168
 169 static
 170 void free_node(struct cds_ja_node *node)
 171 {
 172         struct ja_test_node *test_node = to_test_node(node);
 173
 174         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[] = { 5, 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_ja_node *node;
 261
 262                 rcu_read_lock();
 263                 node = cds_ja_lookup(test_ja, key);
 264                 if (!node) {
 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_ja_node *node;
 274
 275                 rcu_read_lock();
 276                 node = cds_ja_lookup(test_ja, key);
 277                 if (node) {
 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_ja_node *ja_node;
 289                 struct ja_test_node *node;
 290
 291                 rcu_read_lock();
 292                 ja_node = cds_ja_lookup(test_ja, key);
 293                 if (!ja_node) {
 294                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 295                         assert(0);
 296                 }
 297                 node = caa_container_of(ja_node, struct ja_test_node, node);
 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                 ja_node = cds_ja_lookup(test_ja, key);
 305                 if (ja_node) {
 306                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
 307                         assert(0);
 308                 }
 309                 rcu_read_unlock();
 310         }
 311         printf("OK\n");
 312
 313         printf("Test #5: lookup below/above 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_ja_node *ja_node;
 332                 struct ja_test_node *node;
 333
 334                 key = ka[i] + ka_test_offset;
 335                 rcu_read_lock();
 336                 ja_node = cds_ja_lookup_below_equal(test_ja, key);
 337                 if (!ja_node) {
 338                         fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 339                                 ka[i], key);
 340                         assert(0);
 341                 }
 342                 node = caa_container_of(ja_node, struct ja_test_node, node);
 343                 if (node->key != ka[i]) {
 344                         fprintf(stderr, "Error lookup below 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_ja_node *ja_node;
 353                 struct ja_test_node *node;
 354
 355                 key = ka[i] - ka_test_offset;
 356                 rcu_read_lock();
 357                 ja_node = cds_ja_lookup_above_equal(test_ja, key);
 358                 if (!ja_node) {
 359                         fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 360                                 ka[i], key);
 361                         assert(0);
 362                 }
 363                 node = caa_container_of(ja_node, struct ja_test_node, node);
 364                 if (node->key != ka[i]) {
 365                         fprintf(stderr, "Error lookup above 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         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 373                 struct cds_ja_node *ja_node;
 374                 struct ja_test_node *node;
 375
 376                 key = ka[i];    /* without offset */
 377                 rcu_read_lock();
 378                 ja_node = cds_ja_lookup_below_equal(test_ja, key);
 379                 if (!ja_node) {
 380                         fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 381                                 ka[i], key);
 382                         assert(0);
 383                 }
 384                 node = caa_container_of(ja_node, struct ja_test_node, node);
 385                 if (node->key != ka[i]) {
 386                         fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 387                                 ka[i], key, node->key);
 388                         assert(0);
 389                 }
 390
 391                 ja_node = cds_ja_lookup_above_equal(test_ja, key);
 392                 if (!ja_node) {
 393                         fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 394                                 ka[i], key);
 395                         assert(0);
 396                 }
 397                 node = caa_container_of(ja_node, struct ja_test_node, node);
 398                 if (node->key != ka[i]) {
 399                         fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 400                                 ka[i], key, node->key);
 401                         assert(0);
 402                 }
 403                 rcu_read_unlock();
 404         }
 405
 406         printf("OK\n");
 407
 408         ret = cds_ja_destroy(test_ja, free_node);
 409         if (ret) {
 410                 fprintf(stderr, "Error destroying judy array\n");
 411                 return -1;
 412         }
 413         return 0;
 414 }
 415
 416 static
 417 int test_16bit_key(void)
 418 {
 419         int ret, i;
 420         uint64_t key;
 421         uint64_t ka[] = { 105, 206, 4000, 4111, 59990, 65435 };
 422         uint64_t ka_test_offset = 100;
 423
 424         /* Test with 16-bit key */
 425         test_ja = cds_ja_new(16);
 426         if (!test_ja) {
 427                 printf("Error allocating judy array.\n");
 428                 return -1;
 429         }
 430
 431         /* Add keys */
 432         printf("Test #1: add keys (16-bit).\n");
 433         for (key = 0; key < 10000; key++) {
 434         //for (key = 0; key < 65536; key+=256) {
 435                 struct ja_test_node *node = node_alloc();
 436
 437                 ja_test_node_init(node, key);
 438                 rcu_read_lock();
 439                 ret = cds_ja_add(test_ja, key, &node->node);
 440                 rcu_read_unlock();
 441                 if (ret) {
 442                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 443                                 ret, key);
 444                         assert(0);
 445                 }
 446         }
 447         printf("OK\n");
 448
 449         printf("Test #2: successful key lookup (16-bit).\n");
 450         for (key = 0; key < 10000; key++) {
 451         //for (key = 0; key < 65536; key+=256) {
 452                 struct cds_ja_node *node;
 453
 454                 rcu_read_lock();
 455                 node = cds_ja_lookup(test_ja, key);
 456                 if (!node) {
 457                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 458                         assert(0);
 459                 }
 460                 rcu_read_unlock();
 461         }
 462         printf("OK\n");
 463         printf("Test #3: unsuccessful key lookup (16-bit).\n");
 464         for (key = 11000; key <= 11002; key++) {
 465                 struct cds_ja_node *node;
 466
 467                 rcu_read_lock();
 468                 node = cds_ja_lookup(test_ja, key);
 469                 if (node) {
 470                         fprintf(stderr,
 471                                 "Error unexpected lookup node %" PRIu64 "\n",
 472                                 key);
 473                         assert(0);
 474                 }
 475                 rcu_read_unlock();
 476         }
 477         printf("OK\n");
 478         printf("Test #4: remove keys (16-bit).\n");
 479         for (key = 0; key < 10000; key++) {
 480         //for (key = 0; key < 65536; key+=256) {
 481                 struct cds_ja_node *ja_node;
 482                 struct ja_test_node *node;
 483
 484                 rcu_read_lock();
 485                 ja_node = cds_ja_lookup(test_ja, key);
 486                 if (!ja_node) {
 487                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 488                         assert(0);
 489                 }
 490                 node = caa_container_of(ja_node, struct ja_test_node, node);
 491                 ret = cds_ja_del(test_ja, key, &node->node);
 492                 if (ret) {
 493                         fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 494                         assert(0);
 495                 }
 496                 rcu_free_test_node(node);
 497                 ja_node = cds_ja_lookup(test_ja, key);
 498                 if (ja_node) {
 499                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
 500                         assert(0);
 501                 }
 502                 rcu_read_unlock();
 503         }
 504         printf("OK\n");
 505
 506         printf("Test #5: lookup below equal (16-bit).\n");
 507
 508         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 509                 struct ja_test_node *node = node_alloc();
 510
 511                 key = ka[i];
 512                 ja_test_node_init(node, key);
 513                 rcu_read_lock();
 514                 ret = cds_ja_add(test_ja, key, &node->node);
 515                 rcu_read_unlock();
 516                 if (ret) {
 517                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 518                                 ret, key);
 519                         assert(0);
 520                 }
 521         }
 522
 523         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 524                 struct cds_ja_node *ja_node;
 525                 struct ja_test_node *node;
 526
 527                 key = ka[i] + ka_test_offset;
 528                 rcu_read_lock();
 529                 ja_node = cds_ja_lookup_below_equal(test_ja, key);
 530                 if (!ja_node) {
 531                         fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 532                                 ka[i], key);
 533                         assert(0);
 534                 }
 535                 node = caa_container_of(ja_node, struct ja_test_node, node);
 536                 if (node->key != ka[i]) {
 537                         fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 538                                 ka[i], key, node->key);
 539                         assert(0);
 540                 }
 541                 rcu_read_unlock();
 542         }
 543
 544         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 545                 struct cds_ja_node *ja_node;
 546                 struct ja_test_node *node;
 547
 548                 key = ka[i] - ka_test_offset;
 549                 rcu_read_lock();
 550                 ja_node = cds_ja_lookup_above_equal(test_ja, key);
 551                 if (!ja_node) {
 552                         fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n",
 553                                 ka[i], key);
 554                         assert(0);
 555                 }
 556                 node = caa_container_of(ja_node, struct ja_test_node, node);
 557                 if (node->key != ka[i]) {
 558                         fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 559                                 ka[i], key, node->key);
 560                         assert(0);
 561                 }
 562                 rcu_read_unlock();
 563         }
 564
 565         for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) {
 566                 struct cds_ja_node *ja_node;
 567                 struct ja_test_node *node;
 568
 569                 key = ka[i];    /* without offset */
 570                 rcu_read_lock();
 571                 ja_node = cds_ja_lookup_below_equal(test_ja, key);
 572                 if (!ja_node) {
 573                         fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n",
 574                                 ka[i], key);
 575                         assert(0);
 576                 }
 577                 node = caa_container_of(ja_node, struct ja_test_node, node);
 578                 if (node->key != ka[i]) {
 579                         fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 580                                 ka[i], key, node->key);
 581                         assert(0);
 582                 }
 583
 584                 ja_node = cds_ja_lookup_above_equal(test_ja, key);
 585                 if (!ja_node) {
 586                         fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n",
 587                                 ka[i], key);
 588                         assert(0);
 589                 }
 590                 node = caa_container_of(ja_node, struct ja_test_node, node);
 591                 if (node->key != ka[i]) {
 592                         fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n",
 593                                 ka[i], key, node->key);
 594                         assert(0);
 595                 }
 596                 rcu_read_unlock();
 597         }
 598
 599         printf("OK\n");
 600
 601         ret = cds_ja_destroy(test_ja, free_node);
 602         if (ret) {
 603                 fprintf(stderr, "Error destroying judy array\n");
 604                 return -1;
 605         }
 606         return 0;
 607 }
 608
 609 /*
 610  * nr_dup is number of nodes per key.
 611  */
 612 static
 613 int test_sparse_key(unsigned int bits, int nr_dup)
 614 {
 615         uint64_t key, max_key;
 616         int zerocount, i, ret;
 617
 618         if (bits == 64)
 619                 max_key = UINT64_MAX;
 620         else
 621                 max_key = (1ULL << bits) - 1;
 622
 623         printf("Sparse key test begins for %u-bit keys\n", bits);
 624         /* Test with 16-bit key */
 625         test_ja = cds_ja_new(bits);
 626         if (!test_ja) {
 627                 printf("Error allocating judy array.\n");
 628                 return -1;
 629         }
 630
 631         /* Add keys */
 632         printf("Test #1: add keys (%u-bit).\n", bits);
 633         for (i = 0; i < nr_dup; i++) {
 634                 zerocount = 0;
 635                 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 636                         struct ja_test_node *node = node_alloc();
 637
 638                         ja_test_node_init(node, key);
 639                         rcu_read_lock();
 640                         ret = cds_ja_add(test_ja, key, &node->node);
 641                         rcu_read_unlock();
 642                         if (ret) {
 643                                 fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 644                                         ret, key);
 645                                 assert(0);
 646                         }
 647                         if (key == 0)
 648                                 zerocount++;
 649                 }
 650         }
 651         printf("OK\n");
 652
 653         printf("Test #2: successful key lookup (%u-bit).\n", bits);
 654         zerocount = 0;
 655         for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 656                 struct cds_ja_node *ja_node;
 657                 struct ja_test_node *node;
 658                 int count = 0;
 659
 660                 rcu_read_lock();
 661                 ja_node = cds_ja_lookup(test_ja, key);
 662                 if (!ja_node) {
 663                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 664                         assert(0);
 665                 }
 666                 cds_ja_for_each_duplicate_rcu(ja_node) {
 667                         count++;
 668                 }
 669                 if (count != nr_dup) {
 670                         fprintf(stderr, "Unexpected number of match for key %" PRIu64 ", expected %d, got %d.\n", key, nr_dup, count);
 671                 }
 672                 rcu_read_unlock();
 673                 if (key == 0)
 674                         zerocount++;
 675         }
 676         printf("OK\n");
 677         if (bits > 8) {
 678                 printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits);
 679                 zerocount = 0;
 680                 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 681                         struct cds_ja_node *ja_node;
 682
 683                         rcu_read_lock();
 684                         ja_node = cds_ja_lookup(test_ja, key + 42);
 685                         if (ja_node) {
 686                                 fprintf(stderr,
 687                                         "Error unexpected lookup node %" PRIu64 "\n",
 688                                         key + 42);
 689                                 assert(0);
 690                         }
 691                         rcu_read_unlock();
 692                         if (key == 0)
 693                                 zerocount++;
 694                 }
 695                 printf("OK\n");
 696         }
 697         printf("Test #4: remove keys (%u-bit).\n", bits);
 698         zerocount = 0;
 699         for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 700                 struct cds_ja_node *ja_node;
 701                 int count = 0;
 702
 703                 rcu_read_lock();
 704                 ja_node = cds_ja_lookup(test_ja, key);
 705
 706                 cds_ja_for_each_duplicate_rcu(ja_node) {
 707                         struct cds_ja_node *test_ja_node;
 708                         struct ja_test_node *node;
 709
 710                         count++;
 711                         node = caa_container_of(ja_node,
 712                                 struct ja_test_node, node);
 713                         ret = cds_ja_del(test_ja, key, &node->node);
 714                         if (ret) {
 715                                 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 716                                 assert(0);
 717                         }
 718                         rcu_free_test_node(node);
 719                         test_ja_node = cds_ja_lookup(test_ja, key);
 720                         if (count < nr_dup && !test_ja_node) {
 721                                 fprintf(stderr, "Error: no node found after deletion of some nodes of a key\n");
 722                                 assert(0);
 723                         }
 724                 }
 725                 ja_node = cds_ja_lookup(test_ja, key);
 726                 if (ja_node) {
 727                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
 728                         assert(0);
 729                 }
 730                 rcu_read_unlock();
 731                 if (key == 0)
 732                         zerocount++;
 733         }
 734         printf("OK\n");
 735
 736         ret = cds_ja_destroy(test_ja, free_node);
 737         if (ret) {
 738                 fprintf(stderr, "Error destroying judy array\n");
 739                 return -1;
 740         }
 741         printf("Test ends\n");
 742
 743         return 0;
 744 }
 745
 746 static
 747 int do_sanity_test(void)
 748 {
 749         int i, j, ret;
 750
 751         printf("Sanity test start.\n");
 752
 753         for (i = 0; i < 3; i++) {
 754                 ret = test_8bit_key();
 755                 if (ret) {
 756                         return ret;
 757                 }
 758                 rcu_quiescent_state();
 759         }
 760         ret = test_16bit_key();
 761         if (ret) {
 762                 return ret;
 763         }
 764         rcu_quiescent_state();
 765
 766         /* key bits */
 767         for (i = 8; i <= 64; i *= 2) {
 768                 /* nr of nodes per key */
 769                 for (j = 1; j < 4; j++) {
 770                         ret = test_sparse_key(i, j);
 771                         if (ret) {
 772                                 return ret;
 773                         }
 774                         rcu_quiescent_state();
 775                 }
 776         }
 777         printf("Sanity test end.\n");
 778
 779         return 0;
 780 }
 781
 782 enum urcu_ja_addremove {
 783         AR_RANDOM = 0,
 784         AR_ADD = 1,
 785         AR_REMOVE = -1,
 786 };      /* 1: add, -1 remove, 0: random */
 787
 788 static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
 789
 790 static
 791 void test_ja_rw_sigusr1_handler(int signo)
 792 {
 793         switch (addremove) {
 794         case AR_ADD:
 795                 printf("Add/Remove: random.\n");
 796                 addremove = AR_RANDOM;
 797                 break;
 798         case AR_RANDOM:
 799                 printf("Add/Remove: remove only.\n");
 800                 addremove = AR_REMOVE;
 801                 break;
 802         case AR_REMOVE:
 803                 printf("Add/Remove: add only.\n");
 804                 addremove = AR_ADD;
 805                 break;
 806         }
 807 }
 808
 809 static
 810 void *test_ja_rw_thr_reader(void *_count)
 811 {
 812         unsigned long long *count = _count;
 813         struct cds_ja_node *ja_node;
 814         uint64_t key;
 815
 816         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 817                         "reader", pthread_self(), (unsigned long) gettid());
 818
 819         set_affinity();
 820
 821         rcu_register_thread();
 822
 823         while (!test_go)
 824         {
 825         }
 826         cmm_smp_mb();
 827
 828         for (;;) {
 829                 rcu_read_lock();
 830
 831                 /* note: only looking up ulong keys */
 832                 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
 833                 key *= key_mul;
 834                 ja_node = cds_ja_lookup(test_ja, key);
 835                 if (!ja_node) {
 836                         if (validate_lookup) {
 837                                 printf("[ERROR] Lookup cannot find initial node.\n");
 838                                 exit(-1);
 839                         }
 840                         URCU_TLS(lookup_fail)++;
 841                 } else {
 842                         URCU_TLS(lookup_ok)++;
 843                 }
 844                 rcu_debug_yield_read();
 845                 if (caa_unlikely(rduration))
 846                         loop_sleep(rduration);
 847                 rcu_read_unlock();
 848                 URCU_TLS(nr_reads)++;
 849                 if (caa_unlikely(!test_duration_read()))
 850                         break;
 851                 if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
 852                         rcu_quiescent_state();
 853         }
 854
 855         rcu_unregister_thread();
 856
 857         *count = URCU_TLS(nr_reads);
 858         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 859                         "reader", pthread_self(), (unsigned long) gettid());
 860         printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
 861                         pthread_self(), URCU_TLS(lookup_fail),
 862                         URCU_TLS(lookup_ok));
 863         return ((void*)1);
 864 }
 865
 866 static
 867 int is_add(void)
 868 {
 869         return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
 870 }
 871
 872 static
 873 void *test_ja_rw_thr_writer(void *_count)
 874 {
 875         struct wr_count *count = _count;
 876         uint64_t key;
 877         int ret;
 878
 879         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 880                         "writer", pthread_self(), (unsigned long) gettid());
 881
 882         set_affinity();
 883
 884         rcu_register_thread();
 885
 886         while (!test_go)
 887         {
 888         }
 889         cmm_smp_mb();
 890
 891         for (;;) {
 892                 if ((addremove == AR_ADD)
 893                                 || (addremove == AR_RANDOM && is_add())) {
 894                         struct ja_test_node *node = node_alloc();
 895                         struct cds_ja_node *ret_node;
 896
 897                         /* note: only inserting ulong keys */
 898                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 899                         key *= key_mul;
 900                         ja_test_node_init(node, key);
 901                         rcu_read_lock();
 902                         if (add_unique) {
 903                                 ret_node = cds_ja_add_unique(test_ja, key, &node->node);
 904                                 if (ret_node != &node->node) {
 905                                         free_test_node(node);
 906                                         URCU_TLS(nr_addexist)++;
 907                                 } else {
 908                                         URCU_TLS(nr_add)++;
 909                                 }
 910                         } else if (add_replace) {
 911                                 assert(0);      /* not implemented yet. */
 912                         } else {
 913                                 ret = cds_ja_add(test_ja, key, &node->node);
 914                                 if (ret) {
 915                                         fprintf(stderr, "Error in cds_ja_add: %d\n", ret);
 916                                         free_test_node(node);
 917                                 } else {
 918                                         URCU_TLS(nr_add)++;
 919                                 }
 920                         }
 921                         rcu_read_unlock();
 922                 } else {
 923                         struct cds_ja_node *ja_node;
 924                         struct ja_test_node *node;
 925
 926                         /* May delete */
 927                         /* note: only deleting ulong keys */
 928                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 929                         key *= key_mul;
 930
 931                         rcu_read_lock();
 932
 933                         ja_node = cds_ja_lookup(test_ja, key);
 934                         /* Remove first entry */
 935                         if (ja_node) {
 936                                 node = caa_container_of(ja_node,
 937                                         struct ja_test_node, node);
 938                                 ret = cds_ja_del(test_ja, key, &node->node);
 939                                 if (!ret) {
 940                                         rcu_free_test_node(node);
 941                                         URCU_TLS(nr_del)++;
 942                                 } else {
 943                                         URCU_TLS(nr_delnoent)++;
 944                                 }
 945                         } else {
 946                                 URCU_TLS(nr_delnoent)++;
 947                         }
 948                         rcu_read_unlock();
 949                 }
 950
 951                 URCU_TLS(nr_writes)++;
 952                 if (caa_unlikely(!test_duration_write()))
 953                         break;
 954                 if (caa_unlikely(wdelay))
 955                         loop_sleep(wdelay);
 956                 if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
 957                         rcu_quiescent_state();
 958         }
 959
 960         rcu_unregister_thread();
 961
 962         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 963                         "writer", pthread_self(), (unsigned long) gettid());
 964         printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
 965                         "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
 966                         URCU_TLS(nr_addexist), URCU_TLS(nr_del),
 967                         URCU_TLS(nr_delnoent));
 968         count->update_ops = URCU_TLS(nr_writes);
 969         count->add = URCU_TLS(nr_add);
 970         count->add_exist = URCU_TLS(nr_addexist);
 971         count->remove = URCU_TLS(nr_del);
 972         return ((void*)2);
 973 }
 974
 975 static
 976 int do_mt_populate_ja(void)
 977 {
 978         uint64_t iter;
 979         int ret;
 980
 981         if (!init_populate)
 982                 return 0;
 983
 984         printf("Starting rw test\n");
 985
 986         for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
 987                 struct ja_test_node *node = node_alloc();
 988                 uint64_t key;
 989
 990                 /* note: only inserting ulong keys */
 991                 key = (unsigned long) iter;
 992                 key *= key_mul;
 993                 ja_test_node_init(node, key);
 994                 rcu_read_lock();
 995                 ret = cds_ja_add(test_ja, key, &node->node);
 996                 URCU_TLS(nr_add)++;
 997                 URCU_TLS(nr_writes)++;
 998                 rcu_read_unlock();
 999                 if (ret) {
1000                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
1001                                 ret, key);
1002                         assert(0);
1003                 }
1004         }
1005         return 0;
1006 }
1007
1008 static
1009 int do_mt_test(void)
1010 {
1011         pthread_t *tid_reader, *tid_writer;
1012         void *tret;
1013         int ret, i, err;
1014         unsigned long long *count_reader;
1015         struct wr_count *count_writer;
1016         unsigned long long tot_reads = 0, tot_writes = 0,
1017                 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
1018         unsigned int remain;
1019
1020         tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
1021         tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
1022         count_reader = malloc(sizeof(*count_reader) * nr_readers);
1023         count_writer = malloc(sizeof(*count_writer) * nr_writers);
1024
1025         printf("Allocating Judy Array for %u-bit keys\n", key_bits);
1026         test_ja = cds_ja_new(key_bits);
1027         if (!test_ja) {
1028                 printf("Error allocating judy array.\n");
1029                 ret = -1;
1030                 goto end;
1031         }
1032
1033         do_mt_populate_ja();
1034
1035         next_aff = 0;
1036
1037         for (i = 0; i < nr_readers; i++) {
1038                 err = pthread_create(&tid_reader[i],
1039                                      NULL, test_ja_rw_thr_reader,
1040                                      &count_reader[i]);
1041                 if (err != 0)
1042                         exit(1);
1043         }
1044         for (i = 0; i < nr_writers; i++) {
1045                 err = pthread_create(&tid_writer[i],
1046                                      NULL, test_ja_rw_thr_writer,
1047                                      &count_writer[i]);
1048                 if (err != 0)
1049                         exit(1);
1050         }
1051
1052         cmm_smp_mb();
1053
1054         test_go = 1;
1055
1056         rcu_thread_offline_qsbr();
1057
1058         remain = duration;
1059         do {
1060                 remain = sleep(remain);
1061         } while (remain > 0);
1062
1063         test_stop = 1;
1064
1065         for (i = 0; i < nr_readers; i++) {
1066                 err = pthread_join(tid_reader[i], &tret);
1067                 if (err != 0)
1068                         exit(1);
1069                 tot_reads += count_reader[i];
1070         }
1071         for (i = 0; i < nr_writers; i++) {
1072                 err = pthread_join(tid_writer[i], &tret);
1073                 if (err != 0)
1074                         exit(1);
1075                 tot_writes += count_writer[i].update_ops;
1076                 tot_add += count_writer[i].add;
1077                 tot_add_exist += count_writer[i].add_exist;
1078                 tot_remove += count_writer[i].remove;
1079         }
1080         rcu_thread_online_qsbr();
1081
1082         ret = cds_ja_destroy(test_ja, free_node);
1083         if (ret) {
1084                 fprintf(stderr, "Error destroying judy array\n");
1085                 goto end;
1086         }
1087
1088         free(tid_reader);
1089         free(tid_writer);
1090         free(count_reader);
1091         free(count_writer);
1092         ret = 0;
1093 end:
1094         return ret;
1095 }
1096
1097 static
1098 int check_memory_leaks(void)
1099 {
1100         unsigned long na, nf;
1101
1102         na = uatomic_read(&test_nodes_allocated);
1103         nf = uatomic_read(&test_nodes_freed);
1104         if (na != nf) {
1105                 fprintf(stderr, "Memory leak of %ld test nodes detected. Allocated: %lu, freed: %lu\n",
1106                         na - nf, na, nf);
1107                 return -1;
1108         }
1109         return 0;
1110 }
1111
1112 int main(int argc, char **argv)
1113 {
1114         int i, j, a, ret, err;
1115         uint64_t key;
1116         struct sigaction act;
1117
1118         if (argc < 4) {
1119                 show_usage(argc, argv);
1120                 return -1;
1121         }
1122
1123         err = sscanf(argv[1], "%u", &nr_readers);
1124         if (err != 1) {
1125                 show_usage(argc, argv);
1126                 return -1;
1127         }
1128
1129         err = sscanf(argv[2], "%u", &nr_writers);
1130         if (err != 1) {
1131                 show_usage(argc, argv);
1132                 return -1;
1133         }
1134
1135         err = sscanf(argv[3], "%lu", &duration);
1136         if (err != 1) {
1137                 show_usage(argc, argv);
1138                 return -1;
1139         }
1140
1141         for (i = 4; i < argc; i++) {
1142                 if (argv[i][0] != '-')
1143                         continue;
1144                 switch (argv[i][1]) {
1145 #ifdef DEBUG_YIELD
1146                 case 'r':
1147                         yield_active |= YIELD_READ;
1148                         break;
1149                 case 'w':
1150                         yield_active |= YIELD_WRITE;
1151                         break;
1152 #endif
1153                 case 'a':
1154                         if (argc < i + 2) {
1155                                 show_usage(argc, argv);
1156                                 return -1;
1157                         }
1158                         a = atoi(argv[++i]);
1159                         cpu_affinities[next_aff++] = a;
1160                         use_affinity = 1;
1161                         printf_verbose("Adding CPU %d affinity\n", a);
1162                         break;
1163                 case 'c':
1164                         if (argc < i + 2) {
1165                                 show_usage(argc, argv);
1166                                 return -1;
1167                         }
1168                         rduration = atol(argv[++i]);
1169                         break;
1170                 case 'd':
1171                         if (argc < i + 2) {
1172                                 show_usage(argc, argv);
1173                                 return -1;
1174                         }
1175                         wdelay = atol(argv[++i]);
1176                         break;
1177                 case 'v':
1178                         verbose_mode = 1;
1179                         break;
1180                 case 'r':
1181                         add_ratio = atoi(argv[++i]);
1182                         break;
1183                 case 'k':
1184                         init_populate = 1;
1185                         break;
1186                 case 'R':
1187                         lookup_pool_offset = atol(argv[++i]);
1188                         break;
1189                 case 'S':
1190                         write_pool_offset = atol(argv[++i]);
1191                         break;
1192                 case 'T':
1193                         init_pool_offset = atol(argv[++i]);
1194                         break;
1195                 case 'M':
1196                         lookup_pool_size = atol(argv[++i]);
1197                         break;
1198                 case 'N':
1199                         write_pool_size = atol(argv[++i]);
1200                         break;
1201                 case 'O':
1202                         init_pool_size = atol(argv[++i]);
1203                         break;
1204                 case 'V':
1205                         validate_lookup = 1;
1206                         break;
1207                 case 't':
1208                         sanity_test = 1;
1209                         break;
1210                 case 'B':
1211                         key_bits = atol(argv[++i]);
1212                         break;
1213                 case 'm':
1214                         key_mul = atoll(argv[++i]);
1215                         break;
1216                 case 'u':
1217                         add_unique = 1;
1218                         break;
1219                 case 's':
1220                         add_replace = 1;
1221                         break;
1222                 case 'l':
1223                         leak_detection = 1;
1224                         break;
1225                 }
1226         }
1227
1228         printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
1229                 duration, nr_readers, nr_writers);
1230         printf_verbose("Writer delay : %lu loops.\n", wdelay);
1231         printf_verbose("Reader duration : %lu loops.\n", rduration);
1232         printf_verbose("Add ratio: %u%%.\n", add_ratio);
1233         printf_verbose("Mode:%s%s.\n",
1234                 " add/remove",
1235                 add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
1236         printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
1237         printf_verbose("Init pool size offset %lu size %lu.\n",
1238                 init_pool_offset, init_pool_size);
1239         printf_verbose("Lookup pool size offset %lu size %lu.\n",
1240                 lookup_pool_offset, lookup_pool_size);
1241         printf_verbose("Update pool size offset %lu size %lu.\n",
1242                 write_pool_offset, write_pool_size);
1243         if (validate_lookup)
1244                 printf_verbose("Validating lookups.\n");
1245         if (leak_detection)
1246                 printf_verbose("Memory leak dection activated.\n");
1247         printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
1248                         "main", pthread_self(), (unsigned long)gettid());
1249
1250         memset(&act, 0, sizeof(act));
1251         ret = sigemptyset(&act.sa_mask);
1252         if (ret == -1) {
1253                 perror("sigemptyset");
1254                 return -1;
1255         }
1256         act.sa_handler = test_ja_rw_sigusr1_handler;
1257         act.sa_flags = SA_RESTART;
1258         ret = sigaction(SIGUSR1, &act, NULL);
1259         if (ret == -1) {
1260                 perror("sigaction");
1261                 return -1;
1262         }
1263
1264         err = create_all_cpu_call_rcu_data(0);
1265         if (err) {
1266                 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
1267         }
1268
1269         rcu_register_thread();
1270
1271         if (sanity_test) {
1272                 ret = do_sanity_test();
1273         } else {
1274                 ret = do_mt_test();
1275         }
1276
1277         /* Wait for in-flight call_rcu free to complete for leak detection */
1278         rcu_barrier();
1279
1280         ret |= check_memory_leaks();
1281
1282         rcu_unregister_thread();
1283         free_all_cpu_call_rcu_data();
1284
1285         if (ret) {
1286                 printf("Test ended with error: %d\n", ret);
1287         }
1288         return ret;
1289 }