Merge branch '-renato' into stable/2.0

This contains bgp memory leak fixes as well as cleanups to VRF/namespace
handling and has been run through extended testing in Cumulus' testbed:

Tested-by: Donald Sharp <sharpd@cumulusnetworks.com>

10 files changed, 236 insertions, 833 deletions

diff --git a/lib/command.c b/lib/command.c
index cfadfcef6..0b0614b80 100644
--- a/lib/command.c
+++ b/lib/command.c
@@ -4436,4 +4436,6 @@ cmd_terminate ()
     XFREE (MTYPE_HOST, host.motdfile);
   if (host.config)
     XFREE (MTYPE_HOST, host.config);
+
+  qobj_finish ();
 }
diff --git a/lib/if.c b/lib/if.c
index e745dc902..d943d599a 100644
--- a/lib/if.c
+++ b/lib/if.c
@@ -307,13 +307,11 @@ if_lookup_by_name_vrf (const char *name, vrf_id_t vrf_id)
 struct interface *
 if_lookup_by_name_all_vrf (const char *name)
 {
+  struct vrf *vrf;
   struct interface *ifp;
-  struct vrf *vrf = NULL;
-  vrf_iter_t iter;
 
-  for (iter = vrf_first (); iter != VRF_ITER_INVALID; iter = vrf_next (iter))
+  RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id)
     {
-      vrf = vrf_iter2vrf (iter);
       ifp = if_lookup_by_name_vrf (name, vrf->vrf_id);
       if (ifp)
 	return ifp;
@@ -489,18 +487,16 @@ struct interface *
 if_get_by_name_len_vrf (const char *name, size_t namelen, vrf_id_t vrf_id, int vty)
 {
   struct interface *ifp;
+  struct vrf *vrf;
   struct listnode *node;
-  struct vrf *vrf = NULL;
-  vrf_iter_t iter;
 
   ifp = if_lookup_by_name_len_vrf (name, namelen, vrf_id);
   if (ifp)
     return ifp;
 
   /* Didn't find the interface on that vrf. Defined on a different one? */ 
-  for (iter = vrf_first (); iter != VRF_ITER_INVALID; iter = vrf_next (iter))
+  RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id)
     {
-      vrf = vrf_iter2vrf(iter);
       for (ALL_LIST_ELEMENTS_RO (vrf_iflist (vrf->vrf_id), node, ifp))
 	{
 	  if (!memcmp(name, ifp->name, namelen) && (ifp->name[namelen] == '\0'))
@@ -665,14 +661,13 @@ if_dump (const struct interface *ifp)
 void
 if_dump_all (void)
 {
-  struct list *intf_list;
+  struct vrf *vrf;
   struct listnode *node;
   void *p;
-  vrf_iter_t iter;
 
-  for (iter = vrf_first (); iter != VRF_ITER_INVALID; iter = vrf_next (iter))
-    if ((intf_list = vrf_iter2iflist (iter)) != NULL)
-      for (ALL_LIST_ELEMENTS_RO (intf_list, node, p))
+  RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id)
+    if (vrf->iflist != NULL)
+      for (ALL_LIST_ELEMENTS_RO (vrf->iflist, node, p))
         if_dump (p);
 }
 
@@ -839,60 +834,6 @@ ALIAS (no_interface,
        "Interface's name\n"
        VRF_CMD_HELP_STR)
 
-DEFUN (vrf,
-       vrf_cmd,
-       "vrf NAME",
-       "Select a VRF to configure\n"
-       "VRF's name\n")
-{
-  struct vrf *vrfp;
-  size_t sl;
-
-  if ((sl = strlen(argv[0])) > VRF_NAMSIZ)
-    {
-      vty_out (vty, "%% VRF name %s is invalid: length exceeds "
-		    "%d characters%s",
-	       argv[0], VRF_NAMSIZ, VTY_NEWLINE);
-      return CMD_WARNING;
-    }
-
-  vrfp = vrf_get (VRF_UNKNOWN, argv[0]);
-
-  VTY_PUSH_CONTEXT_COMPAT (VRF_NODE, vrfp);
-
-  return CMD_SUCCESS;
-}
-
-DEFUN_NOSH (no_vrf,
-           no_vrf_cmd,
-           "no vrf NAME",
-           NO_STR
-           "Delete a pseudo VRF's configuration\n"
-           "VRF's name\n")
-{
-  struct vrf *vrfp;
-
-  vrfp = vrf_list_lookup_by_name (argv[0]);
-
-  if (vrfp == NULL)
-    {
-      vty_out (vty, "%% VRF %s does not exist%s", argv[0], VTY_NEWLINE);
-      return CMD_WARNING;
-    }
-
-  if (CHECK_FLAG (vrfp->status, VRF_ACTIVE))
-    {
-      vty_out (vty, "%% Only inactive VRFs can be deleted%s",
-	      VTY_NEWLINE);
-      return CMD_WARNING;
-    }
-
-  vrf_delete(vrfp);
-
-  return CMD_SUCCESS;
-}
-
-
 /* For debug purpose. */
 DEFUN (show_address,
        show_address_cmd,
@@ -938,24 +879,22 @@ DEFUN (show_address_vrf_all,
        "address\n"
        VRF_ALL_CMD_HELP_STR)
 {
-  struct list *intf_list;
+  struct vrf *vrf;
   struct listnode *node;
   struct listnode *node2;
   struct interface *ifp;
   struct connected *ifc;
   struct prefix *p;
-  vrf_iter_t iter;
 
-  for (iter = vrf_first (); iter != VRF_ITER_INVALID; iter = vrf_next (iter))
+  RB_FOREACH (vrf, vrf_name_head, &vrfs_by_name)
     {
-      intf_list = vrf_iter2iflist (iter);
-      if (!intf_list || !listcount (intf_list))
+      if (!vrf->iflist || !listcount (vrf->iflist))
         continue;
 
-      vty_out (vty, "%sVRF %u%s%s", VTY_NEWLINE, vrf_iter2id (iter),
-               VTY_NEWLINE, VTY_NEWLINE);
+      vty_out (vty, "%sVRF %u%s%s", VTY_NEWLINE, vrf->vrf_id, VTY_NEWLINE,
+	       VTY_NEWLINE);
 
-      for (ALL_LIST_ELEMENTS_RO (intf_list, node, ifp))
+      for (ALL_LIST_ELEMENTS_RO (vrf->iflist, node, ifp))
         {
           for (ALL_LIST_ELEMENTS_RO (ifp->connected, node2, ifc))
             {
diff --git a/lib/ns.c b/lib/ns.c
index 556350ed1..08432764d 100644
--- a/lib/ns.c
+++ b/lib/ns.c
@@ -31,8 +31,6 @@
 
 #include "if.h"
 #include "ns.h"
-#include "prefix.h"
-#include "table.h"
 #include "log.h"
 #include "memory.h"
 
@@ -43,6 +41,13 @@ DEFINE_MTYPE_STATIC(LIB, NS,        "Logical-Router")
 DEFINE_MTYPE_STATIC(LIB, NS_NAME,   "Logical-Router Name")
 DEFINE_MTYPE_STATIC(LIB, NS_BITMAP, "Logical-Router bit-map")
 
+static __inline int ns_compare (struct ns *, struct ns *);
+static struct ns *ns_lookup (ns_id_t);
+
+RB_GENERATE (ns_head, ns, entry, ns_compare)
+
+struct ns_head ns_tree = RB_INITIALIZER (&ns_tree);
+
 #ifndef CLONE_NEWNET
 #define CLONE_NEWNET 0x40000000 /* New network namespace (lo, device, names sockets, etc) */
 #endif
@@ -91,22 +96,6 @@ static int have_netns(void)
 #endif
 }
 
-struct ns
-{
-  /* Identifier, same as the vector index */
-  ns_id_t ns_id;
-  /* Name */
-  char *name;
-  /* File descriptor */
-  int fd;
-
-  /* Master list of interfaces belonging to this NS */
-  struct list *iflist;
-
-  /* User data */
-  void *info;
-};
-
 /* Holding NS hooks  */
 struct ns_master
 {
@@ -116,44 +105,30 @@ struct ns_master
   int (*ns_disable_hook) (ns_id_t, void **);
 } ns_master = {0,};
 
-/* NS table */
-struct route_table *ns_table = NULL;
-
 static int ns_is_enabled (struct ns *ns);
 static int ns_enable (struct ns *ns);
 static void ns_disable (struct ns *ns);
 
-
-/* Build the table key */
-static void
-ns_build_key (ns_id_t ns_id, struct prefix *p)
+static __inline int
+ns_compare(struct ns *a, struct ns *b)
 {
-  p->family = AF_INET;
-  p->prefixlen = IPV4_MAX_BITLEN;
-  p->u.prefix4.s_addr = ns_id;
+  return (a->ns_id - b->ns_id);
 }
 
 /* Get a NS. If not found, create one. */
 static struct ns *
 ns_get (ns_id_t ns_id)
 {
-  struct prefix p;
-  struct route_node *rn;
   struct ns *ns;
 
-  ns_build_key (ns_id, &p);
-  rn = route_node_get (ns_table, &p);
-  if (rn->info)
-    {
-      ns = (struct ns *)rn->info;
-      route_unlock_node (rn); /* get */
-      return ns;
-    }
+  ns = ns_lookup (ns_id);
+  if (ns)
+    return (ns);
 
   ns = XCALLOC (MTYPE_NS, sizeof (struct ns));
   ns->ns_id = ns_id;
   ns->fd = -1;
-  rn->info = ns;
+  RB_INSERT (ns_head, &ns_tree, ns);
 
   /*
    * Initialize interfaces.
@@ -188,6 +163,7 @@ ns_delete (struct ns *ns)
    */
   //if_terminate (&ns->iflist);
 
+  RB_REMOVE (ns_head, &ns_tree, ns);
   if (ns->name)
     XFREE (MTYPE_NS_NAME, ns->name);
 
@@ -198,18 +174,9 @@ ns_delete (struct ns *ns)
 static struct ns *
 ns_lookup (ns_id_t ns_id)
 {
-  struct prefix p;
-  struct route_node *rn;
-  struct ns *ns = NULL;
-
-  ns_build_key (ns_id, &p);
-  rn = route_node_lookup (ns_table, &p);
-  if (rn)
-    {
-      ns = (struct ns *)rn->info;
-      route_unlock_node (rn); /* lookup */
-    }
-  return ns;
+  struct ns ns;
+  ns.ns_id = ns_id;
+  return (RB_FIND (ns_head, &ns_tree, &ns));
 }
 
 /*
@@ -310,217 +277,6 @@ ns_add_hook (int type, int (*func)(ns_id_t, void **))
   }
 }
 
-/* Return the iterator of the first NS. */
-ns_iter_t
-ns_first (void)
-{
-  struct route_node *rn;
-
-  for (rn = route_top (ns_table); rn; rn = route_next (rn))
-    if (rn->info)
-      {
-        route_unlock_node (rn); /* top/next */
-        return (ns_iter_t)rn;
-      }
-  return NS_ITER_INVALID;
-}
-
-/* Return the next NS iterator to the given iterator. */
-ns_iter_t
-ns_next (ns_iter_t iter)
-{
-  struct route_node *rn = NULL;
-
-  /* Lock it first because route_next() will unlock it. */
-  if (iter != NS_ITER_INVALID)
-    rn = route_next (route_lock_node ((struct route_node *)iter));
-
-  for (; rn; rn = route_next (rn))
-    if (rn->info)
-      {
-        route_unlock_node (rn); /* next */
-        return (ns_iter_t)rn;
-      }
-  return NS_ITER_INVALID;
-}
-
-/* Return the NS iterator of the given NS ID. If it does not exist,
- * the iterator of the next existing NS is returned. */
-ns_iter_t
-ns_iterator (ns_id_t ns_id)
-{
-  struct prefix p;
-  struct route_node *rn;
-
-  ns_build_key (ns_id, &p);
-  rn = route_node_get (ns_table, &p);
-  if (rn->info)
-    {
-      /* OK, the NS exists. */
-      route_unlock_node (rn); /* get */
-      return (ns_iter_t)rn;
-    }
-
-  /* Find the next NS. */
-  for (rn = route_next (rn); rn; rn = route_next (rn))
-    if (rn->info)
-      {
-        route_unlock_node (rn); /* next */
-        return (ns_iter_t)rn;
-      }
-
-  return NS_ITER_INVALID;
-}
-
-/* Obtain the NS ID from the given NS iterator. */
-ns_id_t
-ns_iter2id (ns_iter_t iter)
-{
-  struct route_node *rn = (struct route_node *) iter;
-  return (rn && rn->info) ? ((struct ns *)rn->info)->ns_id : NS_DEFAULT;
-}
-
-/* Obtain the data pointer from the given NS iterator. */
-void *
-ns_iter2info (ns_iter_t iter)
-{
-  struct route_node *rn = (struct route_node *) iter;
-  return (rn && rn->info) ? ((struct ns *)rn->info)->info : NULL;
-}
-
-/* Obtain the interface list from the given NS iterator. */
-struct list *
-ns_iter2iflist (ns_iter_t iter)
-{
-  struct route_node *rn = (struct route_node *) iter;
-  return (rn && rn->info) ? ((struct ns *)rn->info)->iflist : NULL;
-}
-
-/* Get the data pointer of the specified NS. If not found, create one. */
-void *
-ns_info_get (ns_id_t ns_id)
-{
-  struct ns *ns = ns_get (ns_id);
-  return ns->info;
-}
-
-/* Look up the data pointer of the specified NS. */
-void *
-ns_info_lookup (ns_id_t ns_id)
-{
-  struct ns *ns = ns_lookup (ns_id);
-  return ns ? ns->info : NULL;
-}
-
-/* Look up the interface list in a NS. */
-struct list *
-ns_iflist (ns_id_t ns_id)
-{
-   struct ns * ns = ns_lookup (ns_id);
-   return ns ? ns->iflist : NULL;
-}
-
-/* Get the interface list of the specified NS. Create one if not find. */
-struct list *
-ns_iflist_get (ns_id_t ns_id)
-{
-   struct ns * ns = ns_get (ns_id);
-   return ns->iflist;
-}
-
-/*
- * NS bit-map
- */
-
-#define NS_BITMAP_NUM_OF_GROUPS            8
-#define NS_BITMAP_NUM_OF_BITS_IN_GROUP \
-    (UINT16_MAX / NS_BITMAP_NUM_OF_GROUPS)
-#define NS_BITMAP_NUM_OF_BYTES_IN_GROUP \
-    (NS_BITMAP_NUM_OF_BITS_IN_GROUP / CHAR_BIT + 1) /* +1 for ensure */
-
-#define NS_BITMAP_GROUP(_id) \
-    ((_id) / NS_BITMAP_NUM_OF_BITS_IN_GROUP)
-#define NS_BITMAP_BIT_OFFSET(_id) \
-    ((_id) % NS_BITMAP_NUM_OF_BITS_IN_GROUP)
-
-#define NS_BITMAP_INDEX_IN_GROUP(_bit_offset) \
-    ((_bit_offset) / CHAR_BIT)
-#define NS_BITMAP_FLAG(_bit_offset) \
-    (((u_char)1) << ((_bit_offset) % CHAR_BIT))
-
-struct ns_bitmap
-{
-  u_char *groups[NS_BITMAP_NUM_OF_GROUPS];
-};
-
-ns_bitmap_t
-ns_bitmap_init (void)
-{
-  return (ns_bitmap_t) XCALLOC (MTYPE_NS_BITMAP, sizeof (struct ns_bitmap));
-}
-
-void
-ns_bitmap_free (ns_bitmap_t bmap)
-{
-  struct ns_bitmap *bm = (struct ns_bitmap *) bmap;
-  int i;
-
-  if (bmap == NS_BITMAP_NULL)
-    return;
-
-  for (i = 0; i < NS_BITMAP_NUM_OF_GROUPS; i++)
-    if (bm->groups[i])
-      XFREE (MTYPE_NS_BITMAP, bm->groups[i]);
-
-  XFREE (MTYPE_NS_BITMAP, bm);
-}
-
-void
-ns_bitmap_set (ns_bitmap_t bmap, ns_id_t ns_id)
-{
-  struct ns_bitmap *bm = (struct ns_bitmap *) bmap;
-  u_char group = NS_BITMAP_GROUP (ns_id);
-  u_char offset = NS_BITMAP_BIT_OFFSET (ns_id);
-
-  if (bmap == NS_BITMAP_NULL)
-    return;
-
-  if (bm->groups[group] == NULL)
-    bm->groups[group] = XCALLOC (MTYPE_NS_BITMAP,
-                                 NS_BITMAP_NUM_OF_BYTES_IN_GROUP);
-
-  SET_FLAG (bm->groups[group][NS_BITMAP_INDEX_IN_GROUP (offset)],
-            NS_BITMAP_FLAG (offset));
-}
-
-void
-ns_bitmap_unset (ns_bitmap_t bmap, ns_id_t ns_id)
-{
-  struct ns_bitmap *bm = (struct ns_bitmap *) bmap;
-  u_char group = NS_BITMAP_GROUP (ns_id);
-  u_char offset = NS_BITMAP_BIT_OFFSET (ns_id);
-
-  if (bmap == NS_BITMAP_NULL || bm->groups[group] == NULL)
-    return;
-
-  UNSET_FLAG (bm->groups[group][NS_BITMAP_INDEX_IN_GROUP (offset)],
-              NS_BITMAP_FLAG (offset));
-}
-
-int
-ns_bitmap_check (ns_bitmap_t bmap, ns_id_t ns_id)
-{
-  struct ns_bitmap *bm = (struct ns_bitmap *) bmap;
-  u_char group = NS_BITMAP_GROUP (ns_id);
-  u_char offset = NS_BITMAP_BIT_OFFSET (ns_id);
-
-  if (bmap == NS_BITMAP_NULL || bm->groups[group] == NULL)
-    return 0;
-
-  return CHECK_FLAG (bm->groups[group][NS_BITMAP_INDEX_IN_GROUP (offset)],
-                     NS_BITMAP_FLAG (offset)) ? 1 : 0;
-}
-
 /*
  * NS realization with NETNS
  */
@@ -641,17 +397,17 @@ static struct cmd_node ns_node =
 static int
 ns_config_write (struct vty *vty)
 {
-  struct route_node *rn;
   struct ns *ns;
   int write = 0;
 
-  for (rn = route_top (ns_table); rn; rn = route_next (rn))
-    if ((ns = rn->info) != NULL &&
-        ns->ns_id != NS_DEFAULT && ns->name)
-      {
-        vty_out (vty, "logical-router %u netns %s%s", ns->ns_id, ns->name, VTY_NEWLINE);
-        write++;
-      }
+  RB_FOREACH (ns, ns_head, &ns_tree) {
+      if (ns->ns_id == NS_DEFAULT || ns->name == NULL)
+	continue;
+
+      vty_out (vty, "logical-router %u netns %s%s", ns->ns_id, ns->name,
+	       VTY_NEWLINE);
+      write = 1;
+  }
 
   return write;
 }
@@ -662,9 +418,6 @@ ns_init (void)
 {
   struct ns *default_ns;
 
-  /* Allocate NS table.  */
-  ns_table = route_table_init ();
-
   /* The default NS always exists. */
   default_ns = ns_get (NS_DEFAULT);
   if (!default_ns)
@@ -696,15 +449,10 @@ ns_init (void)
 void
 ns_terminate (void)
 {
-  struct route_node *rn;
   struct ns *ns;
 
-  for (rn = route_top (ns_table); rn; rn = route_next (rn))
-    if ((ns = rn->info) != NULL)
-      ns_delete (ns);
-
-  route_table_finish (ns_table);
-  ns_table = NULL;
+  while ((ns = RB_ROOT (&ns_tree)) != NULL)
+    ns_delete (ns);
 }
 
 /* Create a socket for the NS. */
diff --git a/lib/ns.h b/lib/ns.h
index 3fac73986..2a7be1ef8 100644
--- a/lib/ns.h
+++ b/lib/ns.h
@@ -23,6 +23,7 @@
 #ifndef _ZEBRA_NS_H
 #define _ZEBRA_NS_H
 
+#include "openbsd-tree.h"
 #include "linklist.h"
 
 typedef u_int16_t ns_id_t;
@@ -30,15 +31,32 @@ typedef u_int16_t ns_id_t;
 /* The default NS ID */
 #define NS_DEFAULT 0
 
-/*
- * The command strings
- */
+/* Default netns directory (Linux) */
 #define NS_RUN_DIR         "/var/run/netns"
-#define NS_CMD_STR         "logical-router <0-65535>"
-#define NS_CMD_HELP_STR    "Specify the Logical-Router\nThe Logical-Router ID\n"
 
-#define NS_ALL_CMD_STR         "logical-router all"
-#define NS_ALL_CMD_HELP_STR    "Specify the logical-router\nAll logical-router's\n"
+struct ns
+{
+  RB_ENTRY(ns) entry;
+
+  /* Identifier, same as the vector index */
+  ns_id_t ns_id;
+
+  /* Name */
+  char *name;
+
+  /* File descriptor */
+  int fd;
+
+  /* Master list of interfaces belonging to this NS */
+  struct list *iflist;
+
+  /* User data */
+  void *info;
+};
+RB_HEAD (ns_head, ns);
+RB_PROTOTYPE (ns_head, ns, entry, ns_compare)
+
+extern struct ns_head ns_tree;
 
 /*
  * NS hooks
@@ -60,71 +78,6 @@ typedef u_int16_t ns_id_t;
 extern void ns_add_hook (int, int (*)(ns_id_t, void **));
 
 /*
- * NS iteration
- */
-
-typedef void *              ns_iter_t;
-#define NS_ITER_INVALID    NULL    /* invalid value of the iterator */
-
-/*
- * NS iteration utilities. Example for the usage:
- *
- *   ns_iter_t iter = ns_first();
- *   for (; iter != NS_ITER_INVALID; iter = ns_next (iter))
- *
- * or
- *
- *   ns_iter_t iter = ns_iterator (<a given NS ID>);
- *   for (; iter != NS_ITER_INVALID; iter = ns_next (iter))
- */
-
-/* Return the iterator of the first NS. */
-extern ns_iter_t ns_first (void);
-/* Return the next NS iterator to the given iterator. */
-extern ns_iter_t ns_next (ns_iter_t);
-/* Return the NS iterator of the given NS ID. If it does not exist,
- * the iterator of the next existing NS is returned. */
-extern ns_iter_t ns_iterator (ns_id_t);
-
-/*
- * NS iterator to properties
- */
-extern ns_id_t ns_iter2id (ns_iter_t);
-extern void *ns_iter2info (ns_iter_t);
-extern struct list *ns_iter2iflist (ns_iter_t);
-
-/*
- * Utilities to obtain the user data
- */
-
-/* Get the data pointer of the specified NS. If not found, create one. */
-extern void *ns_info_get (ns_id_t);
-/* Look up the data pointer of the specified NS. */
-extern void *ns_info_lookup (ns_id_t);
-
-/*
- * Utilities to obtain the interface list
- */
-
-/* Look up the interface list of the specified NS. */
-extern struct list *ns_iflist (ns_id_t);
-/* Get the interface list of the specified NS. Create one if not find. */
-extern struct list *ns_iflist_get (ns_id_t);
-
-/*
- * NS bit-map: maintaining flags, one bit per NS ID
- */
-
-typedef void *              ns_bitmap_t;
-#define NS_BITMAP_NULL     NULL
-
-extern ns_bitmap_t ns_bitmap_init (void);
-extern void ns_bitmap_free (ns_bitmap_t);
-extern void ns_bitmap_set (ns_bitmap_t, ns_id_t);
-extern void ns_bitmap_unset (ns_bitmap_t, ns_id_t);
-extern int ns_bitmap_check (ns_bitmap_t, ns_id_t);
-
-/*
  * NS initializer/destructor
  */
 /* Please add hooks before calling ns_init(). */
diff --git a/lib/qobj.c b/lib/qobj.c
index 65b537f96..f64972e32 100644
--- a/lib/qobj.c
+++ b/lib/qobj.c
@@ -78,6 +78,7 @@ void qobj_init (void)
 
 void qobj_finish (void)
 {
+  hash_clean (nodes, NULL);
   hash_free (nodes);
   nodes = NULL;
 }
diff --git a/lib/table.c b/lib/table.c
index d0e084ead..5133ef697 100644
--- a/lib/table.c
+++ b/lib/table.c
@@ -494,7 +494,7 @@ route_table_count (const struct route_table *table)
  *
  * Default function for creating a route node.
  */
-static struct route_node *
+struct route_node *
 route_node_create (route_table_delegate_t *delegate,
 		   struct route_table *table)
 {
@@ -508,7 +508,7 @@ route_node_create (route_table_delegate_t *delegate,
  *
  * Default function for destroying a route node.
  */
-static void
+void
 route_node_destroy (route_table_delegate_t *delegate,
 		    struct route_table *table, struct route_node *node)
 {
diff --git a/lib/table.h b/lib/table.h
index e6cdcfef1..78bf5da74 100644
--- a/lib/table.h
+++ b/lib/table.h
@@ -169,6 +169,11 @@ extern struct route_node *route_node_match_ipv6 (const struct route_table *,
 
 extern unsigned long route_table_count (const struct route_table *);
 
+extern struct route_node *route_node_create (route_table_delegate_t *,
+					     struct route_table *);
+extern void route_node_destroy (route_table_delegate_t *,
+				struct route_table *, struct route_node *);
+
 extern struct route_node *
 route_table_get_next (const struct route_table *table, struct prefix *p);
 extern int
diff --git a/lib/vrf.c b/lib/vrf.c
index 63adea4ae..39d8a89a7 100644
--- a/lib/vrf.c
+++ b/lib/vrf.c
@@ -35,6 +35,15 @@ DEFINE_MTYPE_STATIC(LIB, VRF_BITMAP, "VRF bit-map")
 
 DEFINE_QOBJ_TYPE(vrf)
 
+static __inline int vrf_id_compare (struct vrf *, struct vrf *);
+static __inline int vrf_name_compare (struct vrf *, struct vrf *);
+
+RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare)
+RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare)
+
+struct vrf_id_head vrfs_by_id = RB_INITIALIZER (&vrfs_by_id);
+struct vrf_name_head vrfs_by_name = RB_INITIALIZER (&vrfs_by_name);
+
 /*
  * Turn on/off debug code
  * for vrf.
@@ -44,44 +53,34 @@ int debug_vrf = 0;
 /* Holding VRF hooks  */
 struct vrf_master
 {
-  int (*vrf_new_hook) (vrf_id_t, const char *, void **);
-  int (*vrf_delete_hook) (vrf_id_t, const char *, void **);
-  int (*vrf_enable_hook) (vrf_id_t, const char *, void **);
-  int (*vrf_disable_hook) (vrf_id_t, const char *, void **);
+  int (*vrf_new_hook) (struct vrf *);
+  int (*vrf_delete_hook) (struct vrf *);
+  int (*vrf_enable_hook) (struct vrf *);
+  int (*vrf_disable_hook) (struct vrf *);
 } vrf_master = {0,};
 
-/* VRF table */
-struct route_table *vrf_table = NULL;
-
-/* VRF is part of a list too to store it before its actually active */
-struct list *vrf_list;
-
 static int vrf_is_enabled (struct vrf *vrf);
 static void vrf_disable (struct vrf *vrf);
 
 /* VRF list existance check by name. */
 struct vrf *
-vrf_list_lookup_by_name (const char *name)
+vrf_lookup_by_name (const char *name)
 {
-  struct listnode *node;
-  struct vrf *vrfp;
+  struct vrf vrf;
+  strlcpy (vrf.name, name, sizeof (vrf.name));
+  return (RB_FIND (vrf_name_head, &vrfs_by_name, &vrf));
+}
 
-  if (name)
-    for (ALL_LIST_ELEMENTS_RO (vrf_list, node, vrfp))
-      {
-        if (strcmp(name, vrfp->name) == 0)
-          return vrfp;
-      }
-  return NULL;
+static __inline int
+vrf_id_compare (struct vrf *a, struct vrf *b)
+{
+  return (a->vrf_id - b->vrf_id);
 }
 
-/* Build the table key */
-static void
-vrf_build_key (vrf_id_t vrf_id, struct prefix *p)
+static int
+vrf_name_compare (struct vrf *a, struct vrf *b)
 {
-  p->family = AF_INET;
-  p->prefixlen = IPV4_MAX_BITLEN;
-  p->u.prefix4.s_addr = vrf_id;
+  return strcmp (a->name, b->name);
 }
 
 /* Get a VRF. If not found, create one.
@@ -94,177 +93,59 @@ vrf_build_key (vrf_id_t vrf_id, struct prefix *p)
 struct vrf *
 vrf_get (vrf_id_t vrf_id, const char *name)
 {
-  struct prefix p;
-  struct route_node *rn = NULL;
   struct vrf *vrf = NULL;
+  int new = 0;
 
   if (debug_vrf)
     zlog_debug ("VRF_GET: %s(%d)", name, vrf_id);
 
-  /*
-   * Nothing to see, move along here
-   */
+  /* Nothing to see, move along here */
   if (!name && vrf_id == VRF_UNKNOWN)
     return NULL;
 
-  /*
-   * Valid vrf name and unknown vrf_id case
-   *
-   * This is called when we are configured from
-   * the cli but we have no kernel information yet.
-   */
-  if (name && vrf_id == VRF_UNKNOWN)
-    {
-      vrf = vrf_list_lookup_by_name (name);
-      if (vrf)
-	return vrf;
+  /* Try to find VRF both by ID and name */
+  if (vrf_id != VRF_UNKNOWN)
+    vrf = vrf_lookup_by_id (vrf_id);
+  if (! vrf && name)
+    vrf = vrf_lookup_by_name (name);
 
+  if (vrf == NULL)
+    {
       vrf = XCALLOC (MTYPE_VRF, sizeof (struct vrf));
-      if (debug_vrf)
-        zlog_debug ("VRF(%u) %s is created.",
-		    vrf_id, (name) ? name : "(NULL)");
-      strcpy (vrf->name, name);
-      listnode_add_sort (vrf_list, vrf);
+      vrf->vrf_id = VRF_UNKNOWN;
       if_init (&vrf->iflist);
       QOBJ_REG (vrf, vrf);
-      if (vrf_master.vrf_new_hook)
-	{
-	  (*vrf_master.vrf_new_hook) (vrf_id, name, &vrf->info);
+      new = 1;
 
-	  if (debug_vrf && vrf->info)
-	    zlog_info ("zvrf is created.");
-	}
       if (debug_vrf)
-        zlog_debug("Vrf Created: %p", vrf);
-      return vrf;
+	zlog_debug ("VRF(%u) %s is created.",
+		    vrf_id, (name) ? name : "(NULL)");
     }
-  /*
-   * Valid vrf name and valid vrf_id case
-   *
-   * This can be passed from the kernel
-   */
-  else if (name && vrf_id != VRF_UNKNOWN)
+
+  /* Set identifier */
+  if (vrf_id != VRF_UNKNOWN && vrf->vrf_id == VRF_UNKNOWN)
     {
-      vrf = vrf_list_lookup_by_name (name);
-      if (vrf)
-	{
-          /*
-           * If the passed in vrf_id and name match
-	   * return, nothing to do here.
-           */
-	  if (vrf->vrf_id == vrf_id)
-	    return vrf;
-
-	  /*
-	   * Now we have a situation where we've had a
-	   * vrf created, but not yet created the vrf_id route
-	   * node, let's do so and match the code up.
-           */
-	  vrf_build_key (vrf_id, &p);
-	  rn = route_node_get (vrf_table, &p);
-
-	  rn->info = vrf;
-	  vrf->node = rn;
-	  vrf->vrf_id = vrf_id;
-	  if (vrf_master.vrf_new_hook)
-	    (*vrf_master.vrf_new_hook) (vrf_id, name, &vrf->info);
-
-          if (debug_vrf)
-            zlog_debug("Vrf found matched stuff up: %p", vrf);
-
-	  return vrf;
-	}
-      else
-	{
-	  /*
-	   * We can have 1 of two situations here
-	   * We've already been told about the vrf_id
-	   * or we haven't.
-	   */
-	  vrf_build_key (vrf_id, &p);
-          rn = route_node_get (vrf_table, &p);
-	  if (rn->info)
-	    {
-	      vrf = rn->info;
-	      route_unlock_node (rn);
-	      /*
-	       * We know at this point that the vrf->name is not
-	       * right because we would have caught it above.
-	       * so let's set it.
-	       */
-	      strcpy (vrf->name, name);
-	      listnode_add_sort (vrf_list, vrf);
-	      if (vrf_master.vrf_new_hook)
-		{
-		  (*vrf_master.vrf_new_hook) (vrf_id, name, &vrf->info);
-
-		  if (debug_vrf && vrf->info)
-		    zlog_info ("zvrf is created.");
-		}
-	      if (debug_vrf)
-		zlog_debug("Vrf Created: %p", vrf);
-	      return vrf;
-	    }
-	  else
-	    {
-	      vrf = XCALLOC (MTYPE_VRF, sizeof (struct vrf));
-
-	      rn->info = vrf;
-	      vrf->node = rn;
-	      vrf->vrf_id = vrf_id;
-	      strcpy (vrf->name, name);
-	      listnode_add_sort (vrf_list, vrf);
-	      if_init (&vrf->iflist);
-	      QOBJ_REG (vrf, vrf);
-	      if (vrf_master.vrf_new_hook)
-		{
-		  (*vrf_master.vrf_new_hook) (vrf_id, name, &vrf->info);
-
-		  if (debug_vrf && vrf->info)
-		    zlog_info ("zvrf is created.");
-		}
-	      if (debug_vrf)
-		zlog_debug("Vrf Created: %p", vrf);
-	      return vrf;
-	    }
-	}
+      vrf->vrf_id = vrf_id;
+      RB_INSERT (vrf_id_head, &vrfs_by_id, vrf);
     }
-  /*
-   * The final case, we've been passed a valid vrf_id
-   * but no name.  So we create the route node
-   * if it hasn't already been created.
-   */
-  else if (!name)
+
+  /* Set name */
+  if (name && vrf->name[0] != '\0' && strcmp (name, vrf->name))
     {
-      vrf_build_key (vrf_id, &p);
-      rn = route_node_get (vrf_table, &p);
-      if (debug_vrf)
-        zlog_debug("Vrf found: %p", rn->info);
-
-      if (rn->info)
-        {
-           route_unlock_node (rn);
-	   return (rn->info);
-	}
-      else
-	{
-	  vrf = XCALLOC (MTYPE_VRF, sizeof (struct vrf));
-          rn->info = vrf;
-	  vrf->node = rn;
-	  vrf->vrf_id = vrf_id;
-          if_init (&vrf->iflist);
-          QOBJ_REG (vrf, vrf);
-	  if (debug_vrf)
-            zlog_debug("Vrf Created: %p", vrf);
-	  return vrf;
-        }
+      RB_REMOVE (vrf_name_head, &vrfs_by_name, vrf);
+      strlcpy (vrf->name, name, sizeof (vrf->name));
+      RB_INSERT (vrf_name_head, &vrfs_by_name, vrf);
     }
+  else if (name && vrf->name[0] == '\0')
+    {
+      strlcpy (vrf->name, name, sizeof (vrf->name));
+      RB_INSERT (vrf_name_head, &vrfs_by_name, vrf);
+    }
+
+  if (new && vrf_master.vrf_new_hook)
+    (*vrf_master.vrf_new_hook) (vrf);
 
-  /*
-   * We shouldn't get here and if we do
-   * something has gone wrong.
-   */
-  return NULL;
+  return vrf;
 }
 
 /* Delete a VRF. This is called in vrf_terminate(). */
@@ -278,53 +159,35 @@ vrf_delete (struct vrf *vrf)
     vrf_disable (vrf);
 
   if (vrf_master.vrf_delete_hook)
-    (*vrf_master.vrf_delete_hook) (vrf->vrf_id, vrf->name, &vrf->info);
+    (*vrf_master.vrf_delete_hook) (vrf);
 
   QOBJ_UNREG (vrf);
   if_terminate (&vrf->iflist);
 
-  if (vrf->node)
-    {
-      vrf->node->info = NULL;
-      route_unlock_node(vrf->node);
-    }
-
-  listnode_delete (vrf_list, vrf);
+  if (vrf->vrf_id != VRF_UNKNOWN)
+    RB_REMOVE (vrf_id_head, &vrfs_by_id, vrf);
+  if (vrf->name[0] != '\0')
+    RB_REMOVE (vrf_name_head, &vrfs_by_name, vrf);
 
   XFREE (MTYPE_VRF, vrf);
 }
 
 /* Look up a VRF by identifier. */
 struct vrf *
-vrf_lookup (vrf_id_t vrf_id)
+vrf_lookup_by_id (vrf_id_t vrf_id)
 {
-  struct prefix p;
-  struct route_node *rn;
-  struct vrf *vrf = NULL;
-
-  vrf_build_key (vrf_id, &p);
-  rn = route_node_lookup (vrf_table, &p);
-  if (rn)
-    {
-      vrf = (struct vrf *)rn->info;
-      route_unlock_node (rn); /* lookup */
-    }
-  return vrf;
+  struct vrf vrf;
+  vrf.vrf_id = vrf_id;
+  return (RB_FIND (vrf_id_head, &vrfs_by_id, &vrf));
 }
 
 /*
- * Check whether the VRF is enabled - that is, whether the VRF
- * is ready to allocate resources. Currently there's only one
- * type of resource: socket.
+ * Check whether the VRF is enabled.
  */
 static int
 vrf_is_enabled (struct vrf *vrf)
 {
   return vrf && CHECK_FLAG (vrf->status, VRF_ACTIVE);
-
-  /*Pending: figure out the real use of this routine.. it used to be..
-  return vrf && vrf->vrf_id == VRF_DEFAULT;
-  */
 }
 
 /*
@@ -337,14 +200,16 @@ vrf_is_enabled (struct vrf *vrf)
 int
 vrf_enable (struct vrf *vrf)
 {
+  if (vrf_is_enabled (vrf))
+    return 1;
+
   if (debug_vrf)
     zlog_debug ("VRF %u is enabled.", vrf->vrf_id);
 
-  if (!CHECK_FLAG (vrf->status, VRF_ACTIVE))
-    SET_FLAG (vrf->status, VRF_ACTIVE);
+  SET_FLAG (vrf->status, VRF_ACTIVE);
 
   if (vrf_master.vrf_enable_hook)
-    (*vrf_master.vrf_enable_hook) (vrf->vrf_id, vrf->name, &vrf->info);
+    (*vrf_master.vrf_enable_hook) (vrf);
 
   return 1;
 }
@@ -357,26 +222,25 @@ vrf_enable (struct vrf *vrf)
 static void
 vrf_disable (struct vrf *vrf)
 {
-  if (vrf_is_enabled (vrf))
-    {
-      UNSET_FLAG (vrf->status, VRF_ACTIVE);
+  if (! vrf_is_enabled (vrf))
+    return;
 
-      if (debug_vrf)
-	zlog_debug ("VRF %u is to be disabled.", vrf->vrf_id);
+  UNSET_FLAG (vrf->status, VRF_ACTIVE);
 
-      /* Till now, nothing to be done for the default VRF. */
-      //Pending: see why this statement.
+  if (debug_vrf)
+    zlog_debug ("VRF %u is to be disabled.", vrf->vrf_id);
 
-      if (vrf_master.vrf_disable_hook)
-        (*vrf_master.vrf_disable_hook) (vrf->vrf_id, vrf->name, &vrf->info);
-    }
+  /* Till now, nothing to be done for the default VRF. */
+  //Pending: see why this statement.
 
+  if (vrf_master.vrf_disable_hook)
+    (*vrf_master.vrf_disable_hook) (vrf);
 }
 
 
 /* Add a VRF hook. Please add hooks before calling vrf_init(). */
 void
-vrf_add_hook (int type, int (*func)(vrf_id_t, const char *, void **))
+vrf_add_hook (int type, int (*func)(struct vrf *))
 {
   if (debug_vrf)
     zlog_debug ("%s: Add Hook %d to function %p",  __PRETTY_FUNCTION__,
@@ -400,116 +264,6 @@ vrf_add_hook (int type, int (*func)(vrf_id_t, const char *, void **))
   }
 }
 
-/* Return the iterator of the first VRF. */
-vrf_iter_t
-vrf_first (void)
-{
-  struct route_node *rn;
-
-  for (rn = route_top (vrf_table); rn; rn = route_next (rn))
-    if (rn->info)
-      {
-        route_unlock_node (rn); /* top/next */
-        return (vrf_iter_t)rn;
-      }
-  return VRF_ITER_INVALID;
-}
-
-/* Return the next VRF iterator to the given iterator. */
-vrf_iter_t
-vrf_next (vrf_iter_t iter)
-{
-  struct route_node *rn = NULL;
-
-  /* Lock it first because route_next() will unlock it. */
-  if (iter != VRF_ITER_INVALID)
-    rn = route_next (route_lock_node ((struct route_node *)iter));
-
-  for (; rn; rn = route_next (rn))
-    if (rn->info)
-      {
-        route_unlock_node (rn); /* next */
-        return (vrf_iter_t)rn;
-      }
-  return VRF_ITER_INVALID;
-}
-
-/* Return the VRF iterator of the given VRF ID. If it does not exist,
- * the iterator of the next existing VRF is returned. */
-vrf_iter_t
-vrf_iterator (vrf_id_t vrf_id)
-{
-  struct prefix p;
-  struct route_node *rn;
-
-  vrf_build_key (vrf_id, &p);
-  rn = route_node_get (vrf_table, &p);
-  if (rn->info)
-    {
-      /* OK, the VRF exists. */
-      route_unlock_node (rn); /* get */
-      return (vrf_iter_t)rn;
-    }
-
-  /* Find the next VRF. */
-  for (rn = route_next (rn); rn; rn = route_next (rn))
-    if (rn->info)
-      {
-        route_unlock_node (rn); /* next */
-        return (vrf_iter_t)rn;
-      }
-
-  return VRF_ITER_INVALID;
-}
-
-/* Obtain the VRF ID from the given VRF iterator. */
-vrf_id_t
-vrf_iter2id (vrf_iter_t iter)
-{
-  struct route_node *rn = (struct route_node *) iter;
-  return (rn && rn->info) ? ((struct vrf *)rn->info)->vrf_id : VRF_DEFAULT;
-}
-
-struct vrf *
-vrf_iter2vrf (vrf_iter_t iter)
-{
-  struct route_node *rn = (struct route_node *) iter;
-  return (rn && rn->info) ? (struct vrf *)rn->info : NULL;
-}
-
-/* Obtain the data pointer from the given VRF iterator. */
-void *
-vrf_iter2info (vrf_iter_t iter)
-{
-  struct route_node *rn = (struct route_node *) iter;
-  return (rn && rn->info) ? ((struct vrf *)rn->info)->info : NULL;
-}
-
-/* Obtain the interface list from the given VRF iterator. */
-struct list *
-vrf_iter2iflist (vrf_iter_t iter)
-{
-  struct route_node *rn = (struct route_node *) iter;
-  return (rn && rn->info) ? ((struct vrf *)rn->info)->iflist : NULL;
-}
-
-/* Look up a VRF by name. */
-struct vrf *
-vrf_lookup_by_name (const char *name)
-{
-  struct vrf *vrf = NULL;
-  vrf_iter_t iter;
-
-  for (iter = vrf_first (); iter != VRF_ITER_INVALID; iter = vrf_next (iter))
-    {
-      vrf = vrf_iter2vrf (iter);
-      if (vrf && !strcmp(vrf->name, name))
-        return vrf;
-    }
-
-  return NULL;
-}
-
 vrf_id_t
 vrf_name_to_id (const char *name)
 {
@@ -535,7 +289,7 @@ vrf_info_get (vrf_id_t vrf_id)
 void *
 vrf_info_lookup (vrf_id_t vrf_id)
 {
-  struct vrf *vrf = vrf_lookup (vrf_id);
+  struct vrf *vrf = vrf_lookup_by_id (vrf_id);
   return vrf ? vrf->info : NULL;
 }
 
@@ -543,7 +297,7 @@ vrf_info_lookup (vrf_id_t vrf_id)
 struct list *
 vrf_iflist (vrf_id_t vrf_id)
 {
-   struct vrf * vrf = vrf_lookup (vrf_id);
+   struct vrf * vrf = vrf_lookup_by_id (vrf_id);
    return vrf ? vrf->iflist : NULL;
 }
 
@@ -559,7 +313,7 @@ vrf_iflist_get (vrf_id_t vrf_id)
 void
 vrf_iflist_create (vrf_id_t vrf_id)
 {
-   struct vrf * vrf = vrf_lookup (vrf_id);
+   struct vrf * vrf = vrf_lookup_by_id (vrf_id);
    if (vrf && !vrf->iflist)
      if_init (&vrf->iflist);
 }
@@ -568,7 +322,7 @@ vrf_iflist_create (vrf_id_t vrf_id)
 void
 vrf_iflist_terminate (vrf_id_t vrf_id)
 {
-   struct vrf * vrf = vrf_lookup (vrf_id);
+   struct vrf * vrf = vrf_lookup_by_id (vrf_id);
    if (vrf && vrf->iflist)
      if_terminate (&vrf->iflist);
 }
@@ -666,20 +420,6 @@ vrf_bitmap_check (vrf_bitmap_t bmap, vrf_id_t vrf_id)
                      VRF_BITMAP_FLAG (offset)) ? 1 : 0;
 }
 
-/* Compare interface names, returning an integer greater than, equal to, or
- * less than 0, (following the strcmp convention), according to the
- * relationship between vrfp1 and vrfp2.  Interface names consist of an
- * alphabetic prefix and a numeric suffix.  The primary sort key is
- * lexicographic by name, and then numeric by number.  No number sorts
- * before all numbers.  Examples: de0 < de1, de100 < fxp0 < xl0, devpty <
- * devpty0, de0 < del0
- */
-static int
-vrf_cmp_func (struct vrf *vrfp1, struct vrf *vrfp2)
-{
-  return if_cmp_name_func (vrfp1->name, vrfp2->name);
-}
-
 /* Initialize VRF module. */
 void
 vrf_init (void)
@@ -689,12 +429,6 @@ vrf_init (void)
   if (debug_vrf)
     zlog_debug ("%s: Initializing VRF subsystem", __PRETTY_FUNCTION__);
 
-  vrf_list = list_new ();
-  vrf_list->cmp = (int (*)(void *, void *))vrf_cmp_func;
-
-  /* Allocate VRF table.  */
-  vrf_table = route_table_init ();
-
   /* The default VRF always exists. */
   default_vrf = vrf_get (VRF_DEFAULT, VRF_DEFAULT_NAME);
   if (!default_vrf)
@@ -715,18 +449,15 @@ vrf_init (void)
 void
 vrf_terminate (void)
 {
-  struct route_node *rn;
   struct vrf *vrf;
 
   if (debug_vrf)
     zlog_debug ("%s: Shutting down vrf subsystem", __PRETTY_FUNCTION__);
 
-  for (rn = route_top (vrf_table); rn; rn = route_next (rn))
-    if ((vrf = rn->info) != NULL)
-      vrf_delete (vrf);
-
-  route_table_finish (vrf_table);
-  vrf_table = NULL;
+  while ((vrf = RB_ROOT (&vrfs_by_id)) != NULL)
+    vrf_delete (vrf);
+  while ((vrf = RB_ROOT (&vrfs_by_name)) != NULL)
+    vrf_delete (vrf);
 }
 
 /* Create a socket for the VRF. */
@@ -740,6 +471,60 @@ vrf_socket (int domain, int type, int protocol, vrf_id_t vrf_id)
   return ret;
 }
 
+/* vrf CLI commands */
+DEFUN (vrf,
+       vrf_cmd,
+       "vrf NAME",
+       "Select a VRF to configure\n"
+       "VRF's name\n")
+{
+  struct vrf *vrfp;
+  size_t sl;
+
+  if ((sl = strlen(argv[0])) > VRF_NAMSIZ)
+    {
+      vty_out (vty, "%% VRF name %s is invalid: length exceeds "
+		    "%d characters%s",
+	       argv[0], VRF_NAMSIZ, VTY_NEWLINE);
+      return CMD_WARNING;
+    }
+
+  vrfp = vrf_get (VRF_UNKNOWN, argv[0]);
+
+  VTY_PUSH_CONTEXT_COMPAT (VRF_NODE, vrfp);
+
+  return CMD_SUCCESS;
+}
+
+DEFUN_NOSH (no_vrf,
+           no_vrf_cmd,
+           "no vrf NAME",
+           NO_STR
+           "Delete a pseudo VRF's configuration\n"
+           "VRF's name\n")
+{
+  struct vrf *vrfp;
+
+  vrfp = vrf_lookup_by_name (argv[0]);
+
+  if (vrfp == NULL)
+    {
+      vty_out (vty, "%% VRF %s does not exist%s", argv[0], VTY_NEWLINE);
+      return CMD_WARNING;
+    }
+
+  if (CHECK_FLAG (vrfp->status, VRF_ACTIVE))
+    {
+      vty_out (vty, "%% Only inactive VRFs can be deleted%s",
+	      VTY_NEWLINE);
+      return CMD_WARNING;
+    }
+
+  vrf_delete(vrfp);
+
+  return CMD_SUCCESS;
+}
+
 /*
  * Debug CLI for vrf's
  */
diff --git a/lib/vrf.h b/lib/vrf.h
index 127b7082e..c9e81bf66 100644
--- a/lib/vrf.h
+++ b/lib/vrf.h
@@ -23,6 +23,7 @@
 #ifndef _ZEBRA_VRF_H
 #define _ZEBRA_VRF_H
 
+#include "openbsd-tree.h"
 #include "linklist.h"
 #include "qobj.h"
 
@@ -69,18 +70,18 @@ enum {
 
 struct vrf
 {
+  RB_ENTRY(vrf) id_entry, name_entry;
+
   /* Identifier, same as the vector index */
   vrf_id_t vrf_id;
-  /* Name */
 
+  /* Name */
   char name[VRF_NAMSIZ + 1];
 
   /* Zebra internal VRF status */
   u_char status;
 #define VRF_ACTIVE     (1 << 0)
 
-  struct route_node *node;
-
   /* Master list of interfaces belonging to this VRF */
   struct list *iflist;
 
@@ -89,10 +90,15 @@ struct vrf
 
   QOBJ_FIELDS
 };
+RB_HEAD (vrf_id_head, vrf);
+RB_PROTOTYPE (vrf_id_head, vrf, id_entry, vrf_id_compare)
+RB_HEAD (vrf_name_head, vrf);
+RB_PROTOTYPE (vrf_name_head, vrf, name_entry, vrf_name_compare)
 DECLARE_QOBJ_TYPE(vrf)
 
 
-extern struct list *vrf_list;
+extern struct vrf_id_head vrfs_by_id;
+extern struct vrf_name_head vrfs_by_name;
 
 /*
  * Add a specific hook to VRF module.
@@ -102,18 +108,10 @@ extern struct list *vrf_list;
  *          - param 2: the address of the user data pointer (the user data
  *                     can be stored in or freed from there)
  */
-extern void vrf_add_hook (int, int (*)(vrf_id_t, const char *, void **));
+extern void vrf_add_hook (int, int (*)(struct vrf *));
 
-/*
- * VRF iteration
- */
-
-typedef void *              vrf_iter_t;
-#define VRF_ITER_INVALID    NULL    /* invalid value of the iterator */
-
-extern struct vrf *vrf_lookup (vrf_id_t);
+extern struct vrf *vrf_lookup_by_id (vrf_id_t);
 extern struct vrf *vrf_lookup_by_name (const char *);
-extern struct vrf *vrf_list_lookup_by_name (const char *);
 extern struct vrf *vrf_get (vrf_id_t, const char *);
 extern void vrf_delete (struct vrf *);
 extern int vrf_enable (struct vrf *);
@@ -122,7 +120,7 @@ extern vrf_id_t vrf_name_to_id (const char *);
 #define VRF_GET_ID(V,NAME)      \
   do {                          \
       struct vrf *vrf; \
-      if (!(vrf = vrf_list_lookup_by_name(NAME))) \
+      if (!(vrf = vrf_lookup_by_name(NAME))) \
         {                                                           \
           vty_out (vty, "%% VRF %s not found%s", NAME, VTY_NEWLINE);\
           return CMD_WARNING;                                       \
@@ -136,34 +134,6 @@ extern vrf_id_t vrf_name_to_id (const char *);
   } while (0)
 
 /*
- * VRF iteration utilities. Example for the usage:
- *
- *   vrf_iter_t iter = vrf_first();
- *   for (; iter != VRF_ITER_INVALID; iter = vrf_next (iter))
- *
- * or
- *
- *   vrf_iter_t iter = vrf_iterator (<a given VRF ID>);
- *   for (; iter != VRF_ITER_INVALID; iter = vrf_next (iter))
- */
-
-/* Return the iterator of the first VRF. */
-extern vrf_iter_t vrf_first (void);
-/* Return the next VRF iterator to the given iterator. */
-extern vrf_iter_t vrf_next (vrf_iter_t);
-/* Return the VRF iterator of the given VRF ID. If it does not exist,
- * the iterator of the next existing VRF is returned. */
-extern vrf_iter_t vrf_iterator (vrf_id_t);
-
-/*
- * VRF iterator to properties
- */
-extern vrf_id_t vrf_iter2id (vrf_iter_t);
-extern struct vrf *vrf_iter2vrf (vrf_iter_t);
-extern void *vrf_iter2info (vrf_iter_t);
-extern struct list *vrf_iter2iflist (vrf_iter_t);
-
-/*
  * Utilities to obtain the user data
  */
 
diff --git a/lib/zclient.c b/lib/zclient.c
index 84f7314ba..894e0d19e 100644
--- a/lib/zclient.c
+++ b/lib/zclient.c
@@ -1042,7 +1042,7 @@ zclient_vrf_delete (struct zclient *zclient, vrf_id_t vrf_id)
   struct vrf *vrf;
 
   /* Lookup vrf by vrf_id. */
-  vrf = vrf_lookup (vrf_id);
+  vrf = vrf_lookup_by_id (vrf_id);
 
   /*
    * If a routing protocol doesn't know about a