tests/test_urcu_ja.c

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