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