#include <vnet/mfib/mfib_entry.h>
#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 = {
/* (*,*) */
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 =
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
mfib_table_entry_update(mfib_table->mft_index,
&all_zeros,
MFIB_SOURCE_DEFAULT_ROUTE,
+ MFIB_RPF_ID_NONE,
MFIB_ENTRY_FLAG_DROP);
/*
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);
.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,
};
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);
}
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,
mfib_table_entry_path_update(mfib_index,
&pfx,
MFIB_SOURCE_SPECIAL,
- &path,
- MFIB_ITF_FLAG_ACCEPT);
+ &path);
});
}
else
}
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);
}
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; \
}
/*
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
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);
}
}
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 *
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_ {
} 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
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 *
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)
{
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;
}
else
{
- ip6_mfib_table_show_one(mfib, vm, &src, &grp, mask);
+ ip6_mfib_table_show_one(mfib, vm, &src, &grp, mask, cover);
}
}));
}
/*
- * 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
* 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
* 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
Code Review / vpp.git / blobdiff