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;
47 vlib_log_class_t fib_entry_logger;
50 fib_entry_get (fib_node_index_t index)
52 return (pool_elt_at_index(fib_entry_pool, index));
56 fib_entry_get_node (fib_node_index_t index)
58 return ((fib_node_t*)fib_entry_get(index));
62 fib_entry_get_index (const fib_entry_t * fib_entry)
64 return (fib_entry - fib_entry_pool);
68 fib_entry_get_proto (const fib_entry_t * fib_entry)
70 return (fib_entry->fe_prefix.fp_proto);
74 fib_entry_get_dpo_proto (const fib_entry_t * fib_entry)
76 return (fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto));
79 fib_forward_chain_type_t
80 fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
82 switch (fib_entry->fe_prefix.fp_proto)
84 case FIB_PROTOCOL_IP4:
85 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
86 case FIB_PROTOCOL_IP6:
87 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
88 case FIB_PROTOCOL_MPLS:
89 if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
90 return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
92 return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
95 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
99 format_fib_source (u8 * s, va_list * args)
101 fib_source_t source = va_arg (*args, int);
103 s = format (s, "src:%s", fib_source_names[source]);
109 format_fib_entry_flags (u8 *s, va_list *args)
111 fib_entry_attribute_t attr;
112 fib_entry_flag_t flag = va_arg(*args, int);
114 FOR_EACH_FIB_ATTRIBUTE(attr) {
115 if ((1<<attr) & flag) {
116 s = format (s, "%s,", fib_attribute_names[attr]);
124 format_fib_entry_src_flags (u8 *s, va_list *args)
126 fib_entry_src_attribute_t sattr;
127 fib_entry_src_flag_t flag = va_arg(*args, int);
129 FOR_EACH_FIB_SRC_ATTRIBUTE(sattr) {
130 if ((1<<sattr) & flag) {
131 s = format (s, "%s,", fib_src_attribute_names[sattr]);
139 format_fib_entry (u8 * s, va_list * args)
141 fib_forward_chain_type_t fct;
142 fib_entry_t *fib_entry;
143 fib_entry_src_t *src;
144 fib_node_index_t fei;
148 fei = va_arg (*args, fib_node_index_t);
149 level = va_arg (*args, int);
150 fib_entry = fib_entry_get(fei);
152 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
154 if (level >= FIB_ENTRY_FORMAT_DETAIL)
156 s = format (s, " fib:%d", fib_entry->fe_fib_index);
157 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
158 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
160 FOR_EACH_SRC_ADDED(fib_entry, src, source,
162 s = format (s, "\n %U", format_fib_source, source);
163 s = format (s, " refs:%d", src->fes_ref_count);
164 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
165 s = format(s, " entry-flags:%U",
166 format_fib_entry_flags, src->fes_entry_flags);
168 if (FIB_ENTRY_SRC_FLAG_NONE != src->fes_flags) {
169 s = format(s, " src-flags:%U",
170 format_fib_entry_src_flags, src->fes_flags);
172 s = fib_entry_src_format(fib_entry, source, s);
173 s = format (s, "\n");
174 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
176 s = fib_path_list_format(src->fes_pl, s);
178 s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
181 s = format (s, "\n forwarding: ");
185 s = format (s, "\n");
188 fct = fib_entry_get_default_chain_type(fib_entry);
190 if (!dpo_id_is_valid(&fib_entry->fe_lb))
192 s = format (s, " UNRESOLVED\n");
197 s = format(s, " %U-chain\n %U",
198 format_fib_forw_chain_type, fct,
204 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
206 fib_entry_delegate_type_t fdt;
207 fib_entry_delegate_t *fed;
209 s = format (s, " Delegates:\n");
210 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
212 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
217 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
219 s = format(s, " Children:");
220 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
227 fib_entry_from_fib_node (fib_node_t *node)
229 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
230 return ((fib_entry_t*)node);
234 fib_entry_last_lock_gone (fib_node_t *node)
236 fib_entry_delegate_type_t fdt;
237 fib_entry_delegate_t *fed;
238 fib_entry_t *fib_entry;
240 fib_entry = fib_entry_from_fib_node(node);
242 ASSERT(!dpo_id_is_valid(&fib_entry->fe_lb));
244 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
246 dpo_reset(&fed->fd_dpo);
247 fib_entry_delegate_remove(fib_entry, fdt);
250 FIB_ENTRY_DBG(fib_entry, "last-lock");
252 fib_node_deinit(&fib_entry->fe_node);
254 ASSERT(0 == vec_len(fib_entry->fe_delegates));
255 vec_free(fib_entry->fe_delegates);
256 vec_free(fib_entry->fe_srcs);
257 pool_put(fib_entry_pool, fib_entry);
260 static fib_entry_src_t*
261 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
263 fib_entry_src_t *bsrc;
266 * the enum of sources is deliberately arranged in priority order
268 if (0 == vec_len(fib_entry->fe_srcs))
274 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
281 fib_entry_src_get_source (const fib_entry_src_t *esrc)
285 return (esrc->fes_src);
287 return (FIB_SOURCE_MAX);
290 static fib_entry_flag_t
291 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
295 return (esrc->fes_entry_flags);
297 return (FIB_ENTRY_FLAG_NONE);
301 fib_entry_get_flags (fib_node_index_t fib_entry_index)
303 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
307 * fib_entry_back_walk_notify
309 * A back walk has reach this entry.
311 static fib_node_back_walk_rc_t
312 fib_entry_back_walk_notify (fib_node_t *node,
313 fib_node_back_walk_ctx_t *ctx)
315 fib_entry_t *fib_entry;
317 fib_entry = fib_entry_from_fib_node(node);
319 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
320 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
321 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
322 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
323 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
324 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
326 fib_entry_src_action_reactivate(fib_entry,
327 fib_entry_get_best_source(
328 fib_entry_get_index(fib_entry)));
332 * all other walk types can be reclassifed to a re-evaluate to
333 * all recursive dependents.
334 * By reclassifying we ensure that should any of these walk types meet
335 * they can be merged.
337 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
340 * ... and nothing is forced sync from now on.
342 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
344 FIB_ENTRY_DBG(fib_entry, "bw:%U",
345 format_fib_node_bw_reason, ctx->fnbw_reason);
348 * propagate the backwalk further if we haven't already reached the
351 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
352 fib_entry_get_index(fib_entry),
355 return (FIB_NODE_BACK_WALK_CONTINUE);
359 fib_entry_show_memory (void)
361 u32 n_srcs = 0, n_exts = 0;
362 fib_entry_src_t *esrc;
365 fib_show_memory_usage("Entry",
366 pool_elts(fib_entry_pool),
367 pool_len(fib_entry_pool),
368 sizeof(fib_entry_t));
370 pool_foreach(entry, fib_entry_pool,
372 n_srcs += vec_len(entry->fe_srcs);
373 vec_foreach(esrc, entry->fe_srcs)
375 n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
379 fib_show_memory_usage("Entry Source",
380 n_srcs, n_srcs, sizeof(fib_entry_src_t));
381 fib_show_memory_usage("Entry Path-Extensions",
383 sizeof(fib_path_ext_t));
387 * The FIB path-list's graph node virtual function table
389 static const fib_node_vft_t fib_entry_vft = {
390 .fnv_get = fib_entry_get_node,
391 .fnv_last_lock = fib_entry_last_lock_gone,
392 .fnv_back_walk = fib_entry_back_walk_notify,
393 .fnv_mem_show = fib_entry_show_memory,
397 * @brief Contribute the set of Adjacencies that this entry forwards with
398 * to build the uRPF list of its children
401 fib_entry_contribute_urpf (fib_node_index_t entry_index,
404 fib_entry_t *fib_entry;
406 fib_entry = fib_entry_get(entry_index);
408 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
412 * If the client is request a chain for multicast forwarding then swap
413 * the chain type to one that can provide such transport.
415 static fib_forward_chain_type_t
416 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
420 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
421 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
423 * we can only transport IP multicast packets if there is an
426 fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
428 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
429 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
430 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
431 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
432 case FIB_FORW_CHAIN_TYPE_ETHERNET:
433 case FIB_FORW_CHAIN_TYPE_NSH:
434 case FIB_FORW_CHAIN_TYPE_BIER:
442 * fib_entry_contribute_forwarding
444 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
447 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
448 fib_forward_chain_type_t fct,
451 fib_entry_delegate_t *fed;
452 fib_entry_t *fib_entry;
454 fib_entry = fib_entry_get(fib_entry_index);
457 * mfib children ask for mcast chains. fix these to the appropriate ucast types.
459 fct = fib_entry_chain_type_mcast_to_ucast(fct);
461 if (fct == fib_entry_get_default_chain_type(fib_entry))
463 dpo_copy(dpo, &fib_entry->fe_lb);
467 fed = fib_entry_delegate_get(fib_entry,
468 fib_entry_chain_type_to_delegate_type(fct));
472 fed = fib_entry_delegate_find_or_add(
474 fib_entry_chain_type_to_delegate_type(fct));
476 * on-demand create eos/non-eos.
477 * There is no on-demand delete because:
478 * - memory versus complexity & reliability:
479 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
480 * then up on the right trigger is more code. i favour the latter.
482 fib_entry_src_mk_lb(fib_entry,
483 fib_entry_get_best_src_i(fib_entry),
488 dpo_copy(dpo, &fed->fd_dpo);
491 * use the drop DPO is nothing else is present
493 if (!dpo_id_is_valid(dpo))
495 dpo_copy(dpo, drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
499 * don't allow the special index indicating replicate.vs.load-balance
500 * to escape to the clients
502 dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
506 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
508 fib_forward_chain_type_t fct;
509 fib_entry_t *fib_entry;
511 fib_entry = fib_entry_get(fib_entry_index);
512 fct = fib_entry_get_default_chain_type(fib_entry);
514 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
515 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
517 if (dpo_id_is_valid(&fib_entry->fe_lb))
519 return (&fib_entry->fe_lb);
522 return (drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
526 fib_entry_get_adj (fib_node_index_t fib_entry_index)
530 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
532 if (dpo_id_is_valid(dpo))
534 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
538 return (dpo->dpoi_index);
541 return (ADJ_INDEX_INVALID);
545 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
547 fib_entry_t *fib_entry;
549 fib_entry = fib_entry_get(fib_entry_index);
551 return (fib_entry->fe_parent);
555 fib_entry_child_add (fib_node_index_t fib_entry_index,
556 fib_node_type_t child_type,
557 fib_node_index_t child_index)
559 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
566 fib_entry_child_remove (fib_node_index_t fib_entry_index,
569 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
573 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
577 * if there are no children left then there is no reason to keep
578 * the non-default forwarding chains. those chains are built only
579 * because the children want them.
581 fib_entry_delegate_type_t fdt;
582 fib_entry_delegate_t *fed;
583 fib_entry_t *fib_entry;
585 fib_entry = fib_entry_get(fib_entry_index);
587 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
589 dpo_reset(&fed->fd_dpo);
590 fib_entry_delegate_remove(fib_entry, fdt);
596 fib_entry_alloc (u32 fib_index,
597 const fib_prefix_t *prefix,
598 fib_node_index_t *fib_entry_index)
600 fib_entry_t *fib_entry;
603 pool_get(fib_entry_pool, fib_entry);
604 clib_memset(fib_entry, 0, sizeof(*fib_entry));
606 fib_node_init(&fib_entry->fe_node,
607 FIB_NODE_TYPE_ENTRY);
609 fib_entry->fe_fib_index = fib_index;
612 * the one time we need to update the const prefix is when
613 * the entry is first created
615 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
618 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
621 if (MPLS_NON_EOS == fep->fp_eos)
623 fep->fp_payload_proto = DPO_PROTO_MPLS;
625 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
628 dpo_reset(&fib_entry->fe_lb);
630 *fib_entry_index = fib_entry_get_index(fib_entry);
636 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
637 fib_entry_flag_t old_flags)
639 fib_node_index_t fei;
642 * save the index so we can recover from pool reallocs
644 fei = fib_entry_get_index(fib_entry);
647 * handle changes to attached export for import entries
649 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
650 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
652 if (!was_import && is_import)
655 * transition from not exported to exported
659 * there is an assumption here that the entry resolves via only
660 * one interface and that it is the cross VRF interface.
662 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
664 fib_attached_export_import(fib_entry,
665 fib_table_get_index_for_sw_if_index(
666 fib_entry_get_proto(fib_entry),
669 else if (was_import && !is_import)
672 * transition from exported to not exported
674 fib_attached_export_purge(fib_entry);
678 * no change. nothing to do.
682 * reload the entry address post possible pool realloc
684 fib_entry = fib_entry_get(fei);
687 * handle changes to attached export for export entries
689 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
690 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
692 if (!was_attached && is_attached)
695 * transition to attached. time to export
705 fib_entry_post_install_actions (fib_entry_t *fib_entry,
707 fib_entry_flag_t old_flags)
709 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
711 fib_entry_src_action_installed(fib_entry, source);
715 fib_entry_create (u32 fib_index,
716 const fib_prefix_t *prefix,
718 fib_entry_flag_t flags,
719 const fib_route_path_t *paths)
721 fib_node_index_t fib_entry_index;
722 fib_entry_t *fib_entry;
724 ASSERT(0 < vec_len(paths));
726 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
729 * since this is a new entry create, we don't need to check for winning
730 * sources - there is only one.
732 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
735 fib_entry_get_proto(fib_entry))));
736 fib_entry_src_action_path_swap(fib_entry,
741 * handle possible realloc's by refetching the pointer
743 fib_entry = fib_entry_get(fib_entry_index);
744 fib_entry_src_action_activate(fib_entry, source);
746 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
748 FIB_ENTRY_DBG(fib_entry, "create");
750 return (fib_entry_index);
754 fib_entry_create_special (u32 fib_index,
755 const fib_prefix_t *prefix,
757 fib_entry_flag_t flags,
760 fib_node_index_t fib_entry_index;
761 fib_entry_t *fib_entry;
764 * create and initialize the new enty
766 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
769 * create the path-list
771 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
772 fib_entry_src_action_activate(fib_entry, source);
774 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
776 FIB_ENTRY_DBG(fib_entry, "create-special");
778 return (fib_entry_index);
782 fib_entry_post_update_actions (fib_entry_t *fib_entry,
784 fib_entry_flag_t old_flags)
787 * backwalk to children to inform then of the change to forwarding.
789 fib_node_back_walk_ctx_t bw_ctx = {
790 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
793 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
796 * then inform any covered prefixes
798 fib_entry_cover_update_notify(fib_entry);
800 fib_entry_post_install_actions(fib_entry, source, old_flags);
804 fib_entry_recalculate_forwarding (fib_node_index_t fib_entry_index)
806 fib_source_t best_source;
807 fib_entry_t *fib_entry;
808 fib_entry_src_t *bsrc;
810 fib_entry = fib_entry_get(fib_entry_index);
812 bsrc = fib_entry_get_best_src_i(fib_entry);
813 best_source = fib_entry_src_get_source(bsrc);
815 fib_entry_src_action_reactivate(fib_entry, best_source);
819 fib_entry_source_change_w_flags (fib_entry_t *fib_entry,
820 fib_source_t old_source,
821 fib_entry_flag_t old_flags,
822 fib_source_t new_source)
824 if (new_source < old_source)
827 * we have a new winning source.
829 fib_entry_src_action_deactivate(fib_entry, old_source);
830 fib_entry_src_action_activate(fib_entry, new_source);
832 else if (new_source > old_source)
835 * the new source loses. Re-activate the winning sources
836 * in case it is an interposer and hence relied on the losing
837 * source's path-list.
839 fib_entry_src_action_reactivate(fib_entry, old_source);
845 * the new source is one this entry already has.
846 * But the path-list was updated, which will contribute new forwarding,
849 fib_entry_src_action_reactivate(fib_entry, new_source);
852 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
856 fib_entry_source_change (fib_entry_t *fib_entry,
857 fib_source_t old_source,
858 fib_source_t new_source)
860 fib_entry_flag_t old_flags;
862 old_flags = fib_entry_get_flags_for_source(
863 fib_entry_get_index(fib_entry), old_source);
865 return (fib_entry_source_change_w_flags(fib_entry, old_source,
866 old_flags, new_source));
870 fib_entry_special_add (fib_node_index_t fib_entry_index,
872 fib_entry_flag_t flags,
875 fib_source_t best_source;
876 fib_entry_t *fib_entry;
878 fib_entry = fib_entry_get(fib_entry_index);
879 best_source = fib_entry_get_best_source(fib_entry_index);
881 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
882 fib_entry_source_change(fib_entry, best_source, source);
883 FIB_ENTRY_DBG(fib_entry, "special-add:%U", format_fib_source, source);
887 fib_entry_special_update (fib_node_index_t fib_entry_index,
889 fib_entry_flag_t flags,
892 fib_source_t best_source;
893 fib_entry_t *fib_entry;
895 fib_entry = fib_entry_get(fib_entry_index);
896 best_source = fib_entry_get_best_source(fib_entry_index);
898 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
899 fib_entry_source_change(fib_entry, best_source, source);
901 FIB_ENTRY_DBG(fib_entry, "special-updated:%U", format_fib_source, source);
906 fib_entry_path_add (fib_node_index_t fib_entry_index,
908 fib_entry_flag_t flags,
909 const fib_route_path_t *rpath)
911 fib_source_t best_source;
912 fib_entry_t *fib_entry;
913 fib_entry_src_t *bsrc;
915 ASSERT(1 == vec_len(rpath));
917 fib_entry = fib_entry_get(fib_entry_index);
918 ASSERT(NULL != fib_entry);
920 bsrc = fib_entry_get_best_src_i(fib_entry);
921 best_source = fib_entry_src_get_source(bsrc);
923 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
925 fib_entry_source_change(fib_entry, best_source, source);
927 FIB_ENTRY_DBG(fib_entry, "path add:%U", format_fib_source, source);
930 static fib_entry_src_flag_t
931 fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry)
933 fib_entry_src_t *src;
935 int has_only_inherited_sources = 1;
937 FOR_EACH_SRC_ADDED(fib_entry, src, source,
939 if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
941 has_only_inherited_sources = 0;
945 if (has_only_inherited_sources)
947 FOR_EACH_SRC_ADDED(fib_entry, src, source,
949 fib_entry_src_action_remove(fib_entry, source);
951 return (FIB_ENTRY_SRC_FLAG_NONE);
955 return (FIB_ENTRY_SRC_FLAG_ADDED);
959 static fib_entry_src_flag_t
960 fib_entry_source_removed (fib_entry_t *fib_entry,
961 fib_entry_flag_t old_flags)
963 const fib_entry_src_t *bsrc;
964 fib_source_t best_source;
967 * if all that is left are inherited sources, then burn them
969 fib_entry_src_burn_only_inherited(fib_entry);
971 bsrc = fib_entry_get_best_src_i(fib_entry);
972 best_source = fib_entry_src_get_source(bsrc);
974 if (FIB_SOURCE_MAX == best_source)
977 * no more sources left. this entry is toast.
979 fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags);
980 fib_entry_src_action_uninstall(fib_entry);
982 return (FIB_ENTRY_SRC_FLAG_NONE);
986 fib_entry_src_action_activate(fib_entry, best_source);
989 fib_entry_post_update_actions(fib_entry, best_source, old_flags);
994 return (FIB_ENTRY_SRC_FLAG_ADDED);
998 * fib_entry_path_remove
1000 * remove a path from the entry.
1001 * return the fib_entry's index if it is still present, INVALID otherwise.
1003 fib_entry_src_flag_t
1004 fib_entry_path_remove (fib_node_index_t fib_entry_index,
1005 fib_source_t source,
1006 const fib_route_path_t *rpath)
1008 fib_entry_src_flag_t sflag;
1009 fib_source_t best_source;
1010 fib_entry_flag_t bflags;
1011 fib_entry_t *fib_entry;
1012 fib_entry_src_t *bsrc;
1014 ASSERT(1 == vec_len(rpath));
1016 fib_entry = fib_entry_get(fib_entry_index);
1017 ASSERT(NULL != fib_entry);
1019 bsrc = fib_entry_get_best_src_i(fib_entry);
1020 best_source = fib_entry_src_get_source(bsrc);
1021 bflags = fib_entry_src_get_flags(bsrc);
1023 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
1025 FIB_ENTRY_DBG(fib_entry, "path remove:%U", format_fib_source, source);
1028 * if the path list for the source passed is invalid,
1029 * then we need to create a new one. else we are updating
1032 if (source < best_source)
1035 * Que! removing a path from a source that is better than the
1036 * one this entry is using.
1040 else if (source > best_source )
1043 * the source is not the best. no need to update forwarding
1045 if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1048 * the source being removed still has paths
1050 return (FIB_ENTRY_SRC_FLAG_ADDED);
1055 * that was the last path from this source, check if those
1056 * that remain are non-inherited
1058 return (fib_entry_src_burn_only_inherited(fib_entry));
1064 * removing a path from the path-list we were using.
1066 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1069 * the last path from the source was removed.
1070 * fallback to lower source
1072 return (fib_entry_source_removed(fib_entry, bflags));
1077 * re-install the new forwarding information
1079 fib_entry_src_action_reactivate(fib_entry, source);
1083 fib_entry_post_update_actions(fib_entry, source, bflags);
1086 * still have sources
1088 return (FIB_ENTRY_SRC_FLAG_ADDED);
1092 * fib_entry_special_remove
1094 * remove a special source from the entry.
1095 * return the fib_entry's index if it is still present, INVALID otherwise.
1097 fib_entry_src_flag_t
1098 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1099 fib_source_t source)
1101 fib_entry_src_flag_t sflag;
1102 fib_source_t best_source;
1103 fib_entry_flag_t bflags;
1104 fib_entry_t *fib_entry;
1105 fib_entry_src_t *bsrc;
1107 fib_entry = fib_entry_get(fib_entry_index);
1108 ASSERT(NULL != fib_entry);
1110 bsrc = fib_entry_get_best_src_i(fib_entry);
1111 best_source = fib_entry_src_get_source(bsrc);
1112 bflags = fib_entry_src_get_flags(bsrc);
1114 FIB_ENTRY_DBG(fib_entry, "special remove:%U", format_fib_source, source);
1116 sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1119 * if the path list for the source passed is invalid,
1120 * then we need to create a new one. else we are updating
1123 if (source < best_source )
1126 * Que! removing a path from a source that is better than the
1127 * one this entry is using. This can only mean it is a source
1128 * this prefix does not have.
1130 return (FIB_ENTRY_SRC_FLAG_ADDED);
1132 else if (source > best_source ) {
1134 * the source is not the best. no need to update forwarding
1136 if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1139 * the source being removed still has paths
1141 return (FIB_ENTRY_SRC_FLAG_ADDED);
1146 * that was the last path from this source, check if those
1147 * that remain are non-inherited
1149 if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry))
1152 * no more sources left. this entry is toast.
1154 fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags);
1155 fib_entry_src_action_uninstall(fib_entry);
1156 return (FIB_ENTRY_SRC_FLAG_NONE);
1160 * reactivate the best source so the interposer gets restacked
1162 fib_entry_src_action_reactivate(fib_entry, best_source);
1164 return (FIB_ENTRY_SRC_FLAG_ADDED);
1169 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1172 * the source was removed. use the next best.
1174 return (fib_entry_source_removed(fib_entry, bflags));
1179 * re-install the new forwarding information
1181 fib_entry_src_action_reactivate(fib_entry, source);
1185 fib_entry_post_update_actions(fib_entry, source, bflags);
1188 * still have sources
1190 return (FIB_ENTRY_SRC_FLAG_ADDED);
1196 * If the source on the cover is inheriting then push this source
1197 * down to the covered.
1200 fib_entry_inherit (fib_node_index_t cover,
1201 fib_node_index_t covered)
1203 fib_entry_src_inherit(fib_entry_get(cover),
1204 fib_entry_get(covered));
1210 * The source is withdrawing all the paths it provided
1212 fib_entry_src_flag_t
1213 fib_entry_delete (fib_node_index_t fib_entry_index,
1214 fib_source_t source)
1216 return (fib_entry_special_remove(fib_entry_index, source));
1222 * The source has provided a new set of paths that will replace the old.
1225 fib_entry_update (fib_node_index_t fib_entry_index,
1226 fib_source_t source,
1227 fib_entry_flag_t flags,
1228 const fib_route_path_t *paths)
1230 fib_source_t best_source;
1231 fib_entry_flag_t bflags;
1232 fib_entry_t *fib_entry;
1233 fib_entry_src_t *bsrc;
1235 fib_entry = fib_entry_get(fib_entry_index);
1236 ASSERT(NULL != fib_entry);
1238 bsrc = fib_entry_get_best_src_i(fib_entry);
1239 best_source = fib_entry_src_get_source(bsrc);
1240 bflags = fib_entry_get_flags_i(fib_entry);
1242 fib_entry = fib_entry_src_action_path_swap(fib_entry,
1247 fib_entry_source_change_w_flags(fib_entry, best_source, bflags, source);
1248 FIB_ENTRY_DBG(fib_entry, "update");
1253 * fib_entry_cover_changed
1255 * this entry is tracking its cover and that cover has changed.
1258 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1260 fib_entry_src_cover_res_t res = {
1262 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1264 CLIB_UNUSED(fib_source_t source);
1265 fib_source_t best_source;
1266 fib_entry_flag_t bflags;
1267 fib_entry_t *fib_entry;
1268 fib_entry_src_t *esrc;
1271 bflags = FIB_ENTRY_FLAG_NONE;
1272 best_source = FIB_SOURCE_FIRST;
1273 fib_entry = fib_entry_get(fib_entry_index);
1275 fib_attached_export_cover_change(fib_entry);
1278 * propagate the notification to each of the added sources
1281 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1286 * only the best source gets to set the back walk flags
1288 res = fib_entry_src_action_cover_change(fib_entry, esrc);
1289 bflags = fib_entry_src_get_flags(esrc);
1290 best_source = fib_entry_src_get_source(esrc);
1294 fib_entry_src_action_cover_change(fib_entry, esrc);
1301 fib_entry_src_action_reactivate(fib_entry,
1302 fib_entry_src_get_source(
1303 fib_entry_get_best_src_i(fib_entry)));
1304 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1308 fib_entry_src_action_uninstall(fib_entry);
1311 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1314 * time for walkies fido.
1316 fib_node_back_walk_ctx_t bw_ctx = {
1317 .fnbw_reason = res.bw_reason,
1320 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1322 FIB_ENTRY_DBG(fib_entry, "cover-changed");
1326 * fib_entry_cover_updated
1328 * this entry is tracking its cover and that cover has been updated
1329 * (i.e. its forwarding information has changed).
1332 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1334 fib_entry_src_cover_res_t res = {
1336 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1338 CLIB_UNUSED(fib_source_t source);
1339 fib_source_t best_source;
1340 fib_entry_flag_t bflags;
1341 fib_entry_t *fib_entry;
1342 fib_entry_src_t *esrc;
1345 bflags = FIB_ENTRY_FLAG_NONE;
1346 best_source = FIB_SOURCE_FIRST;
1347 fib_entry = fib_entry_get(fib_entry_index);
1349 fib_attached_export_cover_update(fib_entry);
1352 * propagate the notification to each of the added sources
1355 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1360 * only the best source gets to set the back walk flags
1362 res = fib_entry_src_action_cover_update(fib_entry, esrc);
1363 bflags = fib_entry_src_get_flags(esrc);
1364 best_source = fib_entry_src_get_source(esrc);
1368 fib_entry_src_action_cover_update(fib_entry, esrc);
1375 fib_entry_src_action_reactivate(fib_entry,
1376 fib_entry_src_get_source(
1377 fib_entry_get_best_src_i(fib_entry)));
1378 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1382 fib_entry_src_action_uninstall(fib_entry);
1385 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1388 * time for walkies fido.
1390 fib_node_back_walk_ctx_t bw_ctx = {
1391 .fnbw_reason = res.bw_reason,
1394 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1396 FIB_ENTRY_DBG(fib_entry, "cover-updated");
1400 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1401 fib_node_index_t **entry_indicies)
1403 fib_entry_t *fib_entry;
1404 int was_looped, is_looped;
1406 fib_entry = fib_entry_get(entry_index);
1408 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1410 fib_node_index_t *entries = *entry_indicies;
1412 vec_add1(entries, entry_index);
1413 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1414 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1417 *entry_indicies = entries;
1419 if (!!was_looped != !!is_looped)
1422 * re-evaluate all the entry's forwarding
1423 * NOTE: this is an inplace modify
1425 fib_entry_delegate_type_t fdt;
1426 fib_entry_delegate_t *fed;
1428 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1430 fib_entry_src_mk_lb(fib_entry,
1431 fib_entry_get_best_src_i(fib_entry),
1432 fib_entry_delegate_type_to_chain_type(fdt),
1440 * the entry is currently not linked to a path-list. this happens
1441 * when it is this entry that is re-linking path-lists and has thus
1451 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1453 fib_entry_t *fib_entry;
1455 fib_entry = fib_entry_get(entry_index);
1457 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1461 fib_entry_get_best_source (fib_node_index_t entry_index)
1463 fib_entry_t *fib_entry;
1464 fib_entry_src_t *bsrc;
1466 fib_entry = fib_entry_get(entry_index);
1468 bsrc = fib_entry_get_best_src_i(fib_entry);
1469 return (fib_entry_src_get_source(bsrc));
1473 * Return !0 is the entry represents a host prefix
1476 fib_entry_is_host (fib_node_index_t fib_entry_index)
1478 return (fib_prefix_is_host(fib_entry_get_prefix(fib_entry_index)));
1482 * Return !0 is the entry is resolved, i.e. will return a valid forwarding
1486 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1488 fib_entry_delegate_t *fed;
1489 fib_entry_t *fib_entry;
1491 fib_entry = fib_entry_get(fib_entry_index);
1493 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1498 * no BFD tracking - consider it resolved.
1505 * defer to the state of the BFD tracking
1507 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1512 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1513 flow_hash_config_t hash_config)
1515 fib_entry_t *fib_entry;
1517 fib_entry = fib_entry_get(fib_entry_index);
1520 * pass the hash-config on to the load-balance object where it is cached.
1521 * we can ignore LBs in the delegate chains, since they will not be of the
1522 * correct protocol type (i.e. they are not IP)
1523 * There's no way, nor need, to change the hash config for MPLS.
1525 if (dpo_id_is_valid(&fib_entry->fe_lb))
1529 ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1531 lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1534 * atomic update for packets in flight
1536 lb->lb_hash_config = hash_config;
1541 fib_entry_get_stats_index (fib_node_index_t fib_entry_index)
1543 fib_entry_t *fib_entry;
1545 fib_entry = fib_entry_get(fib_entry_index);
1547 return (fib_entry->fe_lb.dpoi_index);
1551 fib_ip4_address_compare (const ip4_address_t * a1,
1552 const ip4_address_t * a2)
1555 * IP addresses are unsigned ints. the return value here needs to be signed
1556 * a simple subtraction won't cut it.
1557 * If the addresses are the same, the sort order is undefined, so phoey.
1559 return ((clib_net_to_host_u32(a1->data_u32) >
1560 clib_net_to_host_u32(a2->data_u32) ) ?
1565 fib_ip6_address_compare (const ip6_address_t * a1,
1566 const ip6_address_t * a2)
1569 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1571 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1572 clib_net_to_host_u16 (a2->as_u16[i]));
1580 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1581 fib_node_index_t fib_entry_index2)
1583 fib_entry_t *fib_entry1, *fib_entry2;
1586 fib_entry1 = fib_entry_get(fib_entry_index1);
1587 fib_entry2 = fib_entry_get(fib_entry_index2);
1589 switch (fib_entry1->fe_prefix.fp_proto)
1591 case FIB_PROTOCOL_IP4:
1592 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1593 &fib_entry2->fe_prefix.fp_addr.ip4);
1595 case FIB_PROTOCOL_IP6:
1596 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1597 &fib_entry2->fe_prefix.fp_addr.ip6);
1599 case FIB_PROTOCOL_MPLS:
1600 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1604 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1610 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1616 fib_entry_cmp_for_sort (void *i1, void *i2)
1618 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1620 return (fib_entry_cmp(*fib_entry_index1,
1621 *fib_entry_index2));
1625 fib_entry_lock (fib_node_index_t fib_entry_index)
1627 fib_entry_t *fib_entry;
1629 fib_entry = fib_entry_get(fib_entry_index);
1631 fib_node_lock(&fib_entry->fe_node);
1635 fib_entry_unlock (fib_node_index_t fib_entry_index)
1637 fib_entry_t *fib_entry;
1639 fib_entry = fib_entry_get(fib_entry_index);
1641 fib_node_unlock(&fib_entry->fe_node);
1645 fib_entry_module_init (void)
1647 fib_node_register_type(FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1648 fib_entry_logger = vlib_log_register_class("fib", "entry");
1652 fib_entry_encode (fib_node_index_t fib_entry_index,
1653 fib_route_path_encode_t **api_rpaths)
1655 fib_path_ext_list_t *ext_list;
1656 fib_entry_t *fib_entry;
1657 fib_entry_src_t *bsrc;
1660 fib_entry = fib_entry_get(fib_entry_index);
1661 bsrc = fib_entry_get_best_src_i(fib_entry);
1665 ext_list = &bsrc->fes_path_exts;
1668 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1670 fib_path_list_walk_w_ext(fib_entry->fe_parent,
1677 const fib_prefix_t *
1678 fib_entry_get_prefix (fib_node_index_t fib_entry_index)
1680 fib_entry_t *fib_entry;
1682 fib_entry = fib_entry_get(fib_entry_index);
1684 return (&fib_entry->fe_prefix);
1688 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1690 fib_entry_t *fib_entry;
1692 fib_entry = fib_entry_get(fib_entry_index);
1694 return (fib_entry->fe_fib_index);
1698 fib_entry_pool_size (void)
1700 return (pool_elts(fib_entry_pool));
1703 static clib_error_t *
1704 show_fib_entry_command (vlib_main_t * vm,
1705 unformat_input_t * input,
1706 vlib_cli_command_t * cmd)
1708 fib_node_index_t fei;
1710 if (unformat (input, "%d", &fei))
1713 * show one in detail
1715 if (!pool_is_free_index(fib_entry_pool, fei))
1717 vlib_cli_output (vm, "%d@%U",
1719 format_fib_entry, fei,
1720 FIB_ENTRY_FORMAT_DETAIL2);
1724 vlib_cli_output (vm, "entry %d invalid", fei);
1732 vlib_cli_output (vm, "FIB Entries:");
1733 pool_foreach_index(fei, fib_entry_pool,
1735 vlib_cli_output (vm, "%d@%U",
1737 format_fib_entry, fei,
1738 FIB_ENTRY_FORMAT_BRIEF);
1745 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1746 .path = "show fib entry",
1747 .function = show_fib_entry_command,
1748 .short_help = "show fib entry",