IP6-MFIB: replace the radix tree with bihash (VPP-1526)

Change-Id: I7a48890c075826fbd8c75436dfdc5ffff230a693
Signed-off-by: Neale Ranns <nranns@cisco.com>

15 files changed, 266 insertions, 194 deletions

diff --git a/src/plugins/unittest/mfib_test.c b/src/plugins/unittest/mfib_test.c
index fda02580bee..bbe6709f4d7 100644
--- a/src/plugins/unittest/mfib_test.c
+++ b/src/plugins/unittest/mfib_test.c
@@ -543,7 +543,8 @@ mfib_test_i (fib_protocol_t PROTO,
     mfei = mfib_table_lookup(fib_index,
                              pfx_star_g_1);
     MFIB_TEST(mfei == mfei_g_1,
-              "%U found via LP match",
+              "[e:%d a:%d] %U found via LP match",
+              mfei, mfei_g_1,
               format_mfib_prefix, pfx_star_g_1);
 
     MFIB_TEST(!mfib_test_entry(mfei,
@@ -929,7 +930,7 @@ mfib_test_i (fib_protocol_t PROTO,
         /*
          * Find the (*,G/m)
          */
-        MFIB_TEST((mfei_g_m == ip6_mfib_table_lookup2(
+        MFIB_TEST((mfei_g_m == ip6_mfib_table_fwd_lookup(
                        ip6_mfib_get(fib_index),
                        &src,
                        &pfx_star_g_slash_m->fp_grp_addr.ip6)),
@@ -940,7 +941,7 @@ mfib_test_i (fib_protocol_t PROTO,
         ip6_address_t tmp = pfx_star_g_slash_m->fp_grp_addr.ip6;
         tmp.as_u8[15] = 0xff;
 
-        MFIB_TEST((mfei_g_m == ip6_mfib_table_lookup2(
+        MFIB_TEST((mfei_g_m == ip6_mfib_table_fwd_lookup(
                        ip6_mfib_get(fib_index),
                        &pfx_s_g->fp_src_addr.ip6,
                        &tmp)),
@@ -951,9 +952,9 @@ mfib_test_i (fib_protocol_t PROTO,
         /*
          * Find the (S,G).
          */
-        mfei = ip6_mfib_table_lookup2(ip6_mfib_get(fib_index),
-                                      &pfx_s_g->fp_src_addr.ip6,
-                                      &pfx_s_g->fp_grp_addr.ip6);
+        mfei = ip6_mfib_table_fwd_lookup(ip6_mfib_get(fib_index),
+                                         &pfx_s_g->fp_src_addr.ip6,
+                                         &pfx_s_g->fp_grp_addr.ip6);
         MFIB_TEST((mfei_s_g == mfei),
                   "%U found via DP LPM: %d",
                   format_mfib_prefix, pfx_s_g, mfei);
@@ -961,21 +962,21 @@ mfib_test_i (fib_protocol_t PROTO,
         /*
          * Find the 3 (*,G) s
          */
-        mfei = ip6_mfib_table_lookup2(ip6_mfib_get(fib_index),
-                                      &src,
-                                      &pfx_star_g_1->fp_grp_addr.ip6);
+        mfei = ip6_mfib_table_fwd_lookup(ip6_mfib_get(fib_index),
+                                         &src,
+                                         &pfx_star_g_1->fp_grp_addr.ip6);
         MFIB_TEST((mfei_g_1 == mfei),
                   "%U found via DP LPM: %d",
                   format_mfib_prefix, pfx_star_g_1, mfei);
-        mfei = ip6_mfib_table_lookup2(ip6_mfib_get(fib_index),
-                                      &src,
-                                      &pfx_star_g_2->fp_grp_addr.ip6);
+        mfei = ip6_mfib_table_fwd_lookup(ip6_mfib_get(fib_index),
+                                         &src,
+                                         &pfx_star_g_2->fp_grp_addr.ip6);
         MFIB_TEST((mfei_g_2 == mfei),
                   "%U found via DP LPM: %d",
                   format_mfib_prefix, pfx_star_g_2, mfei);
-        mfei = ip6_mfib_table_lookup2(ip6_mfib_get(fib_index),
-                                      &src,
-                                      &pfx_star_g_3->fp_grp_addr.ip6);
+        mfei = ip6_mfib_table_fwd_lookup(ip6_mfib_get(fib_index),
+                                         &src,
+                                         &pfx_star_g_3->fp_grp_addr.ip6);
         MFIB_TEST((mfei_g_3 == mfei),
                   "%U found via DP LPM: %d",
                   format_mfib_prefix, pfx_star_g_3, mfei);
diff --git a/src/vnet/adj/adj_nbr.c b/src/vnet/adj/adj_nbr.c
index 38885095a4f..3f73ff9f1d2 100644
--- a/src/vnet/adj/adj_nbr.c
+++ b/src/vnet/adj/adj_nbr.c
@@ -18,6 +18,8 @@
 #include <vnet/ethernet/arp_packet.h>
 #include <vnet/fib/fib_walk.h>
 
+#include <vppinfra/bihash_24_8.h>
+
 /*
  * Vector Hash tables of neighbour (traditional) adjacencies
  *  Key: interface(for the vector index), address (and its proto),
diff --git a/src/vnet/dpo/lookup_dpo.c b/src/vnet/dpo/lookup_dpo.c
index 1ac917cb0de..3bda3b81186 100644
--- a/src/vnet/dpo/lookup_dpo.c
+++ b/src/vnet/dpo/lookup_dpo.c
@@ -1305,9 +1305,9 @@ lookup_dpo_ip_dst_mcast_inline (vlib_main_t * vm,
                 ip6_header_t * ip0;
 
                 ip0 = vlib_buffer_get_current (b0);
-                mfei0 = ip6_mfib_table_lookup2(ip6_mfib_get(fib_index0),
-                                               &ip0->src_address,
-                                               &ip0->dst_address);
+                mfei0 = ip6_mfib_table_fwd_lookup(ip6_mfib_get(fib_index0),
+                                                  &ip0->src_address,
+                                                  &ip0->dst_address);
                 if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
                 {
                     lookup_trace_t *tr = vlib_add_trace (vm, node,
diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c
index 7375b56ee51..60d13659925 100644
--- a/src/vnet/fib/ip6_fib.c
+++ b/src/vnet/fib/ip6_fib.c
@@ -17,6 +17,9 @@
 #include <vnet/fib/fib_table.h>
 #include <vnet/dpo/ip6_ll_dpo.h>
 
+#include <vppinfra/bihash_24_8.h>
+#include <vppinfra/bihash_template.c>
+
 static void
 vnet_ip6_fib_init (u32 fib_index)
 {
@@ -171,7 +174,7 @@ ip6_fib_table_lookup (u32 fib_index,
 		      u32 len)
 {
     ip6_fib_table_instance_t *table;
-    BVT(clib_bihash_kv) kv, value;
+    clib_bihash_kv_24_8_t kv, value;
     int i, n_p, rv;
     u64 fib;
 
@@ -203,7 +206,7 @@ ip6_fib_table_lookup (u32 fib_index,
 	kv.key[1] &= mask->as_u64[1];
 	kv.key[2] = fib | dst_address_length;
       
-	rv = BV(clib_bihash_search_inline_2)(&table->ip6_hash, &kv, &value);
+	rv = clib_bihash_search_inline_2_24_8(&table->ip6_hash, &kv, &value);
 	if (rv == 0)
 	    return value.value;
     }
@@ -217,7 +220,7 @@ ip6_fib_table_lookup_exact_match (u32 fib_index,
 				  u32 len)
 {
     ip6_fib_table_instance_t *table;
-    BVT(clib_bihash_kv) kv, value;
+    clib_bihash_kv_24_8_t kv, value;
     ip6_address_t *mask;
     u64 fib;
     int rv;
@@ -230,7 +233,7 @@ ip6_fib_table_lookup_exact_match (u32 fib_index,
     kv.key[1] = addr->as_u64[1] & mask->as_u64[1];
     kv.key[2] = fib | len;
       
-    rv = BV(clib_bihash_search_inline_2)(&table->ip6_hash, &kv, &value);
+    rv = clib_bihash_search_inline_2_24_8(&table->ip6_hash, &kv, &value);
     if (rv == 0)
 	return value.value;
 
@@ -256,7 +259,7 @@ ip6_fib_table_entry_remove (u32 fib_index,
 			    u32 len)
 {
     ip6_fib_table_instance_t *table;
-    BVT(clib_bihash_kv) kv;
+    clib_bihash_kv_24_8_t kv;
     ip6_address_t *mask;
     u64 fib;
 
@@ -268,7 +271,7 @@ ip6_fib_table_entry_remove (u32 fib_index,
     kv.key[1] = addr->as_u64[1] & mask->as_u64[1];
     kv.key[2] = fib | len;
 
-    BV(clib_bihash_add_del)(&table->ip6_hash, &kv, 0);
+    clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 0);
 
     /* refcount accounting */
     ASSERT (table->dst_address_length_refcounts[len] > 0);
@@ -288,7 +291,7 @@ ip6_fib_table_entry_insert (u32 fib_index,
 			    fib_node_index_t fib_entry_index)
 {
     ip6_fib_table_instance_t *table;
-    BVT(clib_bihash_kv) kv;
+    clib_bihash_kv_24_8_t kv;
     ip6_address_t *mask;
     u64 fib;
 
@@ -301,7 +304,7 @@ ip6_fib_table_entry_insert (u32 fib_index,
     kv.key[2] = fib | len;
     kv.value = fib_entry_index;
 
-    BV(clib_bihash_add_del)(&table->ip6_hash, &kv, 1);
+    clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 1);
 
     table->dst_address_length_refcounts[len]++;
 
@@ -340,7 +343,7 @@ ip6_fib_table_fwding_dpo_update (u32 fib_index,
 				 const dpo_id_t *dpo)
 {
     ip6_fib_table_instance_t *table;
-    BVT(clib_bihash_kv) kv;
+    clib_bihash_kv_24_8_t kv;
     ip6_address_t *mask;
     u64 fib;
 
@@ -353,7 +356,7 @@ ip6_fib_table_fwding_dpo_update (u32 fib_index,
     kv.key[2] = fib | len;
     kv.value = dpo->dpoi_index;
 
-    BV(clib_bihash_add_del)(&table->ip6_hash, &kv, 1);
+    clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 1);
 
     table->dst_address_length_refcounts[len]++;
 
@@ -370,7 +373,7 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index,
 				 const dpo_id_t *dpo)
 {
     ip6_fib_table_instance_t *table;
-    BVT(clib_bihash_kv) kv;
+    clib_bihash_kv_24_8_t kv;
     ip6_address_t *mask;
     u64 fib;
 
@@ -383,7 +386,7 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index,
     kv.key[2] = fib | len;
     kv.value = dpo->dpoi_index;
 
-    BV(clib_bihash_add_del)(&table->ip6_hash, &kv, 0);
+    clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 0);
 
     /* refcount accounting */
     ASSERT (table->dst_address_length_refcounts[len] > 0);
@@ -485,7 +488,7 @@ ip6_fib_table_walk (u32 fib_index,
         .i6w_sub_trees = NULL,
     };
 
-    BV(clib_bihash_foreach_key_value_pair)(
+    clib_bihash_foreach_key_value_pair_24_8(
         &ip6_main.ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
         ip6_fib_walk_cb,
         &ctx);
@@ -506,7 +509,7 @@ ip6_fib_table_sub_tree_walk (u32 fib_index,
         .i6w_root = *root,
     };
 
-    BV(clib_bihash_foreach_key_value_pair)(
+    clib_bihash_foreach_key_value_pair_24_8(
         &ip6_main.ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
         ip6_fib_walk_cb,
         &ctx);
@@ -592,7 +595,7 @@ typedef struct {
 } count_routes_in_fib_at_prefix_length_arg_t;
 
 static void
-count_routes_in_fib_at_prefix_length (BVT(clib_bihash_kv) * kvp,
+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;
@@ -685,7 +688,7 @@ ip6_show_fib (vlib_main_t * vm,
 	/* Show summary? */
 	if (! verbose)
 	{
-	    BVT(clib_bihash) * h = &im6->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash;
+	    clib_bihash_24_8_t * h = &im6->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash;
 	    int len;
 
 	    vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
@@ -693,7 +696,7 @@ ip6_show_fib (vlib_main_t * vm,
 	    clib_memset (ca, 0, sizeof(*ca));
 	    ca->fib_index = fib->index;
 
-	    BV(clib_bihash_foreach_key_value_pair)
+	    clib_bihash_foreach_key_value_pair_24_8
 		(h, count_routes_in_fib_at_prefix_length, ca);
 
 	    for (len = 128; len >= 0; len--)
diff --git a/src/vnet/fib/ip6_fib.h b/src/vnet/fib/ip6_fib.h
index 10ae75ce6f9..583a17f01b8 100644
--- a/src/vnet/fib/ip6_fib.h
+++ b/src/vnet/fib/ip6_fib.h
@@ -69,9 +69,9 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im,
                              const ip6_address_t * dst)
 {
     ip6_fib_table_instance_t *table;
+    clib_bihash_kv_24_8_t kv, value;
     int i, len;
     int rv;
-    BVT(clib_bihash_kv) kv, value;
     u64 fib;
 
     table = &ip6_main.ip6_table[IP6_FIB_TABLE_FWDING];
@@ -92,7 +92,7 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im,
 	kv.key[1] &= mask->as_u64[1];
 	kv.key[2] = fib | dst_address_length;
 
-	rv = BV(clib_bihash_search_inline_2)(&table->ip6_hash, &kv, &value);
+	rv = clib_bihash_search_inline_2_24_8(&table->ip6_hash, &kv, &value);
 	if (rv == 0)
 	    return value.value;
     }
diff --git a/src/vnet/ip/ip6.h b/src/vnet/ip/ip6.h
index 6e0cfff5164..ab17f662198 100644
--- a/src/vnet/ip/ip6.h
+++ b/src/vnet/ip/ip6.h
@@ -47,6 +47,7 @@
 #include <vnet/ip/lookup.h>
 #include <stdbool.h>
 #include <vppinfra/bihash_24_8.h>
+#include <vppinfra/bihash_40_8.h>
 #include <vppinfra/bihash_template.h>
 #include <vnet/util/radix.h>
 #include <vnet/util/throttle.h>
@@ -78,17 +79,14 @@ typedef struct
 
 typedef struct ip6_mfib_t
 {
+  /* required for pool_get_aligned. */
+  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
+
   /* Table ID (hash key) for this FIB. */
   u32 table_id;
 
   /* Index into FIB vector. */
   u32 index;
-
-  /*
-   *  Pointer to the top of a radix tree.
-   * This cannot be realloc'd, hence it cannot be inlined with this table
-   */
-  struct radix_node_head *rhead;
 } ip6_mfib_t;
 
 struct ip6_main_t;
@@ -143,7 +141,7 @@ typedef enum ip6_fib_table_instance_type_t_
 typedef struct ip6_fib_table_instance_t_
 {
   /* The hash table */
-  BVT (clib_bihash) ip6_hash;
+  clib_bihash_24_8_t ip6_hash;
 
   /* bitmap / refcounts / vector of mask widths to search */
   uword *non_empty_dst_address_length_bitmap;
@@ -151,6 +149,20 @@ typedef struct ip6_fib_table_instance_t_
   i32 dst_address_length_refcounts[129];
 } ip6_fib_table_instance_t;
 
+/**
+ * A represenation of a single IP6 mfib table
+ */
+typedef struct ip6_mfib_table_instance_t_
+{
+  /* The hash table */
+  clib_bihash_40_8_t ip6_mhash;
+
+  /* bitmap / refcounts / vector of mask widths to search */
+  uword *non_empty_dst_address_length_bitmap;
+  u16 *prefix_lengths_in_search_order;
+  i32 dst_address_length_refcounts[257];
+} ip6_mfib_table_instance_t;
+
 typedef struct ip6_main_t
 {
   /**
@@ -158,6 +170,11 @@ typedef struct ip6_main_t
    */
   ip6_fib_table_instance_t ip6_table[IP6_FIB_NUM_TABLES];
 
+  /**
+   * the single MFIB table
+   */
+  ip6_mfib_table_instance_t ip6_mtable;
+
   ip_lookup_main_t lookup_main;
 
   /* Pool of FIBs. */
diff --git a/src/vnet/ip/ip6_forward.c b/src/vnet/ip/ip6_forward.c
index 999be870b53..56cef4aa43e 100644
--- a/src/vnet/ip/ip6_forward.c
+++ b/src/vnet/ip/ip6_forward.c
@@ -2658,12 +2658,15 @@ ip6_lookup_init (vlib_main_t * vm)
   if (im->lookup_table_size == 0)
     im->lookup_table_size = IP6_FIB_DEFAULT_HASH_MEMORY_SIZE;
 
-  BV (clib_bihash_init) (&(im->ip6_table[IP6_FIB_TABLE_FWDING].ip6_hash),
+  clib_bihash_init_24_8 (&(im->ip6_table[IP6_FIB_TABLE_FWDING].ip6_hash),
 			 "ip6 FIB fwding table",
 			 im->lookup_table_nbuckets, im->lookup_table_size);
-  BV (clib_bihash_init) (&im->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
+  clib_bihash_init_24_8 (&im->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash,
 			 "ip6 FIB non-fwding table",
 			 im->lookup_table_nbuckets, im->lookup_table_size);
+  clib_bihash_init_40_8 (&im->ip6_mtable.ip6_mhash,
+			 "ip6 mFIB table",
+			 im->lookup_table_nbuckets, im->lookup_table_size);
 
   /* Create FIB with index 0 and table id of 0. */
   fib_table_find_or_create_and_lock (FIB_PROTOCOL_IP6, 0,
diff --git a/src/vnet/ip/ip6_ll_table.c b/src/vnet/ip/ip6_ll_table.c
index dfcb2708259..a7440ea543c 100644
--- a/src/vnet/ip/ip6_ll_table.c
+++ b/src/vnet/ip/ip6_ll_table.c
@@ -298,7 +298,7 @@ ip6_ll_show_fib (vlib_main_t * vm,
     /* Show summary? */
     if (!verbose)
       {
-	BVT (clib_bihash) * h =
+	clib_bihash_24_8_t *h =
 	  &im6->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash;
 	int len;
 
@@ -307,7 +307,7 @@ ip6_ll_show_fib (vlib_main_t * vm,
 	clib_memset (ca, 0, sizeof (*ca));
 	ca->fib_index = fib_index;
 
-	BV (clib_bihash_foreach_key_value_pair)
+	clib_bihash_foreach_key_value_pair_24_8
 	  (h, count_routes_in_fib_at_prefix_length, ca);
 
 	for (len = 128; len >= 0; len--)
diff --git a/src/vnet/mfib/ip4_mfib.c b/src/vnet/mfib/ip4_mfib.c
index eaa61c0f86c..9d70f0b664f 100644
--- a/src/vnet/mfib/ip4_mfib.c
+++ b/src/vnet/mfib/ip4_mfib.c
@@ -210,7 +210,7 @@ ip4_mfib_table_lookup (const ip4_mfib_t *mfib,
         }
     }
 
-    for (mask_len = 32; mask_len >= 0; mask_len--)
+    for (mask_len = (len == 64 ? 32 : len); mask_len >= 0; mask_len--)
     {
         hash = mfib->fib_entry_by_dst_address[mask_len];
         IP4_MFIB_MK_GRP_KEY(grp, mask_len, key);
diff --git a/src/vnet/mfib/ip6_mfib.c b/src/vnet/mfib/ip6_mfib.c
index e98ac42374a..554a932844f 100644
--- a/src/vnet/mfib/ip6_mfib.c
+++ b/src/vnet/mfib/ip6_mfib.c
@@ -20,31 +20,9 @@
 #include <vnet/fib/ip6_fib.h>
 
 /**
- * The number of bytes in an address/ask key in the radix tree
- * First byte is the length in bytes.
- */
-#define IP6_MFIB_KEY_LEN 33
-
-/**
  * Key and mask for radix
  */
-typedef struct ip6_mfib_key_t_
-{
-    u8 key[IP6_MFIB_KEY_LEN];
-    u8 mask[IP6_MFIB_KEY_LEN];
-} ip6_mfib_key_t;
-
-/**
- * An object that is inserted into the radix tree.
- * Since it's in the tree and has pointers, it cannot realloc and so cannot
- * come from a vlib pool.
- */
-typedef struct ip6_mfib_node_t_
-{
-    struct radix_node i6mn_nodes[2];
-    ip6_mfib_key_t i6mn_key;
-    index_t i6mn_entry;
-} ip6_mfib_node_t;
+typedef clib_bihash_kv_40_8_t ip6_mfib_key_t;
 
 static const mfib_prefix_t all_zeros = {
     /* (*,*) */
@@ -185,11 +163,6 @@ ip6_create_mfib_with_table_id (u32 table_id,
 
     mfib_table_lock(mfib_table->mft_index, FIB_PROTOCOL_IP6, src);
 
-    mfib_table->v6.rhead =
-        clib_mem_alloc_aligned (sizeof(*mfib_table->v6.rhead),
-                                CLIB_CACHE_LINE_BYTES);
-    rn_inithead0(mfib_table->v6.rhead, 8);
-
     /*
      * add the special entries into the new FIB
      */
@@ -252,7 +225,6 @@ ip6_mfib_table_destroy (ip6_mfib_t *mfib)
     ASSERT(~0 != mfib_table->mft_table_id);
 
     hash_unset (ip6_main.mfib_index_by_table_id, mfib_table->mft_table_id);
-    clib_mem_free(mfib_table->v6.rhead);
     pool_put(ip6_main.mfibs, mfib_table);
 }
 
@@ -325,29 +297,24 @@ ip6_mfib_table_get_index_for_sw_if_index (u32 sw_if_index)
     return (ip6_main.mfib_index_by_sw_if_index[sw_if_index]);
 }
 
-#define IP6_MFIB_MK_KEY(_grp, _src, _key)                           \
-{                                                                   \
-    (_key)->key[0] = 33;                                            \
-    memcpy((_key)->key+1, _grp, 16);                                \
-    memcpy((_key)->key+17, _src, 16);                               \
-}
+#define IPV6_MFIB_GRP_LEN(_len)                 \
+    (_len > 128 ? 128 : _len)
 
-#define IP6_MFIB_MK_KEY_MASK(_grp, _src, _len, _key)                \
-{                                                                   \
-    IP6_MFIB_MK_KEY(_grp, _src, _key);                              \
-                                                                    \
-    (_key)->mask[0] = 33;                                           \
-    if (_len <= 128)                                                \
-    {                                                               \
-        memcpy((_key)->mask+1, &ip6_main.fib_masks[_len], 16);      \
-        clib_memset((_key)->mask+17, 0, 16);                             \
-    }                                                               \
-    else                                                            \
-    {                                                               \
-        ASSERT(_len == 256);                                        \
-        memcpy((_key)->mask+1, &ip6_main.fib_masks[128], 16);       \
-        memcpy((_key)->mask+17, &ip6_main.fib_masks[128], 16);      \
-    }                                                               \
+#define IP6_MFIB_MK_KEY(_mfib, _grp, _src, _len, _key)                  \
+{                                                                       \
+    _key.key[0] = (_grp->as_u64[0] &                                    \
+                   ip6_main.fib_masks[IPV6_MFIB_GRP_LEN(_len)].as_u64[0]); \
+    _key.key[1] = (_grp->as_u64[1] &                                    \
+                   ip6_main.fib_masks[IPV6_MFIB_GRP_LEN(_len)].as_u64[1]); \
+    if (_len == 256) {                                                  \
+        _key.key[2] = _src->as_u64[0];                                  \
+        _key.key[3] = _src->as_u64[1];                                  \
+    } else {                                                            \
+        _key.key[2] = 0;                                                \
+        _key.key[3] = 0;                                                \
+    }                                                                   \
+    _key.key[4] = _mfib->index;                                         \
+    _key.key[4] = (_key.key[4] << 32) | len;                            \
 }
 
 /*
@@ -361,68 +328,105 @@ ip6_mfib_table_lookup_exact_match (const ip6_mfib_t *mfib,
                                    const ip6_address_t *src,
                                    u32 len)
 {
-    ip6_mfib_node_t *i6mn;
-    ip6_mfib_key_t key;
-
-    IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
+    ip6_mfib_key_t key, value;
+    int rv;
 
-    i6mn = (ip6_mfib_node_t*) rn_lookup(key.key, key.mask,
-                                        (struct radix_node_head *)mfib->rhead);
+    IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
 
-    if (NULL == i6mn)
-    {
-        return (INDEX_INVALID);
-    }
+    rv = clib_bihash_search_inline_2_40_8(&ip6_main.ip6_mtable.ip6_mhash,
+                                          &key, &value);
+    if (rv == 0)
+	return value.value;
 
-    return (i6mn->i6mn_entry);
+    return (FIB_NODE_INDEX_INVALID);
 }
 
 /*
  * ip6_fib_table_lookup
  *
- * Longest prefix match
+ * Longest prefix match for the forwarding plane (no mask given)
  */
 fib_node_index_t
-ip6_mfib_table_lookup (const ip6_mfib_t *mfib,
-                       const ip6_address_t *src,
-                       const ip6_address_t *grp,
-                       u32 len)
+ip6_mfib_table_fwd_lookup (const ip6_mfib_t *mfib,
+                           const ip6_address_t *src,
+                           const ip6_address_t *grp)
 {
-    ip6_mfib_node_t *i6mn;
-    ip6_mfib_key_t key;
+    ip6_mfib_table_instance_t *table;
+    ip6_mfib_key_t key, value;
+    int i, n, len;
+    int rv;
+
+    table = &ip6_main.ip6_mtable;
+    n = vec_len (table->prefix_lengths_in_search_order);
 
-    IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
+    for (i = 0; i < n; i++)
+    {
+	len = table->prefix_lengths_in_search_order[i];
 
-    i6mn = (ip6_mfib_node_t*) rn_search_m(key.key,
-                                          mfib->rhead->rnh_treetop,
-                                          key.mask);
+	ASSERT(len >= 0 && len <= 256);
+        IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
 
-    ASSERT(NULL != i6mn);
+	rv = clib_bihash_search_inline_2_40_8(&table->ip6_mhash, &key, &value);
+	if (rv == 0)
+	    return value.value;
+    }
 
-    return (i6mn->i6mn_entry);
+    return (FIB_NODE_INDEX_INVALID);
 }
 
 /*
  * ip6_fib_table_lookup
  *
- * Longest prefix match no mask
+ * Longest prefix match
  */
 fib_node_index_t
-ip6_mfib_table_lookup2 (const ip6_mfib_t *mfib,
-                        const ip6_address_t *src,
-                        const ip6_address_t *grp)
+ip6_mfib_table_lookup (const ip6_mfib_t *mfib,
+                       const ip6_address_t *src,
+                       const ip6_address_t *grp,
+                       u32 len)
 {
-    ip6_mfib_node_t *i6mn;
-    ip6_mfib_key_t key;
+    ip6_mfib_table_instance_t *table;
+    ip6_mfib_key_t key, value;
+    int i, n, rv;
+
+    table = &ip6_main.ip6_mtable;
+    n = vec_len (table->prefix_lengths_in_search_order);
+
+    /*
+     * 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 && table->prefix_lengths_in_search_order[i] > len)
+    {
+        i++;
+    }
 
-    IP6_MFIB_MK_KEY(grp, src, &key);
+    for (; i < n; i++)
+    {
+	len = table->prefix_lengths_in_search_order[i];
 
-    i6mn = (ip6_mfib_node_t*) rn_match(key.key,
-                                       (struct radix_node_head *)mfib->rhead); // const cast
+	ASSERT(len >= 0 && len <= 256);
+        IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
 
-    ASSERT(NULL != i6mn);
+	rv = clib_bihash_search_inline_2_40_8(&table->ip6_mhash, &key, &value);
+	if (rv == 0)
+	    return value.value;
+    }
 
-    return (i6mn->i6mn_entry);
+    return (FIB_NODE_INDEX_INVALID);
+}
+
+static void
+compute_prefix_lengths_in_search_order (ip6_mfib_table_instance_t *table)
+{
+    int i;
+    vec_reset_length (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,
+    ({
+	vec_add1(table->prefix_lengths_in_search_order, (256 - i));
+    }));
 }
 
 void
@@ -432,19 +436,21 @@ ip6_mfib_table_entry_insert (ip6_mfib_t *mfib,
                              u32 len,
                              fib_node_index_t mfib_entry_index)
 {
-    ip6_mfib_node_t *i6mn = clib_mem_alloc(sizeof(*i6mn));
+    ip6_mfib_table_instance_t *table;
+    ip6_mfib_key_t key;
 
-    clib_memset(i6mn->i6mn_nodes, 0, sizeof(i6mn->i6mn_nodes));
+    table = &ip6_main.ip6_mtable;
+    IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
+    key.value = mfib_entry_index;
 
-    IP6_MFIB_MK_KEY_MASK(grp, src, len, &i6mn->i6mn_key);
-    i6mn->i6mn_entry = mfib_entry_index;
+    clib_bihash_add_del_40_8(&table->ip6_mhash, &key, 1);
 
-    if (NULL == rn_addroute(i6mn->i6mn_key.key,
-                            i6mn->i6mn_key.mask,
-                            mfib->rhead,
-                            i6mn->i6mn_nodes))
+    if (0 == table->dst_address_length_refcounts[len]++)
     {
-        ASSERT(0);
+        table->non_empty_dst_address_length_bitmap =
+            clib_bitmap_set (table->non_empty_dst_address_length_bitmap, 
+                             256 - len, 1);
+        compute_prefix_lengths_in_search_order (table);
     }
 }
 
@@ -454,14 +460,22 @@ ip6_mfib_table_entry_remove (ip6_mfib_t *mfib,
                              const ip6_address_t *src,
                              u32 len)
 {
-    ip6_mfib_node_t *i6mn;
+    ip6_mfib_table_instance_t *table;
     ip6_mfib_key_t key;
 
-    IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
+    IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
 
-    i6mn = (ip6_mfib_node_t*) rn_delete(key.key, key.mask, mfib->rhead);
+    table = &ip6_main.ip6_mtable;
+    clib_bihash_add_del_40_8(&table->ip6_mhash, &key, 0);
 
-    clib_mem_free(i6mn);
+    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, 
+                             256 - len, 0);
+	compute_prefix_lengths_in_search_order (table);
+    }
 }
 
 static clib_error_t *
@@ -536,39 +550,45 @@ ip6_mfib_table_show_all (ip6_mfib_t *mfib,
     vec_free(ctx.entries);
 }
 
-typedef struct ip6_mfib_radix_walk_ctx_t_
+/**
+ * @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_mfib_walk_ctx_t_
 {
-    mfib_table_walk_fn_t user_fn;
-    void *user_ctx;
-} ip6_mfib_radix_walk_ctx_t;
+    u32 i6w_mfib_index;
+    mfib_table_walk_fn_t i6w_fn;
+    void *i6w_ctx;
+} ip6_mfib_walk_ctx_t;
 
 static int
-ip6_mfib_table_radix_walk (struct radix_node *rn,
-                           void *arg)
+ip6_mfib_walk_cb (clib_bihash_kv_40_8_t * kvp,
+                 void *arg)
 {
-    ip6_mfib_radix_walk_ctx_t *ctx = arg;
-    ip6_mfib_node_t *i6mn;
-
-    i6mn = (ip6_mfib_node_t*) rn;
-
-    ctx->user_fn(i6mn->i6mn_entry, ctx->user_ctx);
+    ip6_mfib_walk_ctx_t *ctx = arg;
 
-    return (0);
+    if ((kvp->key[4] >> 32) == ctx->i6w_mfib_index)
+    {
+        return (ctx->i6w_fn(kvp->value, ctx->i6w_ctx));
+    }
+    return (FIB_TABLE_WALK_CONTINUE);
 }
 
 void
 ip6_mfib_table_walk (ip6_mfib_t *mfib,
                      mfib_table_walk_fn_t fn,
-                     void *ctx)
+                     void *arg)
 {
-    ip6_mfib_radix_walk_ctx_t rn_ctx = {
-        .user_fn = fn,
-        .user_ctx = ctx,
+    ip6_mfib_walk_ctx_t ctx = {
+        .i6w_mfib_index = mfib->index,
+        .i6w_fn = fn,
+        .i6w_ctx = arg,
     };
 
-    rn_walktree(mfib->rhead,
-                ip6_mfib_table_radix_walk,
-                &rn_ctx);
+    clib_bihash_foreach_key_value_pair_40_8(
+        &ip6_main.ip6_mtable.ip6_mhash,
+        ip6_mfib_walk_cb,
+        &ctx);
 }
 
 static clib_error_t *
diff --git a/src/vnet/mfib/ip6_mfib.h b/src/vnet/mfib/ip6_mfib.h
index 5ebdd0a6ff4..5ed330b30af 100644
--- a/src/vnet/mfib/ip6_mfib.h
+++ b/src/vnet/mfib/ip6_mfib.h
@@ -34,6 +34,9 @@ extern fib_node_index_t ip6_mfib_table_lookup(const ip6_mfib_t *fib,
                                               const ip6_address_t *src,
                                               const ip6_address_t *grp,
                                               u32 len);
+extern fib_node_index_t ip6_mfib_table_fwd_lookup(const ip6_mfib_t *fib,
+                                                  const ip6_address_t *src,
+                                                  const ip6_address_t *grp);
 extern fib_node_index_t ip6_mfib_table_lookup_exact_match(const ip6_mfib_t *fib,
                                                           const ip6_address_t *grp,
                                                           const ip6_address_t *src,
diff --git a/src/vnet/mfib/mfib_forward.c b/src/vnet/mfib/mfib_forward.c
index 4b121324fb6..634b675999e 100644
--- a/src/vnet/mfib/mfib_forward.c
+++ b/src/vnet/mfib/mfib_forward.c
@@ -165,9 +165,9 @@ mfib_forward_lookup (vlib_main_t * vm,
                 fib_index0 = vec_elt (ip6_main.mfib_index_by_sw_if_index,
                                       vnet_buffer(p0)->sw_if_index[VLIB_RX]);
                 ip0 = vlib_buffer_get_current (p0);
-                mfei0 = ip6_mfib_table_lookup2(ip6_mfib_get(fib_index0),
-                                               &ip0->src_address,
-                                               &ip0->dst_address);
+                mfei0 = ip6_mfib_table_fwd_lookup(ip6_mfib_get(fib_index0),
+                                                  &ip0->src_address,
+                                                  &ip0->dst_address);
             }
 
             vnet_buffer (p0)->ip.adj_index[VLIB_TX] = mfei0;
diff --git a/src/vpp/stats/stats_to_be_deprecated.c b/src/vpp/stats/stats_to_be_deprecated.c
index 70974271658..08117a1b736 100644
--- a/src/vpp/stats/stats_to_be_deprecated.c
+++ b/src/vpp/stats/stats_to_be_deprecated.c
@@ -2005,7 +2005,7 @@ do_ip6_fib_counters (stats_main_t * sm)
   u32 items_this_message;
   vl_api_ip6_fib_counter_t *ctrp = 0;
   u32 start_at_fib_index = 0;
-  BVT (clib_bihash) * h = &im6->ip6_table[IP6_FIB_TABLE_FWDING].ip6_hash;
+  clib_bihash_24_8_t *h = &im6->ip6_table[IP6_FIB_TABLE_FWDING].ip6_hash;
   add_routes_in_fib_arg_t _a, *a = &_a;
   int i;
 
@@ -2049,7 +2049,7 @@ again:
       if (clib_setjmp (&sm->jmp_buf, 0) == 0)
 	{
 	  start_at_fib_index = fib - im6->fibs;
-	  BV (clib_bihash_foreach_key_value_pair) (h, add_routes_in_fib, a);
+	  clib_bihash_foreach_key_value_pair_24_8 (h, add_routes_in_fib, a);
 	}
       else
 	{
diff --git a/test/requirements.txt b/test/requirements.txt
index 7ae21f875fa..b3b14651bc5 100644
--- a/test/requirements.txt
+++ b/test/requirements.txt
@@ -3,6 +3,7 @@ cryptography!=2.0                       # BSD/Apache-2.0
 faulthandler; python_version < '3.3' #  # BSD License (2 clause)
 flake8                                  # MIT
 ipaddress; python_version < '3.3'       # PSF
+parameterized>=0.6.1                    # BSD
 pexpect                                 # ISC
 psutil                                  # BSD
 pycodestyle                             # MIT (Expat license)       https://pypi.org/project/pycodestyle/
diff --git a/test/test_ip6.py b/test/test_ip6.py
index 6c44d79a18f..930d556a876 100644
--- a/test/test_ip6.py
+++ b/test/test_ip6.py
@@ -3,6 +3,7 @@
 import socket
 import unittest
 
+from parameterized import parameterized
 import scapy.layers.inet6 as inet6
 from scapy.contrib.mpls import MPLS
 from scapy.layers.inet6 import IPv6, ICMPv6ND_NS, ICMPv6ND_RS, \
@@ -2163,7 +2164,7 @@ class TestIPDeag(VppTestCase):
 
 
 class TestIP6Input(VppTestCase):
-    """ IPv6 Input Exceptions """
+    """ IPv6 Input Exception Test Cases """
 
     def setUp(self):
         super(TestIP6Input, self).setUp()
@@ -2181,25 +2182,10 @@ class TestIP6Input(VppTestCase):
             i.unconfig_ip6()
             i.admin_down()
 
-    def test_ip_input(self):
-        """ IP6 Input Exceptions """
-
-        #
-        # bad version - this is dropped
-        #
-        p_version = (Ether(src=self.pg0.remote_mac,
-                           dst=self.pg0.local_mac) /
-                     IPv6(src=self.pg0.remote_ip6,
-                          dst=self.pg1.remote_ip6,
-                          version=3) /
-                     inet6.UDP(sport=1234, dport=1234) /
-                     Raw('\xa5' * 100))
-
-        self.send_and_assert_no_replies(self.pg0, p_version * 65,
-                                        "funky version")
-
+    def test_ip_input_icmp_reply(self):
+        """ IP6 Input Exception - Return ICMP (3,0) """
         #
-        # hop limit - IMCP replies
+        # hop limit - ICMP replies
         #
         p_version = (Ether(src=self.pg0.remote_mac,
                            dst=self.pg0.local_mac) /
@@ -2212,9 +2198,45 @@ class TestIP6Input(VppTestCase):
         rx = self.send_and_expect(self.pg0, p_version * 65, self.pg0)
         rx = rx[0]
         icmp = rx[ICMPv6TimeExceeded]
-        self.assertEqual(icmp.type, 3)
+
         # 0: "hop limit exceeded in transit",
-        self.assertEqual(icmp.code, 0)
+        self.assertEqual((icmp.type, icmp.code), (3, 0))
+
+    icmpv6_data = '\x0a' * 18
+    all_0s = "::"
+    all_1s = "FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF"
+
+    @parameterized.expand([
+        # Name, src, dst, l4proto, msg, timeout
+        ("src='iface',   dst='iface'", None, None,
+         inet6.UDP(sport=1234, dport=1234), "funky version", None),
+        ("src='All 0's', dst='iface'", all_0s, None,
+         ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1),
+        ("src='iface',   dst='All 0's'", None, all_0s,
+         ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1),
+        ("src='All 1's', dst='iface'", all_1s, None,
+         ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1),
+        ("src='iface',   dst='All 1's'", None, all_1s,
+         ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1),
+        ("src='All 1's', dst='All 1's'", all_1s, all_1s,
+         ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1),
+
+    ])
+    def test_ip_input_no_replies(self, name, src, dst, l4, msg, timeout):
+
+        self._testMethodDoc = 'IPv6 Input Exception - %s' % name
+
+        p_version = (Ether(src=self.pg0.remote_mac,
+                           dst=self.pg0.local_mac) /
+                     IPv6(src=src or self.pg0.remote_ip6,
+                          dst=dst or self.pg1.remote_ip6,
+                          version=3) /
+                     l4 /
+                     Raw('\xa5' * 100))
+
+        self.send_and_assert_no_replies(self.pg0, p_version * 65,
+                                        remark=msg or "",
+                                        timeout=timeout)
 
 
 if __name__ == '__main__':