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 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
  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
  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
  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
  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
 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 }
 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
 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
 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 }
 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
 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  */
 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  */
 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. */
 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
 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 }