]>
Commit | Line | Data |
---|---|---|
0e666160 BP |
1 | /* |
2 | * Copyright (c) 2008, 2009, 2010, 2013, 2014 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 | #include "cmap.h" | |
22 | #include <getopt.h> | |
23 | #include <string.h> | |
24 | #include "command-line.h" | |
25 | #include "fat-rwlock.h" | |
26 | #include "hash.h" | |
27 | #include "hmap.h" | |
28 | #include "ovstest.h" | |
29 | #include "ovs-thread.h" | |
30 | #include "random.h" | |
31 | #include "timeval.h" | |
32 | #include "util.h" | |
33 | ||
34 | #undef NDEBUG | |
35 | #include <assert.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 | compare_ints(const void *a_, const void *b_) | |
47 | { | |
48 | const int *a = a_; | |
49 | const int *b = b_; | |
50 | return *a < *b ? -1 : *a > *b; | |
51 | } | |
52 | ||
53 | /* Verifies that 'cmap' contains exactly the 'n' values in 'values'. */ | |
54 | static void | |
55 | check_cmap(struct cmap *cmap, const int values[], size_t n, | |
56 | hash_func *hash) | |
57 | { | |
58 | int *sort_values, *cmap_values; | |
59 | struct cmap_cursor cursor; | |
60 | struct element *e; | |
61 | size_t i; | |
62 | ||
63 | /* Check that all the values are there in iteration. */ | |
64 | sort_values = xmalloc(sizeof *sort_values * n); | |
65 | cmap_values = xmalloc(sizeof *sort_values * n); | |
66 | ||
67 | i = 0; | |
68 | CMAP_FOR_EACH (e, node, &cursor, cmap) { | |
69 | assert(i < n); | |
70 | cmap_values[i++] = e->value; | |
71 | } | |
72 | assert(i == n); | |
73 | ||
74 | memcpy(sort_values, values, sizeof *sort_values * n); | |
75 | qsort(sort_values, n, sizeof *sort_values, compare_ints); | |
76 | qsort(cmap_values, n, sizeof *cmap_values, compare_ints); | |
77 | ||
78 | for (i = 0; i < n; i++) { | |
79 | assert(sort_values[i] == cmap_values[i]); | |
80 | } | |
81 | ||
82 | free(cmap_values); | |
83 | free(sort_values); | |
84 | ||
85 | /* Check that all the values are there in lookup. */ | |
86 | for (i = 0; i < n; i++) { | |
87 | size_t count = 0; | |
88 | ||
89 | CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) { | |
90 | count += e->value == values[i]; | |
91 | } | |
92 | assert(count == 1); | |
93 | } | |
94 | ||
9d933fc7 JR |
95 | /* Check that cmap_first() returns NULL only when cmap_is_empty(). */ |
96 | assert(!cmap_first(cmap) == cmap_is_empty(cmap)); | |
97 | ||
0e666160 BP |
98 | /* Check counters. */ |
99 | assert(cmap_is_empty(cmap) == !n); | |
100 | assert(cmap_count(cmap) == n); | |
101 | } | |
102 | ||
103 | static void | |
104 | shuffle(int *p, size_t n) | |
105 | { | |
106 | for (; n > 1; n--, p++) { | |
107 | int *q = &p[random_range(n)]; | |
108 | int tmp = *p; | |
109 | *p = *q; | |
110 | *q = tmp; | |
111 | } | |
112 | } | |
113 | ||
114 | /* Prints the values in 'cmap', plus 'name' as a title. */ | |
115 | static void OVS_UNUSED | |
116 | print_cmap(const char *name, struct cmap *cmap) | |
117 | { | |
118 | struct cmap_cursor cursor; | |
119 | struct element *e; | |
120 | ||
121 | printf("%s:", name); | |
122 | CMAP_FOR_EACH (e, node, &cursor, cmap) { | |
123 | printf(" %d", e->value); | |
124 | } | |
125 | printf("\n"); | |
126 | } | |
127 | ||
128 | /* Prints the 'n' values in 'values', plus 'name' as a title. */ | |
129 | static void OVS_UNUSED | |
130 | print_ints(const char *name, const int *values, size_t n) | |
131 | { | |
132 | size_t i; | |
133 | ||
134 | printf("%s:", name); | |
135 | for (i = 0; i < n; i++) { | |
136 | printf(" %d", values[i]); | |
137 | } | |
138 | printf("\n"); | |
139 | } | |
140 | ||
141 | static size_t | |
142 | identity_hash(int value) | |
143 | { | |
144 | return value; | |
145 | } | |
146 | ||
147 | static size_t | |
148 | good_hash(int value) | |
149 | { | |
150 | return hash_int(value, 0x1234abcd); | |
151 | } | |
152 | ||
153 | static size_t | |
154 | constant_hash(int value OVS_UNUSED) | |
155 | { | |
156 | return 123; | |
157 | } | |
158 | ||
159 | /* Tests basic cmap insertion and deletion. */ | |
160 | static void | |
9d933fc7 | 161 | test_cmap_insert_replace_delete(hash_func *hash) |
0e666160 BP |
162 | { |
163 | enum { N_ELEMS = 1000 }; | |
164 | ||
165 | struct element elements[N_ELEMS]; | |
9d933fc7 | 166 | struct element copies[N_ELEMS]; |
0e666160 BP |
167 | int values[N_ELEMS]; |
168 | struct cmap cmap; | |
169 | size_t i; | |
170 | ||
171 | cmap_init(&cmap); | |
172 | for (i = 0; i < N_ELEMS; i++) { | |
173 | elements[i].value = i; | |
174 | cmap_insert(&cmap, &elements[i].node, hash(i)); | |
175 | values[i] = i; | |
176 | check_cmap(&cmap, values, i + 1, hash); | |
177 | } | |
178 | shuffle(values, N_ELEMS); | |
179 | for (i = 0; i < N_ELEMS; i++) { | |
9d933fc7 JR |
180 | copies[values[i]].value = values[i]; |
181 | cmap_replace(&cmap, &elements[values[i]].node, | |
182 | &copies[values[i]].node, hash(values[i])); | |
183 | check_cmap(&cmap, values, N_ELEMS, hash); | |
184 | } | |
185 | shuffle(values, N_ELEMS); | |
186 | for (i = 0; i < N_ELEMS; i++) { | |
187 | cmap_remove(&cmap, &copies[values[i]].node, hash(values[i])); | |
0e666160 BP |
188 | check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash); |
189 | } | |
190 | cmap_destroy(&cmap); | |
191 | } | |
192 | ||
193 | static void | |
194 | run_test(void (*function)(hash_func *)) | |
195 | { | |
196 | hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash }; | |
197 | size_t i; | |
198 | ||
199 | for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) { | |
200 | function(hash_funcs[i]); | |
201 | printf("."); | |
202 | fflush(stdout); | |
203 | } | |
204 | } | |
205 | ||
206 | static void | |
207 | run_tests(int argc, char *argv[]) | |
208 | { | |
209 | int n; | |
210 | int i; | |
211 | ||
212 | n = argc >= 2 ? atoi(argv[1]) : 100; | |
213 | for (i = 0; i < n; i++) { | |
9d933fc7 | 214 | run_test(test_cmap_insert_replace_delete); |
0e666160 BP |
215 | } |
216 | printf("\n"); | |
217 | } | |
218 | \f | |
219 | static int n_elems; /* Number of elements to insert. */ | |
220 | static int n_threads; /* Number of threads to search and mutate. */ | |
221 | static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */ | |
222 | ||
223 | static void benchmark_cmap(void); | |
224 | static void benchmark_hmap(void); | |
225 | ||
226 | static int | |
227 | elapsed(const struct timeval *start) | |
228 | { | |
229 | struct timeval end; | |
230 | ||
231 | xgettimeofday(&end); | |
232 | return timeval_to_msec(&end) - timeval_to_msec(start); | |
233 | } | |
234 | ||
235 | static void | |
236 | run_benchmarks(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
237 | { | |
238 | n_elems = strtol(argv[1], NULL, 10); | |
239 | n_threads = strtol(argv[2], NULL, 10); | |
240 | mutation_frac = strtod(argv[3], NULL) / 100.0 * UINT32_MAX; | |
241 | ||
242 | printf("Benchmarking with n=%d, %d threads, %.2f%% mutations:\n", | |
243 | n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.); | |
244 | ||
245 | benchmark_cmap(); | |
246 | putchar('\n'); | |
247 | benchmark_hmap(); | |
248 | } | |
249 | \f | |
250 | /* cmap benchmark. */ | |
251 | ||
252 | static struct element * | |
253 | find(const struct cmap *cmap, int value) | |
254 | { | |
255 | struct element *e; | |
256 | ||
257 | CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) { | |
258 | if (e->value == value) { | |
259 | return e; | |
260 | } | |
261 | } | |
262 | return NULL; | |
263 | } | |
264 | ||
265 | struct cmap_aux { | |
266 | struct ovs_mutex mutex; | |
267 | struct cmap *cmap; | |
268 | }; | |
269 | ||
270 | static void * | |
271 | search_cmap(void *aux_) | |
272 | { | |
273 | struct cmap_aux *aux = aux_; | |
274 | size_t i; | |
275 | ||
276 | for (i = 0; i < n_elems; i++) { | |
277 | struct element *e; | |
278 | ||
279 | if (random_uint32() < mutation_frac) { | |
280 | ovs_mutex_lock(&aux->mutex); | |
281 | e = find(aux->cmap, i); | |
282 | if (e) { | |
283 | cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0)); | |
284 | } | |
285 | ovs_mutex_unlock(&aux->mutex); | |
286 | } else { | |
287 | ignore(find(aux->cmap, i)); | |
288 | } | |
289 | } | |
290 | return NULL; | |
291 | } | |
292 | ||
293 | static void | |
294 | benchmark_cmap(void) | |
295 | { | |
296 | struct element *elements; | |
297 | struct cmap cmap; | |
298 | struct element *e; | |
299 | struct cmap_cursor cursor; | |
300 | struct timeval start; | |
301 | pthread_t *threads; | |
302 | struct cmap_aux aux; | |
303 | size_t i; | |
304 | ||
305 | elements = xmalloc(n_elems * sizeof *elements); | |
306 | ||
307 | /* Insertions. */ | |
308 | xgettimeofday(&start); | |
309 | cmap_init(&cmap); | |
310 | for (i = 0; i < n_elems; i++) { | |
311 | elements[i].value = i; | |
312 | cmap_insert(&cmap, &elements[i].node, hash_int(i, 0)); | |
313 | } | |
314 | printf("cmap insert: %5d ms\n", elapsed(&start)); | |
315 | ||
316 | /* Iteration. */ | |
317 | xgettimeofday(&start); | |
318 | CMAP_FOR_EACH (e, node, &cursor, &cmap) { | |
319 | ignore(e); | |
320 | } | |
321 | printf("cmap iterate: %5d ms\n", elapsed(&start)); | |
322 | ||
323 | /* Search and mutation. */ | |
324 | xgettimeofday(&start); | |
325 | aux.cmap = &cmap; | |
326 | ovs_mutex_init(&aux.mutex); | |
327 | threads = xmalloc(n_threads * sizeof *threads); | |
328 | for (i = 0; i < n_threads; i++) { | |
329 | threads[i] = ovs_thread_create("search", search_cmap, &aux); | |
330 | } | |
331 | for (i = 0; i < n_threads; i++) { | |
332 | xpthread_join(threads[i], NULL); | |
333 | } | |
334 | free(threads); | |
335 | printf("cmap search: %5d ms\n", elapsed(&start)); | |
336 | ||
337 | /* Destruction. */ | |
338 | xgettimeofday(&start); | |
339 | CMAP_FOR_EACH (e, node, &cursor, &cmap) { | |
340 | cmap_remove(&cmap, &e->node, hash_int(e->value, 0)); | |
341 | } | |
342 | cmap_destroy(&cmap); | |
343 | printf("cmap destroy: %5d ms\n", elapsed(&start)); | |
344 | ||
345 | free(elements); | |
346 | } | |
347 | \f | |
348 | /* hmap benchmark. */ | |
349 | struct helement { | |
350 | int value; | |
351 | struct hmap_node node; | |
352 | }; | |
353 | ||
354 | static struct helement * | |
355 | hfind(const struct hmap *hmap, int value) | |
356 | { | |
357 | struct helement *e; | |
358 | ||
359 | HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) { | |
360 | if (e->value == value) { | |
361 | return e; | |
362 | } | |
363 | } | |
364 | return NULL; | |
365 | } | |
366 | ||
367 | struct hmap_aux { | |
368 | struct hmap *hmap; | |
369 | struct fat_rwlock fatlock; | |
370 | }; | |
371 | ||
372 | static void * | |
373 | search_hmap(void *aux_) | |
374 | { | |
375 | struct hmap_aux *aux = aux_; | |
376 | size_t i; | |
377 | ||
378 | for (i = 0; i < n_elems; i++) { | |
379 | if (mutation_frac) { | |
380 | if (random_uint32() < mutation_frac) { | |
381 | struct helement *e; | |
382 | ||
383 | fat_rwlock_wrlock(&aux->fatlock); | |
384 | e = hfind(aux->hmap, i); | |
385 | if (e) { | |
386 | hmap_remove(aux->hmap, &e->node); | |
387 | } | |
388 | fat_rwlock_unlock(&aux->fatlock); | |
389 | } else { | |
390 | fat_rwlock_rdlock(&aux->fatlock); | |
391 | ignore(hfind(aux->hmap, i)); | |
392 | fat_rwlock_unlock(&aux->fatlock); | |
393 | } | |
394 | } else { | |
395 | hfind(aux->hmap, i); | |
396 | } | |
397 | } | |
398 | return NULL; | |
399 | } | |
400 | ||
401 | static void | |
402 | benchmark_hmap(void) | |
403 | { | |
404 | struct helement *elements; | |
405 | struct hmap hmap; | |
406 | struct helement *e, *next; | |
407 | struct timeval start; | |
408 | pthread_t *threads; | |
409 | struct hmap_aux aux; | |
410 | size_t i; | |
411 | ||
412 | elements = xmalloc(n_elems * sizeof *elements); | |
413 | ||
414 | xgettimeofday(&start); | |
415 | hmap_init(&hmap); | |
416 | for (i = 0; i < n_elems; i++) { | |
417 | elements[i].value = i; | |
418 | hmap_insert(&hmap, &elements[i].node, hash_int(i, 0)); | |
419 | } | |
420 | ||
421 | printf("hmap insert: %5d ms\n", elapsed(&start)); | |
422 | ||
423 | xgettimeofday(&start); | |
424 | HMAP_FOR_EACH (e, node, &hmap) { | |
425 | ignore(e); | |
426 | } | |
427 | printf("hmap iterate: %5d ms\n", elapsed(&start)); | |
428 | ||
429 | xgettimeofday(&start); | |
430 | aux.hmap = &hmap; | |
431 | fat_rwlock_init(&aux.fatlock); | |
432 | threads = xmalloc(n_threads * sizeof *threads); | |
433 | for (i = 0; i < n_threads; i++) { | |
434 | threads[i] = ovs_thread_create("search", search_hmap, &aux); | |
435 | } | |
436 | for (i = 0; i < n_threads; i++) { | |
437 | xpthread_join(threads[i], NULL); | |
438 | } | |
439 | free(threads); | |
440 | printf("hmap search: %5d ms\n", elapsed(&start)); | |
441 | ||
442 | /* Destruction. */ | |
443 | xgettimeofday(&start); | |
444 | HMAP_FOR_EACH_SAFE (e, next, node, &hmap) { | |
445 | hmap_remove(&hmap, &e->node); | |
446 | } | |
447 | hmap_destroy(&hmap); | |
448 | printf("hmap destroy: %5d ms\n", elapsed(&start)); | |
449 | ||
450 | free(elements); | |
451 | } | |
452 | \f | |
453 | static const struct command commands[] = { | |
454 | {"check", 0, 1, run_tests}, | |
455 | {"benchmark", 3, 3, run_benchmarks}, | |
456 | {NULL, 0, 0, NULL}, | |
457 | }; | |
458 | ||
459 | static void | |
460 | test_cmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
461 | { | |
462 | set_program_name(argv[0]); | |
463 | run_command(argc - optind, argv + optind, commands); | |
464 | } | |
465 | ||
466 | OVSTEST_REGISTER("test-cmap", test_cmap_main); |