summaryrefslogtreecommitdiffstats
path: root/src/vnet/fib/fib_path_list.c
diff options
context:
space:
mode:
authorNeale Ranns <nranns@cisco.com>2017-04-18 09:09:40 -0700
committerDave Barach <openvpp@barachs.net>2017-04-24 12:06:48 +0000
commitf12a83f54ff2239d70494d577af3e1bb253692e1 (patch)
treebd1983c3cd93c5f50f2a8a7ce5da78e059bc16ed /src/vnet/fib/fib_path_list.c
parenta5464817522c7a7dc760af4612f1d6a68ed0afc8 (diff)
Improve Load-Balance MAPs
- only build them for popular path-lists (where popular means more than 64 children) the reason to have a map is to improve convergence speed for recursive prefixes - if there are only a few this technique is not needed - only build them when there is at least one path that has recursive constraints, i.e. a path that can 'fail' in a PIC scenario. - Use the MAPS in the switch path. - PIC test cases for functionality (not convergence performance) Change-Id: I70705444c8469d22b07ae34be82cfb6a01358e10 Signed-off-by: Neale Ranns <nranns@cisco.com>
Diffstat (limited to 'src/vnet/fib/fib_path_list.c')
-rw-r--r--src/vnet/fib/fib_path_list.c73
1 files changed, 61 insertions, 12 deletions
diff --git a/src/vnet/fib/fib_path_list.c b/src/vnet/fib/fib_path_list.c
index ea6565dd19b..64917f95107 100644
--- a/src/vnet/fib/fib_path_list.c
+++ b/src/vnet/fib/fib_path_list.c
@@ -26,6 +26,16 @@
#include <vnet/fib/fib_urpf_list.h>
/**
+ * The magic number of child entries that make a path-list popular.
+ * There's a trade-off here between convergnece and forwarding speed.
+ * Popular path-lists generate load-balance maps for the entires that
+ * use them. If the map is present there is a switch path cost to indirect
+ * through the map - this indirection provides the fast convergence - so
+ * without the map convergence is slower.
+ */
+#define FIB_PATH_LIST_POPULAR 64
+
+/**
* FIB path-list
* A representation of the list/set of path trough which a prefix is reachable
*/
@@ -454,14 +464,7 @@ fib_path_list_back_walk (fib_node_index_t path_list_index,
/*
* propagate the backwalk further
*/
- if (32 >= fib_node_list_get_size(path_list->fpl_node.fn_children))
- {
- /*
- * only a few children. continue the walk synchronously
- */
- fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
- }
- else
+ if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
{
/*
* many children. schedule a async walk
@@ -471,6 +474,13 @@ fib_path_list_back_walk (fib_node_index_t path_list_index,
FIB_WALK_PRIORITY_LOW,
ctx);
}
+ else
+ {
+ /*
+ * only a few children. continue the walk synchronously
+ */
+ fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
+ }
}
/*
@@ -625,6 +635,16 @@ fib_path_list_is_looped (fib_node_index_t path_list_index)
return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
}
+int
+fib_path_list_is_popular (fib_node_index_t path_list_index)
+{
+ fib_path_list_t *path_list;
+
+ path_list = fib_path_list_get(path_list_index);
+
+ return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
+}
+
static fib_path_list_flags_t
fib_path_list_flags_fixup (fib_path_list_flags_t flags)
{
@@ -807,6 +827,7 @@ fib_path_list_path_add (fib_node_index_t path_list_index,
*/
if (0 == fib_path_cmp(new_path_index, *orig_path_index))
{
+ fib_path_destroy(new_path_index);
return (*orig_path_index);
}
}
@@ -1173,10 +1194,38 @@ fib_path_list_child_add (fib_node_index_t path_list_index,
fib_node_type_t child_type,
fib_node_index_t child_index)
{
- return (fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
- path_list_index,
- child_type,
- child_index));
+ u32 sibling;
+
+ sibling = fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
+ path_list_index,
+ child_type,
+ child_index);
+
+ if (FIB_PATH_LIST_POPULAR == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST,
+ path_list_index))
+ {
+ /*
+ * Set the popular flag on the path-list once we pass the magic
+ * threshold. then walk children to update.
+ * We don't undo this action. The rational being that the number
+ * of entries using this prefix is large enough such that it is a
+ * non-trival amount of effort to converge them. If we get into the
+ * situation where we are adding and removing entries such that we
+ * flip-flop over the threshold, then this non-trivial work is added
+ * to each of those routes adds/deletes - not a situation we want.
+ */
+ fib_node_back_walk_ctx_t ctx = {
+ .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
+ };
+ fib_path_list_t *path_list;
+
+ path_list = fib_path_list_get(path_list_index);
+ path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
+
+ fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
+ }
+
+ return (sibling);
}
void