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
24 #include "command-line.h"
25 #include "fat-rwlock.h"
29 #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 = OBJECT_CONTAINING(node, e, node);
84 cmap_values2[i++] = e->value;
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);
93 for (i = 0; i < n; i++) {
94 assert(sort_values[i] == cmap_values[i]);
95 assert(sort_values[i] == cmap_values2[i]);
102 /* Check that all the values are there in lookup. */
103 for (i = 0; i < n; i++) {
106 CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) {
107 count += e->value == values[i];
112 /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
113 assert(!cmap_first(cmap) == cmap_is_empty(cmap));
115 /* Check counters. */
116 assert(cmap_is_empty(cmap) == !n);
117 assert(cmap_count(cmap) == n);
121 shuffle(int *p, size_t n)
123 for (; n > 1; n--, p++) {
124 int *q = &p[random_range(n)];
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)
135 struct cmap_cursor cursor;
139 CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) {
140 printf(" %d", e->value);
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)
152 for (i = 0; i < n; i++) {
153 printf(" %d", values[i]);
159 identity_hash(int value)
167 return hash_int(value, 0x1234abcd);
171 constant_hash(int value OVS_UNUSED)
176 /* Tests basic cmap insertion and deletion. */
178 test_cmap_insert_replace_delete(hash_func *hash)
180 enum { N_ELEMS = 1000 };
182 struct element elements[N_ELEMS];
183 struct element copies[N_ELEMS];
189 for (i = 0; i < N_ELEMS; i++) {
190 elements[i].value = i;
191 cmap_insert(&cmap, &elements[i].node, hash(i));
193 check_cmap(&cmap, values, i + 1, hash);
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);
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);
211 run_test(void (*function)(hash_func *))
213 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
216 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
217 function(hash_funcs[i]);
224 run_tests(int argc, char *argv[])
229 n = argc >= 2 ? atoi(argv[1]) : 100;
230 for (i = 0; i < n; i++) {
231 run_test(test_cmap_insert_replace_delete);
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. */
240 static void benchmark_cmap(void);
241 static void benchmark_hmap(void);
244 elapsed(const struct timeval *start)
249 return timeval_to_msec(&end) - timeval_to_msec(start);
253 run_benchmarks(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
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;
259 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations:\n",
260 n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
267 /* cmap benchmark. */
269 static struct element *
270 find(const struct cmap *cmap, int value)
274 CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
275 if (e->value == value) {
283 struct ovs_mutex mutex;
288 search_cmap(void *aux_)
290 struct cmap_aux *aux = aux_;
293 for (i = 0; i < n_elems; i++) {
296 if (random_uint32() < mutation_frac) {
297 ovs_mutex_lock(&aux->mutex);
298 e = find(aux->cmap, i);
300 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
302 ovs_mutex_unlock(&aux->mutex);
304 ignore(find(aux->cmap, i));
313 struct element *elements;
316 struct timeval start;
321 elements = xmalloc(n_elems * sizeof *elements);
324 xgettimeofday(&start);
326 for (i = 0; i < n_elems; i++) {
327 elements[i].value = i;
328 cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
330 printf("cmap insert: %5d ms\n", elapsed(&start));
333 xgettimeofday(&start);
334 CMAP_FOR_EACH (e, node, &cmap) {
337 printf("cmap iterate: %5d ms\n", elapsed(&start));
339 /* Search and mutation. */
340 xgettimeofday(&start);
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);
347 for (i = 0; i < n_threads; i++) {
348 xpthread_join(threads[i], NULL);
351 printf("cmap search: %5d ms\n", elapsed(&start));
354 xgettimeofday(&start);
355 CMAP_FOR_EACH (e, node, &cmap) {
356 cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
359 printf("cmap destroy: %5d ms\n", elapsed(&start));
364 /* hmap benchmark. */
367 struct hmap_node node;
370 static struct helement *
371 hfind(const struct hmap *hmap, int value)
375 HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
376 if (e->value == value) {
385 struct fat_rwlock fatlock;
389 search_hmap(void *aux_)
391 struct hmap_aux *aux = aux_;
394 for (i = 0; i < n_elems; i++) {
396 if (random_uint32() < mutation_frac) {
399 fat_rwlock_wrlock(&aux->fatlock);
400 e = hfind(aux->hmap, i);
402 hmap_remove(aux->hmap, &e->node);
404 fat_rwlock_unlock(&aux->fatlock);
406 fat_rwlock_rdlock(&aux->fatlock);
407 ignore(hfind(aux->hmap, i));
408 fat_rwlock_unlock(&aux->fatlock);
420 struct helement *elements;
422 struct helement *e, *next;
423 struct timeval start;
428 elements = xmalloc(n_elems * sizeof *elements);
430 xgettimeofday(&start);
432 for (i = 0; i < n_elems; i++) {
433 elements[i].value = i;
434 hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
437 printf("hmap insert: %5d ms\n", elapsed(&start));
439 xgettimeofday(&start);
440 HMAP_FOR_EACH (e, node, &hmap) {
443 printf("hmap iterate: %5d ms\n", elapsed(&start));
445 xgettimeofday(&start);
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);
452 for (i = 0; i < n_threads; i++) {
453 xpthread_join(threads[i], NULL);
456 printf("hmap search: %5d ms\n", elapsed(&start));
459 xgettimeofday(&start);
460 HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
461 hmap_remove(&hmap, &e->node);
464 printf("hmap destroy: %5d ms\n", elapsed(&start));
469 static const struct command commands[] = {
470 {"check", 0, 1, run_tests},
471 {"benchmark", 3, 3, run_benchmarks},
476 test_cmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
478 set_program_name(argv[0]);
479 run_command(argc - optind, argv + optind, commands);
482 OVSTEST_REGISTER("test-cmap", test_cmap_main);