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_entry (u8 * s, va_list * args)
95 fib_forward_chain_type_t fct;
96 fib_entry_attribute_t attr;
97 fib_entry_t *fib_entry;
103 fei = va_arg (*args, fib_node_index_t);
104 level = va_arg (*args, int);
105 fib_entry = fib_entry_get(fei);
107 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
109 if (level >= FIB_ENTRY_FORMAT_DETAIL)
111 s = format (s, " fib:%d", fib_entry->fe_fib_index);
112 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
113 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
115 FOR_EACH_SRC_ADDED(fib_entry, src, source,
117 s = format (s, "\n src:%s ",
118 fib_source_names[source]);
119 s = fib_entry_src_format(fib_entry, source, s);
120 s = format (s, " refs:%d ", src->fes_ref_count);
121 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
122 s = format(s, "flags:");
123 FOR_EACH_FIB_ATTRIBUTE(attr) {
124 if ((1<<attr) & src->fes_entry_flags) {
125 s = format (s, "%s,", fib_attribute_names[attr]);
129 s = format (s, "\n");
130 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
132 s = fib_path_list_format(src->fes_pl, s);
134 s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
137 s = format (s, "\n forwarding: ");
141 s = format (s, "\n");
144 fct = fib_entry_get_default_chain_type(fib_entry);
146 if (!dpo_id_is_valid(&fib_entry->fe_lb))
148 s = format (s, " UNRESOLVED\n");
153 s = format(s, " %U-chain\n %U",
154 format_fib_forw_chain_type, fct,
160 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
162 fib_entry_delegate_type_t fdt;
163 fib_entry_delegate_t *fed;
165 s = format (s, " Delegates:\n");
166 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
168 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
173 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
175 s = format(s, " Children:");
176 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
183 fib_entry_from_fib_node (fib_node_t *node)
186 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
188 return ((fib_entry_t*)node);
192 fib_entry_last_lock_gone (fib_node_t *node)
194 fib_entry_delegate_type_t fdt;
195 fib_entry_delegate_t *fed;
196 fib_entry_t *fib_entry;
198 fib_entry = fib_entry_from_fib_node(node);
200 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
202 dpo_reset(&fed->fd_dpo);
203 fib_entry_delegate_remove(fib_entry, fdt);
206 FIB_ENTRY_DBG(fib_entry, "last-lock");
208 fib_node_deinit(&fib_entry->fe_node);
209 // FIXME -RR Backwalk
211 ASSERT(0 == vec_len(fib_entry->fe_delegates));
212 vec_free(fib_entry->fe_delegates);
213 vec_free(fib_entry->fe_srcs);
214 pool_put(fib_entry_pool, fib_entry);
217 static fib_entry_src_t*
218 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
220 fib_entry_src_t *bsrc;
223 * the enum of sources is deliberately arranged in priority order
225 if (0 == vec_len(fib_entry->fe_srcs))
231 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
238 fib_entry_src_get_source (const fib_entry_src_t *esrc)
242 return (esrc->fes_src);
244 return (FIB_SOURCE_MAX);
247 static fib_entry_flag_t
248 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
252 return (esrc->fes_entry_flags);
254 return (FIB_ENTRY_FLAG_NONE);
258 fib_entry_get_flags (fib_node_index_t fib_entry_index)
260 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
264 * fib_entry_back_walk_notify
266 * A back walk has reach this entry.
268 static fib_node_back_walk_rc_t
269 fib_entry_back_walk_notify (fib_node_t *node,
270 fib_node_back_walk_ctx_t *ctx)
272 fib_entry_t *fib_entry;
274 fib_entry = fib_entry_from_fib_node(node);
276 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
277 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
278 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
279 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
280 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
281 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
283 fib_entry_src_action_reactivate(fib_entry,
284 fib_entry_get_best_source(
285 fib_entry_get_index(fib_entry)));
289 * all other walk types can be reclassifed to a re-evaluate to
290 * all recursive dependents.
291 * By reclassifying we ensure that should any of these walk types meet
292 * they can be merged.
294 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
297 * ... and nothing is forced sync from now on.
299 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
302 * propagate the backwalk further if we haven't already reached the
305 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
306 fib_entry_get_index(fib_entry),
309 return (FIB_NODE_BACK_WALK_CONTINUE);
313 fib_entry_show_memory (void)
315 u32 n_srcs = 0, n_exts = 0;
316 fib_entry_src_t *esrc;
319 fib_show_memory_usage("Entry",
320 pool_elts(fib_entry_pool),
321 pool_len(fib_entry_pool),
322 sizeof(fib_entry_t));
324 pool_foreach(entry, fib_entry_pool,
326 n_srcs += vec_len(entry->fe_srcs);
327 vec_foreach(esrc, entry->fe_srcs)
329 n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
333 fib_show_memory_usage("Entry Source",
334 n_srcs, n_srcs, sizeof(fib_entry_src_t));
335 fib_show_memory_usage("Entry Path-Extensions",
337 sizeof(fib_path_ext_t));
341 * The FIB path-list's graph node virtual function table
343 static const fib_node_vft_t fib_entry_vft = {
344 .fnv_get = fib_entry_get_node,
345 .fnv_last_lock = fib_entry_last_lock_gone,
346 .fnv_back_walk = fib_entry_back_walk_notify,
347 .fnv_mem_show = fib_entry_show_memory,
351 * @brief Contribute the set of Adjacencies that this entry forwards with
352 * to build the uRPF list of its children
355 fib_entry_contribute_urpf (fib_node_index_t entry_index,
358 fib_entry_t *fib_entry;
360 fib_entry = fib_entry_get(entry_index);
362 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
366 * If the client is request a chain for multicast forwarding then swap
367 * the chain type to one that can provide such transport.
369 static fib_forward_chain_type_t
370 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
374 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
375 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
377 * we can only transport IP multicast packets if there is an
380 fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
382 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
383 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
384 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
385 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
386 case FIB_FORW_CHAIN_TYPE_ETHERNET:
387 case FIB_FORW_CHAIN_TYPE_NSH:
395 * fib_entry_contribute_forwarding
397 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
400 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
401 fib_forward_chain_type_t fct,
404 fib_entry_delegate_t *fed;
405 fib_entry_t *fib_entry;
407 fib_entry = fib_entry_get(fib_entry_index);
410 * mfib children ask for mcast chains. fix these to the appropriate ucast types.
412 fct = fib_entry_chain_type_mcast_to_ucast(fct);
414 if (fct == fib_entry_get_default_chain_type(fib_entry))
416 dpo_copy(dpo, &fib_entry->fe_lb);
420 fed = fib_entry_delegate_get(fib_entry,
421 fib_entry_chain_type_to_delegate_type(fct));
425 fed = fib_entry_delegate_find_or_add(
427 fib_entry_chain_type_to_delegate_type(fct));
429 * on-demand create eos/non-eos.
430 * There is no on-demand delete because:
431 * - memory versus complexity & reliability:
432 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
433 * then up on the right trigger is more code. i favour the latter.
435 fib_entry_src_mk_lb(fib_entry,
436 fib_entry_get_best_src_i(fib_entry),
441 dpo_copy(dpo, &fed->fd_dpo);
444 * don't allow the special index indicating replicate.vs.load-balance
445 * to escape to the clients
447 dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
451 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
453 fib_forward_chain_type_t fct;
454 fib_entry_t *fib_entry;
456 fib_entry = fib_entry_get(fib_entry_index);
457 fct = fib_entry_get_default_chain_type(fib_entry);
459 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
460 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
462 return (&fib_entry->fe_lb);
466 fib_entry_get_adj (fib_node_index_t fib_entry_index)
470 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
472 if (dpo_id_is_valid(dpo))
474 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
478 return (dpo->dpoi_index);
481 return (ADJ_INDEX_INVALID);
485 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
487 fib_entry_t *fib_entry;
489 fib_entry = fib_entry_get(fib_entry_index);
491 return (fib_entry->fe_parent);
495 fib_entry_child_add (fib_node_index_t fib_entry_index,
496 fib_node_type_t child_type,
497 fib_node_index_t child_index)
499 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
506 fib_entry_child_remove (fib_node_index_t fib_entry_index,
509 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
513 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
517 * if there are no children left then there is no reason to keep
518 * the non-default forwarding chains. those chains are built only
519 * because the children want them.
521 fib_entry_delegate_type_t fdt;
522 fib_entry_delegate_t *fed;
523 fib_entry_t *fib_entry;
525 fib_entry = fib_entry_get(fib_entry_index);
527 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
529 dpo_reset(&fed->fd_dpo);
530 fib_entry_delegate_remove(fib_entry, fdt);
536 fib_entry_alloc (u32 fib_index,
537 const fib_prefix_t *prefix,
538 fib_node_index_t *fib_entry_index)
540 fib_entry_t *fib_entry;
543 pool_get(fib_entry_pool, fib_entry);
544 memset(fib_entry, 0, sizeof(*fib_entry));
546 fib_node_init(&fib_entry->fe_node,
547 FIB_NODE_TYPE_ENTRY);
549 fib_entry->fe_fib_index = fib_index;
552 * the one time we need to update the const prefix is when
553 * the entry is first created
555 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
558 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
561 if (MPLS_NON_EOS == fep->fp_eos)
563 fep->fp_payload_proto = DPO_PROTO_MPLS;
565 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
568 dpo_reset(&fib_entry->fe_lb);
570 *fib_entry_index = fib_entry_get_index(fib_entry);
572 FIB_ENTRY_DBG(fib_entry, "alloc");
578 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
580 fib_entry_flag_t old_flags)
582 fib_node_index_t fei;
585 * save the index so we can recover from pool reallocs
587 fei = fib_entry_get_index(fib_entry);
590 * handle changes to attached export for import entries
592 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
593 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
595 if (!was_import && is_import)
598 * transition from not exported to exported
602 * there is an assumption here that the entry resolves via only
603 * one interface and that it is the cross VRF interface.
605 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
607 fib_attached_export_import(fib_entry,
608 fib_table_get_index_for_sw_if_index(
609 fib_entry_get_proto(fib_entry),
612 else if (was_import && !is_import)
615 * transition from exported to not exported
617 fib_attached_export_purge(fib_entry);
621 * no change. nothing to do.
625 * reload the entry address post possible pool realloc
627 fib_entry = fib_entry_get(fei);
630 * handle changes to attached export for export entries
632 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
633 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
635 if (!was_attached && is_attached)
638 * transition to attached. time to export
648 fib_entry_post_install_actions (fib_entry_t *fib_entry,
650 fib_entry_flag_t old_flags)
652 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
655 fib_entry_src_action_installed(fib_entry, source);
659 fib_entry_create (u32 fib_index,
660 const fib_prefix_t *prefix,
662 fib_entry_flag_t flags,
663 const fib_route_path_t *paths)
665 fib_node_index_t fib_entry_index;
666 fib_entry_t *fib_entry;
668 ASSERT(0 < vec_len(paths));
670 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
673 * since this is a new entry create, we don't need to check for winning
674 * sources - there is only one.
676 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
679 fib_entry_get_proto(fib_entry))));
680 fib_entry_src_action_path_swap(fib_entry,
685 * handle possible realloc's by refetching the pointer
687 fib_entry = fib_entry_get(fib_entry_index);
688 fib_entry_src_action_activate(fib_entry, source);
690 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
692 return (fib_entry_index);
696 fib_entry_create_special (u32 fib_index,
697 const fib_prefix_t *prefix,
699 fib_entry_flag_t flags,
702 fib_node_index_t fib_entry_index;
703 fib_entry_t *fib_entry;
706 * create and initiliase the new enty
708 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
711 * create the path-list
713 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
714 fib_entry_src_action_activate(fib_entry, source);
716 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
718 return (fib_entry_index);
722 fib_entry_post_update_actions (fib_entry_t *fib_entry,
724 fib_entry_flag_t old_flags)
727 * backwalk to children to inform then of the change to forwarding.
729 fib_node_back_walk_ctx_t bw_ctx = {
730 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
733 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
736 * then inform any covered prefixes
738 fib_entry_cover_update_notify(fib_entry);
740 fib_entry_post_install_actions(fib_entry, source, old_flags);
744 fib_entry_source_change (fib_entry_t *fib_entry,
745 fib_source_t best_source,
746 fib_source_t new_source,
747 fib_entry_flag_t old_flags)
750 * if the path list for the source passed is invalid,
751 * then we need to create a new one. else we are updating
754 if (new_source < best_source)
757 * we have a new winning source.
759 fib_entry_src_action_deactivate(fib_entry, best_source);
760 fib_entry_src_action_activate(fib_entry, new_source);
762 else if (new_source > best_source)
765 * the new source loses. nothing to do here.
766 * the data from the source is saved in the path-list created
773 * the new source is one this entry already has.
774 * But the path-list was updated, which will contribute new forwarding,
777 fib_entry_src_action_deactivate(fib_entry, new_source);
778 fib_entry_src_action_activate(fib_entry, new_source);
781 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
785 fib_entry_special_add (fib_node_index_t fib_entry_index,
787 fib_entry_flag_t flags,
790 fib_source_t best_source;
791 fib_entry_flag_t bflags;
792 fib_entry_t *fib_entry;
793 fib_entry_src_t *bsrc;
795 fib_entry = fib_entry_get(fib_entry_index);
797 bsrc = fib_entry_get_best_src_i(fib_entry);
798 best_source = fib_entry_src_get_source(bsrc);
799 bflags = fib_entry_src_get_flags(bsrc);
801 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
802 fib_entry_source_change(fib_entry, best_source, source, bflags);
806 fib_entry_special_update (fib_node_index_t fib_entry_index,
808 fib_entry_flag_t flags,
811 fib_source_t best_source;
812 fib_entry_flag_t bflags;
813 fib_entry_t *fib_entry;
814 fib_entry_src_t *bsrc;
816 fib_entry = fib_entry_get(fib_entry_index);
818 bsrc = fib_entry_get_best_src_i(fib_entry);
819 best_source = fib_entry_src_get_source(bsrc);
820 bflags = fib_entry_src_get_flags(bsrc);
822 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
823 fib_entry_source_change(fib_entry, best_source, source, bflags);
828 fib_entry_path_add (fib_node_index_t fib_entry_index,
830 fib_entry_flag_t flags,
831 const fib_route_path_t *rpath)
833 fib_source_t best_source;
834 fib_entry_flag_t bflags;
835 fib_entry_t *fib_entry;
836 fib_entry_src_t *bsrc;
838 ASSERT(1 == vec_len(rpath));
840 fib_entry = fib_entry_get(fib_entry_index);
841 ASSERT(NULL != fib_entry);
843 bsrc = fib_entry_get_best_src_i(fib_entry);
844 best_source = fib_entry_src_get_source(bsrc);
845 bflags = fib_entry_src_get_flags(bsrc);
847 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
850 * if the path list for the source passed is invalid,
851 * then we need to create a new one. else we are updating
854 if (source < best_source)
857 * we have a new winning source.
859 fib_entry_src_action_deactivate(fib_entry, best_source);
860 fib_entry_src_action_activate(fib_entry, source);
862 else if (source > best_source)
865 * the new source loses. nothing to do here.
866 * the data from the source is saved in the path-list created
873 * the new source is one this entry already has.
874 * But the path-list was updated, which will contribute new forwarding,
877 fib_entry_src_action_deactivate(fib_entry, source);
878 fib_entry_src_action_activate(fib_entry, source);
881 fib_entry_post_update_actions(fib_entry, source, bflags);
885 * fib_entry_path_remove
887 * remove a path from the entry.
888 * return the fib_entry's index if it is still present, INVALID otherwise.
891 fib_entry_path_remove (fib_node_index_t fib_entry_index,
893 const fib_route_path_t *rpath)
895 fib_entry_src_flag_t sflag;
896 fib_source_t best_source;
897 fib_entry_flag_t bflags;
898 fib_entry_t *fib_entry;
899 fib_entry_src_t *bsrc;
901 ASSERT(1 == vec_len(rpath));
903 fib_entry = fib_entry_get(fib_entry_index);
904 ASSERT(NULL != fib_entry);
906 bsrc = fib_entry_get_best_src_i(fib_entry);
907 best_source = fib_entry_src_get_source(bsrc);
908 bflags = fib_entry_src_get_flags(bsrc);
910 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
913 * if the path list for the source passed is invalid,
914 * then we need to create a new one. else we are updating
917 if (source < best_source )
920 * Que! removing a path from a source that is better than the
921 * one this entry is using.
925 else if (source > best_source )
928 * the source is not the best. nothing to do.
930 return (FIB_ENTRY_SRC_FLAG_ADDED);
935 * removing a path from the path-list we were using.
937 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
940 * the last path from the source was removed.
941 * fallback to lower source
943 bsrc = fib_entry_get_best_src_i(fib_entry);
944 best_source = fib_entry_src_get_source(bsrc);
946 if (FIB_SOURCE_MAX == best_source) {
948 * no more sources left. this entry is toast.
950 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
953 fib_entry_src_action_uninstall(fib_entry);
955 return (FIB_ENTRY_SRC_FLAG_NONE);
959 fib_entry_src_action_activate(fib_entry, best_source);
960 source = best_source;
966 * re-install the new forwarding information
968 fib_entry_src_action_deactivate(fib_entry, source);
969 fib_entry_src_action_activate(fib_entry, source);
973 fib_entry_post_update_actions(fib_entry, source, bflags);
978 return (FIB_ENTRY_SRC_FLAG_ADDED);
982 * fib_entry_special_remove
984 * remove a special source from the entry.
985 * return the fib_entry's index if it is still present, INVALID otherwise.
988 fib_entry_special_remove (fib_node_index_t fib_entry_index,
991 fib_entry_src_flag_t sflag;
992 fib_source_t best_source;
993 fib_entry_flag_t bflags;
994 fib_entry_t *fib_entry;
995 fib_entry_src_t *bsrc;
997 fib_entry = fib_entry_get(fib_entry_index);
998 ASSERT(NULL != fib_entry);
1000 bsrc = fib_entry_get_best_src_i(fib_entry);
1001 best_source = fib_entry_src_get_source(bsrc);
1002 bflags = fib_entry_src_get_flags(bsrc);
1004 sflag = fib_entry_src_action_remove(fib_entry, source);
1007 * if the path list for the source passed is invalid,
1008 * then we need to create a new one. else we are updating
1011 if (source < best_source )
1014 * Que! removing a path from a source that is better than the
1015 * one this entry is using. This can only mean it is a source
1016 * this prefix does not have.
1018 return (FIB_ENTRY_SRC_FLAG_ADDED);
1020 else if (source > best_source ) {
1022 * the source is not the best. nothing to do.
1024 return (FIB_ENTRY_SRC_FLAG_ADDED);
1028 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1031 * the source was removed. use the next best.
1033 bsrc = fib_entry_get_best_src_i(fib_entry);
1034 best_source = fib_entry_src_get_source(bsrc);
1036 if (FIB_SOURCE_MAX == best_source) {
1038 * no more sources left. this entry is toast.
1040 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
1043 fib_entry_src_action_uninstall(fib_entry);
1045 return (FIB_ENTRY_SRC_FLAG_NONE);
1049 fib_entry_src_action_activate(fib_entry, best_source);
1050 source = best_source;
1056 * re-install the new forwarding information
1058 fib_entry_src_action_reactivate(fib_entry, source);
1062 fib_entry_post_update_actions(fib_entry, source, bflags);
1065 * still have sources
1067 return (FIB_ENTRY_SRC_FLAG_ADDED);
1073 * The source is withdrawing all the paths it provided
1075 fib_entry_src_flag_t
1076 fib_entry_delete (fib_node_index_t fib_entry_index,
1077 fib_source_t source)
1079 return (fib_entry_special_remove(fib_entry_index, source));
1085 * The source has provided a new set of paths that will replace the old.
1088 fib_entry_update (fib_node_index_t fib_entry_index,
1089 fib_source_t source,
1090 fib_entry_flag_t flags,
1091 const fib_route_path_t *paths)
1093 fib_source_t best_source;
1094 fib_entry_flag_t bflags;
1095 fib_entry_t *fib_entry;
1096 fib_entry_src_t *bsrc;
1098 fib_entry = fib_entry_get(fib_entry_index);
1099 ASSERT(NULL != fib_entry);
1101 bsrc = fib_entry_get_best_src_i(fib_entry);
1102 best_source = fib_entry_src_get_source(bsrc);
1103 bflags = fib_entry_src_get_flags(bsrc);
1105 fib_entry_src_action_path_swap(fib_entry,
1110 * handle possible realloc's by refetching the pointer
1112 fib_entry = fib_entry_get(fib_entry_index);
1115 * if the path list for the source passed is invalid,
1116 * then we need to create a new one. else we are updating
1119 if (source < best_source)
1122 * we have a new winning source.
1124 fib_entry_src_action_deactivate(fib_entry, best_source);
1125 fib_entry_src_action_activate(fib_entry, source);
1127 else if (source > best_source) {
1129 * the new source loses. nothing to do here.
1130 * the data from the source is saved in the path-list created
1137 * the new source is one this entry already has.
1138 * But the path-list was updated, which will contribute new forwarding,
1141 fib_entry_src_action_deactivate(fib_entry, source);
1142 fib_entry_src_action_activate(fib_entry, source);
1145 fib_entry_post_update_actions(fib_entry, source, bflags);
1150 * fib_entry_cover_changed
1152 * this entry is tracking its cover and that cover has changed.
1155 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1157 fib_entry_src_cover_res_t res = {
1159 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1161 fib_source_t source, best_source;
1162 fib_entry_flag_t bflags;
1163 fib_entry_t *fib_entry;
1164 fib_entry_src_t *esrc;
1167 bflags = FIB_ENTRY_FLAG_NONE;
1168 best_source = FIB_SOURCE_FIRST;
1169 fib_entry = fib_entry_get(fib_entry_index);
1171 fib_attached_export_cover_change(fib_entry);
1174 * propagate the notificuation to each of the added sources
1177 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1182 * only the best source gets to set the back walk flags
1184 res = fib_entry_src_action_cover_change(fib_entry, source);
1185 bflags = fib_entry_src_get_flags(esrc);
1186 best_source = fib_entry_src_get_source(esrc);
1190 fib_entry_src_action_cover_change(fib_entry, source);
1197 fib_entry_src_action_reactivate(fib_entry,
1198 fib_entry_src_get_source(
1199 fib_entry_get_best_src_i(fib_entry)));
1200 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1204 fib_entry_src_action_uninstall(fib_entry);
1207 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1210 * time for walkies fido.
1212 fib_node_back_walk_ctx_t bw_ctx = {
1213 .fnbw_reason = res.bw_reason,
1216 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1221 * fib_entry_cover_updated
1223 * this entry is tracking its cover and that cover has been updated
1224 * (i.e. its forwarding information has changed).
1227 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1229 fib_entry_src_cover_res_t res = {
1231 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1233 fib_source_t source, best_source;
1234 fib_entry_flag_t bflags;
1235 fib_entry_t *fib_entry;
1236 fib_entry_src_t *esrc;
1239 bflags = FIB_ENTRY_FLAG_NONE;
1240 best_source = FIB_SOURCE_FIRST;
1241 fib_entry = fib_entry_get(fib_entry_index);
1243 fib_attached_export_cover_update(fib_entry);
1246 * propagate the notificuation to each of the added sources
1249 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1254 * only the best source gets to set the back walk flags
1256 res = fib_entry_src_action_cover_update(fib_entry, source);
1257 bflags = fib_entry_src_get_flags(esrc);
1258 best_source = fib_entry_src_get_source(esrc);
1262 fib_entry_src_action_cover_update(fib_entry, source);
1269 fib_entry_src_action_reactivate(fib_entry,
1270 fib_entry_src_get_source(
1271 fib_entry_get_best_src_i(fib_entry)));
1272 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1276 fib_entry_src_action_uninstall(fib_entry);
1279 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1282 * time for walkies fido.
1284 fib_node_back_walk_ctx_t bw_ctx = {
1285 .fnbw_reason = res.bw_reason,
1288 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1293 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1294 fib_node_index_t **entry_indicies)
1296 fib_entry_t *fib_entry;
1297 int was_looped, is_looped;
1299 fib_entry = fib_entry_get(entry_index);
1301 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1303 fib_node_index_t *entries = *entry_indicies;
1305 vec_add1(entries, entry_index);
1306 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1307 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1310 *entry_indicies = entries;
1312 if (!!was_looped != !!is_looped)
1315 * re-evaluate all the entry's forwarding
1316 * NOTE: this is an inplace modify
1318 fib_entry_delegate_type_t fdt;
1319 fib_entry_delegate_t *fed;
1321 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1323 fib_entry_src_mk_lb(fib_entry,
1324 fib_entry_get_best_src_i(fib_entry),
1325 fib_entry_delegate_type_to_chain_type(fdt),
1333 * the entry is currently not linked to a path-list. this happens
1334 * when it is this entry that is re-linking path-lists and has thus
1344 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1346 fib_entry_t *fib_entry;
1348 fib_entry = fib_entry_get(entry_index);
1350 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1354 fib_entry_get_best_source (fib_node_index_t entry_index)
1356 fib_entry_t *fib_entry;
1357 fib_entry_src_t *bsrc;
1359 fib_entry = fib_entry_get(entry_index);
1361 bsrc = fib_entry_get_best_src_i(fib_entry);
1362 return (fib_entry_src_get_source(bsrc));
1366 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
1370 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1372 fib_entry_delegate_t *fed;
1373 fib_entry_t *fib_entry;
1375 fib_entry = fib_entry_get(fib_entry_index);
1377 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1382 * no BFD tracking - consider it resolved.
1389 * defer to the state of the BFD tracking
1391 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1396 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1397 flow_hash_config_t hash_config)
1399 fib_entry_t *fib_entry;
1401 fib_entry = fib_entry_get(fib_entry_index);
1404 * pass the hash-config on to the load-balance object where it is cached.
1405 * we can ignore LBs in the delegate chains, since they will not be of the
1406 * correct protocol type (i.e. they are not IP)
1407 * There's no way, nor need, to change the hash config for MPLS.
1409 if (dpo_id_is_valid(&fib_entry->fe_lb))
1413 ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1415 lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1418 * atomic update for packets in flight
1420 lb->lb_hash_config = hash_config;
1425 fib_ip4_address_compare (const ip4_address_t * a1,
1426 const ip4_address_t * a2)
1429 * IP addresses are unsiged ints. the return value here needs to be signed
1430 * a simple subtraction won't cut it.
1431 * If the addresses are the same, the sort order is undefiend, so phoey.
1433 return ((clib_net_to_host_u32(a1->data_u32) >
1434 clib_net_to_host_u32(a2->data_u32) ) ?
1439 fib_ip6_address_compare (const ip6_address_t * a1,
1440 const ip6_address_t * a2)
1443 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1445 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1446 clib_net_to_host_u16 (a2->as_u16[i]));
1454 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1455 fib_node_index_t fib_entry_index2)
1457 fib_entry_t *fib_entry1, *fib_entry2;
1460 fib_entry1 = fib_entry_get(fib_entry_index1);
1461 fib_entry2 = fib_entry_get(fib_entry_index2);
1463 switch (fib_entry1->fe_prefix.fp_proto)
1465 case FIB_PROTOCOL_IP4:
1466 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1467 &fib_entry2->fe_prefix.fp_addr.ip4);
1469 case FIB_PROTOCOL_IP6:
1470 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1471 &fib_entry2->fe_prefix.fp_addr.ip6);
1473 case FIB_PROTOCOL_MPLS:
1474 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1478 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1484 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1490 fib_entry_cmp_for_sort (void *i1, void *i2)
1492 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1494 return (fib_entry_cmp(*fib_entry_index1,
1495 *fib_entry_index2));
1499 fib_entry_lock (fib_node_index_t fib_entry_index)
1501 fib_entry_t *fib_entry;
1503 fib_entry = fib_entry_get(fib_entry_index);
1505 fib_node_lock(&fib_entry->fe_node);
1509 fib_entry_unlock (fib_node_index_t fib_entry_index)
1511 fib_entry_t *fib_entry;
1513 fib_entry = fib_entry_get(fib_entry_index);
1515 fib_node_unlock(&fib_entry->fe_node);
1519 fib_entry_module_init (void)
1521 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1525 fib_entry_encode (fib_node_index_t fib_entry_index,
1526 fib_route_path_encode_t **api_rpaths)
1528 fib_entry_t *fib_entry;
1530 fib_entry = fib_entry_get(fib_entry_index);
1531 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1533 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1538 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1541 fib_entry_t *fib_entry;
1543 fib_entry = fib_entry_get(fib_entry_index);
1544 *pfx = fib_entry->fe_prefix;
1548 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1550 fib_entry_t *fib_entry;
1552 fib_entry = fib_entry_get(fib_entry_index);
1554 return (fib_entry->fe_fib_index);
1558 fib_entry_pool_size (void)
1560 return (pool_elts(fib_entry_pool));
1563 static clib_error_t *
1564 show_fib_entry_command (vlib_main_t * vm,
1565 unformat_input_t * input,
1566 vlib_cli_command_t * cmd)
1568 fib_node_index_t fei;
1570 if (unformat (input, "%d", &fei))
1573 * show one in detail
1575 if (!pool_is_free_index(fib_entry_pool, fei))
1577 vlib_cli_output (vm, "%d@%U",
1579 format_fib_entry, fei,
1580 FIB_ENTRY_FORMAT_DETAIL2);
1584 vlib_cli_output (vm, "entry %d invalid", fei);
1592 vlib_cli_output (vm, "FIB Entries:");
1593 pool_foreach_index(fei, fib_entry_pool,
1595 vlib_cli_output (vm, "%d@%U",
1597 format_fib_entry, fei,
1598 FIB_ENTRY_FORMAT_BRIEF);
1605 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1606 .path = "show fib entry",
1607 .function = show_fib_entry_command,
1608 .short_help = "show fib entry",