Line data Source code
1 : /*
2 : * Test srcdest table for correctness.
3 : *
4 : * Copyright (C) 2014 by Christian Franke, Open Source Routing.
5 : *
6 : * This file is part of Quagga
7 : *
8 : * Quagga is free software; you can redistribute it and/or modify it
9 : * under the terms of the GNU General Public License as published by the
10 : * Free Software Foundation; either version 2, or (at your option) any
11 : * later version.
12 : *
13 : * Quagga is distributed in the hope that it will be useful, but
14 : * WITHOUT ANY WARRANTY; without even the implied warranty of
15 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 : * General Public License for more details.
17 : *
18 : * You should have received a copy of the GNU General Public License
19 : * along with Quagga; see the file COPYING. If not, write to the Free
20 : * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
21 : * 02111-1307, USA.
22 : */
23 :
24 : #include <zebra.h>
25 :
26 : #include "hash.h"
27 : #include "memory.h"
28 : #include "prefix.h"
29 : #include "prng.h"
30 : #include "srcdest_table.h"
31 : #include "table.h"
32 :
33 : struct thread_master *master;
34 :
35 : /* This structure is copied from lib/srcdest_table.c to which it is
36 : * private as far as other parts of Quagga are concerned.
37 : */
38 : struct srcdest_rnode
39 : {
40 : /* must be first in structure for casting to/from route_node */
41 : ROUTE_NODE_FIELDS;
42 :
43 : struct route_table *src_table;
44 : };
45 :
46 : struct test_state
47 : {
48 : struct route_table *table;
49 : struct hash *log;
50 : };
51 :
52 : static char *
53 0 : format_srcdest(const struct prefix_ipv6 *dst_p,
54 : const struct prefix_ipv6 *src_p)
55 : {
56 : char dst_str[BUFSIZ];
57 : char src_str[BUFSIZ];
58 : char *rv;
59 : int ec;
60 :
61 0 : prefix2str((const struct prefix*)dst_p, dst_str, sizeof(dst_str));
62 0 : if (src_p && src_p->prefixlen)
63 0 : prefix2str((const struct prefix*)src_p, src_str, sizeof(src_str));
64 : else
65 0 : src_str[0] = '\0';
66 :
67 0 : ec = asprintf(&rv, "%s%s%s", dst_str,
68 0 : (src_str[0] != '\0') ? " from " : "",
69 : src_str);
70 :
71 0 : assert(ec > 0);
72 0 : return rv;
73 : }
74 :
75 146785 : static unsigned int log_key(void *data)
76 : {
77 146785 : struct prefix *hash_entry = data;
78 146785 : struct prefix_ipv6 *dst_p = (struct prefix_ipv6*) &hash_entry[0];
79 146785 : struct prefix_ipv6 *src_p = (struct prefix_ipv6*) &hash_entry[1];
80 146785 : unsigned int hash = 0;
81 : unsigned int i;
82 :
83 146785 : hash = (hash * 33) ^ (unsigned int)dst_p->prefixlen;
84 733925 : for (i = 0; i < 4; i++)
85 587140 : hash = (hash * 33) ^ (unsigned int)dst_p->prefix.s6_addr32[i];
86 :
87 146785 : hash = (hash * 33) ^ (unsigned int)src_p->prefixlen;
88 146785 : if (src_p->prefixlen)
89 493460 : for (i = 0; i < 4; i++)
90 394768 : hash = (hash * 33) ^ (unsigned int)src_p->prefix.s6_addr32[i];
91 :
92 146785 : return hash;
93 : }
94 :
95 : static int
96 145504 : log_cmp(const void *a, const void *b)
97 : {
98 145504 : if (a == NULL && b != NULL)
99 0 : return 0;
100 145504 : if (b == NULL && a != NULL)
101 0 : return 0;
102 :
103 145504 : return !memcmp(a, b, 2 * sizeof(struct prefix));
104 : }
105 :
106 : static void
107 281 : log_free(void *data)
108 : {
109 281 : XFREE(MTYPE_TMP, data);
110 281 : }
111 :
112 : static void *
113 541 : log_alloc(void *data)
114 : {
115 541 : void *rv = XMALLOC(MTYPE_TMP, 2 * sizeof(struct prefix));
116 541 : memcpy(rv, data, 2 * sizeof(struct prefix));
117 541 : return rv;
118 : }
119 :
120 : static struct test_state *
121 1 : test_state_new(void)
122 : {
123 : struct test_state *rv;
124 :
125 1 : rv = XCALLOC(MTYPE_TMP, sizeof(*rv));
126 1 : assert(rv);
127 :
128 1 : rv->table = srcdest_table_init();
129 1 : assert(rv->table);
130 :
131 1 : rv->log = hash_create(log_key, log_cmp);
132 1 : return rv;
133 : }
134 :
135 : static void
136 1 : test_state_free(struct test_state *test)
137 : {
138 1 : route_table_finish(test->table);
139 1 : hash_clean(test->log, log_free);
140 1 : hash_free(test->log);
141 1 : XFREE(MTYPE_TMP, test);
142 1 : }
143 :
144 : static void
145 541 : test_state_add_route(struct test_state *test,
146 : struct prefix_ipv6 *dst_p,
147 : struct prefix_ipv6 *src_p)
148 : {
149 541 : struct route_node *rn = srcdest_rnode_get(
150 : test->table, (struct prefix*)dst_p,
151 : (struct prefix*)src_p
152 : );
153 : struct prefix hash_entry[2];
154 :
155 541 : memset(hash_entry, 0, sizeof(hash_entry));
156 541 : memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
157 541 : memcpy(&hash_entry[1], src_p, sizeof(*src_p));
158 :
159 541 : if (rn->info) {
160 0 : route_unlock_node(rn);
161 0 : assert(hash_lookup(test->log, hash_entry) != NULL);
162 0 : return;
163 : } else {
164 541 : assert(hash_lookup(test->log, hash_entry) == NULL);
165 : }
166 :
167 541 : rn->info = (void*) 0xdeadbeef;
168 541 : hash_get(test->log, hash_entry, log_alloc);
169 : };
170 :
171 : static void
172 459 : test_state_del_route(struct test_state *test,
173 : struct prefix_ipv6 *dst_p,
174 : struct prefix_ipv6 *src_p)
175 : {
176 459 : struct route_node *rn = srcdest_rnode_lookup(
177 : test->table, (struct prefix*)dst_p,
178 : (struct prefix*)src_p
179 : );
180 : struct prefix hash_entry[2];
181 :
182 459 : memset(hash_entry, 0, sizeof(hash_entry));
183 459 : memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
184 459 : memcpy(&hash_entry[1], src_p, sizeof(*src_p));
185 :
186 459 : if (!rn) {
187 199 : assert(!hash_lookup(test->log, hash_entry));
188 199 : return;
189 : }
190 :
191 260 : assert(rn->info == (void*)0xdeadbeef);
192 260 : rn->info = NULL;
193 260 : route_unlock_node(rn);
194 260 : route_unlock_node(rn);
195 :
196 260 : struct prefix *hash_entry_intern = hash_release(test->log, hash_entry);
197 260 : assert(hash_entry_intern != NULL);
198 260 : XFREE(MTYPE_TMP, hash_entry_intern);
199 : }
200 :
201 : static void
202 145244 : verify_log(struct hash_backet* backet, void *arg)
203 : {
204 145244 : struct test_state *test = arg;
205 145244 : struct prefix *hash_entry = backet->data;
206 145244 : struct prefix *dst_p = &hash_entry[0];
207 145244 : struct prefix *src_p = &hash_entry[1];
208 145244 : struct route_node *rn = srcdest_rnode_lookup(test->table, dst_p, src_p);
209 :
210 145244 : assert(rn);
211 145244 : assert(rn->info == (void*)0xdeadbeef);
212 :
213 145244 : route_unlock_node(rn);
214 145244 : }
215 :
216 : static void
217 0 : dump_log(struct hash_backet* backet, void *arg)
218 : {
219 0 : struct prefix *hash_entry = backet->data;
220 0 : struct prefix_ipv6 *dst_p = (struct prefix_ipv6*)&hash_entry[0];
221 0 : struct prefix_ipv6 *src_p = (struct prefix_ipv6*)&hash_entry[1];
222 0 : char *route_id = format_srcdest(dst_p, src_p);
223 :
224 0 : fprintf(stderr, " %s\n", route_id);
225 0 : free(route_id);
226 0 : }
227 :
228 : static void
229 0 : test_dump(struct test_state *test)
230 : {
231 0 : fprintf(stderr, "Contents of hash table:\n");
232 0 : hash_iterate(test->log, dump_log, test);
233 0 : fprintf(stderr, "\n");
234 0 : }
235 :
236 : static void
237 0 : test_failed(struct test_state *test, const char *message,
238 : struct prefix_ipv6 *dst_p, struct prefix_ipv6 *src_p)
239 : {
240 0 : char *route_id = format_srcdest(dst_p, src_p);
241 :
242 0 : fprintf(stderr, "Test failed. Error: %s\n", message);
243 0 : fprintf(stderr, "Route in question: %s\n", route_id);
244 0 : free(route_id);
245 :
246 0 : test_dump(test);
247 0 : assert(3 == 4);
248 : }
249 :
250 : static void
251 1000 : test_state_verify(struct test_state *test)
252 : {
253 : struct route_node *rn;
254 : struct prefix hash_entry[2];
255 :
256 1000 : memset(hash_entry, 0, sizeof(hash_entry));
257 :
258 : /* Verify that there are no elements in the table which have never
259 : * been added */
260 369314 : for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn))
261 : {
262 : struct prefix_ipv6 *dst_p, *src_p;
263 :
264 : /* While we are iterating, we hold a lock on the current route_node,
265 : * so all the lock counts we check for take that into account; in idle
266 : * state all the numbers will be exactly one less.
267 : *
268 : * Also this makes quite some assumptions based on the current
269 : * implementation details of route_table and srcdest_table - another
270 : * valid implementation might trigger assertions here.
271 : */
272 :
273 368314 : if (rnode_is_dstnode(rn))
274 : {
275 268348 : struct srcdest_rnode *srn = (struct srcdest_rnode *)rn;
276 268348 : unsigned int expected_lock = 1; /* We are in the loop */
277 :
278 268348 : if (rn->info != NULL) /* The route node is not internal */
279 47559 : expected_lock++;
280 268348 : if (srn->src_table != NULL) /* There's a source table associated with rn */
281 95404 : expected_lock++;
282 :
283 268348 : if (rn->lock != expected_lock)
284 0 : test_failed(test, "Dest rnode lock count doesn't match expected count!",
285 0 : (struct prefix_ipv6*)&rn->p, NULL);
286 : }
287 : else
288 : {
289 99966 : unsigned int expected_lock = 1; /* We are in the loop */
290 :
291 99966 : if (rn->info != NULL) /* The route node is not internal */
292 97685 : expected_lock++;
293 :
294 99966 : if (rn->lock != expected_lock)
295 : {
296 : struct prefix_ipv6 *dst_p, *src_p;
297 0 : srcdest_rnode_prefixes(rn, (struct prefix**)&dst_p,
298 : (struct prefix**)&src_p);
299 :
300 0 : test_failed(test, "Src rnode lock count doesn't match expected count!",
301 : dst_p, src_p);
302 : }
303 : }
304 :
305 368314 : if (!rn->info)
306 223070 : continue;
307 :
308 145244 : assert(rn->info == (void*)0xdeadbeef);
309 :
310 145244 : srcdest_rnode_prefixes(rn, (struct prefix**)&dst_p, (struct prefix**)&src_p);
311 145244 : memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
312 145244 : if (src_p)
313 97685 : memcpy(&hash_entry[1], src_p, sizeof(*src_p));
314 : else
315 47559 : memset(&hash_entry[1], 0, sizeof(hash_entry[1]));
316 :
317 145244 : if (hash_lookup(test->log, hash_entry) == NULL)
318 0 : test_failed(test, "Route is missing in hash", dst_p, src_p);
319 : }
320 :
321 : /* Verify that all added elements are still in the table */
322 1000 : hash_iterate(test->log, verify_log, test);
323 1000 : }
324 :
325 : static void
326 1214 : get_rand_prefix(struct prng *prng, struct prefix_ipv6 *p)
327 : {
328 : int i;
329 :
330 1214 : memset(p, 0, sizeof(*p));
331 :
332 6070 : for (i = 0; i < 4; i++)
333 4856 : p->prefix.s6_addr32[i] = prng_rand(prng);
334 1214 : p->prefixlen = prng_rand(prng) % 129;
335 1214 : p->family = AF_INET6;
336 :
337 1214 : apply_mask((struct prefix*)p);
338 1214 : }
339 :
340 : static void
341 740 : get_rand_prefix_pair(struct prng *prng, struct prefix_ipv6 *dst_p,
342 : struct prefix_ipv6 *src_p)
343 : {
344 740 : get_rand_prefix(prng, dst_p);
345 740 : if ((prng_rand(prng) % 4) == 0)
346 : {
347 474 : get_rand_prefix(prng, src_p);
348 474 : if (src_p->prefixlen)
349 468 : return;
350 : }
351 :
352 272 : memset(src_p, 0, sizeof(*src_p));
353 : }
354 :
355 : static void
356 541 : test_state_add_rand_route(struct test_state *test,
357 : struct prng *prng)
358 : {
359 : struct prefix_ipv6 dst_p, src_p;
360 :
361 541 : get_rand_prefix_pair(prng, &dst_p, &src_p);
362 541 : test_state_add_route(test, &dst_p, &src_p);
363 541 : }
364 :
365 : static void
366 199 : test_state_del_rand_route(struct test_state *test,
367 : struct prng *prng)
368 : {
369 : struct prefix_ipv6 dst_p, src_p;
370 :
371 199 : get_rand_prefix_pair(prng, &dst_p, &src_p);
372 199 : test_state_del_route(test, &dst_p, &src_p);
373 199 : }
374 :
375 : static void
376 260 : test_state_del_one_route(struct test_state *test,
377 : struct prng *prng)
378 : {
379 260 : unsigned int which_route = prng_rand(prng) % test->log->count;
380 : struct route_node *rn;
381 : struct prefix *dst_p, *src_p;
382 : struct prefix_ipv6 dst6_p, src6_p;
383 :
384 52677 : for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn))
385 : {
386 52677 : if (!rn->info)
387 31855 : continue;
388 20822 : if (!which_route) {
389 260 : route_unlock_node(rn);
390 260 : break;
391 : }
392 20562 : which_route--;
393 : }
394 :
395 260 : assert(rn);
396 260 : srcdest_rnode_prefixes(rn, &dst_p, &src_p);
397 260 : memcpy(&dst6_p, dst_p, sizeof(dst6_p));
398 260 : if (src_p)
399 179 : memcpy(&src6_p, src_p, sizeof(src6_p));
400 : else
401 81 : memset(&src6_p, 0, sizeof(src6_p));
402 :
403 260 : test_state_del_route(test, &dst6_p, &src6_p);
404 260 : }
405 :
406 : static void
407 1 : run_prng_test(void)
408 : {
409 1 : struct test_state *test = test_state_new();
410 1 : struct prng *prng = prng_new(0);
411 : size_t i;
412 :
413 1001 : for (i = 0; i < 1000; i++)
414 : {
415 1000 : switch (prng_rand(prng) % 10)
416 : {
417 : case 0:
418 : case 1:
419 : case 2:
420 : case 3:
421 : case 4:
422 541 : test_state_add_rand_route(test, prng);
423 541 : break;
424 : case 5:
425 : case 6:
426 : case 7:
427 260 : test_state_del_one_route(test, prng);
428 260 : break;
429 : case 8:
430 : case 9:
431 199 : test_state_del_rand_route(test, prng);
432 199 : break;
433 : }
434 1000 : test_state_verify(test);
435 : }
436 :
437 1 : prng_free(prng);
438 1 : test_state_free(test);
439 1 : }
440 :
441 1 : int main(int argc, char *argv[])
442 : {
443 1 : run_prng_test();
444 1 : printf("PRNG Test successful.\n");
445 1 : return 0;
446 : }
|
