]>
Commit | Line | Data |
---|---|---|
fa713d9e CF |
1 | /* |
2 | * Recursive Nexthop Iterator test. | |
8e688dbd | 3 | * This tests the ALL_NEXTHOPS macro. |
fa713d9e CF |
4 | * |
5 | * Copyright (C) 2012 by Open Source Routing. | |
6 | * Copyright (C) 2012 by Internet Systems Consortium, Inc. ("ISC") | |
7 | * | |
8 | * This file is part of Quagga | |
9 | * | |
10 | * Quagga is free software; you can redistribute it and/or modify it | |
11 | * under the terms of the GNU General Public License as published by the | |
12 | * Free Software Foundation; either version 2, or (at your option) any | |
13 | * later version. | |
14 | * | |
15 | * Quagga is distributed in the hope that it will be useful, but | |
16 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
18 | * General Public License for more details. | |
19 | * | |
896014f4 DL |
20 | * You should have received a copy of the GNU General Public License along |
21 | * with this program; see the file COPYING; if not, write to the Free Software | |
22 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
fa713d9e CF |
23 | */ |
24 | ||
25 | #include <zebra.h> | |
26 | #include "zebra/rib.h" | |
27 | #include "prng.h" | |
28 | ||
29 | struct thread_master *master; | |
30 | static int verbose; | |
31 | ||
d62a17ae | 32 | static void str_append(char **buf, const char *repr) |
fa713d9e | 33 | { |
d62a17ae | 34 | if (*buf) { |
35 | *buf = realloc(*buf, strlen(*buf) + strlen(repr) + 1); | |
36 | assert(*buf); | |
37 | strncpy((*buf) + strlen(*buf), repr, strlen(repr) + 1); | |
38 | } else { | |
39 | *buf = strdup(repr); | |
40 | assert(*buf); | |
41 | } | |
fa713d9e CF |
42 | } |
43 | ||
ba727609 | 44 | PRINTFRR(2, 3) |
d62a17ae | 45 | static void str_appendf(char **buf, const char *format, ...) |
fa713d9e | 46 | { |
d62a17ae | 47 | va_list ap; |
48 | int rv; | |
49 | char *pbuf; | |
fa713d9e | 50 | |
d62a17ae | 51 | va_start(ap, format); |
52 | rv = vasprintf(&pbuf, format, ap); | |
53 | va_end(ap); | |
54 | assert(rv >= 0); | |
fa713d9e | 55 | |
d62a17ae | 56 | str_append(buf, pbuf); |
57 | free(pbuf); | |
fa713d9e CF |
58 | } |
59 | ||
60 | /* This structure contains a nexthop chain | |
61 | * and its expected representation */ | |
d62a17ae | 62 | struct nexthop_chain { |
63 | /* Head of the chain */ | |
7ee30f28 | 64 | struct nexthop_group head; |
d62a17ae | 65 | /* Last nexthop in top chain */ |
66 | struct nexthop *current_top; | |
67 | /* Last nexthop in current recursive chain */ | |
68 | struct nexthop *current_recursive; | |
69 | /* Expected string representation. */ | |
70 | char *repr; | |
fa713d9e CF |
71 | }; |
72 | ||
d62a17ae | 73 | static struct nexthop_chain *nexthop_chain_new(void) |
fa713d9e | 74 | { |
d62a17ae | 75 | struct nexthop_chain *rv; |
fa713d9e | 76 | |
d62a17ae | 77 | rv = calloc(sizeof(*rv), 1); |
78 | assert(rv); | |
79 | return rv; | |
fa713d9e CF |
80 | } |
81 | ||
d62a17ae | 82 | static void nexthop_chain_add_top(struct nexthop_chain *nc) |
fa713d9e | 83 | { |
d62a17ae | 84 | struct nexthop *nh; |
85 | ||
86 | nh = calloc(sizeof(*nh), 1); | |
87 | assert(nh); | |
88 | ||
7ee30f28 | 89 | if (nc->head.nexthop) { |
d62a17ae | 90 | nc->current_top->next = nh; |
91 | nh->prev = nc->current_top; | |
92 | nc->current_top = nh; | |
93 | } else { | |
7ee30f28 | 94 | nc->head.nexthop = nc->current_top = nh; |
d62a17ae | 95 | } |
96 | nc->current_recursive = NULL; | |
97 | str_appendf(&nc->repr, "%p\n", nh); | |
fa713d9e CF |
98 | } |
99 | ||
d62a17ae | 100 | static void add_string_representation(char **repr, struct nexthop *nh) |
97c2fb7c | 101 | { |
d62a17ae | 102 | struct nexthop *parent; |
103 | ||
104 | /* add indentations first */ | |
105 | parent = nh->rparent; | |
106 | while (parent) { | |
107 | str_appendf(repr, " "); | |
108 | parent = parent->rparent; | |
109 | } | |
110 | str_appendf(repr, "%p\n", nh); | |
97c2fb7c | 111 | } |
112 | ||
d62a17ae | 113 | static void start_recursive_chain(struct nexthop_chain *nc, struct nexthop *nh) |
97c2fb7c | 114 | { |
d62a17ae | 115 | SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE); |
116 | nc->current_top->resolved = nh; | |
117 | nh->rparent = nc->current_top; | |
118 | nc->current_recursive = nh; | |
97c2fb7c | 119 | } |
d62a17ae | 120 | static void nexthop_chain_add_recursive(struct nexthop_chain *nc) |
fa713d9e | 121 | { |
d62a17ae | 122 | struct nexthop *nh; |
123 | ||
124 | nh = calloc(sizeof(*nh), 1); | |
125 | assert(nh); | |
126 | ||
127 | assert(nc->current_top); | |
128 | if (nc->current_recursive) { | |
129 | nc->current_recursive->next = nh; | |
130 | nh->prev = nc->current_recursive; | |
131 | nh->rparent = nc->current_recursive->rparent; | |
132 | nc->current_recursive = nh; | |
133 | } else | |
134 | start_recursive_chain(nc, nh); | |
135 | ||
136 | add_string_representation(&nc->repr, nh); | |
97c2fb7c | 137 | } |
138 | ||
d62a17ae | 139 | static void nexthop_chain_add_recursive_level(struct nexthop_chain *nc) |
97c2fb7c | 140 | { |
d62a17ae | 141 | struct nexthop *nh; |
142 | ||
143 | nh = calloc(sizeof(*nh), 1); | |
144 | assert(nh); | |
145 | ||
146 | assert(nc->current_top); | |
147 | if (nc->current_recursive) { | |
148 | SET_FLAG(nc->current_recursive->flags, NEXTHOP_FLAG_RECURSIVE); | |
149 | nc->current_recursive->resolved = nh; | |
150 | nh->rparent = nc->current_recursive; | |
151 | nc->current_recursive = nh; | |
152 | } else | |
153 | start_recursive_chain(nc, nh); | |
154 | ||
155 | add_string_representation(&nc->repr, nh); | |
fa713d9e CF |
156 | } |
157 | ||
d62a17ae | 158 | static void nexthop_clear_recursive(struct nexthop *tcur) |
97c2fb7c | 159 | { |
d62a17ae | 160 | if (!tcur) |
161 | return; | |
162 | if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE)) | |
163 | nexthop_clear_recursive(tcur->resolved); | |
164 | if (tcur->next) | |
165 | nexthop_clear_recursive(tcur->next); | |
166 | free(tcur); | |
97c2fb7c | 167 | } |
d62a17ae | 168 | static void nexthop_chain_clear(struct nexthop_chain *nc) |
fa713d9e | 169 | { |
7ee30f28 DS |
170 | nexthop_clear_recursive(nc->head.nexthop); |
171 | nc->head.nexthop = nc->current_top = nc->current_recursive = NULL; | |
d62a17ae | 172 | free(nc->repr); |
173 | nc->repr = NULL; | |
fa713d9e CF |
174 | } |
175 | ||
d62a17ae | 176 | static void nexthop_chain_free(struct nexthop_chain *nc) |
fa713d9e | 177 | { |
d62a17ae | 178 | if (!nc) |
179 | return; | |
180 | nexthop_chain_clear(nc); | |
181 | free(nc); | |
fa713d9e CF |
182 | } |
183 | ||
184 | /* This function builds a string representation of | |
8e688dbd | 185 | * the nexthop chain using the ALL_NEXTHOPS macro. |
186 | * It verifies that the ALL_NEXTHOPS macro iterated | |
fa713d9e CF |
187 | * correctly over the nexthop chain by comparing the |
188 | * generated representation with the expected representation. | |
189 | */ | |
d62a17ae | 190 | static void nexthop_chain_verify_iter(struct nexthop_chain *nc) |
fa713d9e | 191 | { |
d62a17ae | 192 | struct nexthop *nh; |
193 | char *repr = NULL; | |
fa713d9e | 194 | |
d62a17ae | 195 | for (ALL_NEXTHOPS(nc->head, nh)) |
196 | add_string_representation(&repr, nh); | |
fa713d9e | 197 | |
d62a17ae | 198 | if (repr && verbose) |
199 | printf("===\n%s", repr); | |
200 | assert((!repr && !nc->repr) | |
201 | || (repr && nc->repr && !strcmp(repr, nc->repr))); | |
202 | free(repr); | |
fa713d9e CF |
203 | } |
204 | ||
205 | /* This test run builds a simple nexthop chain | |
206 | * with some recursive nexthops and verifies that | |
207 | * the iterator works correctly in each stage along | |
208 | * the way. | |
209 | */ | |
d62a17ae | 210 | static void test_run_first(void) |
fa713d9e | 211 | { |
d62a17ae | 212 | struct nexthop_chain *nc; |
fa713d9e | 213 | |
d62a17ae | 214 | nc = nexthop_chain_new(); |
215 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 216 | |
d62a17ae | 217 | nexthop_chain_add_top(nc); |
218 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 219 | |
d62a17ae | 220 | nexthop_chain_add_top(nc); |
221 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 222 | |
d62a17ae | 223 | nexthop_chain_add_recursive(nc); |
224 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 225 | |
d62a17ae | 226 | nexthop_chain_add_recursive(nc); |
227 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 228 | |
d62a17ae | 229 | nexthop_chain_add_top(nc); |
230 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 231 | |
d62a17ae | 232 | nexthop_chain_add_top(nc); |
233 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 234 | |
d62a17ae | 235 | nexthop_chain_add_top(nc); |
236 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 237 | |
d62a17ae | 238 | nexthop_chain_add_recursive(nc); |
239 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 240 | |
d62a17ae | 241 | nexthop_chain_add_recursive(nc); |
242 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 243 | |
d62a17ae | 244 | nexthop_chain_add_recursive(nc); |
245 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 246 | |
d62a17ae | 247 | nexthop_chain_add_recursive_level(nc); |
248 | nexthop_chain_verify_iter(nc); | |
97c2fb7c | 249 | |
d62a17ae | 250 | nexthop_chain_add_recursive(nc); |
251 | nexthop_chain_verify_iter(nc); | |
97c2fb7c | 252 | |
d62a17ae | 253 | nexthop_chain_add_recursive(nc); |
254 | nexthop_chain_verify_iter(nc); | |
97c2fb7c | 255 | |
d62a17ae | 256 | nexthop_chain_add_top(nc); |
257 | nexthop_chain_verify_iter(nc); | |
97ba3968 | 258 | |
d62a17ae | 259 | nexthop_chain_free(nc); |
fa713d9e CF |
260 | } |
261 | ||
262 | /* This test run builds numerous random | |
263 | * nexthop chain configurations and verifies | |
264 | * that the iterator correctly progresses | |
265 | * through each. */ | |
d62a17ae | 266 | static void test_run_prng(void) |
fa713d9e | 267 | { |
d62a17ae | 268 | struct nexthop_chain *nc; |
269 | struct prng *prng; | |
270 | int i; | |
271 | ||
272 | nc = nexthop_chain_new(); | |
273 | prng = prng_new(0); | |
274 | ||
275 | for (i = 0; i < 1000000; i++) { | |
276 | switch (prng_rand(prng) % 10) { | |
277 | case 0: | |
278 | nexthop_chain_clear(nc); | |
279 | break; | |
280 | case 1: | |
281 | case 2: | |
282 | case 3: | |
283 | case 4: | |
284 | case 5: | |
285 | nexthop_chain_add_top(nc); | |
286 | break; | |
287 | case 6: | |
288 | case 7: | |
289 | case 8: | |
290 | if (nc->current_top) | |
291 | nexthop_chain_add_recursive(nc); | |
292 | break; | |
293 | case 9: | |
294 | if (nc->current_top) | |
295 | nexthop_chain_add_recursive_level(nc); | |
296 | break; | |
297 | } | |
298 | nexthop_chain_verify_iter(nc); | |
299 | } | |
300 | nexthop_chain_free(nc); | |
301 | prng_free(prng); | |
fa713d9e CF |
302 | } |
303 | ||
304 | int main(int argc, char **argv) | |
305 | { | |
d62a17ae | 306 | if (argc >= 2 && !strcmp("-v", argv[1])) |
307 | verbose = 1; | |
308 | test_run_first(); | |
309 | printf("Simple test passed.\n"); | |
310 | test_run_prng(); | |
311 | printf("PRNG test passed.\n"); | |
fa713d9e | 312 | } |