]> git.proxmox.com Git - ovs.git/blame - tests/test-ccmap.c
tests: Fix sparse error on test-ovn.c
[ovs.git] / tests / test-ccmap.c
CommitLineData
1c4dd424
JR
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 * ccmap.h. */
19
20#include <config.h>
21#undef NDEBUG
22#include "ccmap.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"
ee89ea7b 30#include "openvswitch/hmap.h"
1c4dd424
JR
31#include "ovstest.h"
32#include "ovs-thread.h"
33#include "random.h"
34#include "timeval.h"
35#include "util.h"
36
37typedef size_t hash_func(int value);
38
39static int
40compare_uint32s(const void *a_, const void *b_)
41{
42 const uint32_t *a = a_;
43 const uint32_t *b = b_;
44 return *a < *b ? -1 : *a > *b;
45}
46
47/* Verifies that 'ccmap' contains exactly the 'n' values in 'values'. */
48static void
49check_ccmap(struct ccmap *ccmap, const int values[], size_t n, hash_func *hash)
50{
51 uint32_t *hashes = xmalloc(sizeof *hashes * n);
52 int i;
53
54 for (i = 0; i < n; i++) {
55 hashes[i] = hash(values[i]);
56 }
57 qsort(hashes, n, sizeof *hashes, compare_uint32s);
58
59 /* Check that all the values are there in lookup. */
60 for (i = 0; i < n; i++) {
71f21279
BP
61 uint32_t h = hashes[i];
62 size_t count = ccmap_find(ccmap, h);
1c4dd424
JR
63
64 assert(count); /* Must have at least one. */
65 assert(i + count <= n); /* May not have too many. */
66
67 /* Skip colliding hash values and assert they were in the count. */
68 while (--count) {
69 i++;
71f21279 70 assert(hashes[i] == h);
1c4dd424
JR
71 }
72 /* Make sure next hash is different. */
73 if (i + 1 < n) {
71f21279 74 assert(hashes[i + 1] != h);
1c4dd424
JR
75 }
76 }
77
78 /* Check counters. */
79 assert(ccmap_is_empty(ccmap) == !n);
80 assert(ccmap_count(ccmap) == n);
81
82 free(hashes);
83}
84
85static void
86shuffle(int *p, size_t n)
87{
88 for (; n > 1; n--, p++) {
89 int *q = &p[random_range(n)];
90 int tmp = *p;
91
92 *p = *q;
93 *q = tmp;
94 }
95}
96
97static size_t
98identity_hash(int value)
99{
100 return value;
101}
102
103static size_t
104good_hash(int value)
105{
106 return hash_int(value, 0x1234abcd);
107}
108
109static size_t
110constant_hash(int value OVS_UNUSED)
111{
112 return 123;
113}
114
115/* Tests basic ccmap increment and decrement. */
116static void
117test_ccmap_inc_dec(hash_func *hash)
118{
119 enum { N_ELEMS = 1000 };
120
121 int values[N_ELEMS];
122 struct ccmap ccmap;
123 size_t i;
124
125 ccmap_init(&ccmap);
126 for (i = 0; i < N_ELEMS; i++) {
127 ccmap_inc(&ccmap, hash(i));
128 values[i] = i;
129 check_ccmap(&ccmap, values, i + 1, hash);
130 }
131 shuffle(values, N_ELEMS);
132 for (i = 0; i < N_ELEMS; i++) {
133 ccmap_dec(&ccmap, hash(values[i]));
134 check_ccmap(&ccmap, values + (i + 1), N_ELEMS - (i + 1), hash);
135 }
136 ccmap_destroy(&ccmap);
137}
138
139static void
140run_test(void (*function)(hash_func *))
141{
142 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
143
144 for (size_t i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
145 function(hash_funcs[i]);
146 printf(".");
147 fflush(stdout);
148 }
149}
150
151static void
152run_tests(struct ovs_cmdl_context *ctx)
153{
154 int n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
155 for (int i = 0; i < n; i++) {
156 run_test(test_ccmap_inc_dec);
157 }
158 printf("\n");
159}
160\f
161static int n_elems; /* Number of elements to insert. */
162static int n_threads; /* Number of threads to search and mutate. */
163static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */
164
165
166static void benchmark_ccmap(void);
167
168static int
169elapsed(const struct timeval *start)
170{
171 struct timeval end;
172
173 xgettimeofday(&end);
174 return timeval_to_msec(&end) - timeval_to_msec(start);
175}
176
177static void
178run_benchmarks(struct ovs_cmdl_context *ctx)
179{
180 n_elems = strtol(ctx->argv[1], NULL, 10);
181 n_threads = strtol(ctx->argv[2], NULL, 10);
182 mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX;
183
184 printf("Benchmarking with n=%d, %d threads, %.2f%% mutations\n",
185 n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100.);
186
187 benchmark_ccmap();
188}
189\f
190/* ccmap benchmark. */
191
192struct ccmap_aux {
193 struct ovs_mutex mutex;
194 struct ccmap *ccmap;
195};
196
197static void *
198search_ccmap(void *aux_)
199{
200 struct ccmap_aux *aux = aux_;
201 size_t i;
202
203 if (mutation_frac) {
204 for (i = 0; i < n_elems; i++) {
205 uint32_t hash = hash_int(i, 0);
206
207 if (random_uint32() < mutation_frac) {
208 ovs_mutex_lock(&aux->mutex);
209 uint32_t count = ccmap_find(aux->ccmap, hash);
210 if (count) {
211 ccmap_dec(aux->ccmap, hash);
212 }
213 ovs_mutex_unlock(&aux->mutex);
214 } else {
215 ignore(ccmap_find(aux->ccmap, hash));
216 }
217 }
218 } else {
219 for (i = 0; i < n_elems; i++) {
220 ignore(ccmap_find(aux->ccmap, hash_int(i, 0)));
221 }
222 }
223 return NULL;
224}
225
226static void
227benchmark_ccmap(void)
228{
229 struct ccmap ccmap;
230 struct timeval start;
231 pthread_t *threads;
232 struct ccmap_aux aux;
233 size_t i;
234
235 /* Insertions. */
236 xgettimeofday(&start);
237 ccmap_init(&ccmap);
238 for (i = 0; i < n_elems; i++) {
239 ccmap_inc(&ccmap, hash_int(i, 0));
240 }
241 printf("ccmap insert: %5d ms\n", elapsed(&start));
242
243 /* Search and mutation. */
244 xgettimeofday(&start);
245 aux.ccmap = &ccmap;
246 ovs_mutex_init(&aux.mutex);
247 threads = xmalloc(n_threads * sizeof *threads);
248 for (i = 0; i < n_threads; i++) {
249 threads[i] = ovs_thread_create("search", search_ccmap, &aux);
250 }
251 for (i = 0; i < n_threads; i++) {
252 xpthread_join(threads[i], NULL);
253 }
254 free(threads);
255 printf("ccmap search: %5d ms\n", elapsed(&start));
256
257 /* Destruction. */
258 xgettimeofday(&start);
259 for (i = 0; i < n_elems; i++) {
260 uint32_t hash = hash_int(i, 0);
261
262 if (ccmap_find(&ccmap, hash)) {
263 /* Also remove any colliding hashes. */
264 while (ccmap_dec(&ccmap, hash)) {
265 ;
266 }
267 }
268 }
269 ccmap_destroy(&ccmap);
270 printf("ccmap destroy: %5d ms\n", elapsed(&start));
271}
272
273\f
274static const struct ovs_cmdl_command commands[] = {
1f4a7252
RM
275 {"check", NULL, 0, 1, run_tests, OVS_RO},
276 {"benchmark", NULL, 3, 3, run_benchmarks, OVS_RO},
277 {NULL, NULL, 0, 0, NULL, OVS_RO},
1c4dd424
JR
278};
279
280static void
281test_ccmap_main(int argc, char *argv[])
282{
283 struct ovs_cmdl_context ctx = {
284 .argc = argc - optind,
285 .argv = argv + optind,
286 };
287
288 set_program_name(argv[0]);
289 ovs_cmdl_run_command(&ctx, commands);
290}
291
292OVSTEST_REGISTER("test-ccmap", test_ccmap_main);