Line data Source code
1 : /*
2 : * Recursive Nexthop Iterator test.
3 : * This tests the ALL_NEXTHOPS_RO 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
21 : * along with Quagga; see the file COPYING. If not, write to the Free
22 : * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
23 : * 02111-1307, USA.
24 : */
25 :
26 : #include <zebra.h>
27 : #include "zebra/rib.h"
28 : #include "prng.h"
29 :
30 : struct thread_master *master;
31 : static int verbose;
32 :
33 : static void
34 8723566 : str_append(char **buf, const char *repr)
35 : {
36 8723566 : if (*buf)
37 : {
38 7800270 : *buf = realloc(*buf, strlen(*buf) + strlen(repr) + 1);
39 7800270 : assert(*buf);
40 7800270 : strncpy((*buf) + strlen(*buf), repr, strlen(repr) + 1);
41 : }
42 : else
43 : {
44 923296 : *buf = strdup(repr);
45 923296 : assert(*buf);
46 : }
47 8723566 : }
48 :
49 : static void
50 8723566 : str_appendf(char **buf, const char *format, ...)
51 : {
52 : va_list ap;
53 : int rv;
54 : char *pbuf;
55 :
56 8723566 : va_start(ap, format);
57 8723566 : rv = vasprintf(&pbuf, format, ap);
58 8723566 : va_end(ap);
59 8723566 : assert(rv >= 0);
60 :
61 8723566 : str_append(buf, pbuf);
62 8723566 : free(pbuf);
63 8723566 : }
64 :
65 : /* This structure contains a nexthop chain
66 : * and its expected representation */
67 : struct nexthop_chain
68 : {
69 : /* Head of the chain */
70 : struct nexthop *head;
71 : /* Last nexthop in top chain */
72 : struct nexthop *current_top;
73 : /* Last nexthop in current recursive chain */
74 : struct nexthop *current_recursive;
75 : /* Expected string representation. */
76 : char *repr;
77 : };
78 :
79 : static struct nexthop_chain*
80 2 : nexthop_chain_new(void)
81 : {
82 : struct nexthop_chain *rv;
83 :
84 2 : rv = calloc(sizeof(*rv), 1);
85 2 : assert(rv);
86 2 : return rv;
87 : }
88 :
89 : static void
90 500075 : nexthop_chain_add_top(struct nexthop_chain *nc)
91 : {
92 : struct nexthop *nh;
93 :
94 500075 : nh = calloc(sizeof(*nh), 1);
95 500075 : assert(nh);
96 :
97 500075 : if (nc->head)
98 : {
99 409661 : nc->current_top->next = nh;
100 409661 : nh->prev = nc->current_top;
101 409661 : nc->current_top = nh;
102 : }
103 : else
104 : {
105 90414 : nc->head = nc->current_top = nh;
106 : }
107 500075 : nc->current_recursive = NULL;
108 500075 : str_appendf(&nc->repr, "%p\n", nh);
109 500075 : }
110 :
111 : static void
112 332807 : nexthop_chain_add_recursive(struct nexthop_chain *nc)
113 : {
114 : struct nexthop *nh;
115 :
116 332807 : nh = calloc(sizeof(*nh), 1);
117 332807 : assert(nh);
118 :
119 332807 : assert(nc->current_top);
120 332807 : if (nc->current_recursive)
121 : {
122 132776 : nc->current_recursive->next = nh;
123 132776 : nh->prev = nc->current_recursive;
124 132776 : nc->current_recursive = nh;
125 : }
126 : else
127 : {
128 200031 : SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE);
129 200031 : nc->current_top->resolved = nh;
130 200031 : nc->current_recursive = nh;
131 : }
132 332807 : str_appendf(&nc->repr, " %p\n", nh);
133 332807 : }
134 :
135 : static void
136 100098 : nexthop_chain_clear(struct nexthop_chain *nc)
137 : {
138 : struct nexthop *tcur, *tnext;
139 :
140 600173 : for (tcur = nc->head; tcur; tcur = tnext)
141 : {
142 500075 : tnext = tcur->next;
143 500075 : if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE))
144 : {
145 : struct nexthop *rcur, *rnext;
146 532838 : for (rcur = tcur->resolved; rcur; rcur = rnext)
147 : {
148 332807 : rnext = rcur->next;
149 332807 : free(rcur);
150 : }
151 : }
152 500075 : free(tcur);
153 : }
154 100098 : nc->head = nc->current_top = nc->current_recursive = NULL;
155 100098 : free(nc->repr);
156 100098 : nc->repr = NULL;
157 100098 : }
158 :
159 : static void
160 2 : nexthop_chain_free(struct nexthop_chain *nc)
161 : {
162 2 : if (!nc)
163 0 : return;
164 2 : nexthop_chain_clear(nc);
165 2 : free(nc);
166 : }
167 :
168 : /* This function builds a string representation of
169 : * the nexthop chain using the ALL_NEXTHOPS_RO macro.
170 : * It verifies that the ALL_NEXTHOPS_RO macro iterated
171 : * correctly over the nexthop chain by comparing the
172 : * generated representation with the expected representation.
173 : */
174 : static void
175 1000011 : nexthop_chain_verify_iter(struct nexthop_chain *nc)
176 : {
177 : struct nexthop *nh, *tnh;
178 : int recursing;
179 1000011 : char *repr = NULL;
180 :
181 8890695 : for (ALL_NEXTHOPS_RO(nc->head, nh, tnh, recursing))
182 : {
183 7890684 : if (recursing)
184 3176494 : str_appendf(&repr, " %p\n", nh);
185 : else
186 4714190 : str_appendf(&repr, "%p\n", nh);
187 : }
188 :
189 1000011 : if (repr && verbose)
190 0 : printf("===\n%s", repr);
191 1000011 : assert((!repr && !nc->repr) || (repr && nc->repr && !strcmp(repr, nc->repr)));
192 1000011 : free(repr);
193 1000011 : }
194 :
195 : /* This test run builds a simple nexthop chain
196 : * with some recursive nexthops and verifies that
197 : * the iterator works correctly in each stage along
198 : * the way.
199 : */
200 : static void
201 1 : test_run_first(void)
202 : {
203 : struct nexthop_chain *nc;
204 :
205 1 : nc = nexthop_chain_new();
206 1 : nexthop_chain_verify_iter(nc);
207 :
208 1 : nexthop_chain_add_top(nc);
209 1 : nexthop_chain_verify_iter(nc);
210 :
211 1 : nexthop_chain_add_top(nc);
212 1 : nexthop_chain_verify_iter(nc);
213 :
214 1 : nexthop_chain_add_recursive(nc);
215 1 : nexthop_chain_verify_iter(nc);
216 :
217 1 : nexthop_chain_add_recursive(nc);
218 1 : nexthop_chain_verify_iter(nc);
219 :
220 1 : nexthop_chain_add_top(nc);
221 1 : nexthop_chain_verify_iter(nc);
222 :
223 1 : nexthop_chain_add_top(nc);
224 1 : nexthop_chain_verify_iter(nc);
225 :
226 1 : nexthop_chain_add_top(nc);
227 1 : nexthop_chain_verify_iter(nc);
228 :
229 1 : nexthop_chain_add_recursive(nc);
230 1 : nexthop_chain_verify_iter(nc);
231 :
232 1 : nexthop_chain_add_recursive(nc);
233 1 : nexthop_chain_verify_iter(nc);
234 :
235 1 : nexthop_chain_add_recursive(nc);
236 1 : nexthop_chain_verify_iter(nc);
237 :
238 1 : nexthop_chain_free(nc);
239 1 : }
240 :
241 : /* This test run builds numerous random
242 : * nexthop chain configurations and verifies
243 : * that the iterator correctly progresses
244 : * through each. */
245 : static void
246 1 : test_run_prng(void)
247 : {
248 : struct nexthop_chain *nc;
249 : struct prng *prng;
250 : int i;
251 :
252 1 : nc = nexthop_chain_new();
253 1 : prng = prng_new(0);
254 :
255 1000001 : for (i = 0; i < 1000000; i++)
256 : {
257 1000000 : switch (prng_rand(prng) % 10)
258 : {
259 : case 0:
260 100096 : nexthop_chain_clear(nc);
261 100096 : break;
262 : case 1:
263 : case 2:
264 : case 3:
265 : case 4:
266 : case 5:
267 500070 : nexthop_chain_add_top(nc);
268 500070 : break;
269 : case 6:
270 : case 7:
271 : case 8:
272 : case 9:
273 399834 : if (nc->current_top)
274 332802 : nexthop_chain_add_recursive(nc);
275 399834 : break;
276 : }
277 1000000 : nexthop_chain_verify_iter(nc);
278 : }
279 1 : nexthop_chain_free(nc);
280 1 : prng_free(prng);
281 1 : }
282 :
283 1 : int main(int argc, char **argv)
284 : {
285 1 : if (argc >= 2 && !strcmp("-v", argv[1]))
286 0 : verbose = 1;
287 1 : test_run_first();
288 1 : printf("Simple test passed.\n");
289 1 : test_run_prng();
290 1 : printf("PRNG test passed.\n");
291 : }
|
