From: Neale Ranns Date: Thu, 6 Apr 2017 11:41:02 +0000 (-0700) Subject: FIB Inherited Srouce X-Git-Tag: v18.04-rc1~473 X-Git-Url: https://gerrit.fd.io/r/gitweb?p=vpp.git;a=commitdiff_plain;h=89541992000433b743cbbe8cb396faab42bcf6ae FIB Inherited Srouce forwarding provided by the source is pushed to all other entries it covers in the sub-tree Change-Id: I2a45222ef653358f55c2436de3e3c6353cfadba2 Signed-off-by: Neale Ranns --- diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c index 35716cacc29..fed42129cff 100644 --- a/src/vnet/fib/fib_entry.c +++ b/src/vnet/fib/fib_entry.c @@ -34,6 +34,7 @@ */ static const char *fib_source_names[] = FIB_SOURCES; static const char *fib_attribute_names[] = FIB_ENTRY_ATTRIBUTES; +static const char *fib_src_attribute_names[] = FIB_ENTRY_SRC_ATTRIBUTES; /* * Pool for all fib_entries @@ -102,6 +103,7 @@ format_fib_source (u8 * s, va_list * args) u8 * format_fib_entry (u8 * s, va_list * args) { + fib_entry_src_attribute_t sattr; fib_forward_chain_type_t fct; fib_entry_attribute_t attr; fib_entry_t *fib_entry; @@ -126,15 +128,23 @@ format_fib_entry (u8 * s, va_list * args) ({ s = format (s, "\n %U", format_fib_source, source); s = fib_entry_src_format(fib_entry, source, s); - s = format (s, " refs:%d ", src->fes_ref_count); + s = format (s, " refs:%d", src->fes_ref_count); if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) { - s = format(s, "flags:"); + s = format(s, " entry-flags:"); FOR_EACH_FIB_ATTRIBUTE(attr) { if ((1<fes_entry_flags) { s = format (s, "%s,", fib_attribute_names[attr]); } } } + if (FIB_ENTRY_SRC_FLAG_NONE != src->fes_flags) { + s = format(s, " src-flags:"); + FOR_EACH_FIB_SRC_ATTRIBUTE(sattr) { + if ((1<fes_flags) { + s = format (s, "%s,", fib_src_attribute_names[sattr]); + } + } + } s = format (s, "\n"); if (FIB_NODE_INDEX_INVALID != src->fes_pl) { @@ -584,7 +594,6 @@ fib_entry_alloc (u32 fib_index, static fib_entry_t* fib_entry_post_flag_update_actions (fib_entry_t *fib_entry, - fib_source_t source, fib_entry_flag_t old_flags) { fib_node_index_t fei; @@ -658,7 +667,6 @@ fib_entry_post_install_actions (fib_entry_t *fib_entry, fib_entry_flag_t old_flags) { fib_entry = fib_entry_post_flag_update_actions(fib_entry, - source, old_flags); fib_entry_src_action_installed(fib_entry, source); } @@ -748,26 +756,25 @@ fib_entry_post_update_actions (fib_entry_t *fib_entry, fib_entry_post_install_actions(fib_entry, source, old_flags); } -static void +void fib_entry_source_change (fib_entry_t *fib_entry, - fib_source_t best_source, - fib_source_t new_source, - fib_entry_flag_t old_flags) + fib_source_t old_source, + fib_source_t new_source) { - /* - * if the path list for the source passed is invalid, - * then we need to create a new one. else we are updating - * an existing. - */ - if (new_source < best_source) + fib_entry_flag_t old_flags; + + old_flags = fib_entry_get_flags_for_source( + fib_entry_get_index(fib_entry), old_source); + + if (new_source < old_source) { /* * we have a new winning source. */ - fib_entry_src_action_deactivate(fib_entry, best_source); + fib_entry_src_action_deactivate(fib_entry, old_source); fib_entry_src_action_activate(fib_entry, new_source); } - else if (new_source > best_source) + else if (new_source > old_source) { /* * the new source loses. nothing to do here. @@ -782,8 +789,7 @@ fib_entry_source_change (fib_entry_t *fib_entry, * But the path-list was updated, which will contribute new forwarding, * so install it. */ - fib_entry_src_action_deactivate(fib_entry, new_source); - fib_entry_src_action_activate(fib_entry, new_source); + fib_entry_src_action_reactivate(fib_entry, new_source); } fib_entry_post_update_actions(fib_entry, new_source, old_flags); @@ -796,18 +802,13 @@ fib_entry_special_add (fib_node_index_t fib_entry_index, const dpo_id_t *dpo) { fib_source_t best_source; - fib_entry_flag_t bflags; fib_entry_t *fib_entry; - fib_entry_src_t *bsrc; fib_entry = fib_entry_get(fib_entry_index); - - bsrc = fib_entry_get_best_src_i(fib_entry); - best_source = fib_entry_src_get_source(bsrc); - bflags = fib_entry_src_get_flags(bsrc); + best_source = fib_entry_get_best_source(fib_entry_index); fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo); - fib_entry_source_change(fib_entry, best_source, source, bflags); + fib_entry_source_change(fib_entry, best_source, source); } void @@ -817,18 +818,13 @@ fib_entry_special_update (fib_node_index_t fib_entry_index, const dpo_id_t *dpo) { fib_source_t best_source; - fib_entry_flag_t bflags; fib_entry_t *fib_entry; - fib_entry_src_t *bsrc; fib_entry = fib_entry_get(fib_entry_index); - - bsrc = fib_entry_get_best_src_i(fib_entry); - best_source = fib_entry_src_get_source(bsrc); - bflags = fib_entry_src_get_flags(bsrc); + best_source = fib_entry_get_best_source(fib_entry_index); fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo); - fib_entry_source_change(fib_entry, best_source, source, bflags); + fib_entry_source_change(fib_entry, best_source, source); } @@ -882,13 +878,78 @@ fib_entry_path_add (fib_node_index_t fib_entry_index, * But the path-list was updated, which will contribute new forwarding, * so install it. */ - fib_entry_src_action_deactivate(fib_entry, source); - fib_entry_src_action_activate(fib_entry, source); + fib_entry_src_action_reactivate(fib_entry, source); } fib_entry_post_update_actions(fib_entry, source, bflags); } +static fib_entry_src_flag_t +fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry) +{ + fib_entry_src_t *src; + fib_source_t source; + int has_only_inherited_sources = 1; + + FOR_EACH_SRC_ADDED(fib_entry, src, source, + ({ + if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)) + { + has_only_inherited_sources = 0; + break; + } + })); + if (has_only_inherited_sources) + { + FOR_EACH_SRC_ADDED(fib_entry, src, source, + ({ + fib_entry_src_action_remove(fib_entry, source); + })); + return (FIB_ENTRY_SRC_FLAG_NONE); + } + else + { + return (FIB_ENTRY_SRC_FLAG_ADDED); + } +} + +static fib_entry_src_flag_t +fib_entry_source_removed (fib_entry_t *fib_entry, + fib_entry_flag_t old_flags) +{ + const fib_entry_src_t *bsrc; + fib_source_t best_source; + + /* + * if all that is left are inherited sources, then burn them + */ + fib_entry_src_burn_only_inherited(fib_entry); + + bsrc = fib_entry_get_best_src_i(fib_entry); + best_source = fib_entry_src_get_source(bsrc); + + if (FIB_SOURCE_MAX == best_source) { + /* + * no more sources left. this entry is toast. + */ + fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags); + fib_entry_src_action_uninstall(fib_entry); + + return (FIB_ENTRY_SRC_FLAG_NONE); + } + else + { + fib_entry_src_action_activate(fib_entry, best_source); + } + + fib_entry_post_update_actions(fib_entry, best_source, old_flags); + + /* + * still have sources + */ + return (FIB_ENTRY_SRC_FLAG_ADDED); +} + /* * fib_entry_path_remove * @@ -922,7 +983,7 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index, * then we need to create a new one. else we are updating * an existing. */ - if (source < best_source ) + if (source < best_source) { /* * Que! removing a path from a source that is better than the @@ -933,9 +994,23 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index, else if (source > best_source ) { /* - * the source is not the best. nothing to do. + * the source is not the best. no need to update forwarding */ - return (FIB_ENTRY_SRC_FLAG_ADDED); + if (FIB_ENTRY_SRC_FLAG_ADDED & sflag) + { + /* + * the source being removed still has paths + */ + return (FIB_ENTRY_SRC_FLAG_ADDED); + } + else + { + /* + * that was the last path from this source, check if those + * that remain are non-inherited + */ + return (fib_entry_src_burn_only_inherited(fib_entry)); + } } else { @@ -948,33 +1023,14 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index, * the last path from the source was removed. * fallback to lower source */ - bsrc = fib_entry_get_best_src_i(fib_entry); - best_source = fib_entry_src_get_source(bsrc); - - if (FIB_SOURCE_MAX == best_source) { - /* - * no more sources left. this entry is toast. - */ - fib_entry = fib_entry_post_flag_update_actions(fib_entry, - source, - bflags); - fib_entry_src_action_uninstall(fib_entry); - - return (FIB_ENTRY_SRC_FLAG_NONE); - } - else - { - fib_entry_src_action_activate(fib_entry, best_source); - source = best_source; - } + return (fib_entry_source_removed(fib_entry, bflags)); } else { /* * re-install the new forwarding information */ - fib_entry_src_action_deactivate(fib_entry, source); - fib_entry_src_action_activate(fib_entry, source); + fib_entry_src_action_reactivate(fib_entry, source); } } @@ -1009,7 +1065,7 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index, best_source = fib_entry_src_get_source(bsrc); bflags = fib_entry_src_get_flags(bsrc); - sflag = fib_entry_src_action_remove(fib_entry, source); + sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source); /* * if the path list for the source passed is invalid, @@ -1027,9 +1083,32 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index, } else if (source > best_source ) { /* - * the source is not the best. nothing to do. + * the source is not the best. no need to update forwarding */ - return (FIB_ENTRY_SRC_FLAG_ADDED); + if (FIB_ENTRY_SRC_FLAG_ADDED & sflag) + { + /* + * the source being removed still has paths + */ + return (FIB_ENTRY_SRC_FLAG_ADDED); + } + else + { + /* + * that was the last path from this source, check if those + * that remain are non-inherited + */ + if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry)) + { + /* + * no more sources left. this entry is toast. + */ + fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags); + fib_entry_src_action_uninstall(fib_entry); + return (FIB_ENTRY_SRC_FLAG_NONE); + } + return (FIB_ENTRY_SRC_FLAG_ADDED); + } } else { @@ -1038,25 +1117,7 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index, /* * the source was removed. use the next best. */ - bsrc = fib_entry_get_best_src_i(fib_entry); - best_source = fib_entry_src_get_source(bsrc); - - if (FIB_SOURCE_MAX == best_source) { - /* - * no more sources left. this entry is toast. - */ - fib_entry = fib_entry_post_flag_update_actions(fib_entry, - source, - bflags); - fib_entry_src_action_uninstall(fib_entry); - - return (FIB_ENTRY_SRC_FLAG_NONE); - } - else - { - fib_entry_src_action_activate(fib_entry, best_source); - source = best_source; - } + return (fib_entry_source_removed(fib_entry, bflags)); } else { @@ -1075,6 +1136,20 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index, return (FIB_ENTRY_SRC_FLAG_ADDED); } +/** + * fib_entry_inherit + * + * If the source on the cover is inherting then push this source + * down to the covered. + */ +void +fib_entry_inherit (fib_node_index_t cover, + fib_node_index_t covered) +{ + fib_entry_src_inherit(fib_entry_get(cover), + fib_entry_get(covered)); +} + /** * fib_entry_delete * @@ -1146,8 +1221,7 @@ fib_entry_update (fib_node_index_t fib_entry_index, * But the path-list was updated, which will contribute new forwarding, * so install it. */ - fib_entry_src_action_deactivate(fib_entry, source); - fib_entry_src_action_activate(fib_entry, source); + fib_entry_src_action_reactivate(fib_entry, source); } fib_entry_post_update_actions(fib_entry, source, bflags); diff --git a/src/vnet/fib/fib_entry.h b/src/vnet/fib/fib_entry.h index cd2a685b765..273a5e66b15 100644 --- a/src/vnet/fib/fib_entry.h +++ b/src/vnet/fib/fib_entry.h @@ -212,10 +212,15 @@ typedef enum fib_entry_attribute_t_ { * To be used with caution */ FIB_ENTRY_ATTRIBUTE_URPF_EXEMPT, + /** + * This FIB entry imposes its source information on all prefixes + * that is covers + */ + FIB_ENTRY_ATTRIBUTE_COVERED_INHERIT, /** * Marker. add new entries before this one. */ - FIB_ENTRY_ATTRIBUTE_LAST = FIB_ENTRY_ATTRIBUTE_URPF_EXEMPT, + FIB_ENTRY_ATTRIBUTE_LAST = FIB_ENTRY_ATTRIBUTE_COVERED_INHERIT, } fib_entry_attribute_t; #define FIB_ENTRY_ATTRIBUTES { \ @@ -227,6 +232,7 @@ typedef enum fib_entry_attribute_t_ { [FIB_ENTRY_ATTRIBUTE_LOCAL] = "local", \ [FIB_ENTRY_ATTRIBUTE_URPF_EXEMPT] = "uRPF-exempt", \ [FIB_ENTRY_ATTRIBUTE_MULTICAST] = "multicast", \ + [FIB_ENTRY_ATTRIBUTE_COVERED_INHERIT] = "covered-inherit", \ } #define FOR_EACH_FIB_ATTRIBUTE(_item) \ @@ -244,6 +250,7 @@ typedef enum fib_entry_flag_t_ { FIB_ENTRY_FLAG_IMPORT = (1 << FIB_ENTRY_ATTRIBUTE_IMPORT), FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT = (1 << FIB_ENTRY_ATTRIBUTE_URPF_EXEMPT), FIB_ENTRY_FLAG_MULTICAST = (1 << FIB_ENTRY_ATTRIBUTE_MULTICAST), + FIB_ENTRY_FLAG_COVERED_INHERIT = (1 << FIB_ENTRY_ATTRIBUTE_COVERED_INHERIT), } __attribute__((packed)) fib_entry_flag_t; /** @@ -262,10 +269,14 @@ typedef enum fib_entry_src_attribute_t_ { * the source is active/best */ FIB_ENTRY_SRC_ATTRIBUTE_ACTIVE, + /** + * the source is inherited from its cover + */ + FIB_ENTRY_SRC_ATTRIBUTE_INHERITED, /** * Marker. add new entries before this one. */ - FIB_ENTRY_SRC_ATTRIBUTE_LAST = FIB_ENTRY_SRC_ATTRIBUTE_ACTIVE, + FIB_ENTRY_SRC_ATTRIBUTE_LAST = FIB_ENTRY_SRC_ATTRIBUTE_INHERITED, } fib_entry_src_attribute_t; #define FIB_ENTRY_SRC_ATTRIBUTE_MAX (FIB_ENTRY_SRC_ATTRIBUTE_LAST+1) @@ -273,12 +284,19 @@ typedef enum fib_entry_src_attribute_t_ { #define FIB_ENTRY_SRC_ATTRIBUTES { \ [FIB_ENTRY_SRC_ATTRIBUTE_ADDED] = "added", \ [FIB_ENTRY_SRC_ATTRIBUTE_ACTIVE] = "active", \ + [FIB_ENTRY_SRC_ATTRIBUTE_INHERITED] = "inherited", \ } +#define FOR_EACH_FIB_SRC_ATTRIBUTE(_item) \ + for (_item = FIB_ENTRY_SRC_ATTRIBUTE_FIRST; \ + _item < FIB_ENTRY_SRC_ATTRIBUTE_MAX; \ + _item++) + typedef enum fib_entry_src_flag_t_ { FIB_ENTRY_SRC_FLAG_NONE = 0, FIB_ENTRY_SRC_FLAG_ADDED = (1 << FIB_ENTRY_SRC_ATTRIBUTE_ADDED), FIB_ENTRY_SRC_FLAG_ACTIVE = (1 << FIB_ENTRY_SRC_ATTRIBUTE_ACTIVE), + FIB_ENTRY_SRC_FLAG_INHERITED = (1 << FIB_ENTRY_SRC_ATTRIBUTE_INHERITED), } __attribute__ ((packed)) fib_entry_src_flag_t; /* @@ -477,6 +495,10 @@ extern fib_entry_src_flag_t fib_entry_special_remove(fib_node_index_t fib_entry_ extern fib_entry_src_flag_t fib_entry_path_remove(fib_node_index_t fib_entry_index, fib_source_t source, const fib_route_path_t *rpath); + +extern void fib_entry_inherit(fib_node_index_t cover, + fib_node_index_t covered); + extern fib_entry_src_flag_t fib_entry_delete(fib_node_index_t fib_entry_index, fib_source_t source); diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c index 66f5987a7cf..616d77e8b0a 100644 --- a/src/vnet/fib/fib_entry_src.c +++ b/src/vnet/fib/fib_entry_src.c @@ -108,8 +108,7 @@ fib_entry_is_sourced (fib_node_index_t fib_entry_index, static fib_entry_src_t * fib_entry_src_find_or_create (fib_entry_t *fib_entry, - fib_source_t source, - u32 *index) + fib_source_t source) { fib_entry_src_t *esrc; @@ -654,6 +653,249 @@ fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index) vec_free(entries); } +/* + * fib_entry_src_action_copy + * + * copy a source data from another entry to this one + */ +fib_entry_t * +fib_entry_src_action_copy (fib_entry_t *fib_entry, + const fib_entry_src_t *orig_src) +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find_or_create(fib_entry, orig_src->fes_src); + + *esrc = *orig_src; + esrc->fes_ref_count = 1; + esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_INHERITED; + esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE; + esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT; + + /* + * the source owns a lock on the entry + */ + fib_path_list_lock(esrc->fes_pl); + fib_entry_lock(fib_entry_get_index(fib_entry)); + + return (fib_entry); +} + +/* + * fib_entry_src_action_update + * + * copy a source data from another entry to this one + */ +static fib_entry_src_t * +fib_entry_src_action_update_from_cover (fib_entry_t *fib_entry, + const fib_entry_src_t *orig_src) +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find_or_create(fib_entry, orig_src->fes_src); + + /* + * the source owns a lock on the entry + */ + fib_path_list_unlock(esrc->fes_pl); + esrc->fes_pl = orig_src->fes_pl; + fib_path_list_lock(esrc->fes_pl); + + return (esrc); +} + +static fib_table_walk_rc_t +fib_entry_src_covered_inherit_add_i (fib_entry_t *fib_entry, + const fib_entry_src_t *cover_src) +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, cover_src->fes_src, NULL); + + if (cover_src == esrc) + { + return (FIB_TABLE_WALK_CONTINUE); + } + + if (NULL != esrc) + { + /* + * the covered entry already has this source. + */ + if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) + { + /* + * the covered source is itself a COVERED_INHERIT, i.e. + * it also pushes this source down the sub-tree. + * We consider this more specfic covered to be the owner + * of the sub-tree from this point down. + */ + return (FIB_TABLE_WALK_SUB_TREE_STOP); + } + if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED) + { + /* + * The covered's source data has been inherited, presumably + * from this cover, i.e. this is a modify. + */ + esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src); + fib_entry_source_change(fib_entry, esrc->fes_src, esrc->fes_src); + } + else + { + /* + * The covered's source was not inherited and it is also + * not inherting. Nevertheless, it still owns the sub-tree from + * this point down. + */ + return (FIB_TABLE_WALK_SUB_TREE_STOP); + } + } + else + { + /* + * The covered does not have this source - add it. + */ + fib_source_t best_source; + + best_source = fib_entry_get_best_source( + fib_entry_get_index(fib_entry)); + + fib_entry_src_action_copy(fib_entry, cover_src); + fib_entry_source_change(fib_entry, best_source, cover_src->fes_src); + + } + return (FIB_TABLE_WALK_CONTINUE); +} + +static fib_table_walk_rc_t +fib_entry_src_covered_inherit_walk_add (fib_node_index_t fei, + void *ctx) +{ + return (fib_entry_src_covered_inherit_add_i(fib_entry_get(fei), ctx)); +} + +static fib_table_walk_rc_t +fib_entry_src_covered_inherit_walk_remove (fib_node_index_t fei, + void *ctx) +{ + fib_entry_src_t *cover_src, *esrc; + fib_entry_t *fib_entry; + + fib_entry = fib_entry_get(fei); + + cover_src = ctx; + esrc = fib_entry_src_find(fib_entry, cover_src->fes_src, NULL); + + if (cover_src == esrc) + { + return (FIB_TABLE_WALK_CONTINUE); + } + + if (NULL != esrc) + { + /* + * the covered entry already has this source. + */ + if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) + { + /* + * the covered source is itself a COVERED_INHERIT, i.e. + * it also pushes this source down the sub-tree. + * We consider this more specfic covered to be the owner + * of the sub-tree from this point down. + */ + return (FIB_TABLE_WALK_SUB_TREE_STOP); + } + if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED) + { + /* + * The covered's source data has been inherited, presumably + * from this cover + */ + fib_entry_src_flag_t remaining; + + remaining = fib_entry_special_remove(fei, cover_src->fes_src); + + ASSERT(FIB_ENTRY_SRC_FLAG_ADDED == remaining); + } + else + { + /* + * The covered's source was not inherited and it is also + * not inherting. Nevertheless, it still owns the sub-tree from + * this point down. + */ + return (FIB_TABLE_WALK_SUB_TREE_STOP); + } + } + else + { + /* + * The covered does not have this source - that's an error, + * since it should have inherited, but there is nothing we can do + * about it now. + */ + } + return (FIB_TABLE_WALK_CONTINUE); +} + +void +fib_entry_src_inherit (const fib_entry_t *cover, + fib_entry_t *covered) +{ + CLIB_UNUSED(fib_source_t source); + const fib_entry_src_t *src; + + FOR_EACH_SRC_ADDED(cover, src, source, + ({ + if ((src->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) || + (src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)) + { + fib_entry_src_covered_inherit_add_i(covered, src); + } + })) +} + +static void +fib_entry_src_covered_inherit_add (fib_entry_t *fib_entry, + fib_source_t source) + +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE); + + if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) || + (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)) + { + fib_table_sub_tree_walk(fib_entry->fe_fib_index, + fib_entry->fe_prefix.fp_proto, + &fib_entry->fe_prefix, + fib_entry_src_covered_inherit_walk_add, + esrc); + } +} + +static void +fib_entry_src_covered_inherit_remove (fib_entry_t *fib_entry, + fib_entry_src_t *esrc) + +{ + ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)); + + if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) + { + fib_table_sub_tree_walk(fib_entry->fe_fib_index, + fib_entry->fe_prefix.fp_proto, + &fib_entry->fe_prefix, + fib_entry_src_covered_inherit_walk_remove, + esrc); + } +} + void fib_entry_src_action_activate (fib_entry_t *fib_entry, fib_source_t source) @@ -698,6 +940,11 @@ fib_entry_src_action_activate (fib_entry_t *fib_entry, FIB_ENTRY_DBG(fib_entry, "activate: %d", fib_entry->fe_parent); + /* + * If this source should push its state to covered prefixs, do that now. + */ + fib_entry_src_covered_inherit_add(fib_entry, source); + if (0 != houston_we_are_go_for_install) { fib_entry_src_action_install(fib_entry, source); @@ -729,6 +976,14 @@ fib_entry_src_action_deactivate (fib_entry_t *fib_entry, FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent); + /* + * If this source should pull its state from covered prefixs, do that now. + * If this source also has the INHERITED flag set then it has a cover + * that wants to push down forwarding. We only want the covereds to see + * one update. + */ + fib_entry_src_covered_inherit_remove(fib_entry, esrc); + /* * un-link from an old path-list. Check for any loops this will clear */ @@ -778,6 +1033,8 @@ fib_entry_src_action_reactivate (fib_entry_t *fib_entry, if (fib_entry->fe_parent != esrc->fes_pl) { + int remain_installed; + /* * un-link from an old path-list. Check for any loops this will clear */ @@ -811,6 +1068,30 @@ fib_entry_src_action_reactivate (fib_entry_t *fib_entry, fib_entry_recursive_loop_detect_i(fib_entry->fe_parent); fib_path_list_unlock(path_list_index); + + /* + * call the source to reactive and get the go/no-go to remain installed + */ + if (NULL != fib_entry_src_vft[source].fesv_reactivate) + { + remain_installed = + fib_entry_src_vft[source].fesv_reactivate(esrc, fib_entry); + } + else + { + remain_installed = 1; + } + + /* + * If this source should push its state to covered prefixs, do that now. + */ + fib_entry_src_covered_inherit_add(fib_entry, source); + + if (!remain_installed) + { + fib_entry_src_action_uninstall(fib_entry); + return; + } } fib_entry_src_action_install(fib_entry, source); fib_entry_src_action_fwd_update(fib_entry, source); @@ -850,7 +1131,7 @@ fib_entry_src_action_add (fib_entry_t *fib_entry, fib_node_index_t fib_entry_index; fib_entry_src_t *esrc; - esrc = fib_entry_src_find_or_create(fib_entry, source, NULL); + esrc = fib_entry_src_find_or_create(fib_entry, source); esrc->fes_ref_count++; @@ -909,10 +1190,12 @@ fib_entry_src_action_update (fib_entry_t *fib_entry, fib_node_index_t fib_entry_index, old_path_list_index; fib_entry_src_t *esrc; - esrc = fib_entry_src_find_or_create(fib_entry, source, NULL); + esrc = fib_entry_src_find_or_create(fib_entry, source); if (NULL == esrc) + { return (fib_entry_src_action_add(fib_entry, source, flags, dpo)); + } old_path_list_index = esrc->fes_pl; esrc->fes_entry_flags = flags; @@ -941,6 +1224,60 @@ fib_entry_src_action_update (fib_entry_t *fib_entry, return (fib_entry); } +fib_entry_src_flag_t +fib_entry_src_action_remove_or_update_inherit (fib_entry_t *fib_entry, + fib_source_t source) +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL == esrc) + return (FIB_ENTRY_SRC_FLAG_ACTIVE); + + if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) && + (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)) + { + fib_entry_src_t *cover_src; + fib_node_index_t coveri; + fib_entry_t *cover; + + /* + * this source was pushing inherited state, but so is its + * cover. Now that this source is going away, we need to + * pull the covers forwarding and use it to update the covereds. + * Go grab the path-list from the cover, rather than start a walk from + * the cover, so we don't recursively update this entry. + */ + coveri = fib_table_get_less_specific(fib_entry->fe_fib_index, + &fib_entry->fe_prefix); + + /* + * only the default route has itself as its own cover, but the + * default route cannot have inherited from something else. + */ + ASSERT(coveri != fib_entry_get_index(fib_entry)); + + cover = fib_entry_get(coveri); + cover_src = fib_entry_src_find(cover, source, NULL); + + ASSERT(NULL != cover_src); + + esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src); + esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT; + + /* + * Now push the new state from the cover down to the covereds + */ + fib_entry_src_covered_inherit_add(fib_entry, source); + + return (esrc->fes_flags); + } + else + { + return (fib_entry_src_action_remove(fib_entry, source)); + } +} fib_entry_src_flag_t fib_entry_src_action_remove (fib_entry_t *fib_entry, @@ -969,7 +1306,7 @@ fib_entry_src_action_remove (fib_entry_t *fib_entry, if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE) { - fib_entry_src_action_deactivate(fib_entry, source); + fib_entry_src_action_deactivate(fib_entry, source); } old_path_list = esrc->fes_pl; @@ -1185,6 +1522,10 @@ fib_entry_src_action_path_swap (fib_entry_t *fib_entry, fib_entry_get_dpo_proto(fib_entry))); esrc = fib_entry_src_find(fib_entry, source, NULL); } + else + { + esrc->fes_entry_flags = flags; + } /* * swapping paths may create a new path-list (or may use an existing shared) @@ -1258,7 +1599,7 @@ fib_entry_src_action_path_remove (fib_entry_t *fib_entry, /* * no more paths left from this source */ - fib_entry_src_action_remove(fib_entry, source); + fib_entry_src_action_remove_or_update_inherit(fib_entry, source); return (FIB_ENTRY_SRC_FLAG_NONE); } } diff --git a/src/vnet/fib/fib_entry_src.h b/src/vnet/fib/fib_entry_src.h index 35c43936a1f..57840d555ee 100644 --- a/src/vnet/fib/fib_entry_src.h +++ b/src/vnet/fib/fib_entry_src.h @@ -59,6 +59,13 @@ typedef void (*fib_entry_src_deinit_t)(fib_entry_src_t *src); typedef int (*fib_entry_src_activate_t)(fib_entry_src_t *src, const fib_entry_t *fib_entry); +/** + * Source re-activation. Called when the source is updated and remains + * the best source. + */ +typedef int (*fib_entry_src_reactivate_t)(fib_entry_src_t *src, + const fib_entry_t *fib_entry); + /** * Source Deactivate. * Called when the source is no longer best source on the entry @@ -173,6 +180,7 @@ typedef struct fib_entry_src_vft_t_ { fib_entry_src_deinit_t fesv_deinit; fib_entry_src_activate_t fesv_activate; fib_entry_src_deactivate_t fesv_deactivate; + fib_entry_src_reactivate_t fesv_reactivate; fib_entry_src_add_t fesv_add; fib_entry_src_remove_t fesv_remove; fib_entry_src_path_swap_t fesv_path_swap; @@ -240,6 +248,9 @@ extern fib_entry_t* fib_entry_src_action_update(fib_entry_t *fib_entry, extern fib_entry_src_flag_t fib_entry_src_action_remove(fib_entry_t *fib_entry, fib_source_t source); +extern fib_entry_src_flag_t +fib_entry_src_action_remove_or_update_inherit(fib_entry_t *fib_entry, + fib_source_t source); extern void fib_entry_src_action_install(fib_entry_t *fib_entry, fib_source_t source); @@ -262,10 +273,13 @@ extern fib_entry_src_flag_t fib_entry_src_action_path_remove(fib_entry_t *fib_en extern void fib_entry_src_action_installed(const fib_entry_t *fib_entry, fib_source_t source); +extern void fib_entry_src_inherit (const fib_entry_t *cover, + fib_entry_t *covered); extern fib_forward_chain_type_t fib_entry_get_default_chain_type( const fib_entry_t *fib_entry); extern fib_entry_flag_t fib_entry_get_flags_i(const fib_entry_t *fib_entry); + extern fib_path_list_flags_t fib_entry_src_flags_2_path_list_flags( fib_entry_flag_t eflags); @@ -280,6 +294,10 @@ extern void fib_entry_src_mk_lb (fib_entry_t *fib_entry, extern fib_protocol_t fib_entry_get_proto(const fib_entry_t * fib_entry); extern dpo_proto_t fib_entry_get_dpo_proto(const fib_entry_t * fib_entry); +extern void fib_entry_source_change(fib_entry_t *fib_entry, + fib_source_t old_source, + fib_source_t new_source); + /* * Per-source registration. declared here so we save a separate .h file for each */ diff --git a/src/vnet/fib/fib_entry_src_adj.c b/src/vnet/fib/fib_entry_src_adj.c index 9ea2b17e6b9..04c5c8dc1f7 100644 --- a/src/vnet/fib/fib_entry_src_adj.c +++ b/src/vnet/fib/fib_entry_src_adj.c @@ -201,10 +201,6 @@ fib_entry_src_adj_path_list_walk (fib_node_index_t pl_index, return (FIB_PATH_LIST_WALK_CONTINUE); } -/* - * Source activate. - * Called when the source is the new longer best source on the entry - */ static int fib_entry_src_adj_activate (fib_entry_src_t *src, const fib_entry_t *fib_entry) @@ -261,6 +257,28 @@ fib_entry_src_adj_activate (fib_entry_src_t *src, return (0); } +/* + * Source re-activate. + * Called when the source path lit has changed and the source is still + * the best source + */ +static int +fib_entry_src_adj_reactivate (fib_entry_src_t *src, + const fib_entry_t *fib_entry) +{ + fib_entry_src_path_list_walk_cxt_t ctx = { + .cover_itf = fib_entry_get_resolving_interface(src->adj.fesa_cover), + .flags = FIB_PATH_EXT_ADJ_FLAG_NONE, + .src = src, + }; + + fib_path_list_walk(src->fes_pl, + fib_entry_src_adj_path_list_walk, + &ctx); + + return (FIB_PATH_EXT_ADJ_FLAG_REFINES_COVER & ctx.flags); +} + /* * Source Deactivate. * Called when the source is no longer best source on the entry @@ -291,7 +309,7 @@ static u8* fib_entry_src_adj_format (fib_entry_src_t *src, u8* s) { - return (format(s, "cover:%d", src->adj.fesa_cover)); + return (format(s, " cover:%d", src->adj.fesa_cover)); } static void @@ -368,6 +386,7 @@ const static fib_entry_src_vft_t adj_src_vft = { .fesv_remove = fib_entry_src_adj_remove, .fesv_activate = fib_entry_src_adj_activate, .fesv_deactivate = fib_entry_src_adj_deactivate, + .fesv_reactivate = fib_entry_src_adj_reactivate, .fesv_format = fib_entry_src_adj_format, .fesv_installed = fib_entry_src_adj_installed, .fesv_cover_change = fib_entry_src_adj_cover_change, diff --git a/src/vnet/fib/fib_entry_src_default.c b/src/vnet/fib/fib_entry_src_default.c index 9846cf56e64..18a039afbd6 100644 --- a/src/vnet/fib/fib_entry_src_default.c +++ b/src/vnet/fib/fib_entry_src_default.c @@ -95,7 +95,7 @@ fib_entry_src_default_add (fib_entry_src_t *src, } static void -fib_entry_src_default_remove (fib_entry_src_t *src) +fib_entry_src_default_remove (fib_entry_src_t *src) { } diff --git a/src/vnet/fib/fib_entry_src_interface.c b/src/vnet/fib/fib_entry_src_interface.c index 6c087f34552..f79be72c45a 100644 --- a/src/vnet/fib/fib_entry_src_interface.c +++ b/src/vnet/fib/fib_entry_src_interface.c @@ -190,7 +190,7 @@ static u8* fib_entry_src_interface_format (fib_entry_src_t *src, u8* s) { - return (format(s, "cover:%d", src->interface.fesi_cover)); + return (format(s, " cover:%d", src->interface.fesi_cover)); } const static fib_entry_src_vft_t interface_src_vft = { diff --git a/src/vnet/fib/fib_entry_src_rr.c b/src/vnet/fib/fib_entry_src_rr.c index 1153f3f1da4..b6f4bc3ba45 100644 --- a/src/vnet/fib/fib_entry_src_rr.c +++ b/src/vnet/fib/fib_entry_src_rr.c @@ -280,7 +280,7 @@ static u8* fib_entry_src_rr_format (fib_entry_src_t *src, u8* s) { - return (format(s, "cover:%d", src->rr.fesr_cover)); + return (format(s, " cover:%d", src->rr.fesr_cover)); } const static fib_entry_src_vft_t rr_src_vft = { diff --git a/src/vnet/fib/fib_table.c b/src/vnet/fib/fib_table.c index 80e5a0fe1a0..c20bb255ddf 100644 --- a/src/vnet/fib/fib_table.c +++ b/src/vnet/fib/fib_table.c @@ -181,8 +181,7 @@ fib_table_post_insert_actions (fib_table_t *fib_table, return; /* - * find and inform the covering entry that a new more specific - * has been inserted beneath it + * find the covering entry */ fib_entry_cover_index = fib_table_get_less_specific_i(fib_table, prefix); /* @@ -190,6 +189,16 @@ fib_table_post_insert_actions (fib_table_t *fib_table, */ if (fib_entry_cover_index != fib_entry_index) { + /* + * push any inherting sources from the cover onto the covered + */ + fib_entry_inherit(fib_entry_cover_index, + fib_entry_index); + + /* + * inform the covering entry that a new more specific + * has been inserted beneath it + */ fib_entry_cover_change_notify(fib_entry_cover_index, fib_entry_index); } @@ -982,7 +991,7 @@ typedef struct fib_table_set_flow_hash_config_ctx_t_ flow_hash_config_t hash_config; } fib_table_set_flow_hash_config_ctx_t; -static int +static fib_table_walk_rc_t fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index, void *arg) { @@ -990,7 +999,7 @@ fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index, fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config); - return (1); + return (FIB_TABLE_WALK_CONTINUE); } void @@ -1176,6 +1185,26 @@ fib_table_walk (u32 fib_index, } } +void +fib_table_sub_tree_walk (u32 fib_index, + fib_protocol_t proto, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx) +{ + switch (proto) + { + case FIB_PROTOCOL_IP4: + ip4_fib_table_sub_tree_walk(ip4_fib_get(fib_index), root, fn, ctx); + break; + case FIB_PROTOCOL_IP6: + ip6_fib_table_sub_tree_walk(fib_index, root, fn, ctx); + break; + case FIB_PROTOCOL_MPLS: + break; + } +} + void fib_table_unlock (u32 fib_index, fib_protocol_t proto, @@ -1260,7 +1289,7 @@ typedef struct fib_table_flush_ctx_t_ fib_source_t ftf_source; } fib_table_flush_ctx_t; -static int +static fib_table_walk_rc_t fib_table_flush_cb (fib_node_index_t fib_entry_index, void *arg) { @@ -1270,7 +1299,7 @@ fib_table_flush_cb (fib_node_index_t fib_entry_index, { vec_add1(ctx->ftf_entries, fib_entry_index); } - return (1); + return (FIB_TABLE_WALK_CONTINUE); } diff --git a/src/vnet/fib/fib_table.h b/src/vnet/fib/fib_table.h index 8a0c73968fb..14ac7054059 100644 --- a/src/vnet/fib/fib_table.h +++ b/src/vnet/fib/fib_table.h @@ -792,11 +792,30 @@ extern u32 fib_table_get_num_entries(u32 fib_index, extern fib_table_t *fib_table_get(fib_node_index_t index, fib_protocol_t proto); +/** + * @brief return code controlling how a table walk proceeds + */ +typedef enum fib_table_walk_rc_t_ +{ + /** + * Continue on to the next entry + */ + FIB_TABLE_WALK_CONTINUE, + /** + * Do no traverse down this sub-tree + */ + FIB_TABLE_WALK_SUB_TREE_STOP, + /** + * Stop the walk completely + */ + FIB_TABLE_WALK_STOP, +} fib_table_walk_rc_t; + /** * @brief Call back function when walking entries in a FIB table */ -typedef int (*fib_table_walk_fn_t)(fib_node_index_t fei, - void *ctx); +typedef fib_table_walk_rc_t (*fib_table_walk_fn_t)(fib_node_index_t fei, + void *ctx); /** * @brief Walk all entries in a FIB table @@ -808,6 +827,18 @@ extern void fib_table_walk(u32 fib_index, fib_table_walk_fn_t fn, void *ctx); +/** + * @brief Walk all entries in a sub-tree FIB table. The 'root' paraneter + * is the prefix at the root of the sub-tree. + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void fib_table_sub_tree_walk(u32 fib_index, + fib_protocol_t proto, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx); + /** * @brief format (display) the memory used by the FIB tables */ diff --git a/src/vnet/fib/fib_test.c b/src/vnet/fib/fib_test.c index 9a8febb1396..61b290b8b8f 100644 --- a/src/vnet/fib/fib_test.c +++ b/src/vnet/fib/fib_test.c @@ -661,7 +661,8 @@ fib_test_validate_entry (fib_node_index_t fei, const load_balance_t *lb; FIB_TEST_LB((DPO_LOAD_BALANCE == dpo.dpoi_type), - "Entry links to %U", + "%U Entry links to %U", + format_fib_prefix, &pfx, format_dpo_type, dpo.dpoi_type); lb = load_balance_get(dpo.dpoi_index); @@ -698,7 +699,7 @@ fib_test_validate_entry (fib_node_index_t fei, fw_lbi = 0; } FIB_TEST_LB((fw_lbi == dpo.dpoi_index), - "Contributed LB = FW LB: %U\n %U", + "Contributed LB = FW LB:\n fwd:%U\n cont:%U", format_load_balance, fw_lbi, 0, format_load_balance, dpo.dpoi_index, 0); } @@ -8781,6 +8782,796 @@ lfib_test (void) return (0); } +static int +fib_test_inherit (void) +{ + fib_node_index_t fei; + test_main_t *tm; + int n_feis; + + n_feis = fib_entry_pool_size(); + tm = &test_main; + + const ip46_address_t nh_10_10_10_1 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a01), + }; + const ip46_address_t nh_10_10_10_2 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a02), + }; + const ip46_address_t nh_10_10_10_16 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a10), + }; + const ip46_address_t nh_10_10_10_20 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a14), + }; + const ip46_address_t nh_10_10_10_21 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a15), + }; + const ip46_address_t nh_10_10_10_22 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a16), + }; + const ip46_address_t nh_10_10_10_255 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0aff), + }; + const ip46_address_t nh_10_10_10_0 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a00), + }; + const ip46_address_t nh_10_10_0_0 = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0000), + }; + + /* + * prefixes at the base of a sub-tree + */ + const fib_prefix_t pfx_10_10_10_21_s_32 = { + .fp_len = 32, + .fp_proto = FIB_PROTOCOL_IP4, + .fp_addr = nh_10_10_10_21, + }; + const fib_prefix_t pfx_10_10_10_22_s_32 = { + .fp_len = 32, + .fp_proto = FIB_PROTOCOL_IP4, + .fp_addr = nh_10_10_10_22, + }; + const fib_prefix_t pfx_10_10_10_255_s_32 = { + .fp_len = 32, + .fp_proto = FIB_PROTOCOL_IP4, + .fp_addr = nh_10_10_10_255, + }; + + fib_table_entry_special_add(0, + &pfx_10_10_10_21_s_32, + FIB_SOURCE_CLI, + FIB_ENTRY_FLAG_DROP); + fib_table_entry_special_add(0, + &pfx_10_10_10_22_s_32, + FIB_SOURCE_CLI, + FIB_ENTRY_FLAG_DROP); + fib_table_entry_special_add(0, + &pfx_10_10_10_255_s_32, + FIB_SOURCE_CLI, + FIB_ENTRY_FLAG_DROP); + + /* + * source an entry that pushes its state down the sub-tree + */ + const fib_prefix_t pfx_10_10_10_16_s_28 = { + .fp_len = 28, + .fp_proto = FIB_PROTOCOL_IP4, + .fp_addr = nh_10_10_10_16, + }; + fib_table_entry_update_one_path(0, + &pfx_10_10_10_16_s_28, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP4, + &nh_10_10_10_1, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + + /* + * this covering entry and all those below it should have + * the same forwarding information. + */ + adj_index_t ai_10_10_10_1 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4, + VNET_LINK_IP4, + &nh_10_10_10_1, + tm->hw[0]->sw_if_index); + fib_test_lb_bucket_t adj_o_10_10_10_1 = { + .type = FT_LB_ADJ, + .adj = { + .adj = ai_10_10_10_1, + }, + }; + + fei = fib_table_lookup(0, &pfx_10_10_10_16_s_28); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_16_s_28); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(load_balance_is_drop(fib_entry_contribute_ip_forwarding(fei)), + "%U resolves via drop", + format_fib_prefix, &pfx_10_10_10_255_s_32); + + /* + * remove the inherting cover - covereds go back to drop + */ + fib_table_entry_delete(0, &pfx_10_10_10_16_s_28, FIB_SOURCE_API); + + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(load_balance_is_drop(fib_entry_contribute_ip_forwarding(fei)), + "%U resolves via drop", + format_fib_prefix, &pfx_10_10_10_21_s_32); + + /* + * source an entry that pushes its state down the sub-tree + */ + const fib_prefix_t pfx_10_10_10_0_s_24 = { + .fp_len = 24, + .fp_proto = FIB_PROTOCOL_IP4, + .fp_addr = nh_10_10_10_0, + }; + fib_table_entry_update_one_path(0, + &pfx_10_10_10_0_s_24, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP4, + &nh_10_10_10_1, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + + /* + * whole sub-tree now covered + */ + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_0_s_24); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_255_s_32); + + /* + * insert a more specific into the sub-tree - expect inheritance + * this one is directly covered by the root + */ + fib_table_entry_special_add(0, + &pfx_10_10_10_16_s_28, + FIB_SOURCE_CLI, + FIB_ENTRY_FLAG_DROP); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_16_s_28); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_16_s_28); + + /* + * insert a more specific into the sub-tree - expect inheritance + * this one is indirectly covered by the root + */ + const fib_prefix_t pfx_10_10_10_20_s_30 = { + .fp_len = 30, + .fp_proto = FIB_PROTOCOL_IP4, + .fp_addr = nh_10_10_10_20, + }; + fib_table_entry_special_add(0, + &pfx_10_10_10_20_s_30, + FIB_SOURCE_CLI, + FIB_ENTRY_FLAG_DROP); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_20_s_30); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_20_s_30); + + /* + * remove the prefix from the middle of the sub-tree + * the inherited source will be the only one remaining - expect + * it to be withdrawn and hence the prefix is removed. + */ + fib_table_entry_special_remove(0, + &pfx_10_10_10_20_s_30, + FIB_SOURCE_CLI); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_20_s_30); + FIB_TEST((FIB_NODE_INDEX_INVALID == fei), + "%U gone", + format_fib_prefix, &pfx_10_10_10_20_s_30); + + /* + * inheriting source is modifed - expect the modification to be present + * throughout the sub-tree + */ + adj_index_t ai_10_10_10_2 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4, + VNET_LINK_IP4, + &nh_10_10_10_2, + tm->hw[0]->sw_if_index); + fib_test_lb_bucket_t adj_o_10_10_10_2 = { + .type = FT_LB_ADJ, + .adj = { + .adj = ai_10_10_10_2, + }, + }; + + fib_table_entry_update_one_path(0, + &pfx_10_10_10_0_s_24, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP4, + &nh_10_10_10_2, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_255_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_0_s_24); + + /* + * add the source that replaces inherited state. + * inheriting source is not the best, so it doesn't push state. + */ + fib_table_entry_update_one_path(0, + &pfx_10_10_10_0_s_24, + FIB_SOURCE_PLUGIN_HI, + FIB_ENTRY_FLAG_NONE, + DPO_PROTO_IP4, + &nh_10_10_10_1, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_0_s_24); + + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(load_balance_is_drop(fib_entry_contribute_ip_forwarding(fei)), + "%U resolves via drop", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(load_balance_is_drop(fib_entry_contribute_ip_forwarding(fei)), + "%U resolves via drop", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(load_balance_is_drop(fib_entry_contribute_ip_forwarding(fei)), + "%U resolves via drop", + format_fib_prefix, &pfx_10_10_10_255_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_16_s_28); + FIB_TEST(load_balance_is_drop(fib_entry_contribute_ip_forwarding(fei)), + "%U resolves via drop", + format_fib_prefix, &pfx_10_10_10_16_s_28); + + /* + * withdraw the higher priority source and expect the inherited to return + * throughout the sub-tree + */ + fib_table_entry_delete(0, &pfx_10_10_10_0_s_24, FIB_SOURCE_PLUGIN_HI); + + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_255_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_0_s_24); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_16_s_28); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_16_s_28); + + /* + * source a covered entry in the sub-tree with the same inherting source + * - expect that it now owns the sub-tree and thus over-rides its cover + */ + fib_table_entry_update_one_path(0, + &pfx_10_10_10_16_s_28, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP4, + &nh_10_10_10_1, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_16_s_28); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_16_s_28); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_21_s_32); + + /* these two unaffected by the sub-tree change */ + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_255_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_0_s_24); + + /* + * removes the more specific, expect the /24 to now re-owns the sub-tree + */ + fib_table_entry_delete(0, &pfx_10_10_10_16_s_28, FIB_SOURCE_API); + + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_16_s_28); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_255_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_10_0_s_24); + /* + * modify the /24. expect the new forwarding to be pushed down + */ + fib_table_entry_update_one_path(0, + &pfx_10_10_10_0_s_24, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP4, + &nh_10_10_10_1, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_16_s_28); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_255_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_0_s_24); + + /* + * add an entry less specific to /24. it should not own the /24's tree + */ + const fib_prefix_t pfx_10_10_0_0_s_16 = { + .fp_len = 16, + .fp_proto = FIB_PROTOCOL_IP4, + .fp_addr = nh_10_10_0_0, + }; + fib_table_entry_update_one_path(0, + &pfx_10_10_0_0_s_16, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP4, + &nh_10_10_10_2, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_21_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_16_s_28); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_21_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_22_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_22_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_255_s_32); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_255_s_32); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_10_0_s_24); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_1), + "%U via 10.10.10.1", + format_fib_prefix, &pfx_10_10_10_0_s_24); + fei = fib_table_lookup_exact_match(0, &pfx_10_10_0_0_s_16); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + 1, + &adj_o_10_10_10_2), + "%U via 10.10.10.2", + format_fib_prefix, &pfx_10_10_0_0_s_16); + + /* + * cleanup + */ + fib_table_entry_delete(0, &pfx_10_10_10_21_s_32, FIB_SOURCE_CLI); + fib_table_entry_delete(0, &pfx_10_10_10_22_s_32, FIB_SOURCE_CLI); + fib_table_entry_delete(0, &pfx_10_10_10_16_s_28, FIB_SOURCE_CLI); + fib_table_entry_delete(0, &pfx_10_10_10_255_s_32, FIB_SOURCE_CLI); + fib_table_entry_delete(0, &pfx_10_10_10_0_s_24, FIB_SOURCE_API); + fib_table_entry_delete(0, &pfx_10_10_0_0_s_16, FIB_SOURCE_API); + adj_unlock(ai_10_10_10_1); + adj_unlock(ai_10_10_10_2); + + /* + * test the v6 tree walk. + * a /64 that covers everytinhg. a /96 that covers one /128 + * a second /128 covered only by the /64. + */ + const fib_prefix_t pfx_2001_s_64 = { + .fp_len = 64, + .fp_proto = FIB_PROTOCOL_IP6, + .fp_addr = { + .ip6 = { + .as_u64 = { + [0] = clib_host_to_net_u64(0x2001000000000000), + [1] = clib_host_to_net_u64(0x0000000000000000), + }, + }, + }, + }; + const fib_prefix_t pfx_2001_1_s_96 = { + .fp_len = 96, + .fp_proto = FIB_PROTOCOL_IP6, + .fp_addr = { + .ip6 = { + .as_u64 = { + [0] = clib_host_to_net_u64(0x2001000000000000), + [1] = clib_host_to_net_u64(0x1000000000000000), + }, + }, + }, + }; + const fib_prefix_t pfx_2001_1_1_s_128 = { + .fp_len = 128, + .fp_proto = FIB_PROTOCOL_IP6, + .fp_addr = { + .ip6 = { + .as_u64 = { + [0] = clib_host_to_net_u64(0x2001000000000000), + [1] = clib_host_to_net_u64(0x1000000000000001), + }, + }, + }, + }; + const fib_prefix_t pfx_2001_0_1_s_128 = { + .fp_len = 128, + .fp_proto = FIB_PROTOCOL_IP6, + .fp_addr = { + .ip6 = { + .as_u64 = { + [0] = clib_host_to_net_u64(0x2001000000000000), + [1] = clib_host_to_net_u64(0x0000000000000001), + }, + }, + }, + }; + const ip46_address_t nh_3000_1 = { + .ip6 = { + .as_u64 = { + [0] = clib_host_to_net_u64(0x3000000000000000), + [1] = clib_host_to_net_u64(0x0000000000000001), + }, + }, + }; + const ip46_address_t nh_3000_2 = { + .ip6 = { + .as_u64 = { + [0] = clib_host_to_net_u64(0x3000000000000000), + [1] = clib_host_to_net_u64(0x0000000000000002), + }, + }, + }; + adj_index_t ai_3000_1 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP6, + VNET_LINK_IP6, + &nh_3000_1, + tm->hw[0]->sw_if_index); + adj_index_t ai_3000_2 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP6, + VNET_LINK_IP6, + &nh_3000_2, + tm->hw[0]->sw_if_index); + fib_test_lb_bucket_t adj_o_3000_1 = { + .type = FT_LB_ADJ, + .adj = { + .adj = ai_3000_1, + }, + }; + fib_test_lb_bucket_t adj_o_3000_2 = { + .type = FT_LB_ADJ, + .adj = { + .adj = ai_3000_2, + }, + }; + + fib_table_entry_special_add(0, + &pfx_2001_0_1_s_128, + FIB_SOURCE_CLI, + FIB_ENTRY_FLAG_DROP); + fib_table_entry_special_add(0, + &pfx_2001_1_1_s_128, + FIB_SOURCE_CLI, + FIB_ENTRY_FLAG_DROP); + + /* + * /96 has inherited forwarding pushed down to its covered /128 + */ + fib_table_entry_update_one_path(0, + &pfx_2001_1_s_96, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP6, + &nh_3000_1, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + fei = fib_table_lookup_exact_match(0, &pfx_2001_1_s_96); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP6, + 1, + &adj_o_3000_1), + "%U via 3000::1", + format_fib_prefix, &pfx_2001_1_s_96); + fei = fib_table_lookup_exact_match(0, &pfx_2001_1_1_s_128); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP6, + 1, + &adj_o_3000_1), + "%U via 3000::1", + format_fib_prefix, &pfx_2001_1_1_s_128); + fei = fib_table_lookup_exact_match(0, &pfx_2001_0_1_s_128); + FIB_TEST(load_balance_is_drop(fib_entry_contribute_ip_forwarding(fei)), + "%U resolves via drop", + format_fib_prefix, &pfx_2001_0_1_s_128); + + /* + * /64 has inherited forwarding pushed down to all, but the /96 + * and its sub-tree remain unaffected. + */ + fib_table_entry_update_one_path(0, + &pfx_2001_s_64, + FIB_SOURCE_API, + FIB_ENTRY_FLAG_COVERED_INHERIT, + DPO_PROTO_IP6, + &nh_3000_2, + tm->hw[0]->sw_if_index, + ~0, + 1, + NULL, + FIB_ROUTE_PATH_FLAG_NONE); + + fei = fib_table_lookup_exact_match(0, &pfx_2001_s_64); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP6, + 1, + &adj_o_3000_2), + "%U via 3000::2", + format_fib_prefix, &pfx_2001_s_64); + fei = fib_table_lookup_exact_match(0, &pfx_2001_0_1_s_128); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP6, + 1, + &adj_o_3000_2), + "%U via 3000::1", + format_fib_prefix, &pfx_2001_0_1_s_128); + + fei = fib_table_lookup_exact_match(0, &pfx_2001_1_s_96); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP6, + 1, + &adj_o_3000_1), + "%U via 3000::1", + format_fib_prefix, &pfx_2001_1_s_96); + fei = fib_table_lookup_exact_match(0, &pfx_2001_1_1_s_128); + FIB_TEST(fib_test_validate_entry(fei, + FIB_FORW_CHAIN_TYPE_UNICAST_IP6, + 1, + &adj_o_3000_1), + "%U via 3000::1", + format_fib_prefix, &pfx_2001_1_1_s_128); + + /* + * Cleanup + */ + fib_table_entry_delete(0, &pfx_2001_0_1_s_128, FIB_SOURCE_CLI); + fib_table_entry_delete(0, &pfx_2001_1_1_s_128, FIB_SOURCE_CLI); + fib_table_entry_delete(0, &pfx_2001_s_64, FIB_SOURCE_API); + fib_table_entry_delete(0, &pfx_2001_1_s_96, FIB_SOURCE_API); + adj_unlock(ai_3000_1); + adj_unlock(ai_3000_2); + + /* + * test no-one left behind + */ + FIB_TEST((n_feis == fib_entry_pool_size()), "Entries gone"); + FIB_TEST(0 == adj_nbr_db_size(), "All adjacencies removed"); + return (0); +} + static clib_error_t * fib_test (vlib_main_t * vm, unformat_input_t * input, @@ -8825,6 +9616,10 @@ fib_test (vlib_main_t * vm, { res += fib_test_bfd(); } + else if (unformat (input, "inherit")) + { + res += fib_test_inherit(); + } else { res += fib_test_v4(); @@ -8833,6 +9628,7 @@ fib_test (vlib_main_t * vm, res += fib_test_bfd(); res += fib_test_pref(); res += fib_test_label(); + res += fib_test_inherit(); res += lfib_test(); /* diff --git a/src/vnet/fib/ip4_fib.c b/src/vnet/fib/ip4_fib.c index 0f2d3f7ad89..ef3324645c3 100644 --- a/src/vnet/fib/ip4_fib.c +++ b/src/vnet/fib/ip4_fib.c @@ -417,22 +417,95 @@ ip4_fib_table_walk (ip4_fib_t *fib, fib_table_walk_fn_t fn, void *ctx) { + fib_prefix_t root = { + .fp_proto = FIB_PROTOCOL_IP4, + // address and length default to all 0 + }; + + /* + * A full tree walk is the dengenerate case of a sub-tree from + * the very root + */ + return (ip4_fib_table_sub_tree_walk(fib, &root, fn, ctx)); +} + +void +ip4_fib_table_sub_tree_walk (ip4_fib_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx) +{ + fib_prefix_t *sub_trees = NULL; int i; - for (i = 0; i < ARRAY_LEN (fib->fib_entry_by_dst_address); i++) + /* + * There is no efficent way to walk this array of hash tables. + * so we walk each table with a mask length greater than and equal to + * the required root and check it is covered by the root. + */ + for (i = root->fp_len; + i < ARRAY_LEN (fib->fib_entry_by_dst_address); + i++) { uword * hash = fib->fib_entry_by_dst_address[i]; if (NULL != hash) { + ip4_address_t key; hash_pair_t * p; hash_foreach_pair (p, hash, ({ - fn(p->value[0], ctx); + key.as_u32 = p->key; + if (ip4_destination_matches_route(&ip4_main, + &key, + &root->fp_addr.ip4, + root->fp_len)) + { + const fib_prefix_t *sub_tree; + int skip = 0; + + /* + * exclude sub-trees the walk does not want to explore + */ + vec_foreach(sub_tree, sub_trees) + { + if (ip4_destination_matches_route(&ip4_main, + &key, + &sub_tree->fp_addr.ip4, + sub_tree->fp_len)) + { + skip = 1; + break; + } + } + + if (!skip) + { + switch (fn(p->value[0], ctx)) + { + case FIB_TABLE_WALK_CONTINUE: + break; + case FIB_TABLE_WALK_SUB_TREE_STOP: { + fib_prefix_t pfx = { + .fp_proto = FIB_PROTOCOL_IP4, + .fp_len = i, + .fp_addr.ip4 = key, + }; + vec_add1(sub_trees, pfx); + break; + } + case FIB_TABLE_WALK_STOP: + goto done; + } + } + } })); } } +done: + vec_free(sub_trees); + return; } /** @@ -443,7 +516,7 @@ typedef struct ip4_fib_show_walk_ctx_t_ fib_node_index_t *ifsw_indicies; } ip4_fib_show_walk_ctx_t; -static int +static fib_table_walk_rc_t ip4_fib_show_walk_cb (fib_node_index_t fib_entry_index, void *arg) { @@ -451,7 +524,7 @@ ip4_fib_show_walk_cb (fib_node_index_t fib_entry_index, vec_add1(ctx->ifsw_indicies, fib_entry_index); - return (1); + return (FIB_TABLE_WALK_CONTINUE); } static void diff --git a/src/vnet/fib/ip4_fib.h b/src/vnet/fib/ip4_fib.h index 438eb2405bf..84800eb2397 100644 --- a/src/vnet/fib/ip4_fib.h +++ b/src/vnet/fib/ip4_fib.h @@ -98,6 +98,16 @@ extern void ip4_fib_table_walk(ip4_fib_t *fib, fib_table_walk_fn_t fn, void *ctx); +/** + * @brief Walk all entries in a sub-tree of the FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx); + /** * @brief Get the FIB at the given index */ diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c index 3400987018f..bb092cea1bf 100644 --- a/src/vnet/fib/ip6_fib.c +++ b/src/vnet/fib/ip6_fib.c @@ -437,6 +437,8 @@ typedef struct ip6_fib_walk_ctx_t_ u32 i6w_fib_index; fib_table_walk_fn_t i6w_fn; void *i6w_ctx; + fib_prefix_t i6w_root; + fib_prefix_t *i6w_sub_trees; } ip6_fib_walk_ctx_t; static int @@ -444,11 +446,58 @@ ip6_fib_walk_cb (clib_bihash_kv_24_8_t * kvp, void *arg) { ip6_fib_walk_ctx_t *ctx = arg; + ip6_address_t key; if ((kvp->key[2] >> 32) == ctx->i6w_fib_index) { - ctx->i6w_fn(kvp->value, ctx->i6w_ctx); + key.as_u64[0] = kvp->key[0]; + key.as_u64[1] = kvp->key[1]; + + if (ip6_destination_matches_route(&ip6_main, + &key, + &ctx->i6w_root.fp_addr.ip6, + ctx->i6w_root.fp_len)) + { + const fib_prefix_t *sub_tree; + int skip = 0; + + /* + * exclude sub-trees the walk does not want to explore + */ + vec_foreach(sub_tree, ctx->i6w_sub_trees) + { + if (ip6_destination_matches_route(&ip6_main, + &key, + &sub_tree->fp_addr.ip6, + sub_tree->fp_len)) + { + skip = 1; + break; + } + } + + if (!skip) + { + switch (ctx->i6w_fn(kvp->value, ctx->i6w_ctx)) + { + case FIB_TABLE_WALK_CONTINUE: + break; + case FIB_TABLE_WALK_SUB_TREE_STOP: { + fib_prefix_t pfx = { + .fp_proto = FIB_PROTOCOL_IP6, + .fp_len = kvp->key[2] & 0xffffffff, + .fp_addr.ip6 = key, + }; + vec_add1(ctx->i6w_sub_trees, pfx); + break; + } + case FIB_TABLE_WALK_STOP: + goto done; + } + } + } } +done: return (1); } @@ -462,20 +511,44 @@ ip6_fib_table_walk (u32 fib_index, .i6w_fib_index = fib_index, .i6w_fn = fn, .i6w_ctx = arg, + .i6w_root = { + .fp_proto = FIB_PROTOCOL_IP6, + }, + .i6w_sub_trees = NULL, }; - ip6_main_t *im = &ip6_main; - BV(clib_bihash_foreach_key_value_pair)(&im->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, - ip6_fib_walk_cb, - &ctx); + BV(clib_bihash_foreach_key_value_pair)( + &ip6_main.ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, + ip6_fib_walk_cb, + &ctx); + vec_free(ctx.i6w_sub_trees); +} + +void +ip6_fib_table_sub_tree_walk (u32 fib_index, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *arg) +{ + ip6_fib_walk_ctx_t ctx = { + .i6w_fib_index = fib_index, + .i6w_fn = fn, + .i6w_ctx = arg, + .i6w_root = *root, + }; + + BV(clib_bihash_foreach_key_value_pair)( + &ip6_main.ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, + ip6_fib_walk_cb, + &ctx); } typedef struct ip6_fib_show_ctx_t_ { fib_node_index_t *entries; } ip6_fib_show_ctx_t; -static int +static fib_table_walk_rc_t ip6_fib_table_show_walk (fib_node_index_t fib_entry_index, void *arg) { @@ -483,7 +556,7 @@ ip6_fib_table_show_walk (fib_node_index_t fib_entry_index, vec_add1(ctx->entries, fib_entry_index); - return (1); + return (FIB_TABLE_WALK_CONTINUE); } static void diff --git a/src/vnet/fib/ip6_fib.h b/src/vnet/fib/ip6_fib.h index eda53628b01..dcd6c301bec 100644 --- a/src/vnet/fib/ip6_fib.h +++ b/src/vnet/fib/ip6_fib.h @@ -102,6 +102,16 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im, return 0; } +/** + * @brief Walk all entries in a sub-tree of the FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip6_fib_table_sub_tree_walk(u32 fib_index, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx); + /** * @brief return the DPO that the LB stacks on. */ diff --git a/src/vnet/ip/ip4.h b/src/vnet/ip/ip4.h index f7e5fe332b1..524a90d2616 100644 --- a/src/vnet/ip/ip4.h +++ b/src/vnet/ip/ip4.h @@ -187,18 +187,6 @@ ip4_destination_matches_interface (ip4_main_t * im, return ip4_destination_matches_route (im, key, a, ia->address_length); } -/* As above but allows for unaligned destinations (e.g. works right from IP header of packet). */ -always_inline uword -ip4_unaligned_destination_matches_route (ip4_main_t * im, - ip4_address_t * key, - ip4_address_t * dest, - uword dest_length) -{ - return 0 == - ((clib_mem_unaligned (&key->data_u32, u32) ^ dest-> - data_u32) & im->fib_masks[dest_length]); -} - always_inline int ip4_src_address_for_packet (ip_lookup_main_t * lm, u32 sw_if_index, ip4_address_t * src) diff --git a/src/vnet/ip/ip_api.c b/src/vnet/ip/ip_api.c index f4db43c9df6..0ec69e48e54 100644 --- a/src/vnet/ip/ip_api.c +++ b/src/vnet/ip/ip_api.c @@ -273,14 +273,14 @@ typedef struct vl_api_ip_fib_dump_walk_ctx_t_ fib_node_index_t *feis; } vl_api_ip_fib_dump_walk_ctx_t; -static int +static fib_table_walk_rc_t vl_api_ip_fib_dump_walk (fib_node_index_t fei, void *arg) { vl_api_ip_fib_dump_walk_ctx_t *ctx = arg; vec_add1 (ctx->feis, fei); - return (1); + return (FIB_TABLE_WALK_CONTINUE); } static void @@ -1688,7 +1688,7 @@ typedef struct api_ip6nd_proxy_fib_table_walk_ctx_t_ u32 *indices; } api_ip6nd_proxy_fib_table_walk_ctx_t; -static int +static fib_table_walk_rc_t api_ip6nd_proxy_fib_table_walk (fib_node_index_t fei, void *arg) { api_ip6nd_proxy_fib_table_walk_ctx_t *ctx = arg; @@ -1698,7 +1698,7 @@ api_ip6nd_proxy_fib_table_walk (fib_node_index_t fei, void *arg) vec_add1 (ctx->indices, fei); } - return (1); + return (FIB_TABLE_WALK_CONTINUE); } static void diff --git a/src/vnet/mpls/mpls_api.c b/src/vnet/mpls/mpls_api.c index 394a6b7f51b..36fa610e8ca 100644 --- a/src/vnet/mpls/mpls_api.c +++ b/src/vnet/mpls/mpls_api.c @@ -493,14 +493,14 @@ typedef struct vl_api_mpls_fib_dump_table_walk_ctx_t_ fib_node_index_t *lfeis; } vl_api_mpls_fib_dump_table_walk_ctx_t; -static int +static fib_table_walk_rc_t vl_api_mpls_fib_dump_table_walk (fib_node_index_t fei, void *arg) { vl_api_mpls_fib_dump_table_walk_ctx_t *ctx = arg; vec_add1 (ctx->lfeis, fei); - return (1); + return (FIB_TABLE_WALK_CONTINUE); } static void