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