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 "cmap.h"
  22 #include <getopt.h>
  23 #include <string.h>
  24 #include "command-line.h"
  25 #include "fat-rwlock.h"
  26 #include "hash.h"
  27 #include "hmap.h"
  28 #include "ovstest.h"
  29 #include "ovs-thread.h"
  30 #include "random.h"
  31 #include "timeval.h"
  32 #include "util.h"
  33
  34 #undef NDEBUG
  35 #include <assert.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;
  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 cmap_first() returns NULL only when cmap_is_empty(). */
 114     assert(!cmap_first(cmap) == cmap_is_empty(cmap));
 115
 116     /* Check counters. */
 117     assert(cmap_is_empty(cmap) == !n);
 118     assert(cmap_count(cmap) == n);
 119 }
 120
 121 static void
 122 shuffle(int *p, size_t n)
 123 {
 124     for (; n > 1; n--, p++) {
 125         int *q = &p[random_range(n)];
 126         int tmp = *p;
 127         *p = *q;
 128         *q = tmp;
 129     }
 130 }
 131
 132 /* Prints the values in 'cmap', plus 'name' as a title. */
 133 static void OVS_UNUSED
 134 print_cmap(const char *name, struct cmap *cmap)
 135 {
 136     struct cmap_cursor cursor;
 137     struct element *e;
 138
 139     printf("%s:", name);
 140     CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) {
 141         printf(" %d", e->value);
 142     }
 143     printf("\n");
 144 }
 145
 146 /* Prints the 'n' values in 'values', plus 'name' as a title. */
 147 static void OVS_UNUSED
 148 print_ints(const char *name, const int *values, size_t n)
 149 {
 150     size_t i;
 151
 152     printf("%s:", name);
 153     for (i = 0; i < n; i++) {
 154         printf(" %d", values[i]);
 155     }
 156     printf("\n");
 157 }
 158
 159 static size_t
 160 identity_hash(int value)
 161 {
 162     return value;
 163 }
 164
 165 static size_t
 166 good_hash(int value)
 167 {
 168     return hash_int(value, 0x1234abcd);
 169 }
 170
 171 static size_t
 172 constant_hash(int value OVS_UNUSED)
 173 {
 174     return 123;
 175 }
 176
 177 /* Tests basic cmap insertion and deletion. */
 178 static void
 179 test_cmap_insert_replace_delete(hash_func *hash)
 180 {
 181     enum { N_ELEMS = 1000 };
 182
 183     struct element elements[N_ELEMS];
 184     struct element copies[N_ELEMS];
 185     int values[N_ELEMS];
 186     struct cmap cmap;
 187     size_t i;
 188
 189     cmap_init(&cmap);
 190     for (i = 0; i < N_ELEMS; i++) {
 191         elements[i].value = i;
 192         cmap_insert(&cmap, &elements[i].node, hash(i));
 193         values[i] = i;
 194         check_cmap(&cmap, values, i + 1, hash);
 195     }
 196     shuffle(values, N_ELEMS);
 197     for (i = 0; i < N_ELEMS; i++) {
 198         copies[values[i]].value = values[i];
 199         cmap_replace(&cmap, &elements[values[i]].node,
 200                      &copies[values[i]].node, hash(values[i]));
 201         check_cmap(&cmap, values, N_ELEMS, hash);
 202     }
 203     shuffle(values, N_ELEMS);
 204     for (i = 0; i < N_ELEMS; i++) {
 205         cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
 206         check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
 207     }
 208     cmap_destroy(&cmap);
 209 }
 210
 211 static void
 212 run_test(void (*function)(hash_func *))
 213 {
 214     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
 215     size_t i;
 216
 217     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
 218         function(hash_funcs[i]);
 219         printf(".");
 220         fflush(stdout);
 221     }
 222 }
 223
 224 static void
 225 run_tests(int argc, char *argv[])
 226 {
 227     int n;
 228     int i;
 229
 230     n = argc >= 2 ? atoi(argv[1]) : 100;
 231     for (i = 0; i < n; i++) {
 232         run_test(test_cmap_insert_replace_delete);
 233     }
 234     printf("\n");
 235 }
 236 \f
 237 static int n_elems;             /* Number of elements to insert. */
 238 static int n_threads;           /* Number of threads to search and mutate. */
 239 static uint32_t mutation_frac;  /* % mutations, as fraction of UINT32_MAX. */
 240
 241 static void benchmark_cmap(void);
 242 static void benchmark_hmap(void);
 243
 244 static int
 245 elapsed(const struct timeval *start)
 246 {
 247     struct timeval end;
 248
 249     xgettimeofday(&end);
 250     return timeval_to_msec(&end) - timeval_to_msec(start);
 251 }
 252
 253 static void
 254 run_benchmarks(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 255 {
 256     n_elems = strtol(argv[1], NULL, 10);
 257     n_threads = strtol(argv[2], NULL, 10);
 258     mutation_frac = strtod(argv[3], NULL) / 100.0 * UINT32_MAX;
 259
 260     printf("Benchmarking with n=%d, %d threads, %.2f%% mutations:\n",
 261            n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
 262
 263     benchmark_cmap();
 264     putchar('\n');
 265     benchmark_hmap();
 266 }
 267 \f
 268 /* cmap benchmark. */
 269
 270 static struct element *
 271 find(const struct cmap *cmap, int value)
 272 {
 273     struct element *e;
 274
 275     CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
 276         if (e->value == value) {
 277             return e;
 278         }
 279     }
 280     return NULL;
 281 }
 282
 283 struct cmap_aux {
 284     struct ovs_mutex mutex;
 285     struct cmap *cmap;
 286 };
 287
 288 static void *
 289 search_cmap(void *aux_)
 290 {
 291     struct cmap_aux *aux = aux_;
 292     size_t i;
 293
 294     for (i = 0; i < n_elems; i++) {
 295         struct element *e;
 296
 297         if (random_uint32() < mutation_frac) {
 298             ovs_mutex_lock(&aux->mutex);
 299             e = find(aux->cmap, i);
 300             if (e) {
 301                 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
 302             }
 303             ovs_mutex_unlock(&aux->mutex);
 304         } else {
 305             ignore(find(aux->cmap, i));
 306         }
 307     }
 308     return NULL;
 309 }
 310
 311 static void
 312 benchmark_cmap(void)
 313 {
 314     struct element *elements;
 315     struct cmap cmap;
 316     struct element *e;
 317     struct timeval start;
 318     pthread_t *threads;
 319     struct cmap_aux aux;
 320     size_t i;
 321
 322     elements = xmalloc(n_elems * sizeof *elements);
 323
 324     /* Insertions. */
 325     xgettimeofday(&start);
 326     cmap_init(&cmap);
 327     for (i = 0; i < n_elems; i++) {
 328         elements[i].value = i;
 329         cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
 330     }
 331     printf("cmap insert:  %5d ms\n", elapsed(&start));
 332
 333     /* Iteration. */
 334     xgettimeofday(&start);
 335     CMAP_FOR_EACH (e, node, &cmap) {
 336         ignore(e);
 337     }
 338     printf("cmap iterate: %5d ms\n", elapsed(&start));
 339
 340     /* Search and mutation. */
 341     xgettimeofday(&start);
 342     aux.cmap = &cmap;
 343     ovs_mutex_init(&aux.mutex);
 344     threads = xmalloc(n_threads * sizeof *threads);
 345     for (i = 0; i < n_threads; i++) {
 346         threads[i] = ovs_thread_create("search", search_cmap, &aux);
 347     }
 348     for (i = 0; i < n_threads; i++) {
 349         xpthread_join(threads[i], NULL);
 350     }
 351     free(threads);
 352     printf("cmap search:  %5d ms\n", elapsed(&start));
 353
 354     /* Destruction. */
 355     xgettimeofday(&start);
 356     CMAP_FOR_EACH (e, node, &cmap) {
 357         cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
 358     }
 359     cmap_destroy(&cmap);
 360     printf("cmap destroy: %5d ms\n", elapsed(&start));
 361
 362     free(elements);
 363 }
 364 \f
 365 /* hmap benchmark. */
 366 struct helement {
 367     int value;
 368     struct hmap_node node;
 369 };
 370
 371 static struct helement *
 372 hfind(const struct hmap *hmap, int value)
 373 {
 374     struct helement *e;
 375
 376     HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
 377         if (e->value == value) {
 378             return e;
 379         }
 380     }
 381     return NULL;
 382 }
 383
 384 struct hmap_aux {
 385     struct hmap *hmap;
 386     struct fat_rwlock fatlock;
 387 };
 388
 389 static void *
 390 search_hmap(void *aux_)
 391 {
 392     struct hmap_aux *aux = aux_;
 393     size_t i;
 394
 395     for (i = 0; i < n_elems; i++) {
 396         if (mutation_frac) {
 397             if (random_uint32() < mutation_frac) {
 398                 struct helement *e;
 399
 400                 fat_rwlock_wrlock(&aux->fatlock);
 401                 e = hfind(aux->hmap, i);
 402                 if (e) {
 403                     hmap_remove(aux->hmap, &e->node);
 404                 }
 405                 fat_rwlock_unlock(&aux->fatlock);
 406             } else {
 407                 fat_rwlock_rdlock(&aux->fatlock);
 408                 ignore(hfind(aux->hmap, i));
 409                 fat_rwlock_unlock(&aux->fatlock);
 410             }
 411         } else {
 412             hfind(aux->hmap, i);
 413         }
 414     }
 415     return NULL;
 416 }
 417
 418 static void
 419 benchmark_hmap(void)
 420 {
 421     struct helement *elements;
 422     struct hmap hmap;
 423     struct helement *e, *next;
 424     struct timeval start;
 425     pthread_t *threads;
 426     struct hmap_aux aux;
 427     size_t i;
 428
 429     elements = xmalloc(n_elems * sizeof *elements);
 430
 431     xgettimeofday(&start);
 432     hmap_init(&hmap);
 433     for (i = 0; i < n_elems; i++) {
 434         elements[i].value = i;
 435         hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
 436     }
 437
 438     printf("hmap insert:  %5d ms\n", elapsed(&start));
 439
 440     xgettimeofday(&start);
 441     HMAP_FOR_EACH (e, node, &hmap) {
 442         ignore(e);
 443     }
 444     printf("hmap iterate: %5d ms\n", elapsed(&start));
 445
 446     xgettimeofday(&start);
 447     aux.hmap = &hmap;
 448     fat_rwlock_init(&aux.fatlock);
 449     threads = xmalloc(n_threads * sizeof *threads);
 450     for (i = 0; i < n_threads; i++) {
 451         threads[i] = ovs_thread_create("search", search_hmap, &aux);
 452     }
 453     for (i = 0; i < n_threads; i++) {
 454         xpthread_join(threads[i], NULL);
 455     }
 456     free(threads);
 457     printf("hmap search:  %5d ms\n", elapsed(&start));
 458
 459     /* Destruction. */
 460     xgettimeofday(&start);
 461     HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
 462         hmap_remove(&hmap, &e->node);
 463     }
 464     hmap_destroy(&hmap);
 465     printf("hmap destroy: %5d ms\n", elapsed(&start));
 466
 467     free(elements);
 468 }
 469 \f
 470 static const struct command commands[] = {
 471     {"check", 0, 1, run_tests},
 472     {"benchmark", 3, 3, run_benchmarks},
 473     {NULL, 0, 0, NULL},
 474 };
 475
 476 static void
 477 test_cmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 478 {
 479     set_program_name(argv[0]);
 480     run_command(argc - optind, argv + optind, commands);
 481 }
 482
 483 OVSTEST_REGISTER("test-cmap", test_cmap_main);