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     if (mutation_frac) {
 295         for (i = 0; i < n_elems; i++) {
 296             struct element *e;
 297
 298             if (random_uint32() < mutation_frac) {
 299                 ovs_mutex_lock(&aux->mutex);
 300                 e = find(aux->cmap, i);
 301                 if (e) {
 302                     cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
 303                 }
 304                 ovs_mutex_unlock(&aux->mutex);
 305             } else {
 306                 ignore(find(aux->cmap, i));
 307             }
 308         }
 309     } else {
 310         for (i = 0; i < n_elems; i++) {
 311             ignore(find(aux->cmap, i));
 312         }
 313     }
 314     return NULL;
 315 }
 316
 317 static void
 318 benchmark_cmap(void)
 319 {
 320     struct element *elements;
 321     struct cmap cmap;
 322     struct element *e;
 323     struct timeval start;
 324     pthread_t *threads;
 325     struct cmap_aux aux;
 326     size_t i;
 327
 328     elements = xmalloc(n_elems * sizeof *elements);
 329
 330     /* Insertions. */
 331     xgettimeofday(&start);
 332     cmap_init(&cmap);
 333     for (i = 0; i < n_elems; i++) {
 334         elements[i].value = i;
 335         cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
 336     }
 337     printf("cmap insert:  %5d ms\n", elapsed(&start));
 338
 339     /* Iteration. */
 340     xgettimeofday(&start);
 341     CMAP_FOR_EACH (e, node, &cmap) {
 342         ignore(e);
 343     }
 344     printf("cmap iterate: %5d ms\n", elapsed(&start));
 345
 346     /* Search and mutation. */
 347     xgettimeofday(&start);
 348     aux.cmap = &cmap;
 349     ovs_mutex_init(&aux.mutex);
 350     threads = xmalloc(n_threads * sizeof *threads);
 351     for (i = 0; i < n_threads; i++) {
 352         threads[i] = ovs_thread_create("search", search_cmap, &aux);
 353     }
 354     for (i = 0; i < n_threads; i++) {
 355         xpthread_join(threads[i], NULL);
 356     }
 357     free(threads);
 358     printf("cmap search:  %5d ms\n", elapsed(&start));
 359
 360     /* Destruction. */
 361     xgettimeofday(&start);
 362     CMAP_FOR_EACH (e, node, &cmap) {
 363         cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
 364     }
 365     cmap_destroy(&cmap);
 366     printf("cmap destroy: %5d ms\n", elapsed(&start));
 367
 368     free(elements);
 369 }
 370 \f
 371 /* hmap benchmark. */
 372 struct helement {
 373     int value;
 374     struct hmap_node node;
 375 };
 376
 377 static struct helement *
 378 hfind(const struct hmap *hmap, int value)
 379 {
 380     struct helement *e;
 381
 382     HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
 383         if (e->value == value) {
 384             return e;
 385         }
 386     }
 387     return NULL;
 388 }
 389
 390 struct hmap_aux {
 391     struct hmap *hmap;
 392     struct fat_rwlock fatlock;
 393 };
 394
 395 static void *
 396 search_hmap(void *aux_)
 397 {
 398     struct hmap_aux *aux = aux_;
 399     size_t i;
 400
 401     if (mutation_frac) {
 402         for (i = 0; i < n_elems; i++) {
 403             if (random_uint32() < mutation_frac) {
 404                 struct helement *e;
 405
 406                 fat_rwlock_wrlock(&aux->fatlock);
 407                 e = hfind(aux->hmap, i);
 408                 if (e) {
 409                     hmap_remove(aux->hmap, &e->node);
 410                 }
 411                 fat_rwlock_unlock(&aux->fatlock);
 412             } else {
 413                 fat_rwlock_rdlock(&aux->fatlock);
 414                 ignore(hfind(aux->hmap, i));
 415                 fat_rwlock_unlock(&aux->fatlock);
 416             }
 417         }
 418     } else {
 419         for (i = 0; i < n_elems; i++) {
 420             ignore(hfind(aux->hmap, i));
 421         }
 422     }
 423     return NULL;
 424 }
 425
 426 static void
 427 benchmark_hmap(void)
 428 {
 429     struct helement *elements;
 430     struct hmap hmap;
 431     struct helement *e, *next;
 432     struct timeval start;
 433     pthread_t *threads;
 434     struct hmap_aux aux;
 435     size_t i;
 436
 437     elements = xmalloc(n_elems * sizeof *elements);
 438
 439     xgettimeofday(&start);
 440     hmap_init(&hmap);
 441     for (i = 0; i < n_elems; i++) {
 442         elements[i].value = i;
 443         hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
 444     }
 445
 446     printf("hmap insert:  %5d ms\n", elapsed(&start));
 447
 448     xgettimeofday(&start);
 449     HMAP_FOR_EACH (e, node, &hmap) {
 450         ignore(e);
 451     }
 452     printf("hmap iterate: %5d ms\n", elapsed(&start));
 453
 454     xgettimeofday(&start);
 455     aux.hmap = &hmap;
 456     fat_rwlock_init(&aux.fatlock);
 457     threads = xmalloc(n_threads * sizeof *threads);
 458     for (i = 0; i < n_threads; i++) {
 459         threads[i] = ovs_thread_create("search", search_hmap, &aux);
 460     }
 461     for (i = 0; i < n_threads; i++) {
 462         xpthread_join(threads[i], NULL);
 463     }
 464     free(threads);
 465     printf("hmap search:  %5d ms\n", elapsed(&start));
 466
 467     /* Destruction. */
 468     xgettimeofday(&start);
 469     HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
 470         hmap_remove(&hmap, &e->node);
 471     }
 472     hmap_destroy(&hmap);
 473     printf("hmap destroy: %5d ms\n", elapsed(&start));
 474
 475     free(elements);
 476 }
 477 \f
 478 static const struct command commands[] = {
 479     {"check", 0, 1, run_tests},
 480     {"benchmark", 3, 3, run_benchmarks},
 481     {NULL, 0, 0, NULL},
 482 };
 483
 484 static void
 485 test_cmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 486 {
 487     set_program_name(argv[0]);
 488     run_command(argc - optind, argv + optind, commands);
 489 }
 490
 491 OVSTEST_REGISTER("test-cmap", test_cmap_main);