2 * Copyright (c) 2008, 2009, 2010, 2013, 2014, 2016 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 /* A non-exhaustive test for some of the functions and macros declared in
27 #include "command-line.h"
28 #include "fat-rwlock.h"
30 #include "openvswitch/hmap.h"
32 #include "ovs-thread.h"
37 typedef size_t hash_func(int value);
40 compare_uint32s(const void *a_, const void *b_)
42 const uint32_t *a = a_;
43 const uint32_t *b = b_;
44 return *a < *b ? -1 : *a > *b;
47 /* Verifies that 'ccmap' contains exactly the 'n' values in 'values'. */
49 check_ccmap(struct ccmap *ccmap, const int values[], size_t n, hash_func *hash)
51 uint32_t *hashes = xmalloc(sizeof *hashes * n);
54 for (i = 0; i < n; i++) {
55 hashes[i] = hash(values[i]);
57 qsort(hashes, n, sizeof *hashes, compare_uint32s);
59 /* Check that all the values are there in lookup. */
60 for (i = 0; i < n; i++) {
61 uint32_t hash = hashes[i];
62 size_t count = ccmap_find(ccmap, hash);
64 assert(count); /* Must have at least one. */
65 assert(i + count <= n); /* May not have too many. */
67 /* Skip colliding hash values and assert they were in the count. */
70 assert(hashes[i] == hash);
72 /* Make sure next hash is different. */
74 assert(hashes[i + 1] != hash);
79 assert(ccmap_is_empty(ccmap) == !n);
80 assert(ccmap_count(ccmap) == n);
86 shuffle(int *p, size_t n)
88 for (; n > 1; n--, p++) {
89 int *q = &p[random_range(n)];
98 identity_hash(int value)
106 return hash_int(value, 0x1234abcd);
110 constant_hash(int value OVS_UNUSED)
115 /* Tests basic ccmap increment and decrement. */
117 test_ccmap_inc_dec(hash_func *hash)
119 enum { N_ELEMS = 1000 };
126 for (i = 0; i < N_ELEMS; i++) {
127 ccmap_inc(&ccmap, hash(i));
129 check_ccmap(&ccmap, values, i + 1, hash);
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);
136 ccmap_destroy(&ccmap);
140 run_test(void (*function)(hash_func *))
142 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
144 for (size_t i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
145 function(hash_funcs[i]);
152 run_tests(struct ovs_cmdl_context *ctx)
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);
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. */
166 static void benchmark_ccmap(void);
169 elapsed(const struct timeval *start)
174 return timeval_to_msec(&end) - timeval_to_msec(start);
178 run_benchmarks(struct ovs_cmdl_context *ctx)
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;
184 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations\n",
185 n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
190 /* ccmap benchmark. */
193 struct ovs_mutex mutex;
198 search_ccmap(void *aux_)
200 struct ccmap_aux *aux = aux_;
204 for (i = 0; i < n_elems; i++) {
205 uint32_t hash = hash_int(i, 0);
207 if (random_uint32() < mutation_frac) {
208 ovs_mutex_lock(&aux->mutex);
209 uint32_t count = ccmap_find(aux->ccmap, hash);
211 ccmap_dec(aux->ccmap, hash);
213 ovs_mutex_unlock(&aux->mutex);
215 ignore(ccmap_find(aux->ccmap, hash));
219 for (i = 0; i < n_elems; i++) {
220 ignore(ccmap_find(aux->ccmap, hash_int(i, 0)));
227 benchmark_ccmap(void)
230 struct timeval start;
232 struct ccmap_aux aux;
236 xgettimeofday(&start);
238 for (i = 0; i < n_elems; i++) {
239 ccmap_inc(&ccmap, hash_int(i, 0));
241 printf("ccmap insert: %5d ms\n", elapsed(&start));
243 /* Search and mutation. */
244 xgettimeofday(&start);
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);
251 for (i = 0; i < n_threads; i++) {
252 xpthread_join(threads[i], NULL);
255 printf("ccmap search: %5d ms\n", elapsed(&start));
258 xgettimeofday(&start);
259 for (i = 0; i < n_elems; i++) {
260 uint32_t hash = hash_int(i, 0);
262 if (ccmap_find(&ccmap, hash)) {
263 /* Also remove any colliding hashes. */
264 while (ccmap_dec(&ccmap, hash)) {
269 ccmap_destroy(&ccmap);
270 printf("ccmap destroy: %5d ms\n", elapsed(&start));
274 static const struct ovs_cmdl_command commands[] = {
275 {"check", NULL, 0, 1, run_tests},
276 {"benchmark", NULL, 3, 3, run_benchmarks},
277 {NULL, NULL, 0, 0, NULL},
281 test_ccmap_main(int argc, char *argv[])
283 struct ovs_cmdl_context ctx = {
284 .argc = argc - optind,
285 .argv = argv + optind,
288 set_program_name(argv[0]);
289 ovs_cmdl_run_command(&ctx, commands);
292 OVSTEST_REGISTER("test-ccmap", test_ccmap_main);