diff options
Diffstat (limited to 'vnet/vnet/fib/fib_path_list.c')
| -rw-r--r-- | vnet/vnet/fib/fib_path_list.c | 1223 |
1 files changed, 0 insertions, 1223 deletions
diff --git a/vnet/vnet/fib/fib_path_list.c b/vnet/vnet/fib/fib_path_list.c deleted file mode 100644 index 5b35e9b87e7..00000000000 --- a/vnet/vnet/fib/fib_path_list.c +++ /dev/null @@ -1,1223 +0,0 @@ -/* - * 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> - -/** - * 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; - - /** - * The next-hop protocol for the paths in this path list. - * Note that fixing the proto here means we don't support a mix of - * v4 and v6 paths. ho hum. - */ - fib_protocol_t fpl_nh_proto; - - /** - * 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; - -/* - * 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); \ -} -#else -#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) -#endif - -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) -{ -#if CLIB_DEBUG > 0 - ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type); -#endif - 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); -} - -static u8 * -format_fib_path_list (u8 * s, va_list * args) -{ - fib_path_list_attribute_t attr; - fib_node_index_t *path_index; - fib_path_list_t *path_list; - - path_list = va_arg (*args, fib_path_list_t *); - - s = format (s, " index:%u", fib_path_list_get_index(path_list)); - s = format (s, " locks:%u", path_list->fpl_node.fn_locks); - s = format (s, " proto:%U", format_fib_protocol, path_list->fpl_nh_proto); - - 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 = fib_path_format(*path_index, s); - s = format(s, "\n"); - } - - return (s); -} - -u8 * -fib_path_list_adjs_format (fib_node_index_t path_list_index, - u32 indent, - u8 * s) -{ - fib_path_list_t *path_list; - u32 i; - - path_list = fib_path_list_get(path_list_index); - - vec_foreach_index (i, path_list->fpl_paths) - { - s = fib_path_adj_format(path_list->fpl_paths[i], - indent, s); - } - - return (s); -} - - -u8 * -fib_path_list_format (fib_node_index_t path_list_index, - u8 * s) -{ - fib_path_list_t *path_list; - - path_list = fib_path_list_get(path_list_index); - - return (format(s, "%U", format_fib_path_list, path_list)); -} - -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); - - 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); -} - -/* - * 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) -{ - load_balance_path_t *hash_key; - fib_node_index_t *path_index; - - hash_key = NULL; - - if (!dpo_id_is_valid(dpo)) - { - /* - * first time create - */ - dpo_set(dpo, - DPO_LOAD_BALANCE, - fib_forw_chain_type_to_dpo_proto(fct), - load_balance_create(0, - fib_forw_chain_type_to_dpo_proto(fct), - 0 /* FIXME FLOW HASH */)); - } - - /* - * We gather the DPOs from resolved paths. - */ - vec_foreach (path_index, path_list->fpl_paths) - { - hash_key = fib_path_append_nh_for_multipath_hash( - *path_index, - fct, - hash_key); - } - - /* - * Path-list load-balances, which if used, would be shared and hence - * never need a load-balance map. - */ - load_balance_multipath_update(dpo, hash_key, LOAD_BALANCE_FLAG_NONE); - - FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index); - - vec_free(hash_key); -} - -/** - * @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); - - /* - * 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 - { - /* - * many children. schedule a async walk - */ - fib_walk_async(FIB_NODE_TYPE_PATH_LIST, - path_list_index, - FIB_WALK_PRIORITY_LOW, - 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 thier 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 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); - 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; - - if (NULL != path_list_index) - { - *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"); - fib_path_list_mk_urpf(path_list); - - return (path_list); -} - -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); -} - -fib_protocol_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); -} - -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_LOCAL) - { - pf |= FIB_PATH_CFG_FLAG_LOCAL; - } - 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; - } - - return (pf); -} - -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; - /* - * we'll assume for now all paths are the same next-hop protocol - */ - path_list->fpl_nh_proto = rpaths[0].frp_proto; - - vec_foreach_index(i, rpaths) - { - vec_add1(path_list->fpl_paths, - fib_path_create(path_list_index, - path_list->fpl_nh_proto, - fib_path_list_flags_2_path_flags(flags), - &rpaths[i])); - } - - /* - * 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); -} - -fib_node_index_t -fib_path_list_create_special (fib_protocol_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_list->fpl_nh_proto = nh_proto; - - path_index = - fib_path_create_special(path_list_index, - path_list->fpl_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); -} - -/* - * 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_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_path_list_t *path_list, *orig_path_list; - fib_node_index_t path_list_index; - 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 - */ - 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; - path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto; - vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths)); - pi = 0; - - new_path_index = fib_path_create(path_list_index, - path_list->fpl_nh_proto, - fib_path_list_flags_2_path_flags(flags), - rpaths); - - 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)) - { - path_index = fib_path_copy(*orig_path_index, path_list_index); - path_list->fpl_paths[pi++] = path_index; - } - else - { - _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths); - } - } - - 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"); - - /* - * 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_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 path_index, *orig_path_index, path_list_index, tmp_path_index; - fib_path_list_t *path_list, *orig_path_list; - fib_node_index_t pi; - - ASSERT(1 == vec_len(rpaths)); - - 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; - path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto; - /* - * 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); - } - 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, - path_list->fpl_nh_proto, - fib_path_list_flags_2_path_flags(flags), - rpaths); - - 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); - } - } - } - - /* - * done with the temporary now - */ - 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 type, - 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, type, dpo); -} - -/* - * 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; - } - - FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval); - - 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) -{ - return (fib_node_child_add(FIB_NODE_TYPE_PATH_LIST, - path_list_index, - child_type, - child_index)); -} - -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); - FIB_PATH_LIST_DBG(path_list, "lock"); - } -} - -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_PATH_LIST_DBG(path_list, "unlock"); - - 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 (!func(path_list_index, *path_index, 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); -} - -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, "%s", 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(path_list, fib_path_list_pool, - ({ - vlib_cli_output (vm, "%U", format_fib_path_list, path_list); - })); - } - 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", -}; |