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/plugins/unittest/mfib_test.c b/src/plugins/unittest/mfib_test.c
index fda0258..bbe6709 100644
--- a/src/plugins/unittest/mfib_test.c
+++ b/src/plugins/unittest/mfib_test.c
@@ -543,7 +543,8 @@
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 @@
/*
* 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 @@
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 @@
/*
* 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 @@
/*
* 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 3888509..3f73ff9 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 1ac917c..3bda3b8 100644
--- a/src/vnet/dpo/lookup_dpo.c
+++ b/src/vnet/dpo/lookup_dpo.c
@@ -1305,9 +1305,9 @@
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 7375b56..60d1365 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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
.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 @@
.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 @@
} 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 @@
/* 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 @@
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 10ae75c..583a17f 100644
--- a/src/vnet/fib/ip6_fib.h
+++ b/src/vnet/fib/ip6_fib.h
@@ -69,9 +69,9 @@
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 @@
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 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--)
diff --git a/src/vnet/mfib/ip4_mfib.c b/src/vnet/mfib/ip4_mfib.c
index eaa61c0..9d70f0b 100644
--- a/src/vnet/mfib/ip4_mfib.c
+++ b/src/vnet/mfib/ip4_mfib.c
@@ -210,7 +210,7 @@
}
}
- 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 e98ac42..554a932 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 @@
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 @@
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 @@
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,20 +328,50 @@
const ip6_address_t *src,
u32 len)
{
- ip6_mfib_node_t *i6mn;
- ip6_mfib_key_t key;
+ ip6_mfib_key_t key, value;
+ int rv;
- IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
+ IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
- i6mn = (ip6_mfib_node_t*) rn_lookup(key.key, key.mask,
- (struct radix_node_head *)mfib->rhead);
+ rv = clib_bihash_search_inline_2_40_8(&ip6_main.ip6_mtable.ip6_mhash,
+ &key, &value);
+ if (rv == 0)
+ return value.value;
- if (NULL == i6mn)
+ return (FIB_NODE_INDEX_INVALID);
+}
+
+/*
+ * ip6_fib_table_lookup
+ *
+ * Longest prefix match for the forwarding plane (no mask given)
+ */
+fib_node_index_t
+ip6_mfib_table_fwd_lookup (const ip6_mfib_t *mfib,
+ const ip6_address_t *src,
+ const ip6_address_t *grp)
+{
+ 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);
+
+ for (i = 0; i < n; i++)
{
- return (INDEX_INVALID);
+ len = table->prefix_lengths_in_search_order[i];
+
+ ASSERT(len >= 0 && len <= 256);
+ IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
+
+ 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);
}
/*
@@ -388,41 +385,48 @@
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;
- IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
+ table = &ip6_main.ip6_mtable;
+ n = vec_len (table->prefix_lengths_in_search_order);
- i6mn = (ip6_mfib_node_t*) rn_search_m(key.key,
- mfib->rhead->rnh_treetop,
- key.mask);
+ /*
+ * 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++;
+ }
- ASSERT(NULL != i6mn);
+ for (; i < n; i++)
+ {
+ len = table->prefix_lengths_in_search_order[i];
- return (i6mn->i6mn_entry);
+ ASSERT(len >= 0 && len <= 256);
+ IP6_MFIB_MK_KEY(mfib, grp, src, len, key);
+
+ rv = clib_bihash_search_inline_2_40_8(&table->ip6_mhash, &key, &value);
+ if (rv == 0)
+ return value.value;
+ }
+
+ return (FIB_NODE_INDEX_INVALID);
}
-/*
- * ip6_fib_table_lookup
- *
- * Longest prefix match no mask
- */
-fib_node_index_t
-ip6_mfib_table_lookup2 (const ip6_mfib_t *mfib,
- const ip6_address_t *src,
- const ip6_address_t *grp)
+static void
+compute_prefix_lengths_in_search_order (ip6_mfib_table_instance_t *table)
{
- ip6_mfib_node_t *i6mn;
- ip6_mfib_key_t key;
-
- IP6_MFIB_MK_KEY(grp, src, &key);
-
- i6mn = (ip6_mfib_node_t*) rn_match(key.key,
- (struct radix_node_head *)mfib->rhead); // const cast
-
- ASSERT(NULL != i6mn);
-
- return (i6mn->i6mn_entry);
+ 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 @@
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 @@
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 @@
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;
+ ip6_mfib_walk_ctx_t *ctx = arg;
- i6mn = (ip6_mfib_node_t*) rn;
-
- ctx->user_fn(i6mn->i6mn_entry, ctx->user_ctx);
-
- 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 5ebdd0a..5ed330b 100644
--- a/src/vnet/mfib/ip6_mfib.h
+++ b/src/vnet/mfib/ip6_mfib.h
@@ -34,6 +34,9 @@
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 4b12132..634b675 100644
--- a/src/vnet/mfib/mfib_forward.c
+++ b/src/vnet/mfib/mfib_forward.c
@@ -165,9 +165,9 @@
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 7097427..08117a1 100644
--- a/src/vpp/stats/stats_to_be_deprecated.c
+++ b/src/vpp/stats/stats_to_be_deprecated.c
@@ -2005,7 +2005,7 @@
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 @@
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
{