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[] = { 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_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 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_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 lower 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 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_ja_node *ja_node;
 353                 struct ja_test_node *node;
 354
 355                 key = ka[i];    /* without offset */
 356                 rcu_read_lock();
 357                 ja_node = cds_ja_lookup_below_equal(test_ja, key);
 358                 if (!ja_node) {
 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 = caa_container_of(ja_node, struct ja_test_node, node);
 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, 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_ja_node *node;
 419
 420                 rcu_read_lock();
 421                 node = cds_ja_lookup(test_ja, key);
 422                 if (!node) {
 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_ja_node *node;
 432
 433                 rcu_read_lock();
 434                 node = cds_ja_lookup(test_ja, key);
 435                 if (node) {
 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_ja_node *ja_node;
 448                 struct ja_test_node *node;
 449
 450                 rcu_read_lock();
 451                 ja_node = cds_ja_lookup(test_ja, key);
 452                 if (!ja_node) {
 453                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 454                         assert(0);
 455                 }
 456                 node = caa_container_of(ja_node, struct ja_test_node, node);
 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                 ja_node = cds_ja_lookup(test_ja, key);
 464                 if (ja_node) {
 465                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
 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_ja_node *ja_node;
 491                 struct ja_test_node *node;
 492
 493                 key = ka[i] + ka_test_offset;
 494                 rcu_read_lock();
 495                 ja_node = cds_ja_lookup_below_equal(test_ja, key);
 496                 if (!ja_node) {
 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 = caa_container_of(ja_node, struct ja_test_node, node);
 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_ja_node *ja_node;
 512                 struct ja_test_node *node;
 513
 514                 key = ka[i];    /* without offset */
 515                 rcu_read_lock();
 516                 ja_node = cds_ja_lookup_below_equal(test_ja, key);
 517                 if (!ja_node) {
 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 = caa_container_of(ja_node, struct ja_test_node, node);
 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, 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_ja_node *ja_node;
 589                 struct ja_test_node *node;
 590                 int count = 0;
 591
 592                 rcu_read_lock();
 593                 ja_node = cds_ja_lookup(test_ja, key);
 594                 if (!ja_node) {
 595                         fprintf(stderr, "Error lookup node %" PRIu64 "\n", key);
 596                         assert(0);
 597                 }
 598                 cds_ja_for_each_duplicate_rcu(ja_node) {
 599                         count++;
 600                 }
 601                 if (count != nr_dup) {
 602                         fprintf(stderr, "Unexpected number of match for key %" PRIu64 ", expected %d, got %d.\n", key, nr_dup, count);
 603                 }
 604                 rcu_read_unlock();
 605                 if (key == 0)
 606                         zerocount++;
 607         }
 608         printf("OK\n");
 609         if (bits > 8) {
 610                 printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits);
 611                 zerocount = 0;
 612                 for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 613                         struct cds_ja_node *ja_node;
 614
 615                         rcu_read_lock();
 616                         ja_node = cds_ja_lookup(test_ja, key + 42);
 617                         if (ja_node) {
 618                                 fprintf(stderr,
 619                                         "Error unexpected lookup node %" PRIu64 "\n",
 620                                         key + 42);
 621                                 assert(0);
 622                         }
 623                         rcu_read_unlock();
 624                         if (key == 0)
 625                                 zerocount++;
 626                 }
 627                 printf("OK\n");
 628         }
 629         printf("Test #4: remove keys (%u-bit).\n", bits);
 630         zerocount = 0;
 631         for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) {
 632                 struct cds_ja_node *ja_node;
 633                 int count = 0;
 634
 635                 rcu_read_lock();
 636                 ja_node = cds_ja_lookup(test_ja, key);
 637
 638                 cds_ja_for_each_duplicate_rcu(ja_node) {
 639                         struct cds_ja_node *test_ja_node;
 640                         struct ja_test_node *node;
 641
 642                         count++;
 643                         node = caa_container_of(ja_node,
 644                                 struct ja_test_node, node);
 645                         ret = cds_ja_del(test_ja, key, &node->node);
 646                         if (ret) {
 647                                 fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key);
 648                                 assert(0);
 649                         }
 650                         rcu_free_test_node(node);
 651                         test_ja_node = cds_ja_lookup(test_ja, key);
 652                         if (count < nr_dup && !test_ja_node) {
 653                                 fprintf(stderr, "Error: no node found after deletion of some nodes of a key\n");
 654                                 assert(0);
 655                         }
 656                 }
 657                 ja_node = cds_ja_lookup(test_ja, key);
 658                 if (ja_node) {
 659                         fprintf(stderr, "Error lookup %" PRIu64 ": %p (after delete) failed. Node is not expected.\n", key, ja_node);
 660                         assert(0);
 661                 }
 662                 rcu_read_unlock();
 663                 if (key == 0)
 664                         zerocount++;
 665         }
 666         printf("OK\n");
 667
 668         ret = cds_ja_destroy(test_ja, free_node);
 669         if (ret) {
 670                 fprintf(stderr, "Error destroying judy array\n");
 671                 return -1;
 672         }
 673         printf("Test ends\n");
 674
 675         return 0;
 676 }
 677
 678 static
 679 int do_sanity_test(void)
 680 {
 681         int i, j, ret;
 682
 683         printf("Sanity test start.\n");
 684
 685         for (i = 0; i < 3; i++) {
 686                 ret = test_8bit_key();
 687                 if (ret) {
 688                         return ret;
 689                 }
 690                 rcu_quiescent_state();
 691         }
 692         ret = test_16bit_key();
 693         if (ret) {
 694                 return ret;
 695         }
 696         rcu_quiescent_state();
 697
 698         /* key bits */
 699         for (i = 8; i <= 64; i *= 2) {
 700                 /* nr of nodes per key */
 701                 for (j = 1; j < 4; j++) {
 702                         ret = test_sparse_key(i, j);
 703                         if (ret) {
 704                                 return ret;
 705                         }
 706                         rcu_quiescent_state();
 707                 }
 708         }
 709         printf("Sanity test end.\n");
 710
 711         return 0;
 712 }
 713
 714 enum urcu_ja_addremove {
 715         AR_RANDOM = 0,
 716         AR_ADD = 1,
 717         AR_REMOVE = -1,
 718 };      /* 1: add, -1 remove, 0: random */
 719
 720 static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
 721
 722 static
 723 void test_ja_rw_sigusr1_handler(int signo)
 724 {
 725         switch (addremove) {
 726         case AR_ADD:
 727                 printf("Add/Remove: random.\n");
 728                 addremove = AR_RANDOM;
 729                 break;
 730         case AR_RANDOM:
 731                 printf("Add/Remove: remove only.\n");
 732                 addremove = AR_REMOVE;
 733                 break;
 734         case AR_REMOVE:
 735                 printf("Add/Remove: add only.\n");
 736                 addremove = AR_ADD;
 737                 break;
 738         }
 739 }
 740
 741 static
 742 void *test_ja_rw_thr_reader(void *_count)
 743 {
 744         unsigned long long *count = _count;
 745         struct cds_ja_node *ja_node;
 746         uint64_t key;
 747
 748         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 749                         "reader", pthread_self(), (unsigned long) gettid());
 750
 751         set_affinity();
 752
 753         rcu_register_thread();
 754
 755         while (!test_go)
 756         {
 757         }
 758         cmm_smp_mb();
 759
 760         for (;;) {
 761                 rcu_read_lock();
 762
 763                 /* note: only looking up ulong keys */
 764                 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
 765                 key *= key_mul;
 766                 ja_node = cds_ja_lookup(test_ja, key);
 767                 if (!ja_node) {
 768                         if (validate_lookup) {
 769                                 printf("[ERROR] Lookup cannot find initial node.\n");
 770                                 exit(-1);
 771                         }
 772                         URCU_TLS(lookup_fail)++;
 773                 } else {
 774                         URCU_TLS(lookup_ok)++;
 775                 }
 776                 rcu_debug_yield_read();
 777                 if (caa_unlikely(rduration))
 778                         loop_sleep(rduration);
 779                 rcu_read_unlock();
 780                 URCU_TLS(nr_reads)++;
 781                 if (caa_unlikely(!test_duration_read()))
 782                         break;
 783                 if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
 784                         rcu_quiescent_state();
 785         }
 786
 787         rcu_unregister_thread();
 788
 789         *count = URCU_TLS(nr_reads);
 790         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 791                         "reader", pthread_self(), (unsigned long) gettid());
 792         printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
 793                         pthread_self(), URCU_TLS(lookup_fail),
 794                         URCU_TLS(lookup_ok));
 795         return ((void*)1);
 796 }
 797
 798 static
 799 int is_add(void)
 800 {
 801         return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
 802 }
 803
 804 static
 805 void *test_ja_rw_thr_writer(void *_count)
 806 {
 807         struct wr_count *count = _count;
 808         uint64_t key;
 809         int ret;
 810
 811         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 812                         "writer", pthread_self(), (unsigned long) gettid());
 813
 814         set_affinity();
 815
 816         rcu_register_thread();
 817
 818         while (!test_go)
 819         {
 820         }
 821         cmm_smp_mb();
 822
 823         for (;;) {
 824                 if ((addremove == AR_ADD)
 825                                 || (addremove == AR_RANDOM && is_add())) {
 826                         struct ja_test_node *node = node_alloc();
 827                         struct cds_ja_node *ret_node;
 828
 829                         /* note: only inserting ulong keys */
 830                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 831                         key *= key_mul;
 832                         ja_test_node_init(node, key);
 833                         rcu_read_lock();
 834                         if (add_unique) {
 835                                 ret_node = cds_ja_add_unique(test_ja, key, &node->node);
 836                                 if (ret_node != &node->node) {
 837                                         free_test_node(node);
 838                                         URCU_TLS(nr_addexist)++;
 839                                 } else {
 840                                         URCU_TLS(nr_add)++;
 841                                 }
 842                         } else if (add_replace) {
 843                                 assert(0);      /* not implemented yet. */
 844                         } else {
 845                                 ret = cds_ja_add(test_ja, key, &node->node);
 846                                 if (ret) {
 847                                         fprintf(stderr, "Error in cds_ja_add: %d\n", ret);
 848                                         free_test_node(node);
 849                                 } else {
 850                                         URCU_TLS(nr_add)++;
 851                                 }
 852                         }
 853                         rcu_read_unlock();
 854                 } else {
 855                         struct cds_ja_node *ja_node;
 856                         struct ja_test_node *node;
 857
 858                         /* May delete */
 859                         /* note: only deleting ulong keys */
 860                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 861                         key *= key_mul;
 862
 863                         rcu_read_lock();
 864
 865                         ja_node = cds_ja_lookup(test_ja, key);
 866                         /* Remove first entry */
 867                         if (ja_node) {
 868                                 node = caa_container_of(ja_node,
 869                                         struct ja_test_node, node);
 870                                 ret = cds_ja_del(test_ja, key, &node->node);
 871                                 if (!ret) {
 872                                         rcu_free_test_node(node);
 873                                         URCU_TLS(nr_del)++;
 874                                 } else {
 875                                         URCU_TLS(nr_delnoent)++;
 876                                 }
 877                         } else {
 878                                 URCU_TLS(nr_delnoent)++;
 879                         }
 880                         rcu_read_unlock();
 881                 }
 882
 883                 URCU_TLS(nr_writes)++;
 884                 if (caa_unlikely(!test_duration_write()))
 885                         break;
 886                 if (caa_unlikely(wdelay))
 887                         loop_sleep(wdelay);
 888                 if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
 889                         rcu_quiescent_state();
 890         }
 891
 892         rcu_unregister_thread();
 893
 894         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 895                         "writer", pthread_self(), (unsigned long) gettid());
 896         printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
 897                         "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
 898                         URCU_TLS(nr_addexist), URCU_TLS(nr_del),
 899                         URCU_TLS(nr_delnoent));
 900         count->update_ops = URCU_TLS(nr_writes);
 901         count->add = URCU_TLS(nr_add);
 902         count->add_exist = URCU_TLS(nr_addexist);
 903         count->remove = URCU_TLS(nr_del);
 904         return ((void*)2);
 905 }
 906
 907 static
 908 int do_mt_populate_ja(void)
 909 {
 910         uint64_t iter;
 911         int ret;
 912
 913         if (!init_populate)
 914                 return 0;
 915
 916         printf("Starting rw test\n");
 917
 918         for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
 919                 struct ja_test_node *node = node_alloc();
 920                 uint64_t key;
 921
 922                 /* note: only inserting ulong keys */
 923                 key = (unsigned long) iter;
 924                 key *= key_mul;
 925                 ja_test_node_init(node, key);
 926                 rcu_read_lock();
 927                 ret = cds_ja_add(test_ja, key, &node->node);
 928                 URCU_TLS(nr_add)++;
 929                 URCU_TLS(nr_writes)++;
 930                 rcu_read_unlock();
 931                 if (ret) {
 932                         fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n",
 933                                 ret, key);
 934                         assert(0);
 935                 }
 936         }
 937         return 0;
 938 }
 939
 940 static
 941 int do_mt_test(void)
 942 {
 943         pthread_t *tid_reader, *tid_writer;
 944         void *tret;
 945         int ret, i, err;
 946         unsigned long long *count_reader;
 947         struct wr_count *count_writer;
 948         unsigned long long tot_reads = 0, tot_writes = 0,
 949                 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
 950         unsigned int remain;
 951
 952         tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
 953         tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
 954         count_reader = malloc(sizeof(*count_reader) * nr_readers);
 955         count_writer = malloc(sizeof(*count_writer) * nr_writers);
 956
 957         printf("Allocating Judy Array for %u-bit keys\n", key_bits);
 958         test_ja = cds_ja_new(key_bits);
 959         if (!test_ja) {
 960                 printf("Error allocating judy array.\n");
 961                 ret = -1;
 962                 goto end;
 963         }
 964
 965         do_mt_populate_ja();
 966
 967         next_aff = 0;
 968
 969         for (i = 0; i < nr_readers; i++) {
 970                 err = pthread_create(&tid_reader[i],
 971                                      NULL, test_ja_rw_thr_reader,
 972                                      &count_reader[i]);
 973                 if (err != 0)
 974                         exit(1);
 975         }
 976         for (i = 0; i < nr_writers; i++) {
 977                 err = pthread_create(&tid_writer[i],
 978                                      NULL, test_ja_rw_thr_writer,
 979                                      &count_writer[i]);
 980                 if (err != 0)
 981                         exit(1);
 982         }
 983
 984         cmm_smp_mb();
 985
 986         test_go = 1;
 987
 988         rcu_thread_offline_qsbr();
 989
 990         remain = duration;
 991         do {
 992                 remain = sleep(remain);
 993         } while (remain > 0);
 994
 995         test_stop = 1;
 996
 997         for (i = 0; i < nr_readers; i++) {
 998                 err = pthread_join(tid_reader[i], &tret);
 999                 if (err != 0)
1000                         exit(1);
1001                 tot_reads += count_reader[i];
1002         }
1003         for (i = 0; i < nr_writers; i++) {
1004                 err = pthread_join(tid_writer[i], &tret);
1005                 if (err != 0)
1006                         exit(1);
1007                 tot_writes += count_writer[i].update_ops;
1008                 tot_add += count_writer[i].add;
1009                 tot_add_exist += count_writer[i].add_exist;
1010                 tot_remove += count_writer[i].remove;
1011         }
1012         rcu_thread_online_qsbr();
1013
1014         ret = cds_ja_destroy(test_ja, free_node);
1015         if (ret) {
1016                 fprintf(stderr, "Error destroying judy array\n");
1017                 goto end;
1018         }
1019
1020         free(tid_reader);
1021         free(tid_writer);
1022         free(count_reader);
1023         free(count_writer);
1024         ret = 0;
1025 end:
1026         return ret;
1027 }
1028
1029 static
1030 int check_memory_leaks(void)
1031 {
1032         unsigned long na, nf;
1033
1034         na = uatomic_read(&test_nodes_allocated);
1035         nf = uatomic_read(&test_nodes_freed);
1036         if (na != nf) {
1037                 fprintf(stderr, "Memory leak of %ld test nodes detected. Allocated: %lu, freed: %lu\n",
1038                         na - nf, na, nf);
1039                 return -1;
1040         }
1041         return 0;
1042 }
1043
1044 int main(int argc, char **argv)
1045 {
1046         int i, j, a, ret, err;
1047         uint64_t key;
1048         struct sigaction act;
1049
1050         if (argc < 4) {
1051                 show_usage(argc, argv);
1052                 return -1;
1053         }
1054
1055         err = sscanf(argv[1], "%u", &nr_readers);
1056         if (err != 1) {
1057                 show_usage(argc, argv);
1058                 return -1;
1059         }
1060
1061         err = sscanf(argv[2], "%u", &nr_writers);
1062         if (err != 1) {
1063                 show_usage(argc, argv);
1064                 return -1;
1065         }
1066
1067         err = sscanf(argv[3], "%lu", &duration);
1068         if (err != 1) {
1069                 show_usage(argc, argv);
1070                 return -1;
1071         }
1072
1073         for (i = 4; i < argc; i++) {
1074                 if (argv[i][0] != '-')
1075                         continue;
1076                 switch (argv[i][1]) {
1077 #ifdef DEBUG_YIELD
1078                 case 'r':
1079                         yield_active |= YIELD_READ;
1080                         break;
1081                 case 'w':
1082                         yield_active |= YIELD_WRITE;
1083                         break;
1084 #endif
1085                 case 'a':
1086                         if (argc < i + 2) {
1087                                 show_usage(argc, argv);
1088                                 return -1;
1089                         }
1090                         a = atoi(argv[++i]);
1091                         cpu_affinities[next_aff++] = a;
1092                         use_affinity = 1;
1093                         printf_verbose("Adding CPU %d affinity\n", a);
1094                         break;
1095                 case 'c':
1096                         if (argc < i + 2) {
1097                                 show_usage(argc, argv);
1098                                 return -1;
1099                         }
1100                         rduration = atol(argv[++i]);
1101                         break;
1102                 case 'd':
1103                         if (argc < i + 2) {
1104                                 show_usage(argc, argv);
1105                                 return -1;
1106                         }
1107                         wdelay = atol(argv[++i]);
1108                         break;
1109                 case 'v':
1110                         verbose_mode = 1;
1111                         break;
1112                 case 'r':
1113                         add_ratio = atoi(argv[++i]);
1114                         break;
1115                 case 'k':
1116                         init_populate = 1;
1117                         break;
1118                 case 'R':
1119                         lookup_pool_offset = atol(argv[++i]);
1120                         break;
1121                 case 'S':
1122                         write_pool_offset = atol(argv[++i]);
1123                         break;
1124                 case 'T':
1125                         init_pool_offset = atol(argv[++i]);
1126                         break;
1127                 case 'M':
1128                         lookup_pool_size = atol(argv[++i]);
1129                         break;
1130                 case 'N':
1131                         write_pool_size = atol(argv[++i]);
1132                         break;
1133                 case 'O':
1134                         init_pool_size = atol(argv[++i]);
1135                         break;
1136                 case 'V':
1137                         validate_lookup = 1;
1138                         break;
1139                 case 't':
1140                         sanity_test = 1;
1141                         break;
1142                 case 'B':
1143                         key_bits = atol(argv[++i]);
1144                         break;
1145                 case 'm':
1146                         key_mul = atoll(argv[++i]);
1147                         break;
1148                 case 'u':
1149                         add_unique = 1;
1150                         break;
1151                 case 's':
1152                         add_replace = 1;
1153                         break;
1154                 case 'l':
1155                         leak_detection = 1;
1156                         break;
1157                 }
1158         }
1159
1160         printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
1161                 duration, nr_readers, nr_writers);
1162         printf_verbose("Writer delay : %lu loops.\n", wdelay);
1163         printf_verbose("Reader duration : %lu loops.\n", rduration);
1164         printf_verbose("Add ratio: %u%%.\n", add_ratio);
1165         printf_verbose("Mode:%s%s.\n",
1166                 " add/remove",
1167                 add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
1168         printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
1169         printf_verbose("Init pool size offset %lu size %lu.\n",
1170                 init_pool_offset, init_pool_size);
1171         printf_verbose("Lookup pool size offset %lu size %lu.\n",
1172                 lookup_pool_offset, lookup_pool_size);
1173         printf_verbose("Update pool size offset %lu size %lu.\n",
1174                 write_pool_offset, write_pool_size);
1175         if (validate_lookup)
1176                 printf_verbose("Validating lookups.\n");
1177         if (leak_detection)
1178                 printf_verbose("Memory leak dection activated.\n");
1179         printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
1180                         "main", pthread_self(), (unsigned long)gettid());
1181
1182         memset(&act, 0, sizeof(act));
1183         ret = sigemptyset(&act.sa_mask);
1184         if (ret == -1) {
1185                 perror("sigemptyset");
1186                 return -1;
1187         }
1188         act.sa_handler = test_ja_rw_sigusr1_handler;
1189         act.sa_flags = SA_RESTART;
1190         ret = sigaction(SIGUSR1, &act, NULL);
1191         if (ret == -1) {
1192                 perror("sigaction");
1193                 return -1;
1194         }
1195
1196         err = create_all_cpu_call_rcu_data(0);
1197         if (err) {
1198                 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
1199         }
1200
1201         rcu_register_thread();
1202
1203         if (sanity_test) {
1204                 ret = do_sanity_test();
1205         } else {
1206                 ret = do_mt_test();
1207         }
1208
1209         /* Wait for in-flight call_rcu free to complete for leak detection */
1210         rcu_barrier();
1211
1212         ret |= check_memory_leaks();
1213
1214         rcu_unregister_thread();
1215         free_all_cpu_call_rcu_data();
1216
1217         if (ret) {
1218                 printf("Test ended with error: %d\n", ret);
1219         }
1220         return ret;
1221 }