diff --git a/bgpd/bgp_nexthop.c b/bgpd/bgp_nexthop.c
index fa2f488..d1c5c86 100644
--- a/bgpd/bgp_nexthop.c
+++ b/bgpd/bgp_nexthop.c
@@ -591,6 +591,14 @@
                                   bgp_address_hash_cmp);
 }
 
+void
+bgp_address_destroy (void)
+{
+  hash_clean(bgp_address_hash, NULL);
+  hash_free(bgp_address_hash);
+  bgp_address_hash = NULL;
+}
+
 static void
 bgp_address_add (struct prefix *p)
 {
@@ -1467,3 +1475,16 @@
   bgp_connected_table[AFI_IP6] = NULL;
 #endif /* HAVE_IPV6 */
 }
+
+void
+bgp_scan_destroy (void)
+{
+  if (zlookup == NULL)
+    return;
+  THREAD_OFF(bgp_import_thread);
+  THREAD_OFF(bgp_scan_thread);
+  THREAD_OFF(zlookup->t_connect);
+  bgp_scan_finish();
+  zclient_free (zlookup);
+  zlookup = NULL;
+}
diff --git a/bgpd/bgp_nexthop.h b/bgpd/bgp_nexthop.h
index c8aef58..85c5a5d 100644
--- a/bgpd/bgp_nexthop.h
+++ b/bgpd/bgp_nexthop.h
@@ -66,5 +66,7 @@
 extern int bgp_nexthop_onlink (afi_t, struct attr *);
 extern int bgp_nexthop_self (struct attr *);
 extern void bgp_address_init (void);
+extern void bgp_address_destroy (void);
+extern void bgp_scan_destroy (void);
 
 #endif /* _QUAGGA_BGP_NEXTHOP_H */
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index ff541e8..868fbe5 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -3051,6 +3051,57 @@
       bgp_clear_route (peer, afi, safi, BGP_CLEAR_ROUTE_NORMAL);
 }
 
+/*
+ * Finish freeing things when exiting
+ */
+static void
+bgp_drain_workqueue_immediate (struct work_queue *wq)
+{
+  if (!wq)
+    return;
+
+  if (!wq->thread)
+    {
+      /*
+       * no thread implies no queued items
+       */
+      assert(!wq->items->count);
+      return;
+    }
+
+   while (wq->items->count)
+     {
+       if (wq->thread)
+         thread_cancel(wq->thread);
+       work_queue_run(wq->thread);
+     }
+}
+
+/*
+ * Special function to process clear node queue when bgpd is exiting
+ * and the thread scheduler is no longer running.
+ */
+void
+bgp_peer_clear_node_queue_drain_immediate(struct peer *peer)
+{
+  if (!peer)
+    return;
+
+  bgp_drain_workqueue_immediate(peer->clear_node_queue);
+}
+
+/*
+ * The work queues are not specific to a BGP instance, but the
+ * items in them refer to BGP instances, so this should be called
+ * before each BGP instance is deleted.
+ */
+void
+bgp_process_queues_drain_immediate(void)
+{
+  bgp_drain_workqueue_immediate(bm->process_main_queue);
+  bgp_drain_workqueue_immediate(bm->process_rsclient_queue);
+}
+
 void
 bgp_clear_adj_in (struct peer *peer, afi_t afi, safi_t safi)
 {
@@ -3091,35 +3142,53 @@
     }
 }
 
+static void
+bgp_cleanup_table(struct bgp_table *table, safi_t safi)
+{
+  struct bgp_node *rn;
+  struct bgp_info *ri;
+  struct bgp_info *next;
+
+  for (rn = bgp_table_top (table); rn; rn = bgp_route_next (rn))
+    for (ri = rn->info; ri; ri = next)
+      {
+        next = ri->next;
+        if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED)
+            && ri->type == ZEBRA_ROUTE_BGP
+            && ri->sub_type == BGP_ROUTE_NORMAL)
+          bgp_zebra_withdraw (&rn->p, ri, safi);
+      }
+}
+
 /* Delete all kernel routes. */
 void
 bgp_cleanup_routes (void)
 {
   struct bgp *bgp;
   struct listnode *node, *nnode;
-  struct bgp_node *rn;
-  struct bgp_table *table;
-  struct bgp_info *ri;
+  afi_t afi;
 
   for (ALL_LIST_ELEMENTS (bm->bgp, node, nnode, bgp))
     {
-      table = bgp->rib[AFI_IP][SAFI_UNICAST];
+      for (afi = AFI_IP; afi < AFI_MAX; ++afi)
+	{
+	  struct bgp_node *rn;
 
-      for (rn = bgp_table_top (table); rn; rn = bgp_route_next (rn))
-	for (ri = rn->info; ri; ri = ri->next)
-	  if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED)
-	      && ri->type == ZEBRA_ROUTE_BGP 
-	      && ri->sub_type == BGP_ROUTE_NORMAL)
-	    bgp_zebra_withdraw (&rn->p, ri,SAFI_UNICAST);
+	  bgp_cleanup_table(bgp->rib[afi][SAFI_UNICAST], SAFI_UNICAST);
 
-      table = bgp->rib[AFI_IP6][SAFI_UNICAST];
-
-      for (rn = bgp_table_top (table); rn; rn = bgp_route_next (rn))
-	for (ri = rn->info; ri; ri = ri->next)
-	  if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED)
-	      && ri->type == ZEBRA_ROUTE_BGP 
-	      && ri->sub_type == BGP_ROUTE_NORMAL)
-	    bgp_zebra_withdraw (&rn->p, ri,SAFI_UNICAST);
+	  /*
+	   * VPN and ENCAP tables are two-level (RD is top level)
+	   */
+	  for (rn = bgp_table_top(bgp->rib[afi][SAFI_MPLS_VPN]); rn;
+               rn = bgp_route_next (rn))
+	    if (rn->info)
+                {
+                   bgp_cleanup_table((struct bgp_table *)(rn->info), SAFI_MPLS_VPN);
+                   bgp_table_finish ((struct bgp_table **)&(rn->info));
+		   rn->info = NULL;
+		   bgp_unlock_node(rn);
+                }
+	}
     }
 }
 
diff --git a/bgpd/bgp_route.h b/bgpd/bgp_route.h
index 0482c6f..5a93b44 100644
--- a/bgpd/bgp_route.h
+++ b/bgpd/bgp_route.h
@@ -244,4 +244,7 @@
 extern void route_vty_out_tag (struct vty *, struct prefix *, struct bgp_info *, int, safi_t);
 extern void route_vty_out_tmp (struct vty *, struct prefix *, struct attr *, safi_t);
 
+extern void bgp_peer_clear_node_queue_drain_immediate (struct peer *peer);
+extern void bgp_process_queues_drain_immediate (void);
+
 #endif /* _QUAGGA_BGP_ROUTE_H */
diff --git a/bgpd/bgp_routemap.c b/bgpd/bgp_routemap.c
index 7555ca7..b449cae 100644
--- a/bgpd/bgp_routemap.c
+++ b/bgpd/bgp_routemap.c
@@ -2295,6 +2295,9 @@
   struct bgp_node *bn;
   struct bgp_static *bgp_static;
 
+  if (bm->bgp == NULL)          /* may be called during cleanup */
+    return;
+
   /* For neighbor route-map updates. */
   for (ALL_LIST_ELEMENTS (bm->bgp, mnode, mnnode, bgp))
     {
diff --git a/bgpd/bgp_vty.c b/bgpd/bgp_vty.c
index 304da25..041a6a1 100644
--- a/bgpd/bgp_vty.c
+++ b/bgpd/bgp_vty.c
@@ -9825,9 +9825,9 @@
   install_element (BGP_IPV6M_NODE, &neighbor_unsuppress_map_cmd);
   install_element (BGP_IPV6M_NODE, &no_neighbor_unsuppress_map_cmd);
   install_element (BGP_VPNV4_NODE, &neighbor_unsuppress_map_cmd);
-  install_element (BGP_VPNV4_NODE, &no_neighbor_unsuppress_map_cmd);  
+  install_element (BGP_VPNV4_NODE, &no_neighbor_unsuppress_map_cmd);
   install_element (BGP_VPNV6_NODE, &neighbor_unsuppress_map_cmd);
-  install_element (BGP_VPNV6_NODE, &no_neighbor_unsuppress_map_cmd);  
+  install_element (BGP_VPNV6_NODE, &no_neighbor_unsuppress_map_cmd);
 
   /* "neighbor maximum-prefix" commands. */
   install_element (BGP_NODE, &neighbor_maximum_prefix_cmd);
diff --git a/bgpd/bgp_zebra.c b/bgpd/bgp_zebra.c
index 4a25aa9..1be4440 100644
--- a/bgpd/bgp_zebra.c
+++ b/bgpd/bgp_zebra.c
@@ -1081,3 +1081,13 @@
 
   bgp_nexthop_buf = stream_new(BGP_NEXTHOP_BUF_SIZE);
 }
+
+void
+bgp_zebra_destroy(void)
+{
+  if (zclient == NULL)
+    return;
+  zclient_stop(zclient);
+  zclient_free(zclient);
+  zclient = NULL;
+}
diff --git a/bgpd/bgp_zebra.h b/bgpd/bgp_zebra.h
index 50f727d..ff9b375 100644
--- a/bgpd/bgp_zebra.h
+++ b/bgpd/bgp_zebra.h
@@ -26,6 +26,7 @@
 extern struct stream *bgp_nexthop_buf;
 
 extern void bgp_zebra_init (struct thread_master *master);
+extern void bgp_zebra_destroy (void);
 extern int bgp_if_update_all (void);
 extern int bgp_config_write_maxpaths (struct vty *, struct bgp *, afi_t,
 				      safi_t, int *);
diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c
index d9c32ce..636f569 100644
--- a/bgpd/bgpd.c
+++ b/bgpd/bgpd.c
@@ -1377,6 +1377,9 @@
           }
       }
   
+  if (CHECK_FLAG(bgp->flags, BGP_FLAG_DELETING))
+    bgp_peer_clear_node_queue_drain_immediate(peer);
+
   peer_unlock (peer); /* initial reference */
 
   return 0;
@@ -2165,6 +2168,8 @@
   afi_t afi;
   int i;
 
+  SET_FLAG(bgp->flags, BGP_FLAG_DELETING);
+
   THREAD_OFF (bgp->t_startup);
 
   /* Delete static route. */
@@ -2206,7 +2211,21 @@
     peer_delete(bgp->peer_self);
     bgp->peer_self = NULL;
   }
+
+  /*
+   * Free pending deleted routes. Unfortunately, it also has to process
+   * all the pending activity for other instances of struct bgp.
+   *
+   * This call was added to achieve clean memory allocation at exit,
+   * for the sake of valgrind.
+   */
+  bgp_process_queues_drain_immediate();
+
+  bgp_zebra_destroy();
+  bgp_scan_destroy();
+  bgp_address_destroy();
   
+
   /* Remove visibility via the master list - there may however still be
    * routes to be processed still referencing the struct bgp.
    */
diff --git a/bgpd/bgpd.h b/bgpd/bgpd.h
index 2c4fb20..0b3d449 100644
--- a/bgpd/bgpd.h
+++ b/bgpd/bgpd.h
@@ -123,6 +123,7 @@
 #define BGP_FLAG_GRACEFUL_RESTART         (1 << 12)
 #define BGP_FLAG_ASPATH_CONFED            (1 << 13)
 #define BGP_FLAG_ASPATH_MULTIPATH_RELAX   (1 << 14)
+#define BGP_FLAG_DELETING                 (1 << 15)
 
   /* BGP Per AF flags */
   u_int16_t af_flags[AFI_MAX][SAFI_MAX];
diff --git a/vtysh/vtysh.c b/vtysh/vtysh.c
index 418e5d7..a39889d 100644
--- a/vtysh/vtysh.c
+++ b/vtysh/vtysh.c
@@ -280,7 +280,7 @@
    * to move into node in the vtysh where it succeeded. */
   if (ret == CMD_SUCCESS || ret == CMD_SUCCESS_DAEMON || ret == CMD_WARNING)
     {
-      if ((saved_node == BGP_VPNV4_NODE || saved_node == BGP_VPNV6_NODE 
+      if ((saved_node == BGP_VPNV4_NODE || saved_node == BGP_VPNV6_NODE
            || saved_node == BGP_IPV4_NODE
 	   || saved_node == BGP_IPV6_NODE || saved_node == BGP_IPV4M_NODE
 	   || saved_node == BGP_IPV6M_NODE)