zebra: rework recursive route resolution
Change the datastructure for recursive routes. This brings the following
benefits:
By using struct nexthop also to store nexthops obtained by recursive
resolution, we can get rid of quite a bit of code duplication in the fib
management. (rt_netlink, rt_socket, ...)
With the new datastructure we can make use of all available paths when
recursive routes are resolved with multipath routes.
Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
diff --git a/tests/test-nexthop-iter.c b/tests/test-nexthop-iter.c
new file mode 100644
index 0000000..2503793
--- /dev/null
+++ b/tests/test-nexthop-iter.c
@@ -0,0 +1,291 @@
+/*
+ * 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");
+}