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;
89 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
92 _tmp = fib_path_list_format( \
93 fib_path_list_get_index(_pl), _tmp); \
94 clib_warning("pl:[%d:%p:%p:%s]:" _fmt, \
95 fib_path_list_get_index(_pl), \
96 _pl, _pl->fpl_paths, _tmp, \
101 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
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);
169 fib_path_list_format (fib_node_index_t path_list_index,
172 return (format(s, "%U", format_fib_path_list, path_list_index, 4));
176 fib_path_list_hash (fib_path_list_t *path_list)
178 uword old_path_list_hash, new_path_list_hash, path_hash;
179 fib_node_index_t *path_index;
183 new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths);
185 vec_foreach (path_index, path_list->fpl_paths)
187 path_hash = fib_path_hash(*path_index);
189 hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
191 hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
195 return (new_path_list_hash);
199 fib_path_list_db_hash_key_from_index (uword index)
205 fib_path_list_db_hash_key_is_index (uword key)
211 fib_path_list_db_hash_key_2_index (uword key)
213 ASSERT (fib_path_list_db_hash_key_is_index (key));
217 static fib_path_list_t*
218 fib_path_list_db_get_from_hash_key (uword key)
220 fib_path_list_t *path_list;
222 if (fib_path_list_db_hash_key_is_index (key))
224 fib_node_index_t path_list_index;
226 path_list_index = fib_path_list_db_hash_key_2_index(key);
227 path_list = fib_path_list_get(path_list_index);
231 path_list = uword_to_pointer (key, fib_path_list_t *);
238 fib_path_list_db_hash_key_sum (hash_t * h,
241 fib_path_list_t *path_list;
243 path_list = fib_path_list_db_get_from_hash_key(key);
245 return (fib_path_list_hash(path_list));
249 fib_path_list_db_hash_key_equal (hash_t * h,
253 fib_path_list_t *path_list1, *path_list2;
255 path_list1 = fib_path_list_db_get_from_hash_key(key1);
256 path_list2 = fib_path_list_db_get_from_hash_key(key2);
258 return (fib_path_list_hash(path_list1) ==
259 fib_path_list_hash(path_list2));
262 static fib_node_index_t
263 fib_path_list_db_find (fib_path_list_t *path_list)
267 p = hash_get(fib_path_list_db, path_list);
274 return (FIB_NODE_INDEX_INVALID);
278 fib_path_list_db_insert (fib_node_index_t path_list_index)
280 fib_path_list_t *path_list;
282 path_list = fib_path_list_get(path_list_index);
284 ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list));
286 hash_set (fib_path_list_db,
287 fib_path_list_db_hash_key_from_index(path_list_index),
290 FIB_PATH_LIST_DBG(path_list, "DB-inserted");
294 fib_path_list_db_remove (fib_node_index_t path_list_index)
296 fib_path_list_t *path_list;
298 path_list = fib_path_list_get(path_list_index);
300 ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list));
302 hash_unset(fib_path_list_db,
303 fib_path_list_db_hash_key_from_index(path_list_index));
305 FIB_PATH_LIST_DBG(path_list, "DB-removed");
309 fib_path_list_destroy (fib_path_list_t *path_list)
311 fib_node_index_t *path_index;
313 FIB_PATH_LIST_DBG(path_list, "destroy");
315 vec_foreach (path_index, path_list->fpl_paths)
317 fib_path_destroy(*path_index);
320 vec_free(path_list->fpl_paths);
321 fib_urpf_list_unlock(path_list->fpl_urpf);
323 fib_node_deinit(&path_list->fpl_node);
324 pool_put(fib_path_list_pool, path_list);
328 fib_path_list_last_lock_gone (fib_node_t *node)
330 fib_path_list_t *path_list;
332 path_list = fib_path_list_from_fib_node(node);
334 FIB_PATH_LIST_DBG(path_list, "last-lock");
336 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
338 fib_path_list_db_remove(fib_path_list_get_index(path_list));
340 fib_path_list_destroy(path_list);
346 * update the multipath adj this path-list will contribute to its
347 * children's forwarding.
350 fib_path_list_mk_lb (fib_path_list_t *path_list,
351 fib_forward_chain_type_t fct,
354 load_balance_path_t *nhs;
355 fib_node_index_t *path_index;
360 * We gather the DPOs from resolved paths.
362 vec_foreach (path_index, path_list->fpl_paths)
364 nhs = fib_path_append_nh_for_multipath_hash(*path_index,
370 * Path-list load-balances, which if used, would be shared and hence
371 * never need a load-balance map.
375 fib_forw_chain_type_to_dpo_proto(fct),
376 load_balance_create(vec_len(nhs),
377 fib_forw_chain_type_to_dpo_proto(fct),
378 0 /* FIXME FLOW HASH */));
379 load_balance_multipath_update(dpo, nhs, LOAD_BALANCE_FLAG_NONE);
381 FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
387 * @brief [re]build the path list's uRPF list
390 fib_path_list_mk_urpf (fib_path_list_t *path_list)
392 fib_node_index_t *path_index;
395 * ditch the old one. by iterating through all paths we are going
396 * to re-find all the adjs that were in the old one anyway. If we
397 * keep the old one, then the |sort|uniq requires more work.
398 * All users of the RPF list have their own lock, so we can release
401 fib_urpf_list_unlock(path_list->fpl_urpf);
402 path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
404 vec_foreach (path_index, path_list->fpl_paths)
406 fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
409 fib_urpf_list_bake(path_list->fpl_urpf);
413 * @brief Contribute (add) this path list's uRPF list. This allows the child
414 * to construct an aggregate list.
417 fib_path_list_contribute_urpf (fib_node_index_t path_list_index,
420 fib_path_list_t *path_list;
422 path_list = fib_path_list_get(path_list_index);
424 fib_urpf_list_combine(urpf, path_list->fpl_urpf);
428 * @brief Return the the child the RPF list pre-built for this path list
431 fib_path_list_get_urpf (fib_node_index_t path_list_index)
433 fib_path_list_t *path_list;
435 path_list = fib_path_list_get(path_list_index);
437 return (path_list->fpl_urpf);
441 * fib_path_list_back_walk
443 * Called from one of this path-list's paths to progate
447 fib_path_list_back_walk (fib_node_index_t path_list_index,
448 fib_node_back_walk_ctx_t *ctx)
450 fib_path_list_t *path_list;
452 path_list = fib_path_list_get(path_list_index);
454 fib_path_list_mk_urpf(path_list);
457 * propagate the backwalk further
459 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
462 * many children. schedule a async walk
464 fib_walk_async(FIB_NODE_TYPE_PATH_LIST,
466 FIB_WALK_PRIORITY_LOW,
472 * only a few children. continue the walk synchronously
474 fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
479 * fib_path_list_back_walk_notify
481 * A back walk has reach this path-list.
483 static fib_node_back_walk_rc_t
484 fib_path_list_back_walk_notify (fib_node_t *node,
485 fib_node_back_walk_ctx_t *ctx)
488 * the path-list is not a direct child of any other node type
489 * paths, which do not change thier to-list-mapping, save the
490 * list they are a member of, and invoke the BW function directly.
494 return (FIB_NODE_BACK_WALK_CONTINUE);
498 * Display the path-list memory usage
501 fib_path_list_memory_show (void)
503 fib_show_memory_usage("Path-list",
504 pool_elts(fib_path_list_pool),
505 pool_len(fib_path_list_pool),
506 sizeof(fib_path_list_t));
507 fib_urpf_list_show_mem();
511 * The FIB path-list's graph node virtual function table
513 static const fib_node_vft_t fib_path_list_vft = {
514 .fnv_get = fib_path_list_get_node,
515 .fnv_last_lock = fib_path_list_last_lock_gone,
516 .fnv_back_walk = fib_path_list_back_walk_notify,
517 .fnv_mem_show = fib_path_list_memory_show,
520 static inline fib_path_list_t *
521 fib_path_list_alloc (fib_node_index_t *path_list_index)
523 fib_path_list_t *path_list;
525 pool_get(fib_path_list_pool, path_list);
526 memset(path_list, 0, sizeof(*path_list));
528 fib_node_init(&path_list->fpl_node,
529 FIB_NODE_TYPE_PATH_LIST);
530 path_list->fpl_urpf = INDEX_INVALID;
531 path_list->fpl_paths = NULL;
533 *path_list_index = fib_path_list_get_index(path_list);
535 FIB_PATH_LIST_DBG(path_list, "alloc");
540 static fib_path_list_t *
541 fib_path_list_resolve (fib_path_list_t *path_list)
543 fib_node_index_t *path_index, *paths, path_list_index;
545 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED));
548 * resolving a path-list is a recursive action. this means more path
549 * lists can be created during this call, and hence this path-list
550 * can be realloc'd. so we work with copies.
551 * this function is called only once per-path list, so its no great overhead.
553 path_list_index = fib_path_list_get_index(path_list);
554 paths = vec_dup(path_list->fpl_paths);
556 vec_foreach (path_index, paths)
558 fib_path_resolve(*path_index);
562 path_list = fib_path_list_get(path_list_index);
564 FIB_PATH_LIST_DBG(path_list, "resovled");
566 if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
568 fib_path_list_mk_urpf(path_list);
574 fib_path_list_get_n_paths (fib_node_index_t path_list_index)
576 fib_path_list_t *path_list;
578 if (FIB_NODE_INDEX_INVALID == path_list_index)
583 path_list = fib_path_list_get(path_list_index);
585 return (vec_len(path_list->fpl_paths));
590 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index)
592 fib_node_index_t *path_index;
593 fib_path_list_t *path_list;
596 path_list = fib_path_list_get(path_list_index);
599 vec_foreach (path_index, path_list->fpl_paths)
601 sw_if_index = fib_path_get_resolving_interface(*path_index);
602 if (~0 != sw_if_index)
604 return (sw_if_index);
608 return (sw_if_index);
612 fib_path_list_get_proto (fib_node_index_t path_list_index)
614 fib_path_list_t *path_list;
616 path_list = fib_path_list_get(path_list_index);
619 * we don't support a mix of path protocols, so we can return the proto
622 return (fib_path_get_proto(path_list->fpl_paths[0]));
626 fib_path_list_is_looped (fib_node_index_t path_list_index)
628 fib_path_list_t *path_list;
630 path_list = fib_path_list_get(path_list_index);
632 return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
636 fib_path_list_is_popular (fib_node_index_t path_list_index)
638 fib_path_list_t *path_list;
640 path_list = fib_path_list_get(path_list_index);
642 return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
645 static fib_path_list_flags_t
646 fib_path_list_flags_fixup (fib_path_list_flags_t flags)
649 * we do no share drop nor exclusive path-lists
651 if (flags & FIB_PATH_LIST_FLAG_DROP ||
652 flags & FIB_PATH_LIST_FLAG_EXCLUSIVE)
654 flags &= ~FIB_PATH_LIST_FLAG_SHARED;
661 fib_path_list_create (fib_path_list_flags_t flags,
662 const fib_route_path_t *rpaths)
664 fib_node_index_t path_list_index, old_path_list_index;
665 fib_path_list_t *path_list;
668 flags = fib_path_list_flags_fixup(flags);
669 path_list = fib_path_list_alloc(&path_list_index);
670 path_list->fpl_flags = flags;
674 vec_foreach_index(i, rpaths)
676 vec_add1(path_list->fpl_paths,
677 fib_path_create(path_list_index,
681 * we sort the paths since the key for the path-list is
682 * the description of the paths it contains. The paths need to
683 * be sorted else this description will differ.
685 if (vec_len(path_list->fpl_paths) > 1)
687 vec_sort_with_function(path_list->fpl_paths,
688 fib_path_cmp_for_sort);
693 * If a shared path list is requested, consult the DB for a match
695 if (flags & FIB_PATH_LIST_FLAG_SHARED)
698 * check for a matching path-list in the DB.
699 * If we find one then we can return the existing one and destroy the
700 * new one just created.
702 old_path_list_index = fib_path_list_db_find(path_list);
703 if (FIB_NODE_INDEX_INVALID != old_path_list_index)
705 fib_path_list_destroy(path_list);
707 path_list_index = old_path_list_index;
712 * if there was not a matching path-list, then this
713 * new one will need inserting into the DB and resolving.
715 fib_path_list_db_insert(path_list_index);
716 path_list = fib_path_list_resolve(path_list);
722 * no shared path list requested. resolve and use the one
725 path_list = fib_path_list_resolve(path_list);
728 return (path_list_index);
731 static fib_path_cfg_flags_t
732 fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
734 fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
736 if (plf & FIB_PATH_LIST_FLAG_DROP)
738 pf |= FIB_PATH_CFG_FLAG_DROP;
740 if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE)
742 pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
744 if (plf & FIB_PATH_LIST_FLAG_LOCAL)
746 pf |= FIB_PATH_CFG_FLAG_LOCAL;
753 fib_path_list_create_special (dpo_proto_t nh_proto,
754 fib_path_list_flags_t flags,
757 fib_node_index_t path_index, path_list_index;
758 fib_path_list_t *path_list;
760 path_list = fib_path_list_alloc(&path_list_index);
761 path_list->fpl_flags = flags;
764 fib_path_create_special(path_list_index,
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 * return the index info the path-lists's vector of paths, of the matching path.
783 fib_path_list_find_rpath (fib_node_index_t path_list_index,
784 const fib_route_path_t *rpath)
786 fib_path_list_t *path_list;
789 path_list = fib_path_list_get(path_list_index);
791 vec_foreach_index (ii, path_list->fpl_paths)
793 if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
803 * fib_path_list_copy_and_path_add
805 * Create a copy of a path-list and append one more path to it.
806 * The path-list returned could either have been newly created, or
807 * can be a shared path-list from the data-base.
810 fib_path_list_path_add (fib_node_index_t path_list_index,
811 const fib_route_path_t *rpaths)
813 fib_node_index_t new_path_index, *orig_path_index;
814 fib_path_list_t *path_list;
817 * alloc the new list before we retrieve the old one, lest
818 * the alloc result in a realloc
820 path_list = fib_path_list_get(path_list_index);
822 ASSERT(1 == vec_len(rpaths));
823 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
825 FIB_PATH_LIST_DBG(orig_path_list, "path-add");
827 new_path_index = fib_path_create(path_list_index,
830 vec_foreach (orig_path_index, path_list->fpl_paths)
833 * don't add duplicate paths
835 if (0 == fib_path_cmp(new_path_index, *orig_path_index))
837 fib_path_destroy(new_path_index);
838 return (*orig_path_index);
843 * Add the new path - no sort, no sharing, no key..
845 vec_add1(path_list->fpl_paths, new_path_index);
847 FIB_PATH_LIST_DBG(path_list, "path-added");
850 * no shared path list requested. resolve and use the one
853 fib_path_resolve(new_path_index);
855 return (new_path_index);
859 fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
860 fib_path_list_flags_t flags,
861 const fib_route_path_t *rpaths)
863 fib_node_index_t path_index, new_path_index, *orig_path_index;
864 fib_path_list_t *path_list, *orig_path_list;
865 fib_node_index_t exist_path_list_index;
866 fib_node_index_t path_list_index;
869 ASSERT(1 == vec_len(rpaths));
872 * alloc the new list before we retrieve the old one, lest
873 * the alloc result in a realloc
875 path_list = fib_path_list_alloc(&path_list_index);
877 orig_path_list = fib_path_list_get(orig_path_list_index);
879 FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
881 flags = fib_path_list_flags_fixup(flags);
882 path_list->fpl_flags = flags;
884 vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
887 new_path_index = fib_path_create(path_list_index,
890 vec_foreach (orig_path_index, orig_path_list->fpl_paths)
893 * don't add duplicate paths
894 * In the unlikely event the path is a duplicate, then we'll
895 * find a matching path-list later and this one will be toast.
897 if (0 != fib_path_cmp(new_path_index, *orig_path_index))
899 path_index = fib_path_copy(*orig_path_index, path_list_index);
900 path_list->fpl_paths[pi++] = path_index;
904 _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
908 path_list->fpl_paths[pi] = new_path_index;
911 * we sort the paths since the key for the path-list is
912 * the description of the paths it contains. The paths need to
913 * be sorted else this description will differ.
915 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
917 FIB_PATH_LIST_DBG(path_list, "path-added");
920 * check for a matching path-list in the DB.
921 * If we find one then we can return the existing one and destroy the
922 * new one just created.
924 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
926 exist_path_list_index = fib_path_list_db_find(path_list);
927 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
929 fib_path_list_destroy(path_list);
931 path_list_index = exist_path_list_index;
936 * if there was not a matching path-list, then this
937 * new one will need inserting into the DB and resolving.
939 fib_path_list_db_insert(path_list_index);
941 path_list = fib_path_list_resolve(path_list);
947 * no shared path list requested. resolve and use the one
950 path_list = fib_path_list_resolve(path_list);
953 return (path_list_index);
957 * fib_path_list_path_remove
960 fib_path_list_path_remove (fib_node_index_t path_list_index,
961 const fib_route_path_t *rpaths)
963 fib_node_index_t match_path_index, tmp_path_index;
964 fib_path_list_t *path_list;
967 path_list = fib_path_list_get(path_list_index);
969 ASSERT(1 == vec_len(rpaths));
970 ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
972 FIB_PATH_LIST_DBG(orig_path_list, "path-remove");
975 * create a representation of the path to be removed, so it
976 * can be used as a comparison object during the copy.
978 tmp_path_index = fib_path_create(path_list_index,
980 match_path_index = FIB_NODE_INDEX_INVALID;
982 vec_foreach_index (pi, path_list->fpl_paths)
984 if (0 == fib_path_cmp(tmp_path_index,
985 path_list->fpl_paths[pi]))
990 match_path_index = path_list->fpl_paths[pi];
991 fib_path_destroy(match_path_index);
992 vec_del1(path_list->fpl_paths, pi);
997 * done with the temporary now
999 fib_path_destroy(tmp_path_index);
1001 return (match_path_index);
1005 * fib_path_list_copy_and_path_remove
1007 * Copy the path-list excluding the path passed.
1008 * If the path is the last one, then the index reurned will be invalid.
1009 * i.e. the path-list is toast.
1012 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
1013 fib_path_list_flags_t flags,
1014 const fib_route_path_t *rpaths)
1016 fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
1017 fib_path_list_t *path_list, *orig_path_list;
1018 fib_node_index_t pi;
1020 ASSERT(1 == vec_len(rpaths));
1022 path_list = fib_path_list_alloc(&path_list_index);
1024 flags = fib_path_list_flags_fixup(flags);
1025 orig_path_list = fib_path_list_get(orig_path_list_index);
1027 FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1029 path_list->fpl_flags = flags;
1031 * allocate as many paths as we might need in one go, rather than
1032 * using vec_add to do a few at a time.
1034 if (vec_len(orig_path_list->fpl_paths) > 1)
1036 vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
1041 * create a representation of the path to be removed, so it
1042 * can be used as a comparison object during the copy.
1044 tmp_path_index = fib_path_create(path_list_index,
1047 vec_foreach (orig_path_index, orig_path_list->fpl_paths)
1049 if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
1050 path_index = fib_path_copy(*orig_path_index, path_list_index);
1051 if (pi < vec_len(path_list->fpl_paths))
1053 path_list->fpl_paths[pi++] = path_index;
1058 * this is the unlikely case that the path being
1059 * removed does not match one in the path-list, so
1060 * we end up with as many paths as we started with.
1061 * the paths vector was sized above with the expectation
1062 * that we would have 1 less.
1064 vec_add1(path_list->fpl_paths, path_index);
1070 * done with the temporary now
1072 fib_path_destroy(tmp_path_index);
1075 * if there are no paths, then the new path-list is aborted
1077 if (0 == vec_len(path_list->fpl_paths)) {
1078 FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1080 fib_path_list_destroy(path_list);
1082 path_list_index = FIB_NODE_INDEX_INVALID;
1085 * we sort the paths since the key for the path-list is
1086 * the description of the paths it contains. The paths need to
1087 * be sorted else this description will differ.
1089 vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
1092 * If a shared path list is requested, consult the DB for a match
1094 if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1096 fib_node_index_t exist_path_list_index;
1099 * check for a matching path-list in the DB.
1100 * If we find one then we can return the existing one and destroy the
1101 * new one just created.
1103 exist_path_list_index = fib_path_list_db_find(path_list);
1104 if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1106 fib_path_list_destroy(path_list);
1108 path_list_index = exist_path_list_index;
1113 * if there was not a matching path-list, then this
1114 * new one will need inserting into the DB and resolving.
1116 fib_path_list_db_insert(path_list_index);
1118 path_list = fib_path_list_resolve(path_list);
1124 * no shared path list requested. resolve and use the one
1127 path_list = fib_path_list_resolve(path_list);
1131 return (path_list_index);
1135 * fib_path_list_contribute_forwarding
1137 * Return the index of a load-balance that user of this path-list should
1138 * use for forwarding
1141 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
1142 fib_forward_chain_type_t fct,
1143 fib_path_list_fwd_flags_t flags,
1146 fib_path_list_t *path_list;
1148 path_list = fib_path_list_get(path_list_index);
1150 fib_path_list_mk_lb(path_list, fct, dpo);
1152 ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type);
1155 * If there's only one bucket in the load-balance then we can
1158 if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1159 (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags))
1161 dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0));
1166 * fib_path_list_get_adj
1168 * Return the index of a adjacency for the first path that user of this
1169 * path-list should use for forwarding
1172 fib_path_list_get_adj (fib_node_index_t path_list_index,
1173 fib_forward_chain_type_t type)
1175 fib_path_list_t *path_list;
1177 path_list = fib_path_list_get(path_list_index);
1178 return (fib_path_get_adj(path_list->fpl_paths[0]));
1182 fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
1183 fib_node_index_t **entry_indicies)
1185 fib_node_index_t *path_index;
1186 int is_looped, list_looped;
1187 fib_path_list_t *path_list;
1190 path_list = fib_path_list_get(path_list_index);
1192 vec_foreach (path_index, path_list->fpl_paths)
1194 fib_node_index_t *copy, **copy_ptr;
1197 * we need a copy of the nodes visited so that when we add entries
1198 * we explore on the nth path and a looped is detected, those entries
1199 * are not again searched for n+1 path and so finding a loop that does
1202 copy = vec_dup(*entry_indicies);
1205 is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1206 list_looped += is_looped;
1209 FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval);
1213 path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1217 path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1220 return (list_looped);
1224 fib_path_list_child_add (fib_node_index_t path_list_index,
1225 fib_node_type_t child_type,
1226 fib_node_index_t child_index)
1230 sibling = fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
1235 if (FIB_PATH_LIST_POPULAR == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST,
1239 * Set the popular flag on the path-list once we pass the magic
1240 * threshold. then walk children to update.
1241 * We don't undo this action. The rational being that the number
1242 * of entries using this prefix is large enough such that it is a
1243 * non-trival amount of effort to converge them. If we get into the
1244 * situation where we are adding and removing entries such that we
1245 * flip-flop over the threshold, then this non-trivial work is added
1246 * to each of those routes adds/deletes - not a situation we want.
1248 fib_node_back_walk_ctx_t ctx = {
1249 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1251 fib_path_list_t *path_list;
1253 path_list = fib_path_list_get(path_list_index);
1254 path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1256 fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1263 fib_path_list_child_remove (fib_node_index_t path_list_index,
1266 fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
1272 fib_path_list_lock(fib_node_index_t path_list_index)
1274 fib_path_list_t *path_list;
1276 if (FIB_NODE_INDEX_INVALID != path_list_index)
1278 path_list = fib_path_list_get(path_list_index);
1280 fib_node_lock(&path_list->fpl_node);
1281 FIB_PATH_LIST_DBG(path_list, "lock");
1286 fib_path_list_unlock (fib_node_index_t path_list_index)
1288 fib_path_list_t *path_list;
1290 if (FIB_NODE_INDEX_INVALID != path_list_index)
1292 path_list = fib_path_list_get(path_list_index);
1293 FIB_PATH_LIST_DBG(path_list, "unlock");
1295 fib_node_unlock(&path_list->fpl_node);
1300 fib_path_list_pool_size (void)
1302 return (pool_elts(fib_path_list_pool));
1306 fib_path_list_db_size (void)
1308 return (hash_elts(fib_path_list_db));
1312 fib_path_list_walk (fib_node_index_t path_list_index,
1313 fib_path_list_walk_fn_t func,
1316 fib_node_index_t *path_index;
1317 fib_path_list_t *path_list;
1319 path_list = fib_path_list_get(path_list_index);
1321 vec_foreach(path_index, path_list->fpl_paths)
1323 if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1332 fib_path_list_module_init (void)
1334 fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1336 fib_path_list_db = hash_create2 (/* elts */ 0,
1338 /* value_bytes */ sizeof (fib_node_index_t),
1339 fib_path_list_db_hash_key_sum,
1340 fib_path_list_db_hash_key_equal,
1341 /* format pair/arg */
1345 static clib_error_t *
1346 show_fib_path_list_command (vlib_main_t * vm,
1347 unformat_input_t * input,
1348 vlib_cli_command_t * cmd)
1350 fib_path_list_t *path_list;
1351 fib_node_index_t pli;
1353 if (unformat (input, "%d", &pli))
1356 * show one in detail
1358 if (!pool_is_free_index(fib_path_list_pool, pli))
1360 path_list = fib_path_list_get(pli);
1361 u8 *s = fib_path_list_format(pli, NULL);
1362 s = format(s, "children:");
1363 s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1364 vlib_cli_output (vm, "%s", s);
1369 vlib_cli_output (vm, "path list %d invalid", pli);
1377 vlib_cli_output (vm, "FIB Path Lists");
1378 pool_foreach(path_list, fib_path_list_pool,
1380 vlib_cli_output (vm, "%U", format_fib_path_list, path_list);
1386 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1387 .path = "show fib path-lists",
1388 .function = show_fib_path_list_command,
1389 .short_help = "show fib path-lists",