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