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, "\n src:%s ",
98 fib_source_names[source]);
104 format_fib_entry (u8 * s, va_list * args)
106 fib_forward_chain_type_t fct;
107 fib_entry_attribute_t attr;
108 fib_entry_t *fib_entry;
109 fib_entry_src_t *src;
110 fib_node_index_t fei;
114 fei = va_arg (*args, fib_node_index_t);
115 level = va_arg (*args, int);
116 fib_entry = fib_entry_get(fei);
118 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
120 if (level >= FIB_ENTRY_FORMAT_DETAIL)
122 s = format (s, " fib:%d", fib_entry->fe_fib_index);
123 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
124 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
126 FOR_EACH_SRC_ADDED(fib_entry, src, source,
128 s = format (s, "\n src:%U ",
129 format_fib_source, source);
130 s = fib_entry_src_format(fib_entry, source, s);
131 s = format (s, " refs:%d ", src->fes_ref_count);
132 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
133 s = format(s, "flags:");
134 FOR_EACH_FIB_ATTRIBUTE(attr) {
135 if ((1<<attr) & src->fes_entry_flags) {
136 s = format (s, "%s,", fib_attribute_names[attr]);
140 s = format (s, "\n");
141 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
143 s = fib_path_list_format(src->fes_pl, s);
145 s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
148 s = format (s, "\n forwarding: ");
152 s = format (s, "\n");
155 fct = fib_entry_get_default_chain_type(fib_entry);
157 if (!dpo_id_is_valid(&fib_entry->fe_lb))
159 s = format (s, " UNRESOLVED\n");
164 s = format(s, " %U-chain\n %U",
165 format_fib_forw_chain_type, fct,
171 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
173 fib_entry_delegate_type_t fdt;
174 fib_entry_delegate_t *fed;
176 s = format (s, " Delegates:\n");
177 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
179 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
184 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
186 s = format(s, " Children:");
187 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
194 fib_entry_from_fib_node (fib_node_t *node)
197 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
199 return ((fib_entry_t*)node);
203 fib_entry_last_lock_gone (fib_node_t *node)
205 fib_entry_delegate_type_t fdt;
206 fib_entry_delegate_t *fed;
207 fib_entry_t *fib_entry;
209 fib_entry = fib_entry_from_fib_node(node);
211 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
213 dpo_reset(&fed->fd_dpo);
214 fib_entry_delegate_remove(fib_entry, fdt);
217 FIB_ENTRY_DBG(fib_entry, "last-lock");
219 fib_node_deinit(&fib_entry->fe_node);
220 // FIXME -RR Backwalk
222 ASSERT(0 == vec_len(fib_entry->fe_delegates));
223 vec_free(fib_entry->fe_delegates);
224 vec_free(fib_entry->fe_srcs);
225 pool_put(fib_entry_pool, fib_entry);
228 static fib_entry_src_t*
229 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
231 fib_entry_src_t *bsrc;
234 * the enum of sources is deliberately arranged in priority order
236 if (0 == vec_len(fib_entry->fe_srcs))
242 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
249 fib_entry_src_get_source (const fib_entry_src_t *esrc)
253 return (esrc->fes_src);
255 return (FIB_SOURCE_MAX);
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 (fib_node_index_t fib_entry_index)
271 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
275 * fib_entry_back_walk_notify
277 * A back walk has reach this entry.
279 static fib_node_back_walk_rc_t
280 fib_entry_back_walk_notify (fib_node_t *node,
281 fib_node_back_walk_ctx_t *ctx)
283 fib_entry_t *fib_entry;
285 fib_entry = fib_entry_from_fib_node(node);
287 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
288 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
289 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
290 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
291 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
292 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
294 fib_entry_src_action_reactivate(fib_entry,
295 fib_entry_get_best_source(
296 fib_entry_get_index(fib_entry)));
300 * all other walk types can be reclassifed to a re-evaluate to
301 * all recursive dependents.
302 * By reclassifying we ensure that should any of these walk types meet
303 * they can be merged.
305 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
308 * ... and nothing is forced sync from now on.
310 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
313 * propagate the backwalk further if we haven't already reached the
316 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
317 fib_entry_get_index(fib_entry),
320 return (FIB_NODE_BACK_WALK_CONTINUE);
324 fib_entry_show_memory (void)
326 u32 n_srcs = 0, n_exts = 0;
327 fib_entry_src_t *esrc;
330 fib_show_memory_usage("Entry",
331 pool_elts(fib_entry_pool),
332 pool_len(fib_entry_pool),
333 sizeof(fib_entry_t));
335 pool_foreach(entry, fib_entry_pool,
337 n_srcs += vec_len(entry->fe_srcs);
338 vec_foreach(esrc, entry->fe_srcs)
340 n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
344 fib_show_memory_usage("Entry Source",
345 n_srcs, n_srcs, sizeof(fib_entry_src_t));
346 fib_show_memory_usage("Entry Path-Extensions",
348 sizeof(fib_path_ext_t));
352 * The FIB path-list's graph node virtual function table
354 static const fib_node_vft_t fib_entry_vft = {
355 .fnv_get = fib_entry_get_node,
356 .fnv_last_lock = fib_entry_last_lock_gone,
357 .fnv_back_walk = fib_entry_back_walk_notify,
358 .fnv_mem_show = fib_entry_show_memory,
362 * @brief Contribute the set of Adjacencies that this entry forwards with
363 * to build the uRPF list of its children
366 fib_entry_contribute_urpf (fib_node_index_t entry_index,
369 fib_entry_t *fib_entry;
371 fib_entry = fib_entry_get(entry_index);
373 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
377 * If the client is request a chain for multicast forwarding then swap
378 * the chain type to one that can provide such transport.
380 static fib_forward_chain_type_t
381 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
385 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
386 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
388 * we can only transport IP multicast packets if there is an
391 fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
393 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
394 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
395 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
396 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
397 case FIB_FORW_CHAIN_TYPE_ETHERNET:
398 case FIB_FORW_CHAIN_TYPE_NSH:
406 * fib_entry_contribute_forwarding
408 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
411 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
412 fib_forward_chain_type_t fct,
415 fib_entry_delegate_t *fed;
416 fib_entry_t *fib_entry;
418 fib_entry = fib_entry_get(fib_entry_index);
421 * mfib children ask for mcast chains. fix these to the appropriate ucast types.
423 fct = fib_entry_chain_type_mcast_to_ucast(fct);
425 if (fct == fib_entry_get_default_chain_type(fib_entry))
427 dpo_copy(dpo, &fib_entry->fe_lb);
431 fed = fib_entry_delegate_get(fib_entry,
432 fib_entry_chain_type_to_delegate_type(fct));
436 fed = fib_entry_delegate_find_or_add(
438 fib_entry_chain_type_to_delegate_type(fct));
440 * on-demand create eos/non-eos.
441 * There is no on-demand delete because:
442 * - memory versus complexity & reliability:
443 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
444 * then up on the right trigger is more code. i favour the latter.
446 fib_entry_src_mk_lb(fib_entry,
447 fib_entry_get_best_src_i(fib_entry),
452 dpo_copy(dpo, &fed->fd_dpo);
455 * don't allow the special index indicating replicate.vs.load-balance
456 * to escape to the clients
458 dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
462 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
464 fib_forward_chain_type_t fct;
465 fib_entry_t *fib_entry;
467 fib_entry = fib_entry_get(fib_entry_index);
468 fct = fib_entry_get_default_chain_type(fib_entry);
470 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
471 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
473 return (&fib_entry->fe_lb);
477 fib_entry_get_adj (fib_node_index_t fib_entry_index)
481 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
483 if (dpo_id_is_valid(dpo))
485 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
489 return (dpo->dpoi_index);
492 return (ADJ_INDEX_INVALID);
496 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
498 fib_entry_t *fib_entry;
500 fib_entry = fib_entry_get(fib_entry_index);
502 return (fib_entry->fe_parent);
506 fib_entry_child_add (fib_node_index_t fib_entry_index,
507 fib_node_type_t child_type,
508 fib_node_index_t child_index)
510 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
517 fib_entry_child_remove (fib_node_index_t fib_entry_index,
520 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
524 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
528 * if there are no children left then there is no reason to keep
529 * the non-default forwarding chains. those chains are built only
530 * because the children want them.
532 fib_entry_delegate_type_t fdt;
533 fib_entry_delegate_t *fed;
534 fib_entry_t *fib_entry;
536 fib_entry = fib_entry_get(fib_entry_index);
538 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
540 dpo_reset(&fed->fd_dpo);
541 fib_entry_delegate_remove(fib_entry, fdt);
547 fib_entry_alloc (u32 fib_index,
548 const fib_prefix_t *prefix,
549 fib_node_index_t *fib_entry_index)
551 fib_entry_t *fib_entry;
554 pool_get(fib_entry_pool, fib_entry);
555 memset(fib_entry, 0, sizeof(*fib_entry));
557 fib_node_init(&fib_entry->fe_node,
558 FIB_NODE_TYPE_ENTRY);
560 fib_entry->fe_fib_index = fib_index;
563 * the one time we need to update the const prefix is when
564 * the entry is first created
566 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
569 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
572 if (MPLS_NON_EOS == fep->fp_eos)
574 fep->fp_payload_proto = DPO_PROTO_MPLS;
576 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
579 dpo_reset(&fib_entry->fe_lb);
581 *fib_entry_index = fib_entry_get_index(fib_entry);
583 FIB_ENTRY_DBG(fib_entry, "alloc");
589 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
591 fib_entry_flag_t old_flags)
593 fib_node_index_t fei;
596 * save the index so we can recover from pool reallocs
598 fei = fib_entry_get_index(fib_entry);
601 * handle changes to attached export for import entries
603 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
604 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
606 if (!was_import && is_import)
609 * transition from not exported to exported
613 * there is an assumption here that the entry resolves via only
614 * one interface and that it is the cross VRF interface.
616 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
618 fib_attached_export_import(fib_entry,
619 fib_table_get_index_for_sw_if_index(
620 fib_entry_get_proto(fib_entry),
623 else if (was_import && !is_import)
626 * transition from exported to not exported
628 fib_attached_export_purge(fib_entry);
632 * no change. nothing to do.
636 * reload the entry address post possible pool realloc
638 fib_entry = fib_entry_get(fei);
641 * handle changes to attached export for export entries
643 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
644 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
646 if (!was_attached && is_attached)
649 * transition to attached. time to export
659 fib_entry_post_install_actions (fib_entry_t *fib_entry,
661 fib_entry_flag_t old_flags)
663 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
666 fib_entry_src_action_installed(fib_entry, source);
670 fib_entry_create (u32 fib_index,
671 const fib_prefix_t *prefix,
673 fib_entry_flag_t flags,
674 const fib_route_path_t *paths)
676 fib_node_index_t fib_entry_index;
677 fib_entry_t *fib_entry;
679 ASSERT(0 < vec_len(paths));
681 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
684 * since this is a new entry create, we don't need to check for winning
685 * sources - there is only one.
687 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
690 fib_entry_get_proto(fib_entry))));
691 fib_entry_src_action_path_swap(fib_entry,
696 * handle possible realloc's by refetching the pointer
698 fib_entry = fib_entry_get(fib_entry_index);
699 fib_entry_src_action_activate(fib_entry, source);
701 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
703 return (fib_entry_index);
707 fib_entry_create_special (u32 fib_index,
708 const fib_prefix_t *prefix,
710 fib_entry_flag_t flags,
713 fib_node_index_t fib_entry_index;
714 fib_entry_t *fib_entry;
717 * create and initiliase the new enty
719 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
722 * create the path-list
724 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
725 fib_entry_src_action_activate(fib_entry, source);
727 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
729 return (fib_entry_index);
733 fib_entry_post_update_actions (fib_entry_t *fib_entry,
735 fib_entry_flag_t old_flags)
738 * backwalk to children to inform then of the change to forwarding.
740 fib_node_back_walk_ctx_t bw_ctx = {
741 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
744 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
747 * then inform any covered prefixes
749 fib_entry_cover_update_notify(fib_entry);
751 fib_entry_post_install_actions(fib_entry, source, old_flags);
755 fib_entry_source_change (fib_entry_t *fib_entry,
756 fib_source_t best_source,
757 fib_source_t new_source,
758 fib_entry_flag_t old_flags)
761 * if the path list for the source passed is invalid,
762 * then we need to create a new one. else we are updating
765 if (new_source < best_source)
768 * we have a new winning source.
770 fib_entry_src_action_deactivate(fib_entry, best_source);
771 fib_entry_src_action_activate(fib_entry, new_source);
773 else if (new_source > best_source)
776 * the new source loses. nothing to do here.
777 * the data from the source is saved in the path-list created
784 * the new source is one this entry already has.
785 * But the path-list was updated, which will contribute new forwarding,
788 fib_entry_src_action_deactivate(fib_entry, new_source);
789 fib_entry_src_action_activate(fib_entry, new_source);
792 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
796 fib_entry_special_add (fib_node_index_t fib_entry_index,
798 fib_entry_flag_t flags,
801 fib_source_t best_source;
802 fib_entry_flag_t bflags;
803 fib_entry_t *fib_entry;
804 fib_entry_src_t *bsrc;
806 fib_entry = fib_entry_get(fib_entry_index);
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_add(fib_entry, source, flags, dpo);
813 fib_entry_source_change(fib_entry, best_source, source, bflags);
817 fib_entry_special_update (fib_node_index_t fib_entry_index,
819 fib_entry_flag_t flags,
822 fib_source_t best_source;
823 fib_entry_flag_t bflags;
824 fib_entry_t *fib_entry;
825 fib_entry_src_t *bsrc;
827 fib_entry = fib_entry_get(fib_entry_index);
829 bsrc = fib_entry_get_best_src_i(fib_entry);
830 best_source = fib_entry_src_get_source(bsrc);
831 bflags = fib_entry_src_get_flags(bsrc);
833 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
834 fib_entry_source_change(fib_entry, best_source, source, bflags);
839 fib_entry_path_add (fib_node_index_t fib_entry_index,
841 fib_entry_flag_t flags,
842 const fib_route_path_t *rpath)
844 fib_source_t best_source;
845 fib_entry_flag_t bflags;
846 fib_entry_t *fib_entry;
847 fib_entry_src_t *bsrc;
849 ASSERT(1 == vec_len(rpath));
851 fib_entry = fib_entry_get(fib_entry_index);
852 ASSERT(NULL != fib_entry);
854 bsrc = fib_entry_get_best_src_i(fib_entry);
855 best_source = fib_entry_src_get_source(bsrc);
856 bflags = fib_entry_src_get_flags(bsrc);
858 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
861 * if the path list for the source passed is invalid,
862 * then we need to create a new one. else we are updating
865 if (source < best_source)
868 * we have a new winning source.
870 fib_entry_src_action_deactivate(fib_entry, best_source);
871 fib_entry_src_action_activate(fib_entry, source);
873 else if (source > best_source)
876 * the new source loses. nothing to do here.
877 * the data from the source is saved in the path-list created
884 * the new source is one this entry already has.
885 * But the path-list was updated, which will contribute new forwarding,
888 fib_entry_src_action_deactivate(fib_entry, source);
889 fib_entry_src_action_activate(fib_entry, source);
892 fib_entry_post_update_actions(fib_entry, source, bflags);
896 * fib_entry_path_remove
898 * remove a path from the entry.
899 * return the fib_entry's index if it is still present, INVALID otherwise.
902 fib_entry_path_remove (fib_node_index_t fib_entry_index,
904 const fib_route_path_t *rpath)
906 fib_entry_src_flag_t sflag;
907 fib_source_t best_source;
908 fib_entry_flag_t bflags;
909 fib_entry_t *fib_entry;
910 fib_entry_src_t *bsrc;
912 ASSERT(1 == vec_len(rpath));
914 fib_entry = fib_entry_get(fib_entry_index);
915 ASSERT(NULL != fib_entry);
917 bsrc = fib_entry_get_best_src_i(fib_entry);
918 best_source = fib_entry_src_get_source(bsrc);
919 bflags = fib_entry_src_get_flags(bsrc);
921 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
924 * if the path list for the source passed is invalid,
925 * then we need to create a new one. else we are updating
928 if (source < best_source )
931 * Que! removing a path from a source that is better than the
932 * one this entry is using.
936 else if (source > best_source )
939 * the source is not the best. nothing to do.
941 return (FIB_ENTRY_SRC_FLAG_ADDED);
946 * removing a path from the path-list we were using.
948 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
951 * the last path from the source was removed.
952 * fallback to lower source
954 bsrc = fib_entry_get_best_src_i(fib_entry);
955 best_source = fib_entry_src_get_source(bsrc);
957 if (FIB_SOURCE_MAX == best_source) {
959 * no more sources left. this entry is toast.
961 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
964 fib_entry_src_action_uninstall(fib_entry);
966 return (FIB_ENTRY_SRC_FLAG_NONE);
970 fib_entry_src_action_activate(fib_entry, best_source);
971 source = best_source;
977 * re-install the new forwarding information
979 fib_entry_src_action_deactivate(fib_entry, source);
980 fib_entry_src_action_activate(fib_entry, source);
984 fib_entry_post_update_actions(fib_entry, source, bflags);
989 return (FIB_ENTRY_SRC_FLAG_ADDED);
993 * fib_entry_special_remove
995 * remove a special source from the entry.
996 * return the fib_entry's index if it is still present, INVALID otherwise.
999 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1000 fib_source_t source)
1002 fib_entry_src_flag_t sflag;
1003 fib_source_t best_source;
1004 fib_entry_flag_t bflags;
1005 fib_entry_t *fib_entry;
1006 fib_entry_src_t *bsrc;
1008 fib_entry = fib_entry_get(fib_entry_index);
1009 ASSERT(NULL != fib_entry);
1011 bsrc = fib_entry_get_best_src_i(fib_entry);
1012 best_source = fib_entry_src_get_source(bsrc);
1013 bflags = fib_entry_src_get_flags(bsrc);
1015 sflag = fib_entry_src_action_remove(fib_entry, source);
1018 * if the path list for the source passed is invalid,
1019 * then we need to create a new one. else we are updating
1022 if (source < best_source )
1025 * Que! removing a path from a source that is better than the
1026 * one this entry is using. This can only mean it is a source
1027 * this prefix does not have.
1029 return (FIB_ENTRY_SRC_FLAG_ADDED);
1031 else if (source > best_source ) {
1033 * the source is not the best. nothing to do.
1035 return (FIB_ENTRY_SRC_FLAG_ADDED);
1039 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1042 * the source was removed. use the next best.
1044 bsrc = fib_entry_get_best_src_i(fib_entry);
1045 best_source = fib_entry_src_get_source(bsrc);
1047 if (FIB_SOURCE_MAX == best_source) {
1049 * no more sources left. this entry is toast.
1051 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
1054 fib_entry_src_action_uninstall(fib_entry);
1056 return (FIB_ENTRY_SRC_FLAG_NONE);
1060 fib_entry_src_action_activate(fib_entry, best_source);
1061 source = best_source;
1067 * re-install the new forwarding information
1069 fib_entry_src_action_reactivate(fib_entry, source);
1073 fib_entry_post_update_actions(fib_entry, source, bflags);
1076 * still have sources
1078 return (FIB_ENTRY_SRC_FLAG_ADDED);
1084 * The source is withdrawing all the paths it provided
1086 fib_entry_src_flag_t
1087 fib_entry_delete (fib_node_index_t fib_entry_index,
1088 fib_source_t source)
1090 return (fib_entry_special_remove(fib_entry_index, source));
1096 * The source has provided a new set of paths that will replace the old.
1099 fib_entry_update (fib_node_index_t fib_entry_index,
1100 fib_source_t source,
1101 fib_entry_flag_t flags,
1102 const fib_route_path_t *paths)
1104 fib_source_t best_source;
1105 fib_entry_flag_t bflags;
1106 fib_entry_t *fib_entry;
1107 fib_entry_src_t *bsrc;
1109 fib_entry = fib_entry_get(fib_entry_index);
1110 ASSERT(NULL != fib_entry);
1112 bsrc = fib_entry_get_best_src_i(fib_entry);
1113 best_source = fib_entry_src_get_source(bsrc);
1114 bflags = fib_entry_src_get_flags(bsrc);
1116 fib_entry_src_action_path_swap(fib_entry,
1121 * handle possible realloc's by refetching the pointer
1123 fib_entry = fib_entry_get(fib_entry_index);
1126 * if the path list for the source passed is invalid,
1127 * then we need to create a new one. else we are updating
1130 if (source < best_source)
1133 * we have a new winning source.
1135 fib_entry_src_action_deactivate(fib_entry, best_source);
1136 fib_entry_src_action_activate(fib_entry, source);
1138 else if (source > best_source) {
1140 * the new source loses. nothing to do here.
1141 * the data from the source is saved in the path-list created
1148 * the new source is one this entry already has.
1149 * But the path-list was updated, which will contribute new forwarding,
1152 fib_entry_src_action_deactivate(fib_entry, source);
1153 fib_entry_src_action_activate(fib_entry, source);
1156 fib_entry_post_update_actions(fib_entry, source, bflags);
1161 * fib_entry_cover_changed
1163 * this entry is tracking its cover and that cover has changed.
1166 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1168 fib_entry_src_cover_res_t res = {
1170 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1172 fib_source_t source, best_source;
1173 fib_entry_flag_t bflags;
1174 fib_entry_t *fib_entry;
1175 fib_entry_src_t *esrc;
1178 bflags = FIB_ENTRY_FLAG_NONE;
1179 best_source = FIB_SOURCE_FIRST;
1180 fib_entry = fib_entry_get(fib_entry_index);
1182 fib_attached_export_cover_change(fib_entry);
1185 * propagate the notificuation to each of the added sources
1188 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1193 * only the best source gets to set the back walk flags
1195 res = fib_entry_src_action_cover_change(fib_entry, source);
1196 bflags = fib_entry_src_get_flags(esrc);
1197 best_source = fib_entry_src_get_source(esrc);
1201 fib_entry_src_action_cover_change(fib_entry, source);
1208 fib_entry_src_action_reactivate(fib_entry,
1209 fib_entry_src_get_source(
1210 fib_entry_get_best_src_i(fib_entry)));
1211 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1215 fib_entry_src_action_uninstall(fib_entry);
1218 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1221 * time for walkies fido.
1223 fib_node_back_walk_ctx_t bw_ctx = {
1224 .fnbw_reason = res.bw_reason,
1227 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1232 * fib_entry_cover_updated
1234 * this entry is tracking its cover and that cover has been updated
1235 * (i.e. its forwarding information has changed).
1238 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1240 fib_entry_src_cover_res_t res = {
1242 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1244 fib_source_t source, best_source;
1245 fib_entry_flag_t bflags;
1246 fib_entry_t *fib_entry;
1247 fib_entry_src_t *esrc;
1250 bflags = FIB_ENTRY_FLAG_NONE;
1251 best_source = FIB_SOURCE_FIRST;
1252 fib_entry = fib_entry_get(fib_entry_index);
1254 fib_attached_export_cover_update(fib_entry);
1257 * propagate the notificuation to each of the added sources
1260 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1265 * only the best source gets to set the back walk flags
1267 res = fib_entry_src_action_cover_update(fib_entry, source);
1268 bflags = fib_entry_src_get_flags(esrc);
1269 best_source = fib_entry_src_get_source(esrc);
1273 fib_entry_src_action_cover_update(fib_entry, source);
1280 fib_entry_src_action_reactivate(fib_entry,
1281 fib_entry_src_get_source(
1282 fib_entry_get_best_src_i(fib_entry)));
1283 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1287 fib_entry_src_action_uninstall(fib_entry);
1290 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1293 * time for walkies fido.
1295 fib_node_back_walk_ctx_t bw_ctx = {
1296 .fnbw_reason = res.bw_reason,
1299 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1304 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1305 fib_node_index_t **entry_indicies)
1307 fib_entry_t *fib_entry;
1308 int was_looped, is_looped;
1310 fib_entry = fib_entry_get(entry_index);
1312 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1314 fib_node_index_t *entries = *entry_indicies;
1316 vec_add1(entries, entry_index);
1317 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1318 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1321 *entry_indicies = entries;
1323 if (!!was_looped != !!is_looped)
1326 * re-evaluate all the entry's forwarding
1327 * NOTE: this is an inplace modify
1329 fib_entry_delegate_type_t fdt;
1330 fib_entry_delegate_t *fed;
1332 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1334 fib_entry_src_mk_lb(fib_entry,
1335 fib_entry_get_best_src_i(fib_entry),
1336 fib_entry_delegate_type_to_chain_type(fdt),
1344 * the entry is currently not linked to a path-list. this happens
1345 * when it is this entry that is re-linking path-lists and has thus
1355 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1357 fib_entry_t *fib_entry;
1359 fib_entry = fib_entry_get(entry_index);
1361 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1365 fib_entry_get_best_source (fib_node_index_t entry_index)
1367 fib_entry_t *fib_entry;
1368 fib_entry_src_t *bsrc;
1370 fib_entry = fib_entry_get(entry_index);
1372 bsrc = fib_entry_get_best_src_i(fib_entry);
1373 return (fib_entry_src_get_source(bsrc));
1377 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
1381 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1383 fib_entry_delegate_t *fed;
1384 fib_entry_t *fib_entry;
1386 fib_entry = fib_entry_get(fib_entry_index);
1388 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1393 * no BFD tracking - consider it resolved.
1400 * defer to the state of the BFD tracking
1402 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1407 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1408 flow_hash_config_t hash_config)
1410 fib_entry_t *fib_entry;
1412 fib_entry = fib_entry_get(fib_entry_index);
1415 * pass the hash-config on to the load-balance object where it is cached.
1416 * we can ignore LBs in the delegate chains, since they will not be of the
1417 * correct protocol type (i.e. they are not IP)
1418 * There's no way, nor need, to change the hash config for MPLS.
1420 if (dpo_id_is_valid(&fib_entry->fe_lb))
1424 ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1426 lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1429 * atomic update for packets in flight
1431 lb->lb_hash_config = hash_config;
1436 fib_ip4_address_compare (const ip4_address_t * a1,
1437 const ip4_address_t * a2)
1440 * IP addresses are unsiged ints. the return value here needs to be signed
1441 * a simple subtraction won't cut it.
1442 * If the addresses are the same, the sort order is undefiend, so phoey.
1444 return ((clib_net_to_host_u32(a1->data_u32) >
1445 clib_net_to_host_u32(a2->data_u32) ) ?
1450 fib_ip6_address_compare (const ip6_address_t * a1,
1451 const ip6_address_t * a2)
1454 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1456 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1457 clib_net_to_host_u16 (a2->as_u16[i]));
1465 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1466 fib_node_index_t fib_entry_index2)
1468 fib_entry_t *fib_entry1, *fib_entry2;
1471 fib_entry1 = fib_entry_get(fib_entry_index1);
1472 fib_entry2 = fib_entry_get(fib_entry_index2);
1474 switch (fib_entry1->fe_prefix.fp_proto)
1476 case FIB_PROTOCOL_IP4:
1477 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1478 &fib_entry2->fe_prefix.fp_addr.ip4);
1480 case FIB_PROTOCOL_IP6:
1481 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1482 &fib_entry2->fe_prefix.fp_addr.ip6);
1484 case FIB_PROTOCOL_MPLS:
1485 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1489 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1495 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1501 fib_entry_cmp_for_sort (void *i1, void *i2)
1503 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1505 return (fib_entry_cmp(*fib_entry_index1,
1506 *fib_entry_index2));
1510 fib_entry_lock (fib_node_index_t fib_entry_index)
1512 fib_entry_t *fib_entry;
1514 fib_entry = fib_entry_get(fib_entry_index);
1516 fib_node_lock(&fib_entry->fe_node);
1520 fib_entry_unlock (fib_node_index_t fib_entry_index)
1522 fib_entry_t *fib_entry;
1524 fib_entry = fib_entry_get(fib_entry_index);
1526 fib_node_unlock(&fib_entry->fe_node);
1530 fib_entry_module_init (void)
1532 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1536 fib_entry_encode (fib_node_index_t fib_entry_index,
1537 fib_route_path_encode_t **api_rpaths)
1539 fib_entry_t *fib_entry;
1541 fib_entry = fib_entry_get(fib_entry_index);
1542 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1544 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1549 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1552 fib_entry_t *fib_entry;
1554 fib_entry = fib_entry_get(fib_entry_index);
1555 *pfx = fib_entry->fe_prefix;
1559 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1561 fib_entry_t *fib_entry;
1563 fib_entry = fib_entry_get(fib_entry_index);
1565 return (fib_entry->fe_fib_index);
1569 fib_entry_pool_size (void)
1571 return (pool_elts(fib_entry_pool));
1574 static clib_error_t *
1575 show_fib_entry_command (vlib_main_t * vm,
1576 unformat_input_t * input,
1577 vlib_cli_command_t * cmd)
1579 fib_node_index_t fei;
1581 if (unformat (input, "%d", &fei))
1584 * show one in detail
1586 if (!pool_is_free_index(fib_entry_pool, fei))
1588 vlib_cli_output (vm, "%d@%U",
1590 format_fib_entry, fei,
1591 FIB_ENTRY_FORMAT_DETAIL2);
1595 vlib_cli_output (vm, "entry %d invalid", fei);
1603 vlib_cli_output (vm, "FIB Entries:");
1604 pool_foreach_index(fei, fib_entry_pool,
1606 vlib_cli_output (vm, "%d@%U",
1608 format_fib_entry, fei,
1609 FIB_ENTRY_FORMAT_BRIEF);
1616 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1617 .path = "show fib entry",
1618 .function = show_fib_entry_command,
1619 .short_help = "show fib entry",