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