fib: A 16-8-8 and a 8-8-8-8 versions of an ip4_fib_t

Type: feature

The difference being the MTRIE type they contain.
THE FIB continues to use the 16-8-8 version.

Signed-off-by: Neale Ranns <neale@graphiant.com>
Change-Id: I5a54d4e6e6cc639f18a3fb65ef2925507a7ef1de

13 files changed, 932 insertions, 417 deletions

diff --git a/src/vnet/CMakeLists.txt b/src/vnet/CMakeLists.txt
index a800230c9d5..df23738013d 100644
--- a/src/vnet/CMakeLists.txt
+++ b/src/vnet/CMakeLists.txt
@@ -1164,7 +1164,10 @@ list(APPEND VNET_HEADERS
 
 list(APPEND VNET_SOURCES
   fib/fib.c
+  fib/ip4_fib_hash.c
   fib/ip4_fib.c
+  fib/ip4_fib_16.c
+  fib/ip4_fib_8.c
   fib/ip6_fib.c
   fib/mpls_fib.c
   fib/fib_table.c
diff --git a/src/vnet/fib/ip4_fib.c b/src/vnet/fib/ip4_fib.c
index e8ab653e53a..a343c2b5f37 100644
--- a/src/vnet/fib/ip4_fib.c
+++ b/src/vnet/fib/ip4_fib.c
@@ -99,6 +99,49 @@ static const ip4_fib_table_special_prefix_t ip4_specials[] = {
     }
 };
 
+void
+ip4_fib_hash_load_specials (u32 fib_index)
+{
+    /*
+     * add the special entries into the new FIB
+     */
+    int ii;
+
+    for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++)
+    {
+	fib_prefix_t prefix = ip4_specials[ii].ift_prefix;
+
+	prefix.fp_addr.ip4.data_u32 =
+	    clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32);
+
+	fib_table_entry_special_add(fib_index,
+				    &prefix,
+				    ip4_specials[ii].ift_source,
+				    ip4_specials[ii].ift_flag);
+    }
+}
+
+void
+ip4_fib_hash_flush_specials (u32 fib_index)
+{
+    int ii;
+
+    /*
+     * remove all the specials we added when the table was created.
+     * In reverse order so the default route is last.
+     */
+    for (ii = ARRAY_LEN(ip4_specials) - 1; ii >= 0; ii--)
+    {
+	fib_prefix_t prefix = ip4_specials[ii].ift_prefix;
+
+	prefix.fp_addr.ip4.data_u32 =
+	    clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32);
+
+	fib_table_entry_special_remove(fib_index,
+				       &prefix,
+				       ip4_specials[ii].ift_source);
+    }
+}
 
 static u32
 ip4_create_fib_with_table_id (u32 table_id,
@@ -110,44 +153,34 @@ ip4_create_fib_with_table_id (u32 table_id,
     pool_get(ip4_main.fibs, fib_table);
     clib_memset(fib_table, 0, sizeof(*fib_table));
 
-    pool_get_aligned(ip4_main.v4_fibs, v4_fib, CLIB_CACHE_LINE_BYTES);
-
-    ASSERT((fib_table - ip4_main.fibs) ==
-           (v4_fib - ip4_main.v4_fibs));
+    pool_get_aligned(ip4_fibs, v4_fib, CLIB_CACHE_LINE_BYTES);
 
     fib_table->ft_proto = FIB_PROTOCOL_IP4;
-    fib_table->ft_index =
-	v4_fib->index =
-	    (fib_table - ip4_main.fibs);
+    fib_table->ft_index = (v4_fib - ip4_fibs);
+
+    /*
+     * It is required that the index of the fib_table_t in its pool
+     * is the same as the index of the ip4_fib_t in its pool, since the
+     * rest of the code usues the 'fib_index' to mean either of these
+     * objects, depending on the context.
+     */
+    ASSERT(fib_table->ft_index == fib_table - ip4_main.fibs);
 
     hash_set (ip4_main.fib_index_by_table_id, table_id, fib_table->ft_index);
 
     fib_table->ft_table_id =
-	v4_fib->table_id =
+	v4_fib->hash.table_id =
 	    table_id;
     fib_table->ft_flow_hash_config = IP_FLOW_HASH_DEFAULT;
 
     fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_IP4, src);
 
-    ip4_mtrie_16_init(&v4_fib->mtrie);
+    ip4_fib_table_init(v4_fib);
 
     /*
      * add the special entries into the new FIB
      */
-    int ii;
-
-    for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++)
-    {
-	fib_prefix_t prefix = ip4_specials[ii].ift_prefix;
-
-	prefix.fp_addr.ip4.data_u32 =
-	    clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32);
-
-	fib_table_entry_special_add(fib_table->ft_index,
-				    &prefix,
-				    ip4_specials[ii].ift_source,
-				    ip4_specials[ii].ift_flag);
-    }
+    ip4_fib_hash_load_specials(fib_table - ip4_main.fibs);
 
     return (fib_table->ft_index);
 }
@@ -156,25 +189,14 @@ void
 ip4_fib_table_destroy (u32 fib_index)
 {
     fib_table_t *fib_table = pool_elt_at_index(ip4_main.fibs, fib_index);
-    ip4_fib_t *v4_fib = pool_elt_at_index(ip4_main.v4_fibs, fib_index);
+    ip4_fib_t *v4_fib = pool_elt_at_index(ip4_fibs, fib_table->ft_index);
     u32 *n_locks;
-    int ii;
 
     /*
      * remove all the specials we added when the table was created.
      * In reverse order so the default route is last.
      */
-    for (ii = ARRAY_LEN(ip4_specials) - 1; ii >= 0; ii--)
-    {
-	fib_prefix_t prefix = ip4_specials[ii].ift_prefix;
-
-	prefix.fp_addr.ip4.data_u32 =
-	    clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32);
-
-	fib_table_entry_special_remove(fib_table->ft_index,
-				       &prefix,
-				       ip4_specials[ii].ift_source);
-    }
+    ip4_fib_hash_flush_specials(fib_table - ip4_main.fibs);
 
     /*
      * validate no more routes.
@@ -195,9 +217,9 @@ ip4_fib_table_destroy (u32 fib_index)
     }
 
     vec_free(fib_table->ft_src_route_counts);
-    ip4_mtrie_16_free(&v4_fib->mtrie);
+    ip4_fib_table_free(v4_fib);
 
-    pool_put(ip4_main.v4_fibs, v4_fib);
+    pool_put(ip4_fibs, v4_fib);
     pool_put(ip4_main.fibs, fib_table);
 }
 
@@ -237,268 +259,6 @@ ip4_fib_table_get_index_for_sw_if_index (u32 sw_if_index)
     return (ip4_main.fib_index_by_sw_if_index[sw_if_index]);
 }
 
-/*
- * ip4_fib_table_lookup_exact_match
- *
- * Exact match prefix lookup
- */
-fib_node_index_t
-ip4_fib_table_lookup_exact_match (const ip4_fib_t *fib,
-				  const ip4_address_t *addr,
-				  u32 len)
-{
-    uword * hash, * result;
-    u32 key;
-
-    hash = fib->fib_entry_by_dst_address[len];
-    key  = (addr->data_u32 & ip4_main.fib_masks[len]);
-
-    result = hash_get(hash, key);
-
-    if (NULL != result) {
-	return (result[0]);
-    }
-    return (FIB_NODE_INDEX_INVALID);
-}
-
-/*
- * ip4_fib_table_lookup_adj
- *
- * Longest prefix match
- */
-index_t
-ip4_fib_table_lookup_lb (ip4_fib_t *fib,
-			 const ip4_address_t *addr)
-{
-    fib_node_index_t fei;
-
-    fei = ip4_fib_table_lookup(fib, addr, 32);
-
-    if (FIB_NODE_INDEX_INVALID != fei)
-    {
-	const dpo_id_t *dpo;
-
-	dpo = fib_entry_contribute_ip_forwarding(fei);
-
-	return (dpo->dpoi_index);
-    }
-    return (INDEX_INVALID);
-}
-
-/*
- * ip4_fib_table_lookup
- *
- * Longest prefix match
- */
-fib_node_index_t
-ip4_fib_table_lookup (const ip4_fib_t *fib,
-		      const ip4_address_t *addr,
-		      u32 len)
-{
-    uword * hash, * result;
-    i32 mask_len;
-    u32 key;
-
-    for (mask_len = len; mask_len >= 0; mask_len--)
-    {
-	hash = fib->fib_entry_by_dst_address[mask_len];
-	key = (addr->data_u32 & ip4_main.fib_masks[mask_len]);
-
-	result = hash_get (hash, key);
-
-	if (NULL != result) {
-	    return (result[0]);
-	}
-    }
-    return (FIB_NODE_INDEX_INVALID);
-}
-
-void
-ip4_fib_table_entry_insert (ip4_fib_t *fib,
-			    const ip4_address_t *addr,
-			    u32 len,
-			    fib_node_index_t fib_entry_index)
-{
-    uword * hash, * result;
-    u32 key;
-
-    key = (addr->data_u32 & ip4_main.fib_masks[len]);
-    hash = fib->fib_entry_by_dst_address[len];
-    result = hash_get (hash, key);
-
-    if (NULL == result) {
-	/*
-	 * adding a new entry
-	 */
-
-	if (NULL == hash) {
-	    hash = hash_create (32 /* elts */, sizeof (uword));
-	    hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
-
-	}
-	hash = hash_set(hash, key, fib_entry_index);
-	fib->fib_entry_by_dst_address[len] = hash;
-    }
-    else
-    {
-	ASSERT(0);
-    }
-}
-
-void
-ip4_fib_table_entry_remove (ip4_fib_t *fib,
-			    const ip4_address_t *addr,
-			    u32 len)
-{
-    uword * hash, * result;
-    u32 key;
-
-    key = (addr->data_u32 & ip4_main.fib_masks[len]);
-    hash = fib->fib_entry_by_dst_address[len];
-    result = hash_get (hash, key);
-
-    if (NULL == result)
-    {
-	/*
-	 * removing a non-existent entry. i'll allow it.
-	 */
-    }
-    else
-    {
-	hash_unset(hash, key);
-    }
-
-    fib->fib_entry_by_dst_address[len] = hash;
-}
-
-void
-ip4_fib_table_fwding_dpo_update (ip4_fib_t *fib,
-				 const ip4_address_t *addr,
-				 u32 len,
-				 const dpo_id_t *dpo)
-{
-    ip4_mtrie_16_route_add(&fib->mtrie, addr, len, dpo->dpoi_index);
-}
-
-void
-ip4_fib_table_fwding_dpo_remove (ip4_fib_t *fib,
-				 const ip4_address_t *addr,
-				 u32 len,
-				 const dpo_id_t *dpo,
-                                 u32 cover_index)
-{
-    const fib_prefix_t *cover_prefix;
-    const dpo_id_t *cover_dpo;
-
-    /*
-     * We need to pass the MTRIE the LB index and address length of the
-     * covering prefix, so it can fill the plys with the correct replacement
-     * for the entry being removed
-     */
-    cover_prefix = fib_entry_get_prefix(cover_index);
-    cover_dpo = fib_entry_contribute_ip_forwarding(cover_index);
-
-    ip4_mtrie_16_route_del(&fib->mtrie,
-                            addr, len, dpo->dpoi_index,
-                            cover_prefix->fp_len,
-                            cover_dpo->dpoi_index);
-}
-
-void
-ip4_fib_table_walk (ip4_fib_t *fib,
-                    fib_table_walk_fn_t fn,
-                    void *ctx)
-{
-    fib_prefix_t root = {
-        .fp_proto = FIB_PROTOCOL_IP4,
-        // address and length default to all 0
-    };
-
-    /*
-     * A full tree walk is the dengenerate case of a sub-tree from
-     * the very root
-     */
-    return (ip4_fib_table_sub_tree_walk(fib, &root, fn, ctx));
-}
-
-void
-ip4_fib_table_sub_tree_walk (ip4_fib_t *fib,
-                             const fib_prefix_t *root,
-                             fib_table_walk_fn_t fn,
-                             void *ctx)
-{
-    fib_prefix_t *sub_trees = NULL;
-    int i;
-
-    /*
-     * There is no efficient way to walk this array of hash tables.
-     * so we walk each table with a mask length greater than and equal to
-     * the required root and check it is covered by the root.
-     */
-    for (i = root->fp_len;
-         i < ARRAY_LEN (fib->fib_entry_by_dst_address);
-         i++)
-    {
-	uword * hash = fib->fib_entry_by_dst_address[i];
-
-	if (NULL != hash)
-	{
-            ip4_address_t key;
-	    hash_pair_t * p;
-
-	    hash_foreach_pair (p, hash,
-	    ({
-                key.as_u32 = p->key;
-                if (ip4_destination_matches_route(&ip4_main,
-                                                  &key,
-                                                  &root->fp_addr.ip4,
-                                                  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, sub_trees)
-                    {
-                        if (ip4_destination_matches_route(&ip4_main,
-                                                          &key,
-                                                          &sub_tree->fp_addr.ip4,
-                                                          sub_tree->fp_len))
-                        {
-                            skip = 1;
-                            break;
-                        }
-                    }
-
-                    if (!skip)
-                    {
-                        switch (fn(p->value[0], ctx))
-                        {
-                        case FIB_TABLE_WALK_CONTINUE:
-                            break;
-                        case FIB_TABLE_WALK_SUB_TREE_STOP: {
-                            fib_prefix_t pfx = {
-                                .fp_proto = FIB_PROTOCOL_IP4,
-                                .fp_len = i,
-                                .fp_addr.ip4 = key,
-                            };
-                            vec_add1(sub_trees, pfx);
-                            break;
-                        }
-                        case FIB_TABLE_WALK_STOP:
-                            goto done;
-                        }
-                    }
-                }
-	    }));
-	}
-    }
-done:
-    vec_free(sub_trees);
-    return;
-}
 
 /**
  * Walk show context
@@ -573,12 +333,11 @@ ip4_show_fib (vlib_main_t * vm,
 	      vlib_cli_command_t * cmd)
 {
     ip4_main_t * im4 = &ip4_main;
-    fib_table_t * fib_table;
     u64 total_mtrie_memory, total_hash_memory;
     int verbose, matching, mtrie, memory;
     ip4_address_t matching_address;
-    u32 matching_mask = 32;
-    int i, table_id = -1, fib_index = ~0;
+    u32 fib_index, matching_mask = 32;
+    int i, table_id = -1, user_fib_index = ~0;
     int detail = 0;
 
     verbose = 1;
@@ -610,21 +369,22 @@ ip4_show_fib (vlib_main_t * vm,
 
 	else if (unformat (input, "table %d", &table_id))
 	    ;
-	else if (unformat (input, "index %d", &fib_index))
+	else if (unformat (input, "index %d", &user_fib_index))
 	    ;
 	else
 	    break;
     }
 
-    pool_foreach (fib_table, im4->fibs)
+    pool_foreach_index (fib_index, im4->fibs)
      {
-	ip4_fib_t *fib = pool_elt_at_index(im4->v4_fibs, fib_table->ft_index);
+	fib_table_t *fib_table = pool_elt_at_index(im4->fibs, fib_index);
+	ip4_fib_t *fib = pool_elt_at_index(ip4_fibs, fib_table->ft_index);
         fib_source_t source;
         u8 *s = NULL;
 
-	if (table_id >= 0 && table_id != (int)fib->table_id)
+	if (table_id >= 0 && table_id != (int)fib->hash.table_id)
 	    continue;
-	if (fib_index != ~0 && fib_index != (int)fib->index)
+	if (user_fib_index != ~0 && user_fib_index != fib_index)
 	    continue;
 
         if (memory)
@@ -632,12 +392,12 @@ ip4_show_fib (vlib_main_t * vm,
             uword mtrie_size, hash_size;
 
 
-            mtrie_size = ip4_mtrie_16_memory_usage(&fib->mtrie);
+            mtrie_size = ip4_mtrie_memory_usage(&fib->mtrie);
             hash_size = 0;
 
-	    for (i = 0; i < ARRAY_LEN (fib->fib_entry_by_dst_address); i++)
+	    for (i = 0; i < ARRAY_LEN (fib->hash.fib_entry_by_dst_address); i++)
 	    {
-		uword * hash = fib->fib_entry_by_dst_address[i];
+		uword * hash = fib->hash.fib_entry_by_dst_address[i];
                 if (NULL != hash)
                 {
                     hash_size += hash_bytes(hash);
@@ -646,7 +406,7 @@ ip4_show_fib (vlib_main_t * vm,
 
             if (verbose)
                 vlib_cli_output (vm, "%U mtrie:%d hash:%d",
-                                 format_fib_table_name, fib->index,
+                                 format_fib_table_name, fib_index,
                                  FIB_PROTOCOL_IP4,
                                  mtrie_size,
                                  hash_size);
@@ -656,9 +416,9 @@ ip4_show_fib (vlib_main_t * vm,
         }
 
 	s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[",
-                   format_fib_table_name, fib->index,
+                   format_fib_table_name, fib_index,
                    FIB_PROTOCOL_IP4,
-                   fib->index,
+                   fib_index,
                    format_ip_flow_hash_config,
                    fib_table->ft_flow_hash_config,
                    fib_table->ft_epoch,
@@ -679,15 +439,15 @@ ip4_show_fib (vlib_main_t * vm,
 	/* Show summary? */
 	if (mtrie)
         {
-	    vlib_cli_output (vm, "%U", format_ip4_mtrie_16, &fib->mtrie, verbose);
+	    vlib_cli_output (vm, "%U", format_ip4_mtrie, &fib->mtrie, verbose);
             continue;
         }
 	if (! verbose)
 	{
 	    vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
-	    for (i = 0; i < ARRAY_LEN (fib->fib_entry_by_dst_address); i++)
+	    for (i = 0; i < ARRAY_LEN (fib->hash.fib_entry_by_dst_address); i++)
 	    {
-		uword * hash = fib->fib_entry_by_dst_address[i];
+		uword * hash = fib->hash.fib_entry_by_dst_address[i];
 		uword n_elts = hash_elts (hash);
 		if (n_elts > 0)
 		    vlib_cli_output (vm, "%20d%16d", i, n_elts);
diff --git a/src/vnet/fib/ip4_fib.h b/src/vnet/fib/ip4_fib.h
index 46bfcaf85f1..0f6911dd3aa 100644
--- a/src/vnet/fib/ip4_fib.h
+++ b/src/vnet/fib/ip4_fib.h
@@ -34,77 +34,28 @@
 #include <vnet/ip/ip.h>
 #include <vnet/fib/fib_entry.h>
 #include <vnet/fib/fib_table.h>
-#include <vnet/ip/ip4_mtrie.h>
-
-typedef struct ip4_fib_t_
-{
-  /** Required for pool_get_aligned */
-  CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
-
-  /**
-   * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes.
-   * First member so it's in the first cacheline.
-   */
-  ip4_mtrie_16_t mtrie;
-
-  /* Hash table for each prefix length mapping. */
-  uword *fib_entry_by_dst_address[33];
-
-  /* Table ID (hash key) for this FIB. */
-  u32 table_id;
-
-  /* Index into FIB vector. */
-  u32 index;
-} ip4_fib_t;
-
-extern fib_node_index_t ip4_fib_table_lookup(const ip4_fib_t *fib,
-					     const ip4_address_t *addr,
-					     u32 len);
-extern fib_node_index_t ip4_fib_table_lookup_exact_match(const ip4_fib_t *fib,
-							 const ip4_address_t *addr,
-							 u32 len);
-
-extern void ip4_fib_table_entry_remove(ip4_fib_t *fib,
-				       const ip4_address_t *addr,
-				       u32 len);
-
-extern void ip4_fib_table_entry_insert(ip4_fib_t *fib,
-				       const ip4_address_t *addr,
-				       u32 len,
-				       fib_node_index_t fib_entry_index);
-extern void ip4_fib_table_destroy(u32 fib_index);
-
-extern void ip4_fib_table_fwding_dpo_update(ip4_fib_t *fib,
-					    const ip4_address_t *addr,
-					    u32 len,
-					    const dpo_id_t *dpo);
-
-extern void ip4_fib_table_fwding_dpo_remove(ip4_fib_t *fib,
-					    const ip4_address_t *addr,
-					    u32 len,
-					    const dpo_id_t *dpo,
-                                            fib_node_index_t cover_index);
-extern u32 ip4_fib_table_lookup_lb (ip4_fib_t *fib,
-				    const ip4_address_t * dst);
+#include <vnet/fib/ip4_fib_8.h>
+#include <vnet/fib/ip4_fib_16.h>
 
 /**
- * @brief Walk all entries in a FIB table
- * N.B: This is NOT safe to deletes. If you need to delete walk the whole
- * table and store elements in a vector, then delete the elements
+ * the FIB module uses the 16-8-8 stride trie
  */
-extern void ip4_fib_table_walk(ip4_fib_t *fib,
-                               fib_table_walk_fn_t fn,
-                               void *ctx);
-
-/**
- * @brief Walk all entries in a sub-tree of the FIB table
- * N.B: This is NOT safe to deletes. If you need to delete walk the whole
- * table and store elements in a vector, then delete the elements
- */
-extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib,
-                                        const fib_prefix_t *root,
-                                        fib_table_walk_fn_t fn,
-                                        void *ctx);
+typedef ip4_fib_16_t ip4_fib_t;
+
+#define ip4_fibs ip4_fib_16s
+#define ip4_fib_table_lookup ip4_fib_16_table_lookup
+#define ip4_fib_table_lookup_exact_match ip4_fib_16_table_lookup_exact_match
+#define ip4_fib_table_entry_remove ip4_fib_16_table_entry_remove
+#define ip4_fib_table_entry_insert ip4_fib_16_table_entry_insert
+#define ip4_fib_table_fwding_dpo_update ip4_fib_16_table_fwding_dpo_update
+#define ip4_fib_table_fwding_dpo_remove ip4_fib_16_table_fwding_dpo_remove
+#define ip4_fib_table_lookup_lb ip4_fib_16_table_lookup_lb
+#define ip4_fib_table_walk ip4_fib_16_table_walk
+#define ip4_fib_table_sub_tree_walk ip4_fib_16_table_sub_tree_walk
+#define ip4_fib_table_init ip4_fib_16_table_init
+#define ip4_fib_table_free ip4_fib_16_table_free
+#define ip4_mtrie_memory_usage ip4_mtrie_16_memory_usage
+#define format_ip4_mtrie format_ip4_mtrie_16
 
 /**
  * @brief Get the FIB at the given index
@@ -112,7 +63,7 @@ extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib,
 static inline ip4_fib_t *
 ip4_fib_get (u32 index)
 {
-    return (pool_elt_at_index(ip4_main.v4_fibs, index));
+    return (pool_elt_at_index(ip4_fibs, index));
 }
 
 always_inline u32
@@ -138,6 +89,7 @@ ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst)
 extern u32 ip4_fib_table_find_or_create_and_lock(u32 table_id,
                                                  fib_source_t src);
 extern u32 ip4_fib_table_create_and_lock(fib_source_t src);
+extern void ip4_fib_table_destroy(u32 fib_index);
 
 extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args);
 
diff --git a/src/vnet/fib/ip4_fib_16.c b/src/vnet/fib/ip4_fib_16.c
new file mode 100644
index 00000000000..7699e8926f1
--- /dev/null
+++ b/src/vnet/fib/ip4_fib_16.c
@@ -0,0 +1,137 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry.h>
+#include <vnet/fib/ip4_fib.h>
+
+ip4_fib_16_t *ip4_fib_16s;
+
+void
+ip4_fib_16_table_init (ip4_fib_16_t *fib)
+{
+    ip4_mtrie_16_init(&fib->mtrie);
+}
+
+void
+ip4_fib_16_table_free (ip4_fib_16_t *fib)
+{
+    ip4_mtrie_16_free(&fib->mtrie);
+}
+
+/*
+ * ip4_fib_16_table_lookup_exact_match
+ *
+ * Exact match prefix lookup
+ */
+fib_node_index_t
+ip4_fib_16_table_lookup_exact_match (const ip4_fib_16_t *fib,
+                                     const ip4_address_t *addr,
+                                     u32 len)
+{
+    return (ip4_fib_hash_table_lookup_exact_match(&fib->hash, addr, len));
+}
+
+/*
+ * ip4_fib_16_table_lookup_adj
+ *
+ * Longest prefix match
+ */
+index_t
+ip4_fib_16_table_lookup_lb (ip4_fib_16_t *fib,
+                            const ip4_address_t *addr)
+{
+    return (ip4_fib_hash_table_lookup_lb(&fib->hash, addr));
+}
+
+/*
+ * ip4_fib_16_table_lookup
+ *
+ * Longest prefix match
+ */
+fib_node_index_t
+ip4_fib_16_table_lookup (const ip4_fib_16_t *fib,
+                         const ip4_address_t *addr,
+                         u32 len)
+{
+    return (ip4_fib_hash_table_lookup(&fib->hash, addr, len));
+}
+
+void
+ip4_fib_16_table_entry_insert (ip4_fib_16_t *fib,
+                               const ip4_address_t *addr,
+                               u32 len,
+                               fib_node_index_t fib_entry_index)
+{
+    return (ip4_fib_hash_table_entry_insert(&fib->hash, addr, len, fib_entry_index));
+}
+
+void
+ip4_fib_16_table_entry_remove (ip4_fib_16_t *fib,
+                               const ip4_address_t *addr,
+                               u32 len)
+{
+    return (ip4_fib_hash_table_entry_remove(&fib->hash, addr, len));
+}
+
+void
+ip4_fib_16_table_fwding_dpo_update (ip4_fib_16_t *fib,
+				 const ip4_address_t *addr,
+				 u32 len,
+				 const dpo_id_t *dpo)
+{
+    ip4_mtrie_16_route_add(&fib->mtrie, addr, len, dpo->dpoi_index);
+}
+
+void
+ip4_fib_16_table_fwding_dpo_remove (ip4_fib_16_t *fib,
+                                    const ip4_address_t *addr,
+                                    u32 len,
+                                    const dpo_id_t *dpo,
+                                    u32 cover_index)
+{
+    const fib_prefix_t *cover_prefix;
+    const dpo_id_t *cover_dpo;
+
+    /*
+     * We need to pass the MTRIE the LB index and address length of the
+     * covering prefix, so it can fill the plys with the correct replacement
+     * for the entry being removed
+     */
+    cover_prefix = fib_entry_get_prefix(cover_index);
+    cover_dpo = fib_entry_contribute_ip_forwarding(cover_index);
+
+    ip4_mtrie_16_route_del(&fib->mtrie,
+                            addr, len, dpo->dpoi_index,
+                            cover_prefix->fp_len,
+                            cover_dpo->dpoi_index);
+}
+
+void
+ip4_fib_16_table_walk (ip4_fib_16_t *fib,
+                       fib_table_walk_fn_t fn,
+                       void *ctx)
+{
+    ip4_fib_hash_table_walk(&fib->hash, fn, ctx);
+}
+
+void
+ip4_fib_16_table_sub_tree_walk (ip4_fib_16_t *fib,
+                                const fib_prefix_t *root,
+                                fib_table_walk_fn_t fn,
+                                void *ctx)
+{
+    ip4_fib_hash_table_sub_tree_walk(&fib->hash, root, fn, ctx);
+}
diff --git a/src/vnet/fib/ip4_fib_16.h b/src/vnet/fib/ip4_fib_16.h
new file mode 100644
index 00000000000..b82ad57a04a
--- /dev/null
+++ b/src/vnet/fib/ip4_fib_16.h
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/**
+ * @brief The IPv4 FIB
+ *
+ * FIBs are composed of two prefix data-bases (akak tables). The non-forwarding
+ * table contains all the routes that the control plane has programmed, the
+ * forwarding table contains the sub-set of those routes that can be used to
+ * forward packets.
+ * In the IPv4 FIB the non-forwarding table is an array of hash tables indexed
+ * by mask length, the forwarding table is an mtrie
+ *
+ * This IPv4 FIB is used by the protocol independent FIB. So directly using
+ * this APIs in client code is not encouraged. However, this IPv4 FIB can be
+ * used if all the client wants is an IPv4 prefix data-base
+ */
+
+#ifndef __IP4_FIB_16_H__
+#define __IP4_FIB_16_H__
+
+#include <vnet/fib/ip4_fib_hash.h>
+#include <vnet/ip/ip4_mtrie.h>
+
+typedef struct ip4_fib_16_t_
+{
+  /** Required for pool_get_aligned */
+  CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
+
+  /**
+   * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes.
+   * First member so it's in the first cacheline.
+   */
+  ip4_mtrie_16_t mtrie;
+
+  /**
+   * The hash table DB
+   */
+  ip4_fib_hash_t hash;
+} ip4_fib_16_t;
+
+extern ip4_fib_16_t *ip4_fib_16s;
+
+extern fib_node_index_t ip4_fib_16_table_lookup(const ip4_fib_16_t *fib,
+                                                const ip4_address_t *addr,
+                                                u32 len);
+extern fib_node_index_t ip4_fib_16_table_lookup_exact_match(const ip4_fib_16_t *fib,
+                                                            const ip4_address_t *addr,
+                                                            u32 len);
+
+extern void ip4_fib_16_table_entry_remove(ip4_fib_16_t *fib,
+                                          const ip4_address_t *addr,
+                                          u32 len);
+
+extern void ip4_fib_16_table_entry_insert(ip4_fib_16_t *fib,
+                                          const ip4_address_t *addr,
+                                          u32 len,
+                                          fib_node_index_t fib_entry_index);
+extern void ip4_fib_16_table_free(ip4_fib_16_t *fib);
+extern void ip4_fib_16_table_init(ip4_fib_16_t *fib);
+
+extern void ip4_fib_16_table_fwding_dpo_update(ip4_fib_16_t *fib,
+                                               const ip4_address_t *addr,
+                                               u32 len,
+                                               const dpo_id_t *dpo);
+
+extern void ip4_fib_16_table_fwding_dpo_remove(ip4_fib_16_t *fib,
+                                               const ip4_address_t *addr,
+                                               u32 len,
+                                               const dpo_id_t *dpo,
+                                               fib_node_index_t cover_index);
+extern u32 ip4_fib_16_table_lookup_lb (ip4_fib_16_t *fib,
+                                       const ip4_address_t * dst);
+
+/**
+ * @brief Walk all entries in a FIB table
+ * N.B: This is NOT safe to deletes. If you need to delete walk the whole
+ * table and store elements in a vector, then delete the elements
+ */
+extern void ip4_fib_16_table_walk(ip4_fib_16_t *fib,
+                               fib_table_walk_fn_t fn,
+                               void *ctx);
+
+/**
+ * @brief Walk all entries in a sub-tree of the FIB table
+ * N.B: This is NOT safe to deletes. If you need to delete walk the whole
+ * table and store elements in a vector, then delete the elements
+ */
+extern void ip4_fib_16_table_sub_tree_walk(ip4_fib_16_t *fib,
+                                           const fib_prefix_t *root,
+                                           fib_table_walk_fn_t fn,
+                                           void *ctx);
+
+#endif
+
diff --git a/src/vnet/fib/ip4_fib_8.c b/src/vnet/fib/ip4_fib_8.c
new file mode 100644
index 00000000000..587e28a8c9c
--- /dev/null
+++ b/src/vnet/fib/ip4_fib_8.c
@@ -0,0 +1,137 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry.h>
+#include <vnet/fib/ip4_fib.h>
+
+ip4_fib_8_t *ip4_fib_8s;
+
+void
+ip4_fib_8_table_init (ip4_fib_8_t *fib)
+{
+    ip4_mtrie_8_init(&fib->mtrie);
+}
+
+void
+ip4_fib_8_table_free (ip4_fib_8_t *fib)
+{
+    ip4_mtrie_8_free(&fib->mtrie);
+}
+
+/*
+ * ip4_fib_8_table_lookup_exact_match
+ *
+ * Exact match prefix lookup
+ */
+fib_node_index_t
+ip4_fib_8_table_lookup_exact_match (const ip4_fib_8_t *fib,
+                                     const ip4_address_t *addr,
+                                     u32 len)
+{
+    return (ip4_fib_hash_table_lookup_exact_match(&fib->hash, addr, len));
+}
+
+/*
+ * ip4_fib_8_table_lookup_adj
+ *
+ * Longest prefix match
+ */
+index_t
+ip4_fib_8_table_lookup_lb (ip4_fib_8_t *fib,
+                           const ip4_address_t *addr)
+{
+    return (ip4_fib_hash_table_lookup_lb(&fib->hash, addr));
+}
+
+/*
+ * ip4_fib_8_table_lookup
+ *
+ * Longest prefix match
+ */
+fib_node_index_t
+ip4_fib_8_table_lookup (const ip4_fib_8_t *fib,
+                        const ip4_address_t *addr,
+                        u32 len)
+{
+    return (ip4_fib_hash_table_lookup(&fib->hash, addr, len));
+}
+
+void
+ip4_fib_8_table_entry_insert (ip4_fib_8_t *fib,
+                              const ip4_address_t *addr,
+                              u32 len,
+                              fib_node_index_t fib_entry_index)
+{
+    return (ip4_fib_hash_table_entry_insert(&fib->hash, addr, len, fib_entry_index));
+}
+
+void
+ip4_fib_8_table_entry_remove (ip4_fib_8_t *fib,
+                              const ip4_address_t *addr,
+                              u32 len)
+{
+    return (ip4_fib_hash_table_entry_remove(&fib->hash, addr, len));
+}
+
+void
+ip4_fib_8_table_fwding_dpo_update (ip4_fib_8_t *fib,
+                                   const ip4_address_t *addr,
+                                   u32 len,
+                                   const dpo_id_t *dpo)
+{
+    ip4_mtrie_8_route_add(&fib->mtrie, addr, len, dpo->dpoi_index);
+}
+
+void
+ip4_fib_8_table_fwding_dpo_remove (ip4_fib_8_t *fib,
+                                    const ip4_address_t *addr,
+                                    u32 len,
+                                    const dpo_id_t *dpo,
+                                    u32 cover_index)
+{
+    const fib_prefix_t *cover_prefix;
+    const dpo_id_t *cover_dpo;
+
+    /*
+     * We need to pass the MTRIE the LB index and address length of the
+     * covering prefix, so it can fill the plys with the correct replacement
+     * for the entry being removed
+     */
+    cover_prefix = fib_entry_get_prefix(cover_index);
+    cover_dpo = fib_entry_contribute_ip_forwarding(cover_index);
+
+    ip4_mtrie_8_route_del(&fib->mtrie,
+                            addr, len, dpo->dpoi_index,
+                            cover_prefix->fp_len,
+                            cover_dpo->dpoi_index);
+}
+
+void
+ip4_fib_8_table_walk (ip4_fib_8_t *fib,
+                       fib_table_walk_fn_t fn,
+                       void *ctx)
+{
+    ip4_fib_hash_table_walk(&fib->hash, fn, ctx);
+}
+
+void
+ip4_fib_8_table_sub_tree_walk (ip4_fib_8_t *fib,
+                               const fib_prefix_t *root,
+                               fib_table_walk_fn_t fn,
+                               void *ctx)
+{
+    ip4_fib_hash_table_sub_tree_walk(&fib->hash, root, fn, ctx);
+}
diff --git a/src/vnet/fib/ip4_fib_8.h b/src/vnet/fib/ip4_fib_8.h
new file mode 100644
index 00000000000..0964f3ab133
--- /dev/null
+++ b/src/vnet/fib/ip4_fib_8.h
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/**
+ * @brief The IPv4 FIB
+ *
+ * FIBs are composed of two prefix data-bases (akak tables). The non-forwarding
+ * table contains all the routes that the control plane has programmed, the
+ * forwarding table contains the sub-set of those routes that can be used to
+ * forward packets.
+ * In the IPv4 FIB the non-forwarding table is an array of hash tables indexed
+ * by mask length, the forwarding table is an mtrie
+ *
+ * This IPv4 FIB is used by the protocol independent FIB. So directly using
+ * this APIs in client code is not encouraged. However, this IPv4 FIB can be
+ * used if all the client wants is an IPv4 prefix data-base
+ */
+
+#ifndef __IP4_FIB_8_H__
+#define __IP4_FIB_8_H__
+
+#include <vnet/fib/ip4_fib_hash.h>
+#include <vnet/ip/ip4_mtrie.h>
+
+typedef struct ip4_fib_8_t_
+{
+  /** Required for pool_get_aligned */
+  CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
+
+  /**
+   * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes.
+   * First member so it's in the first cacheline.
+   */
+  ip4_mtrie_8_t mtrie;
+
+  /**
+   * The hash table DB
+   */
+  ip4_fib_hash_t hash;
+} ip4_fib_8_t;
+
+extern ip4_fib_8_t *ip4_fib_8s;
+
+extern fib_node_index_t ip4_fib_8_table_lookup(const ip4_fib_8_t *fib,
+                                               const ip4_address_t *addr,
+                                               u32 len);
+extern fib_node_index_t ip4_fib_8_table_lookup_exact_match(const ip4_fib_8_t *fib,
+                                                           const ip4_address_t *addr,
+                                                           u32 len);
+
+extern void ip4_fib_8_table_entry_remove(ip4_fib_8_t *fib,
+                                         const ip4_address_t *addr,
+                                         u32 len);
+
+extern void ip4_fib_8_table_entry_insert(ip4_fib_8_t *fib,
+                                         const ip4_address_t *addr,
+                                         u32 len,
+                                         fib_node_index_t fib_entry_index);
+extern void ip4_fib_8_table_free(ip4_fib_8_t *fib);
+extern void ip4_fib_8_table_init(ip4_fib_8_t *fib);
+
+extern void ip4_fib_8_table_fwding_dpo_update(ip4_fib_8_t *fib,
+                                              const ip4_address_t *addr,
+                                              u32 len,
+                                              const dpo_id_t *dpo);
+
+extern void ip4_fib_8_table_fwding_dpo_remove(ip4_fib_8_t *fib,
+                                              const ip4_address_t *addr,
+                                              u32 len,
+                                              const dpo_id_t *dpo,
+                                              fib_node_index_t cover_index);
+extern u32 ip4_fib_8_table_lookup_lb (ip4_fib_8_t *fib,
+                                      const ip4_address_t * dst);
+
+/**
+ * @brief Walk all entries in a FIB table
+ * N.B: This is NOT safe to deletes. If you need to delete walk the whole
+ * table and store elements in a vector, then delete the elements
+ */
+extern void ip4_fib_8_table_walk(ip4_fib_8_t *fib,
+                               fib_table_walk_fn_t fn,
+                               void *ctx);
+
+/**
+ * @brief Walk all entries in a sub-tree of the FIB table
+ * N.B: This is NOT safe to deletes. If you need to delete walk the whole
+ * table and store elements in a vector, then delete the elements
+ */
+extern void ip4_fib_8_table_sub_tree_walk(ip4_fib_8_t *fib,
+                                        const fib_prefix_t *root,
+                                        fib_table_walk_fn_t fn,
+                                        void *ctx);
+
+#endif
+
diff --git a/src/vnet/fib/ip4_fib_hash.c b/src/vnet/fib/ip4_fib_hash.c
new file mode 100644
index 00000000000..f42cf28f53e
--- /dev/null
+++ b/src/vnet/fib/ip4_fib_hash.c
@@ -0,0 +1,249 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry.h>
+#include <vnet/fib/ip4_fib.h>
+
+/*
+ * ip4_fib_hash_table_lookup_exact_match
+ *
+ * Exact match prefix lookup
+ */
+fib_node_index_t
+ip4_fib_hash_table_lookup_exact_match (const ip4_fib_hash_t *fib,
+                                       const ip4_address_t *addr,
+                                       u32 len)
+{
+    uword * hash, * result;
+    u32 key;
+
+    hash = fib->fib_entry_by_dst_address[len];
+    key  = (addr->data_u32 & ip4_main.fib_masks[len]);
+
+    result = hash_get(hash, key);
+
+    if (NULL != result) {
+	return (result[0]);
+    }
+    return (FIB_NODE_INDEX_INVALID);
+}
+
+/*
+ * ip4_fib_hash_table_lookup_adj
+ *
+ * Longest prefix match
+ */
+index_t
+ip4_fib_hash_table_lookup_lb (const ip4_fib_hash_t *fib,
+                              const ip4_address_t *addr)
+{
+    fib_node_index_t fei;
+
+    fei = ip4_fib_hash_table_lookup(fib, addr, 32);
+
+    if (FIB_NODE_INDEX_INVALID != fei)
+    {
+	const dpo_id_t *dpo;
+
+	dpo = fib_entry_contribute_ip_forwarding(fei);
+
+	return (dpo->dpoi_index);
+    }
+    return (INDEX_INVALID);
+}
+
+/*
+ * ip4_fib_hash_table_lookup
+ *
+ * Longest prefix match
+ */
+fib_node_index_t
+ip4_fib_hash_table_lookup (const ip4_fib_hash_t *fib,
+                           const ip4_address_t *addr,
+                           u32 len)
+{
+    uword * hash, * result;
+    i32 mask_len;
+    u32 key;
+
+    for (mask_len = len; mask_len >= 0; mask_len--)
+    {
+	hash = fib->fib_entry_by_dst_address[mask_len];
+	key = (addr->data_u32 & ip4_main.fib_masks[mask_len]);
+
+	result = hash_get (hash, key);
+
+	if (NULL != result) {
+	    return (result[0]);
+	}
+    }
+    return (FIB_NODE_INDEX_INVALID);
+}
+
+void
+ip4_fib_hash_table_entry_insert (ip4_fib_hash_t *fib,
+                                 const ip4_address_t *addr,
+                                 u32 len,
+                                 fib_node_index_t fib_entry_index)
+{
+    uword * hash, * result;
+    u32 key;
+
+    key = (addr->data_u32 & ip4_main.fib_masks[len]);
+    hash = fib->fib_entry_by_dst_address[len];
+    result = hash_get (hash, key);
+
+    if (NULL == result) {
+	/*
+	 * adding a new entry
+	 */
+
+	if (NULL == hash) {
+	    hash = hash_create (32 /* elts */, sizeof (uword));
+	    hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);
+
+	}
+	hash = hash_set(hash, key, fib_entry_index);
+	fib->fib_entry_by_dst_address[len] = hash;
+    }
+    else
+    {
+	ASSERT(0);
+    }
+}
+
+void
+ip4_fib_hash_table_entry_remove (ip4_fib_hash_t *fib,
+                                 const ip4_address_t *addr,
+                                 u32 len)
+{
+    uword * hash, * result;
+    u32 key;
+
+    key = (addr->data_u32 & ip4_main.fib_masks[len]);
+    hash = fib->fib_entry_by_dst_address[len];
+    result = hash_get (hash, key);
+
+    if (NULL == result)
+    {
+	/*
+	 * removing a non-existent entry. i'll allow it.
+	 */
+    }
+    else
+    {
+	hash_unset(hash, key);
+    }
+
+    fib->fib_entry_by_dst_address[len] = hash;
+}
+
+void
+ip4_fib_hash_table_walk (ip4_fib_hash_t *fib,
+                         fib_table_walk_fn_t fn,
+                         void *ctx)
+{
+    fib_prefix_t root = {
+        .fp_proto = FIB_PROTOCOL_IP4,
+        // address and length default to all 0
+    };
+
+    /*
+     * A full tree walk is the dengenerate case of a sub-tree from
+     * the very root
+     */
+    return (ip4_fib_hash_table_sub_tree_walk(fib, &root, fn, ctx));
+}
+
+void
+ip4_fib_hash_table_sub_tree_walk (ip4_fib_hash_t *fib,
+                                  const fib_prefix_t *root,
+                                  fib_table_walk_fn_t fn,
+                                  void *ctx)
+{
+    fib_prefix_t *sub_trees = NULL;
+    int i;
+
+    /*
+     * There is no efficient way to walk this array of hash tables.
+     * so we walk each table with a mask length greater than and equal to
+     * the required root and check it is covered by the root.
+     */
+    for (i = root->fp_len;
+         i < ARRAY_LEN (fib->fib_entry_by_dst_address);
+         i++)
+    {
+	uword * hash = fib->fib_entry_by_dst_address[i];
+
+	if (NULL != hash)
+	{
+            ip4_address_t key;
+	    hash_pair_t * p;
+
+	    hash_foreach_pair (p, hash,
+	    ({
+                key.as_u32 = p->key;
+                if (ip4_destination_matches_route(&ip4_main,
+                                                  &key,
+                                                  &root->fp_addr.ip4,
+                                                  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, sub_trees)
+                    {
+                        if (ip4_destination_matches_route(&ip4_main,
+                                                          &key,
+                                                          &sub_tree->fp_addr.ip4,
+                                                          sub_tree->fp_len))
+                        {
+                            skip = 1;
+                            break;
+                        }
+                    }
+
+                    if (!skip)
+                    {
+                        switch (fn(p->value[0], ctx))
+                        {
+                        case FIB_TABLE_WALK_CONTINUE:
+                            break;
+                        case FIB_TABLE_WALK_SUB_TREE_STOP: {
+                            fib_prefix_t pfx = {
+                                .fp_proto = FIB_PROTOCOL_IP4,
+                                .fp_len = i,
+                                .fp_addr.ip4 = key,
+                            };
+                            vec_add1(sub_trees, pfx);
+                            break;
+                        }
+                        case FIB_TABLE_WALK_STOP:
+                            goto done;
+                        }
+                    }
+                }
+	    }));
+	}
+    }
+done:
+    vec_free(sub_trees);
+    return;
+}
+
diff --git a/src/vnet/fib/ip4_fib_hash.h b/src/vnet/fib/ip4_fib_hash.h
new file mode 100644
index 00000000000..84b3b9ae834
--- /dev/null
+++ b/src/vnet/fib/ip4_fib_hash.h
@@ -0,0 +1,74 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/**
+ * @brief The IPv4 FIB Hash table
+ */
+
+#ifndef __IP4_FIB_HASH_H__
+#define __IP4_FIB_HASH_H__
+
+#include <vlib/vlib.h>
+#include <vnet/ip/ip.h>
+
+typedef struct ip4_fib_hash_t_
+{
+  /* Hash table for each prefix length mapping. */
+  uword *fib_entry_by_dst_address[33];
+
+  /* Table ID (hash key) for this FIB. */
+  u32 table_id;
+} ip4_fib_hash_t;
+
+extern fib_node_index_t ip4_fib_hash_table_lookup(const ip4_fib_hash_t *fib,
+                                                  const ip4_address_t *addr,
+                                                  u32 len);
+extern index_t ip4_fib_hash_table_lookup_lb(const ip4_fib_hash_t *fib,
+                                            const ip4_address_t *addr);
+extern fib_node_index_t ip4_fib_hash_table_lookup_exact_match(const ip4_fib_hash_t *fib,
+                                                              const ip4_address_t *addr,
+                                                              u32 len);
+
+extern void ip4_fib_hash_table_entry_remove(ip4_fib_hash_t *fib,
+                                            const ip4_address_t *addr,
+                                            u32 len);
+
+extern void ip4_fib_hash_table_entry_insert(ip4_fib_hash_t *fib,
+                                            const ip4_address_t *addr,
+                                            u32 len,
+                                            fib_node_index_t fib_entry_index);
+extern void ip4_fib_hash_table_init(ip4_fib_hash_t *fib);
+extern void ip4_fib_hash_table_destroy(ip4_fib_hash_t *fib);
+
+/**
+ * @brief Walk all entries in a FIB table
+ * N.B: This is NOT safe to deletes. If you need to delete walk the whole
+ * table and store elements in a vector, then delete the elements
+ */
+extern void ip4_fib_hash_table_walk(ip4_fib_hash_t *fib,
+                                    fib_table_walk_fn_t fn,
+                                    void *ctx);
+
+/**
+ * @brief Walk all entries in a sub-tree of the FIB table
+ * N.B: This is NOT safe to deletes. If you need to delete walk the whole
+ * table and store elements in a vector, then delete the elements
+ */
+extern void ip4_fib_hash_table_sub_tree_walk(ip4_fib_hash_t *fib,
+                                             const fib_prefix_t *root,
+                                             fib_table_walk_fn_t fn,
+                                             void *ctx);
+
+#endif
+
diff --git a/src/vnet/interface_cli.c b/src/vnet/interface_cli.c
index 68431860183..2bddf29b70f 100644
--- a/src/vnet/interface_cli.c
+++ b/src/vnet/interface_cli.c
@@ -448,11 +448,11 @@ show_sw_interfaces (vlib_main_t * vm,
 				      1 /* honor unnumbered */,
 	({
 	  ip4_address_t *r4 = ip_interface_address_get_address (lm4, ia);
-	  if (fib4->table_id)
-	    vlib_cli_output (vm, "  L3 %U/%d ip4 table-id %d fib-idx %d",
-			     format_ip4_address, r4, ia->address_length,
-			     fib4->table_id,
-			     ip4_fib_index_from_table_id (fib4->table_id));
+	  if (fib4->hash.table_id)
+	    vlib_cli_output (
+	      vm, "  L3 %U/%d ip4 table-id %d fib-idx %d", format_ip4_address,
+	      r4, ia->address_length, fib4->hash.table_id,
+	      ip4_fib_index_from_table_id (fib4->hash.table_id));
 	  else
 	    vlib_cli_output (vm, "  L3 %U/%d",
 			     format_ip4_address, r4, ia->address_length);
diff --git a/src/vnet/ip/ip4.h b/src/vnet/ip/ip4.h
index bc971a2b7ca..dba27851c8f 100644
--- a/src/vnet/ip/ip4.h
+++ b/src/vnet/ip/ip4.h
@@ -111,9 +111,6 @@ typedef struct ip4_main_t
   /** Vector of FIBs. */
   struct fib_table_t_ *fibs;
 
-  /** Vector of MTries. */
-  struct ip4_fib_t_ *v4_fibs;
-
   /** Vector of MFIBs. */
   struct mfib_table_t_ *mfibs;
 
diff --git a/src/vnet/ip/ip_container_proxy.c b/src/vnet/ip/ip_container_proxy.c
index 2c94b70ec85..18d07ba6082 100644
--- a/src/vnet/ip/ip_container_proxy.c
+++ b/src/vnet/ip/ip_container_proxy.c
@@ -132,27 +132,23 @@ ip_container_proxy_fib_table_walk (fib_node_index_t fei, void *arg)
 void
 ip_container_proxy_walk (ip_container_proxy_cb_t cb, void *ctx)
 {
-  fib_table_t *fib_table;
   ip_container_proxy_walk_ctx_t wctx = {
     .cb = cb,
     .ctx = ctx,
   };
+  u32 fib_index;
 
   /* *INDENT-OFF* */
-  pool_foreach (fib_table, ip4_main.fibs)
-   {
-    fib_table_walk(fib_table->ft_index,
-                   FIB_PROTOCOL_IP4,
-                   ip_container_proxy_fib_table_walk,
-                   &wctx);
-  }
-  pool_foreach (fib_table, ip6_main.fibs)
-   {
-    fib_table_walk(fib_table->ft_index,
-                   FIB_PROTOCOL_IP6,
-                   ip_container_proxy_fib_table_walk,
-                   &wctx);
-  }
+  pool_foreach_index (fib_index, ip4_main.fibs)
+    {
+      fib_table_walk (fib_index, FIB_PROTOCOL_IP4,
+		      ip_container_proxy_fib_table_walk, &wctx);
+    }
+  pool_foreach_index (fib_index, ip6_main.fibs)
+    {
+      fib_table_walk (fib_index, FIB_PROTOCOL_IP6,
+		      ip_container_proxy_fib_table_walk, &wctx);
+    }
   /* *INDENT-ON* */
 }
 
diff --git a/src/vnet/ip6-nd/ip6_nd_api.c b/src/vnet/ip6-nd/ip6_nd_api.c
index 9e4024670e6..b949e218cfd 100644
--- a/src/vnet/ip6-nd/ip6_nd_api.c
+++ b/src/vnet/ip6-nd/ip6_nd_api.c
@@ -83,7 +83,7 @@ static void
 vl_api_ip6nd_proxy_dump_t_handler (vl_api_ip6nd_proxy_dump_t * mp)
 {
   ip6_main_t *im6 = &ip6_main;
-  fib_table_t *fib_table;
+  u32 fib_index;
   api_ip6nd_proxy_fib_table_walk_ctx_t ctx = {
     .indices = NULL,
   };
@@ -96,13 +96,11 @@ vl_api_ip6nd_proxy_dump_t_handler (vl_api_ip6nd_proxy_dump_t * mp)
     return;
 
   /* *INDENT-OFF* */
-  pool_foreach (fib_table, im6->fibs)
-   {
-    fib_table_walk(fib_table->ft_index,
-                   FIB_PROTOCOL_IP6,
-                   api_ip6nd_proxy_fib_table_walk,
-                   &ctx);
-  }
+  pool_foreach_index (fib_index, im6->fibs)
+    {
+      fib_table_walk (fib_index, FIB_PROTOCOL_IP6,
+		      api_ip6nd_proxy_fib_table_walk, &ctx);
+    }
   /* *INDENT-ON* */
 
   vec_sort_with_function (ctx.indices, fib_entry_cmp_for_sort);