tests/lib/test_nexthop_iter.c

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