/* * Copyright (c) 2016 Cisco and/or its affiliates. * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at: * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include <vppinfra/mhash.h> #include <vnet/ip/ip.h> #include <vnet/adj/adj.h> #include <vnet/dpo/load_balance.h> #include <vnet/dpo/load_balance_map.h> #include <vnet/fib/fib_path_list.h> #include <vnet/fib/fib_internal.h> #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 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. */ #define FIB_PATH_LIST_POPULAR 64 /** * FIB path-list * A representation of the list/set of path trough which a prefix is reachable */ typedef struct fib_path_list_t_ { /** * A path-list is a node in the FIB graph. */ fib_node_t fpl_node; /** * Flags on the path-list */ fib_path_list_flags_t fpl_flags; /** * Vector of paths indicies for all configured paths. * For shareable path-lists this list MUST not change. */ fib_node_index_t *fpl_paths; /** * the RPF list calculated for this path list */ fib_node_index_t fpl_urpf; } fib_path_list_t; /* * Array of strings/names for the FIB sources */ static const char *fib_path_list_attr_names[] = FIB_PATH_LIST_ATTRIBUTES; /* * The memory pool from which we allocate all the path-lists */ static fib_path_list_t * fib_path_list_pool; /* * The data-base of shared path-lists */ static uword *fib_path_list_db; /** * the logger */ vlib_log_class_t fib_path_list_logger; /* * Debug macro */ #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); \ } static fib_path_list_t * fib_path_list_get (fib_node_index_t index) { return (pool_elt_at_index(fib_path_list_pool, index)); } static fib_node_t * fib_path_list_get_node (fib_node_index_t index) { return ((fib_node_t*)fib_path_list_get(index)); } static fib_path_list_t* fib_path_list_from_fib_node (fib_node_t *node) { ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type); return ((fib_path_list_t*)node); } static fib_node_index_t fib_path_list_get_index (fib_path_list_t *path_list) { return (path_list - fib_path_list_pool); } u8 * format_fib_path_list (u8 * s, va_list * args) { fib_node_index_t *path_index, path_list_index; fib_path_list_attribute_t attr; fib_path_list_t *path_list; u32 indent; path_list_index = va_arg (*args, fib_node_index_t); indent = va_arg (*args, u32); path_list = fib_path_list_get(path_list_index); s = format (s, "%Upath-list:[%d]", format_white_space, indent, fib_path_list_get_index(path_list)); s = format (s, " locks:%u", path_list->fpl_node.fn_locks); if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags) { s = format (s, " flags:"); FOR_EACH_PATH_LIST_ATTRIBUTE(attr) { if ((1<<attr) & path_list->fpl_flags) { s = format (s, "%s,", fib_path_list_attr_names[attr]); } } } s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf); vec_foreach (path_index, path_list->fpl_paths) { s = format(s, "%U", format_fib_path, *path_index, indent+2, FIB_PATH_FORMAT_FLAGS_NONE); s = format(s, "\n"); } return (s); } u8 * fib_path_list_format (fib_node_index_t path_list_index, u8 * s) { return (format(s, "%U", format_fib_path_list, path_list_index, 4)); } static uword fib_path_list_hash (fib_path_list_t *path_list) { uword old_path_list_hash, new_path_list_hash, path_hash; fib_node_index_t *path_index; ASSERT(path_list); 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) { path_hash = fib_path_hash(*path_index); #if uword_bits == 64 hash_mix64(path_hash, old_path_list_hash, new_path_list_hash); #else hash_mix32(path_hash, old_path_list_hash, new_path_list_hash); #endif } return (new_path_list_hash); } always_inline uword fib_path_list_db_hash_key_from_index (uword index) { return 1 + 2*index; } always_inline uword fib_path_list_db_hash_key_is_index (uword key) { return key & 1; } always_inline uword fib_path_list_db_hash_key_2_index (uword key) { ASSERT (fib_path_list_db_hash_key_is_index (key)); return key / 2; } static fib_path_list_t* fib_path_list_db_get_from_hash_key (uword key) { fib_path_list_t *path_list; if (fib_path_list_db_hash_key_is_index (key)) { fib_node_index_t path_list_index; path_list_index = fib_path_list_db_hash_key_2_index(key); path_list = fib_path_list_get(path_list_index); } else { path_list = uword_to_pointer (key, fib_path_list_t *); } return (path_list); } static uword fib_path_list_db_hash_key_sum (hash_t * h, uword key) { fib_path_list_t *path_list; path_list = fib_path_list_db_get_from_hash_key(key); return (fib_path_list_hash(path_list)); } static uword fib_path_list_db_hash_key_equal (hash_t * h, uword key1, uword key2) { fib_path_list_t *path_list1, *path_list2; path_list1 = fib_path_list_db_get_from_hash_key(key1); path_list2 = fib_path_list_db_get_from_hash_key(key2); return (fib_path_list_hash(path_list1) == fib_path_list_hash(path_list2)); } static fib_node_index_t fib_path_list_db_find (fib_path_list_t *path_list) { uword *p; p = hash_get(fib_path_list_db, path_list); if (NULL != p) { return p[0]; } return (FIB_NODE_INDEX_INVALID); } static void fib_path_list_db_insert (fib_node_index_t path_list_index) { fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list)); hash_set (fib_path_list_db, fib_path_list_db_hash_key_from_index(path_list_index), path_list_index); FIB_PATH_LIST_DBG(path_list, "DB-inserted"); } static void fib_path_list_db_remove (fib_node_index_t path_list_index) { fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list)); hash_unset(fib_path_list_db, fib_path_list_db_hash_key_from_index(path_list_index)); FIB_PATH_LIST_DBG(path_list, "DB-removed"); } static void fib_path_list_destroy (fib_path_list_t *path_list) { fib_node_index_t *path_index; FIB_PATH_LIST_DBG(path_list, "destroy"); vec_foreach (path_index, path_list->fpl_paths) { fib_path_destroy(*path_index); } vec_free(path_list->fpl_paths); fib_urpf_list_unlock(path_list->fpl_urpf); fib_node_deinit(&path_list->fpl_node); pool_put(fib_path_list_pool, path_list); } static void fib_path_list_last_lock_gone (fib_node_t *node) { fib_path_list_t *path_list; path_list = fib_path_list_from_fib_node(node); FIB_PATH_LIST_DBG(path_list, "last-lock"); if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED) { fib_path_list_db_remove(fib_path_list_get_index(path_list)); } fib_path_list_destroy(path_list); } static load_balance_flags_t fib_path_list_fwd_flags_2_load_balance (fib_path_list_fwd_flags_t pl_flags) { load_balance_flags_t lb_flags = LOAD_BALANCE_FLAG_NONE; if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY) { lb_flags |= LOAD_BALANCE_ATTR_STICKY; } return (lb_flags); } /* * fib_path_mk_lb * * update the multipath adj this path-list will contribute to its * children's forwarding. */ static void fib_path_list_mk_lb (fib_path_list_t *path_list, fib_forward_chain_type_t fct, dpo_id_t *dpo, fib_path_list_fwd_flags_t flags) { 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. */ vec_foreach (path_index, path_list->fpl_paths) { if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) || fib_path_is_resolved(*path_index)) { nhs = fib_path_append_nh_for_multipath_hash(*path_index, fct, nhs); } } /* * Path-list load-balances, which if used, would be shared and hence * never need a load-balance map. */ dpo_set(dpo, DPO_LOAD_BALANCE, dproto, load_balance_create(vec_len(nhs), dproto, load_balance_get_default_flow_hash(dproto))); load_balance_multipath_update(dpo, nhs, fib_path_list_fwd_flags_2_load_balance(flags)); FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index); vec_free(nhs); } /** * @brief [re]build the path list's uRPF list */ static void fib_path_list_mk_urpf (fib_path_list_t *path_list) { fib_node_index_t *path_index; /* * ditch the old one. by iterating through all paths we are going * to re-find all the adjs that were in the old one anyway. If we * keep the old one, then the |sort|uniq requires more work. * All users of the RPF list have their own lock, so we can release * immediately. */ fib_urpf_list_unlock(path_list->fpl_urpf); path_list->fpl_urpf = fib_urpf_list_alloc_and_lock(); vec_foreach (path_index, path_list->fpl_paths) { fib_path_contribute_urpf(*path_index, path_list->fpl_urpf); } fib_urpf_list_bake(path_list->fpl_urpf); } /** * @brief Contribute (add) this path list's uRPF list. This allows the child * to construct an aggregate list. */ void fib_path_list_contribute_urpf (fib_node_index_t path_list_index, index_t urpf) { fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); fib_urpf_list_combine(urpf, path_list->fpl_urpf); } /** * @brief Return the the child the RPF list pre-built for this path list */ index_t fib_path_list_get_urpf (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_urpf); } /* * fib_path_list_back_walk * * Called from one of this path-list's paths to progate * a back walk */ void fib_path_list_back_walk (fib_node_index_t path_list_index, fib_node_back_walk_ctx_t *ctx) { fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); 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 */ if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR) { /* * many children. schedule a async walk */ fib_walk_async(FIB_NODE_TYPE_PATH_LIST, 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); } } /* * fib_path_list_back_walk_notify * * A back walk has reach this path-list. */ static fib_node_back_walk_rc_t fib_path_list_back_walk_notify (fib_node_t *node, fib_node_back_walk_ctx_t *ctx) { /* * the path-list is not a direct child of any other node type * 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); return (FIB_NODE_BACK_WALK_CONTINUE); } /* * Display the path-list memory usage */ static void fib_path_list_memory_show (void) { fib_show_memory_usage("Path-list", pool_elts(fib_path_list_pool), pool_len(fib_path_list_pool), sizeof(fib_path_list_t)); fib_urpf_list_show_mem(); } /* * The FIB path-list's graph node virtual function table */ static const fib_node_vft_t fib_path_list_vft = { .fnv_get = fib_path_list_get_node, .fnv_last_lock = fib_path_list_last_lock_gone, .fnv_back_walk = fib_path_list_back_walk_notify, .fnv_mem_show = fib_path_list_memory_show, }; static inline fib_path_list_t * 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); clib_memset(path_list, 0, sizeof(*path_list)); fib_node_init(&path_list->fpl_node, FIB_NODE_TYPE_PATH_LIST); path_list->fpl_urpf = INDEX_INVALID; path_list->fpl_paths = NULL; *path_list_index = fib_path_list_get_index(path_list); FIB_PATH_LIST_DBG(path_list, "alloc"); return (path_list); } static fib_path_list_t * fib_path_list_resolve (fib_path_list_t *path_list) { fib_node_index_t *path_index, *paths, path_list_index; ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED)); /* * resolving a path-list is a recursive action. this means more path * lists can be created during this call, and hence this path-list * can be realloc'd. so we work with copies. * this function is called only once per-path list, so its no great overhead. */ path_list_index = fib_path_list_get_index(path_list); paths = vec_dup(path_list->fpl_paths); vec_foreach (path_index, paths) { fib_path_resolve(*path_index); } vec_free(paths); path_list = fib_path_list_get(path_list_index); FIB_PATH_LIST_DBG(path_list, "resovled"); if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF)) { fib_path_list_mk_urpf(path_list); } return (path_list); } u32 fib_path_list_get_n_paths (fib_node_index_t path_list_index) { fib_path_list_t *path_list; if (FIB_NODE_INDEX_INVALID == path_list_index) { return (0); } path_list = fib_path_list_get(path_list_index); return (vec_len(path_list->fpl_paths)); } u32 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index) { fib_node_index_t *path_index; fib_path_list_t *path_list; u32 sw_if_index; path_list = fib_path_list_get(path_list_index); sw_if_index = ~0; vec_foreach (path_index, path_list->fpl_paths) { sw_if_index = fib_path_get_resolving_interface(*path_index); if (~0 != sw_if_index) { return (sw_if_index); } } return (sw_if_index); } dpo_proto_t fib_path_list_get_proto (fib_node_index_t path_list_index) { fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); /* * we don't support a mix of path protocols, so we can return the proto * of the first */ return (fib_path_get_proto(path_list->fpl_paths[0])); } int fib_path_list_is_looped (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_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) { /* * we do no share drop nor exclusive path-lists */ if (flags & FIB_PATH_LIST_FLAG_DROP || flags & FIB_PATH_LIST_FLAG_EXCLUSIVE) { flags &= ~FIB_PATH_LIST_FLAG_SHARED; } return (flags); } fib_node_index_t fib_path_list_create (fib_path_list_flags_t flags, const fib_route_path_t *rpaths) { fib_node_index_t path_list_index, old_path_list_index; fib_path_list_t *path_list; int i; flags = fib_path_list_flags_fixup(flags); path_list = fib_path_list_alloc(&path_list_index); path_list->fpl_flags = flags; if (NULL != rpaths) { vec_foreach_index(i, rpaths) { vec_add1(path_list->fpl_paths, fib_path_create(path_list_index, &rpaths[i])); } /* * we sort the paths since the key for the path-list is * the description of the paths it contains. The paths need to * be sorted else this description will differ. */ if (vec_len(path_list->fpl_paths) > 1) { vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort); } } /* * If a shared path list is requested, consult the DB for a match */ if (flags & FIB_PATH_LIST_FLAG_SHARED) { /* * check for a matching path-list in the DB. * If we find one then we can return the existing one and destroy the * new one just created. */ old_path_list_index = fib_path_list_db_find(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 { /* * if there was not a matching path-list, then this * new one will need inserting into the DB and resolving. */ fib_path_list_db_insert(path_list_index); path_list = fib_path_list_resolve(path_list); } } else { /* * no shared path list requested. resolve and use the one * just created. */ path_list = fib_path_list_resolve(path_list); } return (path_list_index); } 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; if (plf & FIB_PATH_LIST_FLAG_DROP) { pf |= FIB_PATH_CFG_FLAG_DROP; } if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE) { pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE; } if (plf & FIB_PATH_LIST_FLAG_LOCAL) { pf |= FIB_PATH_CFG_FLAG_LOCAL; } return (pf); } fib_node_index_t fib_path_list_create_special (dpo_proto_t nh_proto, fib_path_list_flags_t flags, const dpo_id_t *dpo) { fib_node_index_t path_index, path_list_index; fib_path_list_t *path_list; path_list = fib_path_list_alloc(&path_list_index); path_list->fpl_flags = flags; path_index = fib_path_create_special(path_list_index, nh_proto, fib_path_list_flags_2_path_flags(flags), dpo); vec_add1(path_list->fpl_paths, path_index); /* * we don't share path-lists. we can do PIC on them so why bother. */ path_list = fib_path_list_resolve(path_list); return (path_list_index); } /* * return the index info the path-lists's vector of paths, of the matching path. * ~0 if not found */ u32 fib_path_list_find_rpath (fib_node_index_t path_list_index, const fib_route_path_t *rpath) { fib_path_list_t *path_list; u32 ii; path_list = fib_path_list_get(path_list_index); vec_foreach_index (ii, path_list->fpl_paths) { if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath)) { return (ii); } } return (~0); } /* * fib_path_list_copy_and_path_add * * Create a copy of a path-list and append one more path to it. * 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_paths_add (fib_node_index_t path_list_index, const fib_route_path_t *rpaths) { 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 * the alloc result in a realloc */ path_list = fib_path_list_get(path_list_index); ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)); FIB_PATH_LIST_DBG(path_list, "paths-add"); new_path_indices = NULL; vec_validate_init_empty(new_path_indices, vec_len(rpaths) - 1, FIB_NODE_INDEX_INVALID); vec_foreach (path_index, path_list->fpl_paths) { /* * don't add duplicate paths */ int found = 0; vec_foreach_index(ii, rpaths) { 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; } } /* * new_path_indices array contains INVALID for each path not found * and something valid for matches */ vec_foreach_index (ii, new_path_indices) { path_index = &new_path_indices[ii]; rpath = &rpaths[ii]; 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(*path_index); } } FIB_PATH_LIST_DBG(path_list, "paths-added"); return (new_path_indices); } fib_node_index_t 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 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; /* * alloc the new list before we retrieve the old one, lest * the alloc result in a realloc */ path_list = fib_path_list_alloc(&path_list_index); orig_path_list = fib_path_list_get(orig_path_list_index); FIB_PATH_LIST_DBG(orig_path_list, "copy-add"); 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_len(rpaths) - 1)); pi = 0; vec_foreach(orig_path_index, orig_path_list->fpl_paths) { /* * 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 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) { _vec_len(path_list->fpl_paths) = vec_len(path_list->fpl_paths) - 1; fib_path_destroy(new_path_index); } else { 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 * be sorted else this description will differ. */ vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort); FIB_PATH_LIST_DBG(path_list, "path-added"); /* * check for a matching path-list in the DB. * If we find one then we can return the existing one and destroy the * new one just created. */ if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED) { exist_path_list_index = fib_path_list_db_find(path_list); if (FIB_NODE_INDEX_INVALID != exist_path_list_index) { fib_path_list_destroy(path_list); path_list_index = exist_path_list_index; } else { /* * if there was not a matching path-list, then this * new one will need inserting into the DB and resolving. */ fib_path_list_db_insert(path_list_index); path_list = fib_path_list_resolve(path_list); } } else { /* * no shared path list requested. resolve and use the one * just created. */ path_list = fib_path_list_resolve(path_list); } return (path_list_index); } /* * fib_path_list_paths_remove */ 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_indices; fib_path_list_t *path_list; 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(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)); FIB_PATH_LIST_DBG(path_list, "path-remove"); /* * 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 */ vec_foreach_index_backwards(ii, path_list->fpl_paths) { 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[ii]; vec_del1(path_list->fpl_paths, ii); fib_path_destroy(match_path_index); match_path_indices[jj] = match_path_index; } } FIB_PATH_LIST_DBG(path_list, "paths-removed"); return (match_path_indices); } /* * fib_path_list_copy_and_path_remove * * Copy the path-list excluding the path passed. * If the path is the last one, then the index reurned will be invalid. * i.e. the path-list is toast. */ 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 *rpaths) { 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); flags = fib_path_list_flags_fixup(flags); orig_path_list = fib_path_list_get(orig_path_list_index); FIB_PATH_LIST_DBG(orig_path_list, "copy-remove"); path_list->fpl_flags = flags; /* * allocate as many paths as we might need in one go, rather than * using vec_add to do a few at a time. */ 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. */ vec_foreach(orig_path_index, orig_path_list->fpl_paths) { /* * 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); 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 */ if (0 == vec_len(path_list->fpl_paths)) { FIB_PATH_LIST_DBG(path_list, "last-path-removed"); fib_path_list_destroy(path_list); path_list_index = FIB_NODE_INDEX_INVALID; } else { /* * we sort the paths since the key for the path-list is * the description of the paths it contains. The paths need to * be sorted else this description will differ. */ vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort); /* * If a shared path list is requested, consult the DB for a match */ if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED) { fib_node_index_t exist_path_list_index; /* * check for a matching path-list in the DB. * If we find one then we can return the existing one and destroy the * new one just created. */ exist_path_list_index = fib_path_list_db_find(path_list); if (FIB_NODE_INDEX_INVALID != exist_path_list_index) { fib_path_list_destroy(path_list); path_list_index = exist_path_list_index; } else { /* * if there was not a matching path-list, then this * new one will need inserting into the DB and resolving. */ fib_path_list_db_insert(path_list_index); path_list = fib_path_list_resolve(path_list); } } else { /* * no shared path list requested. resolve and use the one * just created. */ path_list = fib_path_list_resolve(path_list); } } return (path_list_index); } /* * fib_path_list_contribute_forwarding * * Return the index of a load-balance that user of this path-list should * use for forwarding */ void fib_path_list_contribute_forwarding (fib_node_index_t path_list_index, fib_forward_chain_type_t fct, fib_path_list_fwd_flags_t flags, dpo_id_t *dpo) { fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); fib_path_list_mk_lb(path_list, fct, dpo, flags); ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type); /* * If there's only one bucket in the load-balance then we can * squash it out. */ if ((1 == load_balance_n_buckets(dpo->dpoi_index)) && (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags)) { dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0)); } } /* * fib_path_list_get_adj * * Return the index of a adjacency for the first path that user of this * path-list should use for forwarding */ adj_index_t fib_path_list_get_adj (fib_node_index_t path_list_index, fib_forward_chain_type_t type) { fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); return (fib_path_get_adj(path_list->fpl_paths[0])); } int fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index, fib_node_index_t **entry_indicies) { fib_node_index_t *path_index; int is_looped, list_looped; fib_path_list_t *path_list; list_looped = 0; path_list = fib_path_list_get(path_list_index); vec_foreach (path_index, path_list->fpl_paths) { fib_node_index_t *copy, **copy_ptr; /* * we need a copy of the nodes visited so that when we add entries * we explore on the nth path and a looped is detected, those entries * are not again searched for n+1 path and so finding a loop that does * not exist. */ copy = vec_dup(*entry_indicies); copy_ptr = © is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr); list_looped += is_looped; vec_free(copy); } FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped); if (list_looped) { path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED; } else { path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED; } return (list_looped); } u32 fib_path_list_child_add (fib_node_index_t path_list_index, fib_node_type_t child_type, fib_node_index_t 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-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. */ 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 fib_path_list_child_remove (fib_node_index_t path_list_index, u32 si) { fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST, path_list_index, si); } void fib_path_list_lock(fib_node_index_t path_list_index) { fib_path_list_t *path_list; if (FIB_NODE_INDEX_INVALID != path_list_index) { path_list = fib_path_list_get(path_list_index); fib_node_lock(&path_list->fpl_node); } } void fib_path_list_unlock (fib_node_index_t path_list_index) { fib_path_list_t *path_list; if (FIB_NODE_INDEX_INVALID != path_list_index) { path_list = fib_path_list_get(path_list_index); fib_node_unlock(&path_list->fpl_node); } } u32 fib_path_list_pool_size (void) { return (pool_elts(fib_path_list_pool)); } u32 fib_path_list_db_size (void) { return (hash_elts(fib_path_list_db)); } void fib_path_list_walk (fib_node_index_t path_list_index, fib_path_list_walk_fn_t func, void *ctx) { fib_node_index_t *path_index; fib_path_list_t *path_list; path_list = fib_path_list_get(path_list_index); vec_foreach(path_index, path_list->fpl_paths) { if (FIB_PATH_LIST_WALK_STOP == func(path_list_index, *path_index, ctx)) break; } } 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_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft); fib_path_list_db = hash_create2 (/* elts */ 0, /* user */ 0, /* value_bytes */ sizeof (fib_node_index_t), fib_path_list_db_hash_key_sum, 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 * show_fib_path_list_command (vlib_main_t * vm, unformat_input_t * input, vlib_cli_command_t * cmd) { fib_path_list_t *path_list; fib_node_index_t pli; if (unformat (input, "%d", &pli)) { /* * show one in detail */ if (!pool_is_free_index(fib_path_list_pool, pli)) { path_list = fib_path_list_get(pli); 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, "%v", s); vec_free(s); } else { vlib_cli_output (vm, "path list %d invalid", pli); } } else { /* * show all */ vlib_cli_output (vm, "FIB Path Lists"); pool_foreach_index (pli, fib_path_list_pool) { vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0); } } return (NULL); } VLIB_CLI_COMMAND (show_fib_path_list, static) = { .path = "show fib path-lists", .function = show_fib_path_list_command, .short_help = "show fib path-lists", };