]>
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 FRRouting (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?
37 #define s6_addr32 __u6_addr.__u6_addr32
40 struct thread_master
*master
;
42 /* This structure is copied from lib/srcdest_table.c to which it is
43 * private as far as other parts of Quagga are concerned.
45 struct srcdest_rnode
{
46 /* must be first in structure for casting to/from route_node */
49 struct route_table
*src_table
;
53 struct route_table
*table
;
57 static char *format_srcdest(const struct prefix_ipv6
*dst_p
,
58 const struct prefix_ipv6
*src_p
)
65 prefix2str((const struct prefix
*)dst_p
, dst_str
, sizeof(dst_str
));
66 if (src_p
&& src_p
->prefixlen
)
67 prefix2str((const struct prefix
*)src_p
, src_str
,
72 ec
= asprintf(&rv
, "%s%s%s", dst_str
,
73 (src_str
[0] != '\0') ? " from " : "", src_str
);
79 static unsigned int log_key(const void *data
)
81 const struct prefix
*hash_entry
= data
;
82 struct prefix_ipv6
*dst_p
= (struct prefix_ipv6
*)&hash_entry
[0];
83 struct prefix_ipv6
*src_p
= (struct prefix_ipv6
*)&hash_entry
[1];
84 unsigned int hash
= 0;
87 hash
= (hash
* 33) ^ (unsigned int)dst_p
->prefixlen
;
88 for (i
= 0; i
< 4; i
++)
89 hash
= (hash
* 33) ^ (unsigned int)dst_p
->prefix
.s6_addr32
[i
];
91 hash
= (hash
* 33) ^ (unsigned int)src_p
->prefixlen
;
93 for (i
= 0; i
< 4; i
++)
95 ^ (unsigned int)src_p
->prefix
.s6_addr32
[i
];
100 static bool log_cmp(const void *a
, const void *b
)
102 if (a
== NULL
|| b
== NULL
)
105 return !memcmp(a
, b
, 2 * sizeof(struct prefix
));
108 static void log_free(void *data
)
110 XFREE(MTYPE_TMP
, data
);
113 static void *log_alloc(void *data
)
115 void *rv
= XMALLOC(MTYPE_TMP
, 2 * sizeof(struct prefix
));
116 memcpy(rv
, data
, 2 * sizeof(struct prefix
));
120 static struct test_state
*test_state_new(void)
122 struct test_state
*rv
;
124 rv
= XCALLOC(MTYPE_TMP
, sizeof(*rv
));
127 rv
->table
= srcdest_table_init();
130 rv
->log
= hash_create(log_key
, log_cmp
, NULL
);
134 static void test_state_free(struct test_state
*test
)
136 route_table_finish(test
->table
);
137 hash_clean(test
->log
, log_free
);
138 hash_free(test
->log
);
139 XFREE(MTYPE_TMP
, test
);
142 static void test_state_add_route(struct test_state
*test
,
143 struct prefix_ipv6
*dst_p
,
144 struct prefix_ipv6
*src_p
)
146 struct route_node
*rn
=
147 srcdest_rnode_get(test
->table
, (struct prefix
*)dst_p
, src_p
);
148 struct prefix hash_entry
[2];
150 memset(hash_entry
, 0, sizeof(hash_entry
));
151 memcpy(&hash_entry
[0], dst_p
, sizeof(*dst_p
));
152 memcpy(&hash_entry
[1], src_p
, sizeof(*src_p
));
155 route_unlock_node(rn
);
156 assert(hash_lookup(test
->log
, hash_entry
) != NULL
);
159 assert(hash_lookup(test
->log
, hash_entry
) == NULL
);
162 rn
->info
= (void *)0xdeadbeef;
163 hash_get(test
->log
, hash_entry
, log_alloc
);
166 static void test_state_del_route(struct test_state
*test
,
167 struct prefix_ipv6
*dst_p
,
168 struct prefix_ipv6
*src_p
)
170 struct route_node
*rn
= srcdest_rnode_lookup(
171 test
->table
, (struct prefix
*)dst_p
, src_p
);
172 struct prefix hash_entry
[2];
174 memset(hash_entry
, 0, sizeof(hash_entry
));
175 memcpy(&hash_entry
[0], dst_p
, sizeof(*dst_p
));
176 memcpy(&hash_entry
[1], src_p
, sizeof(*src_p
));
179 assert(!hash_lookup(test
->log
, hash_entry
));
183 assert(rn
->info
== (void *)0xdeadbeef);
185 route_unlock_node(rn
);
186 route_unlock_node(rn
);
188 struct prefix
*hash_entry_intern
= hash_release(test
->log
, hash_entry
);
189 assert(hash_entry_intern
!= NULL
);
190 XFREE(MTYPE_TMP
, hash_entry_intern
);
193 static void verify_log(struct hash_bucket
*bucket
, void *arg
)
195 struct test_state
*test
= arg
;
196 struct prefix
*hash_entry
= bucket
->data
;
197 struct prefix
*dst_p
= &hash_entry
[0];
198 struct prefix_ipv6
*src_p
= (struct prefix_ipv6
*)&hash_entry
[1];
199 struct route_node
*rn
= srcdest_rnode_lookup(test
->table
, dst_p
, src_p
);
202 assert(rn
->info
== (void *)0xdeadbeef);
204 route_unlock_node(rn
);
207 static void dump_log(struct hash_bucket
*bucket
, void *arg
)
209 struct prefix
*hash_entry
= bucket
->data
;
210 struct prefix_ipv6
*dst_p
= (struct prefix_ipv6
*)&hash_entry
[0];
211 struct prefix_ipv6
*src_p
= (struct prefix_ipv6
*)&hash_entry
[1];
212 char *route_id
= format_srcdest(dst_p
, src_p
);
214 fprintf(stderr
, " %s\n", route_id
);
218 static void test_dump(struct test_state
*test
)
220 fprintf(stderr
, "Contents of hash table:\n");
221 hash_iterate(test
->log
, dump_log
, test
);
222 fprintf(stderr
, "\n");
225 static void test_failed(struct test_state
*test
, const char *message
,
226 const struct prefix_ipv6
*dst_p
,
227 const struct prefix_ipv6
*src_p
)
229 char *route_id
= format_srcdest(dst_p
, src_p
);
231 fprintf(stderr
, "Test failed. Error: %s\n", message
);
232 fprintf(stderr
, "Route in question: %s\n", route_id
);
239 static void test_state_verify(struct test_state
*test
)
241 struct route_node
*rn
;
242 struct prefix hash_entry
[2];
244 memset(hash_entry
, 0, sizeof(hash_entry
));
246 /* Verify that there are no elements in the table which have never
248 for (rn
= route_top(test
->table
); rn
; rn
= srcdest_route_next(rn
)) {
249 const struct prefix_ipv6
*dst_p
, *src_p
;
251 /* While we are iterating, we hold a lock on the current
253 * so all the lock counts we check for take that into account;
255 * state all the numbers will be exactly one less.
257 * Also this makes quite some assumptions based on the current
258 * implementation details of route_table and srcdest_table -
260 * valid implementation might trigger assertions here.
263 if (rnode_is_dstnode(rn
)) {
264 struct srcdest_rnode
*srn
= (struct srcdest_rnode
*)rn
;
265 unsigned int expected_lock
= 1; /* We are in the loop */
268 != NULL
) /* The route node is not internal */
270 if (srn
->src_table
!= NULL
) /* There's a source table
271 associated with rn */
274 if (route_node_get_lock_count(rn
) != expected_lock
)
277 "Dest rnode lock count doesn't match expected count!",
278 (struct prefix_ipv6
*)&rn
->p
, NULL
);
280 unsigned int expected_lock
= 1; /* We are in the loop */
283 != NULL
) /* The route node is not internal */
286 if (route_node_get_lock_count(rn
) != expected_lock
) {
287 srcdest_rnode_prefixes(
288 rn
, (const struct prefix
**)&dst_p
,
289 (const struct prefix
**)&src_p
);
293 "Src rnode lock count doesn't match expected count!",
301 assert(rn
->info
== (void *)0xdeadbeef);
303 srcdest_rnode_prefixes(rn
, (const struct prefix
**)&dst_p
,
304 (const struct prefix
**)&src_p
);
305 memcpy(&hash_entry
[0], dst_p
, sizeof(*dst_p
));
307 memcpy(&hash_entry
[1], src_p
, sizeof(*src_p
));
309 memset(&hash_entry
[1], 0, sizeof(hash_entry
[1]));
311 if (hash_lookup(test
->log
, hash_entry
) == NULL
)
312 test_failed(test
, "Route is missing in hash", dst_p
,
316 /* Verify that all added elements are still in the table */
317 hash_iterate(test
->log
, verify_log
, test
);
320 static void get_rand_prefix(struct prng
*prng
, struct prefix_ipv6
*p
)
324 memset(p
, 0, sizeof(*p
));
326 for (i
= 0; i
< 4; i
++)
327 p
->prefix
.s6_addr32
[i
] = prng_rand(prng
);
328 p
->prefixlen
= prng_rand(prng
) % 129;
329 p
->family
= AF_INET6
;
331 apply_mask((struct prefix
*)p
);
334 static void get_rand_prefix_pair(struct prng
*prng
, struct prefix_ipv6
*dst_p
,
335 struct prefix_ipv6
*src_p
)
337 get_rand_prefix(prng
, dst_p
);
338 if ((prng_rand(prng
) % 4) == 0) {
339 get_rand_prefix(prng
, src_p
);
340 if (src_p
->prefixlen
)
344 memset(src_p
, 0, sizeof(*src_p
));
347 static void test_state_add_rand_route(struct test_state
*test
,
350 struct prefix_ipv6 dst_p
, src_p
;
352 get_rand_prefix_pair(prng
, &dst_p
, &src_p
);
353 test_state_add_route(test
, &dst_p
, &src_p
);
356 static void test_state_del_rand_route(struct test_state
*test
,
359 struct prefix_ipv6 dst_p
, src_p
;
361 get_rand_prefix_pair(prng
, &dst_p
, &src_p
);
362 test_state_del_route(test
, &dst_p
, &src_p
);
365 static void test_state_del_one_route(struct test_state
*test
, struct prng
*prng
)
367 unsigned int which_route
;
369 if (test
->log
->count
== 0)
372 which_route
= prng_rand(prng
) % test
->log
->count
;
374 struct route_node
*rn
;
375 const struct prefix
*dst_p
, *src_p
;
376 struct prefix_ipv6 dst6_p
, src6_p
;
378 for (rn
= route_top(test
->table
); rn
; rn
= srcdest_route_next(rn
)) {
382 route_unlock_node(rn
);
389 srcdest_rnode_prefixes(rn
, &dst_p
, &src_p
);
390 memcpy(&dst6_p
, dst_p
, sizeof(dst6_p
));
392 memcpy(&src6_p
, src_p
, sizeof(src6_p
));
394 memset(&src6_p
, 0, sizeof(src6_p
));
396 test_state_del_route(test
, &dst6_p
, &src6_p
);
399 static void run_prng_test(void)
401 struct test_state
*test
= test_state_new();
402 struct prng
*prng
= prng_new(0);
405 for (i
= 0; i
< 1000; i
++) {
406 switch (prng_rand(prng
) % 10) {
412 test_state_add_rand_route(test
, prng
);
417 test_state_del_one_route(test
, prng
);
421 test_state_del_rand_route(test
, prng
);
424 test_state_verify(test
);
428 test_state_free(test
);
431 int main(int argc
, char *argv
[])
434 printf("PRNG Test successful.\n");