aboutsummaryrefslogtreecommitdiffstats
path: root/src/vnet/fib
diff options
context:
space:
mode:
authorNeale Ranns <nranns@cisco.com>2017-04-06 04:41:02 -0700
committerDamjan Marion <dmarion.lists@gmail.com>2018-01-18 14:37:24 +0000
commit89541992000433b743cbbe8cb396faab42bcf6ae (patch)
tree2b09b2178270ad6de191e2eeaa5d3f49148d5a8e /src/vnet/fib
parentbf246dff1b4ea0792c0083f7e5495930b3b225f7 (diff)
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 <nranns@cisco.com>
Diffstat (limited to 'src/vnet/fib')
-rw-r--r--src/vnet/fib/fib_entry.c238
-rw-r--r--src/vnet/fib/fib_entry.h26
-rw-r--r--src/vnet/fib/fib_entry_src.c353
-rw-r--r--src/vnet/fib/fib_entry_src.h18
-rw-r--r--src/vnet/fib/fib_entry_src_adj.c29
-rw-r--r--src/vnet/fib/fib_entry_src_default.c2
-rw-r--r--src/vnet/fib/fib_entry_src_interface.c2
-rw-r--r--src/vnet/fib/fib_entry_src_rr.c2
-rw-r--r--src/vnet/fib/fib_table.c41
-rw-r--r--src/vnet/fib/fib_table.h35
-rw-r--r--src/vnet/fib/fib_test.c800
-rw-r--r--src/vnet/fib/ip4_fib.c81
-rw-r--r--src/vnet/fib/ip4_fib.h10
-rw-r--r--src/vnet/fib/ip6_fib.c87
-rw-r--r--src/vnet/fib/ip6_fib.h10
15 files changed, 1615 insertions, 119 deletions
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<<attr) & src->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<<sattr) & src->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
{
@@ -1076,6 +1137,20 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index,
}
/**
+ * 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
*
* The source is withdrawing all the paths it provided
@@ -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
@@ -213,9 +213,14 @@ typedef enum fib_entry_attribute_t_ {
*/
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;
/**
@@ -263,9 +270,13 @@ typedef enum fib_entry_src_attribute_t_ {
*/
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);
@@ -730,6 +977,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
*/
path_list_index = fib_entry->fe_parent;
@@ -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
@@ -60,6 +60,13 @@ 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)
@@ -262,6 +258,28 @@ fib_entry_src_adj_activate (fib_entry_src_t *src,
}
/*
+ * 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
@@ -1177,6 +1186,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,
fib_source_t source)
@@ -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
@@ -793,10 +793,29 @@ 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
@@ -809,6 +828,18 @@ extern void fib_table_walk(u32 fib_index,
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
*/
extern u8 *format_fib_table_memory(u8 *s, va_list *args);
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
@@ -99,6 +99,16 @@ extern void ip4_fib_table_walk(ip4_fib_t *fib,
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
*/
static inline ip4_fib_t *
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
@@ -103,6 +103,16 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im,
}
/**
+ * @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.
*/
always_inline u32