diff options
Diffstat (limited to 'src/vnet')
| -rw-r--r-- | src/vnet/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | src/vnet/dpo/receive_dpo.c | 6 | ||||
| -rw-r--r-- | src/vnet/dpo/receive_dpo.h | 2 | ||||
| -rw-r--r-- | src/vnet/dpo/replicate_dpo.c | 88 | ||||
| -rw-r--r-- | src/vnet/dpo/replicate_dpo.h | 17 | ||||
| -rw-r--r-- | src/vnet/ip/ip_api.c | 40 | ||||
| -rw-r--r-- | src/vnet/mfib/ip4_mfib.c | 32 | ||||
| -rw-r--r-- | src/vnet/mfib/ip4_mfib.h | 4 | ||||
| -rw-r--r-- | src/vnet/mfib/ip6_mfib.c | 62 | ||||
| -rw-r--r-- | src/vnet/mfib/ip6_mfib.h | 4 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry.c | 423 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry.h | 52 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry_cover.c | 180 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry_cover.h | 42 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry_delegate.c | 143 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry_delegate.h | 90 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry_src.c | 101 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry_src.h | 142 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_entry_src_rr.c | 112 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_table.c | 136 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_table.h | 23 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_types.c | 76 | ||||
| -rw-r--r-- | src/vnet/mfib/mfib_types.h | 27 |
23 files changed, 1630 insertions, 177 deletions
diff --git a/src/vnet/CMakeLists.txt b/src/vnet/CMakeLists.txt index 62bd57582b4..353bd3f7a6d 100644 --- a/src/vnet/CMakeLists.txt +++ b/src/vnet/CMakeLists.txt @@ -1279,6 +1279,11 @@ list(APPEND VNET_SOURCES mfib/mfib_signal.c mfib/mfib_itf.c mfib/mfib_entry.c + mfib/mfib_entry.c + mfib/mfib_entry_cover.c + mfib/mfib_entry_delegate.c + mfib/mfib_entry_src.c + mfib/mfib_entry_src_rr.c mfib/mfib_table.c ) diff --git a/src/vnet/dpo/receive_dpo.c b/src/vnet/dpo/receive_dpo.c index 30ddceeb23e..949dbfa6587 100644 --- a/src/vnet/dpo/receive_dpo.c +++ b/src/vnet/dpo/receive_dpo.c @@ -25,6 +25,12 @@ */ receive_dpo_t *receive_dpo_pool; +int +dpo_is_receive (const dpo_id_t *dpo) +{ + return (dpo->dpoi_type == DPO_RECEIVE); +} + static receive_dpo_t * receive_dpo_alloc (void) { diff --git a/src/vnet/dpo/receive_dpo.h b/src/vnet/dpo/receive_dpo.h index 9ab86a824c6..ee3c7836aff 100644 --- a/src/vnet/dpo/receive_dpo.h +++ b/src/vnet/dpo/receive_dpo.h @@ -47,6 +47,8 @@ typedef struct receive_dpo_t_ u16 rd_locks; } receive_dpo_t; +extern int dpo_is_receive(const dpo_id_t *dpo); + extern void receive_dpo_add_or_lock (dpo_proto_t proto, u32 sw_if_index, const ip46_address_t *nh_addr, diff --git a/src/vnet/dpo/replicate_dpo.c b/src/vnet/dpo/replicate_dpo.c index 39b17f103c9..69e367aa368 100644 --- a/src/vnet/dpo/replicate_dpo.c +++ b/src/vnet/dpo/replicate_dpo.c @@ -16,6 +16,7 @@ #include <vnet/ip/lookup.h> #include <vnet/dpo/replicate_dpo.h> #include <vnet/dpo/drop_dpo.h> +#include <vnet/dpo/receive_dpo.h> #include <vnet/adj/adj.h> #include <vnet/mpls/mpls_types.h> @@ -101,6 +102,23 @@ replicate_alloc_i (void) } static u8* +format_replicate_flags (u8 *s, va_list *args) +{ + int flags = va_arg (*args, int); + + if (flags == REPLICATE_FLAGS_NONE) + { + s = format (s, "none"); + } + else if (flags & REPLICATE_FLAGS_HAS_LOCAL) + { + s = format (s, "has-local "); + } + + return (s); +} + +static u8* replicate_format (index_t repi, replicate_format_flags_t flags, u32 indent, @@ -118,6 +136,7 @@ replicate_format (index_t repi, s = format(s, "%U: ", format_dpo_type, DPO_REPLICATE); s = format(s, "[index:%d buckets:%d ", repi, rep->rep_n_buckets); + s = format(s, "flags:[%U] ", format_replicate_flags, rep->rep_flags); s = format(s, "to:[%Ld:%Ld]]", to.packets, to.bytes); for (i = 0; i < rep->rep_n_buckets; i++) @@ -182,6 +201,14 @@ replicate_set_bucket_i (replicate_t *rep, dpo_id_t *buckets, const dpo_id_t *next) { + if (dpo_is_receive(&buckets[bucket])) + { + rep->rep_flags &= ~REPLICATE_FLAGS_HAS_LOCAL; + } + if (dpo_is_receive(next)) + { + rep->rep_flags |= REPLICATE_FLAGS_HAS_LOCAL; + } dpo_stack(DPO_REPLICATE, rep->rep_proto, &buckets[bucket], next); } @@ -492,6 +519,67 @@ replicate_lock (dpo_id_t *dpo) rep->rep_locks++; } +index_t +replicate_dup (replicate_flags_t flags, + index_t repi) +{ + replicate_t *rep, *copy; + + rep = replicate_get(repi); + + if (rep->rep_flags == flags || + flags & REPLICATE_FLAGS_HAS_LOCAL) + { + /* + * we can include all the buckets from the original in the copy + */ + return (repi); + } + else + { + /* + * caller doesn't want the local paths that the original has + */ + if (rep->rep_n_buckets == 1) + { + /* + * original has only one bucket that is the local, so create + * a new one with only the drop + */ + copy = replicate_create_i (1, rep->rep_proto); + + replicate_set_bucket_i(copy, 0, + replicate_get_buckets(copy), + drop_dpo_get(rep->rep_proto)); + } + else + { + dpo_id_t *old_buckets, *copy_buckets; + u16 bucket, pos; + + copy = replicate_create_i(rep->rep_n_buckets - 1, + rep->rep_proto); + + rep = replicate_get(repi); + old_buckets = replicate_get_buckets(rep); + copy_buckets = replicate_get_buckets(copy); + pos = 0; + + for (bucket = 0; bucket < rep->rep_n_buckets; bucket++) + { + if (!dpo_is_receive(&old_buckets[bucket])) + { + replicate_set_bucket_i(copy, pos, copy_buckets, + (&old_buckets[bucket])); + pos++; + } + } + } + } + + return (replicate_get_index(copy)); +} + static void replicate_destroy (replicate_t *rep) { diff --git a/src/vnet/dpo/replicate_dpo.h b/src/vnet/dpo/replicate_dpo.h index 7b075394bc3..70faef3e28f 100644 --- a/src/vnet/dpo/replicate_dpo.h +++ b/src/vnet/dpo/replicate_dpo.h @@ -47,6 +47,15 @@ extern replicate_main_t replicate_main; #define REP_NUM_INLINE_BUCKETS 4 /** + * Flags on the replicate DPO + */ +typedef enum replicate_flags_t_ +{ + REPLICATE_FLAGS_NONE, + REPLICATE_FLAGS_HAS_LOCAL, +} __clib_packed replicate_flags_t; + +/** * The FIB DPO provieds; * - load-balancing over the next DPOs in the chain/graph * - per-route counters @@ -71,6 +80,11 @@ typedef struct replicate_t_ { dpo_proto_t rep_proto; /** + * Flags specifying the replicate properties/behaviour + */ + replicate_flags_t rep_flags; + + /** * The number of locks, which is approximately the number of users, * of this load-balance. * Load-balance objects of via-entries are heavily shared by recursives, @@ -121,6 +135,9 @@ extern int replicate_is_drop(const dpo_id_t *dpo); extern u16 replicate_n_buckets(index_t repi); +extern index_t replicate_dup(replicate_flags_t flags, + index_t repi); + /** * The encapsulation breakages are for fast DP access */ diff --git a/src/vnet/ip/ip_api.c b/src/vnet/ip/ip_api.c index b7ee17cfca8..5a2aa60b057 100644 --- a/src/vnet/ip/ip_api.c +++ b/src/vnet/ip/ip_api.c @@ -408,13 +408,13 @@ send_ip_mfib_details (vl_api_registration_t * reg, { fib_route_path_encode_t *api_rpath, *api_rpaths = NULL; vl_api_ip_mfib_details_t *mp; + const mfib_prefix_t *pfx; mfib_entry_t *mfib_entry; vl_api_fib_path_t *fp; - mfib_prefix_t pfx; int path_count; mfib_entry = mfib_entry_get (mfei); - mfib_entry_get_prefix (mfei, &pfx); + pfx = mfib_entry_get_prefix (mfei); mfib_entry_encode (mfei, &api_rpaths); path_count = vec_len (api_rpaths); @@ -428,11 +428,11 @@ send_ip_mfib_details (vl_api_registration_t * reg, mp->rpf_id = mfib_entry->mfe_rpf_id; mp->entry_flags = mfib_entry->mfe_flags; mp->table_id = htonl (table_id); - mp->address_length = pfx.fp_len; - memcpy (mp->grp_address, &pfx.fp_grp_addr.ip4, - sizeof (pfx.fp_grp_addr.ip4)); - memcpy (mp->src_address, &pfx.fp_src_addr.ip4, - sizeof (pfx.fp_src_addr.ip4)); + mp->address_length = pfx->fp_len; + memcpy (mp->grp_address, &pfx->fp_grp_addr.ip4, + sizeof (pfx->fp_grp_addr.ip4)); + memcpy (mp->src_address, &pfx->fp_src_addr.ip4, + sizeof (pfx->fp_src_addr.ip4)); mp->count = htonl (path_count); fp = mp->path; @@ -503,7 +503,7 @@ static void send_ip6_mfib_details (vpe_api_main_t * am, vl_api_registration_t * reg, u32 table_id, - mfib_prefix_t * pfx, + const mfib_prefix_t * pfx, fib_route_path_encode_t * api_rpaths, u32 context) { vl_api_ip6_mfib_details_t *mp; @@ -559,8 +559,8 @@ vl_api_ip6_mfib_dump_t_handler (vl_api_ip6_mfib_dump_t * mp) vl_api_registration_t *reg; ip6_main_t *im = &ip6_main; mfib_table_t *mfib_table; + const mfib_prefix_t *pfx; fib_node_index_t *mfeip; - mfib_prefix_t pfx; fib_route_path_encode_t *api_rpaths = NULL; vl_api_ip6_mfib_dump_ctc_t ctx = { .entries = NULL, @@ -582,11 +582,11 @@ vl_api_ip6_mfib_dump_t_handler (vl_api_ip6_mfib_dump_t * mp) vec_foreach(mfeip, ctx.entries) { - mfib_entry_get_prefix (*mfeip, &pfx); + pfx = mfib_entry_get_prefix (*mfeip); mfib_entry_encode (*mfeip, &api_rpaths); send_ip6_mfib_details (am, reg, mfib_table->mft_table_id, - &pfx, api_rpaths, + pfx, api_rpaths, mp->context); } vec_reset_length (api_rpaths); @@ -1833,7 +1833,7 @@ vl_mfib_signal_send_one (vl_api_registration_t * reg, u32 context, const mfib_signal_t * mfs) { vl_api_mfib_signal_details_t *mp; - mfib_prefix_t prefix; + const mfib_prefix_t *prefix; mfib_table_t *mfib; mfib_itf_t *mfi; @@ -1844,25 +1844,25 @@ vl_mfib_signal_send_one (vl_api_registration_t * reg, mp->context = context; mfi = mfib_itf_get (mfs->mfs_itf); - mfib_entry_get_prefix (mfs->mfs_entry, &prefix); + prefix = mfib_entry_get_prefix (mfs->mfs_entry); mfib = mfib_table_get (mfib_entry_get_fib_index (mfs->mfs_entry), - prefix.fp_proto); + prefix->fp_proto); mp->table_id = ntohl (mfib->mft_table_id); mp->sw_if_index = ntohl (mfi->mfi_sw_if_index); - if (FIB_PROTOCOL_IP4 == prefix.fp_proto) + if (FIB_PROTOCOL_IP4 == prefix->fp_proto) { - mp->grp_address_len = ntohs (prefix.fp_len); + mp->grp_address_len = ntohs (prefix->fp_len); - memcpy (mp->grp_address, &prefix.fp_grp_addr.ip4, 4); - if (prefix.fp_len > 32) + memcpy (mp->grp_address, &prefix->fp_grp_addr.ip4, 4); + if (prefix->fp_len > 32) { - memcpy (mp->src_address, &prefix.fp_src_addr.ip4, 4); + memcpy (mp->src_address, &prefix->fp_src_addr.ip4, 4); } } else { - mp->grp_address_len = ntohs (prefix.fp_len); + mp->grp_address_len = ntohs (prefix->fp_len); ASSERT (0); } diff --git a/src/vnet/mfib/ip4_mfib.c b/src/vnet/mfib/ip4_mfib.c index 9d70f0b664f..d20d1f6c2b9 100644 --- a/src/vnet/mfib/ip4_mfib.c +++ b/src/vnet/mfib/ip4_mfib.c @@ -224,6 +224,38 @@ ip4_mfib_table_lookup (const ip4_mfib_t *mfib, return (FIB_NODE_INDEX_INVALID); } +fib_node_index_t +ip4_mfib_table_get_less_specific (const ip4_mfib_t *mfib, + const ip4_address_t *src, + const ip4_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 == 64) + { + /* go from (S,G) to (*,G*) */ + mask_len = 32; + } + else if (len != 0) + { + mask_len = len - 1; + } + else + { + mask_len = len; + } + + return (ip4_mfib_table_lookup(mfib, src, grp, mask_len)); +} + void ip4_mfib_table_entry_insert (ip4_mfib_t *mfib, const ip4_address_t *grp, diff --git a/src/vnet/mfib/ip4_mfib.h b/src/vnet/mfib/ip4_mfib.h index 7767d795cad..5b225596469 100644 --- a/src/vnet/mfib/ip4_mfib.h +++ b/src/vnet/mfib/ip4_mfib.h @@ -38,6 +38,10 @@ extern fib_node_index_t ip4_mfib_table_lookup_exact_match(const ip4_mfib_t *fib, const ip4_address_t *grp, const ip4_address_t *src, u32 len); +extern fib_node_index_t ip4_mfib_table_get_less_specific (const ip4_mfib_t *mfib, + const ip4_address_t *src, + const ip4_address_t *grp, + u32 len); extern void ip4_mfib_table_entry_remove(ip4_mfib_t *fib, const ip4_address_t *grp, diff --git a/src/vnet/mfib/ip6_mfib.c b/src/vnet/mfib/ip6_mfib.c index 554a932844f..d47887be699 100644 --- a/src/vnet/mfib/ip6_mfib.c +++ b/src/vnet/mfib/ip6_mfib.c @@ -365,7 +365,6 @@ ip6_mfib_table_fwd_lookup (const ip6_mfib_t *mfib, 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; @@ -374,6 +373,39 @@ ip6_mfib_table_fwd_lookup (const ip6_mfib_t *mfib, 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 * @@ -501,12 +533,23 @@ 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_ { @@ -600,11 +643,12 @@ ip6_show_mfib (vlib_main_t * vm, 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) { @@ -634,6 +678,8 @@ ip6_show_mfib (vlib_main_t * vm, ; else if (unformat (input, "index %d", &fib_index)) ; + else if (unformat (input, "cover")) + cover = 1; else break; } @@ -671,7 +717,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); } })); diff --git a/src/vnet/mfib/ip6_mfib.h b/src/vnet/mfib/ip6_mfib.h index 5ed330b30af..f197b9d9fe8 100644 --- a/src/vnet/mfib/ip6_mfib.h +++ b/src/vnet/mfib/ip6_mfib.h @@ -41,6 +41,10 @@ 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, u32 len); +extern 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); extern void ip6_mfib_table_entry_remove(ip6_mfib_t *fib, const ip6_address_t *grp, diff --git a/src/vnet/mfib/mfib_entry.c b/src/vnet/mfib/mfib_entry.c index 90b223e3c25..51d775dd295 100644 --- a/src/vnet/mfib/mfib_entry.c +++ b/src/vnet/mfib/mfib_entry.c @@ -16,7 +16,10 @@ #include <vlib/vlib.h> #include <vnet/mfib/mfib_entry.h> +#include <vnet/mfib/mfib_entry_src.h> +#include <vnet/mfib/mfib_entry_cover.h> #include <vnet/fib/fib_path_list.h> +#include <vnet/fib/fib_walk.h> #include <vnet/dpo/drop_dpo.h> #include <vnet/dpo/replicate_dpo.h> @@ -27,66 +30,6 @@ vlib_log_class_t mfib_entry_logger; /** - * Debug macro - */ -#define MFIB_ENTRY_DBG(_e, _fmt, _args...) \ -{ \ - vlib_log_debug(mfib_entry_logger, \ - "e:[%d:%U]: " _fmt, \ - mfib_entry_get_index(_e), \ - format_mfib_prefix, \ - &_e->mfe_prefix, \ - ##_args); \ -} - -/** - * MFIB extensions to each path - */ -typedef struct mfib_path_ext_t_ -{ - mfib_itf_flags_t mfpe_flags; - fib_node_index_t mfpe_path; -} mfib_path_ext_t; - -/** - * The source of an MFIB entry - */ -typedef struct mfib_entry_src_t_ -{ - /** - * Which source this is - */ - mfib_source_t mfes_src; - - /** - * Route flags - */ - mfib_entry_flags_t mfes_flags; - - /** - * The path-list of forwarding interfaces - */ - fib_node_index_t mfes_pl; - - /** - * RPF-ID - */ - fib_rpf_id_t mfes_rpf_id; - - /** - * Hash table of path extensions - */ - mfib_path_ext_t *mfes_exts; - - /** - * The hash table of all interfaces. - * This is forwarding time information derived from the paths - * and their extensions. - */ - mfib_itf_t *mfes_itfs; -} mfib_entry_src_t; - -/** * Pool of path extensions */ static mfib_path_ext_t *mfib_path_ext_pool; @@ -184,8 +127,14 @@ format_mfib_entry (u8 * s, va_list * args) s = format (s, " locks:%d\n", mfib_entry->mfe_node.fn_locks); vec_foreach(msrc, mfib_entry->mfe_srcs) { - s = format (s, " src:%s", mfib_source_names[msrc->mfes_src]); - s = format (s, ": %U\n", format_mfib_entry_flags, msrc->mfes_flags); + s = format (s, " src:%s locks:%d:", + mfib_source_names[msrc->mfes_src], + msrc->mfes_ref_count); + if (msrc->mfes_cover != FIB_NODE_INDEX_INVALID) + { + s = format (s, " cover:%d", msrc->mfes_cover); + } + s = format (s, " %U\n", format_mfib_entry_flags, msrc->mfes_flags); if (FIB_NODE_INDEX_INVALID != msrc->mfes_pl) { s = fib_path_list_format(msrc->mfes_pl, s); @@ -254,6 +203,9 @@ mfib_entry_src_init (mfib_entry_t *mfib_entry, .mfes_pl = FIB_NODE_INDEX_INVALID, .mfes_flags = MFIB_ENTRY_FLAG_NONE, .mfes_src = source, + .mfes_cover = FIB_NODE_INDEX_INVALID, + .mfes_sibling = FIB_NODE_INDEX_INVALID, + .mfes_ref_count = 1, }; vec_add1(mfib_entry->mfe_srcs, esrc); @@ -294,19 +246,51 @@ static mfib_entry_src_t * mfib_entry_src_find_or_create (mfib_entry_t *mfib_entry, mfib_source_t source) { - mfib_entry_src_t *esrc; + mfib_entry_src_t *msrc; - esrc = mfib_entry_src_find(mfib_entry, source, NULL); + msrc = mfib_entry_src_find(mfib_entry, source, NULL); - if (NULL == esrc) + if (NULL == msrc) { mfib_entry_src_init(mfib_entry, source); + msrc = mfib_entry_src_find(mfib_entry, source, NULL); } - return (mfib_entry_src_find(mfib_entry, source, NULL)); + return (msrc); +} + +static mfib_entry_src_t * +mfib_entry_src_update (mfib_entry_t *mfib_entry, + mfib_source_t source, + fib_rpf_id_t rpf_id, + mfib_entry_flags_t entry_flags) +{ + mfib_entry_src_t *msrc; + + msrc = mfib_entry_src_find_or_create(mfib_entry, source); + + msrc->mfes_flags = entry_flags; + msrc->mfes_rpf_id = rpf_id; + + return (msrc); } -static mfib_entry_src_t* +static mfib_entry_src_t * +mfib_entry_src_update_and_lock (mfib_entry_t *mfib_entry, + mfib_source_t source, + fib_rpf_id_t rpf_id, + mfib_entry_flags_t entry_flags) +{ + mfib_entry_src_t *msrc; + + msrc = mfib_entry_src_update(mfib_entry, source, rpf_id, entry_flags); + + msrc->mfes_ref_count++; + + return (msrc); +} + +mfib_entry_src_t* mfib_entry_get_best_src (const mfib_entry_t *mfib_entry) { mfib_entry_src_t *bsrc; @@ -326,6 +310,16 @@ mfib_entry_get_best_src (const mfib_entry_t *mfib_entry) return (bsrc); } +static mfib_source_t +mfib_entry_get_best_source (const mfib_entry_t *mfib_entry) +{ + mfib_entry_src_t *bsrc; + + bsrc = mfib_entry_get_best_src(mfib_entry); + + return (bsrc->mfes_src); +} + int mfib_entry_is_sourced (fib_node_index_t mfib_entry_index, mfib_source_t source) @@ -337,6 +331,13 @@ mfib_entry_is_sourced (fib_node_index_t mfib_entry_index, return (NULL != mfib_entry_src_find(mfib_entry, source, NULL)); } +int +mfib_entry_is_host (fib_node_index_t mfib_entry_index) +{ + return (mfib_prefix_is_host(mfib_entry_get_prefix(mfib_entry_index))); +} + + static void mfib_entry_src_flush (mfib_entry_src_t *msrc) { @@ -364,8 +365,19 @@ mfib_entry_src_remove (mfib_entry_t *mfib_entry, if (NULL != msrc) { - mfib_entry_src_flush(msrc); - vec_del1(mfib_entry->mfe_srcs, index); + ASSERT(0 != msrc->mfes_ref_count); + msrc->mfes_ref_count--; + + if (0 == msrc->mfes_ref_count) + { + mfib_entry_src_deactivate(mfib_entry, msrc); + mfib_entry_src_flush(msrc); + + vec_del1(mfib_entry->mfe_srcs, index); + if (vec_len (mfib_entry->mfe_srcs) > 1) + vec_sort_with_function(mfib_entry->mfe_srcs, + mfib_entry_src_cmp_for_sort); + } } } @@ -552,8 +564,7 @@ mfib_entry_stack (mfib_entry_t *mfib_entry, mfib_entry->mfe_sibling); } - if (NULL != msrc && - FIB_NODE_INDEX_INVALID != msrc->mfes_pl) + if (NULL != msrc) { mfib_entry_collect_forwarding_ctx_t ctx = { .next_hops = NULL, @@ -561,10 +572,27 @@ mfib_entry_stack (mfib_entry_t *mfib_entry, .msrc = msrc, }; - fib_path_list_walk(msrc->mfes_pl, - mfib_entry_src_collect_forwarding, - &ctx); + /* + * link the entry to the path-list. + * The entry needs to be a child so that we receive the back-walk + * updates to recalculate forwarding. + */ + mfib_entry->mfe_pl = msrc->mfes_pl; + mfib_entry->mfe_flags = msrc->mfes_flags; + mfib_entry->mfe_itfs = msrc->mfes_itfs; + mfib_entry->mfe_rpf_id = msrc->mfes_rpf_id; + if (FIB_NODE_INDEX_INVALID != mfib_entry->mfe_pl) + { + mfib_entry->mfe_sibling = + fib_path_list_child_add(mfib_entry->mfe_pl, + FIB_NODE_TYPE_MFIB_ENTRY, + mfib_entry_get_index(mfib_entry)); + + fib_path_list_walk(mfib_entry->mfe_pl, + mfib_entry_src_collect_forwarding, + &ctx); + } if (!(MFIB_ENTRY_FLAG_EXCLUSIVE & mfib_entry->mfe_flags)) { if (NULL == ctx.next_hops) @@ -616,17 +644,6 @@ mfib_entry_stack (mfib_entry_t *mfib_entry, dpo_reset(&ctx.next_hops[0].path_dpo); vec_free(ctx.next_hops); } - - /* - * link the entry to the path-list. - * The entry needs to be a child so that we receive the back-walk - * updates to recalculate forwarding. - */ - mfib_entry->mfe_pl = msrc->mfes_pl; - mfib_entry->mfe_sibling = - fib_path_list_child_add(mfib_entry->mfe_pl, - FIB_NODE_TYPE_MFIB_ENTRY, - mfib_entry_get_index(mfib_entry)); } else { @@ -634,6 +651,17 @@ mfib_entry_stack (mfib_entry_t *mfib_entry, &mfib_entry->mfe_rep, drop_dpo_get(dp)); } + + /* + * time for walkies fido. + */ + fib_node_back_walk_ctx_t bw_ctx = { + .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE, + }; + + fib_walk_sync(FIB_NODE_TYPE_MFIB_ENTRY, + mfib_entry_get_index(mfib_entry), + &bw_ctx); } static fib_node_index_t @@ -689,23 +717,36 @@ mfib_entry_src_path_remove (mfib_entry_src_t *msrc, } static void -mfib_entry_recalculate_forwarding (mfib_entry_t *mfib_entry) +mfib_entry_recalculate_forwarding (mfib_entry_t *mfib_entry, + mfib_source_t old_best) { - mfib_entry_src_t *bsrc; + mfib_entry_src_t *bsrc, *osrc; /* * copy the forwarding data from the bast source */ bsrc = mfib_entry_get_best_src(mfib_entry); + osrc = mfib_entry_src_find(mfib_entry, old_best, NULL); if (NULL != bsrc) { - mfib_entry->mfe_flags = bsrc->mfes_flags; - mfib_entry->mfe_itfs = bsrc->mfes_itfs; - mfib_entry->mfe_rpf_id = bsrc->mfes_rpf_id; + if (bsrc->mfes_src != old_best) + { + /* + * we are changing from one source to another + * deactivate the old, and activate the new + */ + mfib_entry_src_deactivate(mfib_entry, osrc); + mfib_entry_src_activate(mfib_entry, bsrc); + } + } + else + { + mfib_entry_src_deactivate(mfib_entry, osrc); } mfib_entry_stack(mfib_entry, bsrc); + mfib_entry_cover_update_notify(mfib_entry); } @@ -714,7 +755,8 @@ mfib_entry_create (u32 fib_index, mfib_source_t source, const mfib_prefix_t *prefix, fib_rpf_id_t rpf_id, - mfib_entry_flags_t entry_flags) + mfib_entry_flags_t entry_flags, + index_t repi) { fib_node_index_t mfib_entry_index; mfib_entry_t *mfib_entry; @@ -722,11 +764,37 @@ mfib_entry_create (u32 fib_index, mfib_entry = mfib_entry_alloc(fib_index, prefix, &mfib_entry_index); - msrc = mfib_entry_src_find_or_create(mfib_entry, source); - msrc->mfes_flags = entry_flags; - msrc->mfes_rpf_id = rpf_id; + msrc = mfib_entry_src_update(mfib_entry, source, + rpf_id, entry_flags); - mfib_entry_recalculate_forwarding(mfib_entry); + if (INDEX_INVALID != repi) + { + /* + * The source is providing its own replicate DPO. + * Create a sepcial path-list to manage it, that way + * this entry and the source are equivalent to a normal + * entry + */ + fib_node_index_t old_pl_index; + dpo_proto_t dp; + dpo_id_t dpo = DPO_INVALID; + + dp = fib_proto_to_dpo(mfib_entry_get_proto(mfib_entry)); + old_pl_index = msrc->mfes_pl; + + dpo_set(&dpo, DPO_REPLICATE, dp, repi); + + msrc->mfes_pl = + fib_path_list_create_special(dp, + FIB_PATH_LIST_FLAG_EXCLUSIVE, + &dpo); + + dpo_reset(&dpo); + fib_path_list_lock(msrc->mfes_pl); + fib_path_list_unlock(old_pl_index); + } + + mfib_entry_recalculate_forwarding(mfib_entry, MFIB_SOURCE_NONE); return (mfib_entry_index); } @@ -740,25 +808,18 @@ mfib_entry_ok_for_delete (mfib_entry_t *mfib_entry) static int mfib_entry_src_ok_for_delete (const mfib_entry_src_t *msrc) { - return ((MFIB_ENTRY_FLAG_NONE == msrc->mfes_flags && + return ((INDEX_INVALID == msrc->mfes_cover && + MFIB_ENTRY_FLAG_NONE == msrc->mfes_flags && 0 == fib_path_list_get_n_paths(msrc->mfes_pl))); } -int -mfib_entry_update (fib_node_index_t mfib_entry_index, - mfib_source_t source, - mfib_entry_flags_t entry_flags, - fib_rpf_id_t rpf_id, - index_t repi) -{ - mfib_entry_t *mfib_entry; - mfib_entry_src_t *msrc; - - mfib_entry = mfib_entry_get(mfib_entry_index); - msrc = mfib_entry_src_find_or_create(mfib_entry, source); - msrc->mfes_flags = entry_flags; - msrc->mfes_rpf_id = rpf_id; +static void +mfib_entry_update_i (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc, + mfib_source_t current_best, + index_t repi) +{ if (INDEX_INVALID != repi) { /* @@ -792,10 +853,50 @@ mfib_entry_update (fib_node_index_t mfib_entry_index, * this source has no interfaces and no flags. * it has nothing left to give - remove it */ - mfib_entry_src_remove(mfib_entry, source); + mfib_entry_src_remove(mfib_entry, msrc->mfes_src); } - mfib_entry_recalculate_forwarding(mfib_entry); + mfib_entry_recalculate_forwarding(mfib_entry, current_best); +} + +int +mfib_entry_special_add (fib_node_index_t mfib_entry_index, + mfib_source_t source, + mfib_entry_flags_t entry_flags, + fib_rpf_id_t rpf_id, + index_t repi) +{ + mfib_source_t current_best; + mfib_entry_t *mfib_entry; + mfib_entry_src_t *msrc; + + mfib_entry = mfib_entry_get(mfib_entry_index); + current_best = mfib_entry_get_best_source(mfib_entry); + + msrc = mfib_entry_src_update_and_lock(mfib_entry, source, rpf_id, + entry_flags); + + mfib_entry_update_i(mfib_entry, msrc, current_best, repi); + + return (mfib_entry_ok_for_delete(mfib_entry)); +} + +int +mfib_entry_update (fib_node_index_t mfib_entry_index, + mfib_source_t source, + mfib_entry_flags_t entry_flags, + fib_rpf_id_t rpf_id, + index_t repi) +{ + mfib_source_t current_best; + mfib_entry_t *mfib_entry; + mfib_entry_src_t *msrc; + + mfib_entry = mfib_entry_get(mfib_entry_index); + current_best = mfib_entry_get_best_source(mfib_entry); + msrc = mfib_entry_src_update(mfib_entry, source, rpf_id, entry_flags); + + mfib_entry_update_i(mfib_entry, msrc, current_best, repi); return (mfib_entry_ok_for_delete(mfib_entry)); } @@ -828,6 +929,7 @@ mfib_entry_path_update (fib_node_index_t mfib_entry_index, mfib_itf_flags_t itf_flags) { fib_node_index_t path_index; + mfib_source_t current_best; mfib_path_ext_t *path_ext; mfib_entry_t *mfib_entry; mfib_entry_src_t *msrc; @@ -835,6 +937,7 @@ mfib_entry_path_update (fib_node_index_t mfib_entry_index, mfib_entry = mfib_entry_get(mfib_entry_index); ASSERT(NULL != mfib_entry); + current_best = mfib_entry_get_best_source(mfib_entry); msrc = mfib_entry_src_find_or_create(mfib_entry, source); /* @@ -897,7 +1000,7 @@ mfib_entry_path_update (fib_node_index_t mfib_entry_index, } } - mfib_entry_recalculate_forwarding(mfib_entry); + mfib_entry_recalculate_forwarding(mfib_entry, current_best); } /* @@ -912,11 +1015,13 @@ mfib_entry_path_remove (fib_node_index_t mfib_entry_index, const fib_route_path_t *rpath) { fib_node_index_t path_index; + mfib_source_t current_best; mfib_entry_t *mfib_entry; mfib_entry_src_t *msrc; mfib_entry = mfib_entry_get(mfib_entry_index); ASSERT(NULL != mfib_entry); + current_best = mfib_entry_get_best_source(mfib_entry); msrc = mfib_entry_src_find(mfib_entry, source, NULL); if (NULL == msrc) @@ -968,7 +1073,7 @@ mfib_entry_path_remove (fib_node_index_t mfib_entry_index, mfib_entry_src_remove(mfib_entry, source); } - mfib_entry_recalculate_forwarding(mfib_entry); + mfib_entry_recalculate_forwarding(mfib_entry, current_best); return (mfib_entry_ok_for_delete(mfib_entry)); } @@ -982,12 +1087,14 @@ int mfib_entry_delete (fib_node_index_t mfib_entry_index, mfib_source_t source) { + mfib_source_t current_best; mfib_entry_t *mfib_entry; mfib_entry = mfib_entry_get(mfib_entry_index); + current_best = mfib_entry_get_best_source(mfib_entry); mfib_entry_src_remove(mfib_entry, source); - mfib_entry_recalculate_forwarding(mfib_entry); + mfib_entry_recalculate_forwarding(mfib_entry, current_best); return (mfib_entry_ok_for_delete(mfib_entry)); } @@ -1116,7 +1223,11 @@ static fib_node_back_walk_rc_t mfib_entry_back_walk_notify (fib_node_t *node, fib_node_back_walk_ctx_t *ctx) { - mfib_entry_recalculate_forwarding(mfib_entry_from_fib_node(node)); + mfib_entry_t *mfib_entry; + + mfib_entry = mfib_entry_from_fib_node(node); + mfib_entry_recalculate_forwarding(mfib_entry, + mfib_entry_get_best_source(mfib_entry)); return (FIB_NODE_BACK_WALK_CONTINUE); } @@ -1219,15 +1330,14 @@ mfib_entry_encode (fib_node_index_t mfib_entry_index, } } - -void -mfib_entry_get_prefix (fib_node_index_t mfib_entry_index, - mfib_prefix_t *pfx) +const mfib_prefix_t * +mfib_entry_get_prefix (fib_node_index_t mfib_entry_index) { mfib_entry_t *mfib_entry; mfib_entry = mfib_entry_get(mfib_entry_index); - *pfx = mfib_entry->mfe_prefix; + + return (&mfib_entry->mfe_prefix); } u32 @@ -1253,6 +1363,7 @@ mfib_entry_contribute_ip_forwarding (fib_node_index_t mfib_entry_index) void mfib_entry_contribute_forwarding (fib_node_index_t mfib_entry_index, fib_forward_chain_type_t type, + mfib_entry_fwd_flags_t flags, dpo_id_t *dpo) { /* @@ -1267,9 +1378,26 @@ mfib_entry_contribute_forwarding (fib_node_index_t mfib_entry_index, dp = fib_proto_to_dpo(mfib_entry->mfe_prefix.fp_proto); - if (type == fib_forw_chain_type_from_dpo_proto(dp)) + if (type == mfib_forw_chain_type_from_dpo_proto(dp)) { - dpo_copy(dpo, &mfib_entry->mfe_rep); + replicate_t * rep; + + rep = replicate_get(mfib_entry->mfe_rep.dpoi_index); + + if ((rep->rep_flags & REPLICATE_FLAGS_HAS_LOCAL) && + (flags & MFIB_ENTRY_FWD_FLAG_NO_LOCAL)) + { + /* + * caller does not want the local paths that the entry has + */ + dpo_set(dpo, DPO_REPLICATE, rep->rep_proto, + replicate_dup(REPLICATE_FLAGS_NONE, + mfib_entry->mfe_rep.dpoi_index)); + } + else + { + dpo_copy(dpo, &mfib_entry->mfe_rep); + } } else { @@ -1277,6 +1405,55 @@ mfib_entry_contribute_forwarding (fib_node_index_t mfib_entry_index, } } +/* + * fib_entry_cover_changed + * + * this entry is tracking its cover and that cover has changed. + */ +void +mfib_entry_cover_changed (fib_node_index_t mfib_entry_index) +{ + mfib_entry_t *mfib_entry; + mfib_entry_src_t *msrc; + mfib_src_res_t res; + + mfib_entry = mfib_entry_get(mfib_entry_index); + msrc = mfib_entry_get_best_src(mfib_entry); + + res = mfib_entry_src_cover_change(mfib_entry, msrc); + + if (MFIB_SRC_REEVALUATE == res) + { + mfib_entry_recalculate_forwarding(mfib_entry, msrc->mfes_src); + } + MFIB_ENTRY_DBG(mfib_entry, "cover-changed"); +} + +/* + * mfib_entry_cover_updated + * + * this entry is tracking its cover and that cover has been updated + * (i.e. its forwarding information has changed). + */ +void +mfib_entry_cover_updated (fib_node_index_t mfib_entry_index) +{ + mfib_entry_t *mfib_entry; + mfib_entry_src_t *msrc; + mfib_src_res_t res; + + mfib_entry = mfib_entry_get(mfib_entry_index); + msrc = mfib_entry_get_best_src(mfib_entry); + + res = mfib_entry_src_cover_update(mfib_entry, msrc); + + if (MFIB_SRC_REEVALUATE == res) + { + mfib_entry_recalculate_forwarding(mfib_entry, msrc->mfes_src); + } + MFIB_ENTRY_DBG(mfib_entry, "cover-updated"); +} + u32 mfib_entry_pool_size (void) { diff --git a/src/vnet/mfib/mfib_entry.h b/src/vnet/mfib/mfib_entry.h index 880c1e2933c..8ab7cee5ea7 100644 --- a/src/vnet/mfib/mfib_entry.h +++ b/src/vnet/mfib/mfib_entry.h @@ -19,6 +19,7 @@ #include <vnet/fib/fib_node.h> #include <vnet/mfib/mfib_types.h> #include <vnet/mfib/mfib_itf.h> +#include <vnet/mfib/mfib_entry_delegate.h> #include <vnet/ip/ip.h> #include <vnet/dpo/dpo.h> @@ -34,10 +35,12 @@ typedef struct mfib_entry_t_ { * Base class. The entry's node representation in the graph. */ fib_node_t mfe_node; + /** * The prefix of the route */ mfib_prefix_t mfe_prefix; + /** * The index of the FIB table this entry is in */ @@ -82,8 +85,28 @@ typedef struct mfib_entry_t_ { * A hash table of interfaces */ mfib_itf_t *mfe_itfs; + + /** + * A vector of delegates. + */ + mfib_entry_delegate_t *fe_delegates; } mfib_entry_t; +/** + * Debug macro + */ +extern vlib_log_class_t mfib_entry_logger; + +#define MFIB_ENTRY_DBG(_e, _fmt, _args...) \ +{ \ + vlib_log_debug(mfib_entry_logger, \ + "e:[%d:%U]: " _fmt, \ + mfib_entry_get_index(_e), \ + format_mfib_prefix, \ + &_e->mfe_prefix, \ + ##_args); \ +} + #define MFIB_ENTRY_FORMAT_BRIEF (0x0) #define MFIB_ENTRY_FORMAT_DETAIL (0x1) #define MFIB_ENTRY_FORMAT_DETAIL2 (0x2) @@ -95,7 +118,8 @@ extern fib_node_index_t mfib_entry_create(u32 fib_index, mfib_source_t source, const mfib_prefix_t *prefix, fib_rpf_id_t rpf_id, - mfib_entry_flags_t entry_flags); + mfib_entry_flags_t entry_flags, + index_t repi); extern int mfib_entry_update(fib_node_index_t fib_entry_index, mfib_source_t source, @@ -103,6 +127,12 @@ extern int mfib_entry_update(fib_node_index_t fib_entry_index, fib_rpf_id_t rpf_id, index_t rep_dpo); +extern int mfib_entry_special_add(fib_node_index_t fib_entry_index, + mfib_source_t source, + mfib_entry_flags_t entry_flags, + fib_rpf_id_t rpf_id, + index_t rep_dpo); + extern void mfib_entry_path_update(fib_node_index_t fib_entry_index, mfib_source_t source, const fib_route_path_t *rpath, @@ -127,19 +157,35 @@ extern void mfib_entry_child_remove(fib_node_index_t mfib_entry_index, extern void mfib_entry_lock(fib_node_index_t fib_entry_index); extern void mfib_entry_unlock(fib_node_index_t fib_entry_index); -extern void mfib_entry_get_prefix(fib_node_index_t fib_entry_index, - mfib_prefix_t *pfx); +extern const mfib_prefix_t *mfib_entry_get_prefix(fib_node_index_t fib_entry_index); extern u32 mfib_entry_get_fib_index(fib_node_index_t fib_entry_index); extern int mfib_entry_is_sourced(fib_node_index_t fib_entry_index, mfib_source_t source); +extern int mfib_entry_is_host(fib_node_index_t fib_entry_index); extern u32 mfib_entry_get_stats_index(fib_node_index_t fib_entry_index); +extern void mfib_entry_cover_changed(fib_node_index_t fib_entry_index); +extern void mfib_entry_cover_updated(fib_node_index_t fib_entry_index); extern const dpo_id_t*mfib_entry_contribute_ip_forwarding( fib_node_index_t mfib_entry_index); +/** + * Flags to control what is present in the replicate DPO returned when + * the entry contributes forwarding + */ +typedef enum mfib_entry_fwd_flags_t_ +{ + MFIB_ENTRY_FWD_FLAG_NONE, + /** + * Do not reutrn any local replications in the set + */ + MFIB_ENTRY_FWD_FLAG_NO_LOCAL, +} mfib_entry_fwd_flags_t; + extern void mfib_entry_contribute_forwarding( fib_node_index_t mfib_entry_index, fib_forward_chain_type_t type, + mfib_entry_fwd_flags_t flags, dpo_id_t *dpo); extern void mfib_entry_encode(fib_node_index_t fib_entry_index, diff --git a/src/vnet/mfib/mfib_entry_cover.c b/src/vnet/mfib/mfib_entry_cover.c new file mode 100644 index 00000000000..6caeb1b6928 --- /dev/null +++ b/src/vnet/mfib/mfib_entry_cover.c @@ -0,0 +1,180 @@ +/* + * Copyright (c) 2016 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <vnet/mfib/mfib_entry_cover.h> +#include <vnet/mfib/mfib_entry_src.h> +#include <vnet/fib/fib_node_list.h> + +u32 +mfib_entry_cover_track (mfib_entry_t* cover, + fib_node_index_t covered) +{ + mfib_entry_delegate_t *mfed; + + MFIB_ENTRY_DBG(cover, "cover-track %d", covered); + + ASSERT(mfib_entry_get_index(cover) != covered); + + mfed = mfib_entry_delegate_get(cover, MFIB_ENTRY_DELEGATE_COVERED); + + if (NULL == mfed) + { + mfed = mfib_entry_delegate_find_or_add(cover, MFIB_ENTRY_DELEGATE_COVERED); + mfed->mfd_list = fib_node_list_create(); + } + + return (fib_node_list_push_front(mfed->mfd_list, + 0, FIB_NODE_TYPE_MFIB_ENTRY, + covered)); +} + +void +mfib_entry_cover_untrack (mfib_entry_t* cover, + u32 tracked_index) +{ + mfib_entry_delegate_t *mfed; + + MFIB_ENTRY_DBG(cover, "cover-untrack @ %d", tracked_index); + + mfed = mfib_entry_delegate_get(cover, MFIB_ENTRY_DELEGATE_COVERED); + + if (NULL == mfed) + return; + + fib_node_list_remove(mfed->mfd_list, tracked_index); + + if (0 == fib_node_list_get_size(mfed->mfd_list)) + { + fib_node_list_destroy(&mfed->mfd_list); + mfib_entry_delegate_remove(cover, MFIB_ENTRY_DELEGATE_COVERED); + } +} + +/** + * Internal struct to hold user supplied paraneters for the cover walk + */ +typedef struct mfib_enty_cover_walk_ctx_t_ { + mfib_entry_t *cover; + mfib_entry_covered_walk_t walk; + void *ctx; +} mfib_enty_cover_walk_ctx_t; + +static int +mfib_entry_cover_walk_node_ptr (fib_node_ptr_t *depend, + void *args) +{ + mfib_enty_cover_walk_ctx_t *ctx = args; + + ctx->walk(ctx->cover, depend->fnp_index, ctx->ctx); + + /* continue */ + return (1); +} + +void +mfib_entry_cover_walk (mfib_entry_t *cover, + mfib_entry_covered_walk_t walk, + void *args) +{ + mfib_entry_delegate_t *mfed; + + mfed = mfib_entry_delegate_get(cover, MFIB_ENTRY_DELEGATE_COVERED); + + if (NULL == mfed) + return; + + mfib_enty_cover_walk_ctx_t ctx = { + .cover = cover, + .walk = walk, + .ctx = args, + }; + + fib_node_list_walk(mfed->mfd_list, + mfib_entry_cover_walk_node_ptr, + &ctx); +} + +static int +mfib_entry_cover_change_one (mfib_entry_t *cover, + fib_node_index_t covered, + void *args) +{ + fib_node_index_t new_cover; + + /* + * The 3 entries involved here are: + * cover - the least specific. It will cover both the others + * new_cover - the enty just inserted below the cover + * covered - the entry that was tracking the cover. + * + * The checks below are to determine if new_cover is a cover for covered. + */ + new_cover = pointer_to_uword(args); + + if (FIB_NODE_INDEX_INVALID == new_cover) + { + /* + * nothing has been inserted, which implies the cover was removed. + * 'cover' is thus the new cover. + */ + mfib_entry_cover_changed(covered); + } + else if (new_cover != covered) + { + const mfib_prefix_t *pfx_covered, *pfx_new_cover; + + pfx_covered = mfib_entry_get_prefix(covered); + pfx_new_cover = mfib_entry_get_prefix(new_cover); + + if (mfib_prefix_is_cover(pfx_new_cover, pfx_covered)) + { + mfib_entry_cover_changed(covered); + } + } + /* continue */ + return (1); +} + +void +mfib_entry_cover_change_notify (fib_node_index_t cover_index, + fib_node_index_t covered) +{ + mfib_entry_t *cover; + + cover = mfib_entry_get(cover_index); + + mfib_entry_cover_walk(cover, + mfib_entry_cover_change_one, + uword_to_pointer(covered, void*)); +} + +static int +mfib_entry_cover_update_one (mfib_entry_t *cover, + fib_node_index_t covered, + void *args) +{ + mfib_entry_cover_updated(covered); + + /* continue */ + return (1); +} + +void +mfib_entry_cover_update_notify (mfib_entry_t *mfib_entry) +{ + mfib_entry_cover_walk(mfib_entry, + mfib_entry_cover_update_one, + NULL); +} diff --git a/src/vnet/mfib/mfib_entry_cover.h b/src/vnet/mfib/mfib_entry_cover.h new file mode 100644 index 00000000000..8f165c29dfd --- /dev/null +++ b/src/vnet/mfib/mfib_entry_cover.h @@ -0,0 +1,42 @@ +/* + * Copyright (c) 2018 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __MFIB_ENTRY_COVER_H__ +#define __MFIB_ENTRY_COVER_H__ + +#include <vnet/mfib/mfib_entry.h> + +/** + * callback function used when walking the covered entries + */ +typedef int (*mfib_entry_covered_walk_t)(mfib_entry_t *cover, + fib_node_index_t covered, + void *ctx); + +extern u32 mfib_entry_cover_track(mfib_entry_t *cover, + fib_node_index_t covered); + +extern void mfib_entry_cover_untrack(mfib_entry_t *cover, + u32 tracked_index); + +extern void mfib_entry_cover_walk(mfib_entry_t *cover, + mfib_entry_covered_walk_t walk, + void *ctx); + +extern void mfib_entry_cover_change_notify(fib_node_index_t cover_index, + fib_node_index_t covered_index); +extern void mfib_entry_cover_update_notify(mfib_entry_t *cover); + +#endif diff --git a/src/vnet/mfib/mfib_entry_delegate.c b/src/vnet/mfib/mfib_entry_delegate.c new file mode 100644 index 00000000000..95915cb3807 --- /dev/null +++ b/src/vnet/mfib/mfib_entry_delegate.c @@ -0,0 +1,143 @@ +/* + * Copyright (c) 2018 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <vnet/mfib/mfib_entry_delegate.h> +#include <vnet/mfib/mfib_entry.h> + +static mfib_entry_delegate_t * +mfib_entry_delegate_find_i (const mfib_entry_t *mfib_entry, + mfib_entry_delegate_type_t type, + u32 *index) +{ + mfib_entry_delegate_t *delegate; + int ii; + + ii = 0; + vec_foreach(delegate, mfib_entry->fe_delegates) + { + if (delegate->mfd_type == type) + { + if (NULL != index) + *index = ii; + + return (delegate); + } + else + { + ii++; + } + } + + return (NULL); +} + +mfib_entry_delegate_t * +mfib_entry_delegate_get (const mfib_entry_t *mfib_entry, + mfib_entry_delegate_type_t type) +{ + return (mfib_entry_delegate_find_i(mfib_entry, type, NULL)); +} + +void +mfib_entry_delegate_remove (mfib_entry_t *mfib_entry, + mfib_entry_delegate_type_t type) +{ + mfib_entry_delegate_t *fed; + u32 index = ~0; + + fed = mfib_entry_delegate_find_i(mfib_entry, type, &index); + + ASSERT(NULL != fed); + + vec_del1(mfib_entry->fe_delegates, index); +} + +static int +mfib_entry_delegate_cmp_for_sort (void * v1, + void * v2) +{ + mfib_entry_delegate_t *delegate1 = v1, *delegate2 = v2; + + return (delegate1->mfd_type - delegate2->mfd_type); +} + +static void +mfib_entry_delegate_init (mfib_entry_t *mfib_entry, + mfib_entry_delegate_type_t type) + +{ + mfib_entry_delegate_t delegate = { + .mfd_entry_index = mfib_entry_get_index(mfib_entry), + .mfd_type = type, + }; + + vec_add1(mfib_entry->fe_delegates, delegate); + vec_sort_with_function(mfib_entry->fe_delegates, + mfib_entry_delegate_cmp_for_sort); +} + +mfib_entry_delegate_t * +mfib_entry_delegate_find_or_add (mfib_entry_t *mfib_entry, + mfib_entry_delegate_type_t fdt) +{ + mfib_entry_delegate_t *delegate; + + delegate = mfib_entry_delegate_get(mfib_entry, fdt); + + if (NULL == delegate) + { + mfib_entry_delegate_init(mfib_entry, fdt); + } + + return (mfib_entry_delegate_get(mfib_entry, fdt)); +} + +/** + * typedef for printing a delegate + */ +typedef u8 * (*mfib_entry_delegate_format_t)(const mfib_entry_delegate_t *fed, + u8 *s); + +/** + * Print a delegate that represents cover tracking + */ +static u8 * +mfib_entry_delegate_fmt_covered (const mfib_entry_delegate_t *fed, + u8 *s) +{ + s = format(s, "covered:["); + s = fib_node_children_format(fed->mfd_list, s); + s = format(s, "]"); + + return (s); +} + +/** + * A delegate type to formatter map + */ +static mfib_entry_delegate_format_t fed_formatters[] = +{ + [MFIB_ENTRY_DELEGATE_COVERED] = mfib_entry_delegate_fmt_covered, +}; + +u8 * +format_mfib_entry_deletegate (u8 * s, va_list * args) +{ + mfib_entry_delegate_t *fed; + + fed = va_arg (*args, mfib_entry_delegate_t *); + + return (fed_formatters[fed->mfd_type](fed, s)); +} diff --git a/src/vnet/mfib/mfib_entry_delegate.h b/src/vnet/mfib/mfib_entry_delegate.h new file mode 100644 index 00000000000..0454a0f157a --- /dev/null +++ b/src/vnet/mfib/mfib_entry_delegate.h @@ -0,0 +1,90 @@ +/* + * Copyright (c) 2018 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __MFIB_ENTRY_DELEGATE_T__ +#define __MFIB_ENTRY_DELEGATE_T__ + +#include <vnet/fib/fib_node.h> + +/** + * Delegate types + */ +typedef enum mfib_entry_delegate_type_t_ { + /** + * Dependency list of covered entries. + * these are more specific entries that are interested in changes + * to their respective cover + */ + MFIB_ENTRY_DELEGATE_COVERED, +} mfib_entry_delegate_type_t; + +#define FOR_EACH_MFIB_DELEGATE(_entry, _fdt, _fed, _body) \ +{ \ + for (_fdt = MFIB_ENTRY_DELEGATE_CHAIN_UNICAST_IP4; \ + _fdt <= MFIB_ENTRY_DELEGATE_ATTACHED_EXPORT; \ + _fdt++) \ + { \ + _fed = mfib_entry_delegate_get(_entry, _fdt); \ + if (NULL != _fed) { \ + _body; \ + } \ + } \ +} + +/** + * A Delagate is a means to implmenet the Delagation design pattern; the extension of an + * objects functionality through the composition of, and delgation to, other objects. + * These 'other' objects are delegates. Delagates are thus attached to other MFIB objects + * to extend their functionality. + */ +typedef struct mfib_entry_delegate_t_ +{ + /** + * The MFIB entry object to which the delagate is attached + */ + fib_node_index_t mfd_entry_index; + + /** + * The delagate type + */ + mfib_entry_delegate_type_t mfd_type; + + /** + * A union of data for the different delegate types + * These delegates are stored in a sparse vector on the entry, so they + * must all be of the same size. + */ + union + { + /** + * For the cover tracking. The node list; + */ + fib_node_list_t mfd_list; + }; +} mfib_entry_delegate_t; + +struct mfib_entry_t_; + +extern void mfib_entry_delegate_remove(struct mfib_entry_t_ *mfib_entry, + mfib_entry_delegate_type_t type); + +extern mfib_entry_delegate_t *mfib_entry_delegate_find_or_add(struct mfib_entry_t_ *mfib_entry, + mfib_entry_delegate_type_t fdt); +extern mfib_entry_delegate_t *mfib_entry_delegate_get(const struct mfib_entry_t_ *mfib_entry, + mfib_entry_delegate_type_t type); + +extern u8 *format_mfib_entry_deletegate(u8 * s, va_list * args); + +#endif diff --git a/src/vnet/mfib/mfib_entry_src.c b/src/vnet/mfib/mfib_entry_src.c new file mode 100644 index 00000000000..ca5c788a546 --- /dev/null +++ b/src/vnet/mfib/mfib_entry_src.c @@ -0,0 +1,101 @@ +/* + * Copyright (c) 2018 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +#include <vnet/mfib/mfib_entry_src.h> + +static mfib_entry_src_vft mfib_entry_src_vfts[MFIB_N_SOURCES]; + +static void +mfib_entry_src_default_deactiviate (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ +} + +static void +mfib_entry_src_default_activiate (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ +} + +static mfib_src_res_t +mfib_entry_src_default_cover_change (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + return (MFIB_SRC_OK); +} + +static mfib_src_res_t +mfib_entry_src_default_cover_update (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + return (MFIB_SRC_OK); +} + +void +mfib_entry_src_register (mfib_source_t source, + const mfib_entry_src_vft *mvft) +{ + mfib_entry_src_vfts[source] = *mvft; +} + +void +mfib_entry_src_deactivate (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + if (NULL != msrc) + mfib_entry_src_vfts[msrc->mfes_src].mev_deactivate(mfib_entry, msrc); +} + +void +mfib_entry_src_activate (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + if (NULL != msrc) + mfib_entry_src_vfts[msrc->mfes_src].mev_activate(mfib_entry, msrc); +} + +mfib_src_res_t +mfib_entry_src_cover_change (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + return (mfib_entry_src_vfts[msrc->mfes_src].mev_cover_change(mfib_entry, msrc)); +} + +mfib_src_res_t +mfib_entry_src_cover_update (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + return (mfib_entry_src_vfts[msrc->mfes_src].mev_cover_update(mfib_entry, msrc)); +} + +void +mfib_entry_src_module_init (void) +{ + mfib_entry_src_vft mvft = { + .mev_activate = mfib_entry_src_default_activiate, + .mev_deactivate = mfib_entry_src_default_deactiviate, + .mev_cover_change = mfib_entry_src_default_cover_change, + .mev_cover_update = mfib_entry_src_default_cover_update, + }; + mfib_source_t source; + + FOREACH_MFIB_SOURCE(source) + { + mfib_entry_src_register(source, &mvft); + } + + mfib_entry_src_rr_module_init(); +} diff --git a/src/vnet/mfib/mfib_entry_src.h b/src/vnet/mfib/mfib_entry_src.h new file mode 100644 index 00000000000..86752e071ec --- /dev/null +++ b/src/vnet/mfib/mfib_entry_src.h @@ -0,0 +1,142 @@ +/* + * Copyright (c) 2018 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __MFIB_ENTRY_SRC_H__ +#define __MFIB_ENTRY_SRC_H__ + +#include <vnet/mfib/mfib_entry.h> + +/** + * MFIB extensions to each path + */ +typedef struct mfib_path_ext_t_ +{ + mfib_itf_flags_t mfpe_flags; + fib_node_index_t mfpe_path; +} mfib_path_ext_t; + +/** + * The source of an MFIB entry + */ +typedef struct mfib_entry_src_t_ +{ + /** + * Which source this is + */ + mfib_source_t mfes_src; + + /** + * Route flags + */ + mfib_entry_flags_t mfes_flags; + + /** + * The reference count on the entry. this is a u32 + * since there is no path-list sharing in mfib, so the number + * os children could be high. + */ + u32 mfes_ref_count; + + /** + * The path-list of forwarding interfaces + */ + fib_node_index_t mfes_pl; + + /** + * RPF-ID + */ + fib_rpf_id_t mfes_rpf_id; + + /** + * Hash table of path extensions + */ + mfib_path_ext_t *mfes_exts; + + /** + * Covering entry (if needed) + */ + struct { + fib_node_index_t mfes_cover; + u32 mfes_sibling; + }; + + /** + * The hash table of all interfaces. + * This is forwarding time information derived from the paths + * and their extensions. + */ + mfib_itf_t *mfes_itfs; +} mfib_entry_src_t; + +/** + * signals from the sources to the caller + */ +typedef enum mfib_src_res_t_ +{ + MFIB_SRC_OK, + MFIB_SRC_REEVALUATE, +} mfib_src_res_t; + +/** + * A function provided by each source to be invoked when it is activated + */ +typedef void (*mfib_entry_src_activiate_t) (mfib_entry_t*, mfib_entry_src_t*); + +/** + * A function provided by each source to be invoked when it is deactivated + */ +typedef void (*mfib_entry_src_deactiviate_t) (mfib_entry_t*, mfib_entry_src_t*); + +/** + * A function provided by each source to be invoked when the cover changes + */ +typedef mfib_src_res_t (*mfib_entry_src_cover_change_t) (mfib_entry_t*, mfib_entry_src_t*); + +/** + * A function provided by each source to be invoked when the cover is updated + */ +typedef mfib_src_res_t (*mfib_entry_src_cover_update_t) (mfib_entry_t*, mfib_entry_src_t*); + +/** + * Virtual function table provided by each_source + */ +typedef struct mfib_entry_src_vft_t_ +{ + mfib_entry_src_activiate_t mev_activate; + mfib_entry_src_deactiviate_t mev_deactivate; + mfib_entry_src_cover_change_t mev_cover_change; + mfib_entry_src_cover_update_t mev_cover_update; +} mfib_entry_src_vft; + +extern void mfib_entry_src_register(mfib_source_t, const mfib_entry_src_vft*); + +extern void mfib_entry_src_deactivate(mfib_entry_t *mfib_entry, + mfib_entry_src_t *bsrc); + +extern void mfib_entry_src_activate(mfib_entry_t *mfib_entry, + mfib_entry_src_t *bsrc); + +extern mfib_src_res_t mfib_entry_src_cover_change(mfib_entry_t *mfib_entry, + mfib_entry_src_t *bsrc); + +extern mfib_src_res_t mfib_entry_src_cover_update(mfib_entry_t *mfib_entry, + mfib_entry_src_t *bsrc); + +extern mfib_entry_src_t* mfib_entry_get_best_src(const mfib_entry_t *mfib_entry); + +extern void mfib_entry_src_module_init(void); +extern void mfib_entry_src_rr_module_init(void); + +#endif diff --git a/src/vnet/mfib/mfib_entry_src_rr.c b/src/vnet/mfib/mfib_entry_src_rr.c new file mode 100644 index 00000000000..4512f74a9f5 --- /dev/null +++ b/src/vnet/mfib/mfib_entry_src_rr.c @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2018 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +#include <vnet/mfib/mfib_entry_src.h> +#include <vnet/mfib/mfib_entry_cover.h> +#include <vnet/mfib/mfib_table.h> +#include <vnet/fib/fib_path_list.h> + +static void +mfib_entry_src_rr_deactiviate (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + mfib_entry_t *cover; + + /* + * remove the depednecy on the covering entry + */ + if (FIB_NODE_INDEX_INVALID != msrc->mfes_cover) + { + cover = mfib_entry_get(msrc->mfes_cover); + mfib_entry_cover_untrack(cover, msrc->mfes_sibling); + msrc->mfes_cover = FIB_NODE_INDEX_INVALID; + } + + fib_path_list_unlock(msrc->mfes_pl); + msrc->mfes_pl = FIB_NODE_INDEX_INVALID; + msrc->mfes_itfs = NULL; + msrc->mfes_exts = NULL; +} + +static void +mfib_entry_src_rr_activiate (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + mfib_entry_src_t *csrc; + mfib_entry_t *cover; + + msrc->mfes_cover = mfib_table_get_less_specific(mfib_entry->mfe_fib_index, + &mfib_entry->mfe_prefix); + + ASSERT(FIB_NODE_INDEX_INVALID != msrc->mfes_cover); + + cover = mfib_entry_get(msrc->mfes_cover); + + msrc->mfes_sibling = + mfib_entry_cover_track(cover, mfib_entry_get_index(mfib_entry)); + + csrc = mfib_entry_get_best_src(cover); + + msrc->mfes_pl = csrc->mfes_pl; + fib_path_list_lock(msrc->mfes_pl); + msrc->mfes_flags = csrc->mfes_flags; + msrc->mfes_itfs = csrc->mfes_itfs; + msrc->mfes_exts = csrc->mfes_exts; + msrc->mfes_rpf_id = csrc->mfes_rpf_id; +} + +static mfib_src_res_t +mfib_entry_src_rr_cover_change (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + mfib_entry_src_rr_deactiviate(mfib_entry, msrc); + mfib_entry_src_rr_activiate(mfib_entry, msrc); + + return (MFIB_SRC_REEVALUATE); +} + +static mfib_src_res_t +mfib_entry_src_rr_cover_update (mfib_entry_t *mfib_entry, + mfib_entry_src_t *msrc) +{ + /* + * path lists are updated (i.e. not shared) in the mfib world, + * so there's no need to check for a new one. but we do need to + * copy down any new flags and input interfaces + */ + mfib_entry_t *cover; + + cover = mfib_entry_get(msrc->mfes_cover); + + msrc->mfes_flags = cover->mfe_flags; + msrc->mfes_itfs = cover->mfe_itfs; + msrc->mfes_rpf_id = cover->mfe_rpf_id; + + return (MFIB_SRC_REEVALUATE); +} + +void +mfib_entry_src_rr_module_init (void) +{ + mfib_entry_src_vft mvft = { + .mev_activate = mfib_entry_src_rr_activiate, + .mev_deactivate = mfib_entry_src_rr_deactiviate, + .mev_cover_change = mfib_entry_src_rr_cover_change, + .mev_cover_update = mfib_entry_src_rr_cover_update, + }; + + mfib_entry_src_register(MFIB_SOURCE_RR, &mvft); +} diff --git a/src/vnet/mfib/mfib_table.c b/src/vnet/mfib/mfib_table.c index 82431e370ee..8ae4a784684 100644 --- a/src/vnet/mfib/mfib_table.c +++ b/src/vnet/mfib/mfib_table.c @@ -20,6 +20,8 @@ #include <vnet/mfib/ip4_mfib.h> #include <vnet/mfib/ip6_mfib.h> #include <vnet/mfib/mfib_entry.h> +#include <vnet/mfib/mfib_entry_src.h> +#include <vnet/mfib/mfib_entry_cover.h> #include <vnet/mfib/mfib_signal.h> mfib_table_t * @@ -99,10 +101,41 @@ mfib_table_lookup_exact_match (u32 fib_index, prefix)); } +static fib_node_index_t +mfib_table_get_less_specific_i (const mfib_table_t *mfib_table, + const mfib_prefix_t *prefix) +{ + switch (prefix->fp_proto) + { + case FIB_PROTOCOL_IP4: + return (ip4_mfib_table_get_less_specific(&mfib_table->v4, + &prefix->fp_src_addr.ip4, + &prefix->fp_grp_addr.ip4, + prefix->fp_len)); + case FIB_PROTOCOL_IP6: + return (ip6_mfib_table_get_less_specific(&mfib_table->v6, + &prefix->fp_src_addr.ip6, + &prefix->fp_grp_addr.ip6, + prefix->fp_len)); + case FIB_PROTOCOL_MPLS: + break; + } + return (FIB_NODE_INDEX_INVALID); +} + +fib_node_index_t +mfib_table_get_less_specific (u32 fib_index, + const mfib_prefix_t *prefix) +{ + return (mfib_table_get_less_specific_i(mfib_table_get(fib_index, + prefix->fp_proto), + prefix)); +} + static void mfib_table_entry_remove (mfib_table_t *mfib_table, const mfib_prefix_t *prefix, - fib_node_index_t fib_entry_index) + fib_node_index_t mfib_entry_index) { vlib_smp_unsafe_warning(); @@ -127,10 +160,45 @@ mfib_table_entry_remove (mfib_table_t *mfib_table, break; } - mfib_entry_unlock(fib_entry_index); + mfib_entry_cover_change_notify(mfib_entry_index, + FIB_NODE_INDEX_INVALID); + mfib_entry_unlock(mfib_entry_index); } static void +mfib_table_post_insert_actions (mfib_table_t *mfib_table, + const mfib_prefix_t *prefix, + fib_node_index_t mfib_entry_index) +{ + fib_node_index_t mfib_entry_cover_index; + + /* + * find the covering entry + */ + mfib_entry_cover_index = mfib_table_get_less_specific_i(mfib_table, + prefix); + /* + * the indicies are the same when the default route is first added + */ + if (mfib_entry_cover_index != mfib_entry_index) + { + /* + * inform the covering entry that a new more specific + * has been inserted beneath it. + * If the prefix that has been inserted is a host route + * then it is not possible that it will be the cover for any + * other entry, so we can elide the walk. + */ + if (!mfib_entry_is_host(mfib_entry_index)) + { + mfib_entry_cover_change_notify(mfib_entry_cover_index, + mfib_entry_index); + } + } +} + + +static void mfib_table_entry_insert (mfib_table_t *mfib_table, const mfib_prefix_t *prefix, fib_node_index_t mfib_entry_index) @@ -159,6 +227,8 @@ mfib_table_entry_insert (mfib_table_t *mfib_table, case FIB_PROTOCOL_MPLS: break; } + + mfib_table_post_insert_actions(mfib_table, prefix, mfib_entry_index); } fib_node_index_t @@ -183,7 +253,8 @@ mfib_table_entry_update (u32 fib_index, */ mfib_entry_index = mfib_entry_create(fib_index, source, prefix, rpf_id, - entry_flags); + entry_flags, + INDEX_INVALID); mfib_table_entry_insert(mfib_table, prefix, mfib_entry_index); } @@ -234,16 +305,23 @@ mfib_table_entry_path_update (u32 fib_index, source, prefix, MFIB_RPF_ID_NONE, - MFIB_ENTRY_FLAG_NONE); + MFIB_ENTRY_FLAG_NONE, + INDEX_INVALID); + + mfib_entry_path_update(mfib_entry_index, + source, + rpath, + itf_flags); mfib_table_entry_insert(mfib_table, prefix, mfib_entry_index); } - - mfib_entry_path_update(mfib_entry_index, - source, - rpath, - itf_flags); - + else + { + mfib_entry_path_update(mfib_entry_index, + source, + rpath, + itf_flags); + } return (mfib_entry_index); } @@ -295,7 +373,7 @@ mfib_table_entry_special_add (u32 fib_index, const mfib_prefix_t *prefix, mfib_source_t source, mfib_entry_flags_t entry_flags, - index_t rep_dpo) + index_t repi) { fib_node_index_t mfib_entry_index; mfib_table_t *mfib_table; @@ -303,21 +381,27 @@ mfib_table_entry_special_add (u32 fib_index, mfib_table = mfib_table_get(fib_index, prefix->fp_proto); mfib_entry_index = mfib_table_lookup_exact_match_i(mfib_table, prefix); + if (INDEX_INVALID != repi) + { + entry_flags |= MFIB_ENTRY_FLAG_EXCLUSIVE; + } + if (FIB_NODE_INDEX_INVALID == mfib_entry_index) { mfib_entry_index = mfib_entry_create(fib_index, source, prefix, MFIB_RPF_ID_NONE, - MFIB_ENTRY_FLAG_NONE); + entry_flags, + repi); mfib_table_entry_insert(mfib_table, prefix, mfib_entry_index); } - - mfib_entry_update(mfib_entry_index, source, - (MFIB_ENTRY_FLAG_EXCLUSIVE | entry_flags), - MFIB_RPF_ID_NONE, - rep_dpo); + else + { + mfib_entry_special_add(mfib_entry_index, source, entry_flags, + MFIB_RPF_ID_NONE, repi); + } return (mfib_entry_index); } @@ -380,12 +464,12 @@ void mfib_table_entry_delete_index (fib_node_index_t mfib_entry_index, mfib_source_t source) { - mfib_prefix_t prefix; + const mfib_prefix_t *prefix; - mfib_entry_get_prefix(mfib_entry_index, &prefix); + prefix = mfib_entry_get_prefix(mfib_entry_index); mfib_table_entry_delete_i(mfib_entry_get_fib_index(mfib_entry_index), - mfib_entry_index, &prefix, source); + mfib_entry_index, prefix, source); } u32 @@ -595,6 +679,17 @@ mfib_table_lock (u32 fib_index, mfib_table->mft_locks[MFIB_TABLE_TOTAL_LOCKS]++; } +u32 +mfib_table_get_n_routes (fib_node_index_t fib_index, + fib_protocol_t proto) +{ + mfib_table_t *mfib_table; + + mfib_table = mfib_table_get(fib_index, proto); + + return (mfib_table->mft_total_route_counts); +} + void mfib_table_walk (u32 fib_index, fib_protocol_t proto, @@ -642,6 +737,7 @@ mfib_module_init (vlib_main_t * vm) { clib_error_t * error; + mfib_entry_src_module_init(); mfib_entry_module_init(); mfib_signal_module_init(); diff --git a/src/vnet/mfib/mfib_table.h b/src/vnet/mfib/mfib_table.h index b8ade8b5cd9..89f194f254e 100644 --- a/src/vnet/mfib/mfib_table.h +++ b/src/vnet/mfib/mfib_table.h @@ -405,6 +405,22 @@ extern u32 mfib_table_get_num_entries(u32 fib_index, /** * @brief + * Get the less specific (covering) prefix + * + * @param fib_index + * The index of the FIB + * + * @param prefix + * The prefix to lookup + * + * @return + * The index of the less specific fib_entry_t. + */ +extern fib_node_index_t mfib_table_get_less_specific(u32 fib_index, + const mfib_prefix_t *prefix); + +/** + * @brief * Get a pointer to a FIB table */ extern mfib_table_t *mfib_table_get(fib_node_index_t index, @@ -430,4 +446,11 @@ extern void mfib_table_walk(u32 fib_index, */ extern u8 * format_mfib_table_memory(u8 * s, va_list * args); +/** + * To assit UT + */ +extern u32 mfib_table_get_n_routes(fib_node_index_t index, + fib_protocol_t proto); + + #endif diff --git a/src/vnet/mfib/mfib_types.c b/src/vnet/mfib/mfib_types.c index a3ed46a4b8d..19583ea18f4 100644 --- a/src/vnet/mfib/mfib_types.c +++ b/src/vnet/mfib/mfib_types.c @@ -26,6 +26,82 @@ static const char *mfib_flag_names_long[] = MFIB_ENTRY_NAMES_LONG; static const char *mfib_itf_flag_long_names[] = MFIB_ITF_NAMES_LONG; static const char *mfib_itf_flag_names[] = MFIB_ITF_NAMES_SHORT; +int +mfib_prefix_is_cover (const mfib_prefix_t *p1, + const mfib_prefix_t *p2) +{ + if (!ip46_address_is_equal(&p1->fp_src_addr, &p2->fp_src_addr)) + return (0); + + switch (p1->fp_proto) + { + case FIB_PROTOCOL_IP4: + return (ip4_destination_matches_route(&ip4_main, + &p1->fp_grp_addr.ip4, + &p2->fp_grp_addr.ip4, + p1->fp_len)); + case FIB_PROTOCOL_IP6: + return (ip6_destination_matches_route(&ip6_main, + &p1->fp_grp_addr.ip6, + &p2->fp_grp_addr.ip6, + p1->fp_len)); + case FIB_PROTOCOL_MPLS: + break; + } + return (0); +} + +int +mfib_prefix_is_host (const mfib_prefix_t *pfx) +{ + switch (pfx->fp_proto) + { + case FIB_PROTOCOL_IP4: + return (64 == pfx->fp_len); + case FIB_PROTOCOL_IP6: + return (256 == pfx->fp_len); + case FIB_PROTOCOL_MPLS: + ASSERT(0); + break; + } + return (0); +} + +fib_forward_chain_type_t +mfib_forw_chain_type_from_dpo_proto (dpo_proto_t proto) +{ + switch (proto) + { + case DPO_PROTO_IP4: + return (FIB_FORW_CHAIN_TYPE_MCAST_IP4); + case DPO_PROTO_IP6: + return (FIB_FORW_CHAIN_TYPE_MCAST_IP6); + case DPO_PROTO_MPLS: + case DPO_PROTO_ETHERNET: + case DPO_PROTO_NSH: + case DPO_PROTO_BIER: + break; + } + ASSERT(0); + return (FIB_FORW_CHAIN_TYPE_MCAST_IP4); +} + +fib_forward_chain_type_t +mfib_forw_chain_type_from_fib_proto (fib_protocol_t proto) +{ + switch (proto) + { + case FIB_PROTOCOL_IP4: + return (FIB_FORW_CHAIN_TYPE_MCAST_IP4); + case FIB_PROTOCOL_IP6: + return (FIB_FORW_CHAIN_TYPE_MCAST_IP6); + case FIB_PROTOCOL_MPLS: + break; + } + ASSERT(0); + return (FIB_FORW_CHAIN_TYPE_MCAST_IP4); +} + u8 * format_mfib_prefix (u8 * s, va_list * args) { diff --git a/src/vnet/mfib/mfib_types.h b/src/vnet/mfib/mfib_types.h index 58b7c987ab7..aea4a768a0b 100644 --- a/src/vnet/mfib/mfib_types.h +++ b/src/vnet/mfib/mfib_types.h @@ -169,10 +169,10 @@ typedef enum mfib_source_t_ MFIB_SOURCE_SRv6, MFIB_SOURCE_GTPU, MFIB_SOURCE_VXLAN_GPE, - MFIB_SOURCE_RR, MFIB_SOURCE_GENEVE, MFIB_SOURCE_IGMP, MFIB_SOURCE_VXLAN_GBP, + MFIB_SOURCE_RR, MFIB_SOURCE_DEFAULT_ROUTE, } mfib_source_t; @@ -186,14 +186,20 @@ typedef enum mfib_source_t_ [MFIB_SOURCE_SRv6] = "SRv6", \ [MFIB_SOURCE_GTPU] = "GTPU", \ [MFIB_SOURCE_VXLAN_GPE] = "VXLAN-GPE", \ - [MFIB_SOURCE_RR] = "Recursive-resolution", \ [MFIB_SOURCE_GENEVE] = "Geneve", \ [MFIB_SOURCE_IGMP] = "IGMP", \ [MFIB_SOURCE_VXLAN_GBP] = "VXLAN-GBP", \ + [MFIB_SOURCE_RR] = "Recursive-resolution", \ [MFIB_SOURCE_DEFAULT_ROUTE] = "Default Route", \ } -#define MFIB_N_SOURCES (MFIB_SOURCE_DEFAULT_ROUTE) +#define FOREACH_MFIB_SOURCE(_ms) \ + for (_ms = MFIB_SOURCE_SPECIAL; \ + _ms <= MFIB_SOURCE_DEFAULT_ROUTE; \ + _ms++) + +#define MFIB_N_SOURCES (MFIB_SOURCE_DEFAULT_ROUTE + 1) +#define MFIB_SOURCE_NONE (MFIB_SOURCE_DEFAULT_ROUTE + 1) /** * \brief Compare two prefixes for equality @@ -209,5 +215,20 @@ extern uword unformat_mfib_itf_flags(unformat_input_t * input, va_list * args); extern uword unformat_mfib_entry_flags(unformat_input_t * input, va_list * args); +/** + * \brief Compare two prefixes for covering relationship + * + * \return non-zero if the first prefix is a cover for the second + */ +extern int mfib_prefix_is_cover(const mfib_prefix_t *p1, + const mfib_prefix_t *p2); + +/** + * \brief Return true is the prefix is a host prefix + */ +extern int mfib_prefix_is_host(const mfib_prefix_t *p); + +extern fib_forward_chain_type_t mfib_forw_chain_type_from_dpo_proto(dpo_proto_t proto); +extern fib_forward_chain_type_t mfib_forw_chain_type_from_fib_proto(fib_protocol_t proto); #endif |