]>
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 | ||
d62a17ae | 44 | static void str_appendf(char **buf, const char *format, ...) |
fa713d9e | 45 | { |
d62a17ae | 46 | va_list ap; |
47 | int rv; | |
48 | char *pbuf; | |
fa713d9e | 49 | |
d62a17ae | 50 | va_start(ap, format); |
51 | rv = vasprintf(&pbuf, format, ap); | |
52 | va_end(ap); | |
53 | assert(rv >= 0); | |
fa713d9e | 54 | |
d62a17ae | 55 | str_append(buf, pbuf); |
56 | free(pbuf); | |
fa713d9e CF |
57 | } |
58 | ||
59 | /* This structure contains a nexthop chain | |
60 | * and its expected representation */ | |
d62a17ae | 61 | struct nexthop_chain { |
62 | /* Head of the chain */ | |
7ee30f28 | 63 | struct nexthop_group head; |
d62a17ae | 64 | /* Last nexthop in top chain */ |
65 | struct nexthop *current_top; | |
66 | /* Last nexthop in current recursive chain */ | |
67 | struct nexthop *current_recursive; | |
68 | /* Expected string representation. */ | |
69 | char *repr; | |
fa713d9e CF |
70 | }; |
71 | ||
d62a17ae | 72 | static struct nexthop_chain *nexthop_chain_new(void) |
fa713d9e | 73 | { |
d62a17ae | 74 | struct nexthop_chain *rv; |
fa713d9e | 75 | |
d62a17ae | 76 | rv = calloc(sizeof(*rv), 1); |
77 | assert(rv); | |
78 | return rv; | |
fa713d9e CF |
79 | } |
80 | ||
d62a17ae | 81 | static void nexthop_chain_add_top(struct nexthop_chain *nc) |
fa713d9e | 82 | { |
d62a17ae | 83 | struct nexthop *nh; |
84 | ||
85 | nh = calloc(sizeof(*nh), 1); | |
86 | assert(nh); | |
87 | ||
7ee30f28 | 88 | if (nc->head.nexthop) { |
d62a17ae | 89 | nc->current_top->next = nh; |
90 | nh->prev = nc->current_top; | |
91 | nc->current_top = nh; | |
92 | } else { | |
7ee30f28 | 93 | nc->head.nexthop = nc->current_top = nh; |
d62a17ae | 94 | } |
95 | nc->current_recursive = NULL; | |
96 | str_appendf(&nc->repr, "%p\n", nh); | |
fa713d9e CF |
97 | } |
98 | ||
d62a17ae | 99 | static void add_string_representation(char **repr, struct nexthop *nh) |
97c2fb7c | 100 | { |
d62a17ae | 101 | struct nexthop *parent; |
102 | ||
103 | /* add indentations first */ | |
104 | parent = nh->rparent; | |
105 | while (parent) { | |
106 | str_appendf(repr, " "); | |
107 | parent = parent->rparent; | |
108 | } | |
109 | str_appendf(repr, "%p\n", nh); | |
97c2fb7c | 110 | } |
111 | ||
d62a17ae | 112 | static void start_recursive_chain(struct nexthop_chain *nc, struct nexthop *nh) |
97c2fb7c | 113 | { |
d62a17ae | 114 | SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE); |
115 | nc->current_top->resolved = nh; | |
116 | nh->rparent = nc->current_top; | |
117 | nc->current_recursive = nh; | |
97c2fb7c | 118 | } |
d62a17ae | 119 | static void nexthop_chain_add_recursive(struct nexthop_chain *nc) |
fa713d9e | 120 | { |
d62a17ae | 121 | struct nexthop *nh; |
122 | ||
123 | nh = calloc(sizeof(*nh), 1); | |
124 | assert(nh); | |
125 | ||
126 | assert(nc->current_top); | |
127 | if (nc->current_recursive) { | |
128 | nc->current_recursive->next = nh; | |
129 | nh->prev = nc->current_recursive; | |
130 | nh->rparent = nc->current_recursive->rparent; | |
131 | nc->current_recursive = nh; | |
132 | } else | |
133 | start_recursive_chain(nc, nh); | |
134 | ||
135 | add_string_representation(&nc->repr, nh); | |
97c2fb7c | 136 | } |
137 | ||
d62a17ae | 138 | static void nexthop_chain_add_recursive_level(struct nexthop_chain *nc) |
97c2fb7c | 139 | { |
d62a17ae | 140 | struct nexthop *nh; |
141 | ||
142 | nh = calloc(sizeof(*nh), 1); | |
143 | assert(nh); | |
144 | ||
145 | assert(nc->current_top); | |
146 | if (nc->current_recursive) { | |
147 | SET_FLAG(nc->current_recursive->flags, NEXTHOP_FLAG_RECURSIVE); | |
148 | nc->current_recursive->resolved = nh; | |
149 | nh->rparent = nc->current_recursive; | |
150 | nc->current_recursive = nh; | |
151 | } else | |
152 | start_recursive_chain(nc, nh); | |
153 | ||
154 | add_string_representation(&nc->repr, nh); | |
fa713d9e CF |
155 | } |
156 | ||
d62a17ae | 157 | static void nexthop_clear_recursive(struct nexthop *tcur) |
97c2fb7c | 158 | { |
d62a17ae | 159 | if (!tcur) |
160 | return; | |
161 | if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE)) | |
162 | nexthop_clear_recursive(tcur->resolved); | |
163 | if (tcur->next) | |
164 | nexthop_clear_recursive(tcur->next); | |
165 | free(tcur); | |
97c2fb7c | 166 | } |
d62a17ae | 167 | static void nexthop_chain_clear(struct nexthop_chain *nc) |
fa713d9e | 168 | { |
7ee30f28 DS |
169 | nexthop_clear_recursive(nc->head.nexthop); |
170 | nc->head.nexthop = nc->current_top = nc->current_recursive = NULL; | |
d62a17ae | 171 | free(nc->repr); |
172 | nc->repr = NULL; | |
fa713d9e CF |
173 | } |
174 | ||
d62a17ae | 175 | static void nexthop_chain_free(struct nexthop_chain *nc) |
fa713d9e | 176 | { |
d62a17ae | 177 | if (!nc) |
178 | return; | |
179 | nexthop_chain_clear(nc); | |
180 | free(nc); | |
fa713d9e CF |
181 | } |
182 | ||
183 | /* This function builds a string representation of | |
8e688dbd | 184 | * the nexthop chain using the ALL_NEXTHOPS macro. |
185 | * It verifies that the ALL_NEXTHOPS macro iterated | |
fa713d9e CF |
186 | * correctly over the nexthop chain by comparing the |
187 | * generated representation with the expected representation. | |
188 | */ | |
d62a17ae | 189 | static void nexthop_chain_verify_iter(struct nexthop_chain *nc) |
fa713d9e | 190 | { |
d62a17ae | 191 | struct nexthop *nh; |
192 | char *repr = NULL; | |
fa713d9e | 193 | |
d62a17ae | 194 | for (ALL_NEXTHOPS(nc->head, nh)) |
195 | add_string_representation(&repr, nh); | |
fa713d9e | 196 | |
d62a17ae | 197 | if (repr && verbose) |
198 | printf("===\n%s", repr); | |
199 | assert((!repr && !nc->repr) | |
200 | || (repr && nc->repr && !strcmp(repr, nc->repr))); | |
201 | free(repr); | |
fa713d9e CF |
202 | } |
203 | ||
204 | /* This test run builds a simple nexthop chain | |
205 | * with some recursive nexthops and verifies that | |
206 | * the iterator works correctly in each stage along | |
207 | * the way. | |
208 | */ | |
d62a17ae | 209 | static void test_run_first(void) |
fa713d9e | 210 | { |
d62a17ae | 211 | struct nexthop_chain *nc; |
fa713d9e | 212 | |
d62a17ae | 213 | nc = nexthop_chain_new(); |
214 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 215 | |
d62a17ae | 216 | nexthop_chain_add_top(nc); |
217 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 218 | |
d62a17ae | 219 | nexthop_chain_add_top(nc); |
220 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 221 | |
d62a17ae | 222 | nexthop_chain_add_recursive(nc); |
223 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 224 | |
d62a17ae | 225 | nexthop_chain_add_recursive(nc); |
226 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 227 | |
d62a17ae | 228 | nexthop_chain_add_top(nc); |
229 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 230 | |
d62a17ae | 231 | nexthop_chain_add_top(nc); |
232 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 233 | |
d62a17ae | 234 | nexthop_chain_add_top(nc); |
235 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 236 | |
d62a17ae | 237 | nexthop_chain_add_recursive(nc); |
238 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 239 | |
d62a17ae | 240 | nexthop_chain_add_recursive(nc); |
241 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 242 | |
d62a17ae | 243 | nexthop_chain_add_recursive(nc); |
244 | nexthop_chain_verify_iter(nc); | |
fa713d9e | 245 | |
d62a17ae | 246 | nexthop_chain_add_recursive_level(nc); |
247 | nexthop_chain_verify_iter(nc); | |
97c2fb7c | 248 | |
d62a17ae | 249 | nexthop_chain_add_recursive(nc); |
250 | nexthop_chain_verify_iter(nc); | |
97c2fb7c | 251 | |
d62a17ae | 252 | nexthop_chain_add_recursive(nc); |
253 | nexthop_chain_verify_iter(nc); | |
97c2fb7c | 254 | |
d62a17ae | 255 | nexthop_chain_add_top(nc); |
256 | nexthop_chain_verify_iter(nc); | |
97ba3968 | 257 | |
d62a17ae | 258 | nexthop_chain_free(nc); |
fa713d9e CF |
259 | } |
260 | ||
261 | /* This test run builds numerous random | |
262 | * nexthop chain configurations and verifies | |
263 | * that the iterator correctly progresses | |
264 | * through each. */ | |
d62a17ae | 265 | static void test_run_prng(void) |
fa713d9e | 266 | { |
d62a17ae | 267 | struct nexthop_chain *nc; |
268 | struct prng *prng; | |
269 | int i; | |
270 | ||
271 | nc = nexthop_chain_new(); | |
272 | prng = prng_new(0); | |
273 | ||
274 | for (i = 0; i < 1000000; i++) { | |
275 | switch (prng_rand(prng) % 10) { | |
276 | case 0: | |
277 | nexthop_chain_clear(nc); | |
278 | break; | |
279 | case 1: | |
280 | case 2: | |
281 | case 3: | |
282 | case 4: | |
283 | case 5: | |
284 | nexthop_chain_add_top(nc); | |
285 | break; | |
286 | case 6: | |
287 | case 7: | |
288 | case 8: | |
289 | if (nc->current_top) | |
290 | nexthop_chain_add_recursive(nc); | |
291 | break; | |
292 | case 9: | |
293 | if (nc->current_top) | |
294 | nexthop_chain_add_recursive_level(nc); | |
295 | break; | |
296 | } | |
297 | nexthop_chain_verify_iter(nc); | |
298 | } | |
299 | nexthop_chain_free(nc); | |
300 | prng_free(prng); | |
fa713d9e CF |
301 | } |
302 | ||
303 | int main(int argc, char **argv) | |
304 | { | |
d62a17ae | 305 | if (argc >= 2 && !strcmp("-v", argv[1])) |
306 | verbose = 1; | |
307 | test_run_first(); | |
308 | printf("Simple test passed.\n"); | |
309 | test_run_prng(); | |
310 | printf("PRNG test passed.\n"); | |
fa713d9e | 311 | } |