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
27 #include "command-line.h"
28 #include "fat-rwlock.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 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 all the values are there in batched lookup. */
114 batch_size
= n
% BITMAP_ULONG_BITS
+ 1;
115 for (i
= 0; i
< n
; i
+= batch_size
) {
117 uint32_t hashes
[sizeof map
* CHAR_BIT
];
118 const struct cmap_node
*nodes
[sizeof map
* CHAR_BIT
];
122 j
= MIN(n
- i
, batch_size
); /* Actual batch size. */
123 map
= ~0UL >> (BITMAP_ULONG_BITS
- j
);
125 for (k
= 0; k
< j
; k
++) {
126 hashes
[k
] = hash(values
[i
+ k
]);
128 map
= cmap_find_batch(cmap
, map
, hashes
, nodes
);
130 ULONG_FOR_EACH_1(k
, map
) {
133 CMAP_NODE_FOR_EACH (e
, node
, nodes
[k
]) {
134 count
+= e
->value
== values
[i
+ k
];
137 assert(count
== j
); /* j elements in a batch. */
140 /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
141 assert(!cmap_first(cmap
) == cmap_is_empty(cmap
));
143 /* Check counters. */
144 assert(cmap_is_empty(cmap
) == !n
);
145 assert(cmap_count(cmap
) == n
);
149 shuffle(int *p
, size_t n
)
151 for (; n
> 1; n
--, p
++) {
152 int *q
= &p
[random_range(n
)];
159 /* Prints the values in 'cmap', plus 'name' as a title. */
160 static void OVS_UNUSED
161 print_cmap(const char *name
, struct cmap
*cmap
)
163 struct cmap_cursor cursor
;
167 CMAP_CURSOR_FOR_EACH (e
, node
, &cursor
, cmap
) {
168 printf(" %d", e
->value
);
173 /* Prints the 'n' values in 'values', plus 'name' as a title. */
174 static void OVS_UNUSED
175 print_ints(const char *name
, const int *values
, size_t n
)
180 for (i
= 0; i
< n
; i
++) {
181 printf(" %d", values
[i
]);
187 identity_hash(int value
)
195 return hash_int(value
, 0x1234abcd);
199 constant_hash(int value OVS_UNUSED
)
204 /* Tests basic cmap insertion and deletion. */
206 test_cmap_insert_replace_delete(hash_func
*hash
)
208 enum { N_ELEMS
= 1000 };
210 struct element elements
[N_ELEMS
];
211 struct element copies
[N_ELEMS
];
217 for (i
= 0; i
< N_ELEMS
; i
++) {
218 elements
[i
].value
= i
;
219 cmap_insert(&cmap
, &elements
[i
].node
, hash(i
));
221 check_cmap(&cmap
, values
, i
+ 1, hash
);
223 shuffle(values
, N_ELEMS
);
224 for (i
= 0; i
< N_ELEMS
; i
++) {
225 copies
[values
[i
]].value
= values
[i
];
226 cmap_replace(&cmap
, &elements
[values
[i
]].node
,
227 &copies
[values
[i
]].node
, hash(values
[i
]));
228 check_cmap(&cmap
, values
, N_ELEMS
, hash
);
230 shuffle(values
, N_ELEMS
);
231 for (i
= 0; i
< N_ELEMS
; i
++) {
232 cmap_remove(&cmap
, &copies
[values
[i
]].node
, hash(values
[i
]));
233 check_cmap(&cmap
, values
+ (i
+ 1), N_ELEMS
- (i
+ 1), hash
);
239 run_test(void (*function
)(hash_func
*))
241 hash_func
*hash_funcs
[] = { identity_hash
, good_hash
, constant_hash
};
244 for (i
= 0; i
< ARRAY_SIZE(hash_funcs
); i
++) {
245 function(hash_funcs
[i
]);
252 run_tests(int argc
, char *argv
[])
257 n
= argc
>= 2 ? atoi(argv
[1]) : 100;
258 for (i
= 0; i
< n
; i
++) {
259 run_test(test_cmap_insert_replace_delete
);
264 static int n_elems
; /* Number of elements to insert. */
265 static int n_threads
; /* Number of threads to search and mutate. */
266 static uint32_t mutation_frac
; /* % mutations, as fraction of UINT32_MAX. */
267 static int n_batch
; /* Number of elements in each batch. */
269 #define N_BATCH_MAX BITMAP_ULONG_BITS
271 static void benchmark_cmap(void);
272 static void benchmark_cmap_batched(void);
273 static void benchmark_hmap(void);
276 elapsed(const struct timeval
*start
)
281 return timeval_to_msec(&end
) - timeval_to_msec(start
);
285 run_benchmarks(int argc
, char *argv
[] OVS_UNUSED
)
287 n_elems
= strtol(argv
[1], NULL
, 10);
288 n_threads
= strtol(argv
[2], NULL
, 10);
289 mutation_frac
= strtod(argv
[3], NULL
) / 100.0 * UINT32_MAX
;
290 n_batch
= argc
> 4 ? strtol(argv
[4], NULL
, 10) : 1;
292 if (n_batch
> N_BATCH_MAX
) {
293 n_batch
= N_BATCH_MAX
;
295 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n",
296 n_elems
, n_threads
, (double) mutation_frac
/ UINT32_MAX
* 100.,
300 benchmark_cmap_batched();
308 /* cmap benchmark. */
310 static struct element
*
311 find(const struct cmap
*cmap
, int value
)
315 CMAP_FOR_EACH_WITH_HASH (e
, node
, hash_int(value
, 0), cmap
) {
316 if (e
->value
== value
) {
324 struct ovs_mutex mutex
;
329 search_cmap(void *aux_
)
331 struct cmap_aux
*aux
= aux_
;
335 for (i
= 0; i
< n_elems
; i
++) {
338 if (random_uint32() < mutation_frac
) {
339 ovs_mutex_lock(&aux
->mutex
);
340 e
= find(aux
->cmap
, i
);
342 cmap_remove(aux
->cmap
, &e
->node
, hash_int(e
->value
, 0));
344 ovs_mutex_unlock(&aux
->mutex
);
346 ignore(find(aux
->cmap
, i
));
350 for (i
= 0; i
< n_elems
; i
++) {
351 ignore(find(aux
->cmap
, i
));
360 struct element
*elements
;
363 struct timeval start
;
368 elements
= xmalloc(n_elems
* sizeof *elements
);
371 xgettimeofday(&start
);
373 for (i
= 0; i
< n_elems
; i
++) {
374 elements
[i
].value
= i
;
375 cmap_insert(&cmap
, &elements
[i
].node
, hash_int(i
, 0));
377 printf("cmap insert: %5d ms\n", elapsed(&start
));
380 xgettimeofday(&start
);
381 CMAP_FOR_EACH (e
, node
, &cmap
) {
384 printf("cmap iterate: %5d ms\n", elapsed(&start
));
386 /* Search and mutation. */
387 xgettimeofday(&start
);
389 ovs_mutex_init(&aux
.mutex
);
390 threads
= xmalloc(n_threads
* sizeof *threads
);
391 for (i
= 0; i
< n_threads
; i
++) {
392 threads
[i
] = ovs_thread_create("search", search_cmap
, &aux
);
394 for (i
= 0; i
< n_threads
; i
++) {
395 xpthread_join(threads
[i
], NULL
);
398 printf("cmap search: %5d ms\n", elapsed(&start
));
401 xgettimeofday(&start
);
402 CMAP_FOR_EACH (e
, node
, &cmap
) {
403 cmap_remove(&cmap
, &e
->node
, hash_int(e
->value
, 0));
406 printf("cmap destroy: %5d ms\n", elapsed(&start
));
412 find_batch(const struct cmap
*cmap
, const int value
)
415 const size_t end
= MIN(n_batch
, n_elems
- value
);
416 unsigned long map
= ~0;
417 uint32_t hashes
[N_BATCH_MAX
];
418 const struct cmap_node
*nodes
[N_BATCH_MAX
];
421 for (i
= 0; i
< end
; i
++) {
422 if (random_uint32() < mutation_frac
) {
425 hashes
[i
] = hash_int(value
+ i
, 0);
428 for (i
= 0; i
< end
; i
++) {
429 hashes
[i
] = hash_int(value
+ i
, 0);
435 map
>>= BITMAP_ULONG_BITS
- i
; /* Clear excess bits. */
436 map
= cmap_find_batch(cmap
, map
, hashes
, nodes
);
438 ULONG_FOR_EACH_1(i
, map
) {
441 CMAP_NODE_FOR_EACH (e
, node
, nodes
[i
]) {
442 if (OVS_LIKELY(e
->value
== value
+ i
)) {
443 ignore(e
); /* Found result. */
452 search_cmap_batched(void *aux_
)
454 struct cmap_aux
*aux
= aux_
;
460 j
= find_batch(aux
->cmap
, i
);
466 ovs_mutex_lock(&aux
->mutex
);
467 e
= find(aux
->cmap
, i
);
469 cmap_remove(aux
->cmap
, &e
->node
, hash_int(e
->value
, 0));
471 ovs_mutex_unlock(&aux
->mutex
);
479 benchmark_cmap_batched(void)
481 struct element
*elements
;
484 struct timeval start
;
489 elements
= xmalloc(n_elems
* sizeof *elements
);
492 xgettimeofday(&start
);
494 for (i
= 0; i
< n_elems
; i
++) {
495 elements
[i
].value
= i
;
496 cmap_insert(&cmap
, &elements
[i
].node
, hash_int(i
, 0));
498 printf("cmap insert: %5d ms\n", elapsed(&start
));
501 xgettimeofday(&start
);
502 CMAP_FOR_EACH (e
, node
, &cmap
) {
505 printf("cmap iterate: %5d ms\n", elapsed(&start
));
507 /* Search and mutation. */
508 xgettimeofday(&start
);
510 ovs_mutex_init(&aux
.mutex
);
511 threads
= xmalloc(n_threads
* sizeof *threads
);
512 for (i
= 0; i
< n_threads
; i
++) {
513 threads
[i
] = ovs_thread_create("search", search_cmap_batched
, &aux
);
515 for (i
= 0; i
< n_threads
; i
++) {
516 xpthread_join(threads
[i
], NULL
);
519 printf("batch search: %5d ms\n", elapsed(&start
));
522 xgettimeofday(&start
);
523 CMAP_FOR_EACH (e
, node
, &cmap
) {
524 cmap_remove(&cmap
, &e
->node
, hash_int(e
->value
, 0));
527 printf("cmap destroy: %5d ms\n", elapsed(&start
));
532 /* hmap benchmark. */
535 struct hmap_node node
;
538 static struct helement
*
539 hfind(const struct hmap
*hmap
, int value
)
543 HMAP_FOR_EACH_WITH_HASH (e
, node
, hash_int(value
, 0), hmap
) {
544 if (e
->value
== value
) {
553 struct fat_rwlock fatlock
;
557 search_hmap(void *aux_
)
559 struct hmap_aux
*aux
= aux_
;
563 for (i
= 0; i
< n_elems
; i
++) {
564 if (random_uint32() < mutation_frac
) {
567 fat_rwlock_wrlock(&aux
->fatlock
);
568 e
= hfind(aux
->hmap
, i
);
570 hmap_remove(aux
->hmap
, &e
->node
);
572 fat_rwlock_unlock(&aux
->fatlock
);
574 fat_rwlock_rdlock(&aux
->fatlock
);
575 ignore(hfind(aux
->hmap
, i
));
576 fat_rwlock_unlock(&aux
->fatlock
);
580 for (i
= 0; i
< n_elems
; i
++) {
581 ignore(hfind(aux
->hmap
, i
));
590 struct helement
*elements
;
592 struct helement
*e
, *next
;
593 struct timeval start
;
598 elements
= xmalloc(n_elems
* sizeof *elements
);
600 xgettimeofday(&start
);
602 for (i
= 0; i
< n_elems
; i
++) {
603 elements
[i
].value
= i
;
604 hmap_insert(&hmap
, &elements
[i
].node
, hash_int(i
, 0));
607 printf("hmap insert: %5d ms\n", elapsed(&start
));
609 xgettimeofday(&start
);
610 HMAP_FOR_EACH (e
, node
, &hmap
) {
613 printf("hmap iterate: %5d ms\n", elapsed(&start
));
615 xgettimeofday(&start
);
617 fat_rwlock_init(&aux
.fatlock
);
618 threads
= xmalloc(n_threads
* sizeof *threads
);
619 for (i
= 0; i
< n_threads
; i
++) {
620 threads
[i
] = ovs_thread_create("search", search_hmap
, &aux
);
622 for (i
= 0; i
< n_threads
; i
++) {
623 xpthread_join(threads
[i
], NULL
);
626 printf("hmap search: %5d ms\n", elapsed(&start
));
629 xgettimeofday(&start
);
630 HMAP_FOR_EACH_SAFE (e
, next
, node
, &hmap
) {
631 hmap_remove(&hmap
, &e
->node
);
634 printf("hmap destroy: %5d ms\n", elapsed(&start
));
639 static const struct command commands
[] = {
640 {"check", NULL
, 0, 1, run_tests
},
641 {"benchmark", NULL
, 3, 4, run_benchmarks
},
642 {NULL
, NULL
, 0, 0, NULL
},
646 test_cmap_main(int argc OVS_UNUSED
, char *argv
[] OVS_UNUSED
)
648 set_program_name(argv
[0]);
649 run_command(argc
- optind
, argv
+ optind
, commands
);
652 OVSTEST_REGISTER("test-cmap", test_cmap_main
);