#include <vnet/fib/fib_node_list.h>
#include <vnet/fib/fib_walk.h>
#include <vnet/fib/fib_urpf_list.h>
+#include <vnet/fib/fib_path_ext.h>
+#include <vnet/fib/fib_table.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
+ * Popular path-lists generate load-balance maps for the entries 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.
*/
static uword *fib_path_list_db;
+/**
+ * the logger
+ */
+vlib_log_class_t fib_path_list_logger;
+
/*
* Debug macro
*/
-#ifdef FIB_DEBUG
-#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
-{ \
- u8 *_tmp = 0; \
- _tmp = fib_path_list_format( \
- fib_path_list_get_index(_pl), _tmp); \
- clib_warning("pl:[%d:%p:%p:%s]:" _fmt, \
- fib_path_list_get_index(_pl), \
- _pl, _pl->fpl_paths, _tmp, \
- ##_args); \
- vec_free(_tmp); \
+#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
+{ \
+ vlib_log_debug(fib_path_list_logger, \
+ "[%U]:" _fmt, \
+ format_fib_path_list, \
+ fib_path_list_get_index(_pl), 0, \
+ ##_args); \
}
-#else
-#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
-#endif
static fib_path_list_t *
fib_path_list_get (fib_node_index_t index)
vec_foreach (path_index, path_list->fpl_paths)
{
- s = format(s, "%U", format_fib_path, *path_index, indent+2);
+ s = format(s, "%U", format_fib_path, *path_index, indent+2,
+ FIB_PATH_FORMAT_FLAGS_NONE);
s = format(s, "\n");
}
dpo_id_t *dpo,
fib_path_list_fwd_flags_t flags)
{
- load_balance_path_t *nhs;
fib_node_index_t *path_index;
+ load_balance_path_t *nhs;
+ dpo_proto_t dproto;
nhs = NULL;
+ dproto = fib_forw_chain_type_to_dpo_proto(fct);
/*
* We gather the DPOs from resolved paths.
*/
dpo_set(dpo,
DPO_LOAD_BALANCE,
- fib_forw_chain_type_to_dpo_proto(fct),
+ dproto,
load_balance_create(vec_len(nhs),
- fib_forw_chain_type_to_dpo_proto(fct),
- 0 /* FIXME FLOW HASH */));
+ dproto,
+ fib_table_get_default_flow_hash_config(
+ dpo_proto_to_fib(dproto))));
load_balance_multipath_update(dpo, nhs,
fib_path_list_fwd_flags_2_load_balance(flags));
fib_path_list_mk_urpf(path_list);
+ FIB_PATH_LIST_DBG(path_list, "bw:%U",
+ format_fib_node_bw_reason, ctx->fnbw_reason);
+
/*
* propagate the backwalk further
*/
fib_path_list_t *path_list;
pool_get(fib_path_list_pool, path_list);
- memset(path_list, 0, sizeof(*path_list));
+ clib_memset(path_list, 0, sizeof(*path_list));
fib_node_init(&path_list->fpl_node,
FIB_NODE_TYPE_PATH_LIST);
if (FIB_NODE_INDEX_INVALID != old_path_list_index)
{
fib_path_list_destroy(path_list);
-
+
path_list_index = old_path_list_index;
}
else
return (path_list_index);
}
-static fib_path_cfg_flags_t
+static fib_path_cfg_flags_t
fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
{
fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
* The path-list returned could either have been newly created, or
* can be a shared path-list from the data-base.
*/
-fib_node_index_t
-fib_path_list_path_add (fib_node_index_t path_list_index,
- const fib_route_path_t *rpaths)
+fib_node_index_t*
+fib_path_list_paths_add (fib_node_index_t path_list_index,
+ const fib_route_path_t *rpaths)
{
- fib_node_index_t new_path_index, *orig_path_index;
+ fib_node_index_t *new_path_indices, *path_index;
+ const fib_route_path_t *rpath;
fib_path_list_t *path_list;
+ u32 ii;
/*
* alloc the new list before we retrieve the old one, lest
*/
path_list = fib_path_list_get(path_list_index);
- ASSERT(1 == vec_len(rpaths));
ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
- FIB_PATH_LIST_DBG(orig_path_list, "path-add");
+ FIB_PATH_LIST_DBG(path_list, "paths-add");
- new_path_index = fib_path_create(path_list_index,
- rpaths);
+ new_path_indices = NULL;
+ vec_validate_init_empty(new_path_indices,
+ vec_len(rpaths) - 1,
+ FIB_NODE_INDEX_INVALID);
- vec_foreach (orig_path_index, path_list->fpl_paths)
+ vec_foreach (path_index, path_list->fpl_paths)
{
/*
* don't add duplicate paths
*/
- if (0 == fib_path_cmp(new_path_index, *orig_path_index))
+ int found = 0;
+
+ vec_foreach_index(ii, rpaths)
{
- fib_path_destroy(new_path_index);
- return (*orig_path_index);
+ rpath = &rpaths[ii];
+ if (0 == fib_path_cmp_w_route_path(*path_index, rpath))
+ {
+ found = 1;
+ break;
+ }
+ }
+ if (found)
+ {
+ new_path_indices[ii] = *path_index;
}
}
/*
- * Add the new path - no sort, no sharing, no key..
+ * new_path_indices array contains INVALID for each path not found
+ * and something valid for matches
*/
- vec_add1(path_list->fpl_paths, new_path_index);
+ vec_foreach_index (ii, new_path_indices)
+ {
+ path_index = &new_path_indices[ii];
+ rpath = &rpaths[ii];
- FIB_PATH_LIST_DBG(path_list, "path-added");
+ if (FIB_NODE_INDEX_INVALID == *path_index)
+ {
+ *path_index = fib_path_create(path_list_index, rpath);
+ /*
+ * Add the new path - no sort, no sharing, no key..
+ */
+ vec_add1(path_list->fpl_paths, *path_index);
- /*
- * no shared path list requested. resolve and use the one
- * just created.
- */
- fib_path_resolve(new_path_index);
+ /*
+ * no shared path list requested. resolve and use the one
+ * just created.
+ */
+ fib_path_resolve(*path_index);
+ }
+ }
+
+ FIB_PATH_LIST_DBG(path_list, "paths-added");
- return (new_path_index);
+ return (new_path_indices);
}
fib_node_index_t
fib_path_list_flags_t flags,
const fib_route_path_t *rpaths)
{
- fib_node_index_t path_index, new_path_index, *orig_path_index;
+ fib_node_index_t new_path_index, *orig_path_index;
fib_path_list_t *path_list, *orig_path_list;
fib_node_index_t exist_path_list_index;
fib_node_index_t path_list_index;
+ const fib_route_path_t *rpath;
fib_node_index_t pi;
- ASSERT(1 == vec_len(rpaths));
-
/*
* alloc the new list before we retrieve the old one, lest
* the alloc result in a realloc
flags = fib_path_list_flags_fixup(flags);
path_list->fpl_flags = flags;
- vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
+ vec_validate(path_list->fpl_paths,
+ (vec_len(orig_path_list->fpl_paths) +
+ vec_len(rpaths) - 1));
pi = 0;
- new_path_index = fib_path_create(path_list_index,
- rpaths);
-
- vec_foreach (orig_path_index, orig_path_list->fpl_paths)
+ vec_foreach(orig_path_index, orig_path_list->fpl_paths)
{
/*
- * don't add duplicate paths
- * In the unlikely event the path is a duplicate, then we'll
- * find a matching path-list later and this one will be toast.
+ * copy the original paths over to the new list
*/
- if (0 != fib_path_cmp(new_path_index, *orig_path_index))
+ path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
+ path_list_index);
+ }
+ vec_foreach(rpath, rpaths)
+ {
+ int duplicate = 0;
+
+ new_path_index = fib_path_create(path_list_index, rpath);
+
+ vec_foreach(orig_path_index, orig_path_list->fpl_paths)
+ {
+ /*
+ * don't add duplicate paths
+ * In the unlikely event the path is a duplicate, then we'll
+ * find a matching path-list later and this one will be toast.
+ */
+ if (0 == fib_path_cmp(new_path_index, *orig_path_index))
+ {
+ duplicate = 1;
+ break;
+ }
+ }
+ if (duplicate)
{
- path_index = fib_path_copy(*orig_path_index, path_list_index);
- path_list->fpl_paths[pi++] = path_index;
+ _vec_len(path_list->fpl_paths) =
+ vec_len(path_list->fpl_paths) - 1;
+ fib_path_destroy(new_path_index);
}
else
{
- _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
+ path_list->fpl_paths[pi++] = new_path_index;
}
}
- path_list->fpl_paths[pi] = new_path_index;
-
/*
* we sort the paths since the key for the path-list is
* the description of the paths it contains. The paths need to
}
/*
- * fib_path_list_path_remove
+ * fib_path_list_paths_remove
*/
-fib_node_index_t
-fib_path_list_path_remove (fib_node_index_t path_list_index,
+fib_node_index_t*
+fib_path_list_paths_remove (fib_node_index_t path_list_index,
const fib_route_path_t *rpaths)
{
- fib_node_index_t match_path_index, tmp_path_index;
+ fib_node_index_t *match_path_indices;
fib_path_list_t *path_list;
- fib_node_index_t pi;
+ i32 ii, jj;
path_list = fib_path_list_get(path_list_index);
+ match_path_indices = NULL;
+ vec_validate_init_empty(match_path_indices,
+ vec_len(rpaths) - 1,
+ FIB_NODE_INDEX_INVALID);
- ASSERT(1 == vec_len(rpaths));
ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
- FIB_PATH_LIST_DBG(orig_path_list, "path-remove");
+ FIB_PATH_LIST_DBG(path_list, "path-remove");
/*
- * create a representation of the path to be removed, so it
- * can be used as a comparison object during the copy.
+ * the number of existing paths is likely to be larger than the
+ * number of paths being added.
+ * walk in reverse so the vec_del is ok
*/
- tmp_path_index = fib_path_create(path_list_index,
- rpaths);
- match_path_index = FIB_NODE_INDEX_INVALID;
-
- vec_foreach_index (pi, path_list->fpl_paths)
+ vec_foreach_index_backwards(ii, path_list->fpl_paths)
{
- if (0 == fib_path_cmp(tmp_path_index,
- path_list->fpl_paths[pi]))
+ int found = ~0;
+
+ vec_foreach_index(jj, rpaths)
+ {
+ if (0 == fib_path_cmp_w_route_path(path_list->fpl_paths[ii],
+ &rpaths[jj]))
+ {
+ found = jj;
+ break;
+ }
+ }
+ if (~0 != found)
{
+ fib_node_index_t match_path_index;
/*
* match - remove it
*/
- match_path_index = path_list->fpl_paths[pi];
+ match_path_index = path_list->fpl_paths[ii];
+ vec_del1(path_list->fpl_paths, ii);
fib_path_destroy(match_path_index);
- vec_del1(path_list->fpl_paths, pi);
- }
+ match_path_indices[jj] = match_path_index;
+ }
}
- /*
- * done with the temporary now
- */
- fib_path_destroy(tmp_path_index);
+ FIB_PATH_LIST_DBG(path_list, "paths-removed");
- return (match_path_index);
+ return (match_path_indices);
}
/*
fib_node_index_t
fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
fib_path_list_flags_t flags,
- const fib_route_path_t *rpath)
+ const fib_route_path_t *rpaths)
{
- fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
+ fib_node_index_t *orig_path_index, path_list_index, tmp_path_index;
fib_path_list_t *path_list, *orig_path_list;
+ const fib_route_path_t *rpath;
fib_node_index_t pi;
path_list = fib_path_list_alloc(&path_list_index);
* allocate as many paths as we might need in one go, rather than
* using vec_add to do a few at a time.
*/
- if (vec_len(orig_path_list->fpl_paths) > 1)
- {
- vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
- }
+ vec_validate(path_list->fpl_paths,
+ vec_len(orig_path_list->fpl_paths) - 1);
pi = 0;
/*
* create a representation of the path to be removed, so it
* can be used as a comparison object during the copy.
*/
- tmp_path_index = fib_path_create(path_list_index, rpath);
-
- vec_foreach (orig_path_index, orig_path_list->fpl_paths)
+ vec_foreach(orig_path_index, orig_path_list->fpl_paths)
{
- if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
- path_index = fib_path_copy(*orig_path_index, path_list_index);
- if (pi < vec_len(path_list->fpl_paths))
- {
- path_list->fpl_paths[pi++] = path_index;
- }
- else
- {
- /*
- * this is the unlikely case that the path being
- * removed does not match one in the path-list, so
- * we end up with as many paths as we started with.
- * the paths vector was sized above with the expectation
- * that we would have 1 less.
- */
- vec_add1(path_list->fpl_paths, path_index);
- }
- }
+ /*
+ * copy the original paths over to the new list
+ */
+ path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
+ path_list_index);
}
+ vec_foreach(rpath, rpaths)
+ {
+ int found = 0;
+ tmp_path_index = fib_path_create(path_list_index, rpath);
- /*
- * done with the temporary now
- */
- fib_path_destroy(tmp_path_index);
+ vec_foreach_index(pi, path_list->fpl_paths)
+ {
+ if (0 == fib_path_cmp(tmp_path_index, path_list->fpl_paths[pi]))
+ {
+ found = 1;
+ break;
+ }
+ }
+ if (found)
+ {
+ fib_path_destroy(path_list->fpl_paths[pi]);
+ vec_del1(path_list->fpl_paths, pi);
+ }
+ fib_path_destroy(tmp_path_index);
+ }
/*
* if there are no paths, then the new path-list is aborted
vec_free(copy);
}
- FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval);
+ FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
if (list_looped)
{
path_list = fib_path_list_get(path_list_index);
fib_node_lock(&path_list->fpl_node);
- FIB_PATH_LIST_DBG(path_list, "lock");
}
}
if (FIB_NODE_INDEX_INVALID != path_list_index)
{
path_list = fib_path_list_get(path_list_index);
- FIB_PATH_LIST_DBG(path_list, "unlock");
fib_node_unlock(&path_list->fpl_node);
}
}
}
+void
+fib_path_list_walk_w_ext (fib_node_index_t path_list_index,
+ const fib_path_ext_list_t *ext_list,
+ fib_path_list_walk_w_ext_fn_t func,
+ void *ctx)
+{
+ fib_node_index_t *path_index;
+ fib_path_list_t *path_list;
+ fib_path_ext_t *path_ext;
+
+ path_list = fib_path_list_get(path_list_index);
+
+ vec_foreach(path_index, path_list->fpl_paths)
+ {
+ path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
+
+ if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
+ *path_index,
+ path_ext,
+ ctx))
+ break;
+ }
+}
void
fib_path_list_module_init (void)
fib_path_list_db_hash_key_equal,
/* format pair/arg */
0, 0);
+ fib_path_list_logger = vlib_log_register_class("fib", "path-list");
}
static clib_error_t *
Code Review / vpp.git / blobdiff