X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvnet%2Ffib%2Ffib_path_list.c;h=df08bb2b0d05bb536b36f63b646251174879651b;hb=da3310597;hp=4655c687427fec7fa22367249d362b0503365d06;hpb=710071bf0ed7a0926581d1f738a142b72e795d2b;p=vpp.git diff --git a/src/vnet/fib/fib_path_list.c b/src/vnet/fib/fib_path_list.c index 4655c687427..df08bb2b0d0 100644 --- a/src/vnet/fib/fib_path_list.c +++ b/src/vnet/fib/fib_path_list.c @@ -24,11 +24,13 @@ #include #include #include +#include +#include /** * 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 + * There's a trade-off here between convergence and forwarding speed. + * 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. @@ -60,11 +62,6 @@ typedef struct fib_path_list_t_ { * the RPF list calculated for this path list */ fib_node_index_t fpl_urpf; - - /** - * Hash table of paths. valid only with INDEXED flag - */ - uword *fpl_db; } fib_path_list_t; /* @@ -179,7 +176,10 @@ fib_path_list_hash (fib_path_list_t *path_list) ASSERT(path_list); - new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths); + new_path_list_hash = + old_path_list_hash = + (vec_len(path_list->fpl_paths) << 16 | + (path_list->fpl_flags & FIB_PATH_LIST_KEY_FLAGS)); vec_foreach (path_index, path_list->fpl_paths) { @@ -363,10 +363,12 @@ fib_path_list_mk_lb (fib_path_list_t *path_list, 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. @@ -387,10 +389,10 @@ fib_path_list_mk_lb (fib_path_list_t *path_list, */ 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, + load_balance_get_default_flow_hash(dproto))); load_balance_multipath_update(dpo, nhs, fib_path_list_fwd_flags_2_load_balance(flags)); @@ -505,7 +507,7 @@ fib_path_list_back_walk_notify (fib_node_t *node, { /* * the path-list is not a direct child of any other node type - * paths, which do not change thier to-list-mapping, save the + * paths, which do not change their to-list-mapping, save the * list they are a member of, and invoke the BW function directly. */ ASSERT(0); @@ -542,7 +544,7 @@ fib_path_list_alloc (fib_node_index_t *path_list_index) 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); @@ -722,7 +724,7 @@ fib_path_list_create (fib_path_list_flags_t flags, if (FIB_NODE_INDEX_INVALID != old_path_list_index) { fib_path_list_destroy(path_list); - + path_list_index = old_path_list_index; } else @@ -747,7 +749,7 @@ fib_path_list_create (fib_path_list_flags_t flags, 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; @@ -825,12 +827,14 @@ fib_path_list_find_rpath (fib_node_index_t path_list_index, * 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 @@ -838,40 +842,65 @@ fib_path_list_path_add (fib_node_index_t path_list_index, */ 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(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); + } + } - return (new_path_index); + FIB_PATH_LIST_DBG(path_list, "paths-added"); + + return (new_path_indices); } fib_node_index_t @@ -879,14 +908,13 @@ fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index, 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 @@ -900,32 +928,50 @@ fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index, 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) { - path_index = fib_path_copy(*orig_path_index, path_list_index); - path_list->fpl_paths[pi++] = path_index; + /* + * 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) + { + _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 @@ -973,51 +1019,60 @@ fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index, } /* - * 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(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); } /* @@ -1030,10 +1085,11 @@ fib_path_list_path_remove (fib_node_index_t path_list_index, 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); @@ -1048,44 +1104,42 @@ fib_path_list_copy_and_path_remove (fib_node_index_t orig_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 @@ -1258,7 +1312,7 @@ fib_path_list_child_add (fib_node_index_t path_list_index, * 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 + * non-trivial 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. @@ -1343,6 +1397,29 @@ fib_path_list_walk (fib_node_index_t path_list_index, } } +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) @@ -1378,7 +1455,7 @@ show_fib_path_list_command (vlib_main_t * vm, u8 *s = fib_path_list_format(pli, NULL); s = format(s, "children:"); s = fib_node_children_format(path_list->fpl_node.fn_children, s); - vlib_cli_output (vm, "%s", s); + vlib_cli_output (vm, "%v", s); vec_free(s); } else @@ -1392,10 +1469,10 @@ show_fib_path_list_command (vlib_main_t * vm, * show all */ vlib_cli_output (vm, "FIB Path Lists"); - pool_foreach_index (pli, fib_path_list_pool, - ({ + pool_foreach_index (pli, fib_path_list_pool) + { vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0); - })); + } } return (NULL); }