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);
68 fib_entry_get_dpo_proto (const fib_entry_t * fib_entry)
70 return (fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto));
73 fib_forward_chain_type_t
74 fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
76 switch (fib_entry->fe_prefix.fp_proto)
78 case FIB_PROTOCOL_IP4:
79 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
80 case FIB_PROTOCOL_IP6:
81 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
82 case FIB_PROTOCOL_MPLS:
83 if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
84 return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
86 return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
89 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
93 format_fib_source (u8 * s, va_list * args)
95 fib_source_t source = va_arg (*args, int);
97 s = format (s, "src:%s", fib_source_names[source]);
103 format_fib_entry (u8 * s, va_list * args)
105 fib_forward_chain_type_t fct;
106 fib_entry_attribute_t attr;
107 fib_entry_t *fib_entry;
108 fib_entry_src_t *src;
109 fib_node_index_t fei;
113 fei = va_arg (*args, fib_node_index_t);
114 level = va_arg (*args, int);
115 fib_entry = fib_entry_get(fei);
117 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
119 if (level >= FIB_ENTRY_FORMAT_DETAIL)
121 s = format (s, " fib:%d", fib_entry->fe_fib_index);
122 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
123 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
125 FOR_EACH_SRC_ADDED(fib_entry, src, source,
127 s = format (s, "\n %U", format_fib_source, source);
128 s = fib_entry_src_format(fib_entry, source, s);
129 s = format (s, " refs:%d ", src->fes_ref_count);
130 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
131 s = format(s, "flags:");
132 FOR_EACH_FIB_ATTRIBUTE(attr) {
133 if ((1<<attr) & src->fes_entry_flags) {
134 s = format (s, "%s,", fib_attribute_names[attr]);
138 s = format (s, "\n");
139 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
141 s = fib_path_list_format(src->fes_pl, s);
143 s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
146 s = format (s, "\n forwarding: ");
150 s = format (s, "\n");
153 fct = fib_entry_get_default_chain_type(fib_entry);
155 if (!dpo_id_is_valid(&fib_entry->fe_lb))
157 s = format (s, " UNRESOLVED\n");
162 s = format(s, " %U-chain\n %U",
163 format_fib_forw_chain_type, fct,
169 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
171 fib_entry_delegate_type_t fdt;
172 fib_entry_delegate_t *fed;
174 s = format (s, " Delegates:\n");
175 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
177 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
182 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
184 s = format(s, " Children:");
185 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
192 fib_entry_from_fib_node (fib_node_t *node)
194 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
195 return ((fib_entry_t*)node);
199 fib_entry_last_lock_gone (fib_node_t *node)
201 fib_entry_delegate_type_t fdt;
202 fib_entry_delegate_t *fed;
203 fib_entry_t *fib_entry;
205 fib_entry = fib_entry_from_fib_node(node);
207 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
209 dpo_reset(&fed->fd_dpo);
210 fib_entry_delegate_remove(fib_entry, fdt);
213 FIB_ENTRY_DBG(fib_entry, "last-lock");
215 fib_node_deinit(&fib_entry->fe_node);
217 ASSERT(0 == vec_len(fib_entry->fe_delegates));
218 vec_free(fib_entry->fe_delegates);
219 if (fib_entry_has_multiple_srcs(fib_entry))
221 vec_free(fib_entry->fe_u_src.fe_srcs);
223 pool_put(fib_entry_pool, fib_entry);
226 static const fib_entry_src_t*
227 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
229 const fib_entry_src_t *bsrc;
232 * the enum of sources is deliberately arranged in priority order
234 if (fib_entry_has_multiple_srcs(fib_entry))
236 ASSERT(vec_len(fib_entry->fe_u_src.fe_srcs));
238 bsrc = vec_elt_at_index(fib_entry->fe_u_src.fe_srcs, 0);
242 bsrc = &fib_entry->fe_u_src.fe_src;
249 fib_entry_src_get_source (const fib_entry_src_t *esrc)
253 return (esrc->fes_src);
255 return (FIB_SOURCE_INVALID);
258 static fib_entry_flag_t
259 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
263 return (esrc->fes_entry_flags);
265 return (FIB_ENTRY_FLAG_NONE);
269 fib_entry_get_flags_i (const fib_entry_t *fib_entry)
271 const fib_entry_src_t *esrc;
273 esrc = fib_entry_get_best_src_i(fib_entry);
277 return (esrc->fes_entry_flags);
281 fib_entry_get_flags (fib_node_index_t fib_entry_index)
283 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
287 * fib_entry_back_walk_notify
289 * A back walk has reach this entry.
291 static fib_node_back_walk_rc_t
292 fib_entry_back_walk_notify (fib_node_t *node,
293 fib_node_back_walk_ctx_t *ctx)
295 fib_entry_t *fib_entry;
297 fib_entry = fib_entry_from_fib_node(node);
299 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
300 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
301 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
302 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
303 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
304 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
306 fib_entry_src_action_reactivate(fib_entry,
307 fib_entry_get_best_source(
308 fib_entry_get_index(fib_entry)));
312 * all other walk types can be reclassifed to a re-evaluate to
313 * all recursive dependents.
314 * By reclassifying we ensure that should any of these walk types meet
315 * they can be merged.
317 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
320 * ... and nothing is forced sync from now on.
322 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
325 * propagate the backwalk further if we haven't already reached the
328 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
329 fib_entry_get_index(fib_entry),
332 return (FIB_NODE_BACK_WALK_CONTINUE);
336 fib_entry_show_memory (void)
338 u32 n_srcs = 0, n_exts = 0;
339 fib_entry_src_t *esrc;
342 fib_show_memory_usage("Entry",
343 pool_elts(fib_entry_pool),
344 pool_len(fib_entry_pool),
345 sizeof(fib_entry_t));
347 pool_foreach(entry, fib_entry_pool,
349 if (fib_entry_has_multiple_srcs(entry))
351 n_srcs += vec_len(entry->fe_u_src.fe_srcs);
352 vec_foreach(esrc, entry->fe_u_src.fe_srcs)
354 n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
359 n_exts += fib_path_ext_list_length(&entry->fe_u_src.fe_src.fes_path_exts);
363 fib_show_memory_usage("Entry Source",
364 n_srcs, n_srcs, sizeof(fib_entry_src_t));
365 fib_show_memory_usage("Entry Path-Extensions",
367 sizeof(fib_path_ext_t));
371 * The FIB path-list's graph node virtual function table
373 static const fib_node_vft_t fib_entry_vft = {
374 .fnv_get = fib_entry_get_node,
375 .fnv_last_lock = fib_entry_last_lock_gone,
376 .fnv_back_walk = fib_entry_back_walk_notify,
377 .fnv_mem_show = fib_entry_show_memory,
381 * @brief Contribute the set of Adjacencies that this entry forwards with
382 * to build the uRPF list of its children
385 fib_entry_contribute_urpf (fib_node_index_t entry_index,
388 fib_entry_t *fib_entry;
390 fib_entry = fib_entry_get(entry_index);
392 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
396 * If the client is request a chain for multicast forwarding then swap
397 * the chain type to one that can provide such transport.
399 static fib_forward_chain_type_t
400 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
404 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
405 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
407 * we can only transport IP multicast packets if there is an
410 fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
412 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
413 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
414 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
415 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
416 case FIB_FORW_CHAIN_TYPE_ETHERNET:
417 case FIB_FORW_CHAIN_TYPE_NSH:
418 case FIB_FORW_CHAIN_TYPE_BIER:
426 * fib_entry_contribute_forwarding
428 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
431 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
432 fib_forward_chain_type_t fct,
435 fib_entry_delegate_t *fed;
436 fib_entry_t *fib_entry;
438 fib_entry = fib_entry_get(fib_entry_index);
441 * mfib children ask for mcast chains. fix these to the appropriate ucast types.
443 fct = fib_entry_chain_type_mcast_to_ucast(fct);
445 if (fct == fib_entry_get_default_chain_type(fib_entry))
447 dpo_copy(dpo, &fib_entry->fe_lb);
451 fed = fib_entry_delegate_get(fib_entry,
452 fib_entry_chain_type_to_delegate_type(fct));
456 fed = fib_entry_delegate_find_or_add(
458 fib_entry_chain_type_to_delegate_type(fct));
460 * on-demand create eos/non-eos.
461 * There is no on-demand delete because:
462 * - memory versus complexity & reliability:
463 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
464 * then up on the right trigger is more code. i favour the latter.
466 fib_entry_src_mk_lb(fib_entry,
467 fib_entry_get_best_src_i(fib_entry),
472 dpo_copy(dpo, &fed->fd_dpo);
475 * don't allow the special index indicating replicate.vs.load-balance
476 * to escape to the clients
478 dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
482 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
484 fib_forward_chain_type_t fct;
485 fib_entry_t *fib_entry;
487 fib_entry = fib_entry_get(fib_entry_index);
488 fct = fib_entry_get_default_chain_type(fib_entry);
490 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
491 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
493 return (&fib_entry->fe_lb);
497 fib_entry_get_adj (fib_node_index_t fib_entry_index)
501 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
503 if (dpo_id_is_valid(dpo))
505 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
509 return (dpo->dpoi_index);
512 return (ADJ_INDEX_INVALID);
516 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
518 fib_entry_t *fib_entry;
520 fib_entry = fib_entry_get(fib_entry_index);
522 return (fib_entry->fe_parent);
526 fib_entry_child_add (fib_node_index_t fib_entry_index,
527 fib_node_type_t child_type,
528 fib_node_index_t child_index)
530 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
537 fib_entry_child_remove (fib_node_index_t fib_entry_index,
540 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
544 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
548 * if there are no children left then there is no reason to keep
549 * the non-default forwarding chains. those chains are built only
550 * because the children want them.
552 fib_entry_delegate_type_t fdt;
553 fib_entry_delegate_t *fed;
554 fib_entry_t *fib_entry;
556 fib_entry = fib_entry_get(fib_entry_index);
558 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
560 dpo_reset(&fed->fd_dpo);
561 fib_entry_delegate_remove(fib_entry, fdt);
567 fib_entry_alloc (u32 fib_index,
568 const fib_prefix_t *prefix,
569 fib_node_index_t *fib_entry_index)
571 fib_entry_t *fib_entry;
574 pool_get(fib_entry_pool, fib_entry);
575 memset(fib_entry, 0, sizeof(*fib_entry));
577 fib_node_init(&fib_entry->fe_node,
578 FIB_NODE_TYPE_ENTRY);
580 fib_entry->fe_fib_index = fib_index;
583 * the one time we need to update the const prefix is when
584 * the entry is first created
586 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
589 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
592 if (MPLS_NON_EOS == fep->fp_eos)
594 fep->fp_payload_proto = DPO_PROTO_MPLS;
596 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
599 dpo_reset(&fib_entry->fe_lb);
601 *fib_entry_index = fib_entry_get_index(fib_entry);
603 FIB_ENTRY_DBG(fib_entry, "alloc");
609 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,
686 fib_entry_src_action_installed(fib_entry, source);
690 fib_entry_create (u32 fib_index,
691 const fib_prefix_t *prefix,
693 fib_entry_flag_t flags,
694 const fib_route_path_t *paths)
696 fib_node_index_t fib_entry_index;
697 fib_entry_t *fib_entry;
699 ASSERT(0 < vec_len(paths));
701 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
704 * since this is a new entry create, we don't need to check for winning
705 * sources - there is only one.
707 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
710 fib_entry_get_proto(fib_entry))));
711 fib_entry_src_action_path_swap(fib_entry,
716 * handle possible realloc's by refetching the pointer
718 fib_entry = fib_entry_get(fib_entry_index);
719 fib_entry_src_action_activate(fib_entry, source);
721 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
723 return (fib_entry_index);
727 fib_entry_create_special (u32 fib_index,
728 const fib_prefix_t *prefix,
730 fib_entry_flag_t flags,
733 fib_node_index_t fib_entry_index;
734 fib_entry_t *fib_entry;
737 * create and initiliase the new enty
739 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
742 * create the path-list
744 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
745 fib_entry_src_action_activate(fib_entry, source);
747 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
749 return (fib_entry_index);
753 fib_entry_post_update_actions (fib_entry_t *fib_entry,
755 fib_entry_flag_t old_flags)
758 * backwalk to children to inform then of the change to forwarding.
760 fib_node_back_walk_ctx_t bw_ctx = {
761 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
764 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
767 * then inform any covered prefixes
769 fib_entry_cover_update_notify(fib_entry);
771 fib_entry_post_install_actions(fib_entry, source, old_flags);
775 fib_entry_source_change (fib_entry_t *fib_entry,
776 fib_source_t best_source,
777 fib_source_t new_source,
778 fib_entry_flag_t old_flags)
781 * if the path list for the source passed is invalid,
782 * then we need to create a new one. else we are updating
785 if (new_source < best_source)
788 * we have a new winning source.
790 fib_entry_src_action_deactivate(fib_entry, best_source);
791 fib_entry_src_action_activate(fib_entry, new_source);
793 else if (new_source > best_source)
796 * the new source loses. nothing to do here.
797 * the data from the source is saved in the path-list created
804 * the new source is one this entry already has.
805 * But the path-list was updated, which will contribute new forwarding,
808 fib_entry_src_action_deactivate(fib_entry, new_source);
809 fib_entry_src_action_activate(fib_entry, new_source);
812 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
816 fib_entry_special_add (fib_node_index_t fib_entry_index,
818 fib_entry_flag_t flags,
821 const fib_entry_src_t *bsrc;
822 fib_source_t best_source;
823 fib_entry_flag_t bflags;
824 fib_entry_t *fib_entry;
826 fib_entry = fib_entry_get(fib_entry_index);
828 bsrc = fib_entry_get_best_src_i(fib_entry);
829 best_source = fib_entry_src_get_source(bsrc);
830 bflags = fib_entry_src_get_flags(bsrc);
832 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
833 fib_entry_source_change(fib_entry, best_source, source, bflags);
837 fib_entry_special_update (fib_node_index_t fib_entry_index,
839 fib_entry_flag_t flags,
842 const fib_entry_src_t *bsrc;
843 fib_source_t best_source;
844 fib_entry_flag_t bflags;
845 fib_entry_t *fib_entry;
847 fib_entry = fib_entry_get(fib_entry_index);
849 bsrc = fib_entry_get_best_src_i(fib_entry);
850 best_source = fib_entry_src_get_source(bsrc);
851 bflags = fib_entry_src_get_flags(bsrc);
853 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
854 fib_entry_source_change(fib_entry, best_source, source, bflags);
859 fib_entry_path_add (fib_node_index_t fib_entry_index,
861 fib_entry_flag_t flags,
862 const fib_route_path_t *rpath)
864 const fib_entry_src_t *bsrc;
865 fib_source_t best_source;
866 fib_entry_flag_t bflags;
867 fib_entry_t *fib_entry;
869 ASSERT(1 == vec_len(rpath));
871 fib_entry = fib_entry_get(fib_entry_index);
872 ASSERT(NULL != fib_entry);
874 bsrc = fib_entry_get_best_src_i(fib_entry);
875 best_source = fib_entry_src_get_source(bsrc);
876 bflags = fib_entry_src_get_flags(bsrc);
878 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
881 * if the path list for the source passed is invalid,
882 * then we need to create a new one. else we are updating
885 if (source < best_source)
888 * we have a new winning source.
890 fib_entry_src_action_deactivate(fib_entry, best_source);
891 fib_entry_src_action_activate(fib_entry, source);
893 else if (source > best_source)
896 * the new source loses. nothing to do here.
897 * the data from the source is saved in the path-list created
904 * the new source is one this entry already has.
905 * But the path-list was updated, which will contribute new forwarding,
908 fib_entry_src_action_deactivate(fib_entry, source);
909 fib_entry_src_action_activate(fib_entry, source);
912 fib_entry_post_update_actions(fib_entry, source, bflags);
916 * fib_entry_path_remove
918 * remove a path from the entry.
919 * return the fib_entry's index if it is still present, INVALID otherwise.
922 fib_entry_path_remove (fib_node_index_t fib_entry_index,
924 const fib_route_path_t *rpath)
926 const fib_entry_src_t *bsrc;
927 fib_entry_src_flag_t sflag;
928 fib_source_t best_source;
929 fib_entry_flag_t bflags;
930 fib_entry_t *fib_entry;
932 ASSERT(1 == vec_len(rpath));
934 fib_entry = fib_entry_get(fib_entry_index);
935 ASSERT(NULL != fib_entry);
937 bsrc = fib_entry_get_best_src_i(fib_entry);
938 best_source = fib_entry_src_get_source(bsrc);
939 bflags = fib_entry_src_get_flags(bsrc);
941 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
944 * if the path list for the source passed is invalid,
945 * then we need to create a new one. else we are updating
948 if (source < best_source )
951 * Que! removing a path from a source that is better than the
952 * one this entry is using.
956 else if (source > best_source )
959 * the source is not the best. nothing to do.
961 return (FIB_ENTRY_SRC_FLAG_ADDED);
966 * removing a path from the path-list we were using.
968 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
971 * the last path from the source was removed.
972 * fallback to lower source
974 bsrc = fib_entry_get_best_src_i(fib_entry);
975 best_source = fib_entry_src_get_source(bsrc);
977 if (FIB_SOURCE_INVALID == best_source) {
979 * no more sources left. this entry is toast.
981 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
984 fib_entry_src_action_uninstall(fib_entry);
986 return (FIB_ENTRY_SRC_FLAG_NONE);
990 fib_entry_src_action_activate(fib_entry, best_source);
991 source = best_source;
997 * re-install the new forwarding information
999 fib_entry_src_action_deactivate(fib_entry, source);
1000 fib_entry_src_action_activate(fib_entry, source);
1004 fib_entry_post_update_actions(fib_entry, source, bflags);
1007 * still have sources
1009 return (FIB_ENTRY_SRC_FLAG_ADDED);
1013 * fib_entry_special_remove
1015 * remove a special source from the entry.
1016 * return the fib_entry's index if it is still present, INVALID otherwise.
1018 fib_entry_src_flag_t
1019 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1020 fib_source_t source)
1022 const fib_entry_src_t *bsrc;
1023 fib_entry_src_flag_t sflag;
1024 fib_source_t best_source;
1025 fib_entry_flag_t bflags;
1026 fib_entry_t *fib_entry;
1028 fib_entry = fib_entry_get(fib_entry_index);
1029 ASSERT(NULL != fib_entry);
1031 bsrc = fib_entry_get_best_src_i(fib_entry);
1032 best_source = fib_entry_src_get_source(bsrc);
1033 bflags = fib_entry_src_get_flags(bsrc);
1035 sflag = fib_entry_src_action_remove(fib_entry, source);
1038 * if the path list for the source passed is invalid,
1039 * then we need to create a new one. else we are updating
1042 if (source < best_source )
1045 * Que! removing a path from a source that is better than the
1046 * one this entry is using. This can only mean it is a source
1047 * this prefix does not have.
1049 return (FIB_ENTRY_SRC_FLAG_ADDED);
1051 else if (source > best_source ) {
1053 * the source is not the best. nothing to do.
1055 return (FIB_ENTRY_SRC_FLAG_ADDED);
1059 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1062 * the source was removed. use the next best.
1064 bsrc = fib_entry_get_best_src_i(fib_entry);
1065 best_source = fib_entry_src_get_source(bsrc);
1067 if (FIB_SOURCE_INVALID == best_source) {
1069 * no more sources left. this entry is toast.
1071 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
1074 fib_entry_src_action_uninstall(fib_entry);
1076 return (FIB_ENTRY_SRC_FLAG_NONE);
1080 fib_entry_src_action_activate(fib_entry, best_source);
1081 source = best_source;
1087 * re-install the new forwarding information
1089 fib_entry_src_action_reactivate(fib_entry, source);
1093 fib_entry_post_update_actions(fib_entry, source, bflags);
1096 * still have sources
1098 return (FIB_ENTRY_SRC_FLAG_ADDED);
1104 * The source is withdrawing all the paths it provided
1106 fib_entry_src_flag_t
1107 fib_entry_delete (fib_node_index_t fib_entry_index,
1108 fib_source_t source)
1110 return (fib_entry_special_remove(fib_entry_index, source));
1116 * The source has provided a new set of paths that will replace the old.
1119 fib_entry_update (fib_node_index_t fib_entry_index,
1120 fib_source_t source,
1121 fib_entry_flag_t flags,
1122 const fib_route_path_t *paths)
1124 const fib_entry_src_t *bsrc;
1125 fib_source_t best_source;
1126 fib_entry_flag_t bflags;
1127 fib_entry_t *fib_entry;
1129 fib_entry = fib_entry_get(fib_entry_index);
1130 ASSERT(NULL != fib_entry);
1132 bsrc = fib_entry_get_best_src_i(fib_entry);
1133 best_source = fib_entry_src_get_source(bsrc);
1134 bflags = fib_entry_src_get_flags(bsrc);
1136 fib_entry_src_action_path_swap(fib_entry,
1141 * handle possible realloc's by refetching the pointer
1143 fib_entry = fib_entry_get(fib_entry_index);
1146 * if the path list for the source passed is invalid,
1147 * then we need to create a new one. else we are updating
1150 if (source < best_source)
1153 * we have a new winning source.
1155 fib_entry_src_action_deactivate(fib_entry, best_source);
1156 fib_entry_src_action_activate(fib_entry, source);
1158 else if (source > best_source) {
1160 * the new source loses. nothing to do here.
1161 * the data from the source is saved in the path-list created
1168 * the new source is one this entry already has.
1169 * But the path-list was updated, which will contribute new forwarding,
1172 fib_entry_src_action_deactivate(fib_entry, source);
1173 fib_entry_src_action_activate(fib_entry, source);
1176 fib_entry_post_update_actions(fib_entry, source, bflags);
1181 * fib_entry_cover_changed
1183 * this entry is tracking its cover and that cover has changed.
1186 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1188 fib_entry_src_cover_res_t res = {
1190 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1192 fib_source_t source, best_source;
1193 fib_entry_flag_t bflags;
1194 fib_entry_t *fib_entry;
1195 fib_entry_src_t *esrc;
1198 bflags = FIB_ENTRY_FLAG_NONE;
1199 best_source = FIB_SOURCE_FIRST;
1200 fib_entry = fib_entry_get(fib_entry_index);
1202 fib_attached_export_cover_change(fib_entry);
1205 * propagate the notificuation to each of the added sources
1208 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1213 * only the best source gets to set the back walk flags
1215 res = fib_entry_src_action_cover_change(fib_entry, source);
1216 bflags = fib_entry_src_get_flags(esrc);
1217 best_source = fib_entry_src_get_source(esrc);
1221 fib_entry_src_action_cover_change(fib_entry, source);
1228 fib_entry_src_action_reactivate(fib_entry,
1229 fib_entry_src_get_source(
1230 fib_entry_get_best_src_i(fib_entry)));
1231 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1235 fib_entry_src_action_uninstall(fib_entry);
1238 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1241 * time for walkies fido.
1243 fib_node_back_walk_ctx_t bw_ctx = {
1244 .fnbw_reason = res.bw_reason,
1247 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1252 * fib_entry_cover_updated
1254 * this entry is tracking its cover and that cover has been updated
1255 * (i.e. its forwarding information has changed).
1258 fib_entry_cover_updated (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 fib_source_t source, best_source;
1265 fib_entry_flag_t bflags;
1266 fib_entry_t *fib_entry;
1267 fib_entry_src_t *esrc;
1270 bflags = FIB_ENTRY_FLAG_NONE;
1271 best_source = FIB_SOURCE_FIRST;
1272 fib_entry = fib_entry_get(fib_entry_index);
1274 fib_attached_export_cover_update(fib_entry);
1277 * propagate the notificuation to each of the added sources
1280 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1285 * only the best source gets to set the back walk flags
1287 res = fib_entry_src_action_cover_update(fib_entry, source);
1288 bflags = fib_entry_src_get_flags(esrc);
1289 best_source = fib_entry_src_get_source(esrc);
1293 fib_entry_src_action_cover_update(fib_entry, source);
1300 fib_entry_src_action_reactivate(fib_entry,
1301 fib_entry_src_get_source(
1302 fib_entry_get_best_src_i(fib_entry)));
1303 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1307 fib_entry_src_action_uninstall(fib_entry);
1310 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1313 * time for walkies fido.
1315 fib_node_back_walk_ctx_t bw_ctx = {
1316 .fnbw_reason = res.bw_reason,
1319 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1324 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1325 fib_node_index_t **entry_indicies)
1327 fib_entry_t *fib_entry;
1328 int was_looped, is_looped;
1330 fib_entry = fib_entry_get(entry_index);
1332 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1334 fib_node_index_t *entries = *entry_indicies;
1336 vec_add1(entries, entry_index);
1337 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1338 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1341 *entry_indicies = entries;
1343 if (!!was_looped != !!is_looped)
1346 * re-evaluate all the entry's forwarding
1347 * NOTE: this is an inplace modify
1349 fib_entry_delegate_type_t fdt;
1350 fib_entry_delegate_t *fed;
1352 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1354 fib_entry_src_mk_lb(fib_entry,
1355 fib_entry_get_best_src_i(fib_entry),
1356 fib_entry_delegate_type_to_chain_type(fdt),
1364 * the entry is currently not linked to a path-list. this happens
1365 * when it is this entry that is re-linking path-lists and has thus
1375 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1377 fib_entry_t *fib_entry;
1379 fib_entry = fib_entry_get(entry_index);
1381 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1385 fib_entry_get_best_source (fib_node_index_t entry_index)
1387 const fib_entry_src_t *bsrc;
1388 fib_entry_t *fib_entry;
1390 fib_entry = fib_entry_get(entry_index);
1392 bsrc = fib_entry_get_best_src_i(fib_entry);
1393 return (fib_entry_src_get_source(bsrc));
1397 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
1401 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1403 fib_entry_delegate_t *fed;
1404 fib_entry_t *fib_entry;
1406 fib_entry = fib_entry_get(fib_entry_index);
1408 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1413 * no BFD tracking - consider it resolved.
1420 * defer to the state of the BFD tracking
1422 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1427 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1428 flow_hash_config_t hash_config)
1430 fib_entry_t *fib_entry;
1432 fib_entry = fib_entry_get(fib_entry_index);
1435 * pass the hash-config on to the load-balance object where it is cached.
1436 * we can ignore LBs in the delegate chains, since they will not be of the
1437 * correct protocol type (i.e. they are not IP)
1438 * There's no way, nor need, to change the hash config for MPLS.
1440 if (dpo_id_is_valid(&fib_entry->fe_lb))
1444 ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1446 lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1449 * atomic update for packets in flight
1451 lb->lb_hash_config = hash_config;
1456 fib_ip4_address_compare (const ip4_address_t * a1,
1457 const ip4_address_t * a2)
1460 * IP addresses are unsiged ints. the return value here needs to be signed
1461 * a simple subtraction won't cut it.
1462 * If the addresses are the same, the sort order is undefiend, so phoey.
1464 return ((clib_net_to_host_u32(a1->data_u32) >
1465 clib_net_to_host_u32(a2->data_u32) ) ?
1470 fib_ip6_address_compare (const ip6_address_t * a1,
1471 const ip6_address_t * a2)
1474 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1476 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1477 clib_net_to_host_u16 (a2->as_u16[i]));
1485 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1486 fib_node_index_t fib_entry_index2)
1488 fib_entry_t *fib_entry1, *fib_entry2;
1491 fib_entry1 = fib_entry_get(fib_entry_index1);
1492 fib_entry2 = fib_entry_get(fib_entry_index2);
1494 switch (fib_entry1->fe_prefix.fp_proto)
1496 case FIB_PROTOCOL_IP4:
1497 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1498 &fib_entry2->fe_prefix.fp_addr.ip4);
1500 case FIB_PROTOCOL_IP6:
1501 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1502 &fib_entry2->fe_prefix.fp_addr.ip6);
1504 case FIB_PROTOCOL_MPLS:
1505 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1509 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1515 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1521 fib_entry_cmp_for_sort (void *i1, void *i2)
1523 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1525 return (fib_entry_cmp(*fib_entry_index1,
1526 *fib_entry_index2));
1530 fib_entry_lock (fib_node_index_t fib_entry_index)
1532 fib_entry_t *fib_entry;
1534 fib_entry = fib_entry_get(fib_entry_index);
1536 fib_node_lock(&fib_entry->fe_node);
1540 fib_entry_unlock (fib_node_index_t fib_entry_index)
1542 fib_entry_t *fib_entry;
1544 fib_entry = fib_entry_get(fib_entry_index);
1546 fib_node_unlock(&fib_entry->fe_node);
1550 fib_entry_module_init (void)
1552 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1556 fib_entry_encode (fib_node_index_t fib_entry_index,
1557 fib_route_path_encode_t **api_rpaths)
1559 fib_entry_t *fib_entry;
1561 fib_entry = fib_entry_get(fib_entry_index);
1562 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1564 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1569 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1572 fib_entry_t *fib_entry;
1574 fib_entry = fib_entry_get(fib_entry_index);
1575 *pfx = fib_entry->fe_prefix;
1579 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1581 fib_entry_t *fib_entry;
1583 fib_entry = fib_entry_get(fib_entry_index);
1585 return (fib_entry->fe_fib_index);
1589 fib_entry_pool_size (void)
1591 return (pool_elts(fib_entry_pool));
1594 static clib_error_t *
1595 show_fib_entry_command (vlib_main_t * vm,
1596 unformat_input_t * input,
1597 vlib_cli_command_t * cmd)
1599 fib_node_index_t fei;
1601 if (unformat (input, "%d", &fei))
1604 * show one in detail
1606 if (!pool_is_free_index(fib_entry_pool, fei))
1608 vlib_cli_output (vm, "%d@%U",
1610 format_fib_entry, fei,
1611 FIB_ENTRY_FORMAT_DETAIL2);
1615 vlib_cli_output (vm, "entry %d invalid", fei);
1623 vlib_cli_output (vm, "FIB Entries:");
1624 pool_foreach_index(fei, fib_entry_pool,
1626 vlib_cli_output (vm, "%d@%U",
1628 format_fib_entry, fei,
1629 FIB_ENTRY_FORMAT_BRIEF);
1636 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1637 .path = "show fib entry",
1638 .function = show_fib_entry_command,
1639 .short_help = "show fib entry",