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