summaryrefslogtreecommitdiffstats
path: root/src/vnet/ip
diff options
context:
space:
mode:
authorNeale Ranns <nranns@cisco.com>2018-11-23 09:00:27 -0800
committerFlorin Coras <florin.coras@gmail.com>2018-12-16 01:00:32 +0000
commitae8098350cb7b96f7495fa4d4180238064256e14 (patch)
tree879980c4edd7d6c99a393b3fa4ad81cdc19fc62e /src/vnet/ip
parent7e70ff52c18e62f4fdef1f63dea4edd64bcf9c76 (diff)
IP6-MFIB: replace the radix tree with bihash (VPP-1526)
Change-Id: I7a48890c075826fbd8c75436dfdc5ffff230a693 Signed-off-by: Neale Ranns <nranns@cisco.com>
Diffstat (limited to 'src/vnet/ip')
-rw-r--r--src/vnet/ip/ip6.h31
-rw-r--r--src/vnet/ip/ip6_forward.c7
-rw-r--r--src/vnet/ip/ip6_ll_table.c4
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--)