From ae8098350cb7b96f7495fa4d4180238064256e14 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Fri, 23 Nov 2018 09:00:27 -0800 Subject: IP6-MFIB: replace the radix tree with bihash (VPP-1526) Change-Id: I7a48890c075826fbd8c75436dfdc5ffff230a693 Signed-off-by: Neale Ranns --- src/vnet/ip/ip6.h | 31 ++++++++++++++++++++++++------- src/vnet/ip/ip6_forward.c | 7 +++++-- src/vnet/ip/ip6_ll_table.c | 4 ++-- 3 files changed, 31 insertions(+), 11 deletions(-) (limited to 'src/vnet/ip') 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 #include #include +#include #include #include #include @@ -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--) -- cgit 1.2.3-korg