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>
29 * The magic number of child entries that make a path-list popular.
30 * There's a trade-off here between convergnece and forwarding speed.
31 * Popular path-lists generate load-balance maps for the entires that
32 * use them. If the map is present there is a switch path cost to indirect
33 * through the map - this indirection provides the fast convergence - so
34 * without the map convergence is slower.
36 #define FIB_PATH_LIST_POPULAR 64
40 * A representation of the list/set of path trough which a prefix is reachable
42 typedef struct fib_path_list_t_ {
44 * A path-list is a node in the FIB graph.
49 * Flags on the path-list
51 fib_path_list_flags_t fpl_flags;
54 * Vector of paths indicies for all configured paths.
55 * For shareable path-lists this list MUST not change.
57 fib_node_index_t *fpl_paths;
60 * the RPF list calculated for this path list
62 fib_node_index_t fpl_urpf;
65 * Hash table of paths. valid only with INDEXED flag
71 * Array of strings/names for the FIB sources
73 static const char *fib_path_list_attr_names[] = FIB_PATH_LIST_ATTRIBUTES;
76 * The memory pool from which we allocate all the path-lists
78 static fib_path_list_t * fib_path_list_pool;
81 * The data-base of shared path-lists
83 static uword *fib_path_list_db;
88 vlib_log_class_t fib_path_list_logger;
93 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
95 vlib_log_debug(fib_path_list_logger, \
97 format_fib_path_list, \
98 fib_path_list_get_index(_pl), 0, \
102 static fib_path_list_t *
103 fib_path_list_get (fib_node_index_t index)
105 return (pool_elt_at_index(fib_path_list_pool, index));
109 fib_path_list_get_node (fib_node_index_t index)
111 return ((fib_node_t*)fib_path_list_get(index));
114 static fib_path_list_t*
115 fib_path_list_from_fib_node (fib_node_t *node)
117 ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type);
118 return ((fib_path_list_t*)node);
121 static fib_node_index_t
122 fib_path_list_get_index (fib_path_list_t *path_list)
124 return (path_list - fib_path_list_pool);
128 format_fib_path_list (u8 * s, va_list * args)
130 fib_node_index_t *path_index, path_list_index;
131 fib_path_list_attribute_t attr;
132 fib_path_list_t *path_list;
135 path_list_index = va_arg (*args, fib_node_index_t);
136 indent = va_arg (*args, u32);
137 path_list = fib_path_list_get(path_list_index);
139 s = format (s, "%Upath-list:[%d]",
140 format_white_space, indent,
141 fib_path_list_get_index(path_list));
142 s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
144 if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
146 s = format (s, " flags:");
147 FOR_EACH_PATH_LIST_ATTRIBUTE(attr)
149 if ((1<<attr) & path_list->fpl_flags)
151 s = format (s, "%s,", fib_path_list_attr_names[attr]);
155 s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
157 vec_foreach (path_index, path_list->fpl_paths)
159 s = format(s, "%U", format_fib_path, *path_index, indent+2,
160 FIB_PATH_FORMAT_FLAGS_NONE);
168 fib_path_list_format (fib_node_index_t path_list_index,
171 return (format(s, "%U", format_fib_path_list, path_list_index, 4));
175 fib_path_list_hash (fib_path_list_t *path_list)
177 uword old_path_list_hash, new_path_list_hash, path_hash;
178 fib_node_index_t *path_index;
182 new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths);
184 vec_foreach (path_index, path_list->fpl_paths)
186 path_hash = fib_path_hash(*path_index);
188 hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
190 hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
194 return (new_path_list_hash);
198 fib_path_list_db_hash_key_from_index (uword index)
204 fib_path_list_db_hash_key_is_index (uword key)
210 fib_path_list_db_hash_key_2_index (uword key)
212 ASSERT (fib_path_list_db_hash_key_is_index (key));
216 static fib_path_list_t*
217 fib_path_list_db_get_from_hash_key (uword key)
219 fib_path_list_t *path_list;
221 if (fib_path_list_db_hash_key_is_index (key))
223 fib_node_index_t path_list_index;
225 path_list_index = fib_path_list_db_hash_key_2_index(key);
226 path_list = fib_path_list_get(path_list_index);
230 path_list = uword_to_pointer (key, fib_path_list_t *);
237 fib_path_list_db_hash_key_sum (hash_t * h,
240 fib_path_list_t *path_list;
242 path_list = fib_path_list_db_get_from_hash_key(key);
244 return (fib_path_list_hash(path_list));
248 fib_path_list_db_hash_key_equal (hash_t * h,
252 fib_path_list_t *path_list1, *path_list2;
254 path_list1 = fib_path_list_db_get_from_hash_key(key1);
255 path_list2 = fib_path_list_db_get_from_hash_key(key2);
257 return (fib_path_list_hash(path_list1) ==
258 fib_path_list_hash(path_list2));
261 static fib_node_index_t
262 fib_path_list_db_find (fib_path_list_t *path_list)
266 p = hash_get(fib_path_list_db, path_list);
273 return (FIB_NODE_INDEX_INVALID);
277 fib_path_list_db_insert (fib_node_index_t path_list_index)
279 fib_path_list_t *path_list;
281 path_list = fib_path_list_get(path_list_index);
283 ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list));
285 hash_set (fib_path_list_db,
286 fib_path_list_db_hash_key_from_index(path_list_index),
289 FIB_PATH_LIST_DBG(path_list, "DB-inserted");
293 fib_path_list_db_remove (fib_node_index_t path_list_index)
295 fib_path_list_t *path_list;
297 path_list = fib_path_list_get(path_list_index);
299 ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list));
301 hash_unset(fib_path_list_db,
302 fib_path_list_db_hash_key_from_index(path_list_index));
304 FIB_PATH_LIST_DBG(path_list, "DB-removed");
308 fib_path_list_destroy (fib_path_list_t *path_list)
310 fib_node_index_t *path_index;
312 FIB_PATH_LIST_DBG(path_list, "destroy");
314 vec_foreach (path_index, path_list->fpl_paths)
316 fib_path_destroy(*path_index);
319 vec_free(path_list->fpl_paths);
320 fib_urpf_list_unlock(path_list->fpl_urpf);
322 fib_node_deinit(&path_list->fpl_node);
323 pool_put(fib_path_list_pool, path_list);
327 fib_path_list_last_lock_gone (fib_node_t *node)
329 fib_path_list_t *path_list;
331 path_list = fib_path_list_from_fib_node(node);
333 FIB_PATH_LIST_DBG(path_list, "last-lock");
335 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
337 fib_path_list_db_remove(fib_path_list_get_index(path_list));
339 fib_path_list_destroy(path_list);
342 static load_balance_flags_t
343 fib_path_list_fwd_flags_2_load_balance (fib_path_list_fwd_flags_t pl_flags)
345 load_balance_flags_t lb_flags = LOAD_BALANCE_FLAG_NONE;
347 if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY)
349 lb_flags |= LOAD_BALANCE_ATTR_STICKY;
357 * update the multipath adj this path-list will contribute to its
358 * children's forwarding.
361 fib_path_list_mk_lb (fib_path_list_t *path_list,
362 fib_forward_chain_type_t fct,
364 fib_path_list_fwd_flags_t flags)
366 load_balance_path_t *nhs;
367 fib_node_index_t *path_index;
372 * We gather the DPOs from resolved paths.
374 vec_foreach (path_index, path_list->fpl_paths)
376 if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) ||
377 fib_path_is_resolved(*path_index))
379 nhs = fib_path_append_nh_for_multipath_hash(*path_index,
385 * Path-list load-balances, which if used, would be shared and hence
386 * never need a load-balance map.
390 fib_forw_chain_type_to_dpo_proto(fct),
391 load_balance_create(vec_len(nhs),
392 fib_forw_chain_type_to_dpo_proto(fct),
393 0 /* FIXME FLOW HASH */));
394 load_balance_multipath_update(dpo, nhs,
395 fib_path_list_fwd_flags_2_load_balance(flags));
397 FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
403 * @brief [re]build the path list's uRPF list
406 fib_path_list_mk_urpf (fib_path_list_t *path_list)
408 fib_node_index_t *path_index;
411 * ditch the old one. by iterating through all paths we are going
412 * to re-find all the adjs that were in the old one anyway. If we
413 * keep the old one, then the |sort|uniq requires more work.
414 * All users of the RPF list have their own lock, so we can release
417 fib_urpf_list_unlock(path_list->fpl_urpf);
418 path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
420 vec_foreach (path_index, path_list->fpl_paths)
422 fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
425 fib_urpf_list_bake(path_list->fpl_urpf);
429 * @brief Contribute (add) this path list's uRPF list. This allows the child
430 * to construct an aggregate list.
433 fib_path_list_contribute_urpf (fib_node_index_t path_list_index,
436 fib_path_list_t *path_list;
438 path_list = fib_path_list_get(path_list_index);
440 fib_urpf_list_combine(urpf, path_list->fpl_urpf);
444 * @brief Return the the child the RPF list pre-built for this path list
447 fib_path_list_get_urpf (fib_node_index_t path_list_index)
449 fib_path_list_t *path_list;
451 path_list = fib_path_list_get(path_list_index);
453 return (path_list->fpl_urpf);
457 * fib_path_list_back_walk
459 * Called from one of this path-list's paths to progate
463 fib_path_list_back_walk (fib_node_index_t path_list_index,
464 fib_node_back_walk_ctx_t *ctx)
466 fib_path_list_t *path_list;
468 path_list = fib_path_list_get(path_list_index);
470 fib_path_list_mk_urpf(path_list);
472 FIB_PATH_LIST_DBG(path_list, "bw:%U",
473 format_fib_node_bw_reason, ctx->fnbw_reason);
476 * propagate the backwalk further
478 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
481 * many children. schedule a async walk
483 fib_walk_async(FIB_NODE_TYPE_PATH_LIST,
485 FIB_WALK_PRIORITY_LOW,
491 * only a few children. continue the walk synchronously
493 fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
498 * fib_path_list_back_walk_notify
500 * A back walk has reach this path-list.
502 static fib_node_back_walk_rc_t
503 fib_path_list_back_walk_notify (fib_node_t *node,
504 fib_node_back_walk_ctx_t *ctx)
507 * the path-list is not a direct child of any other node type
508 * paths, which do not change thier to-list-mapping, save the
509 * list they are a member of, and invoke the BW function directly.
513 return (FIB_NODE_BACK_WALK_CONTINUE);
517 * Display the path-list memory usage
520 fib_path_list_memory_show (void)
522 fib_show_memory_usage("Path-list",
523 pool_elts(fib_path_list_pool),
524 pool_len(fib_path_list_pool),
525 sizeof(fib_path_list_t));
526 fib_urpf_list_show_mem();
530 * The FIB path-list's graph node virtual function table
532 static const fib_node_vft_t fib_path_list_vft = {
533 .fnv_get = fib_path_list_get_node,
534 .fnv_last_lock = fib_path_list_last_lock_gone,
535 .fnv_back_walk = fib_path_list_back_walk_notify,
536 .fnv_mem_show = fib_path_list_memory_show,
539 static inline fib_path_list_t *
540 fib_path_list_alloc (fib_node_index_t *path_list_index)
542 fib_path_list_t *path_list;
544 pool_get(fib_path_list_pool, path_list);
545 clib_memset(path_list, 0, sizeof(*path_list));
547 fib_node_init(&path_list->fpl_node,
548 FIB_NODE_TYPE_PATH_LIST);
549 path_list->fpl_urpf = INDEX_INVALID;
550 path_list->fpl_paths = NULL;
552 *path_list_index = fib_path_list_get_index(path_list);
554 FIB_PATH_LIST_DBG(path_list, "alloc");
559 static fib_path_list_t *
560 fib_path_list_resolve (fib_path_list_t *path_list)
562 fib_node_index_t *path_index, *paths, path_list_index;
564 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED));
567 * resolving a path-list is a recursive action. this means more path
568 * lists can be created during this call, and hence this path-list
569 * can be realloc'd. so we work with copies.
570 * this function is called only once per-path list, so its no great overhead.
572 path_list_index = fib_path_list_get_index(path_list);
573 paths = vec_dup(path_list->fpl_paths);
575 vec_foreach (path_index, paths)
577 fib_path_resolve(*path_index);
581 path_list = fib_path_list_get(path_list_index);
583 FIB_PATH_LIST_DBG(path_list, "resovled");
585 if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
587 fib_path_list_mk_urpf(path_list);
593 fib_path_list_get_n_paths (fib_node_index_t path_list_index)
595 fib_path_list_t *path_list;
597 if (FIB_NODE_INDEX_INVALID == path_list_index)
602 path_list = fib_path_list_get(path_list_index);
604 return (vec_len(path_list->fpl_paths));
609 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index)
611 fib_node_index_t *path_index;
612 fib_path_list_t *path_list;
615 path_list = fib_path_list_get(path_list_index);
618 vec_foreach (path_index, path_list->fpl_paths)
620 sw_if_index = fib_path_get_resolving_interface(*path_index);
621 if (~0 != sw_if_index)
623 return (sw_if_index);
627 return (sw_if_index);
631 fib_path_list_get_proto (fib_node_index_t path_list_index)
633 fib_path_list_t *path_list;
635 path_list = fib_path_list_get(path_list_index);
638 * we don't support a mix of path protocols, so we can return the proto
641 return (fib_path_get_proto(path_list->fpl_paths[0]));
645 fib_path_list_is_looped (fib_node_index_t path_list_index)
647 fib_path_list_t *path_list;
649 path_list = fib_path_list_get(path_list_index);
651 return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
655 fib_path_list_is_popular (fib_node_index_t path_list_index)
657 fib_path_list_t *path_list;
659 path_list = fib_path_list_get(path_list_index);
661 return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
664 static fib_path_list_flags_t
665 fib_path_list_flags_fixup (fib_path_list_flags_t flags)
668 * we do no share drop nor exclusive path-lists
670 if (flags & FIB_PATH_LIST_FLAG_DROP ||
671 flags & FIB_PATH_LIST_FLAG_EXCLUSIVE)
673 flags &= ~FIB_PATH_LIST_FLAG_SHARED;
680 fib_path_list_create (fib_path_list_flags_t flags,
681 const fib_route_path_t *rpaths)
683 fib_node_index_t path_list_index, old_path_list_index;
684 fib_path_list_t *path_list;
687 flags = fib_path_list_flags_fixup(flags);
688 path_list = fib_path_list_alloc(&path_list_index);
689 path_list->fpl_flags = flags;
693 vec_foreach_index(i, rpaths)
695 vec_add1(path_list->fpl_paths,
696 fib_path_create(path_list_index,
700 * we sort the paths since the key for the path-list is
701 * the description of the paths it contains. The paths need to
702 * be sorted else this description will differ.
704 if (vec_len(path_list->fpl_paths) > 1)
706 vec_sort_with_function(path_list->fpl_paths,
707 fib_path_cmp_for_sort);
712 * If a shared path list is requested, consult the DB for a match
714 if (flags & FIB_PATH_LIST_FLAG_SHARED)
717 * check for a matching path-list in the DB.
718 * If we find one then we can return the existing one and destroy the
719 * new one just created.
721 old_path_list_index = fib_path_list_db_find(path_list);
722 if (FIB_NODE_INDEX_INVALID != old_path_list_index)
724 fib_path_list_destroy(path_list);
726 path_list_index = old_path_list_index;
731 * if there was not a matching path-list, then this
732 * new one will need inserting into the DB and resolving.
734 fib_path_list_db_insert(path_list_index);
735 path_list = fib_path_list_resolve(path_list);
741 * no shared path list requested. resolve and use the one
744 path_list = fib_path_list_resolve(path_list);
747 return (path_list_index);
750 static fib_path_cfg_flags_t
751 fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
753 fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
755 if (plf & FIB_PATH_LIST_FLAG_DROP)
757 pf |= FIB_PATH_CFG_FLAG_DROP;
759 if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE)
761 pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
763 if (plf & FIB_PATH_LIST_FLAG_LOCAL)
765 pf |= FIB_PATH_CFG_FLAG_LOCAL;
772 fib_path_list_create_special (dpo_proto_t nh_proto,
773 fib_path_list_flags_t flags,
776 fib_node_index_t path_index, path_list_index;
777 fib_path_list_t *path_list;
779 path_list = fib_path_list_alloc(&path_list_index);
780 path_list->fpl_flags = flags;
783 fib_path_create_special(path_list_index,
785 fib_path_list_flags_2_path_flags(flags),
787 vec_add1(path_list->fpl_paths, path_index);
790 * we don't share path-lists. we can do PIC on them so why bother.
792 path_list = fib_path_list_resolve(path_list);
794 return (path_list_index);
798 * return the index info the path-lists's vector of paths, of the matching path.
802 fib_path_list_find_rpath (fib_node_index_t path_list_index,
803 const fib_route_path_t *rpath)
805 fib_path_list_t *path_list;
808 path_list = fib_path_list_get(path_list_index);
810 vec_foreach_index (ii, path_list->fpl_paths)
812 if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
822 * fib_path_list_copy_and_path_add
824 * Create a copy of a path-list and append one more path to it.
825 * The path-list returned could either have been newly created, or
826 * can be a shared path-list from the data-base.
829 fib_path_list_path_add (fib_node_index_t path_list_index,
830 const fib_route_path_t *rpaths)
832 fib_node_index_t new_path_index, *orig_path_index;
833 fib_path_list_t *path_list;
836 * alloc the new list before we retrieve the old one, lest
837 * the alloc result in a realloc
839 path_list = fib_path_list_get(path_list_index);
841 ASSERT(1 == vec_len(rpaths));
842 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
844 FIB_PATH_LIST_DBG(path_list, "path-add");
846 new_path_index = fib_path_create(path_list_index,
849 vec_foreach (orig_path_index, path_list->fpl_paths)
852 * don't add duplicate paths
854 if (0 == fib_path_cmp(new_path_index, *orig_path_index))
856 fib_path_destroy(new_path_index);
857 return (*orig_path_index);
862 * Add the new path - no sort, no sharing, no key..
864 vec_add1(path_list->fpl_paths, new_path_index);
866 FIB_PATH_LIST_DBG(path_list, "path-added");
869 * no shared path list requested. resolve and use the one
872 fib_path_resolve(new_path_index);
874 return (new_path_index);
878 fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
879 fib_path_list_flags_t flags,
880 const fib_route_path_t *rpaths)
882 fib_node_index_t path_index, new_path_index, *orig_path_index;
883 fib_path_list_t *path_list, *orig_path_list;
884 fib_node_index_t exist_path_list_index;
885 fib_node_index_t path_list_index;
888 ASSERT(1 == vec_len(rpaths));
891 * alloc the new list before we retrieve the old one, lest
892 * the alloc result in a realloc
894 path_list = fib_path_list_alloc(&path_list_index);
896 orig_path_list = fib_path_list_get(orig_path_list_index);
898 FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
900 flags = fib_path_list_flags_fixup(flags);
901 path_list->fpl_flags = flags;
903 vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
906 new_path_index = fib_path_create(path_list_index,
909 vec_foreach (orig_path_index, orig_path_list->fpl_paths)
912 * don't add duplicate paths
913 * In the unlikely event the path is a duplicate, then we'll
914 * find a matching path-list later and this one will be toast.
916 if (0 != fib_path_cmp(new_path_index, *orig_path_index))
918 path_index = fib_path_copy(*orig_path_index, path_list_index);
919 path_list->fpl_paths[pi++] = path_index;
923 _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
927 path_list->fpl_paths[pi] = new_path_index;
930 * we sort the paths since the key for the path-list is
931 * the description of the paths it contains. The paths need to
932 * be sorted else this description will differ.
934 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
936 FIB_PATH_LIST_DBG(path_list, "path-added");
939 * check for a matching path-list in the DB.
940 * If we find one then we can return the existing one and destroy the
941 * new one just created.
943 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
945 exist_path_list_index = fib_path_list_db_find(path_list);
946 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
948 fib_path_list_destroy(path_list);
950 path_list_index = exist_path_list_index;
955 * if there was not a matching path-list, then this
956 * new one will need inserting into the DB and resolving.
958 fib_path_list_db_insert(path_list_index);
960 path_list = fib_path_list_resolve(path_list);
966 * no shared path list requested. resolve and use the one
969 path_list = fib_path_list_resolve(path_list);
972 return (path_list_index);
976 * fib_path_list_path_remove
979 fib_path_list_path_remove (fib_node_index_t path_list_index,
980 const fib_route_path_t *rpaths)
982 fib_node_index_t match_path_index, tmp_path_index;
983 fib_path_list_t *path_list;
986 path_list = fib_path_list_get(path_list_index);
988 ASSERT(1 == vec_len(rpaths));
989 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
991 FIB_PATH_LIST_DBG(path_list, "path-remove");
994 * create a representation of the path to be removed, so it
995 * can be used as a comparison object during the copy.
997 tmp_path_index = fib_path_create(path_list_index,
999 match_path_index = FIB_NODE_INDEX_INVALID;
1001 vec_foreach_index (pi, path_list->fpl_paths)
1003 if (0 == fib_path_cmp(tmp_path_index,
1004 path_list->fpl_paths[pi]))
1009 match_path_index = path_list->fpl_paths[pi];
1010 fib_path_destroy(match_path_index);
1011 vec_del1(path_list->fpl_paths, pi);
1016 * done with the temporary now
1018 fib_path_destroy(tmp_path_index);
1020 return (match_path_index);
1024 * fib_path_list_copy_and_path_remove
1026 * Copy the path-list excluding the path passed.
1027 * If the path is the last one, then the index reurned will be invalid.
1028 * i.e. the path-list is toast.
1031 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
1032 fib_path_list_flags_t flags,
1033 const fib_route_path_t *rpath)
1035 fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
1036 fib_path_list_t *path_list, *orig_path_list;
1037 fib_node_index_t pi;
1039 path_list = fib_path_list_alloc(&path_list_index);
1041 flags = fib_path_list_flags_fixup(flags);
1042 orig_path_list = fib_path_list_get(orig_path_list_index);
1044 FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1046 path_list->fpl_flags = flags;
1048 * allocate as many paths as we might need in one go, rather than
1049 * using vec_add to do a few at a time.
1051 if (vec_len(orig_path_list->fpl_paths) > 1)
1053 vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
1058 * create a representation of the path to be removed, so it
1059 * can be used as a comparison object during the copy.
1061 tmp_path_index = fib_path_create(path_list_index, rpath);
1063 vec_foreach (orig_path_index, orig_path_list->fpl_paths)
1065 if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
1066 path_index = fib_path_copy(*orig_path_index, path_list_index);
1067 if (pi < vec_len(path_list->fpl_paths))
1069 path_list->fpl_paths[pi++] = path_index;
1074 * this is the unlikely case that the path being
1075 * removed does not match one in the path-list, so
1076 * we end up with as many paths as we started with.
1077 * the paths vector was sized above with the expectation
1078 * that we would have 1 less.
1080 vec_add1(path_list->fpl_paths, path_index);
1086 * done with the temporary now
1088 fib_path_destroy(tmp_path_index);
1091 * if there are no paths, then the new path-list is aborted
1093 if (0 == vec_len(path_list->fpl_paths)) {
1094 FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1096 fib_path_list_destroy(path_list);
1098 path_list_index = FIB_NODE_INDEX_INVALID;
1101 * we sort the paths since the key for the path-list is
1102 * the description of the paths it contains. The paths need to
1103 * be sorted else this description will differ.
1105 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
1108 * If a shared path list is requested, consult the DB for a match
1110 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1112 fib_node_index_t exist_path_list_index;
1115 * check for a matching path-list in the DB.
1116 * If we find one then we can return the existing one and destroy the
1117 * new one just created.
1119 exist_path_list_index = fib_path_list_db_find(path_list);
1120 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1122 fib_path_list_destroy(path_list);
1124 path_list_index = exist_path_list_index;
1129 * if there was not a matching path-list, then this
1130 * new one will need inserting into the DB and resolving.
1132 fib_path_list_db_insert(path_list_index);
1134 path_list = fib_path_list_resolve(path_list);
1140 * no shared path list requested. resolve and use the one
1143 path_list = fib_path_list_resolve(path_list);
1147 return (path_list_index);
1151 * fib_path_list_contribute_forwarding
1153 * Return the index of a load-balance that user of this path-list should
1154 * use for forwarding
1157 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
1158 fib_forward_chain_type_t fct,
1159 fib_path_list_fwd_flags_t flags,
1162 fib_path_list_t *path_list;
1164 path_list = fib_path_list_get(path_list_index);
1166 fib_path_list_mk_lb(path_list, fct, dpo, flags);
1168 ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type);
1171 * If there's only one bucket in the load-balance then we can
1174 if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1175 (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags))
1177 dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0));
1182 * fib_path_list_get_adj
1184 * Return the index of a adjacency for the first path that user of this
1185 * path-list should use for forwarding
1188 fib_path_list_get_adj (fib_node_index_t path_list_index,
1189 fib_forward_chain_type_t type)
1191 fib_path_list_t *path_list;
1193 path_list = fib_path_list_get(path_list_index);
1194 return (fib_path_get_adj(path_list->fpl_paths[0]));
1198 fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
1199 fib_node_index_t **entry_indicies)
1201 fib_node_index_t *path_index;
1202 int is_looped, list_looped;
1203 fib_path_list_t *path_list;
1206 path_list = fib_path_list_get(path_list_index);
1208 vec_foreach (path_index, path_list->fpl_paths)
1210 fib_node_index_t *copy, **copy_ptr;
1213 * we need a copy of the nodes visited so that when we add entries
1214 * we explore on the nth path and a looped is detected, those entries
1215 * are not again searched for n+1 path and so finding a loop that does
1218 copy = vec_dup(*entry_indicies);
1221 is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1222 list_looped += is_looped;
1227 FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1231 path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1235 path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1238 return (list_looped);
1242 fib_path_list_child_add (fib_node_index_t path_list_index,
1243 fib_node_type_t child_type,
1244 fib_node_index_t child_index)
1248 sibling = fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
1253 if (FIB_PATH_LIST_POPULAR == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST,
1257 * Set the popular flag on the path-list once we pass the magic
1258 * threshold. then walk children to update.
1259 * We don't undo this action. The rational being that the number
1260 * of entries using this prefix is large enough such that it is a
1261 * non-trival amount of effort to converge them. If we get into the
1262 * situation where we are adding and removing entries such that we
1263 * flip-flop over the threshold, then this non-trivial work is added
1264 * to each of those routes adds/deletes - not a situation we want.
1266 fib_node_back_walk_ctx_t ctx = {
1267 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1269 fib_path_list_t *path_list;
1271 path_list = fib_path_list_get(path_list_index);
1272 path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1274 fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1281 fib_path_list_child_remove (fib_node_index_t path_list_index,
1284 fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
1290 fib_path_list_lock(fib_node_index_t path_list_index)
1292 fib_path_list_t *path_list;
1294 if (FIB_NODE_INDEX_INVALID != path_list_index)
1296 path_list = fib_path_list_get(path_list_index);
1298 fib_node_lock(&path_list->fpl_node);
1303 fib_path_list_unlock (fib_node_index_t path_list_index)
1305 fib_path_list_t *path_list;
1307 if (FIB_NODE_INDEX_INVALID != path_list_index)
1309 path_list = fib_path_list_get(path_list_index);
1311 fib_node_unlock(&path_list->fpl_node);
1316 fib_path_list_pool_size (void)
1318 return (pool_elts(fib_path_list_pool));
1322 fib_path_list_db_size (void)
1324 return (hash_elts(fib_path_list_db));
1328 fib_path_list_walk (fib_node_index_t path_list_index,
1329 fib_path_list_walk_fn_t func,
1332 fib_node_index_t *path_index;
1333 fib_path_list_t *path_list;
1335 path_list = fib_path_list_get(path_list_index);
1337 vec_foreach(path_index, path_list->fpl_paths)
1339 if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1348 fib_path_list_module_init (void)
1350 fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1352 fib_path_list_db = hash_create2 (/* elts */ 0,
1354 /* value_bytes */ sizeof (fib_node_index_t),
1355 fib_path_list_db_hash_key_sum,
1356 fib_path_list_db_hash_key_equal,
1357 /* format pair/arg */
1359 fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1362 static clib_error_t *
1363 show_fib_path_list_command (vlib_main_t * vm,
1364 unformat_input_t * input,
1365 vlib_cli_command_t * cmd)
1367 fib_path_list_t *path_list;
1368 fib_node_index_t pli;
1370 if (unformat (input, "%d", &pli))
1373 * show one in detail
1375 if (!pool_is_free_index(fib_path_list_pool, pli))
1377 path_list = fib_path_list_get(pli);
1378 u8 *s = fib_path_list_format(pli, NULL);
1379 s = format(s, "children:");
1380 s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1381 vlib_cli_output (vm, "%s", s);
1386 vlib_cli_output (vm, "path list %d invalid", pli);
1394 vlib_cli_output (vm, "FIB Path Lists");
1395 pool_foreach_index (pli, fib_path_list_pool,
1397 vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1403 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1404 .path = "show fib path-lists",
1405 .function = show_fib_path_list_command,
1406 .short_help = "show fib path-lists",