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
30struct thread_master *master;
31static int verbose;
32
33static void
34str_append(char **buf, const char *repr)
35{
36  if (*buf)
37    {
38      *buf = realloc(*buf, strlen(*buf) + strlen(repr) + 1);
39      assert(*buf);
40      strncpy((*buf) + strlen(*buf), repr, strlen(repr) + 1);
41    }
42  else
43    {
44      *buf = strdup(repr);
45      assert(*buf);
46    }
47}
48
49static void
50str_appendf(char **buf, const char *format, ...)
51{
52  va_list ap;
53  int rv;
54  char *pbuf;
55
56  va_start(ap, format);
57  rv = vasprintf(&pbuf, format, ap);
58  va_end(ap);
59  assert(rv >= 0);
60
61  str_append(buf, pbuf);
62  free(pbuf);
63}
64
65/* This structure contains a nexthop chain
66 * and its expected representation */
67struct 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
79static struct nexthop_chain*
80nexthop_chain_new(void)
81{
82  struct nexthop_chain *rv;
83
84  rv = calloc(sizeof(*rv), 1);
85  assert(rv);
86  return rv;
87}
88
89static void
90nexthop_chain_add_top(struct nexthop_chain *nc)
91{
92  struct nexthop *nh;
93
94  nh = calloc(sizeof(*nh), 1);
95  assert(nh);
96
97  if (nc->head)
98    {
99      nc->current_top->next = nh;
100      nh->prev = nc->current_top;
101      nc->current_top = nh;
102    }
103  else
104    {
105      nc->head = nc->current_top = nh;
106    }
107  nc->current_recursive = NULL;
108  str_appendf(&nc->repr, "%p\n", nh);
109}
110
111static void
112nexthop_chain_add_recursive(struct nexthop_chain *nc)
113{
114  struct nexthop *nh;
115
116  nh = calloc(sizeof(*nh), 1);
117  assert(nh);
118
119  assert(nc->current_top);
120  if (nc->current_recursive)
121    {
122      nc->current_recursive->next = nh;
123      nh->prev = nc->current_recursive;
124      nc->current_recursive = nh;
125    }
126  else
127    {
128      SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE);
129      nc->current_top->resolved = nh;
130      nc->current_recursive = nh;
131    }
132  str_appendf(&nc->repr, "  %p\n", nh);
133}
134
135static void
136nexthop_chain_clear(struct nexthop_chain *nc)
137{
138  struct nexthop *tcur, *tnext;
139
140  for (tcur = nc->head; tcur; tcur = tnext)
141    {
142      tnext = tcur->next;
143      if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE))
144        {
145          struct nexthop *rcur, *rnext;
146          for (rcur = tcur->resolved; rcur; rcur = rnext)
147            {
148              rnext = rcur->next;
149              free(rcur);
150            }
151        }
152      free(tcur);
153    }
154  nc->head = nc->current_top = nc->current_recursive = NULL;
155  free(nc->repr);
156  nc->repr = NULL;
157}
158
159static void
160nexthop_chain_free(struct nexthop_chain *nc)
161{
162  if (!nc)
163    return;
164  nexthop_chain_clear(nc);
165  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 */
174static void
175nexthop_chain_verify_iter(struct nexthop_chain *nc)
176{
177  struct nexthop *nh, *tnh;
178  int recursing;
179  char *repr = NULL;
180
181  for (ALL_NEXTHOPS_RO(nc->head, nh, tnh, recursing))
182    {
183      if (recursing)
184        str_appendf(&repr, "  %p\n", nh);
185      else
186        str_appendf(&repr, "%p\n", nh);
187    }
188
189  if (repr && verbose)
190    printf("===\n%s", repr);
191  assert((!repr && !nc->repr) || (repr && nc->repr && !strcmp(repr, nc->repr)));
192  free(repr);
193}
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 */
200static void
201test_run_first(void)
202{
203  struct nexthop_chain *nc;
204
205  nc = nexthop_chain_new();
206  nexthop_chain_verify_iter(nc);
207
208  nexthop_chain_add_top(nc);
209  nexthop_chain_verify_iter(nc);
210
211  nexthop_chain_add_top(nc);
212  nexthop_chain_verify_iter(nc);
213
214  nexthop_chain_add_recursive(nc);
215  nexthop_chain_verify_iter(nc);
216
217  nexthop_chain_add_recursive(nc);
218  nexthop_chain_verify_iter(nc);
219
220  nexthop_chain_add_top(nc);
221  nexthop_chain_verify_iter(nc);
222
223  nexthop_chain_add_top(nc);
224  nexthop_chain_verify_iter(nc);
225
226  nexthop_chain_add_top(nc);
227  nexthop_chain_verify_iter(nc);
228
229  nexthop_chain_add_recursive(nc);
230  nexthop_chain_verify_iter(nc);
231
232  nexthop_chain_add_recursive(nc);
233  nexthop_chain_verify_iter(nc);
234
235  nexthop_chain_add_recursive(nc);
236  nexthop_chain_verify_iter(nc);
237
238  nexthop_chain_free(nc);
239}
240
241/* This test run builds numerous random
242 * nexthop chain configurations and verifies
243 * that the iterator correctly progresses
244 * through each. */
245static void
246test_run_prng(void)
247{
248  struct nexthop_chain *nc;
249  struct prng *prng;
250  int i;
251
252  nc = nexthop_chain_new();
253  prng = prng_new(0);
254
255  for (i = 0; i < 1000000; i++)
256    {
257      switch (prng_rand(prng) % 10)
258        {
259        case 0:
260          nexthop_chain_clear(nc);
261          break;
262        case 1:
263        case 2:
264        case 3:
265        case 4:
266        case 5:
267          nexthop_chain_add_top(nc);
268          break;
269        case 6:
270        case 7:
271        case 8:
272        case 9:
273          if (nc->current_top)
274            nexthop_chain_add_recursive(nc);
275          break;
276        }
277      nexthop_chain_verify_iter(nc);
278    }
279  nexthop_chain_free(nc);
280  prng_free(prng);
281}
282
283int main(int argc, char **argv)
284{
285  if (argc >= 2 && !strcmp("-v", argv[1]))
286    verbose = 1;
287  test_run_first();
288  printf("Simple test passed.\n");
289  test_run_prng();
290  printf("PRNG test passed.\n");
291}
292