tests/lib/test_nexthop_iter.c

   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 str_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
  49 static void
  50 str_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 */
  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 nexthop_chain_new(void)
  81 {
  82   struct nexthop_chain *rv;
  83
  84   rv = calloc(sizeof(*rv), 1);
  85   assert(rv);
  86   return rv;
  87 }
  88
  89 static void
  90 nexthop_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
 111 static void
 112 nexthop_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
 135 static void
 136 nexthop_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
 159 static void
 160 nexthop_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  */
 174 static void
 175 nexthop_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  */
 200 static void
 201 test_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. */
 245 static void
 246 test_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
 283 int 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 }