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>
30 * A representation of the list/set of path trough which a prefix is reachable
32 typedef struct fib_path_list_t_ {
34 * A path-list is a node in the FIB graph.
39 * Flags on the path-list
41 fib_path_list_flags_t fpl_flags;
44 * The next-hop protocol for the paths in this path list.
45 * Note that fixing the proto here means we don't support a mix of
46 * v4 and v6 paths. ho hum.
48 fib_protocol_t fpl_nh_proto;
51 * Vector of paths indicies for all configured paths.
52 * For shareable path-lists this list MUST not change.
54 fib_node_index_t *fpl_paths;
57 * the RPF list calculated for this path list
59 fib_node_index_t fpl_urpf;
63 * Array of strings/names for the FIB sources
65 static const char *fib_path_list_attr_names[] = FIB_PATH_LIST_ATTRIBUTES;
68 * The memory pool from which we allocate all the path-lists
70 static fib_path_list_t * fib_path_list_pool;
73 * The data-base of shared path-lists
75 static uword *fib_path_list_db;
81 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
84 _tmp = fib_path_list_format( \
85 fib_path_list_get_index(_pl), _tmp); \
86 clib_warning("pl:[%d:%p:%p:%s]:" _fmt, \
87 fib_path_list_get_index(_pl), \
88 _pl, _pl->fpl_paths, _tmp, \
93 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
96 static fib_path_list_t *
97 fib_path_list_get (fib_node_index_t index)
99 return (pool_elt_at_index(fib_path_list_pool, index));
103 fib_path_list_get_node (fib_node_index_t index)
105 return ((fib_node_t*)fib_path_list_get(index));
108 static fib_path_list_t*
109 fib_path_list_from_fib_node (fib_node_t *node)
112 ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type);
114 return ((fib_path_list_t*)node);
117 static fib_node_index_t
118 fib_path_list_get_index (fib_path_list_t *path_list)
120 return (path_list - fib_path_list_pool);
124 format_fib_path_list (u8 * s, va_list * args)
126 fib_path_list_attribute_t attr;
127 fib_node_index_t *path_index;
128 fib_path_list_t *path_list;
130 path_list = va_arg (*args, fib_path_list_t *);
132 s = format (s, " index:%u", fib_path_list_get_index(path_list));
133 s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
134 s = format (s, " proto:%U", format_fib_protocol, path_list->fpl_nh_proto);
136 if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
138 s = format (s, " flags:");
139 FOR_EACH_PATH_LIST_ATTRIBUTE(attr)
141 if ((1<<attr) & path_list->fpl_flags)
143 s = format (s, "%s,", fib_path_list_attr_names[attr]);
147 s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
149 vec_foreach (path_index, path_list->fpl_paths)
151 s = fib_path_format(*path_index, s);
159 fib_path_list_adjs_format (fib_node_index_t path_list_index,
163 fib_path_list_t *path_list;
166 path_list = fib_path_list_get(path_list_index);
168 vec_foreach_index (i, path_list->fpl_paths)
170 s = fib_path_adj_format(path_list->fpl_paths[i],
179 fib_path_list_format (fib_node_index_t path_list_index,
182 fib_path_list_t *path_list;
184 path_list = fib_path_list_get(path_list_index);
186 return (format(s, "%U", format_fib_path_list, path_list));
190 fib_path_list_hash (fib_path_list_t *path_list)
192 uword old_path_list_hash, new_path_list_hash, path_hash;
193 fib_node_index_t *path_index;
197 new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths);
199 vec_foreach (path_index, path_list->fpl_paths)
201 path_hash = fib_path_hash(*path_index);
203 hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
205 hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
209 return (new_path_list_hash);
213 fib_path_list_db_hash_key_from_index (uword index)
219 fib_path_list_db_hash_key_is_index (uword key)
225 fib_path_list_db_hash_key_2_index (uword key)
227 ASSERT (fib_path_list_db_hash_key_is_index (key));
231 static fib_path_list_t*
232 fib_path_list_db_get_from_hash_key (uword key)
234 fib_path_list_t *path_list;
236 if (fib_path_list_db_hash_key_is_index (key))
238 fib_node_index_t path_list_index;
240 path_list_index = fib_path_list_db_hash_key_2_index(key);
241 path_list = fib_path_list_get(path_list_index);
245 path_list = uword_to_pointer (key, fib_path_list_t *);
252 fib_path_list_db_hash_key_sum (hash_t * h,
255 fib_path_list_t *path_list;
257 path_list = fib_path_list_db_get_from_hash_key(key);
259 return (fib_path_list_hash(path_list));
263 fib_path_list_db_hash_key_equal (hash_t * h,
267 fib_path_list_t *path_list1, *path_list2;
269 path_list1 = fib_path_list_db_get_from_hash_key(key1);
270 path_list2 = fib_path_list_db_get_from_hash_key(key2);
272 return (fib_path_list_hash(path_list1) ==
273 fib_path_list_hash(path_list2));
276 static fib_node_index_t
277 fib_path_list_db_find (fib_path_list_t *path_list)
281 p = hash_get(fib_path_list_db, path_list);
288 return (FIB_NODE_INDEX_INVALID);
292 fib_path_list_db_insert (fib_node_index_t path_list_index)
294 fib_path_list_t *path_list;
296 path_list = fib_path_list_get(path_list_index);
298 ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list));
300 hash_set (fib_path_list_db,
301 fib_path_list_db_hash_key_from_index(path_list_index),
304 FIB_PATH_LIST_DBG(path_list, "DB-inserted");
308 fib_path_list_db_remove (fib_node_index_t path_list_index)
310 fib_path_list_t *path_list;
312 path_list = fib_path_list_get(path_list_index);
314 ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list));
316 hash_unset(fib_path_list_db,
317 fib_path_list_db_hash_key_from_index(path_list_index));
319 FIB_PATH_LIST_DBG(path_list, "DB-removed");
323 fib_path_list_destroy (fib_path_list_t *path_list)
325 fib_node_index_t *path_index;
327 FIB_PATH_LIST_DBG(path_list, "destroy");
329 vec_foreach (path_index, path_list->fpl_paths)
331 fib_path_destroy(*path_index);
334 vec_free(path_list->fpl_paths);
335 fib_urpf_list_unlock(path_list->fpl_urpf);
337 fib_node_deinit(&path_list->fpl_node);
338 pool_put(fib_path_list_pool, path_list);
342 fib_path_list_last_lock_gone (fib_node_t *node)
344 fib_path_list_t *path_list;
346 path_list = fib_path_list_from_fib_node(node);
348 FIB_PATH_LIST_DBG(path_list, "last-lock");
350 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
352 fib_path_list_db_remove(fib_path_list_get_index(path_list));
354 fib_path_list_destroy(path_list);
360 * update the multipath adj this path-list will contribute to its
361 * children's forwarding.
364 fib_path_list_mk_lb (fib_path_list_t *path_list,
365 fib_forward_chain_type_t fct,
368 load_balance_path_t *nhs;
369 fib_node_index_t *path_index;
373 if (!dpo_id_is_valid(dpo))
380 fib_forw_chain_type_to_dpo_proto(fct),
381 load_balance_create(0,
382 fib_forw_chain_type_to_dpo_proto(fct),
383 0 /* FIXME FLOW HASH */));
387 * We gather the DPOs from resolved paths.
389 vec_foreach (path_index, path_list->fpl_paths)
391 nhs = fib_path_append_nh_for_multipath_hash(*path_index,
397 * Path-list load-balances, which if used, would be shared and hence
398 * never need a load-balance map.
400 load_balance_multipath_update(dpo, nhs, LOAD_BALANCE_FLAG_NONE);
402 FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
408 * @brief [re]build the path list's uRPF list
411 fib_path_list_mk_urpf (fib_path_list_t *path_list)
413 fib_node_index_t *path_index;
416 * ditch the old one. by iterating through all paths we are going
417 * to re-find all the adjs that were in the old one anyway. If we
418 * keep the old one, then the |sort|uniq requires more work.
419 * All users of the RPF list have their own lock, so we can release
422 fib_urpf_list_unlock(path_list->fpl_urpf);
423 path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
425 vec_foreach (path_index, path_list->fpl_paths)
427 fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
430 fib_urpf_list_bake(path_list->fpl_urpf);
434 * @brief Contribute (add) this path list's uRPF list. This allows the child
435 * to construct an aggregate list.
438 fib_path_list_contribute_urpf (fib_node_index_t path_list_index,
441 fib_path_list_t *path_list;
443 path_list = fib_path_list_get(path_list_index);
445 fib_urpf_list_combine(urpf, path_list->fpl_urpf);
449 * @brief Return the the child the RPF list pre-built for this path list
452 fib_path_list_get_urpf (fib_node_index_t path_list_index)
454 fib_path_list_t *path_list;
456 path_list = fib_path_list_get(path_list_index);
458 return (path_list->fpl_urpf);
462 * fib_path_list_back_walk
464 * Called from one of this path-list's paths to progate
468 fib_path_list_back_walk (fib_node_index_t path_list_index,
469 fib_node_back_walk_ctx_t *ctx)
471 fib_path_list_t *path_list;
473 path_list = fib_path_list_get(path_list_index);
475 fib_path_list_mk_urpf(path_list);
478 * propagate the backwalk further
480 if (32 >= fib_node_list_get_size(path_list->fpl_node.fn_children))
483 * only a few children. continue the walk synchronously
485 fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
490 * many children. schedule a async walk
492 fib_walk_async(FIB_NODE_TYPE_PATH_LIST,
494 FIB_WALK_PRIORITY_LOW,
500 * fib_path_list_back_walk_notify
502 * A back walk has reach this path-list.
504 static fib_node_back_walk_rc_t
505 fib_path_list_back_walk_notify (fib_node_t *node,
506 fib_node_back_walk_ctx_t *ctx)
509 * the path-list is not a direct child of any other node type
510 * paths, which do not change thier to-list-mapping, save the
511 * list they are a member of, and invoke the BW function directly.
515 return (FIB_NODE_BACK_WALK_CONTINUE);
519 * Display the path-list memory usage
522 fib_path_list_memory_show (void)
524 fib_show_memory_usage("Path-list",
525 pool_elts(fib_path_list_pool),
526 pool_len(fib_path_list_pool),
527 sizeof(fib_path_list_t));
528 fib_urpf_list_show_mem();
532 * The FIB path-list's graph node virtual function table
534 static const fib_node_vft_t fib_path_list_vft = {
535 .fnv_get = fib_path_list_get_node,
536 .fnv_last_lock = fib_path_list_last_lock_gone,
537 .fnv_back_walk = fib_path_list_back_walk_notify,
538 .fnv_mem_show = fib_path_list_memory_show,
541 static inline fib_path_list_t *
542 fib_path_list_alloc (fib_node_index_t *path_list_index)
544 fib_path_list_t *path_list;
546 pool_get(fib_path_list_pool, path_list);
547 memset(path_list, 0, sizeof(*path_list));
549 fib_node_init(&path_list->fpl_node,
550 FIB_NODE_TYPE_PATH_LIST);
551 path_list->fpl_urpf = INDEX_INVALID;
552 path_list->fpl_paths = NULL;
554 *path_list_index = fib_path_list_get_index(path_list);
556 FIB_PATH_LIST_DBG(path_list, "alloc");
561 static fib_path_list_t *
562 fib_path_list_resolve (fib_path_list_t *path_list)
564 fib_node_index_t *path_index, *paths, path_list_index;
566 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED));
569 * resolving a path-list is a recursive action. this means more path
570 * lists can be created during this call, and hence this path-list
571 * can be realloc'd. so we work with copies.
572 * this function is called only once per-path list, so its no great overhead.
574 path_list_index = fib_path_list_get_index(path_list);
575 paths = vec_dup(path_list->fpl_paths);
577 vec_foreach (path_index, paths)
579 fib_path_resolve(*path_index);
583 path_list = fib_path_list_get(path_list_index);
585 FIB_PATH_LIST_DBG(path_list, "resovled");
587 if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
589 fib_path_list_mk_urpf(path_list);
595 fib_path_list_get_n_paths (fib_node_index_t path_list_index)
597 fib_path_list_t *path_list;
599 path_list = fib_path_list_get(path_list_index);
601 return (vec_len(path_list->fpl_paths));
606 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index)
608 fib_node_index_t *path_index;
609 fib_path_list_t *path_list;
612 path_list = fib_path_list_get(path_list_index);
615 vec_foreach (path_index, path_list->fpl_paths)
617 sw_if_index = fib_path_get_resolving_interface(*path_index);
618 if (~0 != sw_if_index)
620 return (sw_if_index);
624 return (sw_if_index);
628 fib_path_list_get_proto (fib_node_index_t path_list_index)
630 fib_path_list_t *path_list;
632 path_list = fib_path_list_get(path_list_index);
635 * we don't support a mix of path protocols, so we can return the proto
638 return (fib_path_get_proto(path_list->fpl_paths[0]));
642 fib_path_list_is_looped (fib_node_index_t path_list_index)
644 fib_path_list_t *path_list;
646 path_list = fib_path_list_get(path_list_index);
648 return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
651 static fib_path_cfg_flags_t
652 fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
654 fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
656 if (plf & FIB_PATH_LIST_FLAG_LOCAL)
658 pf |= FIB_PATH_CFG_FLAG_LOCAL;
660 if (plf & FIB_PATH_LIST_FLAG_DROP)
662 pf |= FIB_PATH_CFG_FLAG_DROP;
664 if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE)
666 pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
672 static fib_path_list_flags_t
673 fib_path_list_flags_fixup (fib_path_list_flags_t flags)
676 * we do no share drop nor exclusive path-lists
678 if (flags & FIB_PATH_LIST_FLAG_DROP ||
679 flags & FIB_PATH_LIST_FLAG_EXCLUSIVE)
681 flags &= ~FIB_PATH_LIST_FLAG_SHARED;
688 fib_path_list_create (fib_path_list_flags_t flags,
689 const fib_route_path_t *rpaths)
691 fib_node_index_t path_list_index, old_path_list_index;
692 fib_path_list_t *path_list;
695 flags = fib_path_list_flags_fixup(flags);
696 path_list = fib_path_list_alloc(&path_list_index);
697 path_list->fpl_flags = flags;
699 * we'll assume for now all paths are the same next-hop protocol
701 path_list->fpl_nh_proto = rpaths[0].frp_proto;
703 vec_foreach_index(i, rpaths)
705 vec_add1(path_list->fpl_paths,
706 fib_path_create(path_list_index,
707 path_list->fpl_nh_proto,
708 fib_path_list_flags_2_path_flags(flags),
713 * If a shared path list is requested, consult the DB for a match
715 if (flags & FIB_PATH_LIST_FLAG_SHARED)
718 * check for a matching path-list in the DB.
719 * If we find one then we can return the existing one and destroy the
720 * new one just created.
722 old_path_list_index = fib_path_list_db_find(path_list);
723 if (FIB_NODE_INDEX_INVALID != old_path_list_index)
725 fib_path_list_destroy(path_list);
727 path_list_index = old_path_list_index;
732 * if there was not a matching path-list, then this
733 * new one will need inserting into the DB and resolving.
735 fib_path_list_db_insert(path_list_index);
736 path_list = fib_path_list_resolve(path_list);
742 * no shared path list requested. resolve and use the one
745 path_list = fib_path_list_resolve(path_list);
748 return (path_list_index);
752 fib_path_list_create_special (fib_protocol_t nh_proto,
753 fib_path_list_flags_t flags,
756 fib_node_index_t path_index, path_list_index;
757 fib_path_list_t *path_list;
759 path_list = fib_path_list_alloc(&path_list_index);
760 path_list->fpl_flags = flags;
761 path_list->fpl_nh_proto = nh_proto;
764 fib_path_create_special(path_list_index,
765 path_list->fpl_nh_proto,
766 fib_path_list_flags_2_path_flags(flags),
768 vec_add1(path_list->fpl_paths, path_index);
771 * we don't share path-lists. we can do PIC on them so why bother.
773 path_list = fib_path_list_resolve(path_list);
775 return (path_list_index);
779 * fib_path_list_copy_and_path_add
781 * Create a copy of a path-list and append one more path to it.
782 * The path-list returned could either have been newly created, or
783 * can be a shared path-list from the data-base.
786 fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
787 fib_path_list_flags_t flags,
788 const fib_route_path_t *rpaths)
790 fib_node_index_t path_index, new_path_index, *orig_path_index;
791 fib_path_list_t *path_list, *orig_path_list;
792 fib_node_index_t path_list_index;
795 ASSERT(1 == vec_len(rpaths));
798 * alloc the new list before we retrieve the old one, lest
799 * the alloc result in a realloc
801 path_list = fib_path_list_alloc(&path_list_index);
803 orig_path_list = fib_path_list_get(orig_path_list_index);
805 FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
807 flags = fib_path_list_flags_fixup(flags);
808 path_list->fpl_flags = flags;
809 path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto;
810 vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
813 new_path_index = fib_path_create(path_list_index,
814 path_list->fpl_nh_proto,
815 fib_path_list_flags_2_path_flags(flags),
818 vec_foreach (orig_path_index, orig_path_list->fpl_paths)
821 * don't add duplicate paths
822 * In the unlikely event the path is a duplicate, then we'll
823 * find a matching path-list later and this one will be toast.
825 if (0 != fib_path_cmp(new_path_index, *orig_path_index))
827 path_index = fib_path_copy(*orig_path_index, path_list_index);
828 path_list->fpl_paths[pi++] = path_index;
832 _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
836 path_list->fpl_paths[pi] = new_path_index;
839 * we sort the paths since the key for the path-list is
840 * the description of the paths it contains. The paths need to
841 * be sorted else this description will differ.
843 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
845 FIB_PATH_LIST_DBG(path_list, "path-added");
848 * If a shared path list is requested, consult the DB for a match
850 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
852 fib_node_index_t exist_path_list_index;
854 * check for a matching path-list in the DB.
855 * If we find one then we can return the existing one and destroy the
856 * new one just created.
858 exist_path_list_index = fib_path_list_db_find(path_list);
859 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
861 fib_path_list_destroy(path_list);
863 path_list_index = exist_path_list_index;
868 * if there was not a matching path-list, then this
869 * new one will need inserting into the DB and resolving.
871 fib_path_list_db_insert(path_list_index);
873 path_list = fib_path_list_resolve(path_list);
879 * no shared path list requested. resolve and use the one
882 path_list = fib_path_list_resolve(path_list);
885 return (path_list_index);
889 * fib_path_list_copy_and_path_remove
891 * Copy the path-list excluding the path passed.
892 * If the path is the last one, then the index reurned will be invalid.
893 * i.e. the path-list is toast.
896 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
897 fib_path_list_flags_t flags,
898 const fib_route_path_t *rpaths)
900 fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
901 fib_path_list_t *path_list, *orig_path_list;
904 ASSERT(1 == vec_len(rpaths));
906 path_list = fib_path_list_alloc(&path_list_index);
908 flags = fib_path_list_flags_fixup(flags);
909 orig_path_list = fib_path_list_get(orig_path_list_index);
911 FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
913 path_list->fpl_flags = flags;
914 path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto;
916 * allocate as many paths as we might need in one go, rather than
917 * using vec_add to do a few at a time.
919 if (vec_len(orig_path_list->fpl_paths) > 1)
921 vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
926 * create a representation of the path to be removed, so it
927 * can be used as a comparison object during the copy.
929 tmp_path_index = fib_path_create(path_list_index,
930 path_list->fpl_nh_proto,
931 fib_path_list_flags_2_path_flags(flags),
934 vec_foreach (orig_path_index, orig_path_list->fpl_paths)
936 if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
937 path_index = fib_path_copy(*orig_path_index, path_list_index);
938 if (pi < vec_len(path_list->fpl_paths))
940 path_list->fpl_paths[pi++] = path_index;
945 * this is the unlikely case that the path being
946 * removed does not match one in the path-list, so
947 * we end up with as many paths as we started with.
948 * the paths vector was sized above with the expectation
949 * that we would have 1 less.
951 vec_add1(path_list->fpl_paths, path_index);
957 * done with the temporary now
959 fib_path_destroy(tmp_path_index);
962 * if there are no paths, then the new path-list is aborted
964 if (0 == vec_len(path_list->fpl_paths)) {
965 FIB_PATH_LIST_DBG(path_list, "last-path-removed");
967 fib_path_list_destroy(path_list);
969 path_list_index = FIB_NODE_INDEX_INVALID;
972 * we sort the paths since the key for the path-list is
973 * the description of the paths it contains. The paths need to
974 * be sorted else this description will differ.
976 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
979 * If a shared path list is requested, consult the DB for a match
981 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
983 fib_node_index_t exist_path_list_index;
986 * check for a matching path-list in the DB.
987 * If we find one then we can return the existing one and destroy the
988 * new one just created.
990 exist_path_list_index = fib_path_list_db_find(path_list);
991 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
993 fib_path_list_destroy(path_list);
995 path_list_index = exist_path_list_index;
1000 * if there was not a matching path-list, then this
1001 * new one will need inserting into the DB and resolving.
1003 fib_path_list_db_insert(path_list_index);
1005 path_list = fib_path_list_resolve(path_list);
1011 * no shared path list requested. resolve and use the one
1014 path_list = fib_path_list_resolve(path_list);
1018 return (path_list_index);
1022 * fib_path_list_contribute_forwarding
1024 * Return the index of a load-balance that user of this path-list should
1025 * use for forwarding
1028 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
1029 fib_forward_chain_type_t fct,
1032 fib_path_list_t *path_list;
1034 path_list = fib_path_list_get(path_list_index);
1036 fib_path_list_mk_lb(path_list, fct, dpo);
1040 * fib_path_list_get_adj
1042 * Return the index of a adjacency for the first path that user of this
1043 * path-list should use for forwarding
1046 fib_path_list_get_adj (fib_node_index_t path_list_index,
1047 fib_forward_chain_type_t type)
1049 fib_path_list_t *path_list;
1051 path_list = fib_path_list_get(path_list_index);
1052 return (fib_path_get_adj(path_list->fpl_paths[0]));
1056 fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
1057 fib_node_index_t **entry_indicies)
1059 fib_node_index_t *path_index;
1060 int is_looped, list_looped;
1061 fib_path_list_t *path_list;
1064 path_list = fib_path_list_get(path_list_index);
1066 vec_foreach (path_index, path_list->fpl_paths)
1068 fib_node_index_t *copy, **copy_ptr;
1071 * we need a copy of the nodes visited so that when we add entries
1072 * we explore on the nth path and a looped is detected, those entries
1073 * are not again searched for n+1 path and so finding a loop that does
1076 copy = vec_dup(*entry_indicies);
1079 is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1080 list_looped += is_looped;
1083 FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval);
1087 path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1091 path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1094 return (list_looped);
1098 fib_path_list_child_add (fib_node_index_t path_list_index,
1099 fib_node_type_t child_type,
1100 fib_node_index_t child_index)
1102 return (fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
1109 fib_path_list_child_remove (fib_node_index_t path_list_index,
1112 fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
1118 fib_path_list_lock(fib_node_index_t path_list_index)
1120 fib_path_list_t *path_list;
1122 if (FIB_NODE_INDEX_INVALID != path_list_index)
1124 path_list = fib_path_list_get(path_list_index);
1126 fib_node_lock(&path_list->fpl_node);
1127 FIB_PATH_LIST_DBG(path_list, "lock");
1132 fib_path_list_unlock (fib_node_index_t path_list_index)
1134 fib_path_list_t *path_list;
1136 if (FIB_NODE_INDEX_INVALID != path_list_index)
1138 path_list = fib_path_list_get(path_list_index);
1139 FIB_PATH_LIST_DBG(path_list, "unlock");
1141 fib_node_unlock(&path_list->fpl_node);
1146 fib_path_list_pool_size (void)
1148 return (pool_elts(fib_path_list_pool));
1152 fib_path_list_db_size (void)
1154 return (hash_elts(fib_path_list_db));
1158 fib_path_list_walk (fib_node_index_t path_list_index,
1159 fib_path_list_walk_fn_t func,
1162 fib_node_index_t *path_index;
1163 fib_path_list_t *path_list;
1165 path_list = fib_path_list_get(path_list_index);
1167 vec_foreach(path_index, path_list->fpl_paths)
1169 if (!func(path_list_index, *path_index, ctx))
1176 fib_path_list_module_init (void)
1178 fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1180 fib_path_list_db = hash_create2 (/* elts */ 0,
1182 /* value_bytes */ sizeof (fib_node_index_t),
1183 fib_path_list_db_hash_key_sum,
1184 fib_path_list_db_hash_key_equal,
1185 /* format pair/arg */
1189 static clib_error_t *
1190 show_fib_path_list_command (vlib_main_t * vm,
1191 unformat_input_t * input,
1192 vlib_cli_command_t * cmd)
1194 fib_path_list_t *path_list;
1195 fib_node_index_t pli;
1197 if (unformat (input, "%d", &pli))
1200 * show one in detail
1202 if (!pool_is_free_index(fib_path_list_pool, pli))
1204 path_list = fib_path_list_get(pli);
1205 u8 *s = fib_path_list_format(pli, NULL);
1206 s = format(s, "children:");
1207 s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1208 vlib_cli_output (vm, "%s", s);
1213 vlib_cli_output (vm, "path list %d invalid", pli);
1221 vlib_cli_output (vm, "FIB Path Lists");
1222 pool_foreach(path_list, fib_path_list_pool,
1224 vlib_cli_output (vm, "%U", format_fib_path_list, path_list);
1230 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1231 .path = "show fib path-lists",
1232 .function = show_fib_path_list_command,
1233 .short_help = "show fib path-lists",