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