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)
78 return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
80 return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
83 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
87 format_fib_entry (u8 * s, va_list * args)
89 fib_forward_chain_type_t fct;
90 fib_entry_attribute_t attr;
91 fib_path_ext_t *path_ext;
92 fib_entry_t *fib_entry;
98 fei = va_arg (*args, fib_node_index_t);
99 level = va_arg (*args, int);
100 fib_entry = fib_entry_get(fei);
102 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
104 if (level >= FIB_ENTRY_FORMAT_DETAIL)
106 s = format (s, " fib:%d", fib_entry->fe_fib_index);
107 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
108 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
110 FOR_EACH_SRC_ADDED(fib_entry, src, source,
112 s = format (s, "\n src:%s ",
113 fib_source_names[source]);
114 s = fib_entry_src_format(fib_entry, source, s);
115 s = format (s, " refs:%d ", src->fes_ref_count);
116 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
117 s = format(s, "flags:");
118 FOR_EACH_FIB_ATTRIBUTE(attr) {
119 if ((1<<attr) & src->fes_entry_flags) {
120 s = format (s, "%s,", fib_attribute_names[attr]);
124 s = format (s, "\n");
125 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
127 s = fib_path_list_format(src->fes_pl, s);
129 if (NULL != src->fes_path_exts)
131 s = format(s, " Extensions:");
132 vec_foreach(path_ext, src->fes_path_exts)
134 s = format(s, "\n %U", format_fib_path_ext, path_ext);
139 s = format (s, "\n forwarding: ");
143 s = format (s, "\n");
146 fct = fib_entry_get_default_chain_type(fib_entry);
148 if (!dpo_id_is_valid(&fib_entry->fe_lb))
150 s = format (s, " UNRESOLVED\n");
155 s = format(s, " %U-chain\n %U",
156 format_fib_forw_chain_type, fct,
162 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
164 fib_entry_delegate_type_t fdt;
165 fib_entry_delegate_t *fed;
167 s = format (s, " Delegates:\n");
168 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
170 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
175 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
177 s = format(s, " Children:");
178 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
185 fib_entry_from_fib_node (fib_node_t *node)
188 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
190 return ((fib_entry_t*)node);
194 fib_entry_last_lock_gone (fib_node_t *node)
196 fib_entry_delegate_type_t fdt;
197 fib_entry_delegate_t *fed;
198 fib_entry_t *fib_entry;
200 fib_entry = fib_entry_from_fib_node(node);
202 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
204 dpo_reset(&fed->fd_dpo);
205 fib_entry_delegate_remove(fib_entry, fdt);
208 FIB_ENTRY_DBG(fib_entry, "last-lock");
210 fib_node_deinit(&fib_entry->fe_node);
211 // FIXME -RR Backwalk
213 ASSERT(0 == vec_len(fib_entry->fe_delegates));
214 vec_free(fib_entry->fe_delegates);
215 vec_free(fib_entry->fe_srcs);
216 pool_put(fib_entry_pool, fib_entry);
219 static fib_entry_src_t*
220 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
222 fib_entry_src_t *bsrc;
225 * the enum of sources is deliberately arranged in priority order
227 if (0 == vec_len(fib_entry->fe_srcs))
233 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
240 fib_entry_src_get_source (const fib_entry_src_t *esrc)
244 return (esrc->fes_src);
246 return (FIB_SOURCE_MAX);
249 static fib_entry_flag_t
250 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
254 return (esrc->fes_entry_flags);
256 return (FIB_ENTRY_FLAG_NONE);
260 fib_entry_get_flags (fib_node_index_t fib_entry_index)
262 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
266 * fib_entry_back_walk_notify
268 * A back walk has reach this entry.
270 static fib_node_back_walk_rc_t
271 fib_entry_back_walk_notify (fib_node_t *node,
272 fib_node_back_walk_ctx_t *ctx)
274 fib_entry_t *fib_entry;
276 fib_entry = fib_entry_from_fib_node(node);
278 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
279 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
280 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
281 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
282 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
283 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
285 fib_entry_src_action_reactivate(fib_entry,
286 fib_entry_get_best_source(
287 fib_entry_get_index(fib_entry)));
291 * all other walk types can be reclassifed to a re-evaluate to
292 * all recursive dependents.
293 * By reclassifying we ensure that should any of these walk types meet
294 * they can be merged.
296 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
299 * ... and nothing is forced sync from now on.
301 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
304 * propagate the backwalk further if we haven't already reached the
307 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
308 fib_entry_get_index(fib_entry),
311 return (FIB_NODE_BACK_WALK_CONTINUE);
315 fib_entry_show_memory (void)
317 u32 n_srcs = 0, n_exts = 0;
318 fib_entry_src_t *esrc;
321 fib_show_memory_usage("Entry",
322 pool_elts(fib_entry_pool),
323 pool_len(fib_entry_pool),
324 sizeof(fib_entry_t));
326 pool_foreach(entry, fib_entry_pool,
328 n_srcs += vec_len(entry->fe_srcs);
329 vec_foreach(esrc, entry->fe_srcs)
331 n_exts += vec_len(esrc->fes_path_exts);
335 fib_show_memory_usage("Entry Source",
336 n_srcs, n_srcs, sizeof(fib_entry_src_t));
337 fib_show_memory_usage("Entry Path-Extensions",
339 sizeof(fib_path_ext_t));
343 * The FIB path-list's graph node virtual function table
345 static const fib_node_vft_t fib_entry_vft = {
346 .fnv_get = fib_entry_get_node,
347 .fnv_last_lock = fib_entry_last_lock_gone,
348 .fnv_back_walk = fib_entry_back_walk_notify,
349 .fnv_mem_show = fib_entry_show_memory,
353 * @brief Contribute the set of Adjacencies that this entry forwards with
354 * to build the uRPF list of its children
357 fib_entry_contribute_urpf (fib_node_index_t entry_index,
360 fib_entry_t *fib_entry;
362 fib_entry = fib_entry_get(entry_index);
364 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
368 * If the client is request a chain for multicast forwarding then swap
369 * the chain type to one that can provide such transport.
371 static fib_forward_chain_type_t
372 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
376 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
377 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
379 * we can only transport IP multicast packets if there is an
382 fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
384 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
385 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
386 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
387 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
388 case FIB_FORW_CHAIN_TYPE_ETHERNET:
389 case FIB_FORW_CHAIN_TYPE_NSH:
397 * fib_entry_contribute_forwarding
399 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
402 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
403 fib_forward_chain_type_t fct,
406 fib_entry_delegate_t *fed;
407 fib_entry_t *fib_entry;
409 fib_entry = fib_entry_get(fib_entry_index);
412 * mfib children ask for mcast chains. fix these to the appropriate ucast types.
414 fct = fib_entry_chain_type_mcast_to_ucast(fct);
416 if (fct == fib_entry_get_default_chain_type(fib_entry))
418 dpo_copy(dpo, &fib_entry->fe_lb);
422 fed = fib_entry_delegate_get(fib_entry,
423 fib_entry_chain_type_to_delegate_type(fct));
427 fed = fib_entry_delegate_find_or_add(
429 fib_entry_chain_type_to_delegate_type(fct));
431 * on-demand create eos/non-eos.
432 * There is no on-demand delete because:
433 * - memory versus complexity & reliability:
434 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
435 * then up on the right trigger is more code. i favour the latter.
437 fib_entry_src_mk_lb(fib_entry,
438 fib_entry_get_best_src_i(fib_entry),
443 dpo_copy(dpo, &fed->fd_dpo);
446 * don't allow the special index indicating replicate.vs.load-balance
447 * to escape to the clients
449 dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
453 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
455 fib_forward_chain_type_t fct;
456 fib_entry_t *fib_entry;
458 fib_entry = fib_entry_get(fib_entry_index);
459 fct = fib_entry_get_default_chain_type(fib_entry);
461 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
462 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
464 return (&fib_entry->fe_lb);
468 fib_entry_get_adj (fib_node_index_t fib_entry_index)
472 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
473 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
477 return (dpo->dpoi_index);
479 return (ADJ_INDEX_INVALID);
483 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
485 fib_entry_t *fib_entry;
487 fib_entry = fib_entry_get(fib_entry_index);
489 return (fib_entry->fe_parent);
493 fib_entry_child_add (fib_node_index_t fib_entry_index,
494 fib_node_type_t child_type,
495 fib_node_index_t child_index)
497 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
504 fib_entry_child_remove (fib_node_index_t fib_entry_index,
507 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
511 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
515 * if there are no children left then there is no reason to keep
516 * the non-default forwarding chains. those chains are built only
517 * because the children want them.
519 fib_entry_delegate_type_t fdt;
520 fib_entry_delegate_t *fed;
521 fib_entry_t *fib_entry;
523 fib_entry = fib_entry_get(fib_entry_index);
525 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
527 dpo_reset(&fed->fd_dpo);
528 fib_entry_delegate_remove(fib_entry, fdt);
534 fib_entry_alloc (u32 fib_index,
535 const fib_prefix_t *prefix,
536 fib_node_index_t *fib_entry_index)
538 fib_entry_t *fib_entry;
541 pool_get(fib_entry_pool, fib_entry);
542 memset(fib_entry, 0, sizeof(*fib_entry));
544 fib_node_init(&fib_entry->fe_node,
545 FIB_NODE_TYPE_ENTRY);
547 fib_entry->fe_fib_index = fib_index;
550 * the one time we need to update the const prefix is when
551 * the entry is first created
553 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
556 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
559 if (MPLS_NON_EOS == fep->fp_eos)
561 fep->fp_payload_proto = DPO_PROTO_MPLS;
563 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
566 dpo_reset(&fib_entry->fe_lb);
568 *fib_entry_index = fib_entry_get_index(fib_entry);
570 FIB_ENTRY_DBG(fib_entry, "alloc");
576 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
578 fib_entry_flag_t old_flags)
580 fib_node_index_t fei;
583 * save the index so we can recover from pool reallocs
585 fei = fib_entry_get_index(fib_entry);
588 * handle changes to attached export for import entries
590 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
591 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
593 if (!was_import && is_import)
596 * transition from not exported to exported
600 * there is an assumption here that the entry resolves via only
601 * one interface and that it is the cross VRF interface.
603 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
605 fib_attached_export_import(fib_entry,
606 fib_table_get_index_for_sw_if_index(
607 fib_entry_get_proto(fib_entry),
610 else if (was_import && !is_import)
613 * transition from exported to not exported
615 fib_attached_export_purge(fib_entry);
619 * no change. nothing to do.
623 * reload the entry address post possible pool realloc
625 fib_entry = fib_entry_get(fei);
628 * handle changes to attached export for export entries
630 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
631 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
633 if (!was_attached && is_attached)
636 * transition to attached. time to export
646 fib_entry_post_install_actions (fib_entry_t *fib_entry,
648 fib_entry_flag_t old_flags)
650 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
653 fib_entry_src_action_installed(fib_entry, source);
657 fib_entry_create (u32 fib_index,
658 const fib_prefix_t *prefix,
660 fib_entry_flag_t flags,
661 const fib_route_path_t *paths)
663 fib_node_index_t fib_entry_index;
664 fib_entry_t *fib_entry;
666 ASSERT(0 < vec_len(paths));
668 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
671 * since this is a new entry create, we don't need to check for winning
672 * sources - there is only one.
674 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
677 fib_entry_get_proto(fib_entry))));
678 fib_entry_src_action_path_swap(fib_entry,
683 * handle possible realloc's by refetching the pointer
685 fib_entry = fib_entry_get(fib_entry_index);
686 fib_entry_src_action_activate(fib_entry, source);
688 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
690 return (fib_entry_index);
694 fib_entry_create_special (u32 fib_index,
695 const fib_prefix_t *prefix,
697 fib_entry_flag_t flags,
700 fib_node_index_t fib_entry_index;
701 fib_entry_t *fib_entry;
704 * create and initiliase the new enty
706 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
709 * create the path-list
711 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
712 fib_entry_src_action_activate(fib_entry, source);
714 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
716 return (fib_entry_index);
720 fib_entry_post_update_actions (fib_entry_t *fib_entry,
722 fib_entry_flag_t old_flags)
725 * backwalk to children to inform then of the change to forwarding.
727 fib_node_back_walk_ctx_t bw_ctx = {
728 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
731 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
734 * then inform any covered prefixes
736 fib_entry_cover_update_notify(fib_entry);
738 fib_entry_post_install_actions(fib_entry, source, old_flags);
742 fib_entry_source_change (fib_entry_t *fib_entry,
743 fib_source_t best_source,
744 fib_source_t new_source,
745 fib_entry_flag_t old_flags)
748 * if the path list for the source passed is invalid,
749 * then we need to create a new one. else we are updating
752 if (new_source < best_source)
755 * we have a new winning source.
757 fib_entry_src_action_deactivate(fib_entry, best_source);
758 fib_entry_src_action_activate(fib_entry, new_source);
760 else if (new_source > best_source)
763 * the new source loses. nothing to do here.
764 * the data from the source is saved in the path-list created
771 * the new source is one this entry already has.
772 * But the path-list was updated, which will contribute new forwarding,
775 fib_entry_src_action_deactivate(fib_entry, new_source);
776 fib_entry_src_action_activate(fib_entry, new_source);
779 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
783 fib_entry_special_add (fib_node_index_t fib_entry_index,
785 fib_entry_flag_t flags,
788 fib_source_t best_source;
789 fib_entry_flag_t bflags;
790 fib_entry_t *fib_entry;
791 fib_entry_src_t *bsrc;
793 fib_entry = fib_entry_get(fib_entry_index);
795 bsrc = fib_entry_get_best_src_i(fib_entry);
796 best_source = fib_entry_src_get_source(bsrc);
797 bflags = fib_entry_src_get_flags(bsrc);
799 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
800 fib_entry_source_change(fib_entry, best_source, source, bflags);
804 fib_entry_special_update (fib_node_index_t fib_entry_index,
806 fib_entry_flag_t flags,
809 fib_source_t best_source;
810 fib_entry_flag_t bflags;
811 fib_entry_t *fib_entry;
812 fib_entry_src_t *bsrc;
814 fib_entry = fib_entry_get(fib_entry_index);
816 bsrc = fib_entry_get_best_src_i(fib_entry);
817 best_source = fib_entry_src_get_source(bsrc);
818 bflags = fib_entry_src_get_flags(bsrc);
820 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
821 fib_entry_source_change(fib_entry, best_source, source, bflags);
826 fib_entry_path_add (fib_node_index_t fib_entry_index,
828 fib_entry_flag_t flags,
829 const fib_route_path_t *rpath)
831 fib_source_t best_source;
832 fib_entry_flag_t bflags;
833 fib_entry_t *fib_entry;
834 fib_entry_src_t *bsrc;
836 ASSERT(1 == vec_len(rpath));
838 fib_entry = fib_entry_get(fib_entry_index);
839 ASSERT(NULL != fib_entry);
841 bsrc = fib_entry_get_best_src_i(fib_entry);
842 best_source = fib_entry_src_get_source(bsrc);
843 bflags = fib_entry_src_get_flags(bsrc);
845 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
848 * if the path list for the source passed is invalid,
849 * then we need to create a new one. else we are updating
852 if (source < best_source)
855 * we have a new winning source.
857 fib_entry_src_action_deactivate(fib_entry, best_source);
858 fib_entry_src_action_activate(fib_entry, source);
860 else if (source > best_source)
863 * the new source loses. nothing to do here.
864 * the data from the source is saved in the path-list created
871 * the new source is one this entry already has.
872 * But the path-list was updated, which will contribute new forwarding,
875 fib_entry_src_action_deactivate(fib_entry, source);
876 fib_entry_src_action_activate(fib_entry, source);
879 fib_entry_post_update_actions(fib_entry, source, bflags);
883 * fib_entry_path_remove
885 * remove a path from the entry.
886 * return the fib_entry's index if it is still present, INVALID otherwise.
889 fib_entry_path_remove (fib_node_index_t fib_entry_index,
891 const fib_route_path_t *rpath)
893 fib_entry_src_flag_t sflag;
894 fib_source_t best_source;
895 fib_entry_flag_t bflags;
896 fib_entry_t *fib_entry;
897 fib_entry_src_t *bsrc;
899 ASSERT(1 == vec_len(rpath));
901 fib_entry = fib_entry_get(fib_entry_index);
902 ASSERT(NULL != fib_entry);
904 bsrc = fib_entry_get_best_src_i(fib_entry);
905 best_source = fib_entry_src_get_source(bsrc);
906 bflags = fib_entry_src_get_flags(bsrc);
908 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
911 * if the path list for the source passed is invalid,
912 * then we need to create a new one. else we are updating
915 if (source < best_source )
918 * Que! removing a path from a source that is better than the
919 * one this entry is using.
923 else if (source > best_source )
926 * the source is not the best. nothing to do.
928 return (FIB_ENTRY_SRC_FLAG_ADDED);
933 * removing a path from the path-list we were using.
935 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
938 * the last path from the source was removed.
939 * fallback to lower source
941 bsrc = fib_entry_get_best_src_i(fib_entry);
942 best_source = fib_entry_src_get_source(bsrc);
944 if (FIB_SOURCE_MAX == best_source) {
946 * no more sources left. this entry is toast.
948 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
951 fib_entry_src_action_uninstall(fib_entry);
953 return (FIB_ENTRY_SRC_FLAG_NONE);
957 fib_entry_src_action_activate(fib_entry, best_source);
958 source = best_source;
964 * re-install the new forwarding information
966 fib_entry_src_action_deactivate(fib_entry, source);
967 fib_entry_src_action_activate(fib_entry, source);
971 fib_entry_post_update_actions(fib_entry, source, bflags);
976 return (FIB_ENTRY_SRC_FLAG_ADDED);
980 * fib_entry_special_remove
982 * remove a special source from the entry.
983 * return the fib_entry's index if it is still present, INVALID otherwise.
986 fib_entry_special_remove (fib_node_index_t fib_entry_index,
989 fib_entry_src_flag_t sflag;
990 fib_source_t best_source;
991 fib_entry_flag_t bflags;
992 fib_entry_t *fib_entry;
993 fib_entry_src_t *bsrc;
995 fib_entry = fib_entry_get(fib_entry_index);
996 ASSERT(NULL != fib_entry);
998 bsrc = fib_entry_get_best_src_i(fib_entry);
999 best_source = fib_entry_src_get_source(bsrc);
1000 bflags = fib_entry_src_get_flags(bsrc);
1002 sflag = fib_entry_src_action_remove(fib_entry, source);
1005 * if the path list for the source passed is invalid,
1006 * then we need to create a new one. else we are updating
1009 if (source < best_source )
1012 * Que! removing a path from a source that is better than the
1013 * one this entry is using. This can only mean it is a source
1014 * this prefix does not have.
1016 return (FIB_ENTRY_SRC_FLAG_ADDED);
1018 else if (source > best_source ) {
1020 * the source is not the best. nothing to do.
1022 return (FIB_ENTRY_SRC_FLAG_ADDED);
1026 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1029 * the source was removed. use the next best.
1031 bsrc = fib_entry_get_best_src_i(fib_entry);
1032 best_source = fib_entry_src_get_source(bsrc);
1034 if (FIB_SOURCE_MAX == best_source) {
1036 * no more sources left. this entry is toast.
1038 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
1041 fib_entry_src_action_uninstall(fib_entry);
1043 return (FIB_ENTRY_SRC_FLAG_NONE);
1047 fib_entry_src_action_activate(fib_entry, best_source);
1048 source = best_source;
1054 * re-install the new forwarding information
1056 fib_entry_src_action_reactivate(fib_entry, source);
1060 fib_entry_post_update_actions(fib_entry, source, bflags);
1063 * still have sources
1065 return (FIB_ENTRY_SRC_FLAG_ADDED);
1071 * The source is withdrawing all the paths it provided
1073 fib_entry_src_flag_t
1074 fib_entry_delete (fib_node_index_t fib_entry_index,
1075 fib_source_t source)
1077 return (fib_entry_special_remove(fib_entry_index, source));
1083 * The source has provided a new set of paths that will replace the old.
1086 fib_entry_update (fib_node_index_t fib_entry_index,
1087 fib_source_t source,
1088 fib_entry_flag_t flags,
1089 const fib_route_path_t *paths)
1091 fib_source_t best_source;
1092 fib_entry_flag_t bflags;
1093 fib_entry_t *fib_entry;
1094 fib_entry_src_t *bsrc;
1096 fib_entry = fib_entry_get(fib_entry_index);
1097 ASSERT(NULL != fib_entry);
1099 bsrc = fib_entry_get_best_src_i(fib_entry);
1100 best_source = fib_entry_src_get_source(bsrc);
1101 bflags = fib_entry_src_get_flags(bsrc);
1103 fib_entry_src_action_path_swap(fib_entry,
1108 * handle possible realloc's by refetching the pointer
1110 fib_entry = fib_entry_get(fib_entry_index);
1113 * if the path list for the source passed is invalid,
1114 * then we need to create a new one. else we are updating
1117 if (source < best_source)
1120 * we have a new winning source.
1122 fib_entry_src_action_deactivate(fib_entry, best_source);
1123 fib_entry_src_action_activate(fib_entry, source);
1125 else if (source > best_source) {
1127 * the new source loses. nothing to do here.
1128 * the data from the source is saved in the path-list created
1135 * the new source is one this entry already has.
1136 * But the path-list was updated, which will contribute new forwarding,
1139 fib_entry_src_action_deactivate(fib_entry, source);
1140 fib_entry_src_action_activate(fib_entry, source);
1143 fib_entry_post_update_actions(fib_entry, source, bflags);
1148 * fib_entry_cover_changed
1150 * this entry is tracking its cover and that cover has changed.
1153 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1155 fib_entry_src_cover_res_t res = {
1157 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1159 fib_source_t source, best_source;
1160 fib_entry_flag_t bflags;
1161 fib_entry_t *fib_entry;
1162 fib_entry_src_t *esrc;
1165 bflags = FIB_ENTRY_FLAG_NONE;
1166 best_source = FIB_SOURCE_FIRST;
1167 fib_entry = fib_entry_get(fib_entry_index);
1169 fib_attached_export_cover_change(fib_entry);
1172 * propagate the notificuation to each of the added sources
1175 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1180 * only the best source gets to set the back walk flags
1182 res = fib_entry_src_action_cover_change(fib_entry, source);
1183 bflags = fib_entry_src_get_flags(esrc);
1184 best_source = fib_entry_src_get_source(esrc);
1188 fib_entry_src_action_cover_change(fib_entry, source);
1195 fib_entry_src_action_reactivate(fib_entry,
1196 fib_entry_src_get_source(
1197 fib_entry_get_best_src_i(fib_entry)));
1198 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1202 fib_entry_src_action_uninstall(fib_entry);
1205 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1208 * time for walkies fido.
1210 fib_node_back_walk_ctx_t bw_ctx = {
1211 .fnbw_reason = res.bw_reason,
1214 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1219 * fib_entry_cover_updated
1221 * this entry is tracking its cover and that cover has been updated
1222 * (i.e. its forwarding information has changed).
1225 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1227 fib_entry_src_cover_res_t res = {
1229 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1231 fib_source_t source, best_source;
1232 fib_entry_flag_t bflags;
1233 fib_entry_t *fib_entry;
1234 fib_entry_src_t *esrc;
1237 bflags = FIB_ENTRY_FLAG_NONE;
1238 best_source = FIB_SOURCE_FIRST;
1239 fib_entry = fib_entry_get(fib_entry_index);
1241 fib_attached_export_cover_update(fib_entry);
1244 * propagate the notificuation to each of the added sources
1247 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1252 * only the best source gets to set the back walk flags
1254 res = fib_entry_src_action_cover_update(fib_entry, source);
1255 bflags = fib_entry_src_get_flags(esrc);
1256 best_source = fib_entry_src_get_source(esrc);
1260 fib_entry_src_action_cover_update(fib_entry, source);
1267 fib_entry_src_action_reactivate(fib_entry,
1268 fib_entry_src_get_source(
1269 fib_entry_get_best_src_i(fib_entry)));
1270 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1274 fib_entry_src_action_uninstall(fib_entry);
1277 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1280 * time for walkies fido.
1282 fib_node_back_walk_ctx_t bw_ctx = {
1283 .fnbw_reason = res.bw_reason,
1286 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1291 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1292 fib_node_index_t **entry_indicies)
1294 fib_entry_t *fib_entry;
1295 int was_looped, is_looped;
1297 fib_entry = fib_entry_get(entry_index);
1299 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1301 fib_node_index_t *entries = *entry_indicies;
1303 vec_add1(entries, entry_index);
1304 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1305 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1308 *entry_indicies = entries;
1310 if (!!was_looped != !!is_looped)
1313 * re-evaluate all the entry's forwarding
1314 * NOTE: this is an inplace modify
1316 fib_entry_delegate_type_t fdt;
1317 fib_entry_delegate_t *fed;
1319 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1321 fib_entry_src_mk_lb(fib_entry,
1322 fib_entry_get_best_src_i(fib_entry),
1323 fib_entry_delegate_type_to_chain_type(fdt),
1331 * the entry is currently not linked to a path-list. this happens
1332 * when it is this entry that is re-linking path-lists and has thus
1342 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1344 fib_entry_t *fib_entry;
1346 fib_entry = fib_entry_get(entry_index);
1348 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1352 fib_entry_get_best_source (fib_node_index_t entry_index)
1354 fib_entry_t *fib_entry;
1355 fib_entry_src_t *bsrc;
1357 fib_entry = fib_entry_get(entry_index);
1359 bsrc = fib_entry_get_best_src_i(fib_entry);
1360 return (fib_entry_src_get_source(bsrc));
1364 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
1368 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1370 fib_entry_delegate_t *fed;
1371 fib_entry_t *fib_entry;
1373 fib_entry = fib_entry_get(fib_entry_index);
1375 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1380 * no BFD tracking - resolved
1387 * defer to the state of the BFD tracking
1389 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1394 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1395 flow_hash_config_t hash_config)
1397 fib_entry_t *fib_entry;
1399 fib_entry = fib_entry_get(fib_entry_index);
1402 * pass the hash-config on to the load-balance object where it is cached.
1403 * we can ignore LBs in the delegate chains, since they will not be of the
1404 * correct protocol type (i.e. they are not IP)
1405 * There's no way, nor need, to change the hash config for MPLS.
1407 if (dpo_id_is_valid(&fib_entry->fe_lb))
1411 ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1413 lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1416 * atomic update for packets in flight
1418 lb->lb_hash_config = hash_config;
1423 fib_ip4_address_compare (const ip4_address_t * a1,
1424 const ip4_address_t * a2)
1427 * IP addresses are unsiged ints. the return value here needs to be signed
1428 * a simple subtraction won't cut it.
1429 * If the addresses are the same, the sort order is undefiend, so phoey.
1431 return ((clib_net_to_host_u32(a1->data_u32) >
1432 clib_net_to_host_u32(a2->data_u32) ) ?
1437 fib_ip6_address_compare (const ip6_address_t * a1,
1438 const ip6_address_t * a2)
1441 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1443 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1444 clib_net_to_host_u16 (a2->as_u16[i]));
1452 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1453 fib_node_index_t fib_entry_index2)
1455 fib_entry_t *fib_entry1, *fib_entry2;
1458 fib_entry1 = fib_entry_get(fib_entry_index1);
1459 fib_entry2 = fib_entry_get(fib_entry_index2);
1461 switch (fib_entry1->fe_prefix.fp_proto)
1463 case FIB_PROTOCOL_IP4:
1464 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1465 &fib_entry2->fe_prefix.fp_addr.ip4);
1467 case FIB_PROTOCOL_IP6:
1468 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1469 &fib_entry2->fe_prefix.fp_addr.ip6);
1471 case FIB_PROTOCOL_MPLS:
1472 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1476 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1482 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1488 fib_entry_cmp_for_sort (void *i1, void *i2)
1490 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1492 return (fib_entry_cmp(*fib_entry_index1,
1493 *fib_entry_index2));
1497 fib_entry_lock (fib_node_index_t fib_entry_index)
1499 fib_entry_t *fib_entry;
1501 fib_entry = fib_entry_get(fib_entry_index);
1503 fib_node_lock(&fib_entry->fe_node);
1507 fib_entry_unlock (fib_node_index_t fib_entry_index)
1509 fib_entry_t *fib_entry;
1511 fib_entry = fib_entry_get(fib_entry_index);
1513 fib_node_unlock(&fib_entry->fe_node);
1517 fib_entry_module_init (void)
1519 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1523 fib_entry_encode (fib_node_index_t fib_entry_index,
1524 fib_route_path_encode_t **api_rpaths)
1526 fib_entry_t *fib_entry;
1528 fib_entry = fib_entry_get(fib_entry_index);
1529 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1531 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1536 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1539 fib_entry_t *fib_entry;
1541 fib_entry = fib_entry_get(fib_entry_index);
1542 *pfx = fib_entry->fe_prefix;
1546 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1548 fib_entry_t *fib_entry;
1550 fib_entry = fib_entry_get(fib_entry_index);
1552 return (fib_entry->fe_fib_index);
1556 fib_entry_pool_size (void)
1558 return (pool_elts(fib_entry_pool));
1561 static clib_error_t *
1562 show_fib_entry_command (vlib_main_t * vm,
1563 unformat_input_t * input,
1564 vlib_cli_command_t * cmd)
1566 fib_node_index_t fei;
1568 if (unformat (input, "%d", &fei))
1571 * show one in detail
1573 if (!pool_is_free_index(fib_entry_pool, fei))
1575 vlib_cli_output (vm, "%d@%U",
1577 format_fib_entry, fei,
1578 FIB_ENTRY_FORMAT_DETAIL2);
1582 vlib_cli_output (vm, "entry %d invalid", fei);
1590 vlib_cli_output (vm, "FIB Entries:");
1591 pool_foreach_index(fei, fib_entry_pool,
1593 vlib_cli_output (vm, "%d@%U",
1595 format_fib_entry, fei,
1596 FIB_ENTRY_FORMAT_BRIEF);
1603 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1604 .path = "show fib entry",
1605 .function = show_fib_entry_command,
1606 .short_help = "show fib entry",