1 /*
2 * Recursive Nexthop Iterator test.
3 * This tests the ALL_NEXTHOPS macro.
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 *
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
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
str_append(char ** buf,const char * repr)32 static void str_append(char **buf, const char *repr)
33 {
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 }
42 }
43
str_appendf(char ** buf,const char * format,...)44 static void str_appendf(char **buf, const char *format, ...)
45 {
46 va_list ap;
47 int rv;
48 char *pbuf;
49
50 va_start(ap, format);
51 rv = vasprintf(&pbuf, format, ap);
52 va_end(ap);
53 assert(rv >= 0);
54
55 str_append(buf, pbuf);
56 free(pbuf);
57 }
58
59 /* This structure contains a nexthop chain
60 * and its expected representation */
61 struct nexthop_chain {
62 /* Head of the chain */
63 struct nexthop_group head;
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;
70 };
71
nexthop_chain_new(void)72 static struct nexthop_chain *nexthop_chain_new(void)
73 {
74 struct nexthop_chain *rv;
75
76 rv = calloc(sizeof(*rv), 1);
77 assert(rv);
78 return rv;
79 }
80
nexthop_chain_add_top(struct nexthop_chain * nc)81 static void nexthop_chain_add_top(struct nexthop_chain *nc)
82 {
83 struct nexthop *nh;
84
85 nh = calloc(sizeof(*nh), 1);
86 assert(nh);
87
88 if (nc->head.nexthop) {
89 nc->current_top->next = nh;
90 nh->prev = nc->current_top;
91 nc->current_top = nh;
92 } else {
93 nc->head.nexthop = nc->current_top = nh;
94 }
95 nc->current_recursive = NULL;
96 str_appendf(&nc->repr, "%p\n", nh);
97 }
98
add_string_representation(char ** repr,struct nexthop * nh)99 static void add_string_representation(char **repr, struct nexthop *nh)
100 {
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);
110 }
111
start_recursive_chain(struct nexthop_chain * nc,struct nexthop * nh)112 static void start_recursive_chain(struct nexthop_chain *nc, struct nexthop *nh)
113 {
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;
118 }
nexthop_chain_add_recursive(struct nexthop_chain * nc)119 static void nexthop_chain_add_recursive(struct nexthop_chain *nc)
120 {
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);
136 }
137
nexthop_chain_add_recursive_level(struct nexthop_chain * nc)138 static void nexthop_chain_add_recursive_level(struct nexthop_chain *nc)
139 {
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);
155 }
156
nexthop_clear_recursive(struct nexthop * tcur)157 static void nexthop_clear_recursive(struct nexthop *tcur)
158 {
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);
166 }
nexthop_chain_clear(struct nexthop_chain * nc)167 static void nexthop_chain_clear(struct nexthop_chain *nc)
168 {
169 nexthop_clear_recursive(nc->head.nexthop);
170 nc->head.nexthop = nc->current_top = nc->current_recursive = NULL;
171 free(nc->repr);
172 nc->repr = NULL;
173 }
174
nexthop_chain_free(struct nexthop_chain * nc)175 static void nexthop_chain_free(struct nexthop_chain *nc)
176 {
177 if (!nc)
178 return;
179 nexthop_chain_clear(nc);
180 free(nc);
181 }
182
183 /* This function builds a string representation of
184 * the nexthop chain using the ALL_NEXTHOPS macro.
185 * It verifies that the ALL_NEXTHOPS macro iterated
186 * correctly over the nexthop chain by comparing the
187 * generated representation with the expected representation.
188 */
nexthop_chain_verify_iter(struct nexthop_chain * nc)189 static void nexthop_chain_verify_iter(struct nexthop_chain *nc)
190 {
191 struct nexthop *nh;
192 char *repr = NULL;
193
194 for (ALL_NEXTHOPS(nc->head, nh))
195 add_string_representation(&repr, nh);
196
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);
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 */
test_run_first(void)209 static void test_run_first(void)
210 {
211 struct nexthop_chain *nc;
212
213 nc = nexthop_chain_new();
214 nexthop_chain_verify_iter(nc);
215
216 nexthop_chain_add_top(nc);
217 nexthop_chain_verify_iter(nc);
218
219 nexthop_chain_add_top(nc);
220 nexthop_chain_verify_iter(nc);
221
222 nexthop_chain_add_recursive(nc);
223 nexthop_chain_verify_iter(nc);
224
225 nexthop_chain_add_recursive(nc);
226 nexthop_chain_verify_iter(nc);
227
228 nexthop_chain_add_top(nc);
229 nexthop_chain_verify_iter(nc);
230
231 nexthop_chain_add_top(nc);
232 nexthop_chain_verify_iter(nc);
233
234 nexthop_chain_add_top(nc);
235 nexthop_chain_verify_iter(nc);
236
237 nexthop_chain_add_recursive(nc);
238 nexthop_chain_verify_iter(nc);
239
240 nexthop_chain_add_recursive(nc);
241 nexthop_chain_verify_iter(nc);
242
243 nexthop_chain_add_recursive(nc);
244 nexthop_chain_verify_iter(nc);
245
246 nexthop_chain_add_recursive_level(nc);
247 nexthop_chain_verify_iter(nc);
248
249 nexthop_chain_add_recursive(nc);
250 nexthop_chain_verify_iter(nc);
251
252 nexthop_chain_add_recursive(nc);
253 nexthop_chain_verify_iter(nc);
254
255 nexthop_chain_add_top(nc);
256 nexthop_chain_verify_iter(nc);
257
258 nexthop_chain_free(nc);
259 }
260
261 /* This test run builds numerous random
262 * nexthop chain configurations and verifies
263 * that the iterator correctly progresses
264 * through each. */
test_run_prng(void)265 static void test_run_prng(void)
266 {
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);
301 }
302
main(int argc,char ** argv)303 int main(int argc, char **argv)
304 {
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");
311 }
312