2 * Copyright (c) 2008, 2009, 2010, 2013, 2014, 2016, 2017 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"
30 #include "openvswitch/hmap.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 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 all the values are there in batched lookup. */
113 batch_size
= n
% BITMAP_ULONG_BITS
+ 1;
114 for (i
= 0; i
< n
; i
+= batch_size
) {
116 uint32_t hashes
[sizeof map
* CHAR_BIT
];
117 const struct cmap_node
*nodes
[sizeof map
* CHAR_BIT
];
121 j
= MIN(n
- i
, batch_size
); /* Actual batch size. */
122 map
= ~0UL >> (BITMAP_ULONG_BITS
- j
);
124 for (k
= 0; k
< j
; k
++) {
125 hashes
[k
] = hash(values
[i
+ k
]);
127 map
= cmap_find_batch(cmap
, map
, hashes
, nodes
);
129 ULLONG_FOR_EACH_1(k
, map
) {
130 CMAP_NODE_FOR_EACH (e
, node
, nodes
[k
]) {
131 count
+= e
->value
== values
[i
+ k
];
134 assert(count
== j
); /* j elements in a batch. */
137 /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
138 assert(!cmap_first(cmap
) == cmap_is_empty(cmap
));
140 /* Check counters. */
141 assert(cmap_is_empty(cmap
) == !n
);
142 assert(cmap_count(cmap
) == n
);
146 shuffle(int *p
, size_t n
)
148 for (; n
> 1; n
--, p
++) {
149 int *q
= &p
[random_range(n
)];
156 /* Prints the values in 'cmap', plus 'name' as a title. */
157 static void OVS_UNUSED
158 print_cmap(const char *name
, struct cmap
*cmap
)
160 struct cmap_cursor cursor
;
164 CMAP_CURSOR_FOR_EACH (e
, node
, &cursor
, cmap
) {
165 printf(" %d", e
->value
);
170 /* Prints the 'n' values in 'values', plus 'name' as a title. */
171 static void OVS_UNUSED
172 print_ints(const char *name
, const int *values
, size_t n
)
177 for (i
= 0; i
< n
; i
++) {
178 printf(" %d", values
[i
]);
184 identity_hash(int value
)
192 return hash_int(value
, 0x1234abcd);
196 constant_hash(int value OVS_UNUSED
)
201 /* Tests basic cmap insertion and deletion. */
203 test_cmap_insert_replace_delete(hash_func
*hash
)
205 enum { N_ELEMS
= 1000 };
207 struct element elements
[N_ELEMS
];
208 struct element copies
[N_ELEMS
];
210 struct cmap cmap
= CMAP_INITIALIZER
;
213 for (i
= 0; i
< N_ELEMS
; i
++) {
214 elements
[i
].value
= i
;
215 cmap_insert(&cmap
, &elements
[i
].node
, hash(i
));
217 check_cmap(&cmap
, values
, i
+ 1, hash
);
219 shuffle(values
, N_ELEMS
);
220 for (i
= 0; i
< N_ELEMS
; i
++) {
221 copies
[values
[i
]].value
= values
[i
];
222 cmap_replace(&cmap
, &elements
[values
[i
]].node
,
223 &copies
[values
[i
]].node
, hash(values
[i
]));
224 check_cmap(&cmap
, values
, N_ELEMS
, hash
);
226 shuffle(values
, N_ELEMS
);
227 for (i
= 0; i
< N_ELEMS
; i
++) {
228 cmap_remove(&cmap
, &copies
[values
[i
]].node
, hash(values
[i
]));
229 check_cmap(&cmap
, values
+ (i
+ 1), N_ELEMS
- (i
+ 1), hash
);
235 run_test(void (*function
)(hash_func
*))
237 hash_func
*hash_funcs
[] = { identity_hash
, good_hash
, constant_hash
};
240 for (i
= 0; i
< ARRAY_SIZE(hash_funcs
); i
++) {
241 function(hash_funcs
[i
]);
248 run_tests(struct ovs_cmdl_context
*ctx
)
253 n
= ctx
->argc
>= 2 ? atoi(ctx
->argv
[1]) : 100;
254 for (i
= 0; i
< n
; i
++) {
255 run_test(test_cmap_insert_replace_delete
);
260 static int n_elems
; /* Number of elements to insert. */
261 static int n_threads
; /* Number of threads to search and mutate. */
262 static uint32_t mutation_frac
; /* % mutations, as fraction of UINT32_MAX. */
263 static int n_batch
; /* Number of elements in each batch. */
265 #define N_BATCH_MAX BITMAP_ULONG_BITS
267 static void benchmark_cmap(void);
268 static void benchmark_cmap_batched(void);
269 static void benchmark_hmap(void);
272 elapsed(const struct timeval
*start
)
277 return timeval_to_msec(&end
) - timeval_to_msec(start
);
281 run_benchmarks(struct ovs_cmdl_context
*ctx
)
283 n_elems
= strtol(ctx
->argv
[1], NULL
, 10);
284 n_threads
= strtol(ctx
->argv
[2], NULL
, 10);
285 mutation_frac
= strtod(ctx
->argv
[3], NULL
) / 100.0 * UINT32_MAX
;
286 n_batch
= ctx
->argc
> 4 ? strtol(ctx
->argv
[4], NULL
, 10) : 1;
288 if (n_batch
> N_BATCH_MAX
) {
289 n_batch
= N_BATCH_MAX
;
291 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n",
292 n_elems
, n_threads
, (double) mutation_frac
/ UINT32_MAX
* 100.,
296 benchmark_cmap_batched();
304 /* cmap benchmark. */
306 static struct element
*
307 find(const struct cmap
*cmap
, int value
)
311 CMAP_FOR_EACH_WITH_HASH (e
, node
, hash_int(value
, 0), cmap
) {
312 if (e
->value
== value
) {
320 struct ovs_mutex mutex
;
325 search_cmap(void *aux_
)
327 struct cmap_aux
*aux
= aux_
;
331 for (i
= 0; i
< n_elems
; i
++) {
334 if (random_uint32() < mutation_frac
) {
335 ovs_mutex_lock(&aux
->mutex
);
336 e
= find(aux
->cmap
, i
);
338 cmap_remove(aux
->cmap
, &e
->node
, hash_int(e
->value
, 0));
340 ovs_mutex_unlock(&aux
->mutex
);
342 ignore(find(aux
->cmap
, i
));
346 for (i
= 0; i
< n_elems
; i
++) {
347 ignore(find(aux
->cmap
, i
));
356 struct element
*elements
;
359 struct timeval start
;
364 elements
= xmalloc(n_elems
* sizeof *elements
);
367 xgettimeofday(&start
);
369 for (i
= 0; i
< n_elems
; i
++) {
370 elements
[i
].value
= i
;
371 cmap_insert(&cmap
, &elements
[i
].node
, hash_int(i
, 0));
373 printf("cmap insert: %5d ms\n", elapsed(&start
));
376 xgettimeofday(&start
);
377 CMAP_FOR_EACH (e
, node
, &cmap
) {
380 printf("cmap iterate: %5d ms\n", elapsed(&start
));
382 /* Search and mutation. */
383 xgettimeofday(&start
);
385 ovs_mutex_init(&aux
.mutex
);
386 threads
= xmalloc(n_threads
* sizeof *threads
);
387 for (i
= 0; i
< n_threads
; i
++) {
388 threads
[i
] = ovs_thread_create("search", search_cmap
, &aux
);
390 for (i
= 0; i
< n_threads
; i
++) {
391 xpthread_join(threads
[i
], NULL
);
394 printf("cmap search: %5d ms\n", elapsed(&start
));
397 xgettimeofday(&start
);
398 CMAP_FOR_EACH (e
, node
, &cmap
) {
399 cmap_remove(&cmap
, &e
->node
, hash_int(e
->value
, 0));
402 printf("cmap destroy: %5d ms\n", elapsed(&start
));
408 find_batch(const struct cmap
*cmap
, const int value
)
411 const size_t end
= MIN(n_batch
, n_elems
- value
);
412 uint32_t hashes
[N_BATCH_MAX
];
413 const struct cmap_node
*nodes
[N_BATCH_MAX
];
416 for (i
= 0; i
< end
; i
++) {
417 if (random_uint32() < mutation_frac
) {
420 hashes
[i
] = hash_int(value
+ i
, 0);
423 for (i
= 0; i
< end
; i
++) {
424 hashes
[i
] = hash_int(value
+ i
, 0);
430 unsigned long map
= i
? ~0UL >> (BITMAP_ULONG_BITS
- i
) : 0;
431 map
= cmap_find_batch(cmap
, map
, hashes
, nodes
);
433 ULLONG_FOR_EACH_1(i
, map
) {
436 CMAP_NODE_FOR_EACH (e
, node
, nodes
[i
]) {
437 if (OVS_LIKELY(e
->value
== value
+ i
)) {
438 ignore(e
); /* Found result. */
447 search_cmap_batched(void *aux_
)
449 struct cmap_aux
*aux
= aux_
;
455 j
= find_batch(aux
->cmap
, i
);
461 ovs_mutex_lock(&aux
->mutex
);
462 e
= find(aux
->cmap
, i
);
464 cmap_remove(aux
->cmap
, &e
->node
, hash_int(e
->value
, 0));
466 ovs_mutex_unlock(&aux
->mutex
);
474 benchmark_cmap_batched(void)
476 struct element
*elements
;
479 struct timeval start
;
484 elements
= xmalloc(n_elems
* sizeof *elements
);
487 xgettimeofday(&start
);
489 for (i
= 0; i
< n_elems
; i
++) {
490 elements
[i
].value
= i
;
491 cmap_insert(&cmap
, &elements
[i
].node
, hash_int(i
, 0));
493 printf("cmap insert: %5d ms\n", elapsed(&start
));
496 xgettimeofday(&start
);
497 CMAP_FOR_EACH (e
, node
, &cmap
) {
500 printf("cmap iterate: %5d ms\n", elapsed(&start
));
502 /* Search and mutation. */
503 xgettimeofday(&start
);
505 ovs_mutex_init(&aux
.mutex
);
506 threads
= xmalloc(n_threads
* sizeof *threads
);
507 for (i
= 0; i
< n_threads
; i
++) {
508 threads
[i
] = ovs_thread_create("search", search_cmap_batched
, &aux
);
510 for (i
= 0; i
< n_threads
; i
++) {
511 xpthread_join(threads
[i
], NULL
);
514 printf("batch search: %5d ms\n", elapsed(&start
));
517 xgettimeofday(&start
);
518 CMAP_FOR_EACH (e
, node
, &cmap
) {
519 cmap_remove(&cmap
, &e
->node
, hash_int(e
->value
, 0));
522 printf("cmap destroy: %5d ms\n", elapsed(&start
));
527 /* hmap benchmark. */
530 struct hmap_node node
;
533 static struct helement
*
534 hfind(const struct hmap
*hmap
, int value
)
538 HMAP_FOR_EACH_WITH_HASH (e
, node
, hash_int(value
, 0), hmap
) {
539 if (e
->value
== value
) {
548 struct fat_rwlock fatlock
;
552 search_hmap(void *aux_
)
554 struct hmap_aux
*aux
= aux_
;
558 for (i
= 0; i
< n_elems
; i
++) {
559 if (random_uint32() < mutation_frac
) {
562 fat_rwlock_wrlock(&aux
->fatlock
);
563 e
= hfind(aux
->hmap
, i
);
565 hmap_remove(aux
->hmap
, &e
->node
);
567 fat_rwlock_unlock(&aux
->fatlock
);
569 fat_rwlock_rdlock(&aux
->fatlock
);
570 ignore(hfind(aux
->hmap
, i
));
571 fat_rwlock_unlock(&aux
->fatlock
);
575 for (i
= 0; i
< n_elems
; i
++) {
576 ignore(hfind(aux
->hmap
, i
));
585 struct helement
*elements
;
587 struct helement
*e
, *next
;
588 struct timeval start
;
593 elements
= xmalloc(n_elems
* sizeof *elements
);
595 xgettimeofday(&start
);
597 for (i
= 0; i
< n_elems
; i
++) {
598 elements
[i
].value
= i
;
599 hmap_insert(&hmap
, &elements
[i
].node
, hash_int(i
, 0));
602 printf("hmap insert: %5d ms\n", elapsed(&start
));
604 xgettimeofday(&start
);
605 HMAP_FOR_EACH (e
, node
, &hmap
) {
608 printf("hmap iterate: %5d ms\n", elapsed(&start
));
610 xgettimeofday(&start
);
612 fat_rwlock_init(&aux
.fatlock
);
613 threads
= xmalloc(n_threads
* sizeof *threads
);
614 for (i
= 0; i
< n_threads
; i
++) {
615 threads
[i
] = ovs_thread_create("search", search_hmap
, &aux
);
617 for (i
= 0; i
< n_threads
; i
++) {
618 xpthread_join(threads
[i
], NULL
);
621 printf("hmap search: %5d ms\n", elapsed(&start
));
624 xgettimeofday(&start
);
625 HMAP_FOR_EACH_SAFE (e
, next
, node
, &hmap
) {
626 hmap_remove(&hmap
, &e
->node
);
629 printf("hmap destroy: %5d ms\n", elapsed(&start
));
634 static const struct ovs_cmdl_command commands
[] = {
635 {"check", NULL
, 0, 1, run_tests
, OVS_RO
},
636 {"benchmark", NULL
, 3, 4, run_benchmarks
, OVS_RO
},
637 {NULL
, NULL
, 0, 0, NULL
, OVS_RO
},
641 test_cmap_main(int argc
, char *argv
[])
643 struct ovs_cmdl_context ctx
= {
644 .argc
= argc
- optind
,
645 .argv
= argv
+ optind
,
648 set_program_name(argv
[0]);
649 ovs_cmdl_run_command(&ctx
, commands
);
652 OVSTEST_REGISTER("test-cmap", test_cmap_main
);