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 = 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 cmap_first() returns NULL only when cmap_is_empty(). */
114 assert(!cmap_first(cmap) == cmap_is_empty(cmap));
116 /* Check counters. */
117 assert(cmap_is_empty(cmap) == !n);
118 assert(cmap_count(cmap) == n);
122 shuffle(int *p, size_t n)
124 for (; n > 1; n--, p++) {
125 int *q = &p[random_range(n)];
132 /* Prints the values in 'cmap', plus 'name' as a title. */
133 static void OVS_UNUSED
134 print_cmap(const char *name, struct cmap *cmap)
136 struct cmap_cursor cursor;
140 CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) {
141 printf(" %d", e->value);
146 /* Prints the 'n' values in 'values', plus 'name' as a title. */
147 static void OVS_UNUSED
148 print_ints(const char *name, const int *values, size_t n)
153 for (i = 0; i < n; i++) {
154 printf(" %d", values[i]);
160 identity_hash(int value)
168 return hash_int(value, 0x1234abcd);
172 constant_hash(int value OVS_UNUSED)
177 /* Tests basic cmap insertion and deletion. */
179 test_cmap_insert_replace_delete(hash_func *hash)
181 enum { N_ELEMS = 1000 };
183 struct element elements[N_ELEMS];
184 struct element copies[N_ELEMS];
190 for (i = 0; i < N_ELEMS; i++) {
191 elements[i].value = i;
192 cmap_insert(&cmap, &elements[i].node, hash(i));
194 check_cmap(&cmap, values, i + 1, hash);
196 shuffle(values, N_ELEMS);
197 for (i = 0; i < N_ELEMS; i++) {
198 copies[values[i]].value = values[i];
199 cmap_replace(&cmap, &elements[values[i]].node,
200 &copies[values[i]].node, hash(values[i]));
201 check_cmap(&cmap, values, N_ELEMS, hash);
203 shuffle(values, N_ELEMS);
204 for (i = 0; i < N_ELEMS; i++) {
205 cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
206 check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
212 run_test(void (*function)(hash_func *))
214 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
217 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
218 function(hash_funcs[i]);
225 run_tests(int argc, char *argv[])
230 n = argc >= 2 ? atoi(argv[1]) : 100;
231 for (i = 0; i < n; i++) {
232 run_test(test_cmap_insert_replace_delete);
237 static int n_elems; /* Number of elements to insert. */
238 static int n_threads; /* Number of threads to search and mutate. */
239 static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */
241 static void benchmark_cmap(void);
242 static void benchmark_hmap(void);
245 elapsed(const struct timeval *start)
250 return timeval_to_msec(&end) - timeval_to_msec(start);
254 run_benchmarks(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
256 n_elems = strtol(argv[1], NULL, 10);
257 n_threads = strtol(argv[2], NULL, 10);
258 mutation_frac = strtod(argv[3], NULL) / 100.0 * UINT32_MAX;
260 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations:\n",
261 n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
268 /* cmap benchmark. */
270 static struct element *
271 find(const struct cmap *cmap, int value)
275 CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
276 if (e->value == value) {
284 struct ovs_mutex mutex;
289 search_cmap(void *aux_)
291 struct cmap_aux *aux = aux_;
294 for (i = 0; i < n_elems; i++) {
297 if (random_uint32() < mutation_frac) {
298 ovs_mutex_lock(&aux->mutex);
299 e = find(aux->cmap, i);
301 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
303 ovs_mutex_unlock(&aux->mutex);
305 ignore(find(aux->cmap, i));
314 struct element *elements;
317 struct timeval start;
322 elements = xmalloc(n_elems * sizeof *elements);
325 xgettimeofday(&start);
327 for (i = 0; i < n_elems; i++) {
328 elements[i].value = i;
329 cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
331 printf("cmap insert: %5d ms\n", elapsed(&start));
334 xgettimeofday(&start);
335 CMAP_FOR_EACH (e, node, &cmap) {
338 printf("cmap iterate: %5d ms\n", elapsed(&start));
340 /* Search and mutation. */
341 xgettimeofday(&start);
343 ovs_mutex_init(&aux.mutex);
344 threads = xmalloc(n_threads * sizeof *threads);
345 for (i = 0; i < n_threads; i++) {
346 threads[i] = ovs_thread_create("search", search_cmap, &aux);
348 for (i = 0; i < n_threads; i++) {
349 xpthread_join(threads[i], NULL);
352 printf("cmap search: %5d ms\n", elapsed(&start));
355 xgettimeofday(&start);
356 CMAP_FOR_EACH (e, node, &cmap) {
357 cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
360 printf("cmap destroy: %5d ms\n", elapsed(&start));
365 /* hmap benchmark. */
368 struct hmap_node node;
371 static struct helement *
372 hfind(const struct hmap *hmap, int value)
376 HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
377 if (e->value == value) {
386 struct fat_rwlock fatlock;
390 search_hmap(void *aux_)
392 struct hmap_aux *aux = aux_;
395 for (i = 0; i < n_elems; i++) {
397 if (random_uint32() < mutation_frac) {
400 fat_rwlock_wrlock(&aux->fatlock);
401 e = hfind(aux->hmap, i);
403 hmap_remove(aux->hmap, &e->node);
405 fat_rwlock_unlock(&aux->fatlock);
407 fat_rwlock_rdlock(&aux->fatlock);
408 ignore(hfind(aux->hmap, i));
409 fat_rwlock_unlock(&aux->fatlock);
421 struct helement *elements;
423 struct helement *e, *next;
424 struct timeval start;
429 elements = xmalloc(n_elems * sizeof *elements);
431 xgettimeofday(&start);
433 for (i = 0; i < n_elems; i++) {
434 elements[i].value = i;
435 hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
438 printf("hmap insert: %5d ms\n", elapsed(&start));
440 xgettimeofday(&start);
441 HMAP_FOR_EACH (e, node, &hmap) {
444 printf("hmap iterate: %5d ms\n", elapsed(&start));
446 xgettimeofday(&start);
448 fat_rwlock_init(&aux.fatlock);
449 threads = xmalloc(n_threads * sizeof *threads);
450 for (i = 0; i < n_threads; i++) {
451 threads[i] = ovs_thread_create("search", search_hmap, &aux);
453 for (i = 0; i < n_threads; i++) {
454 xpthread_join(threads[i], NULL);
457 printf("hmap search: %5d ms\n", elapsed(&start));
460 xgettimeofday(&start);
461 HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
462 hmap_remove(&hmap, &e->node);
465 printf("hmap destroy: %5d ms\n", elapsed(&start));
470 static const struct command commands[] = {
471 {"check", 0, 1, run_tests},
472 {"benchmark", 3, 3, run_benchmarks},
477 test_cmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
479 set_program_name(argv[0]);
480 run_command(argc - optind, argv + optind, commands);
483 OVSTEST_REGISTER("test-cmap", test_cmap_main);