ovs-rcu: Log a helpful warning when ovsrcu_synchronize() stalls.
[sliver-openvswitch.git] / tests / test-hindex.c
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  * hindex.h. */
19
20 #include <config.h>
21 #include "hindex.h"
22 #include <string.h>
23 #include "hash.h"
24 #include "random.h"
25 #include "util.h"
26 #include "ovstest.h"
27
28 #undef NDEBUG
29 #include <assert.h>
30
31 /* Sample hindex element. */
32 struct element {
33     int value;
34     struct hindex_node node;
35 };
36
37 typedef size_t hash_func(int value);
38
39 static int
40 compare_ints(const void *a_, const void *b_)
41 {
42     const int *a = a_;
43     const int *b = b_;
44     return *a < *b ? -1 : *a > *b;
45 }
46
47 /* Verifies that 'hindex' contains exactly the 'n' values in 'values'. */
48 static void
49 check_hindex(struct hindex *hindex, const int values[], size_t n,
50            hash_func *hash)
51 {
52     int *sort_values, *hindex_values;
53     struct element *e;
54     size_t i;
55
56     /* Check that all the values are there in iteration. */
57     sort_values = xmalloc(sizeof *sort_values * n);
58     hindex_values = xmalloc(sizeof *sort_values * n);
59
60     i = 0;
61     HINDEX_FOR_EACH (e, node, hindex) {
62         assert(i < n);
63         hindex_values[i++] = e->value;
64     }
65     assert(i == n);
66
67     memcpy(sort_values, values, sizeof *sort_values * n);
68     qsort(sort_values, n, sizeof *sort_values, compare_ints);
69     qsort(hindex_values, n, sizeof *hindex_values, compare_ints);
70
71     for (i = 0; i < n; i++) {
72         assert(sort_values[i] == hindex_values[i]);
73     }
74
75     free(hindex_values);
76     free(sort_values);
77
78     /* Check that all the values are there in lookup. */
79     for (i = 0; i < n; i++) {
80         size_t count = 0;
81
82         HINDEX_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hindex) {
83             count += e->value == values[i];
84         }
85         assert(count == 1);
86     }
87
88     /* Check counters. */
89     assert(hindex_is_empty(hindex) == !n);
90     assert(hindex->n_unique <= n);
91 }
92
93 /* Puts the 'n' values in 'values' into 'elements', and then puts those
94  * elements into 'hindex'. */
95 static void
96 make_hindex(struct hindex *hindex, struct element elements[],
97           int values[], size_t n, hash_func *hash)
98 {
99     size_t i;
100
101     hindex_init(hindex);
102     for (i = 0; i < n; i++) {
103         elements[i].value = i;
104         hindex_insert(hindex, &elements[i].node, hash(elements[i].value));
105         values[i] = i;
106     }
107 }
108
109 static void
110 shuffle(int *p, size_t n)
111 {
112     for (; n > 1; n--, p++) {
113         int *q = &p[random_range(n)];
114         int tmp = *p;
115         *p = *q;
116         *q = tmp;
117     }
118 }
119
120 /* Prints the 'n' values in 'values', plus 'name' as a title. */
121 static void OVS_UNUSED
122 print_ints(const char *name, const int *values, size_t n)
123 {
124     size_t i;
125
126     printf("%s:", name);
127     for (i = 0; i < n; i++) {
128         printf(" %d", values[i]);
129     }
130     printf("\n");
131 }
132
133 /* Prints the values in 'hindex', plus 'name' as a title. */
134 static void OVS_UNUSED
135 print_hindex(const char *name, struct hindex *hindex)
136 {
137     struct element *e;
138
139     printf("%s:", name);
140     HINDEX_FOR_EACH (e, node, hindex) {
141         printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hindex->mask);
142     }
143     printf("\n");
144 }
145
146 static size_t
147 unique_hash(int value)
148 {
149     return value;
150 }
151
152 static size_t
153 good_hash(int value)
154 {
155     return hash_int(value, 0x1234abcd);
156 }
157
158 static size_t
159 constant_hash(int value OVS_UNUSED)
160 {
161     return 123;
162 }
163
164 static size_t
165 mod4_hash(int value)
166 {
167     return value % 4;
168 }
169
170 static size_t
171 mod3_hash(int value)
172 {
173     return value % 3;
174 }
175
176 static size_t
177 mod2_hash(int value)
178 {
179     return value % 2;
180 }
181
182 static size_t
183 multipart_hash(int value)
184 {
185     return (mod4_hash(value) << 16) | (constant_hash(value) & 0xFFFF);
186 }
187
188 /* Tests basic hindex insertion and deletion. */
189 static void
190 test_hindex_insert_delete(hash_func *hash)
191 {
192     enum { N_ELEMS = 100 };
193
194     struct element elements[N_ELEMS];
195     int values[N_ELEMS];
196     struct hindex hindex;
197     size_t i;
198
199     hindex_init(&hindex);
200     for (i = 0; i < N_ELEMS; i++) {
201         elements[i].value = i;
202         hindex_insert(&hindex, &elements[i].node, hash(i));
203         values[i] = i;
204         check_hindex(&hindex, values, i + 1, hash);
205     }
206     shuffle(values, N_ELEMS);
207     for (i = 0; i < N_ELEMS; i++) {
208         hindex_remove(&hindex, &elements[values[i]].node);
209         check_hindex(&hindex, values + (i + 1), N_ELEMS - (i + 1), hash);
210     }
211     hindex_destroy(&hindex);
212 }
213
214 /* Tests basic hindex_reserve() and hindex_shrink(). */
215 static void
216 test_hindex_reserve_shrink(hash_func *hash)
217 {
218     enum { N_ELEMS = 32 };
219
220     size_t i;
221
222     for (i = 0; i < N_ELEMS; i++) {
223         struct element elements[N_ELEMS];
224         int values[N_ELEMS];
225         struct hindex hindex;
226         size_t j;
227
228         hindex_init(&hindex);
229         hindex_reserve(&hindex, i);
230         for (j = 0; j < N_ELEMS; j++) {
231             elements[j].value = j;
232             hindex_insert(&hindex, &elements[j].node, hash(j));
233             values[j] = j;
234             check_hindex(&hindex, values, j + 1, hash);
235         }
236         shuffle(values, N_ELEMS);
237         for (j = 0; j < N_ELEMS; j++) {
238             hindex_remove(&hindex, &elements[values[j]].node);
239             hindex_shrink(&hindex);
240             check_hindex(&hindex, values + (j + 1), N_ELEMS - (j + 1), hash);
241         }
242         hindex_destroy(&hindex);
243     }
244 }
245
246 /* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
247  * element of a hindex.  */
248 static void
249 test_hindex_for_each_safe(hash_func *hash)
250 {
251     enum { MAX_ELEMS = 10 };
252     size_t n;
253     unsigned long int pattern;
254
255     for (n = 0; n <= MAX_ELEMS; n++) {
256         for (pattern = 0; pattern < 1ul << n; pattern++) {
257             struct element elements[MAX_ELEMS];
258             int values[MAX_ELEMS];
259             struct hindex hindex;
260             struct element *e, *next;
261             size_t n_remaining;
262             int i;
263
264             make_hindex(&hindex, elements, values, n, hash);
265
266             i = 0;
267             n_remaining = n;
268             HINDEX_FOR_EACH_SAFE (e, next, node, &hindex) {
269                 assert(i < n);
270                 if (pattern & (1ul << e->value)) {
271                     size_t j;
272                     hindex_remove(&hindex, &e->node);
273                     for (j = 0; ; j++) {
274                         assert(j < n_remaining);
275                         if (values[j] == e->value) {
276                             values[j] = values[--n_remaining];
277                             break;
278                         }
279                     }
280                 }
281                 check_hindex(&hindex, values, n_remaining, hash);
282                 i++;
283             }
284             assert(i == n);
285
286             for (i = 0; i < n; i++) {
287                 if (pattern & (1ul << i)) {
288                     n_remaining++;
289                 }
290             }
291             assert(n == n_remaining);
292
293             hindex_destroy(&hindex);
294         }
295     }
296 }
297
298 static void
299 run_test(void (*function)(hash_func *))
300 {
301     hash_func *hash_funcs[] = {
302         unique_hash,
303         good_hash,
304         constant_hash,
305         mod4_hash,
306         mod3_hash,
307         mod2_hash,
308         multipart_hash,
309     };
310     size_t i;
311
312     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
313         function(hash_funcs[i]);
314         printf(".");
315         fflush(stdout);
316     }
317 }
318
319 static void
320 test_hindex_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
321 {
322     run_test(test_hindex_insert_delete);
323     run_test(test_hindex_for_each_safe);
324     run_test(test_hindex_reserve_shrink);
325     printf("\n");
326 }
327
328 OVSTEST_REGISTER("test-hindex", test_hindex_main);