X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvnet%2Fmfib%2Fip6_mfib.c;h=690f4ed9dfdb46770d7ddd6a90c322322e5f3055;hb=9db6ada77;hp=8f3dae8d7b5ff82a2859cbdc4a50d023040cffcf;hpb=5a8123bda0261158457e38bfb4922aa5961389ff;p=vpp.git diff --git a/src/vnet/mfib/ip6_mfib.c b/src/vnet/mfib/ip6_mfib.c index 8f3dae8d7b5..690f4ed9dfd 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 = { /* (*,*) */ @@ -151,23 +129,25 @@ static const ip6_mfib_special_t ip6_mfib_specials[] = static u32 -ip6_create_mfib_with_table_id (u32 table_id) +ip6_create_mfib_with_table_id (u32 table_id, + mfib_source_t src) { mfib_table_t *mfib_table; mfib_prefix_t pfx = { .fp_proto = FIB_PROTOCOL_IP6, }; const fib_route_path_t path_for_us = { - .frp_proto = FIB_PROTOCOL_IP6, + .frp_proto = DPO_PROTO_IP6, .frp_addr = zero_addr, .frp_sw_if_index = 0xffffffff, .frp_fib_index = ~0, - .frp_weight = 0, + .frp_weight = 1, .frp_flags = FIB_ROUTE_PATH_LOCAL, + .frp_mitf_flags = MFIB_ITF_FLAG_FORWARD, }; pool_get_aligned(ip6_main.mfibs, mfib_table, CLIB_CACHE_LINE_BYTES); - memset(mfib_table, 0, sizeof(*mfib_table)); + clib_memset(mfib_table, 0, sizeof(*mfib_table)); mfib_table->mft_proto = FIB_PROTOCOL_IP6; mfib_table->mft_index = @@ -182,12 +162,7 @@ ip6_create_mfib_with_table_id (u32 table_id) mfib_table->v6.table_id = table_id; - mfib_table_lock(mfib_table->mft_index, FIB_PROTOCOL_IP6); - - mfib_table->v6.rhead = - clib_mem_alloc_aligned (sizeof(*mfib_table->v6.rhead), - CLIB_CACHE_LINE_BYTES); - rn_inithead0(mfib_table->v6.rhead, 8); + mfib_table_lock(mfib_table->mft_index, FIB_PROTOCOL_IP6, src); /* * add the special entries into the new FIB @@ -195,6 +170,7 @@ ip6_create_mfib_with_table_id (u32 table_id) mfib_table_entry_update(mfib_table->mft_index, &all_zeros, MFIB_SOURCE_DEFAULT_ROUTE, + MFIB_RPF_ID_NONE, MFIB_ENTRY_FLAG_DROP); /* @@ -205,8 +181,7 @@ ip6_create_mfib_with_table_id (u32 table_id) mfib_table_entry_path_update(mfib_table->mft_index, &pfx, MFIB_SOURCE_SPECIAL, - &path_for_us, - MFIB_ITF_FLAG_FORWARD); + &path_for_us); })); return (mfib_table->mft_index); @@ -221,11 +196,11 @@ ip6_mfib_table_destroy (ip6_mfib_t *mfib) .fp_proto = FIB_PROTOCOL_IP6, }; const fib_route_path_t path_for_us = { - .frp_proto = FIB_PROTOCOL_IP6, + .frp_proto = DPO_PROTO_IP6, .frp_addr = zero_addr, .frp_sw_if_index = 0xffffffff, .frp_fib_index = ~0, - .frp_weight = 0, + .frp_weight = 1, .frp_flags = FIB_ROUTE_PATH_LOCAL, }; @@ -250,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); } @@ -258,11 +232,12 @@ void ip6_mfib_interface_enable_disable (u32 sw_if_index, int is_enable) { const fib_route_path_t path = { - .frp_proto = FIB_PROTOCOL_IP6, + .frp_proto = DPO_PROTO_IP6, .frp_addr = zero_addr, .frp_sw_if_index = sw_if_index, .frp_fib_index = ~0, - .frp_weight = 0, + .frp_weight = 1, + .frp_mitf_flags = MFIB_ITF_FLAG_ACCEPT, }; mfib_prefix_t pfx = { .fp_proto = FIB_PROTOCOL_IP6, @@ -279,8 +254,7 @@ ip6_mfib_interface_enable_disable (u32 sw_if_index, int is_enable) mfib_table_entry_path_update(mfib_index, &pfx, MFIB_SOURCE_SPECIAL, - &path, - MFIB_ITF_FLAG_ACCEPT); + &path); }); } else @@ -296,14 +270,15 @@ ip6_mfib_interface_enable_disable (u32 sw_if_index, int is_enable) } u32 -ip6_mfib_table_find_or_create_and_lock (u32 table_id) +ip6_mfib_table_find_or_create_and_lock (u32 table_id, + mfib_source_t src) { u32 index; index = ip6_mfib_index_from_table_id(table_id); if (~0 == index) - return ip6_create_mfib_with_table_id(table_id); - mfib_table_lock(index, FIB_PROTOCOL_IP6); + return ip6_create_mfib_with_table_id(table_id, src); + mfib_table_lock(index, FIB_PROTOCOL_IP6, src); return (index); } @@ -322,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); \ - 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; \ } /* @@ -358,68 +328,137 @@ 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_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); - - 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; - 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); + for (i = 0; i < n; i++) + { + len = table->prefix_lengths_in_search_order[i]; - ASSERT(NULL != i6mn); + 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); +} + + +fib_node_index_t +ip6_mfib_table_get_less_specific (const ip6_mfib_t *mfib, + const ip6_address_t *src, + const ip6_address_t *grp, + u32 len) +{ + u32 mask_len; + + /* + * in the absence of a tree structure for the table that allows for an O(1) + * parent get, a cheeky way to find the cover is to LPM for the prefix with + * mask-1. + * there should always be a cover, though it may be the default route. the + * default route's cover is the default route. + */ + if (len == 256) + { + /* go from (S,G) to (*,G*) */ + mask_len = 128; + } + else if (len != 0) + { + mask_len = len - 1; + } + else + { + mask_len = len; + } + + return (ip6_mfib_table_lookup(mfib, src, grp, mask_len)); } /* * 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 <= 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 @@ -429,19 +468,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; - memset(i6mn, 0, sizeof(*i6mn)); + 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); } } @@ -451,14 +492,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 * @@ -469,17 +518,43 @@ ip6_mfib_module_init (vlib_main_t * vm) VLIB_INIT_FUNCTION(ip6_mfib_module_init); +u8 * +format_ip6_mfib_table_memory (u8 * s, va_list * args) +{ + u64 bytes_inuse; + + bytes_inuse = alloc_arena_next(&(ip6_main.ip6_mtable.ip6_mhash)); + + s = format(s, "%=30s %=6d %=12ld\n", + "IPv6 multicast", + pool_elts(ip6_main.mfibs), + bytes_inuse); + + return (s); +} + static void ip6_mfib_table_show_one (ip6_mfib_t *mfib, vlib_main_t * vm, ip6_address_t *src, ip6_address_t *grp, - u32 mask_len) + u32 mask_len, + u32 cover) { - vlib_cli_output(vm, "%U", - format_mfib_entry, - ip6_mfib_table_lookup(mfib, src, grp, mask_len), - MFIB_ENTRY_FORMAT_DETAIL); + if (cover) + { + vlib_cli_output(vm, "%U", + format_mfib_entry, + ip6_mfib_table_get_less_specific(mfib, src, grp, mask_len), + MFIB_ENTRY_FORMAT_DETAIL); + } + else + { + vlib_cli_output(vm, "%U", + format_mfib_entry, + ip6_mfib_table_lookup(mfib, src, grp, mask_len), + MFIB_ENTRY_FORMAT_DETAIL); + } } typedef struct ip6_mfib_show_ctx_t_ { @@ -487,14 +562,14 @@ typedef struct ip6_mfib_show_ctx_t_ { } ip6_mfib_show_ctx_t; -static int +static walk_rc_t ip6_mfib_table_collect_entries (fib_node_index_t mfei, void *arg) { ip6_mfib_show_ctx_t *ctx = arg; vec_add1(ctx->entries, mfei); - return (0); + return (WALK_CONTINUE); } static void @@ -523,39 +598,44 @@ 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) +static void +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) + { + ctx->i6w_fn(kvp->value, ctx->i6w_ctx); + } } 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 * @@ -563,15 +643,16 @@ ip6_show_mfib (vlib_main_t * vm, unformat_input_t * input, vlib_cli_command_t * cmd) { - ip6_main_t * im4 = &ip6_main; + ip6_main_t * im6 = &ip6_main; mfib_table_t *mfib_table; int verbose, matching; ip6_address_t grp, src = {{0}}; - u32 mask = 32; + u32 mask = 128, cover; int table_id = -1, fib_index = ~0; verbose = 1; matching = 0; + cover = 0; while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) { @@ -584,25 +665,30 @@ ip6_show_mfib (vlib_main_t * vm, unformat_ip6_address, &grp)) { matching = 1; - mask = 64; + mask = 256; } - else if (unformat (input, "%U", unformat_ip6_address, &grp)) + else if (unformat (input, "%U/%d", unformat_ip6_address, &grp, &mask)) { + clib_memset(&src, 0, sizeof(src)); matching = 1; - mask = 32; } - else if (unformat (input, "%U/%d", - unformat_ip6_address, &grp, &mask)) + else if (unformat (input, "%U", unformat_ip6_address, &grp)) + { + clib_memset(&src, 0, sizeof(src)); matching = 1; + mask = 128; + } else if (unformat (input, "table %d", &table_id)) ; else if (unformat (input, "index %d", &fib_index)) ; + else if (unformat (input, "cover")) + cover = 1; else break; } - pool_foreach (mfib_table, im4->mfibs, + pool_foreach (mfib_table, im6->mfibs, ({ ip6_mfib_t *mfib = &mfib_table->v6; @@ -635,7 +721,7 @@ ip6_show_mfib (vlib_main_t * vm, } else { - ip6_mfib_table_show_one(mfib, vm, &src, &grp, mask); + ip6_mfib_table_show_one(mfib, vm, &src, &grp, mask, cover); } })); @@ -643,7 +729,7 @@ ip6_show_mfib (vlib_main_t * vm, } /* - * This command displays the IPv4 MulticasrFIB Tables (VRF Tables) and + * This command displays the IPv6 MulticasrFIB Tables (VRF Tables) and * the route entries for each table. * * @note This command will run for a long time when the FIB tables are @@ -651,9 +737,9 @@ ip6_show_mfib (vlib_main_t * vm, * a single table or summary mode. * * @cliexpar - * Example of how to display all the IPv4 Multicast FIB tables: + * Example of how to display all the IPv6 Multicast FIB tables: * @cliexstart{show ip fib} - * ipv4-VRF:0, fib_index 0 + * ipv6-VRF:0, fib_index 0 * (*, 0.0.0.0/0): flags:D, * Interfaces: * multicast-ip6-chain @@ -665,18 +751,18 @@ ip6_show_mfib (vlib_main_t * vm, * test-eth0: Accept, * multicast-ip6-chain * [@2]: dpo-replicate: [index:1 buckets:2 to:[0:0]] - * [0] [@1]: ipv4-mcast: test-eth1: IP6: d0:d1:d2:d3:d4:01 -> 01:00:05:00:00:00 - * [1] [@1]: ipv4-mcast: test-eth2: IP6: d0:d1:d2:d3:d4:02 -> 01:00:05:00:00:00 + * [0] [@1]: ipv6-mcast: test-eth1: IP6: d0:d1:d2:d3:d4:01 -> 01:00:05:00:00:00 + * [1] [@1]: ipv6-mcast: test-eth2: IP6: d0:d1:d2:d3:d4:02 -> 01:00:05:00:00:00 * * @cliexend - * Example of how to display a summary of all IPv4 FIB tables: + * Example of how to display a summary of all IPv6 FIB tables: * @cliexstart{show ip fib summary} - * ipv4-VRF:0, fib_index 0, flow hash: src dst sport dport proto + * ipv6-VRF:0, fib_index 0, flow hash: src dst sport dport proto * Prefix length Count * 0 1 * 8 2 * 32 4 - * ipv4-VRF:7, fib_index 1, flow hash: src dst sport dport proto + * ipv6-VRF:7, fib_index 1, flow hash: src dst sport dport proto * Prefix length Count * 0 1 * 8 2