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;
37 static const char *fib_src_attribute_names[] = FIB_ENTRY_SRC_ATTRIBUTES;
40 * Pool for all fib_entries
42 static fib_entry_t *fib_entry_pool;
45 fib_entry_get (fib_node_index_t index)
47 return (pool_elt_at_index(fib_entry_pool, index));
51 fib_entry_get_node (fib_node_index_t index)
53 return ((fib_node_t*)fib_entry_get(index));
57 fib_entry_get_index (const fib_entry_t * fib_entry)
59 return (fib_entry - fib_entry_pool);
63 fib_entry_get_proto (const fib_entry_t * fib_entry)
65 return (fib_entry->fe_prefix.fp_proto);
69 fib_entry_get_dpo_proto (const fib_entry_t * fib_entry)
71 return (fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto));
74 fib_forward_chain_type_t
75 fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
77 switch (fib_entry->fe_prefix.fp_proto)
79 case FIB_PROTOCOL_IP4:
80 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
81 case FIB_PROTOCOL_IP6:
82 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
83 case FIB_PROTOCOL_MPLS:
84 if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
85 return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
87 return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
90 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
94 format_fib_source (u8 * s, va_list * args)
96 fib_source_t source = va_arg (*args, int);
98 s = format (s, "src:%s", fib_source_names[source]);
104 format_fib_entry (u8 * s, va_list * args)
106 fib_entry_src_attribute_t sattr;
107 fib_forward_chain_type_t fct;
108 fib_entry_attribute_t attr;
109 fib_entry_t *fib_entry;
110 fib_entry_src_t *src;
111 fib_node_index_t fei;
115 fei = va_arg (*args, fib_node_index_t);
116 level = va_arg (*args, int);
117 fib_entry = fib_entry_get(fei);
119 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
121 if (level >= FIB_ENTRY_FORMAT_DETAIL)
123 s = format (s, " fib:%d", fib_entry->fe_fib_index);
124 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
125 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
127 FOR_EACH_SRC_ADDED(fib_entry, src, source,
129 s = format (s, "\n %U", format_fib_source, source);
130 s = format (s, " refs:%d", src->fes_ref_count);
131 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
132 s = format(s, " entry-flags:");
133 FOR_EACH_FIB_ATTRIBUTE(attr) {
134 if ((1<<attr) & src->fes_entry_flags) {
135 s = format (s, "%s,", fib_attribute_names[attr]);
139 if (FIB_ENTRY_SRC_FLAG_NONE != src->fes_flags) {
140 s = format(s, " src-flags:");
141 FOR_EACH_FIB_SRC_ATTRIBUTE(sattr) {
142 if ((1<<sattr) & src->fes_flags) {
143 s = format (s, "%s,", fib_src_attribute_names[sattr]);
147 s = fib_entry_src_format(fib_entry, source, s);
148 s = format (s, "\n");
149 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
151 s = fib_path_list_format(src->fes_pl, s);
153 s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
156 s = format (s, "\n forwarding: ");
160 s = format (s, "\n");
163 fct = fib_entry_get_default_chain_type(fib_entry);
165 if (!dpo_id_is_valid(&fib_entry->fe_lb))
167 s = format (s, " UNRESOLVED\n");
172 s = format(s, " %U-chain\n %U",
173 format_fib_forw_chain_type, fct,
179 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
181 fib_entry_delegate_type_t fdt;
182 fib_entry_delegate_t *fed;
184 s = format (s, " Delegates:\n");
185 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
187 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
192 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
194 s = format(s, " Children:");
195 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
202 fib_entry_from_fib_node (fib_node_t *node)
204 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
205 return ((fib_entry_t*)node);
209 fib_entry_last_lock_gone (fib_node_t *node)
211 fib_entry_delegate_type_t fdt;
212 fib_entry_delegate_t *fed;
213 fib_entry_t *fib_entry;
215 fib_entry = fib_entry_from_fib_node(node);
217 ASSERT(!dpo_id_is_valid(&fib_entry->fe_lb));
219 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
221 dpo_reset(&fed->fd_dpo);
222 fib_entry_delegate_remove(fib_entry, fdt);
225 FIB_ENTRY_DBG(fib_entry, "last-lock");
227 fib_node_deinit(&fib_entry->fe_node);
229 ASSERT(0 == vec_len(fib_entry->fe_delegates));
230 vec_free(fib_entry->fe_delegates);
231 vec_free(fib_entry->fe_srcs);
232 pool_put(fib_entry_pool, fib_entry);
235 static fib_entry_src_t*
236 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
238 fib_entry_src_t *bsrc;
241 * the enum of sources is deliberately arranged in priority order
243 if (0 == vec_len(fib_entry->fe_srcs))
249 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
256 fib_entry_src_get_source (const fib_entry_src_t *esrc)
260 return (esrc->fes_src);
262 return (FIB_SOURCE_MAX);
265 static fib_entry_flag_t
266 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
270 return (esrc->fes_entry_flags);
272 return (FIB_ENTRY_FLAG_NONE);
276 fib_entry_get_flags (fib_node_index_t fib_entry_index)
278 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
282 * fib_entry_back_walk_notify
284 * A back walk has reach this entry.
286 static fib_node_back_walk_rc_t
287 fib_entry_back_walk_notify (fib_node_t *node,
288 fib_node_back_walk_ctx_t *ctx)
290 fib_entry_t *fib_entry;
292 fib_entry = fib_entry_from_fib_node(node);
294 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
295 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
296 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
297 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
298 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
299 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
301 fib_entry_src_action_reactivate(fib_entry,
302 fib_entry_get_best_source(
303 fib_entry_get_index(fib_entry)));
307 * all other walk types can be reclassifed to a re-evaluate to
308 * all recursive dependents.
309 * By reclassifying we ensure that should any of these walk types meet
310 * they can be merged.
312 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
315 * ... and nothing is forced sync from now on.
317 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
320 * propagate the backwalk further if we haven't already reached the
323 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
324 fib_entry_get_index(fib_entry),
327 return (FIB_NODE_BACK_WALK_CONTINUE);
331 fib_entry_show_memory (void)
333 u32 n_srcs = 0, n_exts = 0;
334 fib_entry_src_t *esrc;
337 fib_show_memory_usage("Entry",
338 pool_elts(fib_entry_pool),
339 pool_len(fib_entry_pool),
340 sizeof(fib_entry_t));
342 pool_foreach(entry, fib_entry_pool,
344 n_srcs += vec_len(entry->fe_srcs);
345 vec_foreach(esrc, entry->fe_srcs)
347 n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
351 fib_show_memory_usage("Entry Source",
352 n_srcs, n_srcs, sizeof(fib_entry_src_t));
353 fib_show_memory_usage("Entry Path-Extensions",
355 sizeof(fib_path_ext_t));
359 * The FIB path-list's graph node virtual function table
361 static const fib_node_vft_t fib_entry_vft = {
362 .fnv_get = fib_entry_get_node,
363 .fnv_last_lock = fib_entry_last_lock_gone,
364 .fnv_back_walk = fib_entry_back_walk_notify,
365 .fnv_mem_show = fib_entry_show_memory,
369 * @brief Contribute the set of Adjacencies that this entry forwards with
370 * to build the uRPF list of its children
373 fib_entry_contribute_urpf (fib_node_index_t entry_index,
376 fib_entry_t *fib_entry;
378 fib_entry = fib_entry_get(entry_index);
380 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
384 * If the client is request a chain for multicast forwarding then swap
385 * the chain type to one that can provide such transport.
387 static fib_forward_chain_type_t
388 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
392 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
393 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
395 * we can only transport IP multicast packets if there is an
398 fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
400 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
401 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
402 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
403 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
404 case FIB_FORW_CHAIN_TYPE_ETHERNET:
405 case FIB_FORW_CHAIN_TYPE_NSH:
406 case FIB_FORW_CHAIN_TYPE_BIER:
414 * fib_entry_contribute_forwarding
416 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
419 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
420 fib_forward_chain_type_t fct,
423 fib_entry_delegate_t *fed;
424 fib_entry_t *fib_entry;
426 fib_entry = fib_entry_get(fib_entry_index);
429 * mfib children ask for mcast chains. fix these to the appropriate ucast types.
431 fct = fib_entry_chain_type_mcast_to_ucast(fct);
433 if (fct == fib_entry_get_default_chain_type(fib_entry))
435 dpo_copy(dpo, &fib_entry->fe_lb);
439 fed = fib_entry_delegate_get(fib_entry,
440 fib_entry_chain_type_to_delegate_type(fct));
444 fed = fib_entry_delegate_find_or_add(
446 fib_entry_chain_type_to_delegate_type(fct));
448 * on-demand create eos/non-eos.
449 * There is no on-demand delete because:
450 * - memory versus complexity & reliability:
451 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
452 * then up on the right trigger is more code. i favour the latter.
454 fib_entry_src_mk_lb(fib_entry,
455 fib_entry_get_best_src_i(fib_entry),
460 dpo_copy(dpo, &fed->fd_dpo);
463 * use the drop DPO is nothing else is present
465 if (!dpo_id_is_valid(dpo))
467 dpo_copy(dpo, drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
471 * don't allow the special index indicating replicate.vs.load-balance
472 * to escape to the clients
474 dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
478 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
480 fib_forward_chain_type_t fct;
481 fib_entry_t *fib_entry;
483 fib_entry = fib_entry_get(fib_entry_index);
484 fct = fib_entry_get_default_chain_type(fib_entry);
486 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
487 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
489 if (dpo_id_is_valid(&fib_entry->fe_lb))
491 return (&fib_entry->fe_lb);
494 return (drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
498 fib_entry_get_adj (fib_node_index_t fib_entry_index)
502 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
504 if (dpo_id_is_valid(dpo))
506 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
510 return (dpo->dpoi_index);
513 return (ADJ_INDEX_INVALID);
517 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
519 fib_entry_t *fib_entry;
521 fib_entry = fib_entry_get(fib_entry_index);
523 return (fib_entry->fe_parent);
527 fib_entry_child_add (fib_node_index_t fib_entry_index,
528 fib_node_type_t child_type,
529 fib_node_index_t child_index)
531 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
538 fib_entry_child_remove (fib_node_index_t fib_entry_index,
541 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
545 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
549 * if there are no children left then there is no reason to keep
550 * the non-default forwarding chains. those chains are built only
551 * because the children want them.
553 fib_entry_delegate_type_t fdt;
554 fib_entry_delegate_t *fed;
555 fib_entry_t *fib_entry;
557 fib_entry = fib_entry_get(fib_entry_index);
559 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
561 dpo_reset(&fed->fd_dpo);
562 fib_entry_delegate_remove(fib_entry, fdt);
568 fib_entry_alloc (u32 fib_index,
569 const fib_prefix_t *prefix,
570 fib_node_index_t *fib_entry_index)
572 fib_entry_t *fib_entry;
575 pool_get(fib_entry_pool, fib_entry);
576 memset(fib_entry, 0, sizeof(*fib_entry));
578 fib_node_init(&fib_entry->fe_node,
579 FIB_NODE_TYPE_ENTRY);
581 fib_entry->fe_fib_index = fib_index;
584 * the one time we need to update the const prefix is when
585 * the entry is first created
587 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
590 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
593 if (MPLS_NON_EOS == fep->fp_eos)
595 fep->fp_payload_proto = DPO_PROTO_MPLS;
597 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
600 dpo_reset(&fib_entry->fe_lb);
602 *fib_entry_index = fib_entry_get_index(fib_entry);
604 FIB_ENTRY_DBG(fib_entry, "alloc");
610 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
611 fib_entry_flag_t old_flags)
613 fib_node_index_t fei;
616 * save the index so we can recover from pool reallocs
618 fei = fib_entry_get_index(fib_entry);
621 * handle changes to attached export for import entries
623 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
624 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
626 if (!was_import && is_import)
629 * transition from not exported to exported
633 * there is an assumption here that the entry resolves via only
634 * one interface and that it is the cross VRF interface.
636 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
638 fib_attached_export_import(fib_entry,
639 fib_table_get_index_for_sw_if_index(
640 fib_entry_get_proto(fib_entry),
643 else if (was_import && !is_import)
646 * transition from exported to not exported
648 fib_attached_export_purge(fib_entry);
652 * no change. nothing to do.
656 * reload the entry address post possible pool realloc
658 fib_entry = fib_entry_get(fei);
661 * handle changes to attached export for export entries
663 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
664 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
666 if (!was_attached && is_attached)
669 * transition to attached. time to export
679 fib_entry_post_install_actions (fib_entry_t *fib_entry,
681 fib_entry_flag_t old_flags)
683 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
685 fib_entry_src_action_installed(fib_entry, source);
689 fib_entry_create (u32 fib_index,
690 const fib_prefix_t *prefix,
692 fib_entry_flag_t flags,
693 const fib_route_path_t *paths)
695 fib_node_index_t fib_entry_index;
696 fib_entry_t *fib_entry;
698 ASSERT(0 < vec_len(paths));
700 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
703 * since this is a new entry create, we don't need to check for winning
704 * sources - there is only one.
706 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
709 fib_entry_get_proto(fib_entry))));
710 fib_entry_src_action_path_swap(fib_entry,
715 * handle possible realloc's by refetching the pointer
717 fib_entry = fib_entry_get(fib_entry_index);
718 fib_entry_src_action_activate(fib_entry, source);
720 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
722 return (fib_entry_index);
726 fib_entry_create_special (u32 fib_index,
727 const fib_prefix_t *prefix,
729 fib_entry_flag_t flags,
732 fib_node_index_t fib_entry_index;
733 fib_entry_t *fib_entry;
736 * create and initiliase the new enty
738 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
741 * create the path-list
743 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
744 fib_entry_src_action_activate(fib_entry, source);
746 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
748 return (fib_entry_index);
752 fib_entry_post_update_actions (fib_entry_t *fib_entry,
754 fib_entry_flag_t old_flags)
757 * backwalk to children to inform then of the change to forwarding.
759 fib_node_back_walk_ctx_t bw_ctx = {
760 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
763 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
766 * then inform any covered prefixes
768 fib_entry_cover_update_notify(fib_entry);
770 fib_entry_post_install_actions(fib_entry, source, old_flags);
774 fib_entry_recalculate_forwarding (fib_node_index_t fib_entry_index)
776 fib_source_t best_source;
777 fib_entry_t *fib_entry;
778 fib_entry_src_t *bsrc;
780 fib_entry = fib_entry_get(fib_entry_index);
782 bsrc = fib_entry_get_best_src_i(fib_entry);
783 best_source = fib_entry_src_get_source(bsrc);
785 fib_entry_src_action_reactivate(fib_entry, best_source);
789 fib_entry_source_change_w_flags (fib_entry_t *fib_entry,
790 fib_source_t old_source,
791 fib_entry_flag_t old_flags,
792 fib_source_t new_source)
794 if (new_source < old_source)
797 * we have a new winning source.
799 fib_entry_src_action_deactivate(fib_entry, old_source);
800 fib_entry_src_action_activate(fib_entry, new_source);
802 else if (new_source > old_source)
805 * the new source loses. Re-activate the winning sources
806 * in case it is an interposer and hence relied on the losing
807 * source's path-list.
809 fib_entry_src_action_reactivate(fib_entry, old_source);
815 * the new source is one this entry already has.
816 * But the path-list was updated, which will contribute new forwarding,
819 fib_entry_src_action_reactivate(fib_entry, new_source);
822 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
826 fib_entry_source_change (fib_entry_t *fib_entry,
827 fib_source_t old_source,
828 fib_source_t new_source)
830 fib_entry_flag_t old_flags;
832 old_flags = fib_entry_get_flags_for_source(
833 fib_entry_get_index(fib_entry), old_source);
835 return (fib_entry_source_change_w_flags(fib_entry, old_source,
836 old_flags, new_source));
840 fib_entry_special_add (fib_node_index_t fib_entry_index,
842 fib_entry_flag_t flags,
845 fib_source_t best_source;
846 fib_entry_t *fib_entry;
848 fib_entry = fib_entry_get(fib_entry_index);
849 best_source = fib_entry_get_best_source(fib_entry_index);
851 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
852 fib_entry_source_change(fib_entry, best_source, source);
856 fib_entry_special_update (fib_node_index_t fib_entry_index,
858 fib_entry_flag_t flags,
861 fib_source_t best_source;
862 fib_entry_t *fib_entry;
864 fib_entry = fib_entry_get(fib_entry_index);
865 best_source = fib_entry_get_best_source(fib_entry_index);
867 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
868 fib_entry_source_change(fib_entry, best_source, source);
873 fib_entry_path_add (fib_node_index_t fib_entry_index,
875 fib_entry_flag_t flags,
876 const fib_route_path_t *rpath)
878 fib_source_t best_source;
879 fib_entry_t *fib_entry;
880 fib_entry_src_t *bsrc;
882 ASSERT(1 == vec_len(rpath));
884 fib_entry = fib_entry_get(fib_entry_index);
885 ASSERT(NULL != fib_entry);
887 bsrc = fib_entry_get_best_src_i(fib_entry);
888 best_source = fib_entry_src_get_source(bsrc);
890 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
892 fib_entry_source_change(fib_entry, best_source, source);
895 static fib_entry_src_flag_t
896 fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry)
898 fib_entry_src_t *src;
900 int has_only_inherited_sources = 1;
902 FOR_EACH_SRC_ADDED(fib_entry, src, source,
904 if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
906 has_only_inherited_sources = 0;
910 if (has_only_inherited_sources)
912 FOR_EACH_SRC_ADDED(fib_entry, src, source,
914 fib_entry_src_action_remove(fib_entry, source);
916 return (FIB_ENTRY_SRC_FLAG_NONE);
920 return (FIB_ENTRY_SRC_FLAG_ADDED);
924 static fib_entry_src_flag_t
925 fib_entry_source_removed (fib_entry_t *fib_entry,
926 fib_entry_flag_t old_flags)
928 const fib_entry_src_t *bsrc;
929 fib_source_t best_source;
932 * if all that is left are inherited sources, then burn them
934 fib_entry_src_burn_only_inherited(fib_entry);
936 bsrc = fib_entry_get_best_src_i(fib_entry);
937 best_source = fib_entry_src_get_source(bsrc);
939 if (FIB_SOURCE_MAX == best_source)
942 * no more sources left. this entry is toast.
944 fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags);
945 fib_entry_src_action_uninstall(fib_entry);
947 return (FIB_ENTRY_SRC_FLAG_NONE);
951 fib_entry_src_action_activate(fib_entry, best_source);
954 fib_entry_post_update_actions(fib_entry, best_source, old_flags);
959 return (FIB_ENTRY_SRC_FLAG_ADDED);
963 * fib_entry_path_remove
965 * remove a path from the entry.
966 * return the fib_entry's index if it is still present, INVALID otherwise.
969 fib_entry_path_remove (fib_node_index_t fib_entry_index,
971 const fib_route_path_t *rpath)
973 fib_entry_src_flag_t sflag;
974 fib_source_t best_source;
975 fib_entry_flag_t bflags;
976 fib_entry_t *fib_entry;
977 fib_entry_src_t *bsrc;
979 ASSERT(1 == vec_len(rpath));
981 fib_entry = fib_entry_get(fib_entry_index);
982 ASSERT(NULL != fib_entry);
984 bsrc = fib_entry_get_best_src_i(fib_entry);
985 best_source = fib_entry_src_get_source(bsrc);
986 bflags = fib_entry_src_get_flags(bsrc);
988 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
991 * if the path list for the source passed is invalid,
992 * then we need to create a new one. else we are updating
995 if (source < best_source)
998 * Que! removing a path from a source that is better than the
999 * one this entry is using.
1003 else if (source > best_source )
1006 * the source is not the best. no need to update forwarding
1008 if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1011 * the source being removed still has paths
1013 return (FIB_ENTRY_SRC_FLAG_ADDED);
1018 * that was the last path from this source, check if those
1019 * that remain are non-inherited
1021 return (fib_entry_src_burn_only_inherited(fib_entry));
1027 * removing a path from the path-list we were using.
1029 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1032 * the last path from the source was removed.
1033 * fallback to lower source
1035 return (fib_entry_source_removed(fib_entry, bflags));
1040 * re-install the new forwarding information
1042 fib_entry_src_action_reactivate(fib_entry, source);
1046 fib_entry_post_update_actions(fib_entry, source, bflags);
1049 * still have sources
1051 return (FIB_ENTRY_SRC_FLAG_ADDED);
1055 * fib_entry_special_remove
1057 * remove a special source from the entry.
1058 * return the fib_entry's index if it is still present, INVALID otherwise.
1060 fib_entry_src_flag_t
1061 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1062 fib_source_t source)
1064 fib_entry_src_flag_t sflag;
1065 fib_source_t best_source;
1066 fib_entry_flag_t bflags;
1067 fib_entry_t *fib_entry;
1068 fib_entry_src_t *bsrc;
1070 fib_entry = fib_entry_get(fib_entry_index);
1071 ASSERT(NULL != fib_entry);
1073 bsrc = fib_entry_get_best_src_i(fib_entry);
1074 best_source = fib_entry_src_get_source(bsrc);
1075 bflags = fib_entry_src_get_flags(bsrc);
1077 sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1080 * if the path list for the source passed is invalid,
1081 * then we need to create a new one. else we are updating
1084 if (source < best_source )
1087 * Que! removing a path from a source that is better than the
1088 * one this entry is using. This can only mean it is a source
1089 * this prefix does not have.
1091 return (FIB_ENTRY_SRC_FLAG_ADDED);
1093 else if (source > best_source ) {
1095 * the source is not the best. no need to update forwarding
1097 if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1100 * the source being removed still has paths
1102 return (FIB_ENTRY_SRC_FLAG_ADDED);
1107 * that was the last path from this source, check if those
1108 * that remain are non-inherited
1110 if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry))
1113 * no more sources left. this entry is toast.
1115 fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags);
1116 fib_entry_src_action_uninstall(fib_entry);
1117 return (FIB_ENTRY_SRC_FLAG_NONE);
1121 * reactivate the best source so the interposer gets restacked
1123 fib_entry_src_action_reactivate(fib_entry, best_source);
1125 return (FIB_ENTRY_SRC_FLAG_ADDED);
1130 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1133 * the source was removed. use the next best.
1135 return (fib_entry_source_removed(fib_entry, bflags));
1140 * re-install the new forwarding information
1142 fib_entry_src_action_reactivate(fib_entry, source);
1146 fib_entry_post_update_actions(fib_entry, source, bflags);
1149 * still have sources
1151 return (FIB_ENTRY_SRC_FLAG_ADDED);
1157 * If the source on the cover is inherting then push this source
1158 * down to the covered.
1161 fib_entry_inherit (fib_node_index_t cover,
1162 fib_node_index_t covered)
1164 fib_entry_src_inherit(fib_entry_get(cover),
1165 fib_entry_get(covered));
1171 * The source is withdrawing all the paths it provided
1173 fib_entry_src_flag_t
1174 fib_entry_delete (fib_node_index_t fib_entry_index,
1175 fib_source_t source)
1177 return (fib_entry_special_remove(fib_entry_index, source));
1183 * The source has provided a new set of paths that will replace the old.
1186 fib_entry_update (fib_node_index_t fib_entry_index,
1187 fib_source_t source,
1188 fib_entry_flag_t flags,
1189 const fib_route_path_t *paths)
1191 fib_source_t best_source;
1192 fib_entry_flag_t bflags;
1193 fib_entry_t *fib_entry;
1194 fib_entry_src_t *bsrc;
1196 fib_entry = fib_entry_get(fib_entry_index);
1197 ASSERT(NULL != fib_entry);
1199 bsrc = fib_entry_get_best_src_i(fib_entry);
1200 best_source = fib_entry_src_get_source(bsrc);
1201 bflags = fib_entry_get_flags_i(fib_entry);
1203 fib_entry = fib_entry_src_action_path_swap(fib_entry,
1208 fib_entry_source_change_w_flags(fib_entry, best_source, bflags, source);
1213 * fib_entry_cover_changed
1215 * this entry is tracking its cover and that cover has changed.
1218 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1220 fib_entry_src_cover_res_t res = {
1222 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1224 CLIB_UNUSED(fib_source_t source);
1225 fib_source_t best_source;
1226 fib_entry_flag_t bflags;
1227 fib_entry_t *fib_entry;
1228 fib_entry_src_t *esrc;
1231 bflags = FIB_ENTRY_FLAG_NONE;
1232 best_source = FIB_SOURCE_FIRST;
1233 fib_entry = fib_entry_get(fib_entry_index);
1235 fib_attached_export_cover_change(fib_entry);
1238 * propagate the notificuation to each of the added sources
1241 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1246 * only the best source gets to set the back walk flags
1248 res = fib_entry_src_action_cover_change(fib_entry, esrc);
1249 bflags = fib_entry_src_get_flags(esrc);
1250 best_source = fib_entry_src_get_source(esrc);
1254 fib_entry_src_action_cover_change(fib_entry, esrc);
1261 fib_entry_src_action_reactivate(fib_entry,
1262 fib_entry_src_get_source(
1263 fib_entry_get_best_src_i(fib_entry)));
1264 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1268 fib_entry_src_action_uninstall(fib_entry);
1271 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1274 * time for walkies fido.
1276 fib_node_back_walk_ctx_t bw_ctx = {
1277 .fnbw_reason = res.bw_reason,
1280 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1285 * fib_entry_cover_updated
1287 * this entry is tracking its cover and that cover has been updated
1288 * (i.e. its forwarding information has changed).
1291 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1293 fib_entry_src_cover_res_t res = {
1295 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1297 CLIB_UNUSED(fib_source_t source);
1298 fib_source_t best_source;
1299 fib_entry_flag_t bflags;
1300 fib_entry_t *fib_entry;
1301 fib_entry_src_t *esrc;
1304 bflags = FIB_ENTRY_FLAG_NONE;
1305 best_source = FIB_SOURCE_FIRST;
1306 fib_entry = fib_entry_get(fib_entry_index);
1308 fib_attached_export_cover_update(fib_entry);
1311 * propagate the notificuation to each of the added sources
1314 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1319 * only the best source gets to set the back walk flags
1321 res = fib_entry_src_action_cover_update(fib_entry, esrc);
1322 bflags = fib_entry_src_get_flags(esrc);
1323 best_source = fib_entry_src_get_source(esrc);
1327 fib_entry_src_action_cover_update(fib_entry, esrc);
1334 fib_entry_src_action_reactivate(fib_entry,
1335 fib_entry_src_get_source(
1336 fib_entry_get_best_src_i(fib_entry)));
1337 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1341 fib_entry_src_action_uninstall(fib_entry);
1344 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1347 * time for walkies fido.
1349 fib_node_back_walk_ctx_t bw_ctx = {
1350 .fnbw_reason = res.bw_reason,
1353 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1358 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1359 fib_node_index_t **entry_indicies)
1361 fib_entry_t *fib_entry;
1362 int was_looped, is_looped;
1364 fib_entry = fib_entry_get(entry_index);
1366 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1368 fib_node_index_t *entries = *entry_indicies;
1370 vec_add1(entries, entry_index);
1371 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1372 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1375 *entry_indicies = entries;
1377 if (!!was_looped != !!is_looped)
1380 * re-evaluate all the entry's forwarding
1381 * NOTE: this is an inplace modify
1383 fib_entry_delegate_type_t fdt;
1384 fib_entry_delegate_t *fed;
1386 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1388 fib_entry_src_mk_lb(fib_entry,
1389 fib_entry_get_best_src_i(fib_entry),
1390 fib_entry_delegate_type_to_chain_type(fdt),
1398 * the entry is currently not linked to a path-list. this happens
1399 * when it is this entry that is re-linking path-lists and has thus
1409 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1411 fib_entry_t *fib_entry;
1413 fib_entry = fib_entry_get(entry_index);
1415 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1419 fib_entry_get_best_source (fib_node_index_t entry_index)
1421 fib_entry_t *fib_entry;
1422 fib_entry_src_t *bsrc;
1424 fib_entry = fib_entry_get(entry_index);
1426 bsrc = fib_entry_get_best_src_i(fib_entry);
1427 return (fib_entry_src_get_source(bsrc));
1431 * Return !0 is the entry represents a host prefix
1434 fib_entry_is_host (fib_node_index_t fib_entry_index)
1436 return (fib_prefix_is_host(fib_entry_get_prefix(fib_entry_index)));
1440 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
1444 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1446 fib_entry_delegate_t *fed;
1447 fib_entry_t *fib_entry;
1449 fib_entry = fib_entry_get(fib_entry_index);
1451 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1456 * no BFD tracking - consider it resolved.
1463 * defer to the state of the BFD tracking
1465 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1470 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1471 flow_hash_config_t hash_config)
1473 fib_entry_t *fib_entry;
1475 fib_entry = fib_entry_get(fib_entry_index);
1478 * pass the hash-config on to the load-balance object where it is cached.
1479 * we can ignore LBs in the delegate chains, since they will not be of the
1480 * correct protocol type (i.e. they are not IP)
1481 * There's no way, nor need, to change the hash config for MPLS.
1483 if (dpo_id_is_valid(&fib_entry->fe_lb))
1487 ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1489 lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1492 * atomic update for packets in flight
1494 lb->lb_hash_config = hash_config;
1499 fib_entry_get_stats_index (fib_node_index_t fib_entry_index)
1501 fib_entry_t *fib_entry;
1503 fib_entry = fib_entry_get(fib_entry_index);
1505 return (fib_entry->fe_lb.dpoi_index);
1509 fib_ip4_address_compare (const ip4_address_t * a1,
1510 const ip4_address_t * a2)
1513 * IP addresses are unsiged ints. the return value here needs to be signed
1514 * a simple subtraction won't cut it.
1515 * If the addresses are the same, the sort order is undefiend, so phoey.
1517 return ((clib_net_to_host_u32(a1->data_u32) >
1518 clib_net_to_host_u32(a2->data_u32) ) ?
1523 fib_ip6_address_compare (const ip6_address_t * a1,
1524 const ip6_address_t * a2)
1527 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1529 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1530 clib_net_to_host_u16 (a2->as_u16[i]));
1538 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1539 fib_node_index_t fib_entry_index2)
1541 fib_entry_t *fib_entry1, *fib_entry2;
1544 fib_entry1 = fib_entry_get(fib_entry_index1);
1545 fib_entry2 = fib_entry_get(fib_entry_index2);
1547 switch (fib_entry1->fe_prefix.fp_proto)
1549 case FIB_PROTOCOL_IP4:
1550 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1551 &fib_entry2->fe_prefix.fp_addr.ip4);
1553 case FIB_PROTOCOL_IP6:
1554 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1555 &fib_entry2->fe_prefix.fp_addr.ip6);
1557 case FIB_PROTOCOL_MPLS:
1558 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1562 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1568 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1574 fib_entry_cmp_for_sort (void *i1, void *i2)
1576 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1578 return (fib_entry_cmp(*fib_entry_index1,
1579 *fib_entry_index2));
1583 fib_entry_lock (fib_node_index_t fib_entry_index)
1585 fib_entry_t *fib_entry;
1587 fib_entry = fib_entry_get(fib_entry_index);
1589 fib_node_lock(&fib_entry->fe_node);
1593 fib_entry_unlock (fib_node_index_t fib_entry_index)
1595 fib_entry_t *fib_entry;
1597 fib_entry = fib_entry_get(fib_entry_index);
1599 fib_node_unlock(&fib_entry->fe_node);
1603 fib_entry_module_init (void)
1605 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1609 fib_entry_encode (fib_node_index_t fib_entry_index,
1610 fib_route_path_encode_t **api_rpaths)
1612 fib_entry_t *fib_entry;
1614 fib_entry = fib_entry_get(fib_entry_index);
1615 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1617 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1621 const fib_prefix_t *
1622 fib_entry_get_prefix (fib_node_index_t fib_entry_index)
1624 fib_entry_t *fib_entry;
1626 fib_entry = fib_entry_get(fib_entry_index);
1628 return (&fib_entry->fe_prefix);
1632 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1634 fib_entry_t *fib_entry;
1636 fib_entry = fib_entry_get(fib_entry_index);
1638 return (fib_entry->fe_fib_index);
1642 fib_entry_pool_size (void)
1644 return (pool_elts(fib_entry_pool));
1647 static clib_error_t *
1648 show_fib_entry_command (vlib_main_t * vm,
1649 unformat_input_t * input,
1650 vlib_cli_command_t * cmd)
1652 fib_node_index_t fei;
1654 if (unformat (input, "%d", &fei))
1657 * show one in detail
1659 if (!pool_is_free_index(fib_entry_pool, fei))
1661 vlib_cli_output (vm, "%d@%U",
1663 format_fib_entry, fei,
1664 FIB_ENTRY_FORMAT_DETAIL2);
1668 vlib_cli_output (vm, "entry %d invalid", fei);
1676 vlib_cli_output (vm, "FIB Entries:");
1677 pool_foreach_index(fei, fib_entry_pool,
1679 vlib_cli_output (vm, "%d@%U",
1681 format_fib_entry, fei,
1682 FIB_ENTRY_FORMAT_BRIEF);
1689 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1690 .path = "show fib entry",
1691 .function = show_fib_entry_command,
1692 .short_help = "show fib entry",