]>
git.proxmox.com Git - mirror_frr.git/blob - tests/lib/test_srcdest_table.c
2 * Test srcdest table for correctness.
4 * Copyright (C) 2017 by David Lamparter & Christian Franke,
5 * Open Source Routing / NetDEF Inc.
7 * This file is part of FreeRangeRouting (FRR)
9 * FRR is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License as published by the
11 * Free Software Foundation; either version 2, or (at your option) any
14 * FRR is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * General Public License for more details.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; see the file COPYING; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
30 #include "srcdest_table.h"
33 /* Copied from ripngd/ripng_nexthop.h - maybe the whole s6_addr32 thing
34 * should be added by autoconf if not present?
38 /* Some SunOS define s6_addr32 only to kernel */
39 #define s6_addr32 _S6_un._S6_u32
41 #define s6_addr32 __u6_addr.__u6_addr32
45 struct thread_master
*master
;
47 /* This structure is copied from lib/srcdest_table.c to which it is
48 * private as far as other parts of Quagga are concerned.
50 struct srcdest_rnode
{
51 /* must be first in structure for casting to/from route_node */
54 struct route_table
*src_table
;
58 struct route_table
*table
;
62 static char *format_srcdest(const struct prefix_ipv6
*dst_p
,
63 const struct prefix_ipv6
*src_p
)
70 prefix2str((const struct prefix
*)dst_p
, dst_str
, sizeof(dst_str
));
71 if (src_p
&& src_p
->prefixlen
)
72 prefix2str((const struct prefix
*)src_p
, src_str
,
77 ec
= asprintf(&rv
, "%s%s%s", dst_str
,
78 (src_str
[0] != '\0') ? " from " : "", src_str
);
84 static unsigned int log_key(const void *data
)
86 const struct prefix
*hash_entry
= data
;
87 struct prefix_ipv6
*dst_p
= (struct prefix_ipv6
*)&hash_entry
[0];
88 struct prefix_ipv6
*src_p
= (struct prefix_ipv6
*)&hash_entry
[1];
89 unsigned int hash
= 0;
92 hash
= (hash
* 33) ^ (unsigned int)dst_p
->prefixlen
;
93 for (i
= 0; i
< 4; i
++)
94 hash
= (hash
* 33) ^ (unsigned int)dst_p
->prefix
.s6_addr32
[i
];
96 hash
= (hash
* 33) ^ (unsigned int)src_p
->prefixlen
;
98 for (i
= 0; i
< 4; i
++)
100 ^ (unsigned int)src_p
->prefix
.s6_addr32
[i
];
105 static bool log_cmp(const void *a
, const void *b
)
107 if (a
== NULL
|| b
== NULL
)
110 return !memcmp(a
, b
, 2 * sizeof(struct prefix
));
113 static void log_free(void *data
)
115 XFREE(MTYPE_TMP
, data
);
118 static void *log_alloc(void *data
)
120 void *rv
= XMALLOC(MTYPE_TMP
, 2 * sizeof(struct prefix
));
121 memcpy(rv
, data
, 2 * sizeof(struct prefix
));
125 static struct test_state
*test_state_new(void)
127 struct test_state
*rv
;
129 rv
= XCALLOC(MTYPE_TMP
, sizeof(*rv
));
132 rv
->table
= srcdest_table_init();
135 rv
->log
= hash_create(log_key
, log_cmp
, NULL
);
139 static void test_state_free(struct test_state
*test
)
141 route_table_finish(test
->table
);
142 hash_clean(test
->log
, log_free
);
143 hash_free(test
->log
);
144 XFREE(MTYPE_TMP
, test
);
147 static void test_state_add_route(struct test_state
*test
,
148 struct prefix_ipv6
*dst_p
,
149 struct prefix_ipv6
*src_p
)
151 struct route_node
*rn
=
152 srcdest_rnode_get(test
->table
, (struct prefix
*)dst_p
, src_p
);
153 struct prefix hash_entry
[2];
155 memset(hash_entry
, 0, sizeof(hash_entry
));
156 memcpy(&hash_entry
[0], dst_p
, sizeof(*dst_p
));
157 memcpy(&hash_entry
[1], src_p
, sizeof(*src_p
));
160 route_unlock_node(rn
);
161 assert(hash_lookup(test
->log
, hash_entry
) != NULL
);
164 assert(hash_lookup(test
->log
, hash_entry
) == NULL
);
167 rn
->info
= (void *)0xdeadbeef;
168 hash_get(test
->log
, hash_entry
, log_alloc
);
171 static void test_state_del_route(struct test_state
*test
,
172 struct prefix_ipv6
*dst_p
,
173 struct prefix_ipv6
*src_p
)
175 struct route_node
*rn
= srcdest_rnode_lookup(
176 test
->table
, (struct prefix
*)dst_p
, src_p
);
177 struct prefix hash_entry
[2];
179 memset(hash_entry
, 0, sizeof(hash_entry
));
180 memcpy(&hash_entry
[0], dst_p
, sizeof(*dst_p
));
181 memcpy(&hash_entry
[1], src_p
, sizeof(*src_p
));
184 assert(!hash_lookup(test
->log
, hash_entry
));
188 assert(rn
->info
== (void *)0xdeadbeef);
190 route_unlock_node(rn
);
191 route_unlock_node(rn
);
193 struct prefix
*hash_entry_intern
= hash_release(test
->log
, hash_entry
);
194 assert(hash_entry_intern
!= NULL
);
195 XFREE(MTYPE_TMP
, hash_entry_intern
);
198 static void verify_log(struct hash_bucket
*bucket
, void *arg
)
200 struct test_state
*test
= arg
;
201 struct prefix
*hash_entry
= bucket
->data
;
202 struct prefix
*dst_p
= &hash_entry
[0];
203 struct prefix_ipv6
*src_p
= (struct prefix_ipv6
*)&hash_entry
[1];
204 struct route_node
*rn
= srcdest_rnode_lookup(test
->table
, dst_p
, src_p
);
207 assert(rn
->info
== (void *)0xdeadbeef);
209 route_unlock_node(rn
);
212 static void dump_log(struct hash_bucket
*bucket
, void *arg
)
214 struct prefix
*hash_entry
= bucket
->data
;
215 struct prefix_ipv6
*dst_p
= (struct prefix_ipv6
*)&hash_entry
[0];
216 struct prefix_ipv6
*src_p
= (struct prefix_ipv6
*)&hash_entry
[1];
217 char *route_id
= format_srcdest(dst_p
, src_p
);
219 fprintf(stderr
, " %s\n", route_id
);
223 static void test_dump(struct test_state
*test
)
225 fprintf(stderr
, "Contents of hash table:\n");
226 hash_iterate(test
->log
, dump_log
, test
);
227 fprintf(stderr
, "\n");
230 static void test_failed(struct test_state
*test
, const char *message
,
231 const struct prefix_ipv6
*dst_p
,
232 const struct prefix_ipv6
*src_p
)
234 char *route_id
= format_srcdest(dst_p
, src_p
);
236 fprintf(stderr
, "Test failed. Error: %s\n", message
);
237 fprintf(stderr
, "Route in question: %s\n", route_id
);
244 static void test_state_verify(struct test_state
*test
)
246 struct route_node
*rn
;
247 struct prefix hash_entry
[2];
249 memset(hash_entry
, 0, sizeof(hash_entry
));
251 /* Verify that there are no elements in the table which have never
253 for (rn
= route_top(test
->table
); rn
; rn
= srcdest_route_next(rn
)) {
254 const struct prefix_ipv6
*dst_p
, *src_p
;
256 /* While we are iterating, we hold a lock on the current
258 * so all the lock counts we check for take that into account;
260 * state all the numbers will be exactly one less.
262 * Also this makes quite some assumptions based on the current
263 * implementation details of route_table and srcdest_table -
265 * valid implementation might trigger assertions here.
268 if (rnode_is_dstnode(rn
)) {
269 struct srcdest_rnode
*srn
= (struct srcdest_rnode
*)rn
;
270 unsigned int expected_lock
= 1; /* We are in the loop */
273 != NULL
) /* The route node is not internal */
275 if (srn
->src_table
!= NULL
) /* There's a source table
276 associated with rn */
279 if (rn
->lock
!= expected_lock
)
282 "Dest rnode lock count doesn't match expected count!",
283 (struct prefix_ipv6
*)&rn
->p
, NULL
);
285 unsigned int expected_lock
= 1; /* We are in the loop */
288 != NULL
) /* The route node is not internal */
291 if (rn
->lock
!= expected_lock
) {
292 srcdest_rnode_prefixes(
293 rn
, (const struct prefix
**)&dst_p
,
294 (const struct prefix
**)&src_p
);
298 "Src rnode lock count doesn't match expected count!",
306 assert(rn
->info
== (void *)0xdeadbeef);
308 srcdest_rnode_prefixes(rn
, (const struct prefix
**)&dst_p
,
309 (const struct prefix
**)&src_p
);
310 memcpy(&hash_entry
[0], dst_p
, sizeof(*dst_p
));
312 memcpy(&hash_entry
[1], src_p
, sizeof(*src_p
));
314 memset(&hash_entry
[1], 0, sizeof(hash_entry
[1]));
316 if (hash_lookup(test
->log
, hash_entry
) == NULL
)
317 test_failed(test
, "Route is missing in hash", dst_p
,
321 /* Verify that all added elements are still in the table */
322 hash_iterate(test
->log
, verify_log
, test
);
325 static void get_rand_prefix(struct prng
*prng
, struct prefix_ipv6
*p
)
329 memset(p
, 0, sizeof(*p
));
331 for (i
= 0; i
< 4; i
++)
332 p
->prefix
.s6_addr32
[i
] = prng_rand(prng
);
333 p
->prefixlen
= prng_rand(prng
) % 129;
334 p
->family
= AF_INET6
;
336 apply_mask((struct prefix
*)p
);
339 static void get_rand_prefix_pair(struct prng
*prng
, struct prefix_ipv6
*dst_p
,
340 struct prefix_ipv6
*src_p
)
342 get_rand_prefix(prng
, dst_p
);
343 if ((prng_rand(prng
) % 4) == 0) {
344 get_rand_prefix(prng
, src_p
);
345 if (src_p
->prefixlen
)
349 memset(src_p
, 0, sizeof(*src_p
));
352 static void test_state_add_rand_route(struct test_state
*test
,
355 struct prefix_ipv6 dst_p
, src_p
;
357 get_rand_prefix_pair(prng
, &dst_p
, &src_p
);
358 test_state_add_route(test
, &dst_p
, &src_p
);
361 static void test_state_del_rand_route(struct test_state
*test
,
364 struct prefix_ipv6 dst_p
, src_p
;
366 get_rand_prefix_pair(prng
, &dst_p
, &src_p
);
367 test_state_del_route(test
, &dst_p
, &src_p
);
370 static void test_state_del_one_route(struct test_state
*test
, struct prng
*prng
)
372 unsigned int which_route
;
374 if (test
->log
->count
== 0)
377 which_route
= prng_rand(prng
) % test
->log
->count
;
379 struct route_node
*rn
;
380 const struct prefix
*dst_p
, *src_p
;
381 struct prefix_ipv6 dst6_p
, src6_p
;
383 for (rn
= route_top(test
->table
); rn
; rn
= srcdest_route_next(rn
)) {
387 route_unlock_node(rn
);
394 srcdest_rnode_prefixes(rn
, (const struct prefix
**)&dst_p
,
395 (const struct prefix
**)&src_p
);
396 memcpy(&dst6_p
, dst_p
, sizeof(dst6_p
));
398 memcpy(&src6_p
, src_p
, sizeof(src6_p
));
400 memset(&src6_p
, 0, sizeof(src6_p
));
402 test_state_del_route(test
, &dst6_p
, &src6_p
);
405 static void run_prng_test(void)
407 struct test_state
*test
= test_state_new();
408 struct prng
*prng
= prng_new(0);
411 for (i
= 0; i
< 1000; i
++) {
412 switch (prng_rand(prng
) % 10) {
418 test_state_add_rand_route(test
, prng
);
423 test_state_del_one_route(test
, prng
);
427 test_state_del_rand_route(test
, prng
);
430 test_state_verify(test
);
434 test_state_free(test
);
437 int main(int argc
, char *argv
[])
440 printf("PRNG Test successful.\n");