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 str_append(char **buf, const char *repr)
  34 {
  35         if (*buf) {
  36                 *buf = realloc(*buf, strlen(*buf) + strlen(repr) + 1);
  37                 assert(*buf);
  38                 strncpy((*buf) + strlen(*buf), repr, strlen(repr) + 1);
  39         } else {
  40                 *buf = strdup(repr);
  41                 assert(*buf);
  42         }
  43 }
  44
  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 *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) {
  90                 nc->current_top->next = nh;
  91                 nh->prev = nc->current_top;
  92                 nc->current_top = nh;
  93         } else {
  94                 nc->head = nc->current_top = nh;
  95         }
  96         nc->current_recursive = NULL;
  97         str_appendf(&nc->repr, "%p\n", nh);
  98 }
  99
 100 static void nexthop_chain_add_recursive(struct nexthop_chain *nc)
 101 {
 102         struct nexthop *nh;
 103
 104         nh = calloc(sizeof(*nh), 1);
 105         assert(nh);
 106
 107         assert(nc->current_top);
 108         if (nc->current_recursive) {
 109                 nc->current_recursive->next = nh;
 110                 nh->prev = nc->current_recursive;
 111                 nc->current_recursive = nh;
 112         } else {
 113                 SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE);
 114                 nc->current_top->resolved = nh;
 115                 nc->current_recursive = nh;
 116         }
 117         str_appendf(&nc->repr, "  %p\n", nh);
 118 }
 119
 120 static void nexthop_chain_clear(struct nexthop_chain *nc)
 121 {
 122         struct nexthop *tcur, *tnext;
 123
 124         for (tcur = nc->head; tcur; tcur = tnext) {
 125                 tnext = tcur->next;
 126                 if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE)) {
 127                         struct nexthop *rcur, *rnext;
 128                         for (rcur = tcur->resolved; rcur; rcur = rnext) {
 129                                 rnext = rcur->next;
 130                                 free(rcur);
 131                         }
 132                 }
 133                 free(tcur);
 134         }
 135         nc->head = nc->current_top = nc->current_recursive = NULL;
 136         free(nc->repr);
 137         nc->repr = NULL;
 138 }
 139
 140 static void nexthop_chain_free(struct nexthop_chain *nc)
 141 {
 142         if (!nc)
 143                 return;
 144         nexthop_chain_clear(nc);
 145         free(nc);
 146 }
 147
 148 /* This function builds a string representation of
 149  * the nexthop chain using the ALL_NEXTHOPS_RO macro.
 150  * It verifies that the ALL_NEXTHOPS_RO macro iterated
 151  * correctly over the nexthop chain by comparing the
 152  * generated representation with the expected representation.
 153  */
 154 static void nexthop_chain_verify_iter(struct nexthop_chain *nc)
 155 {
 156         struct nexthop *nh, *tnh;
 157         int recursing;
 158         char *repr = NULL;
 159
 160         for (ALL_NEXTHOPS_RO(nc->head, nh, tnh, recursing)) {
 161                 if (recursing)
 162                         str_appendf(&repr, "  %p\n", nh);
 163                 else
 164                         str_appendf(&repr, "%p\n", nh);
 165         }
 166
 167         if (repr && verbose)
 168                 printf("===\n%s", repr);
 169         assert((!repr && !nc->repr)
 170                || (repr && nc->repr && !strcmp(repr, nc->repr)));
 171         free(repr);
 172 }
 173
 174 /* This test run builds a simple nexthop chain
 175  * with some recursive nexthops and verifies that
 176  * the iterator works correctly in each stage along
 177  * the way.
 178  */
 179 static void test_run_first(void)
 180 {
 181         struct nexthop_chain *nc;
 182
 183         nc = nexthop_chain_new();
 184         nexthop_chain_verify_iter(nc);
 185
 186         nexthop_chain_add_top(nc);
 187         nexthop_chain_verify_iter(nc);
 188
 189         nexthop_chain_add_top(nc);
 190         nexthop_chain_verify_iter(nc);
 191
 192         nexthop_chain_add_recursive(nc);
 193         nexthop_chain_verify_iter(nc);
 194
 195         nexthop_chain_add_recursive(nc);
 196         nexthop_chain_verify_iter(nc);
 197
 198         nexthop_chain_add_top(nc);
 199         nexthop_chain_verify_iter(nc);
 200
 201         nexthop_chain_add_top(nc);
 202         nexthop_chain_verify_iter(nc);
 203
 204         nexthop_chain_add_top(nc);
 205         nexthop_chain_verify_iter(nc);
 206
 207         nexthop_chain_add_recursive(nc);
 208         nexthop_chain_verify_iter(nc);
 209
 210         nexthop_chain_add_recursive(nc);
 211         nexthop_chain_verify_iter(nc);
 212
 213         nexthop_chain_add_recursive(nc);
 214         nexthop_chain_verify_iter(nc);
 215
 216         nexthop_chain_free(nc);
 217 }
 218
 219 /* This test run builds numerous random
 220  * nexthop chain configurations and verifies
 221  * that the iterator correctly progresses
 222  * through each. */
 223 static void test_run_prng(void)
 224 {
 225         struct nexthop_chain *nc;
 226         struct prng *prng;
 227         int i;
 228
 229         nc = nexthop_chain_new();
 230         prng = prng_new(0);
 231
 232         for (i = 0; i < 1000000; i++) {
 233                 switch (prng_rand(prng) % 10) {
 234                 case 0:
 235                         nexthop_chain_clear(nc);
 236                         break;
 237                 case 1:
 238                 case 2:
 239                 case 3:
 240                 case 4:
 241                 case 5:
 242                         nexthop_chain_add_top(nc);
 243                         break;
 244                 case 6:
 245                 case 7:
 246                 case 8:
 247                 case 9:
 248                         if (nc->current_top)
 249                                 nexthop_chain_add_recursive(nc);
 250                         break;
 251                 }
 252                 nexthop_chain_verify_iter(nc);
 253         }
 254         nexthop_chain_free(nc);
 255         prng_free(prng);
 256 }
 257
 258 int main(int argc, char **argv)
 259 {
 260         if (argc >= 2 && !strcmp("-v", argv[1]))
 261                 verbose = 1;
 262         test_run_first();
 263         printf("Simple test passed.\n");
 264         test_run_prng();
 265         printf("PRNG test passed.\n");
 266 }