tests/test_urcu_ja_range.c

   1 /*
   2  * test_urcu_ja_range.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_range.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, range_max_len = 0;
  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 void show_usage(int argc, char **argv)
 137 {
 138         printf("Usage : %s nr_readers nr_writers duration (s)\n", argv[0]);
 139 #ifdef DEBUG_YIELD
 140         printf("        [-r] [-w] (yield reader and/or writer)\n");
 141 #endif
 142         printf("        [-d delay] (writer period (us))\n");
 143         printf("        [-c duration] (reader C.S. duration (in loops))\n");
 144         printf("        [-v] (verbose output)\n");
 145         printf("        [-a cpu#] [-a cpu#]... (affinity)\n");
 146         printf("        [-u] Add unique keys.\n");
 147         printf("        [-s] Replace existing keys.\n");
 148 printf("        [not -u nor -s] Add entries (supports redundant keys).\n");
 149         printf("        [-r ratio] Add ratio (in %% of add+removal).\n");
 150         printf("        [-k] Populate init nodes.\n");
 151         printf("        [-R offset] Lookup pool offset.\n");
 152         printf("        [-S offset] Write pool offset.\n");
 153         printf("        [-T offset] Init pool offset.\n");
 154         printf("        [-M size] Lookup pool size.\n");
 155         printf("        [-N size] Write pool size.\n");
 156         printf("        [-O size] Init pool size.\n");
 157         printf("        [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n");
 158         printf("        [-t] Do sanity test.\n");
 159         printf("        [-B] Key bits for multithread test (default: 32).\n");
 160         printf("        [-m factor] Key multiplication factor.\n");
 161         printf("        [-l] Memory leak detection.\n");
 162         printf("        [-L len] Range max len.\n");
 163         printf("\n\n");
 164 }
 165
 166 enum urcu_ja_addremove {
 167         AR_RANDOM = 0,
 168         AR_ADD = 1,
 169         AR_REMOVE = -1,
 170 };      /* 1: add, -1 remove, 0: random */
 171
 172 static enum urcu_ja_addremove addremove; /* 1: add, -1 remove, 0: random */
 173
 174 static
 175 void test_ja_rw_sigusr1_handler(int signo)
 176 {
 177         switch (addremove) {
 178         case AR_ADD:
 179                 printf("Add/Remove: random.\n");
 180                 addremove = AR_RANDOM;
 181                 break;
 182         case AR_RANDOM:
 183                 printf("Add/Remove: remove only.\n");
 184                 addremove = AR_REMOVE;
 185                 break;
 186         case AR_REMOVE:
 187                 printf("Add/Remove: add only.\n");
 188                 addremove = AR_ADD;
 189                 break;
 190         }
 191 }
 192
 193 static
 194 void *test_ja_rw_thr_reader(void *_count)
 195 {
 196         unsigned long long *count = _count;
 197         struct cds_ja_range *range;
 198         uint64_t key;
 199
 200         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 201                         "reader", pthread_self(), (unsigned long) gettid());
 202
 203         set_affinity();
 204
 205         rcu_register_thread();
 206
 207         while (!test_go)
 208         {
 209         }
 210         cmm_smp_mb();
 211
 212         for (;;) {
 213                 rcu_read_lock();
 214
 215                 /* note: only looking up ulong keys */
 216                 key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % lookup_pool_size) + lookup_pool_offset;
 217                 key *= key_mul;
 218                 range = cds_ja_range_lookup(test_ja, key);
 219                 if (!range) {
 220                         if (validate_lookup) {
 221                                 printf("[ERROR] Lookup cannot find initial node.\n");
 222                                 exit(-1);
 223                         }
 224                         URCU_TLS(lookup_fail)++;
 225                 } else {
 226                         range = cds_ja_range_lock(range);
 227                         if (!range) {
 228                                 if (validate_lookup) {
 229                                         printf("[ERROR] Lookup cannot find initial node.\n");
 230                                         exit(-1);
 231                                 }
 232                         } else {
 233                                 URCU_TLS(lookup_ok)++;
 234                                 cds_ja_range_unlock(range);
 235                         }
 236                 }
 237                 rcu_debug_yield_read();
 238                 if (caa_unlikely(rduration))
 239                         loop_sleep(rduration);
 240                 rcu_read_unlock();
 241                 URCU_TLS(nr_reads)++;
 242                 if (caa_unlikely(!test_duration_read()))
 243                         break;
 244                 if (caa_unlikely((URCU_TLS(nr_reads) & ((1 << 10) - 1)) == 0))
 245                         rcu_quiescent_state();
 246         }
 247
 248         rcu_unregister_thread();
 249
 250         *count = URCU_TLS(nr_reads);
 251         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 252                         "reader", pthread_self(), (unsigned long) gettid());
 253         printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n",
 254                         pthread_self(), URCU_TLS(lookup_fail),
 255                         URCU_TLS(lookup_ok));
 256         return ((void*)1);
 257 }
 258
 259 static
 260 int is_add(void)
 261 {
 262         return ((unsigned int) rand_r(&URCU_TLS(rand_lookup)) % 100) < add_ratio;
 263 }
 264
 265 static
 266 void *test_ja_rw_thr_writer(void *_count)
 267 {
 268         struct wr_count *count = _count;
 269         int ret;
 270
 271         printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n",
 272                         "writer", pthread_self(), (unsigned long) gettid());
 273
 274         set_affinity();
 275
 276         rcu_register_thread();
 277
 278         while (!test_go)
 279         {
 280         }
 281         cmm_smp_mb();
 282
 283         for (;;) {
 284                 if ((addremove == AR_ADD)
 285                                 || (addremove == AR_RANDOM && is_add())) {
 286                         struct cds_ja_range *range;
 287                         uint64_t start, end, tmp;
 288
 289                         /* note: only inserting ulong keys */
 290                         start = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 291                         end = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 292                         start *= key_mul;
 293                         end *= key_mul;
 294                         if (start > end) {
 295                                 tmp = start;
 296                                 start = end;
 297                                 end = tmp;
 298                         }
 299                         if (end - start > range_max_len) {
 300                                 end = start + range_max_len;
 301                         }
 302                         rcu_read_lock();
 303                         ret = cds_ja_range_add(test_ja, start, end, NULL);
 304                         if (ret) {
 305                                 if (ret == -EEXIST) {
 306                                         URCU_TLS(nr_addexist)++;
 307                                 } else {
 308                                         assert(0);
 309                                 }
 310                         } else {
 311                                 URCU_TLS(nr_add)++;
 312                         }
 313                         rcu_read_unlock();
 314                 } else {
 315                         struct cds_ja_range *range;
 316                         uint64_t key;
 317
 318                         /* May delete */
 319                         /* note: only deleting ulong keys */
 320                         key = ((unsigned long) rand_r(&URCU_TLS(rand_lookup)) % write_pool_size) + write_pool_offset;
 321                         key *= key_mul;
 322
 323                         rcu_read_lock();
 324
 325                         range = cds_ja_range_lookup(test_ja, key);
 326                         if (range) {
 327                                 ret = cds_ja_range_del(test_ja, range);
 328                                 if (!ret) {
 329                                         URCU_TLS(nr_del)++;
 330                                 } else {
 331                                         URCU_TLS(nr_delnoent)++;
 332                                 }
 333                         } else {
 334                                 URCU_TLS(nr_delnoent)++;
 335                         }
 336                         rcu_read_unlock();
 337                 }
 338
 339                 URCU_TLS(nr_writes)++;
 340                 if (caa_unlikely(!test_duration_write()))
 341                         break;
 342                 if (caa_unlikely(wdelay))
 343                         loop_sleep(wdelay);
 344                 if (caa_unlikely((URCU_TLS(nr_writes) & ((1 << 10) - 1)) == 0))
 345                         rcu_quiescent_state();
 346         }
 347
 348         rcu_unregister_thread();
 349
 350         printf_verbose("thread_end %s, thread id : %lx, tid %lu\n",
 351                         "writer", pthread_self(), (unsigned long) gettid());
 352         printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, "
 353                         "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add),
 354                         URCU_TLS(nr_addexist), URCU_TLS(nr_del),
 355                         URCU_TLS(nr_delnoent));
 356         count->update_ops = URCU_TLS(nr_writes);
 357         count->add = URCU_TLS(nr_add);
 358         count->add_exist = URCU_TLS(nr_addexist);
 359         count->remove = URCU_TLS(nr_del);
 360         return ((void*)2);
 361 }
 362
 363 static
 364 int do_mt_populate_ja(void)
 365 {
 366         uint64_t iter;
 367         int ret;
 368
 369         if (!init_populate)
 370                 return 0;
 371
 372         printf("Starting rw test\n");
 373
 374         for (iter = init_pool_offset; iter < init_pool_offset + init_pool_size; iter++) {
 375                 struct cds_ja_range *range;
 376                 uint64_t key;
 377
 378                 /* note: only inserting ulong keys */
 379                 key = (unsigned long) iter;
 380                 key *= key_mul;
 381                 rcu_read_lock();
 382                 ret = cds_ja_range_add(test_ja, key, key, NULL);
 383                 URCU_TLS(nr_add)++;
 384                 URCU_TLS(nr_writes)++;
 385                 rcu_read_unlock();
 386                 /* Hash table resize only occurs in call_rcu thread */
 387                 if (!(iter % 100))
 388                         rcu_quiescent_state();
 389                 if (ret) {
 390                         fprintf(stderr, "Error (%d) adding range %" PRIu64 "\n",
 391                                 ret, key);
 392                         assert(0);
 393                 }
 394         }
 395         return 0;
 396 }
 397
 398 static
 399 int do_mt_test(void)
 400 {
 401         pthread_t *tid_reader, *tid_writer;
 402         void *tret;
 403         int ret, i, err;
 404         unsigned long long *count_reader;
 405         struct wr_count *count_writer;
 406         unsigned long long tot_reads = 0, tot_writes = 0,
 407                 tot_add = 0, tot_add_exist = 0, tot_remove = 0;
 408         unsigned int remain;
 409
 410         tid_reader = malloc(sizeof(*tid_reader) * nr_readers);
 411         tid_writer = malloc(sizeof(*tid_writer) * nr_writers);
 412         count_reader = malloc(sizeof(*count_reader) * nr_readers);
 413         count_writer = malloc(sizeof(*count_writer) * nr_writers);
 414
 415         printf("Allocating %u-bit Judy Array for ranges\n",
 416                 key_bits);
 417         test_ja = cds_ja_range_new(key_bits);
 418         if (!test_ja) {
 419                 printf("Error allocating judy array.\n");
 420                 ret = -1;
 421                 goto end;
 422         }
 423
 424         do_mt_populate_ja();
 425
 426         next_aff = 0;
 427
 428         for (i = 0; i < nr_readers; i++) {
 429                 err = pthread_create(&tid_reader[i],
 430                                      NULL, test_ja_rw_thr_reader,
 431                                      &count_reader[i]);
 432                 if (err != 0)
 433                         exit(1);
 434         }
 435         for (i = 0; i < nr_writers; i++) {
 436                 err = pthread_create(&tid_writer[i],
 437                                      NULL, test_ja_rw_thr_writer,
 438                                      &count_writer[i]);
 439                 if (err != 0)
 440                         exit(1);
 441         }
 442
 443         cmm_smp_mb();
 444
 445         test_go = 1;
 446
 447         rcu_thread_offline_qsbr();
 448
 449         remain = duration;
 450         do {
 451                 remain = sleep(remain);
 452         } while (remain > 0);
 453
 454         test_stop = 1;
 455
 456         for (i = 0; i < nr_readers; i++) {
 457                 err = pthread_join(tid_reader[i], &tret);
 458                 if (err != 0)
 459                         exit(1);
 460                 tot_reads += count_reader[i];
 461         }
 462         for (i = 0; i < nr_writers; i++) {
 463                 err = pthread_join(tid_writer[i], &tret);
 464                 if (err != 0)
 465                         exit(1);
 466                 tot_writes += count_writer[i].update_ops;
 467                 tot_add += count_writer[i].add;
 468                 tot_add_exist += count_writer[i].add_exist;
 469                 tot_remove += count_writer[i].remove;
 470         }
 471         rcu_thread_online_qsbr();
 472
 473         ret = cds_ja_range_validate(test_ja);
 474         assert(!ret);
 475
 476         ret = cds_ja_range_destroy(test_ja, NULL);
 477         if (ret) {
 478                 fprintf(stderr, "Error destroying judy array\n");
 479                 goto end;
 480         }
 481
 482         free(tid_reader);
 483         free(tid_writer);
 484         free(count_reader);
 485         free(count_writer);
 486         ret = 0;
 487 end:
 488         return ret;
 489 }
 490
 491 int main(int argc, char **argv)
 492 {
 493         int i, j, a, ret, err;
 494         uint64_t key;
 495         struct sigaction act;
 496
 497         if (argc < 4) {
 498                 show_usage(argc, argv);
 499                 return -1;
 500         }
 501
 502         err = sscanf(argv[1], "%u", &nr_readers);
 503         if (err != 1) {
 504                 show_usage(argc, argv);
 505                 return -1;
 506         }
 507
 508         err = sscanf(argv[2], "%u", &nr_writers);
 509         if (err != 1) {
 510                 show_usage(argc, argv);
 511                 return -1;
 512         }
 513
 514         err = sscanf(argv[3], "%lu", &duration);
 515         if (err != 1) {
 516                 show_usage(argc, argv);
 517                 return -1;
 518         }
 519
 520         for (i = 4; i < argc; i++) {
 521                 if (argv[i][0] != '-')
 522                         continue;
 523                 switch (argv[i][1]) {
 524 #ifdef DEBUG_YIELD
 525                 case 'r':
 526                         yield_active |= YIELD_READ;
 527                         break;
 528                 case 'w':
 529                         yield_active |= YIELD_WRITE;
 530                         break;
 531 #endif
 532                 case 'a':
 533                         if (argc < i + 2) {
 534                                 show_usage(argc, argv);
 535                                 return -1;
 536                         }
 537                         a = atoi(argv[++i]);
 538                         cpu_affinities[next_aff++] = a;
 539                         use_affinity = 1;
 540                         printf_verbose("Adding CPU %d affinity\n", a);
 541                         break;
 542                 case 'c':
 543                         if (argc < i + 2) {
 544                                 show_usage(argc, argv);
 545                                 return -1;
 546                         }
 547                         rduration = atol(argv[++i]);
 548                         break;
 549                 case 'd':
 550                         if (argc < i + 2) {
 551                                 show_usage(argc, argv);
 552                                 return -1;
 553                         }
 554                         wdelay = atol(argv[++i]);
 555                         break;
 556                 case 'v':
 557                         verbose_mode = 1;
 558                         break;
 559                 case 'r':
 560                         add_ratio = atoi(argv[++i]);
 561                         break;
 562                 case 'k':
 563                         init_populate = 1;
 564                         break;
 565                 case 'R':
 566                         lookup_pool_offset = atol(argv[++i]);
 567                         break;
 568                 case 'S':
 569                         write_pool_offset = atol(argv[++i]);
 570                         break;
 571                 case 'T':
 572                         init_pool_offset = atol(argv[++i]);
 573                         break;
 574                 case 'M':
 575                         lookup_pool_size = atol(argv[++i]);
 576                         break;
 577                 case 'N':
 578                         write_pool_size = atol(argv[++i]);
 579                         break;
 580                 case 'O':
 581                         init_pool_size = atol(argv[++i]);
 582                         break;
 583                 case 'V':
 584                         validate_lookup = 1;
 585                         break;
 586                 case 't':
 587                         sanity_test = 1;
 588                         break;
 589                 case 'B':
 590                         key_bits = atol(argv[++i]);
 591                         break;
 592                 case 'm':
 593                         key_mul = atoll(argv[++i]);
 594                         break;
 595                 case 'u':
 596                         add_unique = 1;
 597                         break;
 598                 case 's':
 599                         add_replace = 1;
 600                         break;
 601                 case 'l':
 602                         leak_detection = 1;
 603                         break;
 604                 case 'L':
 605                         range_max_len = atol(argv[++i]);
 606                         break;
 607                 }
 608         }
 609
 610         printf_verbose("running test for %lu seconds, %u readers, %u writers.\n",
 611                 duration, nr_readers, nr_writers);
 612         printf_verbose("Writer delay : %lu loops.\n", wdelay);
 613         printf_verbose("Reader duration : %lu loops.\n", rduration);
 614         printf_verbose("Add ratio: %u%%.\n", add_ratio);
 615         printf_verbose("Mode:%s%s.\n",
 616                 " add/remove",
 617                 add_unique ? " uniquify" : ( add_replace ? " replace" : " insert"));
 618         printf_verbose("Key multiplication factor: %" PRIu64 ".\n", key_mul);
 619         printf_verbose("Init pool size offset %lu size %lu.\n",
 620                 init_pool_offset, init_pool_size);
 621         printf_verbose("Lookup pool size offset %lu size %lu.\n",
 622                 lookup_pool_offset, lookup_pool_size);
 623         printf_verbose("Update pool size offset %lu size %lu.\n",
 624                 write_pool_offset, write_pool_size);
 625         printf_verbose("Range max len: %lu.\n",
 626                 range_max_len);
 627         if (validate_lookup)
 628                 printf_verbose("Validating lookups.\n");
 629         if (leak_detection)
 630                 printf_verbose("Memory leak dection activated.\n");
 631         printf_verbose("thread %-6s, thread id : %lx, tid %lu\n",
 632                         "main", pthread_self(), (unsigned long)gettid());
 633
 634         memset(&act, 0, sizeof(act));
 635         ret = sigemptyset(&act.sa_mask);
 636         if (ret == -1) {
 637                 perror("sigemptyset");
 638                 return -1;
 639         }
 640         act.sa_handler = test_ja_rw_sigusr1_handler;
 641         act.sa_flags = SA_RESTART;
 642         ret = sigaction(SIGUSR1, &act, NULL);
 643         if (ret == -1) {
 644                 perror("sigaction");
 645                 return -1;
 646         }
 647
 648         err = create_all_cpu_call_rcu_data(0);
 649         if (err) {
 650                 printf("Per-CPU call_rcu() worker threads unavailable. Using default global worker thread.\n");
 651         }
 652
 653         rcu_register_thread();
 654
 655         ret = do_mt_test();
 656
 657         /* Wait for in-flight call_rcu free to complete for leak detection */
 658         rcu_barrier();
 659
 660         rcu_unregister_thread();
 661         free_all_cpu_call_rcu_data();
 662
 663         if (ret) {
 664                 printf("Test ended with error: %d\n", ret);
 665         }
 666         return ret;
 667 }