2 * Copyright (c) 2008, 2009, 2010, 2013, 2014 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];
217 for (i = 0; i < N_ELEMS; i++) {
218 elements[i].value = i;
219 cmap_insert(&cmap, &elements[i].node, hash(i));
221 check_cmap(&cmap, values, i + 1, hash);
223 shuffle(values, N_ELEMS);
224 for (i = 0; i < N_ELEMS; i++) {
225 copies[values[i]].value = values[i];
226 cmap_replace(&cmap, &elements[values[i]].node,
227 &copies[values[i]].node, hash(values[i]));
228 check_cmap(&cmap, values, N_ELEMS, hash);
230 shuffle(values, N_ELEMS);
231 for (i = 0; i < N_ELEMS; i++) {
232 cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
233 check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
239 run_test(void (*function)(hash_func *))
241 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
244 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
245 function(hash_funcs[i]);
252 run_tests(struct ovs_cmdl_context *ctx)
257 n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
258 for (i = 0; i < n; i++) {
259 run_test(test_cmap_insert_replace_delete);
264 static int n_elems; /* Number of elements to insert. */
265 static int n_threads; /* Number of threads to search and mutate. */
266 static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */
267 static int n_batch; /* Number of elements in each batch. */
269 #define N_BATCH_MAX BITMAP_ULONG_BITS
271 static void benchmark_cmap(void);
272 static void benchmark_cmap_batched(void);
273 static void benchmark_hmap(void);
276 elapsed(const struct timeval *start)
281 return timeval_to_msec(&end) - timeval_to_msec(start);
285 run_benchmarks(struct ovs_cmdl_context *ctx)
287 n_elems = strtol(ctx->argv[1], NULL, 10);
288 n_threads = strtol(ctx->argv[2], NULL, 10);
289 mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX;
290 n_batch = ctx->argc > 4 ? strtol(ctx->argv[4], NULL, 10) : 1;
292 if (n_batch > N_BATCH_MAX) {
293 n_batch = N_BATCH_MAX;
295 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n",
296 n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.,
300 benchmark_cmap_batched();
308 /* cmap benchmark. */
310 static struct element *
311 find(const struct cmap *cmap, int value)
315 CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
316 if (e->value == value) {
324 struct ovs_mutex mutex;
329 search_cmap(void *aux_)
331 struct cmap_aux *aux = aux_;
335 for (i = 0; i < n_elems; i++) {
338 if (random_uint32() < mutation_frac) {
339 ovs_mutex_lock(&aux->mutex);
340 e = find(aux->cmap, i);
342 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
344 ovs_mutex_unlock(&aux->mutex);
346 ignore(find(aux->cmap, i));
350 for (i = 0; i < n_elems; i++) {
351 ignore(find(aux->cmap, i));
360 struct element *elements;
363 struct timeval start;
368 elements = xmalloc(n_elems * sizeof *elements);
371 xgettimeofday(&start);
373 for (i = 0; i < n_elems; i++) {
374 elements[i].value = i;
375 cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
377 printf("cmap insert: %5d ms\n", elapsed(&start));
380 xgettimeofday(&start);
381 CMAP_FOR_EACH (e, node, &cmap) {
384 printf("cmap iterate: %5d ms\n", elapsed(&start));
386 /* Search and mutation. */
387 xgettimeofday(&start);
389 ovs_mutex_init(&aux.mutex);
390 threads = xmalloc(n_threads * sizeof *threads);
391 for (i = 0; i < n_threads; i++) {
392 threads[i] = ovs_thread_create("search", search_cmap, &aux);
394 for (i = 0; i < n_threads; i++) {
395 xpthread_join(threads[i], NULL);
398 printf("cmap search: %5d ms\n", elapsed(&start));
401 xgettimeofday(&start);
402 CMAP_FOR_EACH (e, node, &cmap) {
403 cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
406 printf("cmap destroy: %5d ms\n", elapsed(&start));
412 find_batch(const struct cmap *cmap, const int value)
415 const size_t end = MIN(n_batch, n_elems - value);
416 unsigned long map = ~0;
417 uint32_t hashes[N_BATCH_MAX];
418 const struct cmap_node *nodes[N_BATCH_MAX];
421 for (i = 0; i < end; i++) {
422 if (random_uint32() < mutation_frac) {
425 hashes[i] = hash_int(value + i, 0);
428 for (i = 0; i < end; i++) {
429 hashes[i] = hash_int(value + i, 0);
435 map >>= BITMAP_ULONG_BITS - i; /* Clear excess bits. */
436 map = cmap_find_batch(cmap, map, hashes, nodes);
438 ULLONG_FOR_EACH_1(i, map) {
441 CMAP_NODE_FOR_EACH (e, node, nodes[i]) {
442 if (OVS_LIKELY(e->value == value + i)) {
443 ignore(e); /* Found result. */
452 search_cmap_batched(void *aux_)
454 struct cmap_aux *aux = aux_;
460 j = find_batch(aux->cmap, i);
466 ovs_mutex_lock(&aux->mutex);
467 e = find(aux->cmap, i);
469 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
471 ovs_mutex_unlock(&aux->mutex);
479 benchmark_cmap_batched(void)
481 struct element *elements;
484 struct timeval start;
489 elements = xmalloc(n_elems * sizeof *elements);
492 xgettimeofday(&start);
494 for (i = 0; i < n_elems; i++) {
495 elements[i].value = i;
496 cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
498 printf("cmap insert: %5d ms\n", elapsed(&start));
501 xgettimeofday(&start);
502 CMAP_FOR_EACH (e, node, &cmap) {
505 printf("cmap iterate: %5d ms\n", elapsed(&start));
507 /* Search and mutation. */
508 xgettimeofday(&start);
510 ovs_mutex_init(&aux.mutex);
511 threads = xmalloc(n_threads * sizeof *threads);
512 for (i = 0; i < n_threads; i++) {
513 threads[i] = ovs_thread_create("search", search_cmap_batched, &aux);
515 for (i = 0; i < n_threads; i++) {
516 xpthread_join(threads[i], NULL);
519 printf("batch search: %5d ms\n", elapsed(&start));
522 xgettimeofday(&start);
523 CMAP_FOR_EACH (e, node, &cmap) {
524 cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
527 printf("cmap destroy: %5d ms\n", elapsed(&start));
532 /* hmap benchmark. */
535 struct hmap_node node;
538 static struct helement *
539 hfind(const struct hmap *hmap, int value)
543 HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
544 if (e->value == value) {
553 struct fat_rwlock fatlock;
557 search_hmap(void *aux_)
559 struct hmap_aux *aux = aux_;
563 for (i = 0; i < n_elems; i++) {
564 if (random_uint32() < mutation_frac) {
567 fat_rwlock_wrlock(&aux->fatlock);
568 e = hfind(aux->hmap, i);
570 hmap_remove(aux->hmap, &e->node);
572 fat_rwlock_unlock(&aux->fatlock);
574 fat_rwlock_rdlock(&aux->fatlock);
575 ignore(hfind(aux->hmap, i));
576 fat_rwlock_unlock(&aux->fatlock);
580 for (i = 0; i < n_elems; i++) {
581 ignore(hfind(aux->hmap, i));
590 struct helement *elements;
592 struct helement *e, *next;
593 struct timeval start;
598 elements = xmalloc(n_elems * sizeof *elements);
600 xgettimeofday(&start);
602 for (i = 0; i < n_elems; i++) {
603 elements[i].value = i;
604 hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
607 printf("hmap insert: %5d ms\n", elapsed(&start));
609 xgettimeofday(&start);
610 HMAP_FOR_EACH (e, node, &hmap) {
613 printf("hmap iterate: %5d ms\n", elapsed(&start));
615 xgettimeofday(&start);
617 fat_rwlock_init(&aux.fatlock);
618 threads = xmalloc(n_threads * sizeof *threads);
619 for (i = 0; i < n_threads; i++) {
620 threads[i] = ovs_thread_create("search", search_hmap, &aux);
622 for (i = 0; i < n_threads; i++) {
623 xpthread_join(threads[i], NULL);
626 printf("hmap search: %5d ms\n", elapsed(&start));
629 xgettimeofday(&start);
630 HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
631 hmap_remove(&hmap, &e->node);
634 printf("hmap destroy: %5d ms\n", elapsed(&start));
639 static const struct ovs_cmdl_command commands[] = {
640 {"check", NULL, 0, 1, run_tests},
641 {"benchmark", NULL, 3, 4, run_benchmarks},
642 {NULL, NULL, 0, 0, NULL},
646 test_cmap_main(int argc, char *argv[])
648 struct ovs_cmdl_context ctx = {
649 .argc = argc - optind,
650 .argv = argv + optind,
653 set_program_name(argv[0]);
654 ovs_cmdl_run_command(&ctx, commands);
657 OVSTEST_REGISTER("test-cmap", test_cmap_main);