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