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