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"
32 #include "ovs-thread.h"
37 /* Sample cmap element. */
40 struct cmap_node node;
43 typedef size_t hash_func(int value);
46 compare_ints(const void *a_, const void *b_)
50 return *a < *b ? -1 : *a > *b;
53 /* Verifies that 'cmap' contains exactly the 'n' values in 'values'. */
55 check_cmap(struct cmap *cmap, const int values[], size_t n,
58 int *sort_values, *cmap_values, *cmap_values2;
59 const struct element *e;
62 struct cmap_position pos = { 0, 0, 0 };
63 struct cmap_node *node;
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);
70 /* Here we test cursor iteration */
72 CMAP_FOR_EACH (e, node, cmap) {
74 cmap_values[i++] = e->value;
78 /* Here we test iteration with cmap_next_position() */
80 while ((node = cmap_next_position(cmap, &pos))) {
81 struct element *e = NULL;
82 e = OBJECT_CONTAINING(node, e, node);
85 cmap_values2[i++] = e->value;
89 memcpy(sort_values, values, sizeof *sort_values * n);
90 qsort(sort_values, n, sizeof *sort_values, compare_ints);
91 qsort(cmap_values, n, sizeof *cmap_values, compare_ints);
92 qsort(cmap_values2, n, sizeof *cmap_values2, compare_ints);
94 for (i = 0; i < n; i++) {
95 assert(sort_values[i] == cmap_values[i]);
96 assert(sort_values[i] == cmap_values2[i]);
103 /* Check that all the values are there in lookup. */
104 for (i = 0; i < n; i++) {
107 CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) {
108 count += e->value == values[i];
113 /* Check that all the values are there in batched lookup. */
114 batch_size = n % BITMAP_ULONG_BITS + 1;
115 for (i = 0; i < n; i += batch_size) {
117 uint32_t hashes[sizeof map * CHAR_BIT];
118 const struct cmap_node *nodes[sizeof map * CHAR_BIT];
122 j = MIN(n - i, batch_size); /* Actual batch size. */
123 map = ~0UL >> (BITMAP_ULONG_BITS - j);
125 for (k = 0; k < j; k++) {
126 hashes[k] = hash(values[i + k]);
128 map = cmap_find_batch(cmap, map, hashes, nodes);
130 ULLONG_FOR_EACH_1(k, map) {
133 CMAP_NODE_FOR_EACH (e, node, nodes[k]) {
134 count += e->value == values[i + k];
137 assert(count == j); /* j elements in a batch. */
140 /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
141 assert(!cmap_first(cmap) == cmap_is_empty(cmap));
143 /* Check counters. */
144 assert(cmap_is_empty(cmap) == !n);
145 assert(cmap_count(cmap) == n);
149 shuffle(int *p, size_t n)
151 for (; n > 1; n--, p++) {
152 int *q = &p[random_range(n)];
159 /* Prints the values in 'cmap', plus 'name' as a title. */
160 static void OVS_UNUSED
161 print_cmap(const char *name, struct cmap *cmap)
163 struct cmap_cursor cursor;
167 CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) {
168 printf(" %d", e->value);
173 /* Prints the 'n' values in 'values', plus 'name' as a title. */
174 static void OVS_UNUSED
175 print_ints(const char *name, const int *values, size_t n)
180 for (i = 0; i < n; i++) {
181 printf(" %d", values[i]);
187 identity_hash(int value)
195 return hash_int(value, 0x1234abcd);
199 constant_hash(int value OVS_UNUSED)
204 /* Tests basic cmap insertion and deletion. */
206 test_cmap_insert_replace_delete(hash_func *hash)
208 enum { N_ELEMS = 1000 };
210 struct element elements[N_ELEMS];
211 struct element copies[N_ELEMS];
213 struct cmap cmap = CMAP_INITIALIZER;
216 for (i = 0; i < N_ELEMS; i++) {
217 elements[i].value = i;
218 cmap_insert(&cmap, &elements[i].node, hash(i));
220 check_cmap(&cmap, values, i + 1, hash);
222 shuffle(values, N_ELEMS);
223 for (i = 0; i < N_ELEMS; i++) {
224 copies[values[i]].value = values[i];
225 cmap_replace(&cmap, &elements[values[i]].node,
226 &copies[values[i]].node, hash(values[i]));
227 check_cmap(&cmap, values, N_ELEMS, hash);
229 shuffle(values, N_ELEMS);
230 for (i = 0; i < N_ELEMS; i++) {
231 cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
232 check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
238 run_test(void (*function)(hash_func *))
240 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
243 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
244 function(hash_funcs[i]);
251 run_tests(struct ovs_cmdl_context *ctx)
256 n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
257 for (i = 0; i < n; i++) {
258 run_test(test_cmap_insert_replace_delete);
263 static int n_elems; /* Number of elements to insert. */
264 static int n_threads; /* Number of threads to search and mutate. */
265 static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */
266 static int n_batch; /* Number of elements in each batch. */
268 #define N_BATCH_MAX BITMAP_ULONG_BITS
270 static void benchmark_cmap(void);
271 static void benchmark_cmap_batched(void);
272 static void benchmark_hmap(void);
275 elapsed(const struct timeval *start)
280 return timeval_to_msec(&end) - timeval_to_msec(start);
284 run_benchmarks(struct ovs_cmdl_context *ctx)
286 n_elems = strtol(ctx->argv[1], NULL, 10);
287 n_threads = strtol(ctx->argv[2], NULL, 10);
288 mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX;
289 n_batch = ctx->argc > 4 ? strtol(ctx->argv[4], NULL, 10) : 1;
291 if (n_batch > N_BATCH_MAX) {
292 n_batch = N_BATCH_MAX;
294 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n",
295 n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.,
299 benchmark_cmap_batched();
307 /* cmap benchmark. */
309 static struct element *
310 find(const struct cmap *cmap, int value)
314 CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
315 if (e->value == value) {
323 struct ovs_mutex mutex;
328 search_cmap(void *aux_)
330 struct cmap_aux *aux = aux_;
334 for (i = 0; i < n_elems; i++) {
337 if (random_uint32() < mutation_frac) {
338 ovs_mutex_lock(&aux->mutex);
339 e = find(aux->cmap, i);
341 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
343 ovs_mutex_unlock(&aux->mutex);
345 ignore(find(aux->cmap, i));
349 for (i = 0; i < n_elems; i++) {
350 ignore(find(aux->cmap, i));
359 struct element *elements;
362 struct timeval start;
367 elements = xmalloc(n_elems * sizeof *elements);
370 xgettimeofday(&start);
372 for (i = 0; i < n_elems; i++) {
373 elements[i].value = i;
374 cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
376 printf("cmap insert: %5d ms\n", elapsed(&start));
379 xgettimeofday(&start);
380 CMAP_FOR_EACH (e, node, &cmap) {
383 printf("cmap iterate: %5d ms\n", elapsed(&start));
385 /* Search and mutation. */
386 xgettimeofday(&start);
388 ovs_mutex_init(&aux.mutex);
389 threads = xmalloc(n_threads * sizeof *threads);
390 for (i = 0; i < n_threads; i++) {
391 threads[i] = ovs_thread_create("search", search_cmap, &aux);
393 for (i = 0; i < n_threads; i++) {
394 xpthread_join(threads[i], NULL);
397 printf("cmap search: %5d ms\n", elapsed(&start));
400 xgettimeofday(&start);
401 CMAP_FOR_EACH (e, node, &cmap) {
402 cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
405 printf("cmap destroy: %5d ms\n", elapsed(&start));
411 find_batch(const struct cmap *cmap, const int value)
414 const size_t end = MIN(n_batch, n_elems - value);
415 unsigned long map = ~0;
416 uint32_t hashes[N_BATCH_MAX];
417 const struct cmap_node *nodes[N_BATCH_MAX];
420 for (i = 0; i < end; i++) {
421 if (random_uint32() < mutation_frac) {
424 hashes[i] = hash_int(value + i, 0);
427 for (i = 0; i < end; i++) {
428 hashes[i] = hash_int(value + i, 0);
434 map >>= BITMAP_ULONG_BITS - i; /* Clear excess bits. */
435 map = cmap_find_batch(cmap, map, hashes, nodes);
437 ULLONG_FOR_EACH_1(i, map) {
440 CMAP_NODE_FOR_EACH (e, node, nodes[i]) {
441 if (OVS_LIKELY(e->value == value + i)) {
442 ignore(e); /* Found result. */
451 search_cmap_batched(void *aux_)
453 struct cmap_aux *aux = aux_;
459 j = find_batch(aux->cmap, i);
465 ovs_mutex_lock(&aux->mutex);
466 e = find(aux->cmap, i);
468 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
470 ovs_mutex_unlock(&aux->mutex);
478 benchmark_cmap_batched(void)
480 struct element *elements;
483 struct timeval start;
488 elements = xmalloc(n_elems * sizeof *elements);
491 xgettimeofday(&start);
493 for (i = 0; i < n_elems; i++) {
494 elements[i].value = i;
495 cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
497 printf("cmap insert: %5d ms\n", elapsed(&start));
500 xgettimeofday(&start);
501 CMAP_FOR_EACH (e, node, &cmap) {
504 printf("cmap iterate: %5d ms\n", elapsed(&start));
506 /* Search and mutation. */
507 xgettimeofday(&start);
509 ovs_mutex_init(&aux.mutex);
510 threads = xmalloc(n_threads * sizeof *threads);
511 for (i = 0; i < n_threads; i++) {
512 threads[i] = ovs_thread_create("search", search_cmap_batched, &aux);
514 for (i = 0; i < n_threads; i++) {
515 xpthread_join(threads[i], NULL);
518 printf("batch search: %5d ms\n", elapsed(&start));
521 xgettimeofday(&start);
522 CMAP_FOR_EACH (e, node, &cmap) {
523 cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
526 printf("cmap destroy: %5d ms\n", elapsed(&start));
531 /* hmap benchmark. */
534 struct hmap_node node;
537 static struct helement *
538 hfind(const struct hmap *hmap, int value)
542 HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
543 if (e->value == value) {
552 struct fat_rwlock fatlock;
556 search_hmap(void *aux_)
558 struct hmap_aux *aux = aux_;
562 for (i = 0; i < n_elems; i++) {
563 if (random_uint32() < mutation_frac) {
566 fat_rwlock_wrlock(&aux->fatlock);
567 e = hfind(aux->hmap, i);
569 hmap_remove(aux->hmap, &e->node);
571 fat_rwlock_unlock(&aux->fatlock);
573 fat_rwlock_rdlock(&aux->fatlock);
574 ignore(hfind(aux->hmap, i));
575 fat_rwlock_unlock(&aux->fatlock);
579 for (i = 0; i < n_elems; i++) {
580 ignore(hfind(aux->hmap, i));
589 struct helement *elements;
591 struct helement *e, *next;
592 struct timeval start;
597 elements = xmalloc(n_elems * sizeof *elements);
599 xgettimeofday(&start);
601 for (i = 0; i < n_elems; i++) {
602 elements[i].value = i;
603 hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
606 printf("hmap insert: %5d ms\n", elapsed(&start));
608 xgettimeofday(&start);
609 HMAP_FOR_EACH (e, node, &hmap) {
612 printf("hmap iterate: %5d ms\n", elapsed(&start));
614 xgettimeofday(&start);
616 fat_rwlock_init(&aux.fatlock);
617 threads = xmalloc(n_threads * sizeof *threads);
618 for (i = 0; i < n_threads; i++) {
619 threads[i] = ovs_thread_create("search", search_hmap, &aux);
621 for (i = 0; i < n_threads; i++) {
622 xpthread_join(threads[i], NULL);
625 printf("hmap search: %5d ms\n", elapsed(&start));
628 xgettimeofday(&start);
629 HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
630 hmap_remove(&hmap, &e->node);
633 printf("hmap destroy: %5d ms\n", elapsed(&start));
638 static const struct ovs_cmdl_command commands[] = {
639 {"check", NULL, 0, 1, run_tests},
640 {"benchmark", NULL, 3, 4, run_benchmarks},
641 {NULL, NULL, 0, 0, NULL},
645 test_cmap_main(int argc, char *argv[])
647 struct ovs_cmdl_context ctx = {
648 .argc = argc - optind,
649 .argv = argv + optind,
652 set_program_name(argv[0]);
653 ovs_cmdl_run_command(&ctx, commands);
656 OVSTEST_REGISTER("test-cmap", test_cmap_main);