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 <vlib/vlib.h>
17 #include <vnet/ip/format.h>
18 #include <vnet/ip/lookup.h>
19 #include <vnet/adj/adj.h>
20 #include <vnet/dpo/load_balance.h>
21 #include <vnet/dpo/drop_dpo.h>
23 #include <vnet/fib/fib_entry.h>
24 #include <vnet/fib/fib_walk.h>
25 #include <vnet/fib/fib_entry_src.h>
26 #include <vnet/fib/fib_entry_cover.h>
27 #include <vnet/fib/fib_table.h>
28 #include <vnet/fib/fib_internal.h>
29 #include <vnet/fib/fib_attached_export.h>
30 #include <vnet/fib/fib_path_ext.h>
33 * Array of strings/names for the FIB sources
35 static const char *fib_source_names[] = FIB_SOURCES;
36 static const char *fib_attribute_names[] = FIB_ENTRY_ATTRIBUTES;
39 * Pool for all fib_entries
41 static fib_entry_t *fib_entry_pool;
44 fib_entry_get (fib_node_index_t index)
46 return (pool_elt_at_index(fib_entry_pool, index));
50 fib_entry_get_node (fib_node_index_t index)
52 return ((fib_node_t*)fib_entry_get(index));
56 fib_entry_get_index (const fib_entry_t * fib_entry)
58 return (fib_entry - fib_entry_pool);
62 fib_entry_get_proto (const fib_entry_t * fib_entry)
64 return (fib_entry->fe_prefix.fp_proto);
67 fib_forward_chain_type_t
68 fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
70 switch (fib_entry->fe_prefix.fp_proto)
72 case FIB_PROTOCOL_IP4:
73 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
74 case FIB_PROTOCOL_IP6:
75 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
76 case FIB_PROTOCOL_MPLS:
77 if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
79 * If the entry being asked is a eos-MPLS label entry,
80 * then use the payload-protocol field, that we stashed there
81 * for just this purpose
83 return (fib_forw_chain_type_from_dpo_proto(
84 fib_entry->fe_prefix.fp_payload_proto));
86 return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
89 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
93 format_fib_entry (u8 * s, va_list * args)
95 fib_forward_chain_type_t fct;
96 fib_entry_attribute_t attr;
97 fib_path_ext_t *path_ext;
98 fib_entry_t *fib_entry;
100 fib_node_index_t fei;
105 fei = va_arg (*args, fib_node_index_t);
106 level = va_arg (*args, int);
107 fib_entry = fib_entry_get(fei);
109 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
111 if (level >= FIB_ENTRY_FORMAT_DETAIL)
113 s = format (s, " fib:%d", fib_entry->fe_fib_index);
114 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
115 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
117 FOR_EACH_SRC_ADDED(fib_entry, src, source,
119 s = format (s, "\n src:%s ",
120 fib_source_names[source]);
121 s = fib_entry_src_format(fib_entry, source, s);
122 s = format (s, " refs:%d ", src->fes_ref_count);
123 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
124 s = format(s, "flags:");
125 FOR_EACH_FIB_ATTRIBUTE(attr) {
126 if ((1<<attr) & src->fes_entry_flags) {
127 s = format (s, "%s,", fib_attribute_names[attr]);
131 s = format (s, "\n");
132 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
134 s = fib_path_list_format(src->fes_pl, s);
136 if (NULL != src->fes_path_exts)
138 s = format(s, " Extensions:");
139 vec_foreach(path_ext, src->fes_path_exts)
141 s = format(s, "\n %U", format_fib_path_ext, path_ext);
146 n_covered = fib_entry_cover_get_size(fib_entry);
148 s = format(s, "\n tracking %d covered: ", n_covered);
149 s = fib_entry_cover_list_format(fib_entry, s);
151 s = fib_ae_import_format(fib_entry, s);
152 s = fib_ae_export_format(fib_entry, s);
154 s = format (s, "\n forwarding: ");
158 s = format (s, "\n");
161 fct = fib_entry_get_default_chain_type(fib_entry);
163 if (!dpo_id_is_valid(&fib_entry->fe_lb))
165 s = format (s, " UNRESOLVED\n");
170 s = format(s, " %U-chain\n %U",
171 format_fib_forw_chain_type, fct,
177 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
179 fib_entry_delegate_type_t fdt;
180 fib_entry_delegate_t *fed;
182 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
184 s = format(s, " %U-chain\n %U",
185 format_fib_forw_chain_type,
186 fib_entry_delegate_type_to_chain_type(fdt),
187 format_dpo_id, &fed->fd_dpo, 2);
193 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
195 s = format(s, "\nchildren:");
196 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
203 fib_entry_from_fib_node (fib_node_t *node)
206 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
208 return ((fib_entry_t*)node);
212 fib_entry_last_lock_gone (fib_node_t *node)
214 fib_entry_delegate_type_t fdt;
215 fib_entry_delegate_t *fed;
216 fib_entry_t *fib_entry;
218 fib_entry = fib_entry_from_fib_node(node);
220 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
222 dpo_reset(&fed->fd_dpo);
223 fib_entry_delegate_remove(fib_entry, fdt);
226 FIB_ENTRY_DBG(fib_entry, "last-lock");
228 fib_node_deinit(&fib_entry->fe_node);
229 // FIXME -RR Backwalk
231 ASSERT(0 == vec_len(fib_entry->fe_delegates));
232 vec_free(fib_entry->fe_delegates);
233 vec_free(fib_entry->fe_srcs);
234 pool_put(fib_entry_pool, fib_entry);
237 static fib_entry_src_t*
238 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
240 fib_entry_src_t *bsrc;
243 * the enum of sources is deliberately arranged in priority order
245 if (0 == vec_len(fib_entry->fe_srcs))
251 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
258 fib_entry_src_get_source (const fib_entry_src_t *esrc)
262 return (esrc->fes_src);
264 return (FIB_SOURCE_MAX);
267 static fib_entry_flag_t
268 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
272 return (esrc->fes_entry_flags);
274 return (FIB_ENTRY_FLAG_NONE);
278 fib_entry_get_flags (fib_node_index_t fib_entry_index)
280 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
284 * fib_entry_back_walk_notify
286 * A back walk has reach this entry.
288 static fib_node_back_walk_rc_t
289 fib_entry_back_walk_notify (fib_node_t *node,
290 fib_node_back_walk_ctx_t *ctx)
292 fib_entry_t *fib_entry;
294 fib_entry = fib_entry_from_fib_node(node);
296 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
297 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
298 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
299 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
300 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
301 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
303 fib_entry_src_action_reactivate(fib_entry,
304 fib_entry_get_best_source(
305 fib_entry_get_index(fib_entry)));
309 * all other walk types can be reclassifed to a re-evaluate to
310 * all recursive dependents.
311 * By reclassifying we ensure that should any of these walk types meet
312 * they can be merged.
314 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
317 * ... and nothing is forced sync from now on.
319 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
322 * propagate the backwalk further if we haven't already reached the
325 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
326 fib_entry_get_index(fib_entry),
329 return (FIB_NODE_BACK_WALK_CONTINUE);
333 fib_entry_show_memory (void)
335 u32 n_srcs = 0, n_exts = 0;
336 fib_entry_src_t *esrc;
339 fib_show_memory_usage("Entry",
340 pool_elts(fib_entry_pool),
341 pool_len(fib_entry_pool),
342 sizeof(fib_entry_t));
344 pool_foreach(entry, fib_entry_pool,
346 n_srcs += vec_len(entry->fe_srcs);
347 vec_foreach(esrc, entry->fe_srcs)
349 n_exts += vec_len(esrc->fes_path_exts);
353 fib_show_memory_usage("Entry Source",
354 n_srcs, n_srcs, sizeof(fib_entry_src_t));
355 fib_show_memory_usage("Entry Path-Extensions",
357 sizeof(fib_path_ext_t));
361 * The FIB path-list's graph node virtual function table
363 static const fib_node_vft_t fib_entry_vft = {
364 .fnv_get = fib_entry_get_node,
365 .fnv_last_lock = fib_entry_last_lock_gone,
366 .fnv_back_walk = fib_entry_back_walk_notify,
367 .fnv_mem_show = fib_entry_show_memory,
371 * @brief Contribute the set of Adjacencies that this entry forwards with
372 * to build the uRPF list of its children
375 fib_entry_contribute_urpf (fib_node_index_t entry_index,
378 fib_entry_t *fib_entry;
380 fib_entry = fib_entry_get(entry_index);
382 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
386 * fib_entry_contribute_forwarding
388 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
391 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
392 fib_forward_chain_type_t fct,
395 fib_entry_delegate_t *fed;
396 fib_entry_t *fib_entry;
398 fib_entry = fib_entry_get(fib_entry_index);
400 if (fct == fib_entry_get_default_chain_type(fib_entry))
402 dpo_copy(dpo, &fib_entry->fe_lb);
406 fed = fib_entry_delegate_get(fib_entry,
407 fib_entry_chain_type_to_delegate_type(fct));
411 fed = fib_entry_delegate_find_or_add(
413 fib_entry_chain_type_to_delegate_type(fct));
415 * on-demand create eos/non-eos.
416 * There is no on-demand delete because:
417 * - memory versus complexity & reliability:
418 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
419 * then up on the right trigger is more code. i favour the latter.
421 fib_entry_src_mk_lb(fib_entry,
422 fib_entry_get_best_src_i(fib_entry),
427 dpo_copy(dpo, &fed->fd_dpo);
432 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
434 fib_forward_chain_type_t fct;
435 fib_entry_t *fib_entry;
437 fib_entry = fib_entry_get(fib_entry_index);
438 fct = fib_entry_get_default_chain_type(fib_entry);
440 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
441 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
443 return (&fib_entry->fe_lb);
447 fib_entry_get_adj (fib_node_index_t fib_entry_index)
451 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
452 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
456 return (dpo->dpoi_index);
458 return (ADJ_INDEX_INVALID);
462 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
464 fib_entry_t *fib_entry;
466 fib_entry = fib_entry_get(fib_entry_index);
468 return (fib_entry->fe_parent);
472 fib_entry_child_add (fib_node_index_t fib_entry_index,
473 fib_node_type_t child_type,
474 fib_node_index_t child_index)
476 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
483 fib_entry_child_remove (fib_node_index_t fib_entry_index,
486 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
490 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
494 * if there are no children left then there is no reason to keep
495 * the non-default forwarding chains. those chains are built only
496 * because the children want them.
498 fib_entry_delegate_type_t fdt;
499 fib_entry_delegate_t *fed;
500 fib_entry_t *fib_entry;
502 fib_entry = fib_entry_get(fib_entry_index);
504 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
506 dpo_reset(&fed->fd_dpo);
507 fib_entry_delegate_remove(fib_entry, fdt);
513 fib_entry_alloc (u32 fib_index,
514 const fib_prefix_t *prefix,
515 fib_node_index_t *fib_entry_index)
517 fib_entry_t *fib_entry;
520 pool_get(fib_entry_pool, fib_entry);
521 memset(fib_entry, 0, sizeof(*fib_entry));
523 fib_node_init(&fib_entry->fe_node,
524 FIB_NODE_TYPE_ENTRY);
526 fib_entry->fe_fib_index = fib_index;
529 * the one time we need to update the const prefix is when
530 * the entry is first created
532 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
535 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
538 if (MPLS_NON_EOS == fep->fp_eos)
540 fep->fp_payload_proto = DPO_PROTO_MPLS;
542 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
545 dpo_reset(&fib_entry->fe_lb);
547 *fib_entry_index = fib_entry_get_index(fib_entry);
549 FIB_ENTRY_DBG(fib_entry, "alloc");
555 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
557 fib_entry_flag_t old_flags)
560 * handle changes to attached export for import entries
562 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
563 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
565 if (!was_import && is_import)
568 * transition from not exported to exported
572 * there is an assumption here that the entry resolves via only
573 * one interface and that it is the cross VRF interface.
575 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
577 fib_attached_export_import(fib_entry,
578 fib_table_get_index_for_sw_if_index(
579 fib_entry_get_proto(fib_entry),
582 else if (was_import && !is_import)
585 * transition from exported to not exported
587 fib_attached_export_purge(fib_entry);
591 * no change. nothing to do.
595 * handle changes to attached export for export entries
597 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
598 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
600 if (!was_attached && is_attached)
603 * transition to attached. time to export
611 fib_entry_post_install_actions (fib_entry_t *fib_entry,
613 fib_entry_flag_t old_flags)
615 fib_entry_post_flag_update_actions(fib_entry, source, old_flags);
616 fib_entry_src_action_installed(fib_entry, source);
620 fib_entry_create (u32 fib_index,
621 const fib_prefix_t *prefix,
623 fib_entry_flag_t flags,
624 const fib_route_path_t *paths)
626 fib_node_index_t fib_entry_index;
627 fib_entry_t *fib_entry;
629 ASSERT(0 < vec_len(paths));
631 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
634 * since this is a new entry create, we don't need to check for winning
635 * sources - there is only one.
637 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
640 fib_entry_get_proto(fib_entry))));
641 fib_entry_src_action_path_swap(fib_entry,
646 * handle possible realloc's by refetching the pointer
648 fib_entry = fib_entry_get(fib_entry_index);
649 fib_entry_src_action_activate(fib_entry, source);
651 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
653 return (fib_entry_index);
657 fib_entry_create_special (u32 fib_index,
658 const fib_prefix_t *prefix,
660 fib_entry_flag_t flags,
663 fib_node_index_t fib_entry_index;
664 fib_entry_t *fib_entry;
667 * create and initiliase the new enty
669 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
672 * create the path-list
674 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
675 fib_entry_src_action_activate(fib_entry, source);
677 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
679 return (fib_entry_index);
683 fib_entry_post_update_actions (fib_entry_t *fib_entry,
685 fib_entry_flag_t old_flags)
688 * backwalk to children to inform then of the change to forwarding.
690 fib_node_back_walk_ctx_t bw_ctx = {
691 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
694 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
697 * then inform any covered prefixes
699 fib_entry_cover_update_notify(fib_entry);
701 fib_entry_post_install_actions(fib_entry, source, old_flags);
705 fib_entry_source_change (fib_entry_t *fib_entry,
706 fib_source_t best_source,
707 fib_source_t new_source,
708 fib_entry_flag_t old_flags)
711 * if the path list for the source passed is invalid,
712 * then we need to create a new one. else we are updating
715 if (new_source < best_source)
718 * we have a new winning source.
720 fib_entry_src_action_deactivate(fib_entry, best_source);
721 fib_entry_src_action_activate(fib_entry, new_source);
723 else if (new_source > best_source)
726 * the new source loses. nothing to do here.
727 * the data from the source is saved in the path-list created
734 * the new source is one this entry already has.
735 * But the path-list was updated, which will contribute new forwarding,
738 fib_entry_src_action_deactivate(fib_entry, new_source);
739 fib_entry_src_action_activate(fib_entry, new_source);
742 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
746 fib_entry_special_add (fib_node_index_t fib_entry_index,
748 fib_entry_flag_t flags,
751 fib_source_t best_source;
752 fib_entry_flag_t bflags;
753 fib_entry_t *fib_entry;
754 fib_entry_src_t *bsrc;
756 fib_entry = fib_entry_get(fib_entry_index);
758 bsrc = fib_entry_get_best_src_i(fib_entry);
759 best_source = fib_entry_src_get_source(bsrc);
760 bflags = fib_entry_src_get_flags(bsrc);
762 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
763 fib_entry_source_change(fib_entry, best_source, source, bflags);
767 fib_entry_special_update (fib_node_index_t fib_entry_index,
769 fib_entry_flag_t flags,
772 fib_source_t best_source;
773 fib_entry_flag_t bflags;
774 fib_entry_t *fib_entry;
775 fib_entry_src_t *bsrc;
777 fib_entry = fib_entry_get(fib_entry_index);
779 bsrc = fib_entry_get_best_src_i(fib_entry);
780 best_source = fib_entry_src_get_source(bsrc);
781 bflags = fib_entry_src_get_flags(bsrc);
783 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
784 fib_entry_source_change(fib_entry, best_source, source, bflags);
789 fib_entry_path_add (fib_node_index_t fib_entry_index,
791 fib_entry_flag_t flags,
792 const fib_route_path_t *rpath)
794 fib_source_t best_source;
795 fib_entry_flag_t bflags;
796 fib_entry_t *fib_entry;
797 fib_entry_src_t *bsrc;
799 ASSERT(1 == vec_len(rpath));
801 fib_entry = fib_entry_get(fib_entry_index);
802 ASSERT(NULL != fib_entry);
804 bsrc = fib_entry_get_best_src_i(fib_entry);
805 best_source = fib_entry_src_get_source(bsrc);
806 bflags = fib_entry_src_get_flags(bsrc);
808 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
811 * if the path list for the source passed is invalid,
812 * then we need to create a new one. else we are updating
815 if (source < best_source)
818 * we have a new winning source.
820 fib_entry_src_action_deactivate(fib_entry, best_source);
821 fib_entry_src_action_activate(fib_entry, source);
823 else if (source > best_source)
826 * the new source loses. nothing to do here.
827 * the data from the source is saved in the path-list created
834 * the new source is one this entry already has.
835 * But the path-list was updated, which will contribute new forwarding,
838 fib_entry_src_action_deactivate(fib_entry, source);
839 fib_entry_src_action_activate(fib_entry, source);
842 fib_entry_post_update_actions(fib_entry, source, bflags);
846 * fib_entry_path_remove
848 * remove a path from the entry.
849 * return the fib_entry's index if it is still present, INVALID otherwise.
852 fib_entry_path_remove (fib_node_index_t fib_entry_index,
854 const fib_route_path_t *rpath)
856 fib_entry_src_flag_t sflag;
857 fib_source_t best_source;
858 fib_entry_flag_t bflags;
859 fib_entry_t *fib_entry;
860 fib_entry_src_t *bsrc;
862 ASSERT(1 == vec_len(rpath));
864 fib_entry = fib_entry_get(fib_entry_index);
865 ASSERT(NULL != fib_entry);
867 bsrc = fib_entry_get_best_src_i(fib_entry);
868 best_source = fib_entry_src_get_source(bsrc);
869 bflags = fib_entry_src_get_flags(bsrc);
871 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
874 * if the path list for the source passed is invalid,
875 * then we need to create a new one. else we are updating
878 if (source < best_source )
881 * Que! removing a path from a source that is better than the
882 * one this entry is using.
886 else if (source > best_source )
889 * the source is not the best. nothing to do.
891 return (FIB_ENTRY_SRC_FLAG_ADDED);
896 * removing a path from the path-list we were using.
898 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
901 * the last path from the source was removed.
902 * fallback to lower source
904 bsrc = fib_entry_get_best_src_i(fib_entry);
905 best_source = fib_entry_src_get_source(bsrc);
907 if (FIB_SOURCE_MAX == best_source) {
909 * no more sources left. this entry is toast.
911 fib_entry_src_action_uninstall(fib_entry);
912 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
914 return (FIB_ENTRY_SRC_FLAG_NONE);
918 fib_entry_src_action_activate(fib_entry, best_source);
919 source = best_source;
925 * re-install the new forwarding information
927 fib_entry_src_action_deactivate(fib_entry, source);
928 fib_entry_src_action_activate(fib_entry, source);
932 fib_entry_post_update_actions(fib_entry, source, bflags);
937 return (FIB_ENTRY_SRC_FLAG_ADDED);
941 * fib_entry_special_remove
943 * remove a special source from the entry.
944 * return the fib_entry's index if it is still present, INVALID otherwise.
947 fib_entry_special_remove (fib_node_index_t fib_entry_index,
950 fib_entry_src_flag_t sflag;
951 fib_source_t best_source;
952 fib_entry_flag_t bflags;
953 fib_entry_t *fib_entry;
954 fib_entry_src_t *bsrc;
956 fib_entry = fib_entry_get(fib_entry_index);
957 ASSERT(NULL != fib_entry);
959 bsrc = fib_entry_get_best_src_i(fib_entry);
960 best_source = fib_entry_src_get_source(bsrc);
961 bflags = fib_entry_src_get_flags(bsrc);
963 sflag = fib_entry_src_action_remove(fib_entry, source);
966 * if the path list for the source passed is invalid,
967 * then we need to create a new one. else we are updating
970 if (source < best_source )
973 * Que! removing a path from a source that is better than the
974 * one this entry is using. This can only mean it is a source
975 * this prefix does not have.
977 return (FIB_ENTRY_SRC_FLAG_ADDED);
979 else if (source > best_source ) {
981 * the source is not the best. nothing to do.
983 return (FIB_ENTRY_SRC_FLAG_ADDED);
987 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
990 * the source was removed. use the next best.
992 bsrc = fib_entry_get_best_src_i(fib_entry);
993 best_source = fib_entry_src_get_source(bsrc);
995 if (FIB_SOURCE_MAX == best_source) {
997 * no more sources left. this entry is toast.
999 fib_entry_src_action_uninstall(fib_entry);
1000 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
1002 return (FIB_ENTRY_SRC_FLAG_NONE);
1006 fib_entry_src_action_activate(fib_entry, best_source);
1007 source = best_source;
1013 * re-install the new forwarding information
1015 fib_entry_src_action_reactivate(fib_entry, source);
1019 fib_entry_post_update_actions(fib_entry, source, bflags);
1022 * still have sources
1024 return (FIB_ENTRY_SRC_FLAG_ADDED);
1030 * The source is withdrawing all the paths it provided
1032 fib_entry_src_flag_t
1033 fib_entry_delete (fib_node_index_t fib_entry_index,
1034 fib_source_t source)
1036 return (fib_entry_special_remove(fib_entry_index, source));
1042 * The source has provided a new set of paths that will replace the old.
1045 fib_entry_update (fib_node_index_t fib_entry_index,
1046 fib_source_t source,
1047 fib_entry_flag_t flags,
1048 const fib_route_path_t *paths)
1050 fib_source_t best_source;
1051 fib_entry_flag_t bflags;
1052 fib_entry_t *fib_entry;
1053 fib_entry_src_t *bsrc;
1055 fib_entry = fib_entry_get(fib_entry_index);
1056 ASSERT(NULL != fib_entry);
1058 bsrc = fib_entry_get_best_src_i(fib_entry);
1059 best_source = fib_entry_src_get_source(bsrc);
1060 bflags = fib_entry_src_get_flags(bsrc);
1062 fib_entry_src_action_path_swap(fib_entry,
1067 * handle possible realloc's by refetching the pointer
1069 fib_entry = fib_entry_get(fib_entry_index);
1072 * if the path list for the source passed is invalid,
1073 * then we need to create a new one. else we are updating
1076 if (source < best_source)
1079 * we have a new winning source.
1081 fib_entry_src_action_deactivate(fib_entry, best_source);
1082 fib_entry_src_action_activate(fib_entry, source);
1084 else if (source > best_source) {
1086 * the new source loses. nothing to do here.
1087 * the data from the source is saved in the path-list created
1094 * the new source is one this entry already has.
1095 * But the path-list was updated, which will contribute new forwarding,
1098 fib_entry_src_action_deactivate(fib_entry, source);
1099 fib_entry_src_action_activate(fib_entry, source);
1102 fib_entry_post_update_actions(fib_entry, source, bflags);
1107 * fib_entry_cover_changed
1109 * this entry is tracking its cover and that cover has changed.
1112 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1114 fib_entry_src_cover_res_t res = {
1116 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1118 fib_source_t source, best_source;
1119 fib_entry_flag_t bflags;
1120 fib_entry_t *fib_entry;
1121 fib_entry_src_t *esrc;
1124 bflags = FIB_ENTRY_FLAG_NONE;
1125 best_source = FIB_SOURCE_FIRST;
1126 fib_entry = fib_entry_get(fib_entry_index);
1128 fib_attached_export_cover_change(fib_entry);
1131 * propagate the notificuation to each of the added sources
1134 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1139 * only the best source gets to set the back walk flags
1141 res = fib_entry_src_action_cover_change(fib_entry, source);
1142 bflags = fib_entry_src_get_flags(esrc);
1143 best_source = fib_entry_src_get_source(esrc);
1147 fib_entry_src_action_cover_change(fib_entry, source);
1154 fib_entry_src_action_reactivate(fib_entry,
1155 fib_entry_src_get_source(
1156 fib_entry_get_best_src_i(fib_entry)));
1157 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1161 fib_entry_src_action_uninstall(fib_entry);
1164 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1167 * time for walkies fido.
1169 fib_node_back_walk_ctx_t bw_ctx = {
1170 .fnbw_reason = res.bw_reason,
1173 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1178 * fib_entry_cover_updated
1180 * this entry is tracking its cover and that cover has been updated
1181 * (i.e. its forwarding information has changed).
1184 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1186 fib_entry_src_cover_res_t res = {
1188 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1190 fib_source_t source, best_source;
1191 fib_entry_flag_t bflags;
1192 fib_entry_t *fib_entry;
1193 fib_entry_src_t *esrc;
1196 bflags = FIB_ENTRY_FLAG_NONE;
1197 best_source = FIB_SOURCE_FIRST;
1198 fib_entry = fib_entry_get(fib_entry_index);
1200 fib_attached_export_cover_update(fib_entry);
1203 * propagate the notificuation to each of the added sources
1206 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1211 * only the best source gets to set the back walk flags
1213 res = fib_entry_src_action_cover_update(fib_entry, source);
1214 bflags = fib_entry_src_get_flags(esrc);
1215 best_source = fib_entry_src_get_source(esrc);
1219 fib_entry_src_action_cover_update(fib_entry, source);
1226 fib_entry_src_action_reactivate(fib_entry,
1227 fib_entry_src_get_source(
1228 fib_entry_get_best_src_i(fib_entry)));
1229 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1233 fib_entry_src_action_uninstall(fib_entry);
1236 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1239 * time for walkies fido.
1241 fib_node_back_walk_ctx_t bw_ctx = {
1242 .fnbw_reason = res.bw_reason,
1245 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1250 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1251 fib_node_index_t **entry_indicies)
1253 fib_entry_t *fib_entry;
1254 int was_looped, is_looped;
1256 fib_entry = fib_entry_get(entry_index);
1258 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1260 fib_node_index_t *entries = *entry_indicies;
1262 vec_add1(entries, entry_index);
1263 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1264 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1267 *entry_indicies = entries;
1269 if (!!was_looped != !!is_looped)
1272 * re-evaluate all the entry's forwarding
1273 * NOTE: this is an inplace modify
1275 fib_entry_delegate_type_t fdt;
1276 fib_entry_delegate_t *fed;
1278 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1280 fib_entry_src_mk_lb(fib_entry,
1281 fib_entry_get_best_src_i(fib_entry),
1282 fib_entry_delegate_type_to_chain_type(fdt),
1290 * the entry is currently not linked to a path-list. this happens
1291 * when it is this entry that is re-linking path-lists and has thus
1301 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1303 fib_entry_t *fib_entry;
1305 fib_entry = fib_entry_get(entry_index);
1307 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1311 fib_entry_get_best_source (fib_node_index_t entry_index)
1313 fib_entry_t *fib_entry;
1314 fib_entry_src_t *bsrc;
1316 fib_entry = fib_entry_get(entry_index);
1318 bsrc = fib_entry_get_best_src_i(fib_entry);
1319 return (fib_entry_src_get_source(bsrc));
1323 fib_ip4_address_compare (const ip4_address_t * a1,
1324 const ip4_address_t * a2)
1327 * IP addresses are unsiged ints. the return value here needs to be signed
1328 * a simple subtraction won't cut it.
1329 * If the addresses are the same, the sort order is undefiend, so phoey.
1331 return ((clib_net_to_host_u32(a1->data_u32) >
1332 clib_net_to_host_u32(a2->data_u32) ) ?
1337 fib_ip6_address_compare (const ip6_address_t * a1,
1338 const ip6_address_t * a2)
1341 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1343 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1344 clib_net_to_host_u16 (a2->as_u16[i]));
1352 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1353 fib_node_index_t fib_entry_index2)
1355 fib_entry_t *fib_entry1, *fib_entry2;
1358 fib_entry1 = fib_entry_get(fib_entry_index1);
1359 fib_entry2 = fib_entry_get(fib_entry_index2);
1361 switch (fib_entry1->fe_prefix.fp_proto)
1363 case FIB_PROTOCOL_IP4:
1364 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1365 &fib_entry2->fe_prefix.fp_addr.ip4);
1367 case FIB_PROTOCOL_IP6:
1368 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1369 &fib_entry2->fe_prefix.fp_addr.ip6);
1371 case FIB_PROTOCOL_MPLS:
1372 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1376 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1382 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1388 fib_entry_cmp_for_sort (void *i1, void *i2)
1390 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1392 return (fib_entry_cmp(*fib_entry_index1,
1393 *fib_entry_index2));
1397 fib_entry_lock (fib_node_index_t fib_entry_index)
1399 fib_entry_t *fib_entry;
1401 fib_entry = fib_entry_get(fib_entry_index);
1403 fib_node_lock(&fib_entry->fe_node);
1407 fib_entry_unlock (fib_node_index_t fib_entry_index)
1409 fib_entry_t *fib_entry;
1411 fib_entry = fib_entry_get(fib_entry_index);
1413 fib_node_unlock(&fib_entry->fe_node);
1417 fib_entry_module_init (void)
1419 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1423 fib_entry_encode (fib_node_index_t fib_entry_index,
1424 fib_route_path_encode_t **api_rpaths)
1426 fib_entry_t *fib_entry;
1428 fib_entry = fib_entry_get(fib_entry_index);
1429 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1433 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1436 fib_entry_t *fib_entry;
1438 fib_entry = fib_entry_get(fib_entry_index);
1439 *pfx = fib_entry->fe_prefix;
1443 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1445 fib_entry_t *fib_entry;
1447 fib_entry = fib_entry_get(fib_entry_index);
1449 return (fib_entry->fe_fib_index);
1453 fib_entry_pool_size (void)
1455 return (pool_elts(fib_entry_pool));
1458 static clib_error_t *
1459 show_fib_entry_command (vlib_main_t * vm,
1460 unformat_input_t * input,
1461 vlib_cli_command_t * cmd)
1463 fib_node_index_t fei;
1465 if (unformat (input, "%d", &fei))
1468 * show one in detail
1470 if (!pool_is_free_index(fib_entry_pool, fei))
1472 vlib_cli_output (vm, "%d@%U",
1474 format_fib_entry, fei,
1475 FIB_ENTRY_FORMAT_DETAIL2);
1479 vlib_cli_output (vm, "entry %d invalid", fei);
1487 vlib_cli_output (vm, "FIB Entries:");
1488 pool_foreach_index(fei, fib_entry_pool,
1490 vlib_cli_output (vm, "%d@%U",
1492 format_fib_entry, fei,
1493 FIB_ENTRY_FORMAT_BRIEF);
1500 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1501 .path = "show fib entry",
1502 .function = show_fib_entry_command,
1503 .short_help = "show fib entry",