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>

16 files changed, 1046 insertions, 718 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");
+}
diff --git a/zebra/rib.h b/zebra/rib.h
index e16ce68a..4d98e059 100644
--- a/zebra/rib.h
+++ b/zebra/rib.h
@@ -254,16 +254,65 @@ struct nexthop
 #define NEXTHOP_FLAG_FIB        (1 << 1) /* FIB nexthop. */
 #define NEXTHOP_FLAG_RECURSIVE  (1 << 2) /* Recursive nexthop. */
 
-  /* Nexthop address or interface name. */
+  /* Nexthop address */
   union g_addr gate;
-
-  /* Recursive lookup nexthop. */
-  u_char rtype;
-  unsigned int rifindex;
-  union g_addr rgate;
   union g_addr src;
+
+  /* Nexthops obtained by recursive resolution.
+   *
+   * If the nexthop struct needs to be resolved recursively,
+   * NEXTHOP_FLAG_RECURSIVE will be set in flags and the nexthops
+   * obtained by recursive resolution will be added to `resolved'.
+   * Only one level of recursive resolution is currently supported. */
+  struct nexthop *resolved;
 };
 
+/* The following for loop allows to iterate over the nexthop
+ * structure of routes.
+ *
+ * We have to maintain quite a bit of state:
+ *
+ * nexthop:   The pointer to the current nexthop, either in the
+ *            top-level chain or in the resolved chain of ni.
+ * tnexthop:  The pointer to the current nexthop in the top-level
+ *            nexthop chain.
+ * recursing: Information if nh currently is in the top-level chain
+ *            (0) or in a resolved chain (1).
+ *
+ * Initialization: Set `nexthop' and `tnexthop' to the head of the
+ * top-level chain. As nexthop is in the top level chain, set recursing
+ * to 0.
+ *
+ * Iteration check: Check that the `nexthop' pointer is not NULL.
+ *
+ * Iteration step: This is the tricky part. Check if `nexthop' has
+ * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' is in
+ * the top level chain and has at least one nexthop attached to
+ * `nexthop->resolved'. As we want to descend into `nexthop->resolved',
+ * set `recursing' to 1 and set `nexthop' to `nexthop->resolved'.
+ * `tnexthop' is left alone in that case so we can remember which nexthop
+ * in the top level chain we are currently handling.
+ *
+ * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
+ * current chain. If we are recursing, `nexthop' will be set to
+ * `nexthop->next' and `tnexthop' will be left alone. If we are not
+ * recursing, both `tnexthop' and `nexthop' will be set to `nexthop->next'
+ * as we are progressing in the top level chain.
+ *   If we encounter `nexthop->next == NULL', we will clear the `recursing'
+ * flag as we arived either at the end of the resolved chain or at the end
+ * of the top level chain. In both cases, we set `tnexthop' and `nexthop'
+ * to `tnexthop->next', progressing to the next position in the top-level
+ * chain and possibly to its end marked by NULL.
+ */
+#define ALL_NEXTHOPS_RO(head, nexthop, tnexthop, recursing) \
+  (tnexthop) = (nexthop) = (head), (recursing) = 0; \
+  (nexthop); \
+  (nexthop) = CHECK_FLAG((nexthop)->flags, NEXTHOP_FLAG_RECURSIVE) \
+    ? (((recursing) = 1), (nexthop)->resolved) \
+    : ((nexthop)->next ? ((recursing) ? (nexthop)->next \
+                                      : ((tnexthop) = (nexthop)->next)) \
+                       : (((recursing) = 0),((tnexthop) = (tnexthop)->next)))
+
 /* Routing table instance.  */
 struct vrf
 {
@@ -333,6 +382,7 @@ extern struct nexthop *nexthop_ipv4_ifindex_add (struct rib *,
                                                  struct in_addr *,
                                                  struct in_addr *,
                                                  unsigned int);
+extern int nexthop_has_fib_child(struct nexthop *);
 extern void rib_lookup_and_dump (struct prefix_ipv4 *);
 extern void rib_lookup_and_pushup (struct prefix_ipv4 *);
 extern void rib_dump (const char *, const struct prefix_ipv4 *, const struct rib *);
diff --git a/zebra/rt_ioctl.c b/zebra/rt_ioctl.c
index a5d588c7..404a7c69 100644
--- a/zebra/rt_ioctl.c
+++ b/zebra/rt_ioctl.c
@@ -169,7 +169,8 @@ kernel_ioctl_ipv4 (u_long cmd, struct prefix *p, struct rib *rib, int family)
   int sock;
   struct rtentry rtentry;
   struct sockaddr_in sin_dest, sin_mask, sin_gate;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   int nexthop_num = 0;
   struct interface *ifp;
 
@@ -188,65 +189,49 @@ kernel_ioctl_ipv4 (u_long cmd, struct prefix *p, struct rib *rib, int family)
       SET_FLAG (rtentry.rt_flags, RTF_REJECT);
 
       if (cmd == SIOCADDRT)
-	for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
-	  SET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
-
+	for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
+	  {
+            /* We shouldn't encounter recursive nexthops on discard routes,
+             * but it is probably better to handle that case correctly anyway.
+             */
+	    if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+	      continue;
+	    SET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
+	  }
       goto skip;
     }
 
   memset (&sin_gate, 0, sizeof (struct sockaddr_in));
 
   /* Make gateway. */
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     {
+      if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+        continue;
+
       if ((cmd == SIOCADDRT 
 	   && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
 	  || (cmd == SIOCDELRT
 	      && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)))
 	{
-	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+	  if (nexthop->type == NEXTHOP_TYPE_IPV4 ||
+	      nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
 	    {
-	      if (nexthop->rtype == NEXTHOP_TYPE_IPV4 ||
-		  nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX)
-		{
-		  sin_gate.sin_family = AF_INET;
+	      sin_gate.sin_family = AF_INET;
 #ifdef HAVE_STRUCT_SOCKADDR_IN_SIN_LEN
-		  sin_gate.sin_len = sizeof (struct sockaddr_in);
+	      sin_gate.sin_len = sizeof (struct sockaddr_in);
 #endif /* HAVE_STRUCT_SOCKADDR_IN_SIN_LEN */
-		  sin_gate.sin_addr = nexthop->rgate.ipv4;
-		  rtentry.rt_flags |= RTF_GATEWAY;
-		}
-	      if (nexthop->rtype == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->rtype == NEXTHOP_TYPE_IFNAME)
-		{
-		  ifp = if_lookup_by_index (nexthop->rifindex);
-		  if (ifp)
-		    rtentry.rt_dev = ifp->name;
-		  else
-		    return -1;
-		}
+	      sin_gate.sin_addr = nexthop->gate.ipv4;
+	      rtentry.rt_flags |= RTF_GATEWAY;
 	    }
-	  else
+	  if (nexthop->type == NEXTHOP_TYPE_IFINDEX
+	      || nexthop->type == NEXTHOP_TYPE_IFNAME)
 	    {
-	      if (nexthop->type == NEXTHOP_TYPE_IPV4 ||
-		  nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-		{
-		  sin_gate.sin_family = AF_INET;
-#ifdef HAVE_STRUCT_SOCKADDR_IN_SIN_LEN
-		  sin_gate.sin_len = sizeof (struct sockaddr_in);
-#endif /* HAVE_STRUCT_SOCKADDR_IN_SIN_LEN */
-		  sin_gate.sin_addr = nexthop->gate.ipv4;
-		  rtentry.rt_flags |= RTF_GATEWAY;
-		}
-	      if (nexthop->type == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->type == NEXTHOP_TYPE_IFNAME)
-		{
-		  ifp = if_lookup_by_index (nexthop->ifindex);
-		  if (ifp)
-		    rtentry.rt_dev = ifp->name;
-		  else
-		    return -1;
-		}
+	      ifp = if_lookup_by_index (nexthop->ifindex);
+	      if (ifp)
+	        rtentry.rt_dev = ifp->name;
+	      else
+	        return -1;
 	    }
 
 	  if (cmd == SIOCADDRT)
@@ -430,7 +415,8 @@ kernel_ioctl_ipv6_multipath (u_long cmd, struct prefix *p, struct rib *rib,
   int ret;
   int sock;
   struct in6_rtmsg rtm;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   int nexthop_num = 0;
     
   memset (&rtm, 0, sizeof (struct in6_rtmsg));
@@ -456,48 +442,30 @@ kernel_ioctl_ipv6_multipath (u_long cmd, struct prefix *p, struct rib *rib,
   /* rtm.rtmsg_flags |= RTF_DYNAMIC; */
 
   /* Make gateway. */
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     {
+      if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+        continue;
+
       if ((cmd == SIOCADDRT 
 	   && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
 	  || (cmd == SIOCDELRT
 	      && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)))
 	{
-	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+	  if (nexthop->type == NEXTHOP_TYPE_IPV6
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
 	    {
-	      if (nexthop->rtype == NEXTHOP_TYPE_IPV6
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX)
-		{
-		  memcpy (&rtm.rtmsg_gateway, &nexthop->rgate.ipv6,
-			  sizeof (struct in6_addr));
-		}
-	      if (nexthop->rtype == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->rtype == NEXTHOP_TYPE_IFNAME
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX)
-		rtm.rtmsg_ifindex = nexthop->rifindex;
-	      else
-		rtm.rtmsg_ifindex = 0;
-	      
+	      memcpy (&rtm.rtmsg_gateway, &nexthop->gate.ipv6,
+		      sizeof (struct in6_addr));
 	    }
+	  if (nexthop->type == NEXTHOP_TYPE_IFINDEX
+	      || nexthop->type == NEXTHOP_TYPE_IFNAME
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
+	    rtm.rtmsg_ifindex = nexthop->ifindex;
 	  else
-	    {
-	      if (nexthop->type == NEXTHOP_TYPE_IPV6
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
-		{
-		  memcpy (&rtm.rtmsg_gateway, &nexthop->gate.ipv6,
-			  sizeof (struct in6_addr));
-		}
-	      if (nexthop->type == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->type == NEXTHOP_TYPE_IFNAME
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
-		rtm.rtmsg_ifindex = nexthop->ifindex;
-	      else
-		rtm.rtmsg_ifindex = 0;
-	    }
+	    rtm.rtmsg_ifindex = 0;
 
 	  if (cmd == SIOCADDRT)
 	    SET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
diff --git a/zebra/rt_netlink.c b/zebra/rt_netlink.c
index 86e02efb..b0ade058 100644
--- a/zebra/rt_netlink.c
+++ b/zebra/rt_netlink.c
@@ -1426,6 +1426,207 @@ netlink_route (int cmd, int family, void *dest, int length, void *gate,
   return 0;
 }
 
+/* This function takes a nexthop as argument and adds
+ * the appropriate netlink attributes to an existing
+ * netlink message.
+ *
+ * @param routedesc: Human readable description of route type
+ *                   (direct/recursive, single-/multipath)
+ * @param bytelen: Length of addresses in bytes.
+ * @param nexthop: Nexthop information
+ * @param nlmsg: nlmsghdr structure to fill in.
+ * @param req_size: The size allocated for the message.
+ */
+static void
+_netlink_route_build_singlepath(
+        const char *routedesc,
+        int bytelen,
+        struct nexthop *nexthop,
+        struct nlmsghdr *nlmsg,
+        size_t req_size)
+{
+  if (nexthop->type == NEXTHOP_TYPE_IPV4
+      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
+    {
+      addattr_l (nlmsg, req_size, RTA_GATEWAY,
+                 &nexthop->gate.ipv4, bytelen);
+      if (nexthop->src.ipv4.s_addr)
+        addattr_l (nlmsg, req_size, RTA_PREFSRC,
+                   &nexthop->src.ipv4, bytelen);
+
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via %s if %u",
+                   routedesc,
+                   inet_ntoa (nexthop->gate.ipv4),
+                   nexthop->ifindex);
+    }
+#ifdef HAVE_IPV6
+  if (nexthop->type == NEXTHOP_TYPE_IPV6
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
+    {
+      addattr_l (nlmsg, req_size, RTA_GATEWAY,
+                 &nexthop->gate.ipv6, bytelen);
+
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via %s if %u",
+                   routedesc,
+                   inet6_ntoa (nexthop->gate.ipv6),
+                   nexthop->ifindex);
+    }
+#endif /* HAVE_IPV6 */
+  if (nexthop->type == NEXTHOP_TYPE_IFINDEX
+      || nexthop->type == NEXTHOP_TYPE_IFNAME
+      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
+    {
+      addattr32 (nlmsg, req_size, RTA_OIF, nexthop->ifindex);
+
+      if (nexthop->src.ipv4.s_addr)
+        addattr_l (nlmsg, req_size, RTA_PREFSRC,
+                   &nexthop->src.ipv4, bytelen);
+
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via if %u", routedesc, nexthop->ifindex);
+    }
+
+  if (nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME)
+    {
+      addattr32 (nlmsg, req_size, RTA_OIF, nexthop->ifindex);
+
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via if %u", routedesc, nexthop->ifindex);
+    }
+}
+
+/* This function takes a nexthop as argument and
+ * appends to the given rtattr/rtnexthop pair the
+ * representation of the nexthop. If the nexthop
+ * defines a preferred source, the src parameter
+ * will be modified to point to that src, otherwise
+ * it will be kept unmodified.
+ *
+ * @param routedesc: Human readable description of route type
+ *                   (direct/recursive, single-/multipath)
+ * @param bytelen: Length of addresses in bytes.
+ * @param nexthop: Nexthop information
+ * @param rta: rtnetlink attribute structure
+ * @param rtnh: pointer to an rtnetlink nexthop structure
+ * @param src: pointer pointing to a location where
+ *             the prefsrc should be stored.
+ */
+static void
+_netlink_route_build_multipath(
+        const char *routedesc,
+        int bytelen,
+        struct nexthop *nexthop,
+        struct rtattr *rta,
+        struct rtnexthop *rtnh,
+        union g_addr **src
+        )
+{
+  rtnh->rtnh_len = sizeof (*rtnh);
+  rtnh->rtnh_flags = 0;
+  rtnh->rtnh_hops = 0;
+  rta->rta_len += rtnh->rtnh_len;
+
+  if (nexthop->type == NEXTHOP_TYPE_IPV4
+      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
+    {
+      rta_addattr_l (rta, NL_PKT_BUF_SIZE, RTA_GATEWAY,
+                     &nexthop->gate.ipv4, bytelen);
+      rtnh->rtnh_len += sizeof (struct rtattr) + 4;
+
+      if (nexthop->src.ipv4.s_addr)
+        *src = &nexthop->src;
+
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via %s if %u",
+                   routedesc,
+                   inet_ntoa (nexthop->gate.ipv4),
+                   nexthop->ifindex);
+    }
+#ifdef HAVE_IPV6
+  if (nexthop->type == NEXTHOP_TYPE_IPV6
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
+    {
+      rta_addattr_l (rta, NL_PKT_BUF_SIZE, RTA_GATEWAY,
+                     &nexthop->gate.ipv6, bytelen);
+
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via %s if %u",
+                   routedesc,
+                   inet6_ntoa (nexthop->gate.ipv6),
+                   nexthop->ifindex);
+    }
+#endif /* HAVE_IPV6 */
+  /* ifindex */
+  if (nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX
+      || nexthop->type == NEXTHOP_TYPE_IFINDEX
+      || nexthop->type == NEXTHOP_TYPE_IFNAME)
+    {
+      rtnh->rtnh_ifindex = nexthop->ifindex;
+      if (nexthop->src.ipv4.s_addr)
+        *src = &nexthop->src;
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via if %u", routedesc, nexthop->ifindex);
+    }
+  else if (nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
+    {
+      rtnh->rtnh_ifindex = nexthop->ifindex;
+
+      if (IS_ZEBRA_DEBUG_KERNEL)
+        zlog_debug("netlink_route_multipath() (%s): "
+                   "nexthop via if %u", routedesc, nexthop->ifindex);
+    }
+  else
+    {
+      rtnh->rtnh_ifindex = 0;
+    }
+}
+
+/* Log debug information for netlink_route_multipath
+ * if debug logging is enabled.
+ *
+ * @param cmd: Netlink command which is to be processed
+ * @param p: Prefix for which the change is due
+ * @param nexthop: Nexthop which is currently processed
+ * @param routedesc: Semantic annotation for nexthop
+ *                     (recursive, multipath, etc.)
+ * @param family: Address family which the change concerns
+ */
+static void
+_netlink_route_debug(
+        int cmd,
+        struct prefix *p,
+        struct nexthop *nexthop,
+        const char *routedesc,
+        int family)
+{
+  if (IS_ZEBRA_DEBUG_KERNEL)
+    {
+      zlog_debug ("netlink_route_multipath() (%s): %s %s/%d type %s",
+         routedesc,
+         lookup (nlmsg_str, cmd),
+#ifdef HAVE_IPV6
+         (family == AF_INET) ? inet_ntoa (p->u.prefix4) :
+         inet6_ntoa (p->u.prefix6),
+#else
+         inet_ntoa (p->u.prefix4),
+#endif /* HAVE_IPV6 */
+         p->prefixlen, nexthop_type_to_str (nexthop->type));
+    }
+}
+
 /* Routing table change via netlink interface. */
 static int
 netlink_route_multipath (int cmd, struct prefix *p, struct rib *rib,
@@ -1433,9 +1634,11 @@ netlink_route_multipath (int cmd, struct prefix *p, struct rib *rib,
 {
   int bytelen;
   struct sockaddr_nl snl;
-  struct nexthop *nexthop = NULL;
-  int nexthop_num = 0;
+  struct nexthop *nexthop = NULL, *tnexthop;
+  int recursing;
+  int nexthop_num;
   int discard;
+  const char *routedesc;
 
   struct
   {
@@ -1485,159 +1688,52 @@ netlink_route_multipath (int cmd, struct prefix *p, struct rib *rib,
   if (discard)
     {
       if (cmd == RTM_NEWROUTE)
-        for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
-          SET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
+        for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
+          {
+            /* We shouldn't encounter recursive nexthops on discard routes,
+             * but it is probably better to handle that case correctly anyway.
+             */
+            if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+              continue;
+            SET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
+          }
       goto skip;
     }
 
-  /* Multipath case. */
-  if (rib->nexthop_active_num == 1 || MULTIPATH_NUM == 1)
+  /* Count overall nexthops so we can decide whether to use singlepath
+   * or multipath case. */
+  nexthop_num = 0;
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
+    {
+      if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+        continue;
+      if (cmd == RTM_NEWROUTE && !CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE))
+        continue;
+      if (cmd == RTM_DELROUTE && !CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
+        continue;
+
+      nexthop_num++;
+    }
+
+  /* Singlepath case. */
+  if (nexthop_num == 1 || MULTIPATH_NUM == 1)
     {
-      for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+      nexthop_num = 0;
+      for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
         {
+          if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+            continue;
 
           if ((cmd == RTM_NEWROUTE
                && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
               || (cmd == RTM_DELROUTE
                   && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)))
             {
+              routedesc = recursing ? "recursive, 1 hop" : "single hop";
 
-              if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-                {
-                  if (IS_ZEBRA_DEBUG_KERNEL)
-                    {
-                      zlog_debug
-                        ("netlink_route_multipath() (recursive, 1 hop): "
-                         "%s %s/%d, type %s", lookup (nlmsg_str, cmd),
-#ifdef HAVE_IPV6
-			 (family == AF_INET) ? inet_ntoa (p->u.prefix4) :
-			 inet6_ntoa (p->u.prefix6),
-#else
-			 inet_ntoa (p->u.prefix4),
-#endif /* HAVE_IPV6 */
-			 
-			 p->prefixlen, nexthop_type_to_str (nexthop->rtype));
-                    }
-
-                  if (nexthop->rtype == NEXTHOP_TYPE_IPV4
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX)
-		    {
-		      addattr_l (&req.n, sizeof req, RTA_GATEWAY,
-				 &nexthop->rgate.ipv4, bytelen);
-                      if (nexthop->src.ipv4.s_addr)
-		          addattr_l(&req.n, sizeof req, RTA_PREFSRC,
-				     &nexthop->src.ipv4, bytelen);
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (recursive, "
-				   "1 hop): nexthop via %s if %u",
-				   inet_ntoa (nexthop->rgate.ipv4),
-				   nexthop->rifindex);
-		    }
-#ifdef HAVE_IPV6
-                  if (nexthop->rtype == NEXTHOP_TYPE_IPV6
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME)
-		    {
-		      addattr_l (&req.n, sizeof req, RTA_GATEWAY,
-				 &nexthop->rgate.ipv6, bytelen);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (recursive, "
-				   "1 hop): nexthop via %s if %u",
-				   inet6_ntoa (nexthop->rgate.ipv6),
-				   nexthop->rifindex);
-		    }
-#endif /* HAVE_IPV6 */
-                  if (nexthop->rtype == NEXTHOP_TYPE_IFINDEX
-                      || nexthop->rtype == NEXTHOP_TYPE_IFNAME
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME)
-		    {
-		      addattr32 (&req.n, sizeof req, RTA_OIF,
-				 nexthop->rifindex);
-                      if ((nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX
-                           || nexthop->rtype == NEXTHOP_TYPE_IFINDEX)
-                          && nexthop->src.ipv4.s_addr)
-                        addattr_l (&req.n, sizeof req, RTA_PREFSRC,
-				 &nexthop->src.ipv4, bytelen);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (recursive, "
-				   "1 hop): nexthop via if %u",
-				   nexthop->rifindex);
-		    }
-                }
-              else
-                {
-                  if (IS_ZEBRA_DEBUG_KERNEL)
-                    {
-                      zlog_debug
-                        ("netlink_route_multipath() (single hop): "
-                         "%s %s/%d, type %s", lookup (nlmsg_str, cmd),
-#ifdef HAVE_IPV6
-			 (family == AF_INET) ? inet_ntoa (p->u.prefix4) :
-			 inet6_ntoa (p->u.prefix6),
-#else
-			 inet_ntoa (p->u.prefix4),
-#endif /* HAVE_IPV6 */
-			 p->prefixlen, nexthop_type_to_str (nexthop->type));
-                    }
-
-                  if (nexthop->type == NEXTHOP_TYPE_IPV4
-                      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-		    {
-		      addattr_l (&req.n, sizeof req, RTA_GATEWAY,
-				 &nexthop->gate.ipv4, bytelen);
-		      if (nexthop->src.ipv4.s_addr)
-                        addattr_l (&req.n, sizeof req, RTA_PREFSRC,
-				 &nexthop->src.ipv4, bytelen);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (single hop): "
-				   "nexthop via %s if %u",
-				   inet_ntoa (nexthop->gate.ipv4),
-				   nexthop->ifindex);
-		    }
-#ifdef HAVE_IPV6
-                  if (nexthop->type == NEXTHOP_TYPE_IPV6
-                      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
-                      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
-		    {
-		      addattr_l (&req.n, sizeof req, RTA_GATEWAY,
-				 &nexthop->gate.ipv6, bytelen);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (single hop): "
-				   "nexthop via %s if %u",
-				   inet6_ntoa (nexthop->gate.ipv6),
-				   nexthop->ifindex);
-		    }
-#endif /* HAVE_IPV6 */
-                  if (nexthop->type == NEXTHOP_TYPE_IFINDEX
-                      || nexthop->type == NEXTHOP_TYPE_IFNAME
-                      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-		    {
-		      addattr32 (&req.n, sizeof req, RTA_OIF, nexthop->ifindex);
-
-		      if (nexthop->src.ipv4.s_addr)
-                        addattr_l (&req.n, sizeof req, RTA_PREFSRC,
-				 &nexthop->src.ipv4, bytelen);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (single hop): "
-				   "nexthop via if %u", nexthop->ifindex);
-		    }
-                  else if (nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX
-                      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME)
-		    {
-		      addattr32 (&req.n, sizeof req, RTA_OIF, nexthop->ifindex);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (single hop): "
-				   "nexthop via if %u", nexthop->ifindex);
-		    }
-                }
+              _netlink_route_debug(cmd, p, nexthop, routedesc, family);
+              _netlink_route_build_singlepath(routedesc, bytelen,
+                                              nexthop, &req.n, sizeof req);
 
               if (cmd == RTM_NEWROUTE)
                 SET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
@@ -1659,168 +1755,26 @@ netlink_route_multipath (int cmd, struct prefix *p, struct rib *rib,
       rtnh = RTA_DATA (rta);
 
       nexthop_num = 0;
-      for (nexthop = rib->nexthop;
-           nexthop && (MULTIPATH_NUM == 0 || nexthop_num < MULTIPATH_NUM);
-           nexthop = nexthop->next)
+      for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
         {
+          if (MULTIPATH_NUM != 0 && nexthop_num >= MULTIPATH_NUM)
+            break;
+
+          if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+            continue;
+
           if ((cmd == RTM_NEWROUTE
                && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
               || (cmd == RTM_DELROUTE
                   && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)))
             {
+              routedesc = recursing ? "recursive, multihop" : "multihop";
               nexthop_num++;
 
-              rtnh->rtnh_len = sizeof (*rtnh);
-              rtnh->rtnh_flags = 0;
-              rtnh->rtnh_hops = 0;
-              rta->rta_len += rtnh->rtnh_len;
-
-              if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-                {
-                  if (IS_ZEBRA_DEBUG_KERNEL)
-                    {
-                      zlog_debug ("netlink_route_multipath() "
-                         "(recursive, multihop): %s %s/%d type %s",
-			 lookup (nlmsg_str, cmd),
-#ifdef HAVE_IPV6
-			 (family == AF_INET) ? inet_ntoa (p->u.prefix4) :
-			 inet6_ntoa (p->u.prefix6),
-#else
-			 inet_ntoa (p->u.prefix4),
-#endif /* HAVE_IPV6 */
-			 p->prefixlen, nexthop_type_to_str (nexthop->rtype));
-                    }
-                  if (nexthop->rtype == NEXTHOP_TYPE_IPV4
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX)
-                    {
-                      rta_addattr_l (rta, NL_PKT_BUF_SIZE, RTA_GATEWAY,
-                                     &nexthop->rgate.ipv4, bytelen);
-                      rtnh->rtnh_len += sizeof (struct rtattr) + 4;
-
-		      if (nexthop->src.ipv4.s_addr)
-                        src = &nexthop->src;
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (recursive, "
-				   "multihop): nexthop via %s if %u",
-				   inet_ntoa (nexthop->rgate.ipv4),
-				   nexthop->rifindex);
-                    }
-#ifdef HAVE_IPV6
-                  if (nexthop->rtype == NEXTHOP_TYPE_IPV6
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX)
-		    {
-		      rta_addattr_l (rta, NL_PKT_BUF_SIZE, RTA_GATEWAY,
-				     &nexthop->rgate.ipv6, bytelen);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (recursive, "
-				   "multihop): nexthop via %s if %u",
-				   inet6_ntoa (nexthop->rgate.ipv6),
-				   nexthop->rifindex);
-		    }
-#endif /* HAVE_IPV6 */
-                  /* ifindex */
-                  if (nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX
-		      || nexthop->rtype == NEXTHOP_TYPE_IFINDEX
-                      || nexthop->rtype == NEXTHOP_TYPE_IFNAME)
-		    {
-		      rtnh->rtnh_ifindex = nexthop->rifindex;
-                      if (nexthop->src.ipv4.s_addr)
-                        src = &nexthop->src;
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (recursive, "
-				   "multihop): nexthop via if %u",
-				   nexthop->rifindex);
-		    }
-		  else if (nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX
-                      || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME)
-		    {
-		      rtnh->rtnh_ifindex = nexthop->rifindex;
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (recursive, "
-				   "multihop): nexthop via if %u",
-				   nexthop->rifindex);
-		    }
-                  else
-		    {
-		      rtnh->rtnh_ifindex = 0;
-		    }
-                }
-              else
-                {
-                  if (IS_ZEBRA_DEBUG_KERNEL)
-                    {
-                      zlog_debug ("netlink_route_multipath() (multihop): "
-                         "%s %s/%d, type %s", lookup (nlmsg_str, cmd),
-#ifdef HAVE_IPV6
-			 (family == AF_INET) ? inet_ntoa (p->u.prefix4) :
-			 inet6_ntoa (p->u.prefix6),
-#else
-			 inet_ntoa (p->u.prefix4),
-#endif /* HAVE_IPV6 */
-			 p->prefixlen, nexthop_type_to_str (nexthop->type));
-                    }
-                  if (nexthop->type == NEXTHOP_TYPE_IPV4
-                      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-                    {
-		      rta_addattr_l (rta, NL_PKT_BUF_SIZE, RTA_GATEWAY,
-				     &nexthop->gate.ipv4, bytelen);
-		      rtnh->rtnh_len += sizeof (struct rtattr) + 4;
-
-		      if (nexthop->src.ipv4.s_addr)
-                        src = &nexthop->src;
-
-                      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (multihop): "
-				   "nexthop via %s if %u",
-				   inet_ntoa (nexthop->gate.ipv4),
-				   nexthop->ifindex);
-                    }
-#ifdef HAVE_IPV6
-                  if (nexthop->type == NEXTHOP_TYPE_IPV6
-                      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
-                      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
-		    { 
-		      rta_addattr_l (rta, NL_PKT_BUF_SIZE, RTA_GATEWAY,
-				     &nexthop->gate.ipv6, bytelen);
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (multihop): "
-				   "nexthop via %s if %u",
-				   inet6_ntoa (nexthop->gate.ipv6),
-				   nexthop->ifindex);
-		    }
-#endif /* HAVE_IPV6 */
-                  /* ifindex */
-                  if (nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX
-		      || nexthop->type == NEXTHOP_TYPE_IFINDEX
-                      || nexthop->type == NEXTHOP_TYPE_IFNAME)
-                    {
-		      rtnh->rtnh_ifindex = nexthop->ifindex;
-		      if (nexthop->src.ipv4.s_addr)
-			src = &nexthop->src;
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (multihop): "
-				   "nexthop via if %u", nexthop->ifindex);
-		    }
-                  else if (nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
-                      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
-		    {
-		      rtnh->rtnh_ifindex = nexthop->ifindex;
-
-		      if (IS_ZEBRA_DEBUG_KERNEL)
-			zlog_debug("netlink_route_multipath() (multihop): "
-				   "nexthop via if %u", nexthop->ifindex);
-		    }
-                  else
-		    {
-		      rtnh->rtnh_ifindex = 0;
-		    }
-                }
+              _netlink_route_debug(cmd, p, nexthop,
+                                   routedesc, family);
+              _netlink_route_build_multipath(routedesc, bytelen,
+                                             nexthop, rta, rtnh, &src);
               rtnh = RTNH_NEXT (rtnh);
 
               if (cmd == RTM_NEWROUTE)
diff --git a/zebra/rt_socket.c b/zebra/rt_socket.c
index 1b8ded7e..5d175d84 100644
--- a/zebra/rt_socket.c
+++ b/zebra/rt_socket.c
@@ -71,7 +71,8 @@ kernel_rtm_ipv4 (int cmd, struct prefix *p, struct rib *rib, int family)
 {
   struct sockaddr_in *mask = NULL;
   struct sockaddr_in sin_dest, sin_mask, sin_gate;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   int nexthop_num = 0;
   unsigned int ifindex = 0;
   int gate = 0;
@@ -96,8 +97,11 @@ kernel_rtm_ipv4 (int cmd, struct prefix *p, struct rib *rib, int family)
 #endif /* HAVE_STRUCT_SOCKADDR_IN_SIN_LEN */
 
   /* Make gateway. */
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     {
+      if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+        continue;
+
       gate = 0;
       char gate_buf[INET_ADDRSTRLEN] = "NULL";
 
@@ -112,38 +116,22 @@ kernel_rtm_ipv4 (int cmd, struct prefix *p, struct rib *rib, int family)
 	      && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)
 	      ))
 	{
-	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+	  if (nexthop->type == NEXTHOP_TYPE_IPV4 ||
+	      nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
 	    {
-	      if (nexthop->rtype == NEXTHOP_TYPE_IPV4 ||
-		  nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX)
-		{
-		  sin_gate.sin_addr = nexthop->rgate.ipv4;
-		  gate = 1;
-		}
-	      if (nexthop->rtype == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->rtype == NEXTHOP_TYPE_IFNAME
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX)
-		ifindex = nexthop->rifindex;
+	      sin_gate.sin_addr = nexthop->gate.ipv4;
+	      gate = 1;
 	    }
-	  else
+	  if (nexthop->type == NEXTHOP_TYPE_IFINDEX
+	      || nexthop->type == NEXTHOP_TYPE_IFNAME
+	      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
+	    ifindex = nexthop->ifindex;
+	  if (nexthop->type == NEXTHOP_TYPE_BLACKHOLE)
 	    {
-	      if (nexthop->type == NEXTHOP_TYPE_IPV4 ||
-		  nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-		{
-		  sin_gate.sin_addr = nexthop->gate.ipv4;
-		  gate = 1;
-		}
-	      if (nexthop->type == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->type == NEXTHOP_TYPE_IFNAME
-		  || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-		ifindex = nexthop->ifindex;
-	      if (nexthop->type == NEXTHOP_TYPE_BLACKHOLE)
-		{
-		  struct in_addr loopback;
-		  loopback.s_addr = htonl (INADDR_LOOPBACK);
-		  sin_gate.sin_addr = loopback;
-		  gate = 1;
-		}
+	      struct in_addr loopback;
+	      loopback.s_addr = htonl (INADDR_LOOPBACK);
+	      sin_gate.sin_addr = loopback;
+	      gate = 1;
 	    }
 
 	  if (gate && p->prefixlen == 32)
@@ -219,7 +207,7 @@ kernel_rtm_ipv4 (int cmd, struct prefix *p, struct rib *rib, int family)
          if (IS_ZEBRA_DEBUG_RIB)
            zlog_debug ("%s: odd command %s for flags %d",
              __func__, lookup (rtm_type_str, cmd), nexthop->flags);
-     } /* for (nexthop = ... */
+     } /* for (ALL_NEXTHOPS_RO(...))*/
  
    /* If there was no useful nexthop, then complain. */
    if (nexthop_num == 0 && IS_ZEBRA_DEBUG_KERNEL)
@@ -354,7 +342,8 @@ kernel_rtm_ipv6_multipath (int cmd, struct prefix *p, struct rib *rib,
 {
   struct sockaddr_in6 *mask;
   struct sockaddr_in6 sin_dest, sin_mask, sin_gate;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   int nexthop_num = 0;
   unsigned int ifindex = 0;
   int gate = 0;
@@ -376,8 +365,11 @@ kernel_rtm_ipv6_multipath (int cmd, struct prefix *p, struct rib *rib,
 #endif /* HAVE_STRUCT_SOCKADDR_IN_SIN_LEN */
 
   /* Make gateway. */
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     {
+      if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+	continue;
+
       gate = 0;
 
       if ((cmd == RTM_ADD
@@ -388,36 +380,18 @@ kernel_rtm_ipv6_multipath (int cmd, struct prefix *p, struct rib *rib,
 #endif
 	      ))
 	{
-	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-	    {
-	      if (nexthop->rtype == NEXTHOP_TYPE_IPV6
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX)
-		{
-		  sin_gate.sin6_addr = nexthop->rgate.ipv6;
-		  gate = 1;
-		}
-	      if (nexthop->rtype == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->rtype == NEXTHOP_TYPE_IFNAME
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX)
-		ifindex = nexthop->rifindex;
-	    }
-	  else
+	  if (nexthop->type == NEXTHOP_TYPE_IPV6
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
 	    {
-	      if (nexthop->type == NEXTHOP_TYPE_IPV6
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
-		{
-		  sin_gate.sin6_addr = nexthop->gate.ipv6;
-		  gate = 1;
-		}
-	      if (nexthop->type == NEXTHOP_TYPE_IFINDEX
-		  || nexthop->type == NEXTHOP_TYPE_IFNAME
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
-		  || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
-		ifindex = nexthop->ifindex;
+	      sin_gate.sin6_addr = nexthop->gate.ipv6;
+	      gate = 1;
 	    }
+	  if (nexthop->type == NEXTHOP_TYPE_IFINDEX
+	      || nexthop->type == NEXTHOP_TYPE_IFNAME
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+	      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
+	    ifindex = nexthop->ifindex;
 
 	  if (cmd == RTM_ADD)
 	    SET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
diff --git a/zebra/zebra_fpm_netlink.c b/zebra/zebra_fpm_netlink.c
index 67bcf0a1..b5f2b760 100644
--- a/zebra/zebra_fpm_netlink.c
+++ b/zebra/zebra_fpm_netlink.c
@@ -152,7 +152,8 @@ typedef struct netlink_route_info_t_
  * Returns TRUE if a nexthop was added, FALSE otherwise.
  */
 static int
-netlink_route_info_add_nh (netlink_route_info_t *ri, struct nexthop *nexthop)
+netlink_route_info_add_nh (netlink_route_info_t *ri, struct nexthop *nexthop,
+			   int recursive)
 {
   netlink_nh_info_t nhi;
   union g_addr *src;
@@ -163,40 +164,7 @@ netlink_route_info_add_nh (netlink_route_info_t *ri, struct nexthop *nexthop)
   if (ri->num_nhs >= (int) ZEBRA_NUM_OF (ri->nhs))
     return 0;
 
-  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-    {
-      nhi.recursive = 1;
-      nhi.type = nexthop->rtype;
-      nhi.if_index = nexthop->rifindex;
-
-      if (nexthop->rtype == NEXTHOP_TYPE_IPV4
-	  || nexthop->rtype == NEXTHOP_TYPE_IPV4_IFINDEX)
-	{
-	  nhi.gateway = &nexthop->rgate;
-	  if (nexthop->src.ipv4.s_addr)
-	    src = &nexthop->src;
-	}
-
-#ifdef HAVE_IPV6
-      if (nexthop->rtype == NEXTHOP_TYPE_IPV6
-	  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFINDEX
-	  || nexthop->rtype == NEXTHOP_TYPE_IPV6_IFNAME)
-	{
-	  nhi.gateway = &nexthop->rgate;
-	}
-#endif /* HAVE_IPV6 */
-
-      if (nexthop->rtype == NEXTHOP_TYPE_IFINDEX
-	  || nexthop->rtype == NEXTHOP_TYPE_IFNAME)
-	{
-	  if (nexthop->src.ipv4.s_addr)
-	    src = &nexthop->src;
-	}
-
-      goto done;
-    }
-
-  nhi.recursive = 0;
+  nhi.recursive = recursive;
   nhi.type = nexthop->type;
   nhi.if_index = nexthop->ifindex;
 
@@ -224,11 +192,6 @@ netlink_route_info_add_nh (netlink_route_info_t *ri, struct nexthop *nexthop)
 	src = &nexthop->src;
     }
 
-  /*
-   * Fall through...
-   */
-
- done:
   if (!nhi.gateway && nhi.if_index == 0)
     return 0;
 
@@ -272,7 +235,8 @@ static int
 netlink_route_info_fill (netlink_route_info_t *ri, int cmd,
 			 rib_dest_t *dest, struct rib *rib)
 {
-  struct nexthop *nexthop = NULL;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   int discard;
 
   memset (ri, 0, sizeof (*ri));
@@ -321,35 +285,20 @@ netlink_route_info_fill (netlink_route_info_t *ri, int cmd,
       goto skip;
     }
 
-  /* Multipath case. */
-  if (rib->nexthop_active_num == 1 || MULTIPATH_NUM == 1)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     {
-      for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
-        {
+      if (MULTIPATH_NUM != 0 && ri->num_nhs >= MULTIPATH_NUM)
+        break;
 
-          if ((cmd == RTM_NEWROUTE
-               && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
-              || (cmd == RTM_DELROUTE
-                  && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)))
-            {
-	      netlink_route_info_add_nh (ri, nexthop);
-              break;
-            }
-        }
-    }
-  else
-    {
-      for (nexthop = rib->nexthop;
-           nexthop && (MULTIPATH_NUM == 0 || ri->num_nhs < MULTIPATH_NUM);
-           nexthop = nexthop->next)
+      if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+        continue;
+
+      if ((cmd == RTM_NEWROUTE
+           && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
+          || (cmd == RTM_DELROUTE
+              && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)))
         {
-          if ((cmd == RTM_NEWROUTE
-               && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
-              || (cmd == RTM_DELROUTE
-                  && CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)))
-            {
-	      netlink_route_info_add_nh (ri, nexthop);
-            }
+          netlink_route_info_add_nh (ri, nexthop, recursing);
         }
     }
 
diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c
index 4dd8551a..e39976ee 100644
--- a/zebra/zebra_rib.c
+++ b/zebra/zebra_rib.c
@@ -202,20 +202,26 @@ nexthop_type_to_str (enum nexthop_types_t nh_type)
   return desc[nh_type];
 }
 
-/* Add nexthop to the end of the list.  */
+/* Add nexthop to the end of a nexthop list.  */
 static void
-nexthop_add (struct rib *rib, struct nexthop *nexthop)
+_nexthop_add (struct nexthop **target, struct nexthop *nexthop)
 {
   struct nexthop *last;
 
-  for (last = rib->nexthop; last && last->next; last = last->next)
+  for (last = *target; last && last->next; last = last->next)
     ;
   if (last)
     last->next = nexthop;
   else
-    rib->nexthop = nexthop;
+    *target = nexthop;
   nexthop->prev = last;
+}
 
+/* Add nexthop to the end of a rib node's nexthop list */
+static void
+nexthop_add (struct rib *rib, struct nexthop *nexthop)
+{
+  _nexthop_add(&rib->nexthop, nexthop);
   rib->nexthop_num++;
 }
 
@@ -232,15 +238,32 @@ nexthop_delete (struct rib *rib, struct nexthop *nexthop)
   rib->nexthop_num--;
 }
 
+static void nexthops_free(struct nexthop *nexthop);
+
 /* Free nexthop. */
 static void
 nexthop_free (struct nexthop *nexthop)
 {
   if (nexthop->ifname)
     XFREE (0, nexthop->ifname);
+  if (nexthop->resolved)
+    nexthops_free(nexthop->resolved);
   XFREE (MTYPE_NEXTHOP, nexthop);
 }
 
+/* Frees a list of nexthops */
+static void
+nexthops_free (struct nexthop *nexthop)
+{
+  struct nexthop *nh, *next;
+
+  for (nh = nexthop; nh; nh = next)
+    {
+      next = nh->next;
+      nexthop_free (nh);
+    }
+}
+
 struct nexthop *
 nexthop_ifindex_add (struct rib *rib, unsigned int ifindex)
 {
@@ -365,6 +388,24 @@ nexthop_blackhole_add (struct rib *rib)
   return nexthop;
 }
 
+/* This method checks whether a recursive nexthop has at
+ * least one resolved nexthop in the fib.
+ */
+int
+nexthop_has_fib_child(struct nexthop *nexthop)
+{
+  struct nexthop *nh;
+
+  if (! CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+    return 0;
+
+  for (nh = nexthop->resolved; nh; nh = nh->next)
+    if (CHECK_FLAG (nh->flags, NEXTHOP_FLAG_FIB))
+      return 1;
+
+  return 0;
+}
+
 /* If force flag is not set, do not modify falgs at all for uninstall
    the route from FIB. */
 static int
@@ -375,13 +416,19 @@ nexthop_active_ipv4 (struct rib *rib, struct nexthop *nexthop, int set,
   struct route_table *table;
   struct route_node *rn;
   struct rib *match;
+  int resolved;
   struct nexthop *newhop;
+  struct nexthop *resolved_hop;
 
   if (nexthop->type == NEXTHOP_TYPE_IPV4)
     nexthop->ifindex = 0;
 
   if (set)
-    UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
+    {
+      UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
+      nexthops_free(nexthop->resolved);
+      nexthop->resolved = NULL;
+    }
 
   /* Make lookup prefix. */
   memset (&p, 0, sizeof (struct prefix_ipv4));
@@ -436,6 +483,7 @@ nexthop_active_ipv4 (struct rib *rib, struct nexthop *nexthop, int set,
 	    }
 	  else if (CHECK_FLAG (rib->flags, ZEBRA_FLAG_INTERNAL))
 	    {
+	      resolved = 0;
 	      for (newhop = match->nexthop; newhop; newhop = newhop->next)
 		if (CHECK_FLAG (newhop->flags, NEXTHOP_FLAG_FIB)
 		    && ! CHECK_FLAG (newhop->flags, NEXTHOP_FLAG_RECURSIVE))
@@ -443,18 +491,25 @@ nexthop_active_ipv4 (struct rib *rib, struct nexthop *nexthop, int set,
 		    if (set)
 		      {
 			SET_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
-			nexthop->rtype = newhop->type;
+
+			resolved_hop = XCALLOC(MTYPE_NEXTHOP, sizeof (struct nexthop));
+			SET_FLAG (resolved_hop->flags, NEXTHOP_FLAG_ACTIVE);
+
+			resolved_hop->type = newhop->type;
 			if (newhop->type == NEXTHOP_TYPE_IPV4 ||
 			    newhop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-			  nexthop->rgate.ipv4 = newhop->gate.ipv4;
+			  resolved_hop->gate.ipv4 = newhop->gate.ipv4;
+
 			if (newhop->type == NEXTHOP_TYPE_IFINDEX
 			    || newhop->type == NEXTHOP_TYPE_IFNAME
 			    || newhop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
-			  nexthop->rifindex = newhop->ifindex;
+			  resolved_hop->ifindex = newhop->ifindex;
+
+			_nexthop_add(&nexthop->resolved, resolved_hop);
 		      }
-		    return 1;
+		    resolved = 1;
 		  }
-	      return 0;
+	      return resolved;
 	    }
 	  else
 	    {
@@ -476,13 +531,19 @@ nexthop_active_ipv6 (struct rib *rib, struct nexthop *nexthop, int set,
   struct route_table *table;
   struct route_node *rn;
   struct rib *match;
+  int resolved;
   struct nexthop *newhop;
+  struct nexthop *resolved_hop;
 
   if (nexthop->type == NEXTHOP_TYPE_IPV6)
     nexthop->ifindex = 0;
 
   if (set)
-    UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
+    {
+      UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
+      nexthops_free(nexthop->resolved);
+      nexthop->resolved = NULL;
+    }
 
   /* Make lookup prefix. */
   memset (&p, 0, sizeof (struct prefix_ipv6));
@@ -538,6 +599,7 @@ nexthop_active_ipv6 (struct rib *rib, struct nexthop *nexthop, int set,
 	    }
 	  else if (CHECK_FLAG (rib->flags, ZEBRA_FLAG_INTERNAL))
 	    {
+	      resolved = 0;
 	      for (newhop = match->nexthop; newhop; newhop = newhop->next)
 		if (CHECK_FLAG (newhop->flags, NEXTHOP_FLAG_FIB)
 		    && ! CHECK_FLAG (newhop->flags, NEXTHOP_FLAG_RECURSIVE))
@@ -545,20 +607,27 @@ nexthop_active_ipv6 (struct rib *rib, struct nexthop *nexthop, int set,
 		    if (set)
 		      {
 			SET_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
-			nexthop->rtype = newhop->type;
+
+			resolved_hop = XCALLOC(MTYPE_NEXTHOP, sizeof (struct nexthop));
+			SET_FLAG (resolved_hop->flags, NEXTHOP_FLAG_ACTIVE);
+
+			resolved_hop->type = newhop->type;
 			if (newhop->type == NEXTHOP_TYPE_IPV6
 			    || newhop->type == NEXTHOP_TYPE_IPV6_IFINDEX
 			    || newhop->type == NEXTHOP_TYPE_IPV6_IFNAME)
-			  nexthop->rgate.ipv6 = newhop->gate.ipv6;
+			  resolved_hop->gate.ipv6 = newhop->gate.ipv6;
+
 			if (newhop->type == NEXTHOP_TYPE_IFINDEX
 			    || newhop->type == NEXTHOP_TYPE_IFNAME
 			    || newhop->type == NEXTHOP_TYPE_IPV6_IFINDEX
 			    || newhop->type == NEXTHOP_TYPE_IPV6_IFNAME)
-			  nexthop->rifindex = newhop->ifindex;
+			  resolved_hop->ifindex = newhop->ifindex;
+
+			_nexthop_add(&nexthop->resolved, resolved_hop);
 		      }
-		    return 1;
+		    resolved = 1;
 		  }
-	      return 0;
+	      return resolved;
 	    }
 	  else
 	    {
@@ -577,7 +646,8 @@ rib_match_ipv4 (struct in_addr addr)
   struct route_table *table;
   struct route_node *rn;
   struct rib *match;
-  struct nexthop *newhop;
+  struct nexthop *newhop, *tnewhop;
+  int recursing;
 
   /* Lookup table.  */
   table = vrf_table (AFI_IP, SAFI_UNICAST, 0);
@@ -622,7 +692,7 @@ rib_match_ipv4 (struct in_addr addr)
 	    return match;
 	  else
 	    {
-	      for (newhop = match->nexthop; newhop; newhop = newhop->next)
+	      for (ALL_NEXTHOPS_RO(match->nexthop, newhop, tnewhop, recursing))
 		if (CHECK_FLAG (newhop->flags, NEXTHOP_FLAG_FIB))
 		  return match;
 	      return NULL;
@@ -638,7 +708,8 @@ rib_lookup_ipv4 (struct prefix_ipv4 *p)
   struct route_table *table;
   struct route_node *rn;
   struct rib *match;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
 
   /* Lookup table.  */
   table = vrf_table (AFI_IP, SAFI_UNICAST, 0);
@@ -668,7 +739,7 @@ rib_lookup_ipv4 (struct prefix_ipv4 *p)
   if (match->type == ZEBRA_ROUTE_CONNECT)
     return match;
   
-  for (nexthop = match->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(match->nexthop, nexthop, tnexthop, recursing))
     if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
       return match;
 
@@ -693,7 +764,9 @@ rib_lookup_ipv4_route (struct prefix_ipv4 *p, union sockunion * qgate)
   struct route_table *table;
   struct route_node *rn;
   struct rib *match;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
+  int nexthops_active;
 
   /* Lookup table.  */
   table = vrf_table (AFI_IP, SAFI_UNICAST, 0);
@@ -727,26 +800,25 @@ rib_lookup_ipv4_route (struct prefix_ipv4 *p, union sockunion * qgate)
     return ZEBRA_RIB_FOUND_CONNECTED;
   
   /* Ok, we have a cood candidate, let's check it's nexthop list... */
-  for (nexthop = match->nexthop; nexthop; nexthop = nexthop->next)
+  nexthops_active = 0;
+  for (ALL_NEXTHOPS_RO(match->nexthop, nexthop, tnexthop, recursing))
     if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
-    {
-      /* We are happy with either direct or recursive hexthop */
-      if (nexthop->gate.ipv4.s_addr == sockunion2ip (qgate) ||
-          nexthop->rgate.ipv4.s_addr == sockunion2ip (qgate))
-        return ZEBRA_RIB_FOUND_EXACT;
-      else
       {
+        nexthops_active = 1;
+        if (nexthop->gate.ipv4.s_addr == sockunion2ip (qgate))
+          return ZEBRA_RIB_FOUND_EXACT;
         if (IS_ZEBRA_DEBUG_RIB)
-        {
-          char gate_buf[INET_ADDRSTRLEN], rgate_buf[INET_ADDRSTRLEN], qgate_buf[INET_ADDRSTRLEN];
-          inet_ntop (AF_INET, &nexthop->gate.ipv4.s_addr, gate_buf, INET_ADDRSTRLEN);
-          inet_ntop (AF_INET, &nexthop->rgate.ipv4.s_addr, rgate_buf, INET_ADDRSTRLEN);
-          inet_ntop (AF_INET, &sockunion2ip (qgate), qgate_buf, INET_ADDRSTRLEN);
-          zlog_debug ("%s: qgate == %s, gate == %s, rgate == %s", __func__, qgate_buf, gate_buf, rgate_buf);
-        }
-        return ZEBRA_RIB_FOUND_NOGATE;
+          {
+            char gate_buf[INET_ADDRSTRLEN], qgate_buf[INET_ADDRSTRLEN];
+            inet_ntop (AF_INET, &nexthop->gate.ipv4.s_addr, gate_buf, INET_ADDRSTRLEN);
+            inet_ntop (AF_INET, &sockunion2ip(qgate), qgate_buf, INET_ADDRSTRLEN);
+            zlog_debug ("%s: qgate == %s, %s == %s", __func__,
+                        qgate_buf, recursing ? "rgate" : "gate", gate_buf);
+          }
       }
-    }
+
+  if (nexthops_active)
+    return ZEBRA_RIB_FOUND_NOGATE;
 
   return ZEBRA_RIB_NOTFOUND;
 }
@@ -759,7 +831,8 @@ rib_match_ipv6 (struct in6_addr *addr)
   struct route_table *table;
   struct route_node *rn;
   struct rib *match;
-  struct nexthop *newhop;
+  struct nexthop *newhop, *tnewhop;
+  int recursing;
 
   /* Lookup table.  */
   table = vrf_table (AFI_IP6, SAFI_UNICAST, 0);
@@ -804,7 +877,7 @@ rib_match_ipv6 (struct in6_addr *addr)
 	    return match;
 	  else
 	    {
-	      for (newhop = match->nexthop; newhop; newhop = newhop->next)
+	      for (ALL_NEXTHOPS_RO(match->nexthop, newhop, tnewhop, recursing))
 		if (CHECK_FLAG (newhop->flags, NEXTHOP_FLAG_FIB))
 		  return match;
 	      return NULL;
@@ -966,7 +1039,8 @@ static void
 rib_install_kernel (struct route_node *rn, struct rib *rib)
 {
   int ret = 0;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
 
   /*
    * Make sure we update the FPM any time we send new information to
@@ -988,7 +1062,7 @@ rib_install_kernel (struct route_node *rn, struct rib *rib)
   /* This condition is never met, if we are using rt_socket.c */
   if (ret < 0)
     {
-      for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+      for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
 	UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
     }
 }
@@ -998,7 +1072,8 @@ static int
 rib_uninstall_kernel (struct route_node *rn, struct rib *rib)
 {
   int ret = 0;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
 
   /*
    * Make sure we update the FPM any time we send new information to
@@ -1018,7 +1093,7 @@ rib_uninstall_kernel (struct route_node *rn, struct rib *rib)
 #endif /* HAVE_IPV6 */
     }
 
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB);
 
   return ret;
@@ -1114,7 +1189,8 @@ rib_process (struct route_node *rn)
   struct rib *select = NULL;
   struct rib *del = NULL;
   int installed = 0;
-  struct nexthop *nexthop = NULL;
+  struct nexthop *nexthop = NULL, *tnexthop;
+  int recursing;
   char buf[INET6_ADDRSTRLEN];
   
   assert (rn);
@@ -1237,7 +1313,7 @@ rib_process (struct route_node *rn)
              This makes sure the routes are IN the kernel.
            */
 
-          for (nexthop = select->nexthop; nexthop; nexthop = nexthop->next)
+          for (ALL_NEXTHOPS_RO(select->nexthop, nexthop, tnexthop, recursing))
             if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
             {
               installed = 1;
@@ -1626,7 +1702,6 @@ rib_addnode (struct route_node *rn, struct rib *rib)
 static void
 rib_unlink (struct route_node *rn, struct rib *rib)
 {
-  struct nexthop *nexthop, *next;
   char buf[INET6_ADDRSTRLEN];
   rib_dest_t *dest;
 
@@ -1652,11 +1727,7 @@ rib_unlink (struct route_node *rn, struct rib *rib)
     }
 
   /* free RIB and nexthops */
-  for (nexthop = rib->nexthop; nexthop; nexthop = next)
-    {
-      next = nexthop->next;
-      nexthop_free (nexthop);
-    }
+  nexthops_free(rib->nexthop);
   XFREE (MTYPE_RIB, rib);
 
 }
@@ -1786,11 +1857,12 @@ rib_add_ipv4 (int type, int flags, struct prefix_ipv4 *p,
 
 void rib_dump (const char * func, const struct prefix_ipv4 * p, const struct rib * rib)
 {
-  char straddr1[INET_ADDRSTRLEN], straddr2[INET_ADDRSTRLEN];
-  struct nexthop *nexthop;
+  char straddr[INET_ADDRSTRLEN];
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
 
-  inet_ntop (AF_INET, &p->prefix, straddr1, INET_ADDRSTRLEN);
-  zlog_debug ("%s: dumping RIB entry %p for %s/%d", func, rib, straddr1, p->prefixlen);
+  inet_ntop (AF_INET, &p->prefix, straddr, INET_ADDRSTRLEN);
+  zlog_debug ("%s: dumping RIB entry %p for %s/%d", func, rib, straddr, p->prefixlen);
   zlog_debug
   (
     "%s: refcnt == %lu, uptime == %lu, type == %u, table == %d",
@@ -1817,21 +1889,20 @@ void rib_dump (const char * func, const struct prefix_ipv4 * p, const struct rib
     rib->nexthop_active_num,
     rib->nexthop_fib_num
   );
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
-  {
-    inet_ntop (AF_INET, &nexthop->gate.ipv4.s_addr, straddr1, INET_ADDRSTRLEN);
-    inet_ntop (AF_INET, &nexthop->rgate.ipv4.s_addr, straddr2, INET_ADDRSTRLEN);
-    zlog_debug
-    (
-      "%s: NH %s (%s) with flags %s%s%s",
-      func,
-      straddr1,
-      straddr2,
-      (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE) ? "ACTIVE " : ""),
-      (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB) ? "FIB " : ""),
-      (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE) ? "RECURSIVE" : "")
-    );
-  }
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
+    {
+      inet_ntop (AF_INET, &nexthop->gate.ipv4.s_addr, straddr, INET_ADDRSTRLEN);
+      zlog_debug
+      (
+        "%s: %s %s with flags %s%s%s",
+        func,
+        (recursing ? "  NH" : "NH"),
+        straddr,
+        (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE) ? "ACTIVE " : ""),
+        (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB) ? "FIB " : ""),
+        (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE) ? "RECURSIVE" : "")
+      );
+    }
   zlog_debug ("%s: dump complete", func);
 }
 
@@ -2018,7 +2089,8 @@ rib_delete_ipv4 (int type, int flags, struct prefix_ipv4 *p,
   struct rib *rib;
   struct rib *fib = NULL;
   struct rib *same = NULL;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   char buf1[INET_ADDRSTRLEN];
   char buf2[INET_ADDRSTRLEN];
 
@@ -2085,16 +2157,23 @@ rib_delete_ipv4 (int type, int flags, struct prefix_ipv4 *p,
 	  break;
 	}
       /* Make sure that the route found has the same gateway. */
-      else if (gate == NULL ||
-	       ((nexthop = rib->nexthop) &&
-	        (IPV4_ADDR_SAME (&nexthop->gate.ipv4, gate) ||
-		 IPV4_ADDR_SAME (&nexthop->rgate.ipv4, gate)))) 
+      else
         {
-	  same = rib;
-	  break;
-	}
+          if (gate == NULL)
+            {
+              same = rib;
+              break;
+            }
+          for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
+            if (IPV4_ADDR_SAME (&nexthop->gate.ipv4, gate))
+              {
+                same = rib;
+                break;
+              }
+          if (same)
+            break;
+        }
     }
-
   /* If same type of route can't be found and this message is from
      kernel. */
   if (! same)
@@ -2576,7 +2655,8 @@ rib_delete_ipv6 (int type, int flags, struct prefix_ipv6 *p,
   struct rib *rib;
   struct rib *fib = NULL;
   struct rib *same = NULL;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   char buf1[INET6_ADDRSTRLEN];
   char buf2[INET6_ADDRSTRLEN];
 
@@ -2636,14 +2716,22 @@ rib_delete_ipv6 (int type, int flags, struct prefix_ipv6 *p,
 	  break;
 	}
       /* Make sure that the route found has the same gateway. */
-      else if (gate == NULL ||
-	       ((nexthop = rib->nexthop) &&
-	        (IPV6_ADDR_SAME (&nexthop->gate.ipv6, gate) ||
-		 IPV6_ADDR_SAME (&nexthop->rgate.ipv6, gate))))
-	{
-	  same = rib;
-	  break;
-	}
+      else
+        {
+          if (gate == NULL)
+            {
+              same = rib;
+              break;
+            }
+          for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
+            if (IPV6_ADDR_SAME (&nexthop->gate.ipv6, gate))
+              {
+                same = rib;
+                break;
+              }
+          if (same)
+            break;
+        }
     }
 
   /* If same type of route can't be found and this message is from
diff --git a/zebra/zebra_routemap.c b/zebra/zebra_routemap.c
index b3111b8e..39c7e1bf 100644
--- a/zebra/zebra_routemap.c
+++ b/zebra/zebra_routemap.c
@@ -422,14 +422,10 @@ route_match_ip_next_hop (void *rule, struct prefix *prefix,
       switch (nexthop->type) {
       case NEXTHOP_TYPE_IFINDEX:
       case NEXTHOP_TYPE_IFNAME:
+        /* Interface routes can't match ip next-hop */
+        return RMAP_NOMATCH;
       case NEXTHOP_TYPE_IPV4_IFINDEX:
       case NEXTHOP_TYPE_IPV4_IFNAME:
-        if (nexthop->rtype != NEXTHOP_TYPE_IPV4)
-		return RMAP_NOMATCH;
-        p.family = AF_INET;
-        p.prefix = nexthop->rgate.ipv4;
-        p.prefixlen = IPV4_MAX_BITLEN;
-        break;
       case NEXTHOP_TYPE_IPV4:
         p.family = AF_INET;
         p.prefix = nexthop->gate.ipv4;
@@ -488,14 +484,10 @@ route_match_ip_next_hop_prefix_list (void *rule, struct prefix *prefix,
       switch (nexthop->type) {
       case NEXTHOP_TYPE_IFINDEX:
       case NEXTHOP_TYPE_IFNAME:
+        /* Interface routes can't match ip next-hop */
+        return RMAP_NOMATCH;
       case NEXTHOP_TYPE_IPV4_IFINDEX:
       case NEXTHOP_TYPE_IPV4_IFNAME:
-        if (nexthop->rtype != NEXTHOP_TYPE_IPV4)
-		return RMAP_NOMATCH;
-        p.family = AF_INET;
-        p.prefix = nexthop->rgate.ipv4;
-        p.prefixlen = IPV4_MAX_BITLEN;
-        break;
       case NEXTHOP_TYPE_IPV4:
         p.family = AF_INET;
         p.prefix = nexthop->gate.ipv4;
diff --git a/zebra/zebra_vty.c b/zebra/zebra_vty.c
index a672d422..e1da7df8 100644
--- a/zebra/zebra_vty.c
+++ b/zebra/zebra_vty.c
@@ -533,7 +533,8 @@ static void
 vty_show_ip_route_detail (struct vty *vty, struct route_node *rn)
 {
   struct rib *rib;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
 
   RNODE_FOREACH_RIB (rn, rib)
     {
@@ -582,12 +583,13 @@ vty_show_ip_route_detail (struct vty *vty, struct route_node *rn)
 	  vty_out (vty, " ago%s", VTY_NEWLINE);
 	}
 
-      for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+      for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
 	{
           char addrstr[32];
 
-	  vty_out (vty, "  %c",
-		   CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB) ? '*' : ' ');
+	  vty_out (vty, "  %c%s",
+		   CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB) ? '*' : ' ',
+		   recursing ? "  " : "");
 
 	  switch (nexthop->type)
 	    {
@@ -614,28 +616,8 @@ vty_show_ip_route_detail (struct vty *vty, struct route_node *rn)
 	    vty_out (vty, " inactive");
 
 	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-	    {
-	      vty_out (vty, " (recursive");
-		
-	      switch (nexthop->rtype)
-		{
-		case NEXTHOP_TYPE_IPV4:
-		case NEXTHOP_TYPE_IPV4_IFINDEX:
-		  vty_out (vty, " via %s", inet_ntoa (nexthop->rgate.ipv4));
-		  if (nexthop->rifindex)
-		    vty_out (vty, ", %s", ifindex2ifname (nexthop->rifindex));
-		  vty_out (vty, ")");
-
-		  break;
-		case NEXTHOP_TYPE_IFINDEX:
-		case NEXTHOP_TYPE_IFNAME:
-		  vty_out (vty, " is directly connected, %s)",
-			   ifindex2ifname (nexthop->rifindex));
-		  break;
-		default:
-		  break;
-		}
-	    }
+	    vty_out (vty, " (recursive)");
+
 	  switch (nexthop->type)
             {
             case NEXTHOP_TYPE_IPV4:
@@ -672,12 +654,13 @@ vty_show_ip_route_detail (struct vty *vty, struct route_node *rn)
 static void
 vty_show_ip_route (struct vty *vty, struct route_node *rn, struct rib *rib)
 {
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   int len = 0;
   char buf[BUFSIZ];
 
   /* Nexthop information. */
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     {
       if (nexthop == rib->nexthop)
 	{
@@ -701,7 +684,7 @@ vty_show_ip_route (struct vty *vty, struct route_node *rn, struct rib *rib)
 	vty_out (vty, "  %c%*c",
 		 CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)
 		 ? '*' : ' ',
-		 len - 3, ' ');
+		 len - 3 + (2 * recursing), ' ');
 
       switch (nexthop->type)
 	{
@@ -728,27 +711,8 @@ vty_show_ip_route (struct vty *vty, struct route_node *rn, struct rib *rib)
 	vty_out (vty, " inactive");
 
       if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-	{
-	  vty_out (vty, " (recursive");
-		
-	  switch (nexthop->rtype)
-	    {
-	    case NEXTHOP_TYPE_IPV4:
-	    case NEXTHOP_TYPE_IPV4_IFINDEX:
-	      vty_out (vty, " via %s", inet_ntoa (nexthop->rgate.ipv4));
-	      if (nexthop->rifindex)
-		vty_out (vty, ", %s", ifindex2ifname (nexthop->rifindex));
-	      vty_out (vty, ")");
-	      break;
-	    case NEXTHOP_TYPE_IFINDEX:
-	    case NEXTHOP_TYPE_IFNAME:
-	      vty_out (vty, " is directly connected, %s)",
-		       ifindex2ifname (nexthop->rifindex));
-	      break;
-	    default:
-	      break;
-	    }
-	}
+	vty_out (vty, " (recursive)");
+
       switch (nexthop->type)
         {
           case NEXTHOP_TYPE_IPV4:
@@ -1058,7 +1022,8 @@ vty_show_ip_route_summary (struct vty *vty, struct route_table *table)
         {
 	  rib_cnt[ZEBRA_ROUTE_TOTAL]++;
 	  rib_cnt[rib->type]++;
-	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)) 
+	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)
+	      || nexthop_has_fib_child(nexthop))
 	    {
 	      fib_cnt[ZEBRA_ROUTE_TOTAL]++;
 	      fib_cnt[rib->type]++;
@@ -1067,7 +1032,8 @@ vty_show_ip_route_summary (struct vty *vty, struct route_table *table)
 	      CHECK_FLAG (rib->flags, ZEBRA_FLAG_IBGP)) 
 	    {
 	      rib_cnt[ZEBRA_ROUTE_IBGP]++;
-	      if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)) 
+	      if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)
+		  || nexthop_has_fib_child(nexthop))
 		fib_cnt[ZEBRA_ROUTE_IBGP]++;
 	    }
 	}
@@ -1550,7 +1516,8 @@ static void
 vty_show_ipv6_route_detail (struct vty *vty, struct route_node *rn)
 {
   struct rib *rib;
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   char buf[BUFSIZ];
 
   RNODE_FOREACH_RIB (rn, rib)
@@ -1601,10 +1568,11 @@ vty_show_ipv6_route_detail (struct vty *vty, struct route_node *rn)
 	  vty_out (vty, " ago%s", VTY_NEWLINE);
 	}
 
-      for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+      for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
 	{
-	  vty_out (vty, "  %c",
-		   CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB) ? '*' : ' ');
+	  vty_out (vty, "  %c%s",
+		   CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB) ? '*' : ' ',
+		   recursing ? "  " : "");
 
 	  switch (nexthop->type)
 	    {
@@ -1633,29 +1601,8 @@ vty_show_ipv6_route_detail (struct vty *vty, struct route_node *rn)
 	    vty_out (vty, " inactive");
 
 	  if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-	    {
-	      vty_out (vty, " (recursive");
-		
-	      switch (nexthop->rtype)
-		{
-		case NEXTHOP_TYPE_IPV6:
-		case NEXTHOP_TYPE_IPV6_IFINDEX:
-		case NEXTHOP_TYPE_IPV6_IFNAME:
-		  vty_out (vty, " via %s)",
-			   inet_ntop (AF_INET6, &nexthop->rgate.ipv6,
-				      buf, BUFSIZ));
-		  if (nexthop->rifindex)
-		    vty_out (vty, ", %s", ifindex2ifname (nexthop->rifindex));
-		  break;
-		case NEXTHOP_TYPE_IFINDEX:
-		case NEXTHOP_TYPE_IFNAME:
-		  vty_out (vty, " is directly connected, %s)",
-			   ifindex2ifname (nexthop->rifindex));
-		  break;
-		default:
-		  break;
-		}
-	    }
+	    vty_out (vty, " (recursive)");
+
 	  vty_out (vty, "%s", VTY_NEWLINE);
 	}
       vty_out (vty, "%s", VTY_NEWLINE);
@@ -1666,12 +1613,13 @@ static void
 vty_show_ipv6_route (struct vty *vty, struct route_node *rn,
 		     struct rib *rib)
 {
-  struct nexthop *nexthop;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
   int len = 0;
   char buf[BUFSIZ];
 
   /* Nexthop information. */
-  for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
+  for (ALL_NEXTHOPS_RO(rib->nexthop, nexthop, tnexthop, recursing))
     {
       if (nexthop == rib->nexthop)
 	{
@@ -1695,7 +1643,7 @@ vty_show_ipv6_route (struct vty *vty, struct route_node *rn,
 	vty_out (vty, "  %c%*c",
 		 CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB)
 		 ? '*' : ' ',
-		 len - 3, ' ');
+		 len - 3 + (2 * recursing), ' ');
 
       switch (nexthop->type)
 	{
@@ -1724,29 +1672,7 @@ vty_show_ipv6_route (struct vty *vty, struct route_node *rn,
 	vty_out (vty, " inactive");
 
       if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-	{
-	  vty_out (vty, " (recursive");
-		
-	  switch (nexthop->rtype)
-	    {
-	    case NEXTHOP_TYPE_IPV6:
-	    case NEXTHOP_TYPE_IPV6_IFINDEX:
-	    case NEXTHOP_TYPE_IPV6_IFNAME:
-	      vty_out (vty, " via %s)",
-		       inet_ntop (AF_INET6, &nexthop->rgate.ipv6,
-				  buf, BUFSIZ));
-	      if (nexthop->rifindex)
-		vty_out (vty, ", %s", ifindex2ifname (nexthop->rifindex));
-	      break;
-	    case NEXTHOP_TYPE_IFINDEX:
-	    case NEXTHOP_TYPE_IFNAME:
-	      vty_out (vty, " is directly connected, %s)",
-		       ifindex2ifname (nexthop->rifindex));
-	      break;
-	    default:
-	      break;
-	    }
-	}
+	vty_out (vty, " (recursive)");
 
       if (CHECK_FLAG (rib->flags, ZEBRA_FLAG_BLACKHOLE))
        vty_out (vty, ", bh");
diff --git a/zebra/zserv.c b/zebra/zserv.c
index 11829378..5df521b0 100644
--- a/zebra/zserv.c
+++ b/zebra/zserv.c
@@ -389,7 +389,8 @@ zsend_route_multipath (int cmd, struct zserv *client, struct prefix *p,
   
   for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
     {
-      if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
+      if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB)
+          || nexthop_has_fib_child(nexthop))
         {
           SET_FLAG (zapi_flags, ZAPI_MESSAGE_NEXTHOP);
           SET_FLAG (zapi_flags, ZAPI_MESSAGE_IFINDEX);
@@ -488,6 +489,9 @@ zsend_ipv6_nexthop_lookup (struct zserv *client, struct in6_addr *addr)
       num = 0;
       nump = stream_get_endp(s);
       stream_putc (s, 0);
+      /* Only non-recursive routes are elegible to resolve nexthop we
+       * are looking up. Therefore, we will just iterate over the top
+       * chain of nexthops. */
       for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
 	if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
 	  {
@@ -554,6 +558,9 @@ zsend_ipv4_nexthop_lookup (struct zserv *client, struct in_addr addr)
       num = 0;
       nump = stream_get_endp(s);
       stream_putc (s, 0);
+      /* Only non-recursive routes are elegible to resolve the nexthop we
+       * are looking up. Therefore, we will just iterate over the top
+       * chain of nexthops. */
       for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
 	if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
 	  {
@@ -619,7 +626,8 @@ zsend_ipv4_import_lookup (struct zserv *client, struct prefix_ipv4 *p)
       nump = stream_get_endp(s);
       stream_putc (s, 0);
       for (nexthop = rib->nexthop; nexthop; nexthop = nexthop->next)
-	if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_FIB))
+	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB)
+            || nexthop_has_fib_child(nexthop))
 	  {
 	    stream_putc (s, nexthop->type);
 	    switch (nexthop->type)