tests/test_urcu_ja.c

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