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;
59 const struct element *e;
62 /* Check that all the values are there in iteration. */
63 sort_values = xmalloc(sizeof *sort_values * n);
64 cmap_values = xmalloc(sizeof *sort_values * n);
67 CMAP_FOR_EACH (e, node, cmap) {
69 cmap_values[i++] = e->value;
73 memcpy(sort_values, values, sizeof *sort_values * n);
74 qsort(sort_values, n, sizeof *sort_values, compare_ints);
75 qsort(cmap_values, n, sizeof *cmap_values, compare_ints);
77 for (i = 0; i < n; i++) {
78 assert(sort_values[i] == cmap_values[i]);
84 /* Check that all the values are there in lookup. */
85 for (i = 0; i < n; i++) {
88 CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) {
89 count += e->value == values[i];
94 /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
95 assert(!cmap_first(cmap) == cmap_is_empty(cmap));
98 assert(cmap_is_empty(cmap) == !n);
99 assert(cmap_count(cmap) == n);
103 shuffle(int *p, size_t n)
105 for (; n > 1; n--, p++) {
106 int *q = &p[random_range(n)];
113 /* Prints the values in 'cmap', plus 'name' as a title. */
114 static void OVS_UNUSED
115 print_cmap(const char *name, struct cmap *cmap)
117 struct cmap_cursor cursor;
121 CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) {
122 printf(" %d", e->value);
127 /* Prints the 'n' values in 'values', plus 'name' as a title. */
128 static void OVS_UNUSED
129 print_ints(const char *name, const int *values, size_t n)
134 for (i = 0; i < n; i++) {
135 printf(" %d", values[i]);
141 identity_hash(int value)
149 return hash_int(value, 0x1234abcd);
153 constant_hash(int value OVS_UNUSED)
158 /* Tests basic cmap insertion and deletion. */
160 test_cmap_insert_replace_delete(hash_func *hash)
162 enum { N_ELEMS = 1000 };
164 struct element elements[N_ELEMS];
165 struct element copies[N_ELEMS];
171 for (i = 0; i < N_ELEMS; i++) {
172 elements[i].value = i;
173 cmap_insert(&cmap, &elements[i].node, hash(i));
175 check_cmap(&cmap, values, i + 1, hash);
177 shuffle(values, N_ELEMS);
178 for (i = 0; i < N_ELEMS; i++) {
179 copies[values[i]].value = values[i];
180 cmap_replace(&cmap, &elements[values[i]].node,
181 &copies[values[i]].node, hash(values[i]));
182 check_cmap(&cmap, values, N_ELEMS, hash);
184 shuffle(values, N_ELEMS);
185 for (i = 0; i < N_ELEMS; i++) {
186 cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
187 check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
193 run_test(void (*function)(hash_func *))
195 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
198 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
199 function(hash_funcs[i]);
206 run_tests(int argc, char *argv[])
211 n = argc >= 2 ? atoi(argv[1]) : 100;
212 for (i = 0; i < n; i++) {
213 run_test(test_cmap_insert_replace_delete);
218 static int n_elems; /* Number of elements to insert. */
219 static int n_threads; /* Number of threads to search and mutate. */
220 static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */
222 static void benchmark_cmap(void);
223 static void benchmark_hmap(void);
226 elapsed(const struct timeval *start)
231 return timeval_to_msec(&end) - timeval_to_msec(start);
235 run_benchmarks(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
237 n_elems = strtol(argv[1], NULL, 10);
238 n_threads = strtol(argv[2], NULL, 10);
239 mutation_frac = strtod(argv[3], NULL) / 100.0 * UINT32_MAX;
241 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations:\n",
242 n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
249 /* cmap benchmark. */
251 static struct element *
252 find(const struct cmap *cmap, int value)
256 CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
257 if (e->value == value) {
265 struct ovs_mutex mutex;
270 search_cmap(void *aux_)
272 struct cmap_aux *aux = aux_;
275 for (i = 0; i < n_elems; i++) {
278 if (random_uint32() < mutation_frac) {
279 ovs_mutex_lock(&aux->mutex);
280 e = find(aux->cmap, i);
282 cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
284 ovs_mutex_unlock(&aux->mutex);
286 ignore(find(aux->cmap, i));
295 struct element *elements;
298 struct timeval start;
303 elements = xmalloc(n_elems * sizeof *elements);
306 xgettimeofday(&start);
308 for (i = 0; i < n_elems; i++) {
309 elements[i].value = i;
310 cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
312 printf("cmap insert: %5d ms\n", elapsed(&start));
315 xgettimeofday(&start);
316 CMAP_FOR_EACH (e, node, &cmap) {
319 printf("cmap iterate: %5d ms\n", elapsed(&start));
321 /* Search and mutation. */
322 xgettimeofday(&start);
324 ovs_mutex_init(&aux.mutex);
325 threads = xmalloc(n_threads * sizeof *threads);
326 for (i = 0; i < n_threads; i++) {
327 threads[i] = ovs_thread_create("search", search_cmap, &aux);
329 for (i = 0; i < n_threads; i++) {
330 xpthread_join(threads[i], NULL);
333 printf("cmap search: %5d ms\n", elapsed(&start));
336 xgettimeofday(&start);
337 CMAP_FOR_EACH (e, node, &cmap) {
338 cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
341 printf("cmap destroy: %5d ms\n", elapsed(&start));
346 /* hmap benchmark. */
349 struct hmap_node node;
352 static struct helement *
353 hfind(const struct hmap *hmap, int value)
357 HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
358 if (e->value == value) {
367 struct fat_rwlock fatlock;
371 search_hmap(void *aux_)
373 struct hmap_aux *aux = aux_;
376 for (i = 0; i < n_elems; i++) {
378 if (random_uint32() < mutation_frac) {
381 fat_rwlock_wrlock(&aux->fatlock);
382 e = hfind(aux->hmap, i);
384 hmap_remove(aux->hmap, &e->node);
386 fat_rwlock_unlock(&aux->fatlock);
388 fat_rwlock_rdlock(&aux->fatlock);
389 ignore(hfind(aux->hmap, i));
390 fat_rwlock_unlock(&aux->fatlock);
402 struct helement *elements;
404 struct helement *e, *next;
405 struct timeval start;
410 elements = xmalloc(n_elems * sizeof *elements);
412 xgettimeofday(&start);
414 for (i = 0; i < n_elems; i++) {
415 elements[i].value = i;
416 hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
419 printf("hmap insert: %5d ms\n", elapsed(&start));
421 xgettimeofday(&start);
422 HMAP_FOR_EACH (e, node, &hmap) {
425 printf("hmap iterate: %5d ms\n", elapsed(&start));
427 xgettimeofday(&start);
429 fat_rwlock_init(&aux.fatlock);
430 threads = xmalloc(n_threads * sizeof *threads);
431 for (i = 0; i < n_threads; i++) {
432 threads[i] = ovs_thread_create("search", search_hmap, &aux);
434 for (i = 0; i < n_threads; i++) {
435 xpthread_join(threads[i], NULL);
438 printf("hmap search: %5d ms\n", elapsed(&start));
441 xgettimeofday(&start);
442 HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
443 hmap_remove(&hmap, &e->node);
446 printf("hmap destroy: %5d ms\n", elapsed(&start));
451 static const struct command commands[] = {
452 {"check", 0, 1, run_tests},
453 {"benchmark", 3, 3, run_benchmarks},
458 test_cmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
460 set_program_name(argv[0]);
461 run_command(argc - optind, argv + optind, commands);
464 OVSTEST_REGISTER("test-cmap", test_cmap_main);