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>

7 files changed, 421 insertions, 2 deletions

diff --git a/tests/.gitignore b/tests/.gitignore
index 8baea0a8..31fb70a4 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -31,4 +31,5 @@ testmemory
 testprivs
 testsig
 teststream
+testnexthopiter
 site.exp
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 2ed0e1c5..e5c7fd79 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -25,7 +25,7 @@ TESTS_BGPD =
 endif
 
 check_PROGRAMS = testsig testbuffer testmemory heavy heavywq heavythread \
-		testprivs teststream testchecksum tabletest \
+		testprivs teststream testchecksum tabletest testnexthopiter \
 		$(TESTS_BGPD)
 
 testsig_SOURCES = test-sig.c
@@ -43,6 +43,7 @@ testbgpmpattr_SOURCES =  bgp_mp_attr_test.c
 testchecksum_SOURCES = test-checksum.c
 testbgpmpath_SOURCES = bgp_mpath_test.c
 tabletest_SOURCES = table_test.c
+testnexthopiter_SOURCES = test-nexthop-iter.c prng.c
 
 testsig_LDADD = ../lib/libzebra.la @LIBCAP@
 testbuffer_LDADD = ../lib/libzebra.la @LIBCAP@
@@ -59,3 +60,4 @@ testbgpmpattr_LDADD = ../bgpd/libbgp.a ../lib/libzebra.la @LIBCAP@ -lm
 testchecksum_LDADD = ../lib/libzebra.la @LIBCAP@ 
 testbgpmpath_LDADD = ../bgpd/libbgp.a ../lib/libzebra.la @LIBCAP@ -lm
 tabletest_LDADD = ../lib/libzebra.la @LIBCAP@ -lm
+testnexthopiter_LDADD = ../lib/libzebra.la @LIBCAP@
diff --git a/tests/libzebra.tests/Makefile.am b/tests/libzebra.tests/Makefile.am
index 0d29e287..14138a08 100644
--- a/tests/libzebra.tests/Makefile.am
+++ b/tests/libzebra.tests/Makefile.am
@@ -1,2 +1,3 @@
 EXTRA_DIST = \
-	tabletest.exp
+	tabletest.exp \
+	testnexthopiter.exp
diff --git a/tests/libzebra.tests/testnexthopiter.exp b/tests/libzebra.tests/testnexthopiter.exp
new file mode 100644
index 00000000..be35a0a2
--- /dev/null
+++ b/tests/libzebra.tests/testnexthopiter.exp
@@ -0,0 +1,8 @@
+set timeout 10
+set testprefix "testnexthopiter "
+set aborted 0
+
+spawn "./testnexthopiter"
+
+onesimple "simple" "Simple test passed."
+onesimple "prng" "PRNG test passed."
diff --git a/tests/prng.c b/tests/prng.c
new file mode 100644
index 00000000..7b1b4282
--- /dev/null
+++ b/tests/prng.c
@@ -0,0 +1,82 @@
+/*
+ * Very simple prng to allow for randomized tests with reproducable
+ * results.
+ *
+ * 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 <assert.h>
+#include <stdlib.h>
+
+#include "prng.h"
+
+struct prng
+{
+  unsigned long long state1;
+  unsigned long long state2;
+};
+
+static char
+prng_bit(struct prng *prng)
+{
+  prng->state1 *= 2416;
+  prng->state1 += 374441;
+  prng->state1 %= 1771875;
+
+  if (prng->state1 % 2)
+    {
+      prng->state2 *= 84589;
+      prng->state2 += 45989;
+      prng->state2 %= 217728;
+    }
+
+  return prng->state2 % 2;
+}
+
+struct prng*
+prng_new(unsigned long long seed)
+{
+  struct prng *rv = calloc(sizeof(*rv), 1);
+  assert(rv);
+
+  rv->state1 = rv->state2 = seed;
+
+  return rv;
+}
+
+unsigned int
+prng_rand(struct prng *prng)
+{
+  unsigned int i, rv = 0;
+
+  for (i = 0; i < 32; i++)
+    {
+      rv |= prng_bit(prng);
+      rv <<= 1;
+    }
+  return rv;
+}
+
+void
+prng_free(struct prng *prng)
+{
+  free(prng);
+}
diff --git a/tests/prng.h b/tests/prng.h
new file mode 100644
index 00000000..ed364986
--- /dev/null
+++ b/tests/prng.h
@@ -0,0 +1,34 @@
+/*
+ * Very simple prng to allow for randomized tests with reproducable
+ * results.
+ *
+ * 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.
+ */
+#ifndef _PRNG_H
+#define _PRNG_H
+
+struct prng;
+
+struct prng* prng_new(unsigned long long seed);
+unsigned int prng_rand(struct prng*);
+void prng_free(struct prng *);
+
+#endif
diff --git a/tests/test-nexthop-iter.c b/tests/test-nexthop-iter.c
new file mode 100644
index 00000000..25037932
--- /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");
+}