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)
79 * If the entry being asked is a eos-MPLS label entry,
80 * then use the payload-protocol field, that we stashed there
81 * for just this purpose
83 return (fib_forw_chain_type_from_dpo_proto(
84 fib_entry->fe_prefix.fp_payload_proto));
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_path_ext_t *path_ext;
98 fib_entry_t *fib_entry;
100 fib_node_index_t fei;
104 fei = va_arg (*args, fib_node_index_t);
105 level = va_arg (*args, int);
106 fib_entry = fib_entry_get(fei);
108 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
110 if (level >= FIB_ENTRY_FORMAT_DETAIL)
112 s = format (s, " fib:%d", fib_entry->fe_fib_index);
113 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
114 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
116 FOR_EACH_SRC_ADDED(fib_entry, src, source,
118 s = format (s, "\n src:%s ",
119 fib_source_names[source]);
120 s = fib_entry_src_format(fib_entry, source, s);
121 s = format (s, " refs:%d ", src->fes_ref_count);
122 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
123 s = format(s, "flags:");
124 FOR_EACH_FIB_ATTRIBUTE(attr) {
125 if ((1<<attr) & src->fes_entry_flags) {
126 s = format (s, "%s,", fib_attribute_names[attr]);
130 s = format (s, "\n");
131 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
133 s = fib_path_list_format(src->fes_pl, s);
135 if (NULL != src->fes_path_exts)
137 s = format(s, " Extensions:");
138 vec_foreach(path_ext, src->fes_path_exts)
140 s = format(s, "\n %U", format_fib_path_ext, path_ext);
145 s = format (s, "\n forwarding: ");
149 s = format (s, "\n");
152 fct = fib_entry_get_default_chain_type(fib_entry);
154 if (!dpo_id_is_valid(&fib_entry->fe_lb))
156 s = format (s, " UNRESOLVED\n");
161 s = format(s, " %U-chain\n %U",
162 format_fib_forw_chain_type, fct,
168 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
170 fib_entry_delegate_type_t fdt;
171 fib_entry_delegate_t *fed;
173 s = format (s, " Delegates:\n");
174 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
176 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
181 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
183 s = format(s, " Children:");
184 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
191 fib_entry_from_fib_node (fib_node_t *node)
194 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
196 return ((fib_entry_t*)node);
200 fib_entry_last_lock_gone (fib_node_t *node)
202 fib_entry_delegate_type_t fdt;
203 fib_entry_delegate_t *fed;
204 fib_entry_t *fib_entry;
206 fib_entry = fib_entry_from_fib_node(node);
208 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
210 dpo_reset(&fed->fd_dpo);
211 fib_entry_delegate_remove(fib_entry, fdt);
214 FIB_ENTRY_DBG(fib_entry, "last-lock");
216 fib_node_deinit(&fib_entry->fe_node);
217 // FIXME -RR Backwalk
219 ASSERT(0 == vec_len(fib_entry->fe_delegates));
220 vec_free(fib_entry->fe_delegates);
221 vec_free(fib_entry->fe_srcs);
222 pool_put(fib_entry_pool, fib_entry);
225 static fib_entry_src_t*
226 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
228 fib_entry_src_t *bsrc;
231 * the enum of sources is deliberately arranged in priority order
233 if (0 == vec_len(fib_entry->fe_srcs))
239 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
246 fib_entry_src_get_source (const fib_entry_src_t *esrc)
250 return (esrc->fes_src);
252 return (FIB_SOURCE_MAX);
255 static fib_entry_flag_t
256 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
260 return (esrc->fes_entry_flags);
262 return (FIB_ENTRY_FLAG_NONE);
266 fib_entry_get_flags (fib_node_index_t fib_entry_index)
268 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
272 * fib_entry_back_walk_notify
274 * A back walk has reach this entry.
276 static fib_node_back_walk_rc_t
277 fib_entry_back_walk_notify (fib_node_t *node,
278 fib_node_back_walk_ctx_t *ctx)
280 fib_entry_t *fib_entry;
282 fib_entry = fib_entry_from_fib_node(node);
284 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
285 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
286 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
287 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
288 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
289 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
291 fib_entry_src_action_reactivate(fib_entry,
292 fib_entry_get_best_source(
293 fib_entry_get_index(fib_entry)));
297 * all other walk types can be reclassifed to a re-evaluate to
298 * all recursive dependents.
299 * By reclassifying we ensure that should any of these walk types meet
300 * they can be merged.
302 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
305 * ... and nothing is forced sync from now on.
307 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
310 * propagate the backwalk further if we haven't already reached the
313 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
314 fib_entry_get_index(fib_entry),
317 return (FIB_NODE_BACK_WALK_CONTINUE);
321 fib_entry_show_memory (void)
323 u32 n_srcs = 0, n_exts = 0;
324 fib_entry_src_t *esrc;
327 fib_show_memory_usage("Entry",
328 pool_elts(fib_entry_pool),
329 pool_len(fib_entry_pool),
330 sizeof(fib_entry_t));
332 pool_foreach(entry, fib_entry_pool,
334 n_srcs += vec_len(entry->fe_srcs);
335 vec_foreach(esrc, entry->fe_srcs)
337 n_exts += vec_len(esrc->fes_path_exts);
341 fib_show_memory_usage("Entry Source",
342 n_srcs, n_srcs, sizeof(fib_entry_src_t));
343 fib_show_memory_usage("Entry Path-Extensions",
345 sizeof(fib_path_ext_t));
349 * The FIB path-list's graph node virtual function table
351 static const fib_node_vft_t fib_entry_vft = {
352 .fnv_get = fib_entry_get_node,
353 .fnv_last_lock = fib_entry_last_lock_gone,
354 .fnv_back_walk = fib_entry_back_walk_notify,
355 .fnv_mem_show = fib_entry_show_memory,
359 * @brief Contribute the set of Adjacencies that this entry forwards with
360 * to build the uRPF list of its children
363 fib_entry_contribute_urpf (fib_node_index_t entry_index,
366 fib_entry_t *fib_entry;
368 fib_entry = fib_entry_get(entry_index);
370 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
374 * fib_entry_contribute_forwarding
376 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
379 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
380 fib_forward_chain_type_t fct,
383 fib_entry_delegate_t *fed;
384 fib_entry_t *fib_entry;
386 fib_entry = fib_entry_get(fib_entry_index);
388 if (fct == fib_entry_get_default_chain_type(fib_entry))
390 dpo_copy(dpo, &fib_entry->fe_lb);
394 fed = fib_entry_delegate_get(fib_entry,
395 fib_entry_chain_type_to_delegate_type(fct));
399 fed = fib_entry_delegate_find_or_add(
401 fib_entry_chain_type_to_delegate_type(fct));
403 * on-demand create eos/non-eos.
404 * There is no on-demand delete because:
405 * - memory versus complexity & reliability:
406 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
407 * then up on the right trigger is more code. i favour the latter.
409 fib_entry_src_mk_lb(fib_entry,
410 fib_entry_get_best_src_i(fib_entry),
415 dpo_copy(dpo, &fed->fd_dpo);
420 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
422 fib_forward_chain_type_t fct;
423 fib_entry_t *fib_entry;
425 fib_entry = fib_entry_get(fib_entry_index);
426 fct = fib_entry_get_default_chain_type(fib_entry);
428 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
429 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
431 return (&fib_entry->fe_lb);
435 fib_entry_get_adj (fib_node_index_t fib_entry_index)
439 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
440 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
444 return (dpo->dpoi_index);
446 return (ADJ_INDEX_INVALID);
450 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
452 fib_entry_t *fib_entry;
454 fib_entry = fib_entry_get(fib_entry_index);
456 return (fib_entry->fe_parent);
460 fib_entry_child_add (fib_node_index_t fib_entry_index,
461 fib_node_type_t child_type,
462 fib_node_index_t child_index)
464 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
471 fib_entry_child_remove (fib_node_index_t fib_entry_index,
474 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
478 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
482 * if there are no children left then there is no reason to keep
483 * the non-default forwarding chains. those chains are built only
484 * because the children want them.
486 fib_entry_delegate_type_t fdt;
487 fib_entry_delegate_t *fed;
488 fib_entry_t *fib_entry;
490 fib_entry = fib_entry_get(fib_entry_index);
492 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
494 dpo_reset(&fed->fd_dpo);
495 fib_entry_delegate_remove(fib_entry, fdt);
501 fib_entry_alloc (u32 fib_index,
502 const fib_prefix_t *prefix,
503 fib_node_index_t *fib_entry_index)
505 fib_entry_t *fib_entry;
508 pool_get(fib_entry_pool, fib_entry);
509 memset(fib_entry, 0, sizeof(*fib_entry));
511 fib_node_init(&fib_entry->fe_node,
512 FIB_NODE_TYPE_ENTRY);
514 fib_entry->fe_fib_index = fib_index;
517 * the one time we need to update the const prefix is when
518 * the entry is first created
520 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
523 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
526 if (MPLS_NON_EOS == fep->fp_eos)
528 fep->fp_payload_proto = DPO_PROTO_MPLS;
530 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
533 dpo_reset(&fib_entry->fe_lb);
535 *fib_entry_index = fib_entry_get_index(fib_entry);
537 FIB_ENTRY_DBG(fib_entry, "alloc");
543 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
545 fib_entry_flag_t old_flags)
547 fib_node_index_t fei;
550 * save the index so we can recover from pool reallocs
552 fei = fib_entry_get_index(fib_entry);
555 * handle changes to attached export for import entries
557 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
558 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
560 if (!was_import && is_import)
563 * transition from not exported to exported
567 * there is an assumption here that the entry resolves via only
568 * one interface and that it is the cross VRF interface.
570 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
572 fib_attached_export_import(fib_entry,
573 fib_table_get_index_for_sw_if_index(
574 fib_entry_get_proto(fib_entry),
577 else if (was_import && !is_import)
580 * transition from exported to not exported
582 fib_attached_export_purge(fib_entry);
586 * no change. nothing to do.
590 * reload the entry address post possible pool realloc
592 fib_entry = fib_entry_get(fei);
595 * handle changes to attached export for export entries
597 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
598 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
600 if (!was_attached && is_attached)
603 * transition to attached. time to export
613 fib_entry_post_install_actions (fib_entry_t *fib_entry,
615 fib_entry_flag_t old_flags)
617 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
620 fib_entry_src_action_installed(fib_entry, source);
624 fib_entry_create (u32 fib_index,
625 const fib_prefix_t *prefix,
627 fib_entry_flag_t flags,
628 const fib_route_path_t *paths)
630 fib_node_index_t fib_entry_index;
631 fib_entry_t *fib_entry;
633 ASSERT(0 < vec_len(paths));
635 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
638 * since this is a new entry create, we don't need to check for winning
639 * sources - there is only one.
641 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
644 fib_entry_get_proto(fib_entry))));
645 fib_entry_src_action_path_swap(fib_entry,
650 * handle possible realloc's by refetching the pointer
652 fib_entry = fib_entry_get(fib_entry_index);
653 fib_entry_src_action_activate(fib_entry, source);
655 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
657 return (fib_entry_index);
661 fib_entry_create_special (u32 fib_index,
662 const fib_prefix_t *prefix,
664 fib_entry_flag_t flags,
667 fib_node_index_t fib_entry_index;
668 fib_entry_t *fib_entry;
671 * create and initiliase the new enty
673 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
676 * create the path-list
678 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
679 fib_entry_src_action_activate(fib_entry, source);
681 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
683 return (fib_entry_index);
687 fib_entry_post_update_actions (fib_entry_t *fib_entry,
689 fib_entry_flag_t old_flags)
692 * backwalk to children to inform then of the change to forwarding.
694 fib_node_back_walk_ctx_t bw_ctx = {
695 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
698 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
701 * then inform any covered prefixes
703 fib_entry_cover_update_notify(fib_entry);
705 fib_entry_post_install_actions(fib_entry, source, old_flags);
709 fib_entry_source_change (fib_entry_t *fib_entry,
710 fib_source_t best_source,
711 fib_source_t new_source,
712 fib_entry_flag_t old_flags)
715 * if the path list for the source passed is invalid,
716 * then we need to create a new one. else we are updating
719 if (new_source < best_source)
722 * we have a new winning source.
724 fib_entry_src_action_deactivate(fib_entry, best_source);
725 fib_entry_src_action_activate(fib_entry, new_source);
727 else if (new_source > best_source)
730 * the new source loses. nothing to do here.
731 * the data from the source is saved in the path-list created
738 * the new source is one this entry already has.
739 * But the path-list was updated, which will contribute new forwarding,
742 fib_entry_src_action_deactivate(fib_entry, new_source);
743 fib_entry_src_action_activate(fib_entry, new_source);
746 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
750 fib_entry_special_add (fib_node_index_t fib_entry_index,
752 fib_entry_flag_t flags,
755 fib_source_t best_source;
756 fib_entry_flag_t bflags;
757 fib_entry_t *fib_entry;
758 fib_entry_src_t *bsrc;
760 fib_entry = fib_entry_get(fib_entry_index);
762 bsrc = fib_entry_get_best_src_i(fib_entry);
763 best_source = fib_entry_src_get_source(bsrc);
764 bflags = fib_entry_src_get_flags(bsrc);
766 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
767 fib_entry_source_change(fib_entry, best_source, source, bflags);
771 fib_entry_special_update (fib_node_index_t fib_entry_index,
773 fib_entry_flag_t flags,
776 fib_source_t best_source;
777 fib_entry_flag_t bflags;
778 fib_entry_t *fib_entry;
779 fib_entry_src_t *bsrc;
781 fib_entry = fib_entry_get(fib_entry_index);
783 bsrc = fib_entry_get_best_src_i(fib_entry);
784 best_source = fib_entry_src_get_source(bsrc);
785 bflags = fib_entry_src_get_flags(bsrc);
787 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
788 fib_entry_source_change(fib_entry, best_source, source, bflags);
793 fib_entry_path_add (fib_node_index_t fib_entry_index,
795 fib_entry_flag_t flags,
796 const fib_route_path_t *rpath)
798 fib_source_t best_source;
799 fib_entry_flag_t bflags;
800 fib_entry_t *fib_entry;
801 fib_entry_src_t *bsrc;
803 ASSERT(1 == vec_len(rpath));
805 fib_entry = fib_entry_get(fib_entry_index);
806 ASSERT(NULL != fib_entry);
808 bsrc = fib_entry_get_best_src_i(fib_entry);
809 best_source = fib_entry_src_get_source(bsrc);
810 bflags = fib_entry_src_get_flags(bsrc);
812 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
815 * if the path list for the source passed is invalid,
816 * then we need to create a new one. else we are updating
819 if (source < best_source)
822 * we have a new winning source.
824 fib_entry_src_action_deactivate(fib_entry, best_source);
825 fib_entry_src_action_activate(fib_entry, source);
827 else if (source > best_source)
830 * the new source loses. nothing to do here.
831 * the data from the source is saved in the path-list created
838 * the new source is one this entry already has.
839 * But the path-list was updated, which will contribute new forwarding,
842 fib_entry_src_action_deactivate(fib_entry, source);
843 fib_entry_src_action_activate(fib_entry, source);
846 fib_entry_post_update_actions(fib_entry, source, bflags);
850 * fib_entry_path_remove
852 * remove a path from the entry.
853 * return the fib_entry's index if it is still present, INVALID otherwise.
856 fib_entry_path_remove (fib_node_index_t fib_entry_index,
858 const fib_route_path_t *rpath)
860 fib_entry_src_flag_t sflag;
861 fib_source_t best_source;
862 fib_entry_flag_t bflags;
863 fib_entry_t *fib_entry;
864 fib_entry_src_t *bsrc;
866 ASSERT(1 == vec_len(rpath));
868 fib_entry = fib_entry_get(fib_entry_index);
869 ASSERT(NULL != fib_entry);
871 bsrc = fib_entry_get_best_src_i(fib_entry);
872 best_source = fib_entry_src_get_source(bsrc);
873 bflags = fib_entry_src_get_flags(bsrc);
875 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
878 * if the path list for the source passed is invalid,
879 * then we need to create a new one. else we are updating
882 if (source < best_source )
885 * Que! removing a path from a source that is better than the
886 * one this entry is using.
890 else if (source > best_source )
893 * the source is not the best. nothing to do.
895 return (FIB_ENTRY_SRC_FLAG_ADDED);
900 * removing a path from the path-list we were using.
902 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
905 * the last path from the source was removed.
906 * fallback to lower source
908 bsrc = fib_entry_get_best_src_i(fib_entry);
909 best_source = fib_entry_src_get_source(bsrc);
911 if (FIB_SOURCE_MAX == best_source) {
913 * no more sources left. this entry is toast.
915 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
918 fib_entry_src_action_uninstall(fib_entry);
920 return (FIB_ENTRY_SRC_FLAG_NONE);
924 fib_entry_src_action_activate(fib_entry, best_source);
925 source = best_source;
931 * re-install the new forwarding information
933 fib_entry_src_action_deactivate(fib_entry, source);
934 fib_entry_src_action_activate(fib_entry, source);
938 fib_entry_post_update_actions(fib_entry, source, bflags);
943 return (FIB_ENTRY_SRC_FLAG_ADDED);
947 * fib_entry_special_remove
949 * remove a special source from the entry.
950 * return the fib_entry's index if it is still present, INVALID otherwise.
953 fib_entry_special_remove (fib_node_index_t fib_entry_index,
956 fib_entry_src_flag_t sflag;
957 fib_source_t best_source;
958 fib_entry_flag_t bflags;
959 fib_entry_t *fib_entry;
960 fib_entry_src_t *bsrc;
962 fib_entry = fib_entry_get(fib_entry_index);
963 ASSERT(NULL != fib_entry);
965 bsrc = fib_entry_get_best_src_i(fib_entry);
966 best_source = fib_entry_src_get_source(bsrc);
967 bflags = fib_entry_src_get_flags(bsrc);
969 sflag = fib_entry_src_action_remove(fib_entry, source);
972 * if the path list for the source passed is invalid,
973 * then we need to create a new one. else we are updating
976 if (source < best_source )
979 * Que! removing a path from a source that is better than the
980 * one this entry is using. This can only mean it is a source
981 * this prefix does not have.
983 return (FIB_ENTRY_SRC_FLAG_ADDED);
985 else if (source > best_source ) {
987 * the source is not the best. nothing to do.
989 return (FIB_ENTRY_SRC_FLAG_ADDED);
993 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
996 * the source was removed. use the next best.
998 bsrc = fib_entry_get_best_src_i(fib_entry);
999 best_source = fib_entry_src_get_source(bsrc);
1001 if (FIB_SOURCE_MAX == best_source) {
1003 * no more sources left. this entry is toast.
1005 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
1008 fib_entry_src_action_uninstall(fib_entry);
1010 return (FIB_ENTRY_SRC_FLAG_NONE);
1014 fib_entry_src_action_activate(fib_entry, best_source);
1015 source = best_source;
1021 * re-install the new forwarding information
1023 fib_entry_src_action_reactivate(fib_entry, source);
1027 fib_entry_post_update_actions(fib_entry, source, bflags);
1030 * still have sources
1032 return (FIB_ENTRY_SRC_FLAG_ADDED);
1038 * The source is withdrawing all the paths it provided
1040 fib_entry_src_flag_t
1041 fib_entry_delete (fib_node_index_t fib_entry_index,
1042 fib_source_t source)
1044 return (fib_entry_special_remove(fib_entry_index, source));
1050 * The source has provided a new set of paths that will replace the old.
1053 fib_entry_update (fib_node_index_t fib_entry_index,
1054 fib_source_t source,
1055 fib_entry_flag_t flags,
1056 const fib_route_path_t *paths)
1058 fib_source_t best_source;
1059 fib_entry_flag_t bflags;
1060 fib_entry_t *fib_entry;
1061 fib_entry_src_t *bsrc;
1063 fib_entry = fib_entry_get(fib_entry_index);
1064 ASSERT(NULL != fib_entry);
1066 bsrc = fib_entry_get_best_src_i(fib_entry);
1067 best_source = fib_entry_src_get_source(bsrc);
1068 bflags = fib_entry_src_get_flags(bsrc);
1070 fib_entry_src_action_path_swap(fib_entry,
1075 * handle possible realloc's by refetching the pointer
1077 fib_entry = fib_entry_get(fib_entry_index);
1080 * if the path list for the source passed is invalid,
1081 * then we need to create a new one. else we are updating
1084 if (source < best_source)
1087 * we have a new winning source.
1089 fib_entry_src_action_deactivate(fib_entry, best_source);
1090 fib_entry_src_action_activate(fib_entry, source);
1092 else if (source > best_source) {
1094 * the new source loses. nothing to do here.
1095 * the data from the source is saved in the path-list created
1102 * the new source is one this entry already has.
1103 * But the path-list was updated, which will contribute new forwarding,
1106 fib_entry_src_action_deactivate(fib_entry, source);
1107 fib_entry_src_action_activate(fib_entry, source);
1110 fib_entry_post_update_actions(fib_entry, source, bflags);
1115 * fib_entry_cover_changed
1117 * this entry is tracking its cover and that cover has changed.
1120 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1122 fib_entry_src_cover_res_t res = {
1124 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1126 fib_source_t source, best_source;
1127 fib_entry_flag_t bflags;
1128 fib_entry_t *fib_entry;
1129 fib_entry_src_t *esrc;
1132 bflags = FIB_ENTRY_FLAG_NONE;
1133 best_source = FIB_SOURCE_FIRST;
1134 fib_entry = fib_entry_get(fib_entry_index);
1136 fib_attached_export_cover_change(fib_entry);
1139 * propagate the notificuation to each of the added sources
1142 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1147 * only the best source gets to set the back walk flags
1149 res = fib_entry_src_action_cover_change(fib_entry, source);
1150 bflags = fib_entry_src_get_flags(esrc);
1151 best_source = fib_entry_src_get_source(esrc);
1155 fib_entry_src_action_cover_change(fib_entry, source);
1162 fib_entry_src_action_reactivate(fib_entry,
1163 fib_entry_src_get_source(
1164 fib_entry_get_best_src_i(fib_entry)));
1165 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1169 fib_entry_src_action_uninstall(fib_entry);
1172 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1175 * time for walkies fido.
1177 fib_node_back_walk_ctx_t bw_ctx = {
1178 .fnbw_reason = res.bw_reason,
1181 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1186 * fib_entry_cover_updated
1188 * this entry is tracking its cover and that cover has been updated
1189 * (i.e. its forwarding information has changed).
1192 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1194 fib_entry_src_cover_res_t res = {
1196 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1198 fib_source_t source, best_source;
1199 fib_entry_flag_t bflags;
1200 fib_entry_t *fib_entry;
1201 fib_entry_src_t *esrc;
1204 bflags = FIB_ENTRY_FLAG_NONE;
1205 best_source = FIB_SOURCE_FIRST;
1206 fib_entry = fib_entry_get(fib_entry_index);
1208 fib_attached_export_cover_update(fib_entry);
1211 * propagate the notificuation to each of the added sources
1214 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1219 * only the best source gets to set the back walk flags
1221 res = fib_entry_src_action_cover_update(fib_entry, source);
1222 bflags = fib_entry_src_get_flags(esrc);
1223 best_source = fib_entry_src_get_source(esrc);
1227 fib_entry_src_action_cover_update(fib_entry, source);
1234 fib_entry_src_action_reactivate(fib_entry,
1235 fib_entry_src_get_source(
1236 fib_entry_get_best_src_i(fib_entry)));
1237 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1241 fib_entry_src_action_uninstall(fib_entry);
1244 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1247 * time for walkies fido.
1249 fib_node_back_walk_ctx_t bw_ctx = {
1250 .fnbw_reason = res.bw_reason,
1253 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1258 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1259 fib_node_index_t **entry_indicies)
1261 fib_entry_t *fib_entry;
1262 int was_looped, is_looped;
1264 fib_entry = fib_entry_get(entry_index);
1266 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1268 fib_node_index_t *entries = *entry_indicies;
1270 vec_add1(entries, entry_index);
1271 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1272 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1275 *entry_indicies = entries;
1277 if (!!was_looped != !!is_looped)
1280 * re-evaluate all the entry's forwarding
1281 * NOTE: this is an inplace modify
1283 fib_entry_delegate_type_t fdt;
1284 fib_entry_delegate_t *fed;
1286 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1288 fib_entry_src_mk_lb(fib_entry,
1289 fib_entry_get_best_src_i(fib_entry),
1290 fib_entry_delegate_type_to_chain_type(fdt),
1298 * the entry is currently not linked to a path-list. this happens
1299 * when it is this entry that is re-linking path-lists and has thus
1309 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1311 fib_entry_t *fib_entry;
1313 fib_entry = fib_entry_get(entry_index);
1315 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1319 fib_entry_get_best_source (fib_node_index_t entry_index)
1321 fib_entry_t *fib_entry;
1322 fib_entry_src_t *bsrc;
1324 fib_entry = fib_entry_get(entry_index);
1326 bsrc = fib_entry_get_best_src_i(fib_entry);
1327 return (fib_entry_src_get_source(bsrc));
1331 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
1335 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1337 fib_entry_delegate_t *fed;
1338 fib_entry_t *fib_entry;
1340 fib_entry = fib_entry_get(fib_entry_index);
1342 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1347 * no BFD tracking - resolved
1354 * defer to the state of the BFD tracking
1356 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1361 fib_ip4_address_compare (const ip4_address_t * a1,
1362 const ip4_address_t * a2)
1365 * IP addresses are unsiged ints. the return value here needs to be signed
1366 * a simple subtraction won't cut it.
1367 * If the addresses are the same, the sort order is undefiend, so phoey.
1369 return ((clib_net_to_host_u32(a1->data_u32) >
1370 clib_net_to_host_u32(a2->data_u32) ) ?
1375 fib_ip6_address_compare (const ip6_address_t * a1,
1376 const ip6_address_t * a2)
1379 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1381 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1382 clib_net_to_host_u16 (a2->as_u16[i]));
1390 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1391 fib_node_index_t fib_entry_index2)
1393 fib_entry_t *fib_entry1, *fib_entry2;
1396 fib_entry1 = fib_entry_get(fib_entry_index1);
1397 fib_entry2 = fib_entry_get(fib_entry_index2);
1399 switch (fib_entry1->fe_prefix.fp_proto)
1401 case FIB_PROTOCOL_IP4:
1402 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1403 &fib_entry2->fe_prefix.fp_addr.ip4);
1405 case FIB_PROTOCOL_IP6:
1406 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1407 &fib_entry2->fe_prefix.fp_addr.ip6);
1409 case FIB_PROTOCOL_MPLS:
1410 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1414 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1420 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1426 fib_entry_cmp_for_sort (void *i1, void *i2)
1428 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1430 return (fib_entry_cmp(*fib_entry_index1,
1431 *fib_entry_index2));
1435 fib_entry_lock (fib_node_index_t fib_entry_index)
1437 fib_entry_t *fib_entry;
1439 fib_entry = fib_entry_get(fib_entry_index);
1441 fib_node_lock(&fib_entry->fe_node);
1445 fib_entry_unlock (fib_node_index_t fib_entry_index)
1447 fib_entry_t *fib_entry;
1449 fib_entry = fib_entry_get(fib_entry_index);
1451 fib_node_unlock(&fib_entry->fe_node);
1455 fib_entry_module_init (void)
1457 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1461 fib_entry_encode (fib_node_index_t fib_entry_index,
1462 fib_route_path_encode_t **api_rpaths)
1464 fib_entry_t *fib_entry;
1466 fib_entry = fib_entry_get(fib_entry_index);
1467 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1469 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1474 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1477 fib_entry_t *fib_entry;
1479 fib_entry = fib_entry_get(fib_entry_index);
1480 *pfx = fib_entry->fe_prefix;
1484 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1486 fib_entry_t *fib_entry;
1488 fib_entry = fib_entry_get(fib_entry_index);
1490 return (fib_entry->fe_fib_index);
1494 fib_entry_pool_size (void)
1496 return (pool_elts(fib_entry_pool));
1499 static clib_error_t *
1500 show_fib_entry_command (vlib_main_t * vm,
1501 unformat_input_t * input,
1502 vlib_cli_command_t * cmd)
1504 fib_node_index_t fei;
1506 if (unformat (input, "%d", &fei))
1509 * show one in detail
1511 if (!pool_is_free_index(fib_entry_pool, fei))
1513 vlib_cli_output (vm, "%d@%U",
1515 format_fib_entry, fei,
1516 FIB_ENTRY_FORMAT_DETAIL2);
1520 vlib_cli_output (vm, "entry %d invalid", fei);
1528 vlib_cli_output (vm, "FIB Entries:");
1529 pool_foreach_index(fei, fib_entry_pool,
1531 vlib_cli_output (vm, "%d@%U",
1533 format_fib_entry, fei,
1534 FIB_ENTRY_FORMAT_BRIEF);
1541 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1542 .path = "show fib entry",
1543 .function = show_fib_entry_command,
1544 .short_help = "show fib entry",