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