tests/test-cmap.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2013, 2014, 2016 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /* A non-exhaustive test for some of the functions and macros declared in
  18  * cmap.h. */
  19
  20 #include <config.h>
  21 #undef NDEBUG
  22 #include "cmap.h"
  23 #include <assert.h>
  24 #include <getopt.h>
  25 #include <string.h>
  26 #include "bitmap.h"
  27 #include "command-line.h"
  28 #include "fat-rwlock.h"
  29 #include "hash.h"
  30 #include "openvswitch/hmap.h"
  31 #include "ovstest.h"
  32 #include "ovs-thread.h"
  33 #include "random.h"
  34 #include "timeval.h"
  35 #include "util.h"
  36
  37 /* Sample cmap element. */
  38 struct element {
  39     int value;
  40     struct cmap_node node;
  41 };
  42
  43 typedef size_t hash_func(int value);
  44
  45 static int
  46 compare_ints(const void *a_, const void *b_)
  47 {
  48     const int *a = a_;
  49     const int *b = b_;
  50     return *a < *b ? -1 : *a > *b;
  51 }
  52
  53 /* Verifies that 'cmap' contains exactly the 'n' values in 'values'. */
  54 static void
  55 check_cmap(struct cmap *cmap, const int values[], size_t n,
  56            hash_func *hash)
  57 {
  58     int *sort_values, *cmap_values, *cmap_values2;
  59     const struct element *e;
  60     size_t i, batch_size;
  61
  62     struct cmap_position pos = { 0, 0, 0 };
  63     struct cmap_node *node;
  64
  65     /* Check that all the values are there in iteration. */
  66     sort_values = xmalloc(sizeof *sort_values * n);
  67     cmap_values = xmalloc(sizeof *sort_values * n);
  68     cmap_values2 = xmalloc(sizeof *sort_values * n);
  69
  70     /* Here we test cursor iteration */
  71     i = 0;
  72     CMAP_FOR_EACH (e, node, cmap) {
  73         assert(i < n);
  74         cmap_values[i++] = e->value;
  75     }
  76     assert(i == n);
  77
  78     /* Here we test iteration with cmap_next_position() */
  79     i = 0;
  80     while ((node = cmap_next_position(cmap, &pos))) {
  81         struct element *e = NULL;
  82         e = OBJECT_CONTAINING(node, e, node);
  83
  84         assert(i < n);
  85         cmap_values2[i++] = e->value;
  86     }
  87     assert(i == n);
  88
  89     memcpy(sort_values, values, sizeof *sort_values * n);
  90     qsort(sort_values, n, sizeof *sort_values, compare_ints);
  91     qsort(cmap_values, n, sizeof *cmap_values, compare_ints);
  92     qsort(cmap_values2, n, sizeof *cmap_values2, compare_ints);
  93
  94     for (i = 0; i < n; i++) {
  95         assert(sort_values[i] == cmap_values[i]);
  96         assert(sort_values[i] == cmap_values2[i]);
  97     }
  98
  99     free(cmap_values2);
 100     free(cmap_values);
 101     free(sort_values);
 102
 103     /* Check that all the values are there in lookup. */
 104     for (i = 0; i < n; i++) {
 105         size_t count = 0;
 106
 107         CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) {
 108             count += e->value == values[i];
 109         }
 110         assert(count == 1);
 111     }
 112
 113     /* Check that all the values are there in batched lookup. */
 114     batch_size = n % BITMAP_ULONG_BITS + 1;
 115     for (i = 0; i < n; i += batch_size) {
 116         unsigned long map;
 117         uint32_t hashes[sizeof map * CHAR_BIT];
 118         const struct cmap_node *nodes[sizeof map * CHAR_BIT];
 119         size_t count = 0;
 120         int k, j;
 121
 122         j = MIN(n - i, batch_size); /* Actual batch size. */
 123         map = ~0UL >> (BITMAP_ULONG_BITS - j);
 124
 125         for (k = 0; k < j; k++) {
 126             hashes[k] = hash(values[i + k]);
 127         }
 128         map = cmap_find_batch(cmap, map, hashes, nodes);
 129
 130         ULLONG_FOR_EACH_1(k, map) {
 131             struct element *e;
 132
 133             CMAP_NODE_FOR_EACH (e, node, nodes[k]) {
 134                 count += e->value == values[i + k];
 135             }
 136         }
 137         assert(count == j); /* j elements in a batch. */
 138     }
 139
 140     /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
 141     assert(!cmap_first(cmap) == cmap_is_empty(cmap));
 142
 143     /* Check counters. */
 144     assert(cmap_is_empty(cmap) == !n);
 145     assert(cmap_count(cmap) == n);
 146 }
 147
 148 static void
 149 shuffle(int *p, size_t n)
 150 {
 151     for (; n > 1; n--, p++) {
 152         int *q = &p[random_range(n)];
 153         int tmp = *p;
 154         *p = *q;
 155         *q = tmp;
 156     }
 157 }
 158
 159 /* Prints the values in 'cmap', plus 'name' as a title. */
 160 static void OVS_UNUSED
 161 print_cmap(const char *name, struct cmap *cmap)
 162 {
 163     struct cmap_cursor cursor;
 164     struct element *e;
 165
 166     printf("%s:", name);
 167     CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) {
 168         printf(" %d", e->value);
 169     }
 170     printf("\n");
 171 }
 172
 173 /* Prints the 'n' values in 'values', plus 'name' as a title. */
 174 static void OVS_UNUSED
 175 print_ints(const char *name, const int *values, size_t n)
 176 {
 177     size_t i;
 178
 179     printf("%s:", name);
 180     for (i = 0; i < n; i++) {
 181         printf(" %d", values[i]);
 182     }
 183     printf("\n");
 184 }
 185
 186 static size_t
 187 identity_hash(int value)
 188 {
 189     return value;
 190 }
 191
 192 static size_t
 193 good_hash(int value)
 194 {
 195     return hash_int(value, 0x1234abcd);
 196 }
 197
 198 static size_t
 199 constant_hash(int value OVS_UNUSED)
 200 {
 201     return 123;
 202 }
 203
 204 /* Tests basic cmap insertion and deletion. */
 205 static void
 206 test_cmap_insert_replace_delete(hash_func *hash)
 207 {
 208     enum { N_ELEMS = 1000 };
 209
 210     struct element elements[N_ELEMS];
 211     struct element copies[N_ELEMS];
 212     int values[N_ELEMS];
 213     struct cmap cmap = CMAP_INITIALIZER;
 214     size_t i;
 215
 216     for (i = 0; i < N_ELEMS; i++) {
 217         elements[i].value = i;
 218         cmap_insert(&cmap, &elements[i].node, hash(i));
 219         values[i] = i;
 220         check_cmap(&cmap, values, i + 1, hash);
 221     }
 222     shuffle(values, N_ELEMS);
 223     for (i = 0; i < N_ELEMS; i++) {
 224         copies[values[i]].value = values[i];
 225         cmap_replace(&cmap, &elements[values[i]].node,
 226                      &copies[values[i]].node, hash(values[i]));
 227         check_cmap(&cmap, values, N_ELEMS, hash);
 228     }
 229     shuffle(values, N_ELEMS);
 230     for (i = 0; i < N_ELEMS; i++) {
 231         cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
 232         check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
 233     }
 234     cmap_destroy(&cmap);
 235 }
 236
 237 static void
 238 run_test(void (*function)(hash_func *))
 239 {
 240     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
 241     size_t i;
 242
 243     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
 244         function(hash_funcs[i]);
 245         printf(".");
 246         fflush(stdout);
 247     }
 248 }
 249
 250 static void
 251 run_tests(struct ovs_cmdl_context *ctx)
 252 {
 253     int n;
 254     int i;
 255
 256     n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
 257     for (i = 0; i < n; i++) {
 258         run_test(test_cmap_insert_replace_delete);
 259     }
 260     printf("\n");
 261 }
 262 \f
 263 static int n_elems;             /* Number of elements to insert. */
 264 static int n_threads;           /* Number of threads to search and mutate. */
 265 static uint32_t mutation_frac;  /* % mutations, as fraction of UINT32_MAX. */
 266 static int n_batch;             /* Number of elements in each batch. */
 267
 268 #define N_BATCH_MAX BITMAP_ULONG_BITS
 269
 270 static void benchmark_cmap(void);
 271 static void benchmark_cmap_batched(void);
 272 static void benchmark_hmap(void);
 273
 274 static int
 275 elapsed(const struct timeval *start)
 276 {
 277     struct timeval end;
 278
 279     xgettimeofday(&end);
 280     return timeval_to_msec(&end) - timeval_to_msec(start);
 281 }
 282
 283 static void
 284 run_benchmarks(struct ovs_cmdl_context *ctx)
 285 {
 286     n_elems = strtol(ctx->argv[1], NULL, 10);
 287     n_threads = strtol(ctx->argv[2], NULL, 10);
 288     mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX;
 289     n_batch = ctx->argc > 4 ? strtol(ctx->argv[4], NULL, 10) : 1;
 290
 291     if (n_batch > N_BATCH_MAX) {
 292         n_batch = N_BATCH_MAX;
 293     }
 294     printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n",
 295            n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.,
 296            n_batch);
 297
 298     if (n_batch > 0) {
 299         benchmark_cmap_batched();
 300     }
 301     putchar('\n');
 302     benchmark_cmap();
 303     putchar('\n');
 304     benchmark_hmap();
 305 }
 306 \f
 307 /* cmap benchmark. */
 308
 309 static struct element *
 310 find(const struct cmap *cmap, int value)
 311 {
 312     struct element *e;
 313
 314     CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
 315         if (e->value == value) {
 316             return e;
 317         }
 318     }
 319     return NULL;
 320 }
 321
 322 struct cmap_aux {
 323     struct ovs_mutex mutex;
 324     struct cmap *cmap;
 325 };
 326
 327 static void *
 328 search_cmap(void *aux_)
 329 {
 330     struct cmap_aux *aux = aux_;
 331     size_t i;
 332
 333     if (mutation_frac) {
 334         for (i = 0; i < n_elems; i++) {
 335             struct element *e;
 336
 337             if (random_uint32() < mutation_frac) {
 338                 ovs_mutex_lock(&aux->mutex);
 339                 e = find(aux->cmap, i);
 340                 if (e) {
 341                     cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
 342                 }
 343                 ovs_mutex_unlock(&aux->mutex);
 344             } else {
 345                 ignore(find(aux->cmap, i));
 346             }
 347         }
 348     } else {
 349         for (i = 0; i < n_elems; i++) {
 350             ignore(find(aux->cmap, i));
 351         }
 352     }
 353     return NULL;
 354 }
 355
 356 static void
 357 benchmark_cmap(void)
 358 {
 359     struct element *elements;
 360     struct cmap cmap;
 361     struct element *e;
 362     struct timeval start;
 363     pthread_t *threads;
 364     struct cmap_aux aux;
 365     size_t i;
 366
 367     elements = xmalloc(n_elems * sizeof *elements);
 368
 369     /* Insertions. */
 370     xgettimeofday(&start);
 371     cmap_init(&cmap);
 372     for (i = 0; i < n_elems; i++) {
 373         elements[i].value = i;
 374         cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
 375     }
 376     printf("cmap insert:  %5d ms\n", elapsed(&start));
 377
 378     /* Iteration. */
 379     xgettimeofday(&start);
 380     CMAP_FOR_EACH (e, node, &cmap) {
 381         ignore(e);
 382     }
 383     printf("cmap iterate: %5d ms\n", elapsed(&start));
 384
 385     /* Search and mutation. */
 386     xgettimeofday(&start);
 387     aux.cmap = &cmap;
 388     ovs_mutex_init(&aux.mutex);
 389     threads = xmalloc(n_threads * sizeof *threads);
 390     for (i = 0; i < n_threads; i++) {
 391         threads[i] = ovs_thread_create("search", search_cmap, &aux);
 392     }
 393     for (i = 0; i < n_threads; i++) {
 394         xpthread_join(threads[i], NULL);
 395     }
 396     free(threads);
 397     printf("cmap search:  %5d ms\n", elapsed(&start));
 398
 399     /* Destruction. */
 400     xgettimeofday(&start);
 401     CMAP_FOR_EACH (e, node, &cmap) {
 402         cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
 403     }
 404     cmap_destroy(&cmap);
 405     printf("cmap destroy: %5d ms\n", elapsed(&start));
 406
 407     free(elements);
 408 }
 409
 410 static size_t
 411 find_batch(const struct cmap *cmap, const int value)
 412 {
 413     size_t i, ret;
 414     const size_t end = MIN(n_batch, n_elems - value);
 415     unsigned long map = ~0;
 416     uint32_t hashes[N_BATCH_MAX];
 417     const struct cmap_node *nodes[N_BATCH_MAX];
 418
 419     if (mutation_frac) {
 420         for (i = 0; i < end; i++) {
 421             if (random_uint32() < mutation_frac) {
 422                 break;
 423             }
 424             hashes[i] = hash_int(value + i, 0);
 425         }
 426     } else {
 427         for (i = 0; i < end; i++) {
 428             hashes[i] = hash_int(value + i, 0);
 429         }
 430     }
 431
 432     ret = i;
 433
 434     map >>= BITMAP_ULONG_BITS - i; /* Clear excess bits. */
 435     map = cmap_find_batch(cmap, map, hashes, nodes);
 436
 437     ULLONG_FOR_EACH_1(i, map) {
 438         struct element *e;
 439
 440         CMAP_NODE_FOR_EACH (e, node, nodes[i]) {
 441             if (OVS_LIKELY(e->value == value + i)) {
 442                 ignore(e); /* Found result. */
 443                 break;
 444             }
 445         }
 446     }
 447     return ret;
 448 }
 449
 450 static void *
 451 search_cmap_batched(void *aux_)
 452 {
 453     struct cmap_aux *aux = aux_;
 454     size_t i = 0, j;
 455
 456     for (;;) {
 457         struct element *e;
 458
 459         j = find_batch(aux->cmap, i);
 460         i += j;
 461         if (i >= n_elems) {
 462             break;
 463         }
 464         if (j < n_batch) {
 465             ovs_mutex_lock(&aux->mutex);
 466             e = find(aux->cmap, i);
 467             if (e) {
 468                 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
 469             }
 470             ovs_mutex_unlock(&aux->mutex);
 471         }
 472     }
 473
 474     return NULL;
 475 }
 476
 477 static void
 478 benchmark_cmap_batched(void)
 479 {
 480     struct element *elements;
 481     struct cmap cmap;
 482     struct element *e;
 483     struct timeval start;
 484     pthread_t *threads;
 485     struct cmap_aux aux;
 486     size_t i;
 487
 488     elements = xmalloc(n_elems * sizeof *elements);
 489
 490     /* Insertions. */
 491     xgettimeofday(&start);
 492     cmap_init(&cmap);
 493     for (i = 0; i < n_elems; i++) {
 494         elements[i].value = i;
 495         cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
 496     }
 497     printf("cmap insert:  %5d ms\n", elapsed(&start));
 498
 499     /* Iteration. */
 500     xgettimeofday(&start);
 501     CMAP_FOR_EACH (e, node, &cmap) {
 502         ignore(e);
 503     }
 504     printf("cmap iterate: %5d ms\n", elapsed(&start));
 505
 506     /* Search and mutation. */
 507     xgettimeofday(&start);
 508     aux.cmap = &cmap;
 509     ovs_mutex_init(&aux.mutex);
 510     threads = xmalloc(n_threads * sizeof *threads);
 511     for (i = 0; i < n_threads; i++) {
 512         threads[i] = ovs_thread_create("search", search_cmap_batched, &aux);
 513     }
 514     for (i = 0; i < n_threads; i++) {
 515         xpthread_join(threads[i], NULL);
 516     }
 517     free(threads);
 518     printf("batch search: %5d ms\n", elapsed(&start));
 519
 520     /* Destruction. */
 521     xgettimeofday(&start);
 522     CMAP_FOR_EACH (e, node, &cmap) {
 523         cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
 524     }
 525     cmap_destroy(&cmap);
 526     printf("cmap destroy: %5d ms\n", elapsed(&start));
 527
 528     free(elements);
 529 }
 530 \f
 531 /* hmap benchmark. */
 532 struct helement {
 533     int value;
 534     struct hmap_node node;
 535 };
 536
 537 static struct helement *
 538 hfind(const struct hmap *hmap, int value)
 539 {
 540     struct helement *e;
 541
 542     HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
 543         if (e->value == value) {
 544             return e;
 545         }
 546     }
 547     return NULL;
 548 }
 549
 550 struct hmap_aux {
 551     struct hmap *hmap;
 552     struct fat_rwlock fatlock;
 553 };
 554
 555 static void *
 556 search_hmap(void *aux_)
 557 {
 558     struct hmap_aux *aux = aux_;
 559     size_t i;
 560
 561     if (mutation_frac) {
 562         for (i = 0; i < n_elems; i++) {
 563             if (random_uint32() < mutation_frac) {
 564                 struct helement *e;
 565
 566                 fat_rwlock_wrlock(&aux->fatlock);
 567                 e = hfind(aux->hmap, i);
 568                 if (e) {
 569                     hmap_remove(aux->hmap, &e->node);
 570                 }
 571                 fat_rwlock_unlock(&aux->fatlock);
 572             } else {
 573                 fat_rwlock_rdlock(&aux->fatlock);
 574                 ignore(hfind(aux->hmap, i));
 575                 fat_rwlock_unlock(&aux->fatlock);
 576             }
 577         }
 578     } else {
 579         for (i = 0; i < n_elems; i++) {
 580             ignore(hfind(aux->hmap, i));
 581         }
 582     }
 583     return NULL;
 584 }
 585
 586 static void
 587 benchmark_hmap(void)
 588 {
 589     struct helement *elements;
 590     struct hmap hmap;
 591     struct helement *e, *next;
 592     struct timeval start;
 593     pthread_t *threads;
 594     struct hmap_aux aux;
 595     size_t i;
 596
 597     elements = xmalloc(n_elems * sizeof *elements);
 598
 599     xgettimeofday(&start);
 600     hmap_init(&hmap);
 601     for (i = 0; i < n_elems; i++) {
 602         elements[i].value = i;
 603         hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
 604     }
 605
 606     printf("hmap insert:  %5d ms\n", elapsed(&start));
 607
 608     xgettimeofday(&start);
 609     HMAP_FOR_EACH (e, node, &hmap) {
 610         ignore(e);
 611     }
 612     printf("hmap iterate: %5d ms\n", elapsed(&start));
 613
 614     xgettimeofday(&start);
 615     aux.hmap = &hmap;
 616     fat_rwlock_init(&aux.fatlock);
 617     threads = xmalloc(n_threads * sizeof *threads);
 618     for (i = 0; i < n_threads; i++) {
 619         threads[i] = ovs_thread_create("search", search_hmap, &aux);
 620     }
 621     for (i = 0; i < n_threads; i++) {
 622         xpthread_join(threads[i], NULL);
 623     }
 624     free(threads);
 625     printf("hmap search:  %5d ms\n", elapsed(&start));
 626
 627     /* Destruction. */
 628     xgettimeofday(&start);
 629     HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
 630         hmap_remove(&hmap, &e->node);
 631     }
 632     hmap_destroy(&hmap);
 633     printf("hmap destroy: %5d ms\n", elapsed(&start));
 634
 635     free(elements);
 636 }
 637 \f
 638 static const struct ovs_cmdl_command commands[] = {
 639     {"check", NULL, 0, 1, run_tests},
 640     {"benchmark", NULL, 3, 4, run_benchmarks},
 641     {NULL, NULL, 0, 0, NULL},
 642 };
 643
 644 static void
 645 test_cmap_main(int argc, char *argv[])
 646 {
 647     struct ovs_cmdl_context ctx = {
 648         .argc = argc - optind,
 649         .argv = argv + optind,
 650     };
 651
 652     set_program_name(argv[0]);
 653     ovs_cmdl_run_command(&ctx, commands);
 654 }
 655
 656 OVSTEST_REGISTER("test-cmap", test_cmap_main);