tests/test-cmap.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2013, 2014 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 "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;
 214     size_t i;
 215
 216     cmap_init(&cmap);
 217     for (i = 0; i < N_ELEMS; i++) {
 218         elements[i].value = i;
 219         cmap_insert(&cmap, &elements[i].node, hash(i));
 220         values[i] = i;
 221         check_cmap(&cmap, values, i + 1, hash);
 222     }
 223     shuffle(values, N_ELEMS);
 224     for (i = 0; i < N_ELEMS; i++) {
 225         copies[values[i]].value = values[i];
 226         cmap_replace(&cmap, &elements[values[i]].node,
 227                      &copies[values[i]].node, hash(values[i]));
 228         check_cmap(&cmap, values, N_ELEMS, hash);
 229     }
 230     shuffle(values, N_ELEMS);
 231     for (i = 0; i < N_ELEMS; i++) {
 232         cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
 233         check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
 234     }
 235     cmap_destroy(&cmap);
 236 }
 237
 238 static void
 239 run_test(void (*function)(hash_func *))
 240 {
 241     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
 242     size_t i;
 243
 244     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
 245         function(hash_funcs[i]);
 246         printf(".");
 247         fflush(stdout);
 248     }
 249 }
 250
 251 static void
 252 run_tests(struct ovs_cmdl_context *ctx)
 253 {
 254     int n;
 255     int i;
 256
 257     n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
 258     for (i = 0; i < n; i++) {
 259         run_test(test_cmap_insert_replace_delete);
 260     }
 261     printf("\n");
 262 }
 263 \f
 264 static int n_elems;             /* Number of elements to insert. */
 265 static int n_threads;           /* Number of threads to search and mutate. */
 266 static uint32_t mutation_frac;  /* % mutations, as fraction of UINT32_MAX. */
 267 static int n_batch;             /* Number of elements in each batch. */
 268
 269 #define N_BATCH_MAX BITMAP_ULONG_BITS
 270
 271 static void benchmark_cmap(void);
 272 static void benchmark_cmap_batched(void);
 273 static void benchmark_hmap(void);
 274
 275 static int
 276 elapsed(const struct timeval *start)
 277 {
 278     struct timeval end;
 279
 280     xgettimeofday(&end);
 281     return timeval_to_msec(&end) - timeval_to_msec(start);
 282 }
 283
 284 static void
 285 run_benchmarks(struct ovs_cmdl_context *ctx)
 286 {
 287     n_elems = strtol(ctx->argv[1], NULL, 10);
 288     n_threads = strtol(ctx->argv[2], NULL, 10);
 289     mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX;
 290     n_batch = ctx->argc > 4 ? strtol(ctx->argv[4], NULL, 10) : 1;
 291
 292     if (n_batch > N_BATCH_MAX) {
 293         n_batch = N_BATCH_MAX;
 294     }
 295     printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n",
 296            n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.,
 297            n_batch);
 298
 299     if (n_batch > 0) {
 300         benchmark_cmap_batched();
 301     }
 302     putchar('\n');
 303     benchmark_cmap();
 304     putchar('\n');
 305     benchmark_hmap();
 306 }
 307 \f
 308 /* cmap benchmark. */
 309
 310 static struct element *
 311 find(const struct cmap *cmap, int value)
 312 {
 313     struct element *e;
 314
 315     CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
 316         if (e->value == value) {
 317             return e;
 318         }
 319     }
 320     return NULL;
 321 }
 322
 323 struct cmap_aux {
 324     struct ovs_mutex mutex;
 325     struct cmap *cmap;
 326 };
 327
 328 static void *
 329 search_cmap(void *aux_)
 330 {
 331     struct cmap_aux *aux = aux_;
 332     size_t i;
 333
 334     if (mutation_frac) {
 335         for (i = 0; i < n_elems; i++) {
 336             struct element *e;
 337
 338             if (random_uint32() < mutation_frac) {
 339                 ovs_mutex_lock(&aux->mutex);
 340                 e = find(aux->cmap, i);
 341                 if (e) {
 342                     cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
 343                 }
 344                 ovs_mutex_unlock(&aux->mutex);
 345             } else {
 346                 ignore(find(aux->cmap, i));
 347             }
 348         }
 349     } else {
 350         for (i = 0; i < n_elems; i++) {
 351             ignore(find(aux->cmap, i));
 352         }
 353     }
 354     return NULL;
 355 }
 356
 357 static void
 358 benchmark_cmap(void)
 359 {
 360     struct element *elements;
 361     struct cmap cmap;
 362     struct element *e;
 363     struct timeval start;
 364     pthread_t *threads;
 365     struct cmap_aux aux;
 366     size_t i;
 367
 368     elements = xmalloc(n_elems * sizeof *elements);
 369
 370     /* Insertions. */
 371     xgettimeofday(&start);
 372     cmap_init(&cmap);
 373     for (i = 0; i < n_elems; i++) {
 374         elements[i].value = i;
 375         cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
 376     }
 377     printf("cmap insert:  %5d ms\n", elapsed(&start));
 378
 379     /* Iteration. */
 380     xgettimeofday(&start);
 381     CMAP_FOR_EACH (e, node, &cmap) {
 382         ignore(e);
 383     }
 384     printf("cmap iterate: %5d ms\n", elapsed(&start));
 385
 386     /* Search and mutation. */
 387     xgettimeofday(&start);
 388     aux.cmap = &cmap;
 389     ovs_mutex_init(&aux.mutex);
 390     threads = xmalloc(n_threads * sizeof *threads);
 391     for (i = 0; i < n_threads; i++) {
 392         threads[i] = ovs_thread_create("search", search_cmap, &aux);
 393     }
 394     for (i = 0; i < n_threads; i++) {
 395         xpthread_join(threads[i], NULL);
 396     }
 397     free(threads);
 398     printf("cmap search:  %5d ms\n", elapsed(&start));
 399
 400     /* Destruction. */
 401     xgettimeofday(&start);
 402     CMAP_FOR_EACH (e, node, &cmap) {
 403         cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
 404     }
 405     cmap_destroy(&cmap);
 406     printf("cmap destroy: %5d ms\n", elapsed(&start));
 407
 408     free(elements);
 409 }
 410
 411 static size_t
 412 find_batch(const struct cmap *cmap, const int value)
 413 {
 414     size_t i, ret;
 415     const size_t end = MIN(n_batch, n_elems - value);
 416     unsigned long map = ~0;
 417     uint32_t hashes[N_BATCH_MAX];
 418     const struct cmap_node *nodes[N_BATCH_MAX];
 419
 420     if (mutation_frac) {
 421         for (i = 0; i < end; i++) {
 422             if (random_uint32() < mutation_frac) {
 423                 break;
 424             }
 425             hashes[i] = hash_int(value + i, 0);
 426         }
 427     } else {
 428         for (i = 0; i < end; i++) {
 429             hashes[i] = hash_int(value + i, 0);
 430         }
 431     }
 432
 433     ret = i;
 434
 435     map >>= BITMAP_ULONG_BITS - i; /* Clear excess bits. */
 436     map = cmap_find_batch(cmap, map, hashes, nodes);
 437
 438     ULLONG_FOR_EACH_1(i, map) {
 439         struct element *e;
 440
 441         CMAP_NODE_FOR_EACH (e, node, nodes[i]) {
 442             if (OVS_LIKELY(e->value == value + i)) {
 443                 ignore(e); /* Found result. */
 444                 break;
 445             }
 446         }
 447     }
 448     return ret;
 449 }
 450
 451 static void *
 452 search_cmap_batched(void *aux_)
 453 {
 454     struct cmap_aux *aux = aux_;
 455     size_t i = 0, j;
 456
 457     for (;;) {
 458         struct element *e;
 459
 460         j = find_batch(aux->cmap, i);
 461         i += j;
 462         if (i >= n_elems) {
 463             break;
 464         }
 465         if (j < n_batch) {
 466             ovs_mutex_lock(&aux->mutex);
 467             e = find(aux->cmap, i);
 468             if (e) {
 469                 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
 470             }
 471             ovs_mutex_unlock(&aux->mutex);
 472         }
 473     }
 474
 475     return NULL;
 476 }
 477
 478 static void
 479 benchmark_cmap_batched(void)
 480 {
 481     struct element *elements;
 482     struct cmap cmap;
 483     struct element *e;
 484     struct timeval start;
 485     pthread_t *threads;
 486     struct cmap_aux aux;
 487     size_t i;
 488
 489     elements = xmalloc(n_elems * sizeof *elements);
 490
 491     /* Insertions. */
 492     xgettimeofday(&start);
 493     cmap_init(&cmap);
 494     for (i = 0; i < n_elems; i++) {
 495         elements[i].value = i;
 496         cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
 497     }
 498     printf("cmap insert:  %5d ms\n", elapsed(&start));
 499
 500     /* Iteration. */
 501     xgettimeofday(&start);
 502     CMAP_FOR_EACH (e, node, &cmap) {
 503         ignore(e);
 504     }
 505     printf("cmap iterate: %5d ms\n", elapsed(&start));
 506
 507     /* Search and mutation. */
 508     xgettimeofday(&start);
 509     aux.cmap = &cmap;
 510     ovs_mutex_init(&aux.mutex);
 511     threads = xmalloc(n_threads * sizeof *threads);
 512     for (i = 0; i < n_threads; i++) {
 513         threads[i] = ovs_thread_create("search", search_cmap_batched, &aux);
 514     }
 515     for (i = 0; i < n_threads; i++) {
 516         xpthread_join(threads[i], NULL);
 517     }
 518     free(threads);
 519     printf("batch search: %5d ms\n", elapsed(&start));
 520
 521     /* Destruction. */
 522     xgettimeofday(&start);
 523     CMAP_FOR_EACH (e, node, &cmap) {
 524         cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
 525     }
 526     cmap_destroy(&cmap);
 527     printf("cmap destroy: %5d ms\n", elapsed(&start));
 528
 529     free(elements);
 530 }
 531 \f
 532 /* hmap benchmark. */
 533 struct helement {
 534     int value;
 535     struct hmap_node node;
 536 };
 537
 538 static struct helement *
 539 hfind(const struct hmap *hmap, int value)
 540 {
 541     struct helement *e;
 542
 543     HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
 544         if (e->value == value) {
 545             return e;
 546         }
 547     }
 548     return NULL;
 549 }
 550
 551 struct hmap_aux {
 552     struct hmap *hmap;
 553     struct fat_rwlock fatlock;
 554 };
 555
 556 static void *
 557 search_hmap(void *aux_)
 558 {
 559     struct hmap_aux *aux = aux_;
 560     size_t i;
 561
 562     if (mutation_frac) {
 563         for (i = 0; i < n_elems; i++) {
 564             if (random_uint32() < mutation_frac) {
 565                 struct helement *e;
 566
 567                 fat_rwlock_wrlock(&aux->fatlock);
 568                 e = hfind(aux->hmap, i);
 569                 if (e) {
 570                     hmap_remove(aux->hmap, &e->node);
 571                 }
 572                 fat_rwlock_unlock(&aux->fatlock);
 573             } else {
 574                 fat_rwlock_rdlock(&aux->fatlock);
 575                 ignore(hfind(aux->hmap, i));
 576                 fat_rwlock_unlock(&aux->fatlock);
 577             }
 578         }
 579     } else {
 580         for (i = 0; i < n_elems; i++) {
 581             ignore(hfind(aux->hmap, i));
 582         }
 583     }
 584     return NULL;
 585 }
 586
 587 static void
 588 benchmark_hmap(void)
 589 {
 590     struct helement *elements;
 591     struct hmap hmap;
 592     struct helement *e, *next;
 593     struct timeval start;
 594     pthread_t *threads;
 595     struct hmap_aux aux;
 596     size_t i;
 597
 598     elements = xmalloc(n_elems * sizeof *elements);
 599
 600     xgettimeofday(&start);
 601     hmap_init(&hmap);
 602     for (i = 0; i < n_elems; i++) {
 603         elements[i].value = i;
 604         hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
 605     }
 606
 607     printf("hmap insert:  %5d ms\n", elapsed(&start));
 608
 609     xgettimeofday(&start);
 610     HMAP_FOR_EACH (e, node, &hmap) {
 611         ignore(e);
 612     }
 613     printf("hmap iterate: %5d ms\n", elapsed(&start));
 614
 615     xgettimeofday(&start);
 616     aux.hmap = &hmap;
 617     fat_rwlock_init(&aux.fatlock);
 618     threads = xmalloc(n_threads * sizeof *threads);
 619     for (i = 0; i < n_threads; i++) {
 620         threads[i] = ovs_thread_create("search", search_hmap, &aux);
 621     }
 622     for (i = 0; i < n_threads; i++) {
 623         xpthread_join(threads[i], NULL);
 624     }
 625     free(threads);
 626     printf("hmap search:  %5d ms\n", elapsed(&start));
 627
 628     /* Destruction. */
 629     xgettimeofday(&start);
 630     HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
 631         hmap_remove(&hmap, &e->node);
 632     }
 633     hmap_destroy(&hmap);
 634     printf("hmap destroy: %5d ms\n", elapsed(&start));
 635
 636     free(elements);
 637 }
 638 \f
 639 static const struct ovs_cmdl_command commands[] = {
 640     {"check", NULL, 0, 1, run_tests},
 641     {"benchmark", NULL, 3, 4, run_benchmarks},
 642     {NULL, NULL, 0, 0, NULL},
 643 };
 644
 645 static void
 646 test_cmap_main(int argc, char *argv[])
 647 {
 648     struct ovs_cmdl_context ctx = {
 649         .argc = argc - optind,
 650         .argv = argv + optind,
 651     };
 652
 653     set_program_name(argv[0]);
 654     ovs_cmdl_run_command(&ctx, commands);
 655 }
 656
 657 OVSTEST_REGISTER("test-cmap", test_cmap_main);