From: Neale Ranns Date: Fri, 23 Nov 2018 17:00:27 +0000 (-0800) Subject: IP6-MFIB: replace the radix tree with bihash (VPP-1526) X-Git-Tag: v19.04-rc0~162 X-Git-Url: https://gerrit.fd.io/r/gitweb?p=vpp.git;a=commitdiff_plain;h=ae8098350cb7b96f7495fa4d4180238064256e14 IP6-MFIB: replace the radix tree with bihash (VPP-1526) Change-Id: I7a48890c075826fbd8c75436dfdc5ffff230a693 Signed-off-by: Neale Ranns --- diff --git a/src/plugins/unittest/mfib_test.c b/src/plugins/unittest/mfib_test.c index fda02580bee..bbe6709f4d7 100644 --- a/src/plugins/unittest/mfib_test.c +++ b/src/plugins/unittest/mfib_test.c @@ -543,7 +543,8 @@ mfib_test_i (fib_protocol_t PROTO, 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 @@ mfib_test_i (fib_protocol_t PROTO, /* * 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 @@ mfib_test_i (fib_protocol_t PROTO, 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 @@ mfib_test_i (fib_protocol_t PROTO, /* * 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 @@ mfib_test_i (fib_protocol_t PROTO, /* * 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 38885095a4f..3f73ff9f1d2 100644 --- a/src/vnet/adj/adj_nbr.c +++ b/src/vnet/adj/adj_nbr.c @@ -18,6 +18,8 @@ #include #include +#include + /* * 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 1ac917cb0de..3bda3b81186 100644 --- a/src/vnet/dpo/lookup_dpo.c +++ b/src/vnet/dpo/lookup_dpo.c @@ -1305,9 +1305,9 @@ lookup_dpo_ip_dst_mcast_inline (vlib_main_t * vm, 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 7375b56ee51..60d13659925 100644 --- a/src/vnet/fib/ip6_fib.c +++ b/src/vnet/fib/ip6_fib.c @@ -17,6 +17,9 @@ #include #include +#include +#include + static void vnet_ip6_fib_init (u32 fib_index) { @@ -171,7 +174,7 @@ ip6_fib_table_lookup (u32 fib_index, 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 @@ ip6_fib_table_lookup (u32 fib_index, 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 @@ ip6_fib_table_lookup_exact_match (u32 fib_index, 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 @@ ip6_fib_table_lookup_exact_match (u32 fib_index, 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 @@ ip6_fib_table_entry_remove (u32 fib_index, 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 @@ ip6_fib_table_entry_remove (u32 fib_index, 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 @@ ip6_fib_table_entry_insert (u32 fib_index, 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 @@ ip6_fib_table_entry_insert (u32 fib_index, 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 @@ ip6_fib_table_fwding_dpo_update (u32 fib_index, 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 @@ ip6_fib_table_fwding_dpo_update (u32 fib_index, 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 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index, 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 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index, 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 @@ ip6_fib_table_walk (u32 fib_index, .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 @@ ip6_fib_table_sub_tree_walk (u32 fib_index, .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 @@ typedef struct { } 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 @@ ip6_show_fib (vlib_main_t * vm, /* 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 @@ ip6_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--) diff --git a/src/vnet/fib/ip6_fib.h b/src/vnet/fib/ip6_fib.h index 10ae75ce6f9..583a17f01b8 100644 --- a/src/vnet/fib/ip6_fib.h +++ b/src/vnet/fib/ip6_fib.h @@ -69,9 +69,9 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im, 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 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im, 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 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--) diff --git a/src/vnet/mfib/ip4_mfib.c b/src/vnet/mfib/ip4_mfib.c index eaa61c0f86c..9d70f0b664f 100644 --- a/src/vnet/mfib/ip4_mfib.c +++ b/src/vnet/mfib/ip4_mfib.c @@ -210,7 +210,7 @@ ip4_mfib_table_lookup (const ip4_mfib_t *mfib, } } - 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 e98ac42374a..554a932844f 100644 --- a/src/vnet/mfib/ip6_mfib.c +++ b/src/vnet/mfib/ip6_mfib.c @@ -19,32 +19,10 @@ #include #include -/** - * 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 @@ ip6_create_mfib_with_table_id (u32 table_id, 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 @@ ip6_mfib_table_destroy (ip6_mfib_t *mfib) 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 @@ ip6_mfib_table_get_index_for_sw_if_index (u32 sw_if_index) 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,68 +328,105 @@ ip6_mfib_table_lookup_exact_match (const ip6_mfib_t *mfib, const ip6_address_t *src, u32 len) { - ip6_mfib_node_t *i6mn; - ip6_mfib_key_t key; - - IP6_MFIB_MK_KEY_MASK(grp, src, len, &key); + ip6_mfib_key_t key, value; + int rv; - i6mn = (ip6_mfib_node_t*) rn_lookup(key.key, key.mask, - (struct radix_node_head *)mfib->rhead); + IP6_MFIB_MK_KEY(mfib, grp, src, len, key); - if (NULL == i6mn) - { - return (INDEX_INVALID); - } + rv = clib_bihash_search_inline_2_40_8(&ip6_main.ip6_mtable.ip6_mhash, + &key, &value); + if (rv == 0) + return value.value; - return (i6mn->i6mn_entry); + return (FIB_NODE_INDEX_INVALID); } /* * ip6_fib_table_lookup * - * Longest prefix match + * Longest prefix match for the forwarding plane (no mask given) */ fib_node_index_t -ip6_mfib_table_lookup (const ip6_mfib_t *mfib, - const ip6_address_t *src, - const ip6_address_t *grp, - u32 len) +ip6_mfib_table_fwd_lookup (const ip6_mfib_t *mfib, + const ip6_address_t *src, + const ip6_address_t *grp) { - 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, len; + int rv; + + table = &ip6_main.ip6_mtable; + n = vec_len (table->prefix_lengths_in_search_order); - IP6_MFIB_MK_KEY_MASK(grp, src, len, &key); + for (i = 0; i < n; i++) + { + len = table->prefix_lengths_in_search_order[i]; - i6mn = (ip6_mfib_node_t*) rn_search_m(key.key, - mfib->rhead->rnh_treetop, - key.mask); + ASSERT(len >= 0 && len <= 256); + IP6_MFIB_MK_KEY(mfib, grp, src, len, key); - ASSERT(NULL != i6mn); + 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); } /* * ip6_fib_table_lookup * - * Longest prefix match no mask + * Longest prefix match */ fib_node_index_t -ip6_mfib_table_lookup2 (const ip6_mfib_t *mfib, - const ip6_address_t *src, - const ip6_address_t *grp) +ip6_mfib_table_lookup (const ip6_mfib_t *mfib, + const ip6_address_t *src, + 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; + + table = &ip6_main.ip6_mtable; + n = vec_len (table->prefix_lengths_in_search_order); + + /* + * 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++; + } - IP6_MFIB_MK_KEY(grp, src, &key); + for (; i < n; i++) + { + len = table->prefix_lengths_in_search_order[i]; - i6mn = (ip6_mfib_node_t*) rn_match(key.key, - (struct radix_node_head *)mfib->rhead); // const cast + ASSERT(len >= 0 && len <= 256); + IP6_MFIB_MK_KEY(mfib, grp, src, len, key); - ASSERT(NULL != i6mn); + 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); +} + +static void +compute_prefix_lengths_in_search_order (ip6_mfib_table_instance_t *table) +{ + 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 @@ ip6_mfib_table_entry_insert (ip6_mfib_t *mfib, 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 @@ ip6_mfib_table_entry_remove (ip6_mfib_t *mfib, 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 @@ ip6_mfib_table_show_all (ip6_mfib_t *mfib, 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; - - i6mn = (ip6_mfib_node_t*) rn; - - ctx->user_fn(i6mn->i6mn_entry, ctx->user_ctx); + ip6_mfib_walk_ctx_t *ctx = arg; - 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 5ebdd0a6ff4..5ed330b30af 100644 --- a/src/vnet/mfib/ip6_mfib.h +++ b/src/vnet/mfib/ip6_mfib.h @@ -34,6 +34,9 @@ extern fib_node_index_t ip6_mfib_table_lookup(const ip6_mfib_t *fib, 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 4b121324fb6..634b675999e 100644 --- a/src/vnet/mfib/mfib_forward.c +++ b/src/vnet/mfib/mfib_forward.c @@ -165,9 +165,9 @@ mfib_forward_lookup (vlib_main_t * vm, 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 70974271658..08117a1b736 100644 --- a/src/vpp/stats/stats_to_be_deprecated.c +++ b/src/vpp/stats/stats_to_be_deprecated.c @@ -2005,7 +2005,7 @@ do_ip6_fib_counters (stats_main_t * sm) 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 @@ again: 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 { diff --git a/test/requirements.txt b/test/requirements.txt index 7ae21f875fa..b3b14651bc5 100644 --- a/test/requirements.txt +++ b/test/requirements.txt @@ -3,6 +3,7 @@ cryptography!=2.0 # BSD/Apache-2.0 faulthandler; python_version < '3.3' # # BSD License (2 clause) flake8 # MIT ipaddress; python_version < '3.3' # PSF +parameterized>=0.6.1 # BSD pexpect # ISC psutil # BSD pycodestyle # MIT (Expat license) https://pypi.org/project/pycodestyle/ diff --git a/test/test_ip6.py b/test/test_ip6.py index 6c44d79a18f..930d556a876 100644 --- a/test/test_ip6.py +++ b/test/test_ip6.py @@ -3,6 +3,7 @@ import socket import unittest +from parameterized import parameterized import scapy.layers.inet6 as inet6 from scapy.contrib.mpls import MPLS from scapy.layers.inet6 import IPv6, ICMPv6ND_NS, ICMPv6ND_RS, \ @@ -2163,7 +2164,7 @@ class TestIPDeag(VppTestCase): class TestIP6Input(VppTestCase): - """ IPv6 Input Exceptions """ + """ IPv6 Input Exception Test Cases """ def setUp(self): super(TestIP6Input, self).setUp() @@ -2181,25 +2182,10 @@ class TestIP6Input(VppTestCase): i.unconfig_ip6() i.admin_down() - def test_ip_input(self): - """ IP6 Input Exceptions """ - - # - # bad version - this is dropped - # - p_version = (Ether(src=self.pg0.remote_mac, - dst=self.pg0.local_mac) / - IPv6(src=self.pg0.remote_ip6, - dst=self.pg1.remote_ip6, - version=3) / - inet6.UDP(sport=1234, dport=1234) / - Raw('\xa5' * 100)) - - self.send_and_assert_no_replies(self.pg0, p_version * 65, - "funky version") - + def test_ip_input_icmp_reply(self): + """ IP6 Input Exception - Return ICMP (3,0) """ # - # hop limit - IMCP replies + # hop limit - ICMP replies # p_version = (Ether(src=self.pg0.remote_mac, dst=self.pg0.local_mac) / @@ -2212,9 +2198,45 @@ class TestIP6Input(VppTestCase): rx = self.send_and_expect(self.pg0, p_version * 65, self.pg0) rx = rx[0] icmp = rx[ICMPv6TimeExceeded] - self.assertEqual(icmp.type, 3) + # 0: "hop limit exceeded in transit", - self.assertEqual(icmp.code, 0) + self.assertEqual((icmp.type, icmp.code), (3, 0)) + + icmpv6_data = '\x0a' * 18 + all_0s = "::" + all_1s = "FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF" + + @parameterized.expand([ + # Name, src, dst, l4proto, msg, timeout + ("src='iface', dst='iface'", None, None, + inet6.UDP(sport=1234, dport=1234), "funky version", None), + ("src='All 0's', dst='iface'", all_0s, None, + ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1), + ("src='iface', dst='All 0's'", None, all_0s, + ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1), + ("src='All 1's', dst='iface'", all_1s, None, + ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1), + ("src='iface', dst='All 1's'", None, all_1s, + ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1), + ("src='All 1's', dst='All 1's'", all_1s, all_1s, + ICMPv6EchoRequest(id=0xb, seq=5, data=icmpv6_data), None, 0.1), + + ]) + def test_ip_input_no_replies(self, name, src, dst, l4, msg, timeout): + + self._testMethodDoc = 'IPv6 Input Exception - %s' % name + + p_version = (Ether(src=self.pg0.remote_mac, + dst=self.pg0.local_mac) / + IPv6(src=src or self.pg0.remote_ip6, + dst=dst or self.pg1.remote_ip6, + version=3) / + l4 / + Raw('\xa5' * 100)) + + self.send_and_assert_no_replies(self.pg0, p_version * 65, + remark=msg or "", + timeout=timeout) if __name__ == '__main__':