fib: improve ipv6 fib scaling

VPP IPv6 FIB relies on 2 bihash for all its VRFs: 1 for control plane
and one for data plane. Because of that, control plane VRF walks
time grows with the number of VRFs as it has to go through all the VRFs.
In order to improve control plane performance with large number of VRFs,
the control plane data structure is changed from a global bihash to a
per-VRF hashtable, similarly to IPv4. Contrary to IPv4, there is only 1
hashtable per VRF and not 1 hashtable per prefix-length per VRF, which
is a compromise between memory consumption and single VRF scaling.

Type: improvement

Change-Id: Ib738a44adb88e46c95c4c62c853ee1f1392c7187
Signed-off-by: Benoît Ganne <bganne@cisco.com>

4 files changed, 203 insertions, 406 deletions

diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c
index ccf8e22f5a7..f844cfaa420 100644
--- a/src/vnet/fib/ip6_fib.c
+++ b/src/vnet/fib/ip6_fib.c
@@ -20,14 +20,20 @@
 #include <vppinfra/bihash_24_8.h>
 #include <vppinfra/bihash_template.c>
 
-ip6_fib_table_instance_t ip6_fib_table[IP6_FIB_NUM_TABLES];
+ip6_fib_fwding_table_instance_t ip6_fib_fwding_table;
 
 /* ip6 lookup table config parameters */
 u32 ip6_fib_table_nbuckets;
 uword ip6_fib_table_size;
 
+typedef struct ip6_fib_hash_key_t_
+{
+  ip6_address_t addr;
+  u8 len;
+} ip6_fib_hash_key_t;
+
 static void
-vnet_ip6_fib_init (u32 fib_index)
+ip6_fib_hash_load_specials (u32 fib_index)
 {
     fib_prefix_t pfx = {
 	.fp_proto = FIB_PROTOCOL_IP6,
@@ -77,7 +83,7 @@ create_fib_with_table_id (u32 table_id,
 
     ASSERT((fib_table - ip6_main.fibs) ==
            (v6_fib - ip6_main.v6_fibs));
-    
+
     fib_table->ft_proto = FIB_PROTOCOL_IP6;
     fib_table->ft_index =
 	    v6_fib->index =
@@ -92,9 +98,15 @@ create_fib_with_table_id (u32 table_id,
     fib_table->ft_flags = flags;
     fib_table->ft_desc = desc;
 
-    vnet_ip6_fib_init(fib_table->ft_index);
     fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_IP6, src);
 
+    v6_fib->fib_entry_by_dst_address = hash_create_mem(2, sizeof(ip6_fib_hash_key_t), sizeof(fib_node_index_t));
+
+    /*
+     * add the special entries into the new FIB
+     */
+    ip6_fib_hash_load_specials (fib_table->ft_index);
+
     return (fib_table->ft_index);
 }
 
@@ -173,54 +185,40 @@ ip6_fib_table_destroy (u32 fib_index)
     }
     vec_free (fib_table->ft_locks);
     vec_free(fib_table->ft_src_route_counts);
+    hash_free(pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address);
     pool_put_index(ip6_main.v6_fibs, fib_table->ft_index);
     pool_put(ip6_main.fibs, fib_table);
 }
 
+static void
+ip6_fib_table_mk_key (ip6_fib_hash_key_t *key, const ip6_address_t *addr, u8 len)
+{
+  const ip6_address_t *mask = &ip6_main.fib_masks[len];
+  key->addr.as_u64[0] = addr->as_u64[0] & mask->as_u64[0];
+  key->addr.as_u64[1] = addr->as_u64[1] & mask->as_u64[1];
+  key->len = len;
+}
+
 fib_node_index_t
 ip6_fib_table_lookup (u32 fib_index,
 		      const ip6_address_t *addr,
 		      u32 len)
 {
-    ip6_fib_table_instance_t *table;
-    clib_bihash_kv_24_8_t kv, value;
-    int i, n_p, rv;
-    u64 fib;
-
-    table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING];
-    n_p = vec_len (table->prefix_lengths_in_search_order);
-
-    kv.key[0] = addr->as_u64[0];
-    kv.key[1] = addr->as_u64[1];
-    fib = ((u64)((fib_index))<<32);
+    uword *hash = pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address;
+    ip6_fib_hash_key_t key;
+    i32 mask_len;
+    uword *result;
 
-    /*
-     * start search from a mask length same length or shorter.
-     * we don't want matches longer than the mask passed
-     */
-    i = 0;
-    while (i < n_p && table->prefix_lengths_in_search_order[i] > len)
+    for (mask_len = len; mask_len >= 0; mask_len--)
     {
-        i++;
+      ip6_fib_table_mk_key (&key, addr, mask_len);
+      result = hash_get_mem(hash, &key);
+      if (result) {
+	  return result[0];
+      }
     }
 
-    for (; i < n_p; i++)
-    {
-	int dst_address_length = table->prefix_lengths_in_search_order[i];
-	ip6_address_t * mask = &ip6_main.fib_masks[dst_address_length];
-      
-	ASSERT(dst_address_length >= 0 && dst_address_length <= 128);
-	//As lengths are decreasing, masks are increasingly specific.
-	kv.key[0] &= mask->as_u64[0];
-	kv.key[1] &= mask->as_u64[1];
-	kv.key[2] = fib | dst_address_length;
-      
-	rv = clib_bihash_search_inline_2_24_8(&table->ip6_hash, &kv, &value);
-	if (rv == 0)
-	    return value.value;
-    }
-
-    return (FIB_NODE_INDEX_INVALID);
+    return FIB_NODE_INDEX_INVALID;
 }
 
 fib_node_index_t
@@ -228,53 +226,11 @@ ip6_fib_table_lookup_exact_match (u32 fib_index,
 				  const ip6_address_t *addr,
 				  u32 len)
 {
-    ip6_fib_table_instance_t *table;
-    clib_bihash_kv_24_8_t kv, value;
-    ip6_address_t *mask;
-    u64 fib;
-    int rv;
-
-    table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING];
-    mask = &ip6_main.fib_masks[len];
-    fib = ((u64)((fib_index))<<32);
-
-    kv.key[0] = addr->as_u64[0] & mask->as_u64[0];
-    kv.key[1] = addr->as_u64[1] & mask->as_u64[1];
-    kv.key[2] = fib | len;
-      
-    rv = clib_bihash_search_inline_2_24_8(&table->ip6_hash, &kv, &value);
-    if (rv == 0)
-	return value.value;
-
-    return (FIB_NODE_INDEX_INVALID);
-}
-
-static void
-compute_prefix_lengths_in_search_order (ip6_fib_table_instance_t *table)
-{
-    u8 *old, *prefix_lengths_in_search_order = NULL;
-    int i;
-
-    /*
-     * build the list in a scratch space then cutover so the workers
-     * can continue uninterrupted.
-     */
-    old = table->prefix_lengths_in_search_order;
-
-    /* Note: bitmap reversed so this is in fact a longest prefix match */
-    clib_bitmap_foreach (i, table->non_empty_dst_address_length_bitmap)
-     {
-	int dst_address_length = 128 - i;
-	vec_add1(prefix_lengths_in_search_order, dst_address_length);
-    }
-
-    table->prefix_lengths_in_search_order = prefix_lengths_in_search_order;
-
-    /*
-     * let the workers go once round the track before we free the old set
-     */
-    vlib_worker_wait_one_loop();
-    vec_free(old);
+    uword *hash = pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address;
+    ip6_fib_hash_key_t key;
+    ip6_fib_table_mk_key (&key, addr, len);
+    uword *result = hash_get(hash, &key);
+    return result ? result[0] : FIB_NODE_INDEX_INVALID;
 }
 
 void
@@ -282,30 +238,10 @@ ip6_fib_table_entry_remove (u32 fib_index,
 			    const ip6_address_t *addr,
 			    u32 len)
 {
-    ip6_fib_table_instance_t *table;
-    clib_bihash_kv_24_8_t kv;
-    ip6_address_t *mask;
-    u64 fib;
-
-    table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING];
-    mask = &ip6_main.fib_masks[len];
-    fib = ((u64)((fib_index))<<32);
-
-    kv.key[0] = addr->as_u64[0] & mask->as_u64[0];
-    kv.key[1] = addr->as_u64[1] & mask->as_u64[1];
-    kv.key[2] = fib | len;
-
-    clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 0);
-
-    /* refcount accounting */
-    ASSERT (table->dst_address_length_refcounts[len] > 0);
-    if (--table->dst_address_length_refcounts[len] == 0)
-    {
-	table->non_empty_dst_address_length_bitmap =
-            clib_bitmap_set (table->non_empty_dst_address_length_bitmap, 
-                             128 - len, 0);
-	compute_prefix_lengths_in_search_order (table);
-    }
+    uword **hash = &pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address;
+    ip6_fib_hash_key_t key;
+    ip6_fib_table_mk_key (&key, addr, len);
+    hash_unset_mem_free(hash, &key);
 }
 
 void
@@ -314,29 +250,11 @@ ip6_fib_table_entry_insert (u32 fib_index,
 			    u32 len,
 			    fib_node_index_t fib_entry_index)
 {
-    ip6_fib_table_instance_t *table;
-    clib_bihash_kv_24_8_t kv;
-    ip6_address_t *mask;
-    u64 fib;
-
-    table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING];
-    mask = &ip6_main.fib_masks[len];
-    fib = ((u64)((fib_index))<<32);
-
-    kv.key[0] = addr->as_u64[0] & mask->as_u64[0];
-    kv.key[1] = addr->as_u64[1] & mask->as_u64[1];
-    kv.key[2] = fib | len;
-    kv.value = fib_entry_index;
-
-    clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 1);
-
-    if (0 == table->dst_address_length_refcounts[len]++)
-    {
-        table->non_empty_dst_address_length_bitmap =
-            clib_bitmap_set (table->non_empty_dst_address_length_bitmap,
-                             128 - len, 1);
-        compute_prefix_lengths_in_search_order (table);
-    }
+    uword **hash = &pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address;
+    ip6_fib_hash_key_t key;
+    ip6_fib_table_mk_key (&key, addr, len);
+    ASSERT (0 == hash_get(*hash, &key) && "entry already exists");
+    hash_set_mem_alloc(hash, &key, fib_entry_index);
 }
 
 u32 ip6_fib_table_fwding_lookup_with_if_index (ip6_main_t * im,
@@ -361,18 +279,46 @@ ip6_fib_table_get_index_for_sw_if_index (u32 sw_if_index)
     return (ip6_main.fib_index_by_sw_if_index[sw_if_index]);
 }
 
+static void
+compute_prefix_lengths_in_search_order (ip6_fib_fwding_table_instance_t *table)
+{
+    u8 *old, *prefix_lengths_in_search_order = NULL;
+    int i;
+
+    /*
+     * build the list in a scratch space then cutover so the workers
+     * can continue uninterrupted.
+     */
+    old = table->prefix_lengths_in_search_order;
+
+    /* Note: bitmap reversed so this is in fact a longest prefix match */
+    clib_bitmap_foreach (i, table->non_empty_dst_address_length_bitmap)
+     {
+	int dst_address_length = 128 - i;
+	vec_add1(prefix_lengths_in_search_order, dst_address_length);
+    }
+
+    table->prefix_lengths_in_search_order = prefix_lengths_in_search_order;
+
+    /*
+     * let the workers go once round the track before we free the old set
+     */
+    vlib_worker_wait_one_loop();
+    vec_free(old);
+}
+
 void
 ip6_fib_table_fwding_dpo_update (u32 fib_index,
 				 const ip6_address_t *addr,
 				 u32 len,
 				 const dpo_id_t *dpo)
 {
-    ip6_fib_table_instance_t *table;
+    ip6_fib_fwding_table_instance_t *table;
     clib_bihash_kv_24_8_t kv;
     ip6_address_t *mask;
     u64 fib;
 
-    table = &ip6_fib_table[IP6_FIB_TABLE_FWDING];
+    table = &ip6_fib_fwding_table;
     mask = &ip6_main.fib_masks[len];
     fib = ((u64)((fib_index))<<32);
 
@@ -398,12 +344,12 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index,
 				 u32 len,
 				 const dpo_id_t *dpo)
 {
-    ip6_fib_table_instance_t *table;
+    ip6_fib_fwding_table_instance_t *table;
     clib_bihash_kv_24_8_t kv;
     ip6_address_t *mask;
     u64 fib;
 
-    table = &ip6_fib_table[IP6_FIB_TABLE_FWDING];
+    table = &ip6_fib_fwding_table;
     mask = &ip6_main.fib_masks[len];
     fib = ((u64)((fib_index))<<32);
 
@@ -425,101 +371,18 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index,
     }
 }
 
-/**
- * @brief Context when walking the IPv6 table. Since all VRFs are in the
- * same hash table, we need to filter only those we need as we walk
- */
-typedef struct ip6_fib_walk_ctx_t_
-{
-    u32 i6w_fib_index;
-    fib_table_walk_fn_t i6w_fn;
-    void *i6w_ctx;
-    fib_prefix_t i6w_root;
-    fib_prefix_t *i6w_sub_trees;
-} ip6_fib_walk_ctx_t;
-
-static int
-ip6_fib_walk_cb (clib_bihash_kv_24_8_t * kvp,
-                 void *arg)
-{
-    ip6_fib_walk_ctx_t *ctx = arg;
-    ip6_address_t key;
-
-    if ((kvp->key[2] >> 32) == ctx->i6w_fib_index)
-    {
-        key.as_u64[0] = kvp->key[0];
-        key.as_u64[1] = kvp->key[1];
-
-        if (ip6_destination_matches_route(&ip6_main,
-                                          &key,
-                                          &ctx->i6w_root.fp_addr.ip6,
-                                          ctx->i6w_root.fp_len))
-        {
-            const fib_prefix_t *sub_tree;
-            int skip = 0;
-
-            /*
-             * exclude sub-trees the walk does not want to explore
-             */
-            vec_foreach(sub_tree, ctx->i6w_sub_trees)
-            {
-                if (ip6_destination_matches_route(&ip6_main,
-                                                  &key,
-                                                  &sub_tree->fp_addr.ip6,
-                                                  sub_tree->fp_len))
-                {
-                    skip = 1;
-                    break;
-                }
-            }
-
-            if (!skip)
-            {
-                switch (ctx->i6w_fn(kvp->value, ctx->i6w_ctx))
-                {
-                case FIB_TABLE_WALK_CONTINUE:
-                    break;
-                case FIB_TABLE_WALK_SUB_TREE_STOP: {
-                    fib_prefix_t pfx = {
-                        .fp_proto = FIB_PROTOCOL_IP6,
-                        .fp_len = kvp->key[2] & 0xffffffff,
-                        .fp_addr.ip6 = key,
-                    };
-                    vec_add1(ctx->i6w_sub_trees, pfx);
-                    break;
-                }
-                case FIB_TABLE_WALK_STOP:
-                    goto done;
-                }
-            }
-        }
-    }
-done:
-
-    return (1);
-}
-
 void
 ip6_fib_table_walk (u32 fib_index,
                     fib_table_walk_fn_t fn,
                     void *arg)
 {
-    ip6_fib_walk_ctx_t ctx = {
-        .i6w_fib_index = fib_index,
-        .i6w_fn = fn,
-        .i6w_ctx = arg,
-        .i6w_root = {
-            .fp_proto = FIB_PROTOCOL_IP6,
-        },
-        .i6w_sub_trees = NULL,
+    const fib_prefix_t root = {
+        .fp_proto = FIB_PROTOCOL_IP6,
+        // address and length default to all 0
     };
-
-    clib_bihash_foreach_key_value_pair_24_8(
-        &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
-        ip6_fib_walk_cb,
-        &ctx);
-
-    vec_free(ctx.i6w_sub_trees);
+    /* A full tree walk is the dengenerate case of a sub-tree from
+     * the very root */
+    return (ip6_fib_table_sub_tree_walk(fib_index, &root, fn, arg));
 }
 
 void
@@ -528,17 +391,43 @@ ip6_fib_table_sub_tree_walk (u32 fib_index,
                              fib_table_walk_fn_t fn,
                              void *arg)
 {
-    ip6_fib_walk_ctx_t ctx = {
-        .i6w_fib_index = fib_index,
-        .i6w_fn = fn,
-        .i6w_ctx = arg,
-        .i6w_root = *root,
-    };
+    uword *hash = pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address;
+    const ip6_fib_hash_key_t *key, *sub_tree;
+    ip6_fib_hash_key_t *sub_trees = 0;
+    u32 fei;
 
-    clib_bihash_foreach_key_value_pair_24_8(
-        &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
-        ip6_fib_walk_cb,
-        &ctx);
+    /*
+     * There is no efficient way to walk this hash table.
+     * so we walk over all entries and check it is covered by the root.
+     */
+    hash_foreach_mem(key, fei, hash, ({
+	/* check if the prefix is covered by the root */
+	if (!ip6_destination_matches_route(&ip6_main, &key->addr, &root->fp_addr.ip6, root->fp_len))
+	  continue; /* not covered by root, ignore */
+
+	/* exclude sub-trees the walk does not want to explore */
+	vec_foreach (sub_tree, sub_trees)
+	  {
+	    if (ip6_destination_matches_route(&ip6_main, &key->addr, &sub_tree->addr, sub_tree->len))
+	      goto ignore_sub_tree;
+	  }
+
+	switch (fn(fei, arg))
+	  {
+	  case FIB_TABLE_WALK_STOP:
+	    goto done;
+	  case FIB_TABLE_WALK_CONTINUE:
+	    break;
+	  case FIB_TABLE_WALK_SUB_TREE_STOP:
+	    vec_add1(sub_trees, *key);
+	    break;
+	  }
+
+ignore_sub_tree:;
+    }));
+
+done:
+    vec_free(sub_trees);
 }
 
 typedef struct ip6_fib_show_ctx_t_ {
@@ -599,8 +488,7 @@ format_ip6_fib_table_memory (u8 * s, va_list * args)
 {
     uword bytes_inuse;
 
-    bytes_inuse = (alloc_arena_next(&(ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash)) +
-                   alloc_arena_next(&(ip6_fib_table[IP6_FIB_TABLE_FWDING].ip6_hash)));
+    bytes_inuse = alloc_arena_next(&ip6_fib_fwding_table.ip6_hash);
 
     s = format(s, "%=30s %=6d %=12ld\n",
                "IPv6 unicast",
@@ -609,26 +497,60 @@ format_ip6_fib_table_memory (u8 * s, va_list * args)
     return (s);
 }
 
-typedef struct {
-  u32 fib_index;
-  u64 count_by_prefix_length[129];
-} count_routes_in_fib_at_prefix_length_arg_t;
-
-static int
-count_routes_in_fib_at_prefix_length (clib_bihash_kv_24_8_t * kvp,
-                                      void *arg)
+void
+ip6_fib_table_show (vlib_main_t *vm, fib_table_t *fib_table, int summary)
 {
-  count_routes_in_fib_at_prefix_length_arg_t * ap = arg;
-  int mask_width;
+    ip6_main_t * im6 = &ip6_main;
+    ip6_fib_t *fib = pool_elt_at_index(im6->v6_fibs, fib_table->ft_index);
+    fib_source_t source;
+    u8 *s = NULL;
+
+    s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[",
+	       format_fib_table_name, fib->index,
+	       FIB_PROTOCOL_IP6,
+	       fib->index,
+	       format_ip_flow_hash_config,
+	       fib_table->ft_flow_hash_config,
+	       fib_table->ft_epoch,
+	       format_fib_table_flags, fib_table->ft_flags);
+
+    vec_foreach_index(source, fib_table->ft_locks)
+    {
+	if (0 != fib_table->ft_locks[source])
+	{
+	    s = format(s, "%U:%d, ",
+		       format_fib_source, source,
+		       fib_table->ft_locks[source]);
+	}
+    }
+    s = format (s, "]");
+    vlib_cli_output (vm, "%v", s);
+    vec_free(s);
 
-  if ((kvp->key[2]>>32) != ap->fib_index)
-      return (BIHASH_WALK_CONTINUE);
+    /* Show summary? */
+    if (summary)
+    {
+	u32 count_by_prefix_length[129];
+	const ip6_fib_hash_key_t *key;
+	u32 fei;
+	int len;
 
-  mask_width = kvp->key[2] & 0xFF;
+	vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
 
-  ap->count_by_prefix_length[mask_width]++;
+	clib_memset (count_by_prefix_length, 0, sizeof(count_by_prefix_length));
 
-  return (BIHASH_WALK_CONTINUE);
+	hash_foreach_mem(key, fei, fib->fib_entry_by_dst_address, ({
+	    ASSERT(key->len <= 128);
+	    count_by_prefix_length[key->len]++;
+	}));
+
+	for (len = 128; len >= 0; len--)
+	{
+	    if (count_by_prefix_length[len])
+		vlib_cli_output (vm, "%=20d%=16lld",
+				 len, count_by_prefix_length[len]);
+	}
+    }
 }
 
 static clib_error_t *
@@ -636,7 +558,6 @@ ip6_show_fib (vlib_main_t * vm,
 	      unformat_input_t * input,
 	      vlib_cli_command_t * cmd)
 {
-    count_routes_in_fib_at_prefix_length_arg_t _ca, *ca = &_ca;
     ip6_main_t * im6 = &ip6_main;
     fib_table_t *fib_table;
     ip6_fib_t * fib;
@@ -683,22 +604,15 @@ ip6_show_fib (vlib_main_t * vm,
 
     if (hash)
     {
-        vlib_cli_output (vm, "IPv6 Non-Forwarding Hash Table:\n%U\n",
-                         BV (format_bihash),
-                         &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
-                         detail);
         vlib_cli_output (vm, "IPv6 Forwarding Hash Table:\n%U\n",
                          BV (format_bihash),
-                         &ip6_fib_table[IP6_FIB_TABLE_FWDING].ip6_hash,
+                         &ip6_fib_fwding_table.ip6_hash,
                          detail);
         return (NULL);
     }
 
     pool_foreach (fib_table, im6->fibs)
      {
-        fib_source_t source;
-        u8 *s = NULL;
-
 	fib = pool_elt_at_index(im6->v6_fibs, fib_table->ft_index);
 	if (table_id >= 0 && table_id != (int)fib->table_id)
 	    continue;
@@ -707,50 +621,9 @@ ip6_show_fib (vlib_main_t * vm,
         if (fib_table->ft_flags & FIB_TABLE_FLAG_IP6_LL)
             continue;
 
-	s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[",
-                   format_fib_table_name, fib->index,
-                   FIB_PROTOCOL_IP6,
-                   fib->index,
-                   format_ip_flow_hash_config,
-                   fib_table->ft_flow_hash_config,
-                   fib_table->ft_epoch,
-                   format_fib_table_flags, fib_table->ft_flags);
-
-        vec_foreach_index(source, fib_table->ft_locks)
-        {
-            if (0 != fib_table->ft_locks[source])
-            {
-                s = format(s, "%U:%d, ",
-                           format_fib_source, source,
-                           fib_table->ft_locks[source]);
-            }
-        }
-        s = format (s, "]");
-        vlib_cli_output (vm, "%v", s);
-        vec_free(s);
-
-	/* Show summary? */
-	if (! verbose)
-	{
-	    clib_bihash_24_8_t * h = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash;
-	    int len;
-
-	    vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
-
-	    clib_memset (ca, 0, sizeof(*ca));
-	    ca->fib_index = fib->index;
-
-	    clib_bihash_foreach_key_value_pair_24_8
-		(h, count_routes_in_fib_at_prefix_length, ca);
-
-	    for (len = 128; len >= 0; len--)
-            {
-		if (ca->count_by_prefix_length[len])
-		    vlib_cli_output (vm, "%=20d%=16lld", 
-				     len, ca->count_by_prefix_length[len]);
-            }
-	    continue;
-	}
+	ip6_fib_table_show(vm, fib_table, !verbose);
+	if (!verbose)
+	  continue;
 
 	if (!matching)
 	{
@@ -906,12 +779,9 @@ ip6_fib_init (vlib_main_t * vm)
     if (ip6_fib_table_size == 0)
         ip6_fib_table_size = IP6_FIB_DEFAULT_HASH_MEMORY_SIZE;
 
-    clib_bihash_init_24_8 (&(ip6_fib_table[IP6_FIB_TABLE_FWDING].ip6_hash),
+    clib_bihash_init_24_8 (&(ip6_fib_fwding_table.ip6_hash),
                            "ip6 FIB fwding table",
                            ip6_fib_table_nbuckets, ip6_fib_table_size);
-    clib_bihash_init_24_8 (&ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
-                           "ip6 FIB non-fwding table",
-                           ip6_fib_table_nbuckets, ip6_fib_table_size);
 
     return (NULL);
 }
diff --git a/src/vnet/fib/ip6_fib.h b/src/vnet/fib/ip6_fib.h
index 706bebbce09..80d56b1a7ba 100644
--- a/src/vnet/fib/ip6_fib.h
+++ b/src/vnet/fib/ip6_fib.h
@@ -26,36 +26,15 @@
 #include <vppinfra/bihash_template.h>
 
 /*
- * Default size of the ip6 fib hash table
+ * Default size of the ip6 fib forwarding hash table
  */
 #define IP6_FIB_DEFAULT_HASH_NUM_BUCKETS (64 * 1024)
 #define IP6_FIB_DEFAULT_HASH_MEMORY_SIZE (32<<20)
 
 /**
- * Enumeration of the FIB table instance types
+ * A representation the forwarding IP6 table
  */
-typedef enum ip6_fib_table_instance_type_t_
-{
-    /**
-     * This table stores the routes that are used to forward traffic.
-     * The key is the prefix, the result the adjacency to forward on.
-     */
-  IP6_FIB_TABLE_FWDING,
-    /**
-     * The table that stores ALL routes learned by the DP.
-     * Some of these routes may not be ready to install in forwarding
-     * at a given time.
-     * The key in this table is the prefix, the result is the fib_entry_t
-     */
-  IP6_FIB_TABLE_NON_FWDING,
-} ip6_fib_table_instance_type_t;
-
-#define IP6_FIB_NUM_TABLES (IP6_FIB_TABLE_NON_FWDING+1)
-
-/**
- * A representation of a single IP6 table
- */
-typedef struct ip6_fib_table_instance_t_
+typedef struct ip6_fib_fwding_table_instance_t_
 {
   /* The hash table */
   clib_bihash_24_8_t ip6_hash;
@@ -64,12 +43,12 @@ typedef struct ip6_fib_table_instance_t_
   uword *non_empty_dst_address_length_bitmap;
   u8 *prefix_lengths_in_search_order;
   i32 dst_address_length_refcounts[129];
-} ip6_fib_table_instance_t;
+} ip6_fib_fwding_table_instance_t;
 
 /**
  * The two FIB tables; fwding and non-fwding
  */
-extern ip6_fib_table_instance_t ip6_fib_table[IP6_FIB_NUM_TABLES];
+extern ip6_fib_fwding_table_instance_t ip6_fib_fwding_table;
 
 extern fib_node_index_t ip6_fib_table_lookup(u32 fib_index,
 					     const ip6_address_t *addr,
@@ -115,13 +94,13 @@ always_inline u32
 ip6_fib_table_fwding_lookup (u32 fib_index,
                              const ip6_address_t * dst)
 {
-    ip6_fib_table_instance_t *table;
+    ip6_fib_fwding_table_instance_t *table;
     clib_bihash_kv_24_8_t kv, value;
     int i, len;
     int rv;
     u64 fib;
 
-    table = &ip6_fib_table[IP6_FIB_TABLE_FWDING];
+    table = &ip6_fib_fwding_table;
     len = vec_len (table->prefix_lengths_in_search_order);
 
     kv.key[0] = dst->as_u64[0];
@@ -230,6 +209,7 @@ u32 ip6_fib_index_from_table_id (u32 table_id)
 }
 
 extern u32 ip6_fib_table_get_index_for_sw_if_index(u32 sw_if_index);
+extern void ip6_fib_table_show (vlib_main_t *vm, fib_table_t *fib_table, int summary);
 
 #endif
 
diff --git a/src/vnet/ip/ip6.h b/src/vnet/ip/ip6.h
index 56eec523d5b..f8462a5cbff 100644
--- a/src/vnet/ip/ip6.h
+++ b/src/vnet/ip/ip6.h
@@ -68,6 +68,11 @@ typedef struct
 
   /* Index into FIB vector. */
   u32 index;
+
+  /**
+   * The hash table DB
+   */
+  uword *fib_entry_by_dst_address;
 } ip6_fib_t;
 
 typedef struct ip6_mfib_t
diff --git a/src/vnet/ip/ip6_ll_table.c b/src/vnet/ip/ip6_ll_table.c
index f9172f6c50c..2234ea9df37 100644
--- a/src/vnet/ip/ip6_ll_table.c
+++ b/src/vnet/ip/ip6_ll_table.c
@@ -144,17 +144,20 @@ ip6_ll_table_entry_delete (const ip6_ll_prefix_t * ilp)
   fib_node_index_t ip6_ll_entry_index;
   u32 fib_index;
 
+  fib_index = ip6_ll_fib_get (ilp->ilp_sw_if_index);
+  if (~0 == fib_index)
+    return;
+
   ip6_ll_entry_index = ip6_ll_table_lookup_exact_match (ilp);
+  if (FIB_NODE_INDEX_INVALID == ip6_ll_entry_index)
+    return;
 
-  if (FIB_NODE_INDEX_INVALID != ip6_ll_entry_index)
-    fib_table_entry_delete_index (ip6_ll_entry_index, FIB_SOURCE_IP6_ND);
+  fib_table_entry_delete_index (ip6_ll_entry_index, FIB_SOURCE_IP6_ND);
 
   /*
    * if there are no ND sourced prefixes left, then we can clean up this FIB
    */
-  fib_index = ip6_ll_fib_get (ilp->ilp_sw_if_index);
-  if (~0 != fib_index &&
-      0 == fib_table_get_num_entries (fib_index, FIB_PROTOCOL_IP6,
+  if (0 == fib_table_get_num_entries (fib_index, FIB_PROTOCOL_IP6,
 				      FIB_SOURCE_IP6_ND))
     {
       fib_table_unlock (fib_index, FIB_PROTOCOL_IP6, FIB_SOURCE_IP6_ND);
@@ -208,33 +211,10 @@ ip6_ll_table_show_all (vlib_main_t * vm, u32 fib_index)
   vec_free (ctx.entries);
 }
 
-typedef struct
-{
-  u32 fib_index;
-  u64 count_by_prefix_length[129];
-} count_routes_in_fib_at_prefix_length_arg_t;
-
-static int
-count_routes_in_fib_at_prefix_length (clib_bihash_kv_24_8_t * kvp, void *arg)
-{
-  count_routes_in_fib_at_prefix_length_arg_t *ap = arg;
-  int mask_width;
-
-  if ((kvp->key[2] >> 32) != ap->fib_index)
-    return (BIHASH_WALK_CONTINUE);
-
-  mask_width = kvp->key[2] & 0xFF;
-
-  ap->count_by_prefix_length[mask_width]++;
-
-  return (BIHASH_WALK_CONTINUE);
-}
-
 static clib_error_t *
 ip6_ll_show_fib (vlib_main_t * vm,
 		 unformat_input_t * input, vlib_cli_command_t * cmd)
 {
-  count_routes_in_fib_at_prefix_length_arg_t _ca, *ca = &_ca;
   fib_table_t *fib_table;
   int verbose, matching;
   ip6_address_t matching_address;
@@ -272,9 +252,6 @@ ip6_ll_show_fib (vlib_main_t * vm,
 
   vec_foreach_index (sw_if_index, ip6_ll_table.ilt_fibs)
   {
-    fib_source_t source;
-    u8 *s = NULL;
-
     fib_index = ip6_ll_table.ilt_fibs[sw_if_index];
     if (~0 == fib_index)
       continue;
@@ -284,44 +261,9 @@ ip6_ll_show_fib (vlib_main_t * vm,
     if (!(fib_table->ft_flags & FIB_TABLE_FLAG_IP6_LL))
       continue;
 
-    s = format (s, "%U, fib_index:%d, locks:[",
-		format_fib_table_name, fib_index,
-		FIB_PROTOCOL_IP6, fib_index);
-    vec_foreach_index (source, fib_table->ft_locks)
-    {
-      if (0 != fib_table->ft_locks[source])
-	{
-	  s = format (s, "%U:%d, ",
-		      format_fib_source, source, fib_table->ft_locks[source]);
-	}
-    }
-    s = format (s, "]");
-    vlib_cli_output (vm, "%v", s);
-    vec_free (s);
-
-    /* Show summary? */
+    ip6_fib_table_show (vm, fib_table, !verbose);
     if (!verbose)
-      {
-	clib_bihash_24_8_t *h =
-	  &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash;
-	int len;
-
-	vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
-
-	clib_memset (ca, 0, sizeof (*ca));
-	ca->fib_index = fib_index;
-
-	clib_bihash_foreach_key_value_pair_24_8
-	  (h, count_routes_in_fib_at_prefix_length, ca);
-
-	for (len = 128; len >= 0; len--)
-	  {
-	    if (ca->count_by_prefix_length[len])
-	      vlib_cli_output (vm, "%=20d%=16lld",
-			       len, ca->count_by_prefix_length[len]);
-	  }
-	continue;
-      }
+      continue;
 
     if (!matching)
       {