tests/lib/test_nexthop_iter.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Recursive Nexthop Iterator test.
   4  * This tests the ALL_NEXTHOPS macro.
   5  *
   6  * Copyright (C) 2012 by Open Source Routing.
   7  * Copyright (C) 2012 by Internet Systems Consortium, Inc. ("ISC")
   8  *
   9  * This file is part of Quagga
  10  */
  11
  12 #include <zebra.h>
  13 #include "zebra/rib.h"
  14 #include "prng.h"
  15
  16 struct thread_master *master;
  17 static int verbose;
  18
  19 static void str_append(char **buf, const char *repr)
  20 {
  21         if (*buf) {
  22                 *buf = realloc(*buf, strlen(*buf) + strlen(repr) + 1);
  23                 assert(*buf);
  24                 strncpy((*buf) + strlen(*buf), repr, strlen(repr) + 1);
  25         } else {
  26                 *buf = strdup(repr);
  27                 assert(*buf);
  28         }
  29 }
  30
  31 PRINTFRR(2, 3)
  32 static void str_appendf(char **buf, const char *format, ...)
  33 {
  34         va_list ap;
  35         int rv;
  36         char *pbuf;
  37
  38         va_start(ap, format);
  39         rv = vasprintf(&pbuf, format, ap);
  40         va_end(ap);
  41         assert(rv >= 0);
  42
  43         str_append(buf, pbuf);
  44         free(pbuf);
  45 }
  46
  47 /* This structure contains a nexthop chain
  48  * and its expected representation */
  49 struct nexthop_chain {
  50         /* Head of the chain */
  51         struct nexthop_group head;
  52         /* Last nexthop in top chain */
  53         struct nexthop *current_top;
  54         /* Last nexthop in current recursive chain */
  55         struct nexthop *current_recursive;
  56         /* Expected string representation. */
  57         char *repr;
  58 };
  59
  60 static struct nexthop_chain *nexthop_chain_new(void)
  61 {
  62         struct nexthop_chain *rv;
  63
  64         rv = calloc(sizeof(*rv), 1);
  65         assert(rv);
  66         return rv;
  67 }
  68
  69 static void nexthop_chain_add_top(struct nexthop_chain *nc)
  70 {
  71         struct nexthop *nh;
  72
  73         nh = calloc(sizeof(*nh), 1);
  74         assert(nh);
  75
  76         if (nc->head.nexthop) {
  77                 nc->current_top->next = nh;
  78                 nh->prev = nc->current_top;
  79                 nc->current_top = nh;
  80         } else {
  81                 nc->head.nexthop = nc->current_top = nh;
  82         }
  83         nc->current_recursive = NULL;
  84         str_appendf(&nc->repr, "%p\n", nh);
  85 }
  86
  87 static void add_string_representation(char **repr, struct nexthop *nh)
  88 {
  89         struct nexthop *parent;
  90
  91         /* add indentations first */
  92         parent = nh->rparent;
  93         while (parent) {
  94                 str_appendf(repr, "  ");
  95                 parent = parent->rparent;
  96         }
  97         str_appendf(repr, "%p\n", nh);
  98 }
  99
 100 static void start_recursive_chain(struct nexthop_chain *nc, struct nexthop *nh)
 101 {
 102         SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE);
 103         nc->current_top->resolved = nh;
 104         nh->rparent = nc->current_top;
 105         nc->current_recursive = nh;
 106 }
 107 static void nexthop_chain_add_recursive(struct nexthop_chain *nc)
 108 {
 109         struct nexthop *nh;
 110
 111         nh = calloc(sizeof(*nh), 1);
 112         assert(nh);
 113
 114         assert(nc->current_top);
 115         if (nc->current_recursive) {
 116                 nc->current_recursive->next = nh;
 117                 nh->prev = nc->current_recursive;
 118                 nh->rparent = nc->current_recursive->rparent;
 119                 nc->current_recursive = nh;
 120         } else
 121                 start_recursive_chain(nc, nh);
 122
 123         add_string_representation(&nc->repr, nh);
 124 }
 125
 126 static void nexthop_chain_add_recursive_level(struct nexthop_chain *nc)
 127 {
 128         struct nexthop *nh;
 129
 130         nh = calloc(sizeof(*nh), 1);
 131         assert(nh);
 132
 133         assert(nc->current_top);
 134         if (nc->current_recursive) {
 135                 SET_FLAG(nc->current_recursive->flags, NEXTHOP_FLAG_RECURSIVE);
 136                 nc->current_recursive->resolved = nh;
 137                 nh->rparent = nc->current_recursive;
 138                 nc->current_recursive = nh;
 139         } else
 140                 start_recursive_chain(nc, nh);
 141
 142         add_string_representation(&nc->repr, nh);
 143 }
 144
 145 static void nexthop_clear_recursive(struct nexthop *tcur)
 146 {
 147         if (!tcur)
 148                 return;
 149         if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE))
 150                 nexthop_clear_recursive(tcur->resolved);
 151         if (tcur->next)
 152                 nexthop_clear_recursive(tcur->next);
 153         free(tcur);
 154 }
 155 static void nexthop_chain_clear(struct nexthop_chain *nc)
 156 {
 157         nexthop_clear_recursive(nc->head.nexthop);
 158         nc->head.nexthop = nc->current_top = nc->current_recursive = NULL;
 159         free(nc->repr);
 160         nc->repr = NULL;
 161 }
 162
 163 static void nexthop_chain_free(struct nexthop_chain *nc)
 164 {
 165         if (!nc)
 166                 return;
 167         nexthop_chain_clear(nc);
 168         free(nc);
 169 }
 170
 171 /* This function builds a string representation of
 172  * the nexthop chain using the ALL_NEXTHOPS macro.
 173  * It verifies that the ALL_NEXTHOPS macro iterated
 174  * correctly over the nexthop chain by comparing the
 175  * generated representation with the expected representation.
 176  */
 177 static void nexthop_chain_verify_iter(struct nexthop_chain *nc)
 178 {
 179         struct nexthop *nh;
 180         char *repr = NULL;
 181
 182         for (ALL_NEXTHOPS(nc->head, nh))
 183                 add_string_representation(&repr, nh);
 184
 185         if (repr && verbose)
 186                 printf("===\n%s", repr);
 187         assert((!repr && !nc->repr)
 188                || (repr && nc->repr && !strcmp(repr, nc->repr)));
 189         free(repr);
 190 }
 191
 192 /* This test run builds a simple nexthop chain
 193  * with some recursive nexthops and verifies that
 194  * the iterator works correctly in each stage along
 195  * the way.
 196  */
 197 static void test_run_first(void)
 198 {
 199         struct nexthop_chain *nc;
 200
 201         nc = nexthop_chain_new();
 202         nexthop_chain_verify_iter(nc);
 203
 204         nexthop_chain_add_top(nc);
 205         nexthop_chain_verify_iter(nc);
 206
 207         nexthop_chain_add_top(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_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_top(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_recursive(nc);
 229         nexthop_chain_verify_iter(nc);
 230
 231         nexthop_chain_add_recursive(nc);
 232         nexthop_chain_verify_iter(nc);
 233
 234         nexthop_chain_add_recursive_level(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_top(nc);
 244         nexthop_chain_verify_iter(nc);
 245
 246         nexthop_chain_free(nc);
 247 }
 248
 249 /* This test run builds numerous random
 250  * nexthop chain configurations and verifies
 251  * that the iterator correctly progresses
 252  * through each. */
 253 static void test_run_prng(void)
 254 {
 255         struct nexthop_chain *nc;
 256         struct prng *prng;
 257         int i;
 258
 259         nc = nexthop_chain_new();
 260         prng = prng_new(0);
 261
 262         for (i = 0; i < 1000000; i++) {
 263                 switch (prng_rand(prng) % 10) {
 264                 case 0:
 265                         nexthop_chain_clear(nc);
 266                         break;
 267                 case 1:
 268                 case 2:
 269                 case 3:
 270                 case 4:
 271                 case 5:
 272                         nexthop_chain_add_top(nc);
 273                         break;
 274                 case 6:
 275                 case 7:
 276                 case 8:
 277                         if (nc->current_top)
 278                                 nexthop_chain_add_recursive(nc);
 279                         break;
 280                 case 9:
 281                         if (nc->current_top)
 282                                 nexthop_chain_add_recursive_level(nc);
 283                         break;
 284                 }
 285                 nexthop_chain_verify_iter(nc);
 286         }
 287         nexthop_chain_free(nc);
 288         prng_free(prng);
 289 }
 290
 291 int main(int argc, char **argv)
 292 {
 293         if (argc >= 2 && !strcmp("-v", argv[1]))
 294                 verbose = 1;
 295         test_run_first();
 296         printf("Simple test passed.\n");
 297         test_run_prng();
 298         printf("PRNG test passed.\n");
 299 }