2 * Copyright (c) 2016 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 #include <vlib/vlib.h>
17 #include <vnet/ip/format.h>
18 #include <vnet/ip/lookup.h>
19 #include <vnet/adj/adj.h>
20 #include <vnet/dpo/load_balance.h>
21 #include <vnet/dpo/drop_dpo.h>
23 #include <vnet/fib/fib_entry.h>
24 #include <vnet/fib/fib_walk.h>
25 #include <vnet/fib/fib_entry_src.h>
26 #include <vnet/fib/fib_entry_cover.h>
27 #include <vnet/fib/fib_table.h>
28 #include <vnet/fib/fib_internal.h>
29 #include <vnet/fib/fib_attached_export.h>
30 #include <vnet/fib/fib_path_ext.h>
33 * Array of strings/names for the FIB sources
35 static const char *fib_source_names[] = FIB_SOURCES;
36 static const char *fib_attribute_names[] = FIB_ENTRY_ATTRIBUTES;
39 * Pool for all fib_entries
41 static fib_entry_t *fib_entry_pool;
44 fib_entry_get (fib_node_index_t index)
46 return (pool_elt_at_index(fib_entry_pool, index));
50 fib_entry_get_node (fib_node_index_t index)
52 return ((fib_node_t*)fib_entry_get(index));
56 fib_entry_get_index (const fib_entry_t * fib_entry)
58 return (fib_entry - fib_entry_pool);
62 fib_entry_get_proto (const fib_entry_t * fib_entry)
64 return (fib_entry->fe_prefix.fp_proto);
67 fib_forward_chain_type_t
68 fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
70 switch (fib_entry->fe_prefix.fp_proto)
72 case FIB_PROTOCOL_IP4:
73 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
74 case FIB_PROTOCOL_IP6:
75 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
76 case FIB_PROTOCOL_MPLS:
77 if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
78 return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
80 return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
83 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
87 format_fib_entry (u8 * s, va_list * args)
89 fib_forward_chain_type_t fct;
90 fib_entry_attribute_t attr;
91 fib_entry_t *fib_entry;
97 fei = va_arg (*args, fib_node_index_t);
98 level = va_arg (*args, int);
99 fib_entry = fib_entry_get(fei);
101 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
103 if (level >= FIB_ENTRY_FORMAT_DETAIL)
105 s = format (s, " fib:%d", fib_entry->fe_fib_index);
106 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
107 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
109 FOR_EACH_SRC_ADDED(fib_entry, src, source,
111 s = format (s, "\n src:%s ",
112 fib_source_names[source]);
113 s = fib_entry_src_format(fib_entry, source, s);
114 s = format (s, " refs:%d ", src->fes_ref_count);
115 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
116 s = format(s, "flags:");
117 FOR_EACH_FIB_ATTRIBUTE(attr) {
118 if ((1<<attr) & src->fes_entry_flags) {
119 s = format (s, "%s,", fib_attribute_names[attr]);
123 s = format (s, "\n");
124 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
126 s = fib_path_list_format(src->fes_pl, s);
128 s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
131 s = format (s, "\n forwarding: ");
135 s = format (s, "\n");
138 fct = fib_entry_get_default_chain_type(fib_entry);
140 if (!dpo_id_is_valid(&fib_entry->fe_lb))
142 s = format (s, " UNRESOLVED\n");
147 s = format(s, " %U-chain\n %U",
148 format_fib_forw_chain_type, fct,
154 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
156 fib_entry_delegate_type_t fdt;
157 fib_entry_delegate_t *fed;
159 s = format (s, " Delegates:\n");
160 FOR_EACH_DELEGATE(fib_entry, fdt, fed,
162 s = format(s, " %U\n", format_fib_entry_deletegate, fed);
167 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
169 s = format(s, " Children:");
170 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
177 fib_entry_from_fib_node (fib_node_t *node)
180 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
182 return ((fib_entry_t*)node);
186 fib_entry_last_lock_gone (fib_node_t *node)
188 fib_entry_delegate_type_t fdt;
189 fib_entry_delegate_t *fed;
190 fib_entry_t *fib_entry;
192 fib_entry = fib_entry_from_fib_node(node);
194 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
196 dpo_reset(&fed->fd_dpo);
197 fib_entry_delegate_remove(fib_entry, fdt);
200 FIB_ENTRY_DBG(fib_entry, "last-lock");
202 fib_node_deinit(&fib_entry->fe_node);
203 // FIXME -RR Backwalk
205 ASSERT(0 == vec_len(fib_entry->fe_delegates));
206 vec_free(fib_entry->fe_delegates);
207 vec_free(fib_entry->fe_srcs);
208 pool_put(fib_entry_pool, fib_entry);
211 static fib_entry_src_t*
212 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
214 fib_entry_src_t *bsrc;
217 * the enum of sources is deliberately arranged in priority order
219 if (0 == vec_len(fib_entry->fe_srcs))
225 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
232 fib_entry_src_get_source (const fib_entry_src_t *esrc)
236 return (esrc->fes_src);
238 return (FIB_SOURCE_MAX);
241 static fib_entry_flag_t
242 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
246 return (esrc->fes_entry_flags);
248 return (FIB_ENTRY_FLAG_NONE);
252 fib_entry_get_flags (fib_node_index_t fib_entry_index)
254 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
258 * fib_entry_back_walk_notify
260 * A back walk has reach this entry.
262 static fib_node_back_walk_rc_t
263 fib_entry_back_walk_notify (fib_node_t *node,
264 fib_node_back_walk_ctx_t *ctx)
266 fib_entry_t *fib_entry;
268 fib_entry = fib_entry_from_fib_node(node);
270 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
271 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
272 FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason ||
273 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
274 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
275 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
277 fib_entry_src_action_reactivate(fib_entry,
278 fib_entry_get_best_source(
279 fib_entry_get_index(fib_entry)));
283 * all other walk types can be reclassifed to a re-evaluate to
284 * all recursive dependents.
285 * By reclassifying we ensure that should any of these walk types meet
286 * they can be merged.
288 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
291 * ... and nothing is forced sync from now on.
293 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
296 * propagate the backwalk further if we haven't already reached the
299 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
300 fib_entry_get_index(fib_entry),
303 return (FIB_NODE_BACK_WALK_CONTINUE);
307 fib_entry_show_memory (void)
309 u32 n_srcs = 0, n_exts = 0;
310 fib_entry_src_t *esrc;
313 fib_show_memory_usage("Entry",
314 pool_elts(fib_entry_pool),
315 pool_len(fib_entry_pool),
316 sizeof(fib_entry_t));
318 pool_foreach(entry, fib_entry_pool,
320 n_srcs += vec_len(entry->fe_srcs);
321 vec_foreach(esrc, entry->fe_srcs)
323 n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
327 fib_show_memory_usage("Entry Source",
328 n_srcs, n_srcs, sizeof(fib_entry_src_t));
329 fib_show_memory_usage("Entry Path-Extensions",
331 sizeof(fib_path_ext_t));
335 * The FIB path-list's graph node virtual function table
337 static const fib_node_vft_t fib_entry_vft = {
338 .fnv_get = fib_entry_get_node,
339 .fnv_last_lock = fib_entry_last_lock_gone,
340 .fnv_back_walk = fib_entry_back_walk_notify,
341 .fnv_mem_show = fib_entry_show_memory,
345 * @brief Contribute the set of Adjacencies that this entry forwards with
346 * to build the uRPF list of its children
349 fib_entry_contribute_urpf (fib_node_index_t entry_index,
352 fib_entry_t *fib_entry;
354 fib_entry = fib_entry_get(entry_index);
356 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
360 * If the client is request a chain for multicast forwarding then swap
361 * the chain type to one that can provide such transport.
363 static fib_forward_chain_type_t
364 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
368 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
369 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
371 * we can only transport IP multicast packets if there is an
374 fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
376 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
377 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
378 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
379 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
380 case FIB_FORW_CHAIN_TYPE_ETHERNET:
381 case FIB_FORW_CHAIN_TYPE_NSH:
389 * fib_entry_contribute_forwarding
391 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
394 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
395 fib_forward_chain_type_t fct,
398 fib_entry_delegate_t *fed;
399 fib_entry_t *fib_entry;
401 fib_entry = fib_entry_get(fib_entry_index);
404 * mfib children ask for mcast chains. fix these to the appropriate ucast types.
406 fct = fib_entry_chain_type_mcast_to_ucast(fct);
408 if (fct == fib_entry_get_default_chain_type(fib_entry))
410 dpo_copy(dpo, &fib_entry->fe_lb);
414 fed = fib_entry_delegate_get(fib_entry,
415 fib_entry_chain_type_to_delegate_type(fct));
419 fed = fib_entry_delegate_find_or_add(
421 fib_entry_chain_type_to_delegate_type(fct));
423 * on-demand create eos/non-eos.
424 * There is no on-demand delete because:
425 * - memory versus complexity & reliability:
426 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
427 * then up on the right trigger is more code. i favour the latter.
429 fib_entry_src_mk_lb(fib_entry,
430 fib_entry_get_best_src_i(fib_entry),
435 dpo_copy(dpo, &fed->fd_dpo);
438 * don't allow the special index indicating replicate.vs.load-balance
439 * to escape to the clients
441 dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
445 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
447 fib_forward_chain_type_t fct;
448 fib_entry_t *fib_entry;
450 fib_entry = fib_entry_get(fib_entry_index);
451 fct = fib_entry_get_default_chain_type(fib_entry);
453 ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
454 fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
456 return (&fib_entry->fe_lb);
460 fib_entry_get_adj (fib_node_index_t fib_entry_index)
464 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
466 if (dpo_id_is_valid(dpo))
468 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
472 return (dpo->dpoi_index);
475 return (ADJ_INDEX_INVALID);
479 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
481 fib_entry_t *fib_entry;
483 fib_entry = fib_entry_get(fib_entry_index);
485 return (fib_entry->fe_parent);
489 fib_entry_child_add (fib_node_index_t fib_entry_index,
490 fib_node_type_t child_type,
491 fib_node_index_t child_index)
493 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
500 fib_entry_child_remove (fib_node_index_t fib_entry_index,
503 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
507 if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
511 * if there are no children left then there is no reason to keep
512 * the non-default forwarding chains. those chains are built only
513 * because the children want them.
515 fib_entry_delegate_type_t fdt;
516 fib_entry_delegate_t *fed;
517 fib_entry_t *fib_entry;
519 fib_entry = fib_entry_get(fib_entry_index);
521 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
523 dpo_reset(&fed->fd_dpo);
524 fib_entry_delegate_remove(fib_entry, fdt);
530 fib_entry_alloc (u32 fib_index,
531 const fib_prefix_t *prefix,
532 fib_node_index_t *fib_entry_index)
534 fib_entry_t *fib_entry;
537 pool_get(fib_entry_pool, fib_entry);
538 memset(fib_entry, 0, sizeof(*fib_entry));
540 fib_node_init(&fib_entry->fe_node,
541 FIB_NODE_TYPE_ENTRY);
543 fib_entry->fe_fib_index = fib_index;
546 * the one time we need to update the const prefix is when
547 * the entry is first created
549 fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
552 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
555 if (MPLS_NON_EOS == fep->fp_eos)
557 fep->fp_payload_proto = DPO_PROTO_MPLS;
559 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
562 dpo_reset(&fib_entry->fe_lb);
564 *fib_entry_index = fib_entry_get_index(fib_entry);
566 FIB_ENTRY_DBG(fib_entry, "alloc");
572 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
574 fib_entry_flag_t old_flags)
576 fib_node_index_t fei;
579 * save the index so we can recover from pool reallocs
581 fei = fib_entry_get_index(fib_entry);
584 * handle changes to attached export for import entries
586 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
587 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
589 if (!was_import && is_import)
592 * transition from not exported to exported
596 * there is an assumption here that the entry resolves via only
597 * one interface and that it is the cross VRF interface.
599 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
601 fib_attached_export_import(fib_entry,
602 fib_table_get_index_for_sw_if_index(
603 fib_entry_get_proto(fib_entry),
606 else if (was_import && !is_import)
609 * transition from exported to not exported
611 fib_attached_export_purge(fib_entry);
615 * no change. nothing to do.
619 * reload the entry address post possible pool realloc
621 fib_entry = fib_entry_get(fei);
624 * handle changes to attached export for export entries
626 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
627 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
629 if (!was_attached && is_attached)
632 * transition to attached. time to export
642 fib_entry_post_install_actions (fib_entry_t *fib_entry,
644 fib_entry_flag_t old_flags)
646 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
649 fib_entry_src_action_installed(fib_entry, source);
653 fib_entry_create (u32 fib_index,
654 const fib_prefix_t *prefix,
656 fib_entry_flag_t flags,
657 const fib_route_path_t *paths)
659 fib_node_index_t fib_entry_index;
660 fib_entry_t *fib_entry;
662 ASSERT(0 < vec_len(paths));
664 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
667 * since this is a new entry create, we don't need to check for winning
668 * sources - there is only one.
670 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
673 fib_entry_get_proto(fib_entry))));
674 fib_entry_src_action_path_swap(fib_entry,
679 * handle possible realloc's by refetching the pointer
681 fib_entry = fib_entry_get(fib_entry_index);
682 fib_entry_src_action_activate(fib_entry, source);
684 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
686 return (fib_entry_index);
690 fib_entry_create_special (u32 fib_index,
691 const fib_prefix_t *prefix,
693 fib_entry_flag_t flags,
696 fib_node_index_t fib_entry_index;
697 fib_entry_t *fib_entry;
700 * create and initiliase the new enty
702 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
705 * create the path-list
707 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
708 fib_entry_src_action_activate(fib_entry, source);
710 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
712 return (fib_entry_index);
716 fib_entry_post_update_actions (fib_entry_t *fib_entry,
718 fib_entry_flag_t old_flags)
721 * backwalk to children to inform then of the change to forwarding.
723 fib_node_back_walk_ctx_t bw_ctx = {
724 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
727 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
730 * then inform any covered prefixes
732 fib_entry_cover_update_notify(fib_entry);
734 fib_entry_post_install_actions(fib_entry, source, old_flags);
738 fib_entry_source_change (fib_entry_t *fib_entry,
739 fib_source_t best_source,
740 fib_source_t new_source,
741 fib_entry_flag_t old_flags)
744 * if the path list for the source passed is invalid,
745 * then we need to create a new one. else we are updating
748 if (new_source < best_source)
751 * we have a new winning source.
753 fib_entry_src_action_deactivate(fib_entry, best_source);
754 fib_entry_src_action_activate(fib_entry, new_source);
756 else if (new_source > best_source)
759 * the new source loses. nothing to do here.
760 * the data from the source is saved in the path-list created
767 * the new source is one this entry already has.
768 * But the path-list was updated, which will contribute new forwarding,
771 fib_entry_src_action_deactivate(fib_entry, new_source);
772 fib_entry_src_action_activate(fib_entry, new_source);
775 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
779 fib_entry_special_add (fib_node_index_t fib_entry_index,
781 fib_entry_flag_t flags,
784 fib_source_t best_source;
785 fib_entry_flag_t bflags;
786 fib_entry_t *fib_entry;
787 fib_entry_src_t *bsrc;
789 fib_entry = fib_entry_get(fib_entry_index);
791 bsrc = fib_entry_get_best_src_i(fib_entry);
792 best_source = fib_entry_src_get_source(bsrc);
793 bflags = fib_entry_src_get_flags(bsrc);
795 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
796 fib_entry_source_change(fib_entry, best_source, source, bflags);
800 fib_entry_special_update (fib_node_index_t fib_entry_index,
802 fib_entry_flag_t flags,
805 fib_source_t best_source;
806 fib_entry_flag_t bflags;
807 fib_entry_t *fib_entry;
808 fib_entry_src_t *bsrc;
810 fib_entry = fib_entry_get(fib_entry_index);
812 bsrc = fib_entry_get_best_src_i(fib_entry);
813 best_source = fib_entry_src_get_source(bsrc);
814 bflags = fib_entry_src_get_flags(bsrc);
816 fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
817 fib_entry_source_change(fib_entry, best_source, source, bflags);
822 fib_entry_path_add (fib_node_index_t fib_entry_index,
824 fib_entry_flag_t flags,
825 const fib_route_path_t *rpath)
827 fib_source_t best_source;
828 fib_entry_flag_t bflags;
829 fib_entry_t *fib_entry;
830 fib_entry_src_t *bsrc;
832 ASSERT(1 == vec_len(rpath));
834 fib_entry = fib_entry_get(fib_entry_index);
835 ASSERT(NULL != fib_entry);
837 bsrc = fib_entry_get_best_src_i(fib_entry);
838 best_source = fib_entry_src_get_source(bsrc);
839 bflags = fib_entry_src_get_flags(bsrc);
841 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
844 * if the path list for the source passed is invalid,
845 * then we need to create a new one. else we are updating
848 if (source < best_source)
851 * we have a new winning source.
853 fib_entry_src_action_deactivate(fib_entry, best_source);
854 fib_entry_src_action_activate(fib_entry, source);
856 else if (source > best_source)
859 * the new source loses. nothing to do here.
860 * the data from the source is saved in the path-list created
867 * the new source is one this entry already has.
868 * But the path-list was updated, which will contribute new forwarding,
871 fib_entry_src_action_deactivate(fib_entry, source);
872 fib_entry_src_action_activate(fib_entry, source);
875 fib_entry_post_update_actions(fib_entry, source, bflags);
879 * fib_entry_path_remove
881 * remove a path from the entry.
882 * return the fib_entry's index if it is still present, INVALID otherwise.
885 fib_entry_path_remove (fib_node_index_t fib_entry_index,
887 const fib_route_path_t *rpath)
889 fib_entry_src_flag_t sflag;
890 fib_source_t best_source;
891 fib_entry_flag_t bflags;
892 fib_entry_t *fib_entry;
893 fib_entry_src_t *bsrc;
895 ASSERT(1 == vec_len(rpath));
897 fib_entry = fib_entry_get(fib_entry_index);
898 ASSERT(NULL != fib_entry);
900 bsrc = fib_entry_get_best_src_i(fib_entry);
901 best_source = fib_entry_src_get_source(bsrc);
902 bflags = fib_entry_src_get_flags(bsrc);
904 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
907 * if the path list for the source passed is invalid,
908 * then we need to create a new one. else we are updating
911 if (source < best_source )
914 * Que! removing a path from a source that is better than the
915 * one this entry is using.
919 else if (source > best_source )
922 * the source is not the best. nothing to do.
924 return (FIB_ENTRY_SRC_FLAG_ADDED);
929 * removing a path from the path-list we were using.
931 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
934 * the last path from the source was removed.
935 * fallback to lower source
937 bsrc = fib_entry_get_best_src_i(fib_entry);
938 best_source = fib_entry_src_get_source(bsrc);
940 if (FIB_SOURCE_MAX == best_source) {
942 * no more sources left. this entry is toast.
944 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
947 fib_entry_src_action_uninstall(fib_entry);
949 return (FIB_ENTRY_SRC_FLAG_NONE);
953 fib_entry_src_action_activate(fib_entry, best_source);
954 source = best_source;
960 * re-install the new forwarding information
962 fib_entry_src_action_deactivate(fib_entry, source);
963 fib_entry_src_action_activate(fib_entry, source);
967 fib_entry_post_update_actions(fib_entry, source, bflags);
972 return (FIB_ENTRY_SRC_FLAG_ADDED);
976 * fib_entry_special_remove
978 * remove a special source from the entry.
979 * return the fib_entry's index if it is still present, INVALID otherwise.
982 fib_entry_special_remove (fib_node_index_t fib_entry_index,
985 fib_entry_src_flag_t sflag;
986 fib_source_t best_source;
987 fib_entry_flag_t bflags;
988 fib_entry_t *fib_entry;
989 fib_entry_src_t *bsrc;
991 fib_entry = fib_entry_get(fib_entry_index);
992 ASSERT(NULL != fib_entry);
994 bsrc = fib_entry_get_best_src_i(fib_entry);
995 best_source = fib_entry_src_get_source(bsrc);
996 bflags = fib_entry_src_get_flags(bsrc);
998 sflag = fib_entry_src_action_remove(fib_entry, source);
1001 * if the path list for the source passed is invalid,
1002 * then we need to create a new one. else we are updating
1005 if (source < best_source )
1008 * Que! removing a path from a source that is better than the
1009 * one this entry is using. This can only mean it is a source
1010 * this prefix does not have.
1012 return (FIB_ENTRY_SRC_FLAG_ADDED);
1014 else if (source > best_source ) {
1016 * the source is not the best. nothing to do.
1018 return (FIB_ENTRY_SRC_FLAG_ADDED);
1022 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1025 * the source was removed. use the next best.
1027 bsrc = fib_entry_get_best_src_i(fib_entry);
1028 best_source = fib_entry_src_get_source(bsrc);
1030 if (FIB_SOURCE_MAX == best_source) {
1032 * no more sources left. this entry is toast.
1034 fib_entry = fib_entry_post_flag_update_actions(fib_entry,
1037 fib_entry_src_action_uninstall(fib_entry);
1039 return (FIB_ENTRY_SRC_FLAG_NONE);
1043 fib_entry_src_action_activate(fib_entry, best_source);
1044 source = best_source;
1050 * re-install the new forwarding information
1052 fib_entry_src_action_reactivate(fib_entry, source);
1056 fib_entry_post_update_actions(fib_entry, source, bflags);
1059 * still have sources
1061 return (FIB_ENTRY_SRC_FLAG_ADDED);
1067 * The source is withdrawing all the paths it provided
1069 fib_entry_src_flag_t
1070 fib_entry_delete (fib_node_index_t fib_entry_index,
1071 fib_source_t source)
1073 return (fib_entry_special_remove(fib_entry_index, source));
1079 * The source has provided a new set of paths that will replace the old.
1082 fib_entry_update (fib_node_index_t fib_entry_index,
1083 fib_source_t source,
1084 fib_entry_flag_t flags,
1085 const fib_route_path_t *paths)
1087 fib_source_t best_source;
1088 fib_entry_flag_t bflags;
1089 fib_entry_t *fib_entry;
1090 fib_entry_src_t *bsrc;
1092 fib_entry = fib_entry_get(fib_entry_index);
1093 ASSERT(NULL != fib_entry);
1095 bsrc = fib_entry_get_best_src_i(fib_entry);
1096 best_source = fib_entry_src_get_source(bsrc);
1097 bflags = fib_entry_src_get_flags(bsrc);
1099 fib_entry_src_action_path_swap(fib_entry,
1104 * handle possible realloc's by refetching the pointer
1106 fib_entry = fib_entry_get(fib_entry_index);
1109 * if the path list for the source passed is invalid,
1110 * then we need to create a new one. else we are updating
1113 if (source < best_source)
1116 * we have a new winning source.
1118 fib_entry_src_action_deactivate(fib_entry, best_source);
1119 fib_entry_src_action_activate(fib_entry, source);
1121 else if (source > best_source) {
1123 * the new source loses. nothing to do here.
1124 * the data from the source is saved in the path-list created
1131 * the new source is one this entry already has.
1132 * But the path-list was updated, which will contribute new forwarding,
1135 fib_entry_src_action_deactivate(fib_entry, source);
1136 fib_entry_src_action_activate(fib_entry, source);
1139 fib_entry_post_update_actions(fib_entry, source, bflags);
1144 * fib_entry_cover_changed
1146 * this entry is tracking its cover and that cover has changed.
1149 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1151 fib_entry_src_cover_res_t res = {
1153 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1155 fib_source_t source, best_source;
1156 fib_entry_flag_t bflags;
1157 fib_entry_t *fib_entry;
1158 fib_entry_src_t *esrc;
1161 bflags = FIB_ENTRY_FLAG_NONE;
1162 best_source = FIB_SOURCE_FIRST;
1163 fib_entry = fib_entry_get(fib_entry_index);
1165 fib_attached_export_cover_change(fib_entry);
1168 * propagate the notificuation to each of the added sources
1171 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1176 * only the best source gets to set the back walk flags
1178 res = fib_entry_src_action_cover_change(fib_entry, source);
1179 bflags = fib_entry_src_get_flags(esrc);
1180 best_source = fib_entry_src_get_source(esrc);
1184 fib_entry_src_action_cover_change(fib_entry, source);
1191 fib_entry_src_action_reactivate(fib_entry,
1192 fib_entry_src_get_source(
1193 fib_entry_get_best_src_i(fib_entry)));
1194 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1198 fib_entry_src_action_uninstall(fib_entry);
1201 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1204 * time for walkies fido.
1206 fib_node_back_walk_ctx_t bw_ctx = {
1207 .fnbw_reason = res.bw_reason,
1210 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1215 * fib_entry_cover_updated
1217 * this entry is tracking its cover and that cover has been updated
1218 * (i.e. its forwarding information has changed).
1221 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1223 fib_entry_src_cover_res_t res = {
1225 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1227 fib_source_t source, best_source;
1228 fib_entry_flag_t bflags;
1229 fib_entry_t *fib_entry;
1230 fib_entry_src_t *esrc;
1233 bflags = FIB_ENTRY_FLAG_NONE;
1234 best_source = FIB_SOURCE_FIRST;
1235 fib_entry = fib_entry_get(fib_entry_index);
1237 fib_attached_export_cover_update(fib_entry);
1240 * propagate the notificuation to each of the added sources
1243 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1248 * only the best source gets to set the back walk flags
1250 res = fib_entry_src_action_cover_update(fib_entry, source);
1251 bflags = fib_entry_src_get_flags(esrc);
1252 best_source = fib_entry_src_get_source(esrc);
1256 fib_entry_src_action_cover_update(fib_entry, source);
1263 fib_entry_src_action_reactivate(fib_entry,
1264 fib_entry_src_get_source(
1265 fib_entry_get_best_src_i(fib_entry)));
1266 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1270 fib_entry_src_action_uninstall(fib_entry);
1273 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1276 * time for walkies fido.
1278 fib_node_back_walk_ctx_t bw_ctx = {
1279 .fnbw_reason = res.bw_reason,
1282 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1287 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1288 fib_node_index_t **entry_indicies)
1290 fib_entry_t *fib_entry;
1291 int was_looped, is_looped;
1293 fib_entry = fib_entry_get(entry_index);
1295 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1297 fib_node_index_t *entries = *entry_indicies;
1299 vec_add1(entries, entry_index);
1300 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1301 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1304 *entry_indicies = entries;
1306 if (!!was_looped != !!is_looped)
1309 * re-evaluate all the entry's forwarding
1310 * NOTE: this is an inplace modify
1312 fib_entry_delegate_type_t fdt;
1313 fib_entry_delegate_t *fed;
1315 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1317 fib_entry_src_mk_lb(fib_entry,
1318 fib_entry_get_best_src_i(fib_entry),
1319 fib_entry_delegate_type_to_chain_type(fdt),
1327 * the entry is currently not linked to a path-list. this happens
1328 * when it is this entry that is re-linking path-lists and has thus
1338 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1340 fib_entry_t *fib_entry;
1342 fib_entry = fib_entry_get(entry_index);
1344 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1348 fib_entry_get_best_source (fib_node_index_t entry_index)
1350 fib_entry_t *fib_entry;
1351 fib_entry_src_t *bsrc;
1353 fib_entry = fib_entry_get(entry_index);
1355 bsrc = fib_entry_get_best_src_i(fib_entry);
1356 return (fib_entry_src_get_source(bsrc));
1360 * Return !0 is the entry is reoslved, i.e. will return a valid forwarding
1364 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1366 fib_entry_delegate_t *fed;
1367 fib_entry_t *fib_entry;
1369 fib_entry = fib_entry_get(fib_entry_index);
1371 fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1376 * no BFD tracking - resolved
1383 * defer to the state of the BFD tracking
1385 return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1390 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1391 flow_hash_config_t hash_config)
1393 fib_entry_t *fib_entry;
1395 fib_entry = fib_entry_get(fib_entry_index);
1398 * pass the hash-config on to the load-balance object where it is cached.
1399 * we can ignore LBs in the delegate chains, since they will not be of the
1400 * correct protocol type (i.e. they are not IP)
1401 * There's no way, nor need, to change the hash config for MPLS.
1403 if (dpo_id_is_valid(&fib_entry->fe_lb))
1407 ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1409 lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1412 * atomic update for packets in flight
1414 lb->lb_hash_config = hash_config;
1419 fib_ip4_address_compare (const ip4_address_t * a1,
1420 const ip4_address_t * a2)
1423 * IP addresses are unsiged ints. the return value here needs to be signed
1424 * a simple subtraction won't cut it.
1425 * If the addresses are the same, the sort order is undefiend, so phoey.
1427 return ((clib_net_to_host_u32(a1->data_u32) >
1428 clib_net_to_host_u32(a2->data_u32) ) ?
1433 fib_ip6_address_compare (const ip6_address_t * a1,
1434 const ip6_address_t * a2)
1437 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1439 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1440 clib_net_to_host_u16 (a2->as_u16[i]));
1448 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1449 fib_node_index_t fib_entry_index2)
1451 fib_entry_t *fib_entry1, *fib_entry2;
1454 fib_entry1 = fib_entry_get(fib_entry_index1);
1455 fib_entry2 = fib_entry_get(fib_entry_index2);
1457 switch (fib_entry1->fe_prefix.fp_proto)
1459 case FIB_PROTOCOL_IP4:
1460 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1461 &fib_entry2->fe_prefix.fp_addr.ip4);
1463 case FIB_PROTOCOL_IP6:
1464 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1465 &fib_entry2->fe_prefix.fp_addr.ip6);
1467 case FIB_PROTOCOL_MPLS:
1468 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1472 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1478 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1484 fib_entry_cmp_for_sort (void *i1, void *i2)
1486 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1488 return (fib_entry_cmp(*fib_entry_index1,
1489 *fib_entry_index2));
1493 fib_entry_lock (fib_node_index_t fib_entry_index)
1495 fib_entry_t *fib_entry;
1497 fib_entry = fib_entry_get(fib_entry_index);
1499 fib_node_lock(&fib_entry->fe_node);
1503 fib_entry_unlock (fib_node_index_t fib_entry_index)
1505 fib_entry_t *fib_entry;
1507 fib_entry = fib_entry_get(fib_entry_index);
1509 fib_node_unlock(&fib_entry->fe_node);
1513 fib_entry_module_init (void)
1515 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1519 fib_entry_encode (fib_node_index_t fib_entry_index,
1520 fib_route_path_encode_t **api_rpaths)
1522 fib_entry_t *fib_entry;
1524 fib_entry = fib_entry_get(fib_entry_index);
1525 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1527 fib_path_list_walk(fib_entry->fe_parent, fib_path_encode, api_rpaths);
1532 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1535 fib_entry_t *fib_entry;
1537 fib_entry = fib_entry_get(fib_entry_index);
1538 *pfx = fib_entry->fe_prefix;
1542 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1544 fib_entry_t *fib_entry;
1546 fib_entry = fib_entry_get(fib_entry_index);
1548 return (fib_entry->fe_fib_index);
1552 fib_entry_pool_size (void)
1554 return (pool_elts(fib_entry_pool));
1557 static clib_error_t *
1558 show_fib_entry_command (vlib_main_t * vm,
1559 unformat_input_t * input,
1560 vlib_cli_command_t * cmd)
1562 fib_node_index_t fei;
1564 if (unformat (input, "%d", &fei))
1567 * show one in detail
1569 if (!pool_is_free_index(fib_entry_pool, fei))
1571 vlib_cli_output (vm, "%d@%U",
1573 format_fib_entry, fei,
1574 FIB_ENTRY_FORMAT_DETAIL2);
1578 vlib_cli_output (vm, "entry %d invalid", fei);
1586 vlib_cli_output (vm, "FIB Entries:");
1587 pool_foreach_index(fei, fib_entry_pool,
1589 vlib_cli_output (vm, "%d@%U",
1591 format_fib_entry, fei,
1592 FIB_ENTRY_FORMAT_BRIEF);
1599 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1600 .path = "show fib entry",
1601 .function = show_fib_entry_command,
1602 .short_help = "show fib entry",