2 * Copyright (c) 2016 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 #include <vppinfra/mhash.h>
17 #include <vnet/ip/ip.h>
18 #include <vnet/adj/adj.h>
19 #include <vnet/dpo/load_balance.h>
20 #include <vnet/dpo/load_balance_map.h>
22 #include <vnet/fib/fib_path_list.h>
23 #include <vnet/fib/fib_internal.h>
24 #include <vnet/fib/fib_node_list.h>
25 #include <vnet/fib/fib_walk.h>
26 #include <vnet/fib/fib_urpf_list.h>
27 #include <vnet/fib/fib_path_ext.h>
28 #include <vnet/fib/fib_table.h>
31 * The magic number of child entries that make a path-list popular.
32 * There's a trade-off here between convergence and forwarding speed.
33 * Popular path-lists generate load-balance maps for the entries that
34 * use them. If the map is present there is a switch path cost to indirect
35 * through the map - this indirection provides the fast convergence - so
36 * without the map convergence is slower.
38 #define FIB_PATH_LIST_POPULAR 64
42 * A representation of the list/set of path trough which a prefix is reachable
44 typedef struct fib_path_list_t_ {
46 * A path-list is a node in the FIB graph.
51 * Flags on the path-list
53 fib_path_list_flags_t fpl_flags;
56 * Vector of paths indicies for all configured paths.
57 * For shareable path-lists this list MUST not change.
59 fib_node_index_t *fpl_paths;
62 * the RPF list calculated for this path list
64 fib_node_index_t fpl_urpf;
67 * Hash table of paths. valid only with INDEXED flag
73 * Array of strings/names for the FIB sources
75 static const char *fib_path_list_attr_names[] = FIB_PATH_LIST_ATTRIBUTES;
78 * The memory pool from which we allocate all the path-lists
80 static fib_path_list_t * fib_path_list_pool;
83 * The data-base of shared path-lists
85 static uword *fib_path_list_db;
90 vlib_log_class_t fib_path_list_logger;
95 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
97 vlib_log_debug(fib_path_list_logger, \
99 format_fib_path_list, \
100 fib_path_list_get_index(_pl), 0, \
104 static fib_path_list_t *
105 fib_path_list_get (fib_node_index_t index)
107 return (pool_elt_at_index(fib_path_list_pool, index));
111 fib_path_list_get_node (fib_node_index_t index)
113 return ((fib_node_t*)fib_path_list_get(index));
116 static fib_path_list_t*
117 fib_path_list_from_fib_node (fib_node_t *node)
119 ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type);
120 return ((fib_path_list_t*)node);
123 static fib_node_index_t
124 fib_path_list_get_index (fib_path_list_t *path_list)
126 return (path_list - fib_path_list_pool);
130 format_fib_path_list (u8 * s, va_list * args)
132 fib_node_index_t *path_index, path_list_index;
133 fib_path_list_attribute_t attr;
134 fib_path_list_t *path_list;
137 path_list_index = va_arg (*args, fib_node_index_t);
138 indent = va_arg (*args, u32);
139 path_list = fib_path_list_get(path_list_index);
141 s = format (s, "%Upath-list:[%d]",
142 format_white_space, indent,
143 fib_path_list_get_index(path_list));
144 s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
146 if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
148 s = format (s, " flags:");
149 FOR_EACH_PATH_LIST_ATTRIBUTE(attr)
151 if ((1<<attr) & path_list->fpl_flags)
153 s = format (s, "%s,", fib_path_list_attr_names[attr]);
157 s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
159 vec_foreach (path_index, path_list->fpl_paths)
161 s = format(s, "%U", format_fib_path, *path_index, indent+2,
162 FIB_PATH_FORMAT_FLAGS_NONE);
170 fib_path_list_format (fib_node_index_t path_list_index,
173 return (format(s, "%U", format_fib_path_list, path_list_index, 4));
177 fib_path_list_hash (fib_path_list_t *path_list)
179 uword old_path_list_hash, new_path_list_hash, path_hash;
180 fib_node_index_t *path_index;
186 (vec_len(path_list->fpl_paths) << 16 |
187 (path_list->fpl_flags & FIB_PATH_LIST_KEY_FLAGS));
189 vec_foreach (path_index, path_list->fpl_paths)
191 path_hash = fib_path_hash(*path_index);
193 hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
195 hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
199 return (new_path_list_hash);
203 fib_path_list_db_hash_key_from_index (uword index)
209 fib_path_list_db_hash_key_is_index (uword key)
215 fib_path_list_db_hash_key_2_index (uword key)
217 ASSERT (fib_path_list_db_hash_key_is_index (key));
221 static fib_path_list_t*
222 fib_path_list_db_get_from_hash_key (uword key)
224 fib_path_list_t *path_list;
226 if (fib_path_list_db_hash_key_is_index (key))
228 fib_node_index_t path_list_index;
230 path_list_index = fib_path_list_db_hash_key_2_index(key);
231 path_list = fib_path_list_get(path_list_index);
235 path_list = uword_to_pointer (key, fib_path_list_t *);
242 fib_path_list_db_hash_key_sum (hash_t * h,
245 fib_path_list_t *path_list;
247 path_list = fib_path_list_db_get_from_hash_key(key);
249 return (fib_path_list_hash(path_list));
253 fib_path_list_db_hash_key_equal (hash_t * h,
257 fib_path_list_t *path_list1, *path_list2;
259 path_list1 = fib_path_list_db_get_from_hash_key(key1);
260 path_list2 = fib_path_list_db_get_from_hash_key(key2);
262 return (fib_path_list_hash(path_list1) ==
263 fib_path_list_hash(path_list2));
266 static fib_node_index_t
267 fib_path_list_db_find (fib_path_list_t *path_list)
271 p = hash_get(fib_path_list_db, path_list);
278 return (FIB_NODE_INDEX_INVALID);
282 fib_path_list_db_insert (fib_node_index_t path_list_index)
284 fib_path_list_t *path_list;
286 path_list = fib_path_list_get(path_list_index);
288 ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list));
290 hash_set (fib_path_list_db,
291 fib_path_list_db_hash_key_from_index(path_list_index),
294 FIB_PATH_LIST_DBG(path_list, "DB-inserted");
298 fib_path_list_db_remove (fib_node_index_t path_list_index)
300 fib_path_list_t *path_list;
302 path_list = fib_path_list_get(path_list_index);
304 ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list));
306 hash_unset(fib_path_list_db,
307 fib_path_list_db_hash_key_from_index(path_list_index));
309 FIB_PATH_LIST_DBG(path_list, "DB-removed");
313 fib_path_list_destroy (fib_path_list_t *path_list)
315 fib_node_index_t *path_index;
317 FIB_PATH_LIST_DBG(path_list, "destroy");
319 vec_foreach (path_index, path_list->fpl_paths)
321 fib_path_destroy(*path_index);
324 vec_free(path_list->fpl_paths);
325 fib_urpf_list_unlock(path_list->fpl_urpf);
327 fib_node_deinit(&path_list->fpl_node);
328 pool_put(fib_path_list_pool, path_list);
332 fib_path_list_last_lock_gone (fib_node_t *node)
334 fib_path_list_t *path_list;
336 path_list = fib_path_list_from_fib_node(node);
338 FIB_PATH_LIST_DBG(path_list, "last-lock");
340 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
342 fib_path_list_db_remove(fib_path_list_get_index(path_list));
344 fib_path_list_destroy(path_list);
347 static load_balance_flags_t
348 fib_path_list_fwd_flags_2_load_balance (fib_path_list_fwd_flags_t pl_flags)
350 load_balance_flags_t lb_flags = LOAD_BALANCE_FLAG_NONE;
352 if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY)
354 lb_flags |= LOAD_BALANCE_ATTR_STICKY;
362 * update the multipath adj this path-list will contribute to its
363 * children's forwarding.
366 fib_path_list_mk_lb (fib_path_list_t *path_list,
367 fib_forward_chain_type_t fct,
369 fib_path_list_fwd_flags_t flags)
371 fib_node_index_t *path_index;
372 load_balance_path_t *nhs;
376 dproto = fib_forw_chain_type_to_dpo_proto(fct);
379 * We gather the DPOs from resolved paths.
381 vec_foreach (path_index, path_list->fpl_paths)
383 if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) ||
384 fib_path_is_resolved(*path_index))
386 nhs = fib_path_append_nh_for_multipath_hash(*path_index,
392 * Path-list load-balances, which if used, would be shared and hence
393 * never need a load-balance map.
398 load_balance_create(vec_len(nhs),
400 load_balance_get_default_flow_hash(dproto)));
401 load_balance_multipath_update(dpo, nhs,
402 fib_path_list_fwd_flags_2_load_balance(flags));
404 FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
410 * @brief [re]build the path list's uRPF list
413 fib_path_list_mk_urpf (fib_path_list_t *path_list)
415 fib_node_index_t *path_index;
418 * ditch the old one. by iterating through all paths we are going
419 * to re-find all the adjs that were in the old one anyway. If we
420 * keep the old one, then the |sort|uniq requires more work.
421 * All users of the RPF list have their own lock, so we can release
424 fib_urpf_list_unlock(path_list->fpl_urpf);
425 path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
427 vec_foreach (path_index, path_list->fpl_paths)
429 fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
432 fib_urpf_list_bake(path_list->fpl_urpf);
436 * @brief Contribute (add) this path list's uRPF list. This allows the child
437 * to construct an aggregate list.
440 fib_path_list_contribute_urpf (fib_node_index_t path_list_index,
443 fib_path_list_t *path_list;
445 path_list = fib_path_list_get(path_list_index);
447 fib_urpf_list_combine(urpf, path_list->fpl_urpf);
451 * @brief Return the the child the RPF list pre-built for this path list
454 fib_path_list_get_urpf (fib_node_index_t path_list_index)
456 fib_path_list_t *path_list;
458 path_list = fib_path_list_get(path_list_index);
460 return (path_list->fpl_urpf);
464 * fib_path_list_back_walk
466 * Called from one of this path-list's paths to progate
470 fib_path_list_back_walk (fib_node_index_t path_list_index,
471 fib_node_back_walk_ctx_t *ctx)
473 fib_path_list_t *path_list;
475 path_list = fib_path_list_get(path_list_index);
477 fib_path_list_mk_urpf(path_list);
479 FIB_PATH_LIST_DBG(path_list, "bw:%U",
480 format_fib_node_bw_reason, ctx->fnbw_reason);
483 * propagate the backwalk further
485 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
488 * many children. schedule a async walk
490 fib_walk_async(FIB_NODE_TYPE_PATH_LIST,
492 FIB_WALK_PRIORITY_LOW,
498 * only a few children. continue the walk synchronously
500 fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
505 * fib_path_list_back_walk_notify
507 * A back walk has reach this path-list.
509 static fib_node_back_walk_rc_t
510 fib_path_list_back_walk_notify (fib_node_t *node,
511 fib_node_back_walk_ctx_t *ctx)
514 * the path-list is not a direct child of any other node type
515 * paths, which do not change their to-list-mapping, save the
516 * list they are a member of, and invoke the BW function directly.
520 return (FIB_NODE_BACK_WALK_CONTINUE);
524 * Display the path-list memory usage
527 fib_path_list_memory_show (void)
529 fib_show_memory_usage("Path-list",
530 pool_elts(fib_path_list_pool),
531 pool_len(fib_path_list_pool),
532 sizeof(fib_path_list_t));
533 fib_urpf_list_show_mem();
537 * The FIB path-list's graph node virtual function table
539 static const fib_node_vft_t fib_path_list_vft = {
540 .fnv_get = fib_path_list_get_node,
541 .fnv_last_lock = fib_path_list_last_lock_gone,
542 .fnv_back_walk = fib_path_list_back_walk_notify,
543 .fnv_mem_show = fib_path_list_memory_show,
546 static inline fib_path_list_t *
547 fib_path_list_alloc (fib_node_index_t *path_list_index)
549 fib_path_list_t *path_list;
551 pool_get(fib_path_list_pool, path_list);
552 clib_memset(path_list, 0, sizeof(*path_list));
554 fib_node_init(&path_list->fpl_node,
555 FIB_NODE_TYPE_PATH_LIST);
556 path_list->fpl_urpf = INDEX_INVALID;
557 path_list->fpl_paths = NULL;
559 *path_list_index = fib_path_list_get_index(path_list);
561 FIB_PATH_LIST_DBG(path_list, "alloc");
566 static fib_path_list_t *
567 fib_path_list_resolve (fib_path_list_t *path_list)
569 fib_node_index_t *path_index, *paths, path_list_index;
571 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED));
574 * resolving a path-list is a recursive action. this means more path
575 * lists can be created during this call, and hence this path-list
576 * can be realloc'd. so we work with copies.
577 * this function is called only once per-path list, so its no great overhead.
579 path_list_index = fib_path_list_get_index(path_list);
580 paths = vec_dup(path_list->fpl_paths);
582 vec_foreach (path_index, paths)
584 fib_path_resolve(*path_index);
588 path_list = fib_path_list_get(path_list_index);
590 FIB_PATH_LIST_DBG(path_list, "resovled");
592 if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
594 fib_path_list_mk_urpf(path_list);
600 fib_path_list_get_n_paths (fib_node_index_t path_list_index)
602 fib_path_list_t *path_list;
604 if (FIB_NODE_INDEX_INVALID == path_list_index)
609 path_list = fib_path_list_get(path_list_index);
611 return (vec_len(path_list->fpl_paths));
616 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index)
618 fib_node_index_t *path_index;
619 fib_path_list_t *path_list;
622 path_list = fib_path_list_get(path_list_index);
625 vec_foreach (path_index, path_list->fpl_paths)
627 sw_if_index = fib_path_get_resolving_interface(*path_index);
628 if (~0 != sw_if_index)
630 return (sw_if_index);
634 return (sw_if_index);
638 fib_path_list_get_proto (fib_node_index_t path_list_index)
640 fib_path_list_t *path_list;
642 path_list = fib_path_list_get(path_list_index);
645 * we don't support a mix of path protocols, so we can return the proto
648 return (fib_path_get_proto(path_list->fpl_paths[0]));
652 fib_path_list_is_looped (fib_node_index_t path_list_index)
654 fib_path_list_t *path_list;
656 path_list = fib_path_list_get(path_list_index);
658 return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
662 fib_path_list_is_popular (fib_node_index_t path_list_index)
664 fib_path_list_t *path_list;
666 path_list = fib_path_list_get(path_list_index);
668 return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
671 static fib_path_list_flags_t
672 fib_path_list_flags_fixup (fib_path_list_flags_t flags)
675 * we do no share drop nor exclusive path-lists
677 if (flags & FIB_PATH_LIST_FLAG_DROP ||
678 flags & FIB_PATH_LIST_FLAG_EXCLUSIVE)
680 flags &= ~FIB_PATH_LIST_FLAG_SHARED;
687 fib_path_list_create (fib_path_list_flags_t flags,
688 const fib_route_path_t *rpaths)
690 fib_node_index_t path_list_index, old_path_list_index;
691 fib_path_list_t *path_list;
694 flags = fib_path_list_flags_fixup(flags);
695 path_list = fib_path_list_alloc(&path_list_index);
696 path_list->fpl_flags = flags;
700 vec_foreach_index(i, rpaths)
702 vec_add1(path_list->fpl_paths,
703 fib_path_create(path_list_index,
707 * we sort the paths since the key for the path-list is
708 * the description of the paths it contains. The paths need to
709 * be sorted else this description will differ.
711 if (vec_len(path_list->fpl_paths) > 1)
713 vec_sort_with_function(path_list->fpl_paths,
714 fib_path_cmp_for_sort);
719 * If a shared path list is requested, consult the DB for a match
721 if (flags & FIB_PATH_LIST_FLAG_SHARED)
724 * check for a matching path-list in the DB.
725 * If we find one then we can return the existing one and destroy the
726 * new one just created.
728 old_path_list_index = fib_path_list_db_find(path_list);
729 if (FIB_NODE_INDEX_INVALID != old_path_list_index)
731 fib_path_list_destroy(path_list);
733 path_list_index = old_path_list_index;
738 * if there was not a matching path-list, then this
739 * new one will need inserting into the DB and resolving.
741 fib_path_list_db_insert(path_list_index);
742 path_list = fib_path_list_resolve(path_list);
748 * no shared path list requested. resolve and use the one
751 path_list = fib_path_list_resolve(path_list);
754 return (path_list_index);
757 static fib_path_cfg_flags_t
758 fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
760 fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
762 if (plf & FIB_PATH_LIST_FLAG_DROP)
764 pf |= FIB_PATH_CFG_FLAG_DROP;
766 if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE)
768 pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
770 if (plf & FIB_PATH_LIST_FLAG_LOCAL)
772 pf |= FIB_PATH_CFG_FLAG_LOCAL;
779 fib_path_list_create_special (dpo_proto_t nh_proto,
780 fib_path_list_flags_t flags,
783 fib_node_index_t path_index, path_list_index;
784 fib_path_list_t *path_list;
786 path_list = fib_path_list_alloc(&path_list_index);
787 path_list->fpl_flags = flags;
790 fib_path_create_special(path_list_index,
792 fib_path_list_flags_2_path_flags(flags),
794 vec_add1(path_list->fpl_paths, path_index);
797 * we don't share path-lists. we can do PIC on them so why bother.
799 path_list = fib_path_list_resolve(path_list);
801 return (path_list_index);
805 * return the index info the path-lists's vector of paths, of the matching path.
809 fib_path_list_find_rpath (fib_node_index_t path_list_index,
810 const fib_route_path_t *rpath)
812 fib_path_list_t *path_list;
815 path_list = fib_path_list_get(path_list_index);
817 vec_foreach_index (ii, path_list->fpl_paths)
819 if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
829 * fib_path_list_copy_and_path_add
831 * Create a copy of a path-list and append one more path to it.
832 * The path-list returned could either have been newly created, or
833 * can be a shared path-list from the data-base.
836 fib_path_list_paths_add (fib_node_index_t path_list_index,
837 const fib_route_path_t *rpaths)
839 fib_node_index_t *new_path_indices, *path_index;
840 const fib_route_path_t *rpath;
841 fib_path_list_t *path_list;
845 * alloc the new list before we retrieve the old one, lest
846 * the alloc result in a realloc
848 path_list = fib_path_list_get(path_list_index);
850 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
852 FIB_PATH_LIST_DBG(path_list, "paths-add");
854 new_path_indices = NULL;
855 vec_validate_init_empty(new_path_indices,
857 FIB_NODE_INDEX_INVALID);
859 vec_foreach (path_index, path_list->fpl_paths)
862 * don't add duplicate paths
866 vec_foreach_index(ii, rpaths)
869 if (0 == fib_path_cmp_w_route_path(*path_index, rpath))
877 new_path_indices[ii] = *path_index;
882 * new_path_indices array contains INVALID for each path not found
883 * and something valid for matches
885 vec_foreach_index (ii, new_path_indices)
887 path_index = &new_path_indices[ii];
890 if (FIB_NODE_INDEX_INVALID == *path_index)
892 *path_index = fib_path_create(path_list_index, rpath);
894 * Add the new path - no sort, no sharing, no key..
896 vec_add1(path_list->fpl_paths, *path_index);
899 * no shared path list requested. resolve and use the one
902 fib_path_resolve(*path_index);
906 FIB_PATH_LIST_DBG(path_list, "paths-added");
908 return (new_path_indices);
912 fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
913 fib_path_list_flags_t flags,
914 const fib_route_path_t *rpaths)
916 fib_node_index_t new_path_index, *orig_path_index;
917 fib_path_list_t *path_list, *orig_path_list;
918 fib_node_index_t exist_path_list_index;
919 fib_node_index_t path_list_index;
920 const fib_route_path_t *rpath;
924 * alloc the new list before we retrieve the old one, lest
925 * the alloc result in a realloc
927 path_list = fib_path_list_alloc(&path_list_index);
929 orig_path_list = fib_path_list_get(orig_path_list_index);
931 FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
933 flags = fib_path_list_flags_fixup(flags);
934 path_list->fpl_flags = flags;
936 vec_validate(path_list->fpl_paths,
937 (vec_len(orig_path_list->fpl_paths) +
938 vec_len(rpaths) - 1));
941 vec_foreach(orig_path_index, orig_path_list->fpl_paths)
944 * copy the original paths over to the new list
946 path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
949 vec_foreach(rpath, rpaths)
953 new_path_index = fib_path_create(path_list_index, rpath);
955 vec_foreach(orig_path_index, orig_path_list->fpl_paths)
958 * don't add duplicate paths
959 * In the unlikely event the path is a duplicate, then we'll
960 * find a matching path-list later and this one will be toast.
962 if (0 == fib_path_cmp(new_path_index, *orig_path_index))
970 _vec_len(path_list->fpl_paths) =
971 vec_len(path_list->fpl_paths) - 1;
972 fib_path_destroy(new_path_index);
976 path_list->fpl_paths[pi++] = new_path_index;
981 * we sort the paths since the key for the path-list is
982 * the description of the paths it contains. The paths need to
983 * be sorted else this description will differ.
985 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
987 FIB_PATH_LIST_DBG(path_list, "path-added");
990 * check for a matching path-list in the DB.
991 * If we find one then we can return the existing one and destroy the
992 * new one just created.
994 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
996 exist_path_list_index = fib_path_list_db_find(path_list);
997 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
999 fib_path_list_destroy(path_list);
1001 path_list_index = exist_path_list_index;
1006 * if there was not a matching path-list, then this
1007 * new one will need inserting into the DB and resolving.
1009 fib_path_list_db_insert(path_list_index);
1011 path_list = fib_path_list_resolve(path_list);
1017 * no shared path list requested. resolve and use the one
1020 path_list = fib_path_list_resolve(path_list);
1023 return (path_list_index);
1027 * fib_path_list_paths_remove
1030 fib_path_list_paths_remove (fib_node_index_t path_list_index,
1031 const fib_route_path_t *rpaths)
1033 fib_node_index_t *match_path_indices;
1034 fib_path_list_t *path_list;
1037 path_list = fib_path_list_get(path_list_index);
1038 match_path_indices = NULL;
1039 vec_validate_init_empty(match_path_indices,
1040 vec_len(rpaths) - 1,
1041 FIB_NODE_INDEX_INVALID);
1043 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
1045 FIB_PATH_LIST_DBG(path_list, "path-remove");
1048 * the number of existing paths is likely to be larger than the
1049 * number of paths being added.
1050 * walk in reverse so the vec_del is ok
1052 vec_foreach_index_backwards(ii, path_list->fpl_paths)
1056 vec_foreach_index(jj, rpaths)
1058 if (0 == fib_path_cmp_w_route_path(path_list->fpl_paths[ii],
1067 fib_node_index_t match_path_index;
1071 match_path_index = path_list->fpl_paths[ii];
1072 vec_del1(path_list->fpl_paths, ii);
1073 fib_path_destroy(match_path_index);
1074 match_path_indices[jj] = match_path_index;
1078 FIB_PATH_LIST_DBG(path_list, "paths-removed");
1080 return (match_path_indices);
1084 * fib_path_list_copy_and_path_remove
1086 * Copy the path-list excluding the path passed.
1087 * If the path is the last one, then the index reurned will be invalid.
1088 * i.e. the path-list is toast.
1091 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
1092 fib_path_list_flags_t flags,
1093 const fib_route_path_t *rpaths)
1095 fib_node_index_t *orig_path_index, path_list_index, tmp_path_index;
1096 fib_path_list_t *path_list, *orig_path_list;
1097 const fib_route_path_t *rpath;
1098 fib_node_index_t pi;
1100 path_list = fib_path_list_alloc(&path_list_index);
1102 flags = fib_path_list_flags_fixup(flags);
1103 orig_path_list = fib_path_list_get(orig_path_list_index);
1105 FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1107 path_list->fpl_flags = flags;
1109 * allocate as many paths as we might need in one go, rather than
1110 * using vec_add to do a few at a time.
1112 vec_validate(path_list->fpl_paths,
1113 vec_len(orig_path_list->fpl_paths) - 1);
1117 * create a representation of the path to be removed, so it
1118 * can be used as a comparison object during the copy.
1120 vec_foreach(orig_path_index, orig_path_list->fpl_paths)
1123 * copy the original paths over to the new list
1125 path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
1128 vec_foreach(rpath, rpaths)
1131 tmp_path_index = fib_path_create(path_list_index, rpath);
1133 vec_foreach_index(pi, path_list->fpl_paths)
1135 if (0 == fib_path_cmp(tmp_path_index, path_list->fpl_paths[pi]))
1143 fib_path_destroy(path_list->fpl_paths[pi]);
1144 vec_del1(path_list->fpl_paths, pi);
1146 fib_path_destroy(tmp_path_index);
1150 * if there are no paths, then the new path-list is aborted
1152 if (0 == vec_len(path_list->fpl_paths)) {
1153 FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1155 fib_path_list_destroy(path_list);
1157 path_list_index = FIB_NODE_INDEX_INVALID;
1160 * we sort the paths since the key for the path-list is
1161 * the description of the paths it contains. The paths need to
1162 * be sorted else this description will differ.
1164 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
1167 * If a shared path list is requested, consult the DB for a match
1169 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1171 fib_node_index_t exist_path_list_index;
1174 * check for a matching path-list in the DB.
1175 * If we find one then we can return the existing one and destroy the
1176 * new one just created.
1178 exist_path_list_index = fib_path_list_db_find(path_list);
1179 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1181 fib_path_list_destroy(path_list);
1183 path_list_index = exist_path_list_index;
1188 * if there was not a matching path-list, then this
1189 * new one will need inserting into the DB and resolving.
1191 fib_path_list_db_insert(path_list_index);
1193 path_list = fib_path_list_resolve(path_list);
1199 * no shared path list requested. resolve and use the one
1202 path_list = fib_path_list_resolve(path_list);
1206 return (path_list_index);
1210 * fib_path_list_contribute_forwarding
1212 * Return the index of a load-balance that user of this path-list should
1213 * use for forwarding
1216 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
1217 fib_forward_chain_type_t fct,
1218 fib_path_list_fwd_flags_t flags,
1221 fib_path_list_t *path_list;
1223 path_list = fib_path_list_get(path_list_index);
1225 fib_path_list_mk_lb(path_list, fct, dpo, flags);
1227 ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type);
1230 * If there's only one bucket in the load-balance then we can
1233 if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1234 (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags))
1236 dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0));
1241 * fib_path_list_get_adj
1243 * Return the index of a adjacency for the first path that user of this
1244 * path-list should use for forwarding
1247 fib_path_list_get_adj (fib_node_index_t path_list_index,
1248 fib_forward_chain_type_t type)
1250 fib_path_list_t *path_list;
1252 path_list = fib_path_list_get(path_list_index);
1253 return (fib_path_get_adj(path_list->fpl_paths[0]));
1257 fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
1258 fib_node_index_t **entry_indicies)
1260 fib_node_index_t *path_index;
1261 int is_looped, list_looped;
1262 fib_path_list_t *path_list;
1265 path_list = fib_path_list_get(path_list_index);
1267 vec_foreach (path_index, path_list->fpl_paths)
1269 fib_node_index_t *copy, **copy_ptr;
1272 * we need a copy of the nodes visited so that when we add entries
1273 * we explore on the nth path and a looped is detected, those entries
1274 * are not again searched for n+1 path and so finding a loop that does
1277 copy = vec_dup(*entry_indicies);
1280 is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1281 list_looped += is_looped;
1286 FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1290 path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1294 path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1297 return (list_looped);
1301 fib_path_list_child_add (fib_node_index_t path_list_index,
1302 fib_node_type_t child_type,
1303 fib_node_index_t child_index)
1307 sibling = fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
1312 if (FIB_PATH_LIST_POPULAR == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST,
1316 * Set the popular flag on the path-list once we pass the magic
1317 * threshold. then walk children to update.
1318 * We don't undo this action. The rational being that the number
1319 * of entries using this prefix is large enough such that it is a
1320 * non-trival amount of effort to converge them. If we get into the
1321 * situation where we are adding and removing entries such that we
1322 * flip-flop over the threshold, then this non-trivial work is added
1323 * to each of those routes adds/deletes - not a situation we want.
1325 fib_node_back_walk_ctx_t ctx = {
1326 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1328 fib_path_list_t *path_list;
1330 path_list = fib_path_list_get(path_list_index);
1331 path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1333 fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1340 fib_path_list_child_remove (fib_node_index_t path_list_index,
1343 fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
1349 fib_path_list_lock(fib_node_index_t path_list_index)
1351 fib_path_list_t *path_list;
1353 if (FIB_NODE_INDEX_INVALID != path_list_index)
1355 path_list = fib_path_list_get(path_list_index);
1357 fib_node_lock(&path_list->fpl_node);
1362 fib_path_list_unlock (fib_node_index_t path_list_index)
1364 fib_path_list_t *path_list;
1366 if (FIB_NODE_INDEX_INVALID != path_list_index)
1368 path_list = fib_path_list_get(path_list_index);
1370 fib_node_unlock(&path_list->fpl_node);
1375 fib_path_list_pool_size (void)
1377 return (pool_elts(fib_path_list_pool));
1381 fib_path_list_db_size (void)
1383 return (hash_elts(fib_path_list_db));
1387 fib_path_list_walk (fib_node_index_t path_list_index,
1388 fib_path_list_walk_fn_t func,
1391 fib_node_index_t *path_index;
1392 fib_path_list_t *path_list;
1394 path_list = fib_path_list_get(path_list_index);
1396 vec_foreach(path_index, path_list->fpl_paths)
1398 if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1406 fib_path_list_walk_w_ext (fib_node_index_t path_list_index,
1407 const fib_path_ext_list_t *ext_list,
1408 fib_path_list_walk_w_ext_fn_t func,
1411 fib_node_index_t *path_index;
1412 fib_path_list_t *path_list;
1413 fib_path_ext_t *path_ext;
1415 path_list = fib_path_list_get(path_list_index);
1417 vec_foreach(path_index, path_list->fpl_paths)
1419 path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
1421 if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1430 fib_path_list_module_init (void)
1432 fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1434 fib_path_list_db = hash_create2 (/* elts */ 0,
1436 /* value_bytes */ sizeof (fib_node_index_t),
1437 fib_path_list_db_hash_key_sum,
1438 fib_path_list_db_hash_key_equal,
1439 /* format pair/arg */
1441 fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1444 static clib_error_t *
1445 show_fib_path_list_command (vlib_main_t * vm,
1446 unformat_input_t * input,
1447 vlib_cli_command_t * cmd)
1449 fib_path_list_t *path_list;
1450 fib_node_index_t pli;
1452 if (unformat (input, "%d", &pli))
1455 * show one in detail
1457 if (!pool_is_free_index(fib_path_list_pool, pli))
1459 path_list = fib_path_list_get(pli);
1460 u8 *s = fib_path_list_format(pli, NULL);
1461 s = format(s, "children:");
1462 s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1463 vlib_cli_output (vm, "%v", s);
1468 vlib_cli_output (vm, "path list %d invalid", pli);
1476 vlib_cli_output (vm, "FIB Path Lists");
1477 pool_foreach_index (pli, fib_path_list_pool,
1479 vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1485 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1486 .path = "show fib path-lists",
1487 .function = show_fib_path_list_command,
1488 .short_help = "show fib path-lists",