IP6-MFIB: replace the radix tree with bihash (VPP-1526)
Change-Id: I7a48890c075826fbd8c75436dfdc5ffff230a693
Signed-off-by: Neale Ranns <nranns@cisco.com>
diff --git a/src/vnet/ip/ip6.h b/src/vnet/ip/ip6.h
index 6e0cfff..ab17f66 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 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 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 @@
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 @@
*/
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 999be87..56cef4a 100644
--- a/src/vnet/ip/ip6_forward.c
+++ b/src/vnet/ip/ip6_forward.c
@@ -2658,12 +2658,15 @@
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 dfcb270..a7440ea 100644
--- a/src/vnet/ip/ip6_ll_table.c
+++ b/src/vnet/ip/ip6_ll_table.c
@@ -298,7 +298,7 @@
/* 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 @@
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--)