tests/test-ccmap.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2013, 2014, 2016 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  * ccmap.h. */
  19
  20 #include <config.h>
  21 #undef NDEBUG
  22 #include "ccmap.h"
  23 #include <assert.h>
  24 #include <getopt.h>
  25 #include <string.h>
  26 #include "bitmap.h"
  27 #include "command-line.h"
  28 #include "fat-rwlock.h"
  29 #include "hash.h"
  30 #include "openvswitch/hmap.h"
  31 #include "ovstest.h"
  32 #include "ovs-thread.h"
  33 #include "random.h"
  34 #include "timeval.h"
  35 #include "util.h"
  36
  37 typedef size_t hash_func(int value);
  38
  39 static int
  40 compare_uint32s(const void *a_, const void *b_)
  41 {
  42     const uint32_t *a = a_;
  43     const uint32_t *b = b_;
  44     return *a < *b ? -1 : *a > *b;
  45 }
  46
  47 /* Verifies that 'ccmap' contains exactly the 'n' values in 'values'. */
  48 static void
  49 check_ccmap(struct ccmap *ccmap, const int values[], size_t n, hash_func *hash)
  50 {
  51     uint32_t *hashes = xmalloc(sizeof *hashes * n);
  52     int i;
  53
  54     for (i = 0; i < n; i++) {
  55         hashes[i] = hash(values[i]);
  56     }
  57     qsort(hashes, n, sizeof *hashes, compare_uint32s);
  58
  59     /* Check that all the values are there in lookup. */
  60     for (i = 0; i < n; i++) {
  61         uint32_t h = hashes[i];
  62         size_t count = ccmap_find(ccmap, h);
  63
  64         assert(count);   /* Must have at least one. */
  65         assert(i + count <= n); /* May not have too many. */
  66
  67         /* Skip colliding hash values and assert they were in the count. */
  68         while (--count) {
  69             i++;
  70             assert(hashes[i] == h);
  71         }
  72         /* Make sure next hash is different. */
  73         if (i + 1 < n) {
  74             assert(hashes[i + 1] != h);
  75         }
  76     }
  77
  78     /* Check counters. */
  79     assert(ccmap_is_empty(ccmap) == !n);
  80     assert(ccmap_count(ccmap) == n);
  81
  82     free(hashes);
  83 }
  84
  85 static void
  86 shuffle(int *p, size_t n)
  87 {
  88     for (; n > 1; n--, p++) {
  89         int *q = &p[random_range(n)];
  90         int tmp = *p;
  91
  92         *p = *q;
  93         *q = tmp;
  94     }
  95 }
  96
  97 static size_t
  98 identity_hash(int value)
  99 {
 100     return value;
 101 }
 102
 103 static size_t
 104 good_hash(int value)
 105 {
 106     return hash_int(value, 0x1234abcd);
 107 }
 108
 109 static size_t
 110 constant_hash(int value OVS_UNUSED)
 111 {
 112     return 123;
 113 }
 114
 115 /* Tests basic ccmap increment and decrement. */
 116 static void
 117 test_ccmap_inc_dec(hash_func *hash)
 118 {
 119     enum { N_ELEMS = 1000 };
 120
 121     int values[N_ELEMS];
 122     struct ccmap ccmap;
 123     size_t i;
 124
 125     ccmap_init(&ccmap);
 126     for (i = 0; i < N_ELEMS; i++) {
 127         ccmap_inc(&ccmap, hash(i));
 128         values[i] = i;
 129         check_ccmap(&ccmap, values, i + 1, hash);
 130     }
 131     shuffle(values, N_ELEMS);
 132     for (i = 0; i < N_ELEMS; i++) {
 133         ccmap_dec(&ccmap, hash(values[i]));
 134         check_ccmap(&ccmap, values + (i + 1), N_ELEMS - (i + 1), hash);
 135     }
 136     ccmap_destroy(&ccmap);
 137 }
 138
 139 static void
 140 run_test(void (*function)(hash_func *))
 141 {
 142     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
 143
 144     for (size_t i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
 145         function(hash_funcs[i]);
 146         printf(".");
 147         fflush(stdout);
 148     }
 149 }
 150
 151 static void
 152 run_tests(struct ovs_cmdl_context *ctx)
 153 {
 154     int n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
 155     for (int i = 0; i < n; i++) {
 156         run_test(test_ccmap_inc_dec);
 157     }
 158     printf("\n");
 159 }
 160 \f
 161 static int n_elems;             /* Number of elements to insert. */
 162 static int n_threads;           /* Number of threads to search and mutate. */
 163 static uint32_t mutation_frac;  /* % mutations, as fraction of UINT32_MAX. */
 164
 165
 166 static void benchmark_ccmap(void);
 167
 168 static int
 169 elapsed(const struct timeval *start)
 170 {
 171     struct timeval end;
 172
 173     xgettimeofday(&end);
 174     return timeval_to_msec(&end) - timeval_to_msec(start);
 175 }
 176
 177 static void
 178 run_benchmarks(struct ovs_cmdl_context *ctx)
 179 {
 180     n_elems = strtol(ctx->argv[1], NULL, 10);
 181     n_threads = strtol(ctx->argv[2], NULL, 10);
 182     mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX;
 183
 184     printf("Benchmarking with n=%d, %d threads, %.2f%% mutations\n",
 185            n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
 186
 187     benchmark_ccmap();
 188 }
 189 \f
 190 /* ccmap benchmark. */
 191
 192 struct ccmap_aux {
 193     struct ovs_mutex mutex;
 194     struct ccmap *ccmap;
 195 };
 196
 197 static void *
 198 search_ccmap(void *aux_)
 199 {
 200     struct ccmap_aux *aux = aux_;
 201     size_t i;
 202
 203     if (mutation_frac) {
 204         for (i = 0; i < n_elems; i++) {
 205             uint32_t hash = hash_int(i, 0);
 206
 207             if (random_uint32() < mutation_frac) {
 208                 ovs_mutex_lock(&aux->mutex);
 209                 uint32_t count = ccmap_find(aux->ccmap, hash);
 210                 if (count) {
 211                     ccmap_dec(aux->ccmap, hash);
 212                 }
 213                 ovs_mutex_unlock(&aux->mutex);
 214             } else {
 215                 ignore(ccmap_find(aux->ccmap, hash));
 216             }
 217         }
 218     } else {
 219         for (i = 0; i < n_elems; i++) {
 220             ignore(ccmap_find(aux->ccmap, hash_int(i, 0)));
 221         }
 222     }
 223     return NULL;
 224 }
 225
 226 static void
 227 benchmark_ccmap(void)
 228 {
 229     struct ccmap ccmap;
 230     struct timeval start;
 231     pthread_t *threads;
 232     struct ccmap_aux aux;
 233     size_t i;
 234
 235     /* Insertions. */
 236     xgettimeofday(&start);
 237     ccmap_init(&ccmap);
 238     for (i = 0; i < n_elems; i++) {
 239         ccmap_inc(&ccmap, hash_int(i, 0));
 240     }
 241     printf("ccmap insert:  %5d ms\n", elapsed(&start));
 242
 243     /* Search and mutation. */
 244     xgettimeofday(&start);
 245     aux.ccmap = &ccmap;
 246     ovs_mutex_init(&aux.mutex);
 247     threads = xmalloc(n_threads * sizeof *threads);
 248     for (i = 0; i < n_threads; i++) {
 249         threads[i] = ovs_thread_create("search", search_ccmap, &aux);
 250     }
 251     for (i = 0; i < n_threads; i++) {
 252         xpthread_join(threads[i], NULL);
 253     }
 254     free(threads);
 255     printf("ccmap search:  %5d ms\n", elapsed(&start));
 256
 257     /* Destruction. */
 258     xgettimeofday(&start);
 259     for (i = 0; i < n_elems; i++) {
 260         uint32_t hash = hash_int(i, 0);
 261
 262         if (ccmap_find(&ccmap, hash)) {
 263             /* Also remove any colliding hashes. */
 264             while (ccmap_dec(&ccmap, hash)) {
 265                 ;
 266             }
 267         }
 268     }
 269     ccmap_destroy(&ccmap);
 270     printf("ccmap destroy: %5d ms\n", elapsed(&start));
 271 }
 272
 273 \f
 274 static const struct ovs_cmdl_command commands[] = {
 275     {"check", NULL, 0, 1, run_tests, OVS_RO},
 276     {"benchmark", NULL, 3, 3, run_benchmarks, OVS_RO},
 277     {NULL, NULL, 0, 0, NULL, OVS_RO},
 278 };
 279
 280 static void
 281 test_ccmap_main(int argc, char *argv[])
 282 {
 283     struct ovs_cmdl_context ctx = {
 284         .argc = argc - optind,
 285         .argv = argv + optind,
 286     };
 287
 288     set_program_name(argv[0]);
 289     ovs_cmdl_run_command(&ctx, commands);
 290 }
 291
 292 OVSTEST_REGISTER("test-ccmap", test_ccmap_main);