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

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

3 files changed, 31 insertions, 11 deletions

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--)