123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291 |
- /*
- * Recursive Nexthop Iterator test.
- * This tests the ALL_NEXTHOPS_RO macro.
- *
- * Copyright (C) 2012 by Open Source Routing.
- * Copyright (C) 2012 by Internet Systems Consortium, Inc. ("ISC")
- *
- * This file is part of Quagga
- *
- * Quagga is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2, or (at your option) any
- * later version.
- *
- * Quagga is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with Quagga; see the file COPYING. If not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
- * 02111-1307, USA.
- */
- #include <zebra.h>
- #include "zebra/rib.h"
- #include "prng.h"
- struct thread_master *master;
- static int verbose;
- static void
- str_append(char **buf, const char *repr)
- {
- if (*buf)
- {
- *buf = realloc(*buf, strlen(*buf) + strlen(repr) + 1);
- assert(*buf);
- strncpy((*buf) + strlen(*buf), repr, strlen(repr) + 1);
- }
- else
- {
- *buf = strdup(repr);
- assert(*buf);
- }
- }
- static void
- str_appendf(char **buf, const char *format, ...)
- {
- va_list ap;
- int rv;
- char *pbuf;
- va_start(ap, format);
- rv = vasprintf(&pbuf, format, ap);
- va_end(ap);
- assert(rv >= 0);
- str_append(buf, pbuf);
- free(pbuf);
- }
- /* This structure contains a nexthop chain
- * and its expected representation */
- struct nexthop_chain
- {
- /* Head of the chain */
- struct nexthop *head;
- /* Last nexthop in top chain */
- struct nexthop *current_top;
- /* Last nexthop in current recursive chain */
- struct nexthop *current_recursive;
- /* Expected string representation. */
- char *repr;
- };
- static struct nexthop_chain*
- nexthop_chain_new(void)
- {
- struct nexthop_chain *rv;
- rv = calloc(sizeof(*rv), 1);
- assert(rv);
- return rv;
- }
- static void
- nexthop_chain_add_top(struct nexthop_chain *nc)
- {
- struct nexthop *nh;
- nh = calloc(sizeof(*nh), 1);
- assert(nh);
- if (nc->head)
- {
- nc->current_top->next = nh;
- nh->prev = nc->current_top;
- nc->current_top = nh;
- }
- else
- {
- nc->head = nc->current_top = nh;
- }
- nc->current_recursive = NULL;
- str_appendf(&nc->repr, "%p\n", nh);
- }
- static void
- nexthop_chain_add_recursive(struct nexthop_chain *nc)
- {
- struct nexthop *nh;
- nh = calloc(sizeof(*nh), 1);
- assert(nh);
- assert(nc->current_top);
- if (nc->current_recursive)
- {
- nc->current_recursive->next = nh;
- nh->prev = nc->current_recursive;
- nc->current_recursive = nh;
- }
- else
- {
- SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE);
- nc->current_top->resolved = nh;
- nc->current_recursive = nh;
- }
- str_appendf(&nc->repr, " %p\n", nh);
- }
- static void
- nexthop_chain_clear(struct nexthop_chain *nc)
- {
- struct nexthop *tcur, *tnext;
- for (tcur = nc->head; tcur; tcur = tnext)
- {
- tnext = tcur->next;
- if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE))
- {
- struct nexthop *rcur, *rnext;
- for (rcur = tcur->resolved; rcur; rcur = rnext)
- {
- rnext = rcur->next;
- free(rcur);
- }
- }
- free(tcur);
- }
- nc->head = nc->current_top = nc->current_recursive = NULL;
- free(nc->repr);
- nc->repr = NULL;
- }
- static void
- nexthop_chain_free(struct nexthop_chain *nc)
- {
- if (!nc)
- return;
- nexthop_chain_clear(nc);
- free(nc);
- }
- /* This function builds a string representation of
- * the nexthop chain using the ALL_NEXTHOPS_RO macro.
- * It verifies that the ALL_NEXTHOPS_RO macro iterated
- * correctly over the nexthop chain by comparing the
- * generated representation with the expected representation.
- */
- static void
- nexthop_chain_verify_iter(struct nexthop_chain *nc)
- {
- struct nexthop *nh, *tnh;
- int recursing;
- char *repr = NULL;
- for (ALL_NEXTHOPS_RO(nc->head, nh, tnh, recursing))
- {
- if (recursing)
- str_appendf(&repr, " %p\n", nh);
- else
- str_appendf(&repr, "%p\n", nh);
- }
- if (repr && verbose)
- printf("===\n%s", repr);
- assert((!repr && !nc->repr) || (repr && nc->repr && !strcmp(repr, nc->repr)));
- free(repr);
- }
- /* This test run builds a simple nexthop chain
- * with some recursive nexthops and verifies that
- * the iterator works correctly in each stage along
- * the way.
- */
- static void
- test_run_first(void)
- {
- struct nexthop_chain *nc;
- nc = nexthop_chain_new();
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_top(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_top(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_recursive(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_recursive(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_top(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_top(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_top(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_recursive(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_recursive(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_add_recursive(nc);
- nexthop_chain_verify_iter(nc);
- nexthop_chain_free(nc);
- }
- /* This test run builds numerous random
- * nexthop chain configurations and verifies
- * that the iterator correctly progresses
- * through each. */
- static void
- test_run_prng(void)
- {
- struct nexthop_chain *nc;
- struct prng *prng;
- int i;
- nc = nexthop_chain_new();
- prng = prng_new(0);
- for (i = 0; i < 1000000; i++)
- {
- switch (prng_rand(prng) % 10)
- {
- case 0:
- nexthop_chain_clear(nc);
- break;
- case 1:
- case 2:
- case 3:
- case 4:
- case 5:
- nexthop_chain_add_top(nc);
- break;
- case 6:
- case 7:
- case 8:
- case 9:
- if (nc->current_top)
- nexthop_chain_add_recursive(nc);
- break;
- }
- nexthop_chain_verify_iter(nc);
- }
- nexthop_chain_free(nc);
- prng_free(prng);
- }
- int main(int argc, char **argv)
- {
- if (argc >= 2 && !strcmp("-v", argv[1]))
- verbose = 1;
- test_run_first();
- printf("Simple test passed.\n");
- test_run_prng();
- printf("PRNG test passed.\n");
- }
|