Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2013, 2014, 2016 Nicira, Inc.
3 : : *
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:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
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.
15 : : */
16 : :
17 : : /* A non-exhaustive test for some of the functions and macros declared in
18 : : * cmap.h. */
19 : :
20 : : #include <config.h>
21 : : #undef NDEBUG
22 : : #include "cmap.h"
23 : : #include <assert.h>
24 : : #include <getopt.h>
25 : : #include <string.h>
26 : : #include "bitmap.h"
27 : : #include "command-line.h"
28 : : #include "fat-rwlock.h"
29 : : #include "hash.h"
30 : : #include "openvswitch/hmap.h"
31 : : #include "ovstest.h"
32 : : #include "ovs-thread.h"
33 : : #include "random.h"
34 : : #include "timeval.h"
35 : : #include "util.h"
36 : :
37 : : /* Sample cmap element. */
38 : : struct element {
39 : : int value;
40 : : struct cmap_node node;
41 : : };
42 : :
43 : : typedef size_t hash_func(int value);
44 : :
45 : : static int
46 : 131218675 : compare_ints(const void *a_, const void *b_)
47 : : {
48 : 131218675 : const int *a = a_;
49 : 131218675 : const int *b = b_;
50 [ + + ]: 131218675 : return *a < *b ? -1 : *a > *b;
51 : : }
52 : :
53 : : /* Verifies that 'cmap' contains exactly the 'n' values in 'values'. */
54 : : static void
55 : 9000 : check_cmap(struct cmap *cmap, const int values[], size_t n,
56 : : hash_func *hash)
57 : : {
58 : : int *sort_values, *cmap_values, *cmap_values2;
59 : : const struct element *e;
60 : : size_t i, batch_size;
61 : :
62 : 9000 : struct cmap_position pos = { 0, 0, 0 };
63 : : struct cmap_node *node;
64 : :
65 : : /* Check that all the values are there in iteration. */
66 : 9000 : sort_values = xmalloc(sizeof *sort_values * n);
67 : 9000 : cmap_values = xmalloc(sizeof *sort_values * n);
68 : 9000 : cmap_values2 = xmalloc(sizeof *sort_values * n);
69 : :
70 : : /* Here we test cursor iteration */
71 : 9000 : i = 0;
72 [ + + ][ + + ]: 6009000 : CMAP_FOR_EACH (e, node, cmap) {
73 [ - + ]: 6000000 : assert(i < n);
74 : 6000000 : cmap_values[i++] = e->value;
75 : : }
76 [ - + ]: 9000 : assert(i == n);
77 : :
78 : : /* Here we test iteration with cmap_next_position() */
79 : 9000 : i = 0;
80 [ + + ]: 6009000 : while ((node = cmap_next_position(cmap, &pos))) {
81 : 6000000 : struct element *e = NULL;
82 : 6000000 : e = OBJECT_CONTAINING(node, e, node);
83 : :
84 [ - + ]: 6000000 : assert(i < n);
85 : 6000000 : cmap_values2[i++] = e->value;
86 : : }
87 [ - + ]: 9000 : assert(i == n);
88 : :
89 : 9000 : memcpy(sort_values, values, sizeof *sort_values * n);
90 : 9000 : qsort(sort_values, n, sizeof *sort_values, compare_ints);
91 : 9000 : qsort(cmap_values, n, sizeof *cmap_values, compare_ints);
92 : 9000 : qsort(cmap_values2, n, sizeof *cmap_values2, compare_ints);
93 : :
94 [ + + ]: 6009000 : for (i = 0; i < n; i++) {
95 [ - + ]: 6000000 : assert(sort_values[i] == cmap_values[i]);
96 [ - + ]: 6000000 : assert(sort_values[i] == cmap_values2[i]);
97 : : }
98 : :
99 : 9000 : free(cmap_values2);
100 : 9000 : free(cmap_values);
101 : 9000 : free(sort_values);
102 : :
103 : : /* Check that all the values are there in lookup. */
104 [ + + ]: 6009000 : for (i = 0; i < n; i++) {
105 : 6000000 : size_t count = 0;
106 : :
107 [ + + ]: 1676667000 : CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) {
108 : 1670667000 : count += e->value == values[i];
109 : : }
110 [ - + ]: 6000000 : assert(count == 1);
111 : : }
112 : :
113 : : /* Check that all the values are there in batched lookup. */
114 : 9000 : batch_size = n % BITMAP_ULONG_BITS + 1;
115 [ + + ]: 308145 : for (i = 0; i < n; i += batch_size) {
116 : : unsigned long map;
117 : : uint32_t hashes[sizeof map * CHAR_BIT];
118 : : const struct cmap_node *nodes[sizeof map * CHAR_BIT];
119 : 299145 : size_t count = 0;
120 : : int k, j;
121 : :
122 : 299145 : j = MIN(n - i, batch_size); /* Actual batch size. */
123 : 299145 : map = ~0UL >> (BITMAP_ULONG_BITS - j);
124 : :
125 [ + + ]: 6299145 : for (k = 0; k < j; k++) {
126 : 6000000 : hashes[k] = hash(values[i + k]);
127 : : }
128 : 299145 : map = cmap_find_batch(cmap, map, hashes, nodes);
129 : :
130 [ + + ]: 6299145 : ULLONG_FOR_EACH_1(k, map) {
131 : : struct element *e;
132 : :
133 [ + + ]: 1676667000 : CMAP_NODE_FOR_EACH (e, node, nodes[k]) {
134 : 1670667000 : count += e->value == values[i + k];
135 : : }
136 : : }
137 [ - + ]: 299145 : assert(count == j); /* j elements in a batch. */
138 : : }
139 : :
140 : : /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
141 [ - + ]: 9000 : assert(!cmap_first(cmap) == cmap_is_empty(cmap));
142 : :
143 : : /* Check counters. */
144 [ - + ]: 9000 : assert(cmap_is_empty(cmap) == !n);
145 [ - + ]: 9000 : assert(cmap_count(cmap) == n);
146 : 9000 : }
147 : :
148 : : static void
149 : 6 : shuffle(int *p, size_t n)
150 : : {
151 [ + + ]: 6000 : for (; n > 1; n--, p++) {
152 : 5994 : int *q = &p[random_range(n)];
153 : 5994 : int tmp = *p;
154 : 5994 : *p = *q;
155 : 5994 : *q = tmp;
156 : : }
157 : 6 : }
158 : :
159 : : /* Prints the values in 'cmap', plus 'name' as a title. */
160 : : static void OVS_UNUSED
161 : 0 : print_cmap(const char *name, struct cmap *cmap)
162 : : {
163 : : struct cmap_cursor cursor;
164 : : struct element *e;
165 : :
166 : 0 : printf("%s:", name);
167 [ # # ][ # # ]: 0 : CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) {
168 : 0 : printf(" %d", e->value);
169 : : }
170 : 0 : printf("\n");
171 : 0 : }
172 : :
173 : : /* Prints the 'n' values in 'values', plus 'name' as a title. */
174 : : static void OVS_UNUSED
175 : 0 : print_ints(const char *name, const int *values, size_t n)
176 : : {
177 : : size_t i;
178 : :
179 : 0 : printf("%s:", name);
180 [ # # ]: 0 : for (i = 0; i < n; i++) {
181 : 0 : printf(" %d", values[i]);
182 : : }
183 : 0 : printf("\n");
184 : 0 : }
185 : :
186 : : static size_t
187 : 4003000 : identity_hash(int value)
188 : : {
189 : 4003000 : return value;
190 : : }
191 : :
192 : : static size_t
193 : 4003000 : good_hash(int value)
194 : : {
195 : 4003000 : return hash_int(value, 0x1234abcd);
196 : : }
197 : :
198 : : static size_t
199 : 4003000 : constant_hash(int value OVS_UNUSED)
200 : : {
201 : 4003000 : return 123;
202 : : }
203 : :
204 : : /* Tests basic cmap insertion and deletion. */
205 : : static void
206 : 3 : test_cmap_insert_replace_delete(hash_func *hash)
207 : : {
208 : : enum { N_ELEMS = 1000 };
209 : :
210 : : struct element elements[N_ELEMS];
211 : : struct element copies[N_ELEMS];
212 : : int values[N_ELEMS];
213 : 3 : struct cmap cmap = CMAP_INITIALIZER;
214 : : size_t i;
215 : :
216 [ + + ]: 3003 : for (i = 0; i < N_ELEMS; i++) {
217 : 3000 : elements[i].value = i;
218 : 3000 : cmap_insert(&cmap, &elements[i].node, hash(i));
219 : 3000 : values[i] = i;
220 : 3000 : check_cmap(&cmap, values, i + 1, hash);
221 : : }
222 : 3 : shuffle(values, N_ELEMS);
223 [ + + ]: 3003 : for (i = 0; i < N_ELEMS; i++) {
224 : 3000 : copies[values[i]].value = values[i];
225 : 3000 : cmap_replace(&cmap, &elements[values[i]].node,
226 : 3000 : &copies[values[i]].node, hash(values[i]));
227 : 3000 : check_cmap(&cmap, values, N_ELEMS, hash);
228 : : }
229 : 3 : shuffle(values, N_ELEMS);
230 [ + + ]: 3003 : for (i = 0; i < N_ELEMS; i++) {
231 : 3000 : cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
232 : 3000 : check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
233 : : }
234 : 3 : cmap_destroy(&cmap);
235 : 3 : }
236 : :
237 : : static void
238 : 1 : run_test(void (*function)(hash_func *))
239 : : {
240 : 1 : hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
241 : : size_t i;
242 : :
243 [ + + ]: 4 : for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
244 : 3 : function(hash_funcs[i]);
245 : 3 : printf(".");
246 : 3 : fflush(stdout);
247 : : }
248 : 1 : }
249 : :
250 : : static void
251 : 1 : run_tests(struct ovs_cmdl_context *ctx)
252 : : {
253 : : int n;
254 : : int i;
255 : :
256 [ + - ]: 1 : n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
257 [ + + ]: 2 : for (i = 0; i < n; i++) {
258 : 1 : run_test(test_cmap_insert_replace_delete);
259 : : }
260 : 1 : printf("\n");
261 : 1 : }
262 : :
263 : : static int n_elems; /* Number of elements to insert. */
264 : : static int n_threads; /* Number of threads to search and mutate. */
265 : : static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */
266 : : static int n_batch; /* Number of elements in each batch. */
267 : :
268 : : #define N_BATCH_MAX BITMAP_ULONG_BITS
269 : :
270 : : static void benchmark_cmap(void);
271 : : static void benchmark_cmap_batched(void);
272 : : static void benchmark_hmap(void);
273 : :
274 : : static int
275 : 0 : elapsed(const struct timeval *start)
276 : : {
277 : : struct timeval end;
278 : :
279 : 0 : xgettimeofday(&end);
280 : 0 : return timeval_to_msec(&end) - timeval_to_msec(start);
281 : : }
282 : :
283 : : static void
284 : 0 : run_benchmarks(struct ovs_cmdl_context *ctx)
285 : : {
286 : 0 : n_elems = strtol(ctx->argv[1], NULL, 10);
287 : 0 : n_threads = strtol(ctx->argv[2], NULL, 10);
288 : 0 : mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX;
289 [ # # ]: 0 : n_batch = ctx->argc > 4 ? strtol(ctx->argv[4], NULL, 10) : 1;
290 : :
291 [ # # ]: 0 : if (n_batch > N_BATCH_MAX) {
292 : 0 : n_batch = N_BATCH_MAX;
293 : : }
294 : 0 : printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n",
295 : 0 : n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.,
296 : : n_batch);
297 : :
298 [ # # ]: 0 : if (n_batch > 0) {
299 : 0 : benchmark_cmap_batched();
300 : : }
301 : 0 : putchar('\n');
302 : 0 : benchmark_cmap();
303 : 0 : putchar('\n');
304 : 0 : benchmark_hmap();
305 : 0 : }
306 : :
307 : : /* cmap benchmark. */
308 : :
309 : : static struct element *
310 : 0 : find(const struct cmap *cmap, int value)
311 : : {
312 : : struct element *e;
313 : :
314 [ # # ]: 0 : CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) {
315 [ # # ]: 0 : if (e->value == value) {
316 : 0 : return e;
317 : : }
318 : : }
319 : 0 : return NULL;
320 : : }
321 : :
322 : : struct cmap_aux {
323 : : struct ovs_mutex mutex;
324 : : struct cmap *cmap;
325 : : };
326 : :
327 : : static void *
328 : 0 : search_cmap(void *aux_)
329 : : {
330 : 0 : struct cmap_aux *aux = aux_;
331 : : size_t i;
332 : :
333 [ # # ]: 0 : if (mutation_frac) {
334 [ # # ]: 0 : for (i = 0; i < n_elems; i++) {
335 : : struct element *e;
336 : :
337 [ # # ]: 0 : if (random_uint32() < mutation_frac) {
338 : 0 : ovs_mutex_lock(&aux->mutex);
339 : 0 : e = find(aux->cmap, i);
340 [ # # ]: 0 : if (e) {
341 : 0 : cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
342 : : }
343 : 0 : ovs_mutex_unlock(&aux->mutex);
344 : : } else {
345 : 0 : ignore(find(aux->cmap, i));
346 : : }
347 : : }
348 : : } else {
349 [ # # ]: 0 : for (i = 0; i < n_elems; i++) {
350 : 0 : ignore(find(aux->cmap, i));
351 : : }
352 : : }
353 : 0 : return NULL;
354 : : }
355 : :
356 : : static void
357 : 0 : benchmark_cmap(void)
358 : : {
359 : : struct element *elements;
360 : : struct cmap cmap;
361 : : struct element *e;
362 : : struct timeval start;
363 : : pthread_t *threads;
364 : : struct cmap_aux aux;
365 : : size_t i;
366 : :
367 : 0 : elements = xmalloc(n_elems * sizeof *elements);
368 : :
369 : : /* Insertions. */
370 : 0 : xgettimeofday(&start);
371 : 0 : cmap_init(&cmap);
372 [ # # ]: 0 : for (i = 0; i < n_elems; i++) {
373 : 0 : elements[i].value = i;
374 : 0 : cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
375 : : }
376 : 0 : printf("cmap insert: %5d ms\n", elapsed(&start));
377 : :
378 : : /* Iteration. */
379 : 0 : xgettimeofday(&start);
380 [ # # ][ # # ]: 0 : CMAP_FOR_EACH (e, node, &cmap) {
381 : 0 : ignore(e);
382 : : }
383 : 0 : printf("cmap iterate: %5d ms\n", elapsed(&start));
384 : :
385 : : /* Search and mutation. */
386 : 0 : xgettimeofday(&start);
387 : 0 : aux.cmap = &cmap;
388 : 0 : ovs_mutex_init(&aux.mutex);
389 : 0 : threads = xmalloc(n_threads * sizeof *threads);
390 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
391 : 0 : threads[i] = ovs_thread_create("search", search_cmap, &aux);
392 : : }
393 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
394 : 0 : xpthread_join(threads[i], NULL);
395 : : }
396 : 0 : free(threads);
397 : 0 : printf("cmap search: %5d ms\n", elapsed(&start));
398 : :
399 : : /* Destruction. */
400 : 0 : xgettimeofday(&start);
401 [ # # ][ # # ]: 0 : CMAP_FOR_EACH (e, node, &cmap) {
402 : 0 : cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
403 : : }
404 : 0 : cmap_destroy(&cmap);
405 : 0 : printf("cmap destroy: %5d ms\n", elapsed(&start));
406 : :
407 : 0 : free(elements);
408 : 0 : }
409 : :
410 : : static size_t
411 : 0 : find_batch(const struct cmap *cmap, const int value)
412 : : {
413 : : size_t i, ret;
414 : 0 : const size_t end = MIN(n_batch, n_elems - value);
415 : 0 : unsigned long map = ~0;
416 : : uint32_t hashes[N_BATCH_MAX];
417 : : const struct cmap_node *nodes[N_BATCH_MAX];
418 : :
419 [ # # ]: 0 : if (mutation_frac) {
420 [ # # ]: 0 : for (i = 0; i < end; i++) {
421 [ # # ]: 0 : if (random_uint32() < mutation_frac) {
422 : 0 : break;
423 : : }
424 : 0 : hashes[i] = hash_int(value + i, 0);
425 : : }
426 : : } else {
427 [ # # ]: 0 : for (i = 0; i < end; i++) {
428 : 0 : hashes[i] = hash_int(value + i, 0);
429 : : }
430 : : }
431 : :
432 : 0 : ret = i;
433 : :
434 : 0 : map >>= BITMAP_ULONG_BITS - i; /* Clear excess bits. */
435 : 0 : map = cmap_find_batch(cmap, map, hashes, nodes);
436 : :
437 [ # # ]: 0 : ULLONG_FOR_EACH_1(i, map) {
438 : : struct element *e;
439 : :
440 [ # # ]: 0 : CMAP_NODE_FOR_EACH (e, node, nodes[i]) {
441 [ # # ]: 0 : if (OVS_LIKELY(e->value == value + i)) {
442 : 0 : ignore(e); /* Found result. */
443 : 0 : break;
444 : : }
445 : : }
446 : : }
447 : 0 : return ret;
448 : : }
449 : :
450 : : static void *
451 : 0 : search_cmap_batched(void *aux_)
452 : : {
453 : 0 : struct cmap_aux *aux = aux_;
454 : 0 : size_t i = 0, j;
455 : :
456 : : for (;;) {
457 : : struct element *e;
458 : :
459 : 0 : j = find_batch(aux->cmap, i);
460 : 0 : i += j;
461 [ # # ]: 0 : if (i >= n_elems) {
462 : 0 : break;
463 : : }
464 [ # # ]: 0 : if (j < n_batch) {
465 : 0 : ovs_mutex_lock(&aux->mutex);
466 : 0 : e = find(aux->cmap, i);
467 [ # # ]: 0 : if (e) {
468 : 0 : cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0));
469 : : }
470 : 0 : ovs_mutex_unlock(&aux->mutex);
471 : : }
472 : 0 : }
473 : :
474 : 0 : return NULL;
475 : : }
476 : :
477 : : static void
478 : 0 : benchmark_cmap_batched(void)
479 : : {
480 : : struct element *elements;
481 : : struct cmap cmap;
482 : : struct element *e;
483 : : struct timeval start;
484 : : pthread_t *threads;
485 : : struct cmap_aux aux;
486 : : size_t i;
487 : :
488 : 0 : elements = xmalloc(n_elems * sizeof *elements);
489 : :
490 : : /* Insertions. */
491 : 0 : xgettimeofday(&start);
492 : 0 : cmap_init(&cmap);
493 [ # # ]: 0 : for (i = 0; i < n_elems; i++) {
494 : 0 : elements[i].value = i;
495 : 0 : cmap_insert(&cmap, &elements[i].node, hash_int(i, 0));
496 : : }
497 : 0 : printf("cmap insert: %5d ms\n", elapsed(&start));
498 : :
499 : : /* Iteration. */
500 : 0 : xgettimeofday(&start);
501 [ # # ][ # # ]: 0 : CMAP_FOR_EACH (e, node, &cmap) {
502 : 0 : ignore(e);
503 : : }
504 : 0 : printf("cmap iterate: %5d ms\n", elapsed(&start));
505 : :
506 : : /* Search and mutation. */
507 : 0 : xgettimeofday(&start);
508 : 0 : aux.cmap = &cmap;
509 : 0 : ovs_mutex_init(&aux.mutex);
510 : 0 : threads = xmalloc(n_threads * sizeof *threads);
511 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
512 : 0 : threads[i] = ovs_thread_create("search", search_cmap_batched, &aux);
513 : : }
514 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
515 : 0 : xpthread_join(threads[i], NULL);
516 : : }
517 : 0 : free(threads);
518 : 0 : printf("batch search: %5d ms\n", elapsed(&start));
519 : :
520 : : /* Destruction. */
521 : 0 : xgettimeofday(&start);
522 [ # # ][ # # ]: 0 : CMAP_FOR_EACH (e, node, &cmap) {
523 : 0 : cmap_remove(&cmap, &e->node, hash_int(e->value, 0));
524 : : }
525 : 0 : cmap_destroy(&cmap);
526 : 0 : printf("cmap destroy: %5d ms\n", elapsed(&start));
527 : :
528 : 0 : free(elements);
529 : 0 : }
530 : :
531 : : /* hmap benchmark. */
532 : : struct helement {
533 : : int value;
534 : : struct hmap_node node;
535 : : };
536 : :
537 : : static struct helement *
538 : 0 : hfind(const struct hmap *hmap, int value)
539 : : {
540 : : struct helement *e;
541 : :
542 [ # # ][ # # ]: 0 : HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) {
543 [ # # ]: 0 : if (e->value == value) {
544 : 0 : return e;
545 : : }
546 : : }
547 : 0 : return NULL;
548 : : }
549 : :
550 : : struct hmap_aux {
551 : : struct hmap *hmap;
552 : : struct fat_rwlock fatlock;
553 : : };
554 : :
555 : : static void *
556 : 0 : search_hmap(void *aux_)
557 : : {
558 : 0 : struct hmap_aux *aux = aux_;
559 : : size_t i;
560 : :
561 [ # # ]: 0 : if (mutation_frac) {
562 [ # # ]: 0 : for (i = 0; i < n_elems; i++) {
563 [ # # ]: 0 : if (random_uint32() < mutation_frac) {
564 : : struct helement *e;
565 : :
566 : 0 : fat_rwlock_wrlock(&aux->fatlock);
567 : 0 : e = hfind(aux->hmap, i);
568 [ # # ]: 0 : if (e) {
569 : 0 : hmap_remove(aux->hmap, &e->node);
570 : : }
571 : 0 : fat_rwlock_unlock(&aux->fatlock);
572 : : } else {
573 : 0 : fat_rwlock_rdlock(&aux->fatlock);
574 : 0 : ignore(hfind(aux->hmap, i));
575 : 0 : fat_rwlock_unlock(&aux->fatlock);
576 : : }
577 : : }
578 : : } else {
579 [ # # ]: 0 : for (i = 0; i < n_elems; i++) {
580 : 0 : ignore(hfind(aux->hmap, i));
581 : : }
582 : : }
583 : 0 : return NULL;
584 : : }
585 : :
586 : : static void
587 : 0 : benchmark_hmap(void)
588 : : {
589 : : struct helement *elements;
590 : : struct hmap hmap;
591 : : struct helement *e, *next;
592 : : struct timeval start;
593 : : pthread_t *threads;
594 : : struct hmap_aux aux;
595 : : size_t i;
596 : :
597 : 0 : elements = xmalloc(n_elems * sizeof *elements);
598 : :
599 : 0 : xgettimeofday(&start);
600 : 0 : hmap_init(&hmap);
601 [ # # ]: 0 : for (i = 0; i < n_elems; i++) {
602 : 0 : elements[i].value = i;
603 : 0 : hmap_insert(&hmap, &elements[i].node, hash_int(i, 0));
604 : : }
605 : :
606 : 0 : printf("hmap insert: %5d ms\n", elapsed(&start));
607 : :
608 : 0 : xgettimeofday(&start);
609 [ # # ][ # # ]: 0 : HMAP_FOR_EACH (e, node, &hmap) {
610 : 0 : ignore(e);
611 : : }
612 : 0 : printf("hmap iterate: %5d ms\n", elapsed(&start));
613 : :
614 : 0 : xgettimeofday(&start);
615 : 0 : aux.hmap = &hmap;
616 : 0 : fat_rwlock_init(&aux.fatlock);
617 : 0 : threads = xmalloc(n_threads * sizeof *threads);
618 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
619 : 0 : threads[i] = ovs_thread_create("search", search_hmap, &aux);
620 : : }
621 [ # # ]: 0 : for (i = 0; i < n_threads; i++) {
622 : 0 : xpthread_join(threads[i], NULL);
623 : : }
624 : 0 : free(threads);
625 : 0 : printf("hmap search: %5d ms\n", elapsed(&start));
626 : :
627 : : /* Destruction. */
628 : 0 : xgettimeofday(&start);
629 [ # # ][ # # ]: 0 : HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
[ # # ]
630 : 0 : hmap_remove(&hmap, &e->node);
631 : : }
632 : 0 : hmap_destroy(&hmap);
633 : 0 : printf("hmap destroy: %5d ms\n", elapsed(&start));
634 : :
635 : 0 : free(elements);
636 : 0 : }
637 : :
638 : : static const struct ovs_cmdl_command commands[] = {
639 : : {"check", NULL, 0, 1, run_tests, OVS_RO},
640 : : {"benchmark", NULL, 3, 4, run_benchmarks, OVS_RO},
641 : : {NULL, NULL, 0, 0, NULL, OVS_RO},
642 : : };
643 : :
644 : : static void
645 : 1 : test_cmap_main(int argc, char *argv[])
646 : : {
647 : 3 : struct ovs_cmdl_context ctx = {
648 : 1 : .argc = argc - optind,
649 : 1 : .argv = argv + optind,
650 : : };
651 : :
652 : 1 : set_program_name(argv[0]);
653 : 1 : ovs_cmdl_run_command(&ctx, commands);
654 : 1 : }
655 : :
656 : 1176 : OVSTEST_REGISTER("test-cmap", test_cmap_main);
|
