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 * @brief Turn the chain type requested by the client into the one they
71 static fib_forward_chain_type_t
72 fib_entry_chain_type_fixup (const fib_entry_t *entry,
73 fib_forward_chain_type_t fct)
75 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS == fct)
78 * The EOS chain is a tricky since one cannot know the adjacency
79 * to link to without knowing what the packets payload protocol
80 * will be once the label is popped.
82 fib_forward_chain_type_t dfct;
84 dfct = fib_entry_get_default_chain_type(entry);
86 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS == dfct)
89 * If the entry being asked is a eos-MPLS label entry,
90 * then use the payload-protocol field, that we stashed there
91 * for just this purpose
93 return (fib_forw_chain_type_from_dpo_proto(
94 entry->fe_prefix.fp_payload_proto));
97 * else give them what this entry would be by default. i.e. if it's a v6
98 * entry, then the label its local labelled should be carrying v6 traffic.
99 * If it's a non-EOS label entry, then there are more labels and we want
108 fib_forward_chain_type_t
109 fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
111 switch (fib_entry->fe_prefix.fp_proto)
113 case FIB_PROTOCOL_IP4:
114 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
115 case FIB_PROTOCOL_IP6:
116 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
117 case FIB_PROTOCOL_MPLS:
118 if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
120 * If the entry being asked is a eos-MPLS label entry,
121 * then use the payload-protocol field, that we stashed there
122 * for just this purpose
124 return (fib_forw_chain_type_from_dpo_proto(
125 fib_entry->fe_prefix.fp_payload_proto));
127 return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
130 return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
134 format_fib_entry (u8 * s, va_list * args)
136 fib_forward_chain_type_t fct;
137 fib_entry_attribute_t attr;
138 fib_path_ext_t *path_ext;
139 fib_entry_t *fib_entry;
140 fib_entry_src_t *src;
141 fib_node_index_t fei;
146 fei = va_arg (*args, fib_node_index_t);
147 level = va_arg (*args, int);
148 fib_entry = fib_entry_get(fei);
150 s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
152 if (level >= FIB_ENTRY_FORMAT_DETAIL)
154 s = format (s, " fib:%d", fib_entry->fe_fib_index);
155 s = format (s, " index:%d", fib_entry_get_index(fib_entry));
156 s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
158 FOR_EACH_SRC_ADDED(fib_entry, src, source,
160 s = format (s, "\n src:%s ",
161 fib_source_names[source]);
162 s = fib_entry_src_format(fib_entry, source, s);
163 s = format (s, " refs:%d ", src->fes_ref_count);
164 if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
165 s = format(s, "flags:");
166 FOR_EACH_FIB_ATTRIBUTE(attr) {
167 if ((1<<attr) & src->fes_entry_flags) {
168 s = format (s, "%s,", fib_attribute_names[attr]);
172 s = format (s, "\n");
173 if (FIB_NODE_INDEX_INVALID != src->fes_pl)
175 s = fib_path_list_format(src->fes_pl, s);
177 if (NULL != src->fes_path_exts)
179 s = format(s, " Extensions:");
180 vec_foreach(path_ext, src->fes_path_exts)
182 s = format(s, "\n %U", format_fib_path_ext, path_ext);
187 n_covered = fib_entry_cover_get_size(fib_entry);
189 s = format(s, "\n tracking %d covered: ", n_covered);
190 s = fib_entry_cover_list_format(fib_entry, s);
192 s = fib_ae_import_format(fib_entry->fe_import, s);
193 s = fib_ae_export_format(fib_entry->fe_export, s);
195 s = format (s, "\n forwarding: ");
199 s = format (s, "\n");
202 fct = fib_entry_get_default_chain_type(fib_entry);
204 if (!dpo_id_is_valid(&fib_entry->fe_lb[fct]))
206 s = format (s, " UNRESOLVED\n");
211 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
214 FOR_EACH_FIB_FORW_CHAIN(fct)
216 s = format(s, " %U-chain\n %U",
217 format_fib_forw_chain_type, fct,
219 &fib_entry->fe_lb[fct],
226 s = format(s, " %U-chain\n %U",
227 format_fib_forw_chain_type, fct,
229 &fib_entry->fe_lb[fct],
235 if (level >= FIB_ENTRY_FORMAT_DETAIL2)
237 s = format(s, "\nchildren:");
238 s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
241 /* adj = adj_get(fib_entry->fe_prefix.fp_proto, fib_entry->fe_adj_index); */
243 /* ip_multipath_next_hop_t * nhs, tmp_nhs[1]; */
244 /* u32 i, j, n_left, n_nhs; */
245 /* vlib_counter_t c, sum; */
246 /* ip_lookup_main_t *lm = fib_get_lookup_main(fib_entry->fe_prefix.fp_proto); */
248 /* if (adj->n_adj == 1) */
250 /* nhs = &tmp_nhs[0]; */
251 /* nhs[0].next_hop_adj_index = ~0; /\* not used *\/ */
252 /* nhs[0].weight = 1; */
257 /* ip_multipath_adjacency_t * madj; */
258 /* madj = vec_elt_at_index (lm->multipath_adjacencies, adj->heap_handle); */
259 /* nhs = heap_elt_at_index (lm->next_hop_heap, madj->normalized_next_hops.heap_offset); */
260 /* n_nhs = madj->normalized_next_hops.count; */
263 /* n_left = nhs[0].weight; */
264 /* vlib_counter_zero (&sum); */
265 /* for (i = j = 0; i < adj->n_adj; i++) */
268 /* vlib_get_combined_counter(&lm->adjacency_counters, */
269 /* fib_entry->fe_adj_index + i, */
271 /* /\* if (clear) *\/ */
272 /* /\* vlib_zero_combined_counter (&lm->adjacency_counters, *\/ */
273 /* /\* fib_entry->fe_adj_index + i); *\/ */
275 /* vlib_counter_add (&sum, &c); */
276 /* if (n_left == 0) */
278 /* s = format (s, "%16Ld%16Ld ", sum.packets, sum.bytes); */
279 /* s = format (s, "weight %d, index %d", */
280 /* nhs[j].weight, fib_entry->fe_adj_index + i); */
282 /* if (adj->n_adj > 1) */
283 /* s = format (s, ", multipath"); */
285 /* s = format (s, "\n%U", */
286 /* format_ip_adjacency, */
287 /* vnet_get_main(), lm, fib_entry->fe_adj_index + i); */
289 /* // vlib_cli_output (vm, "%v", msg); */
290 /* //vec_free (msg); */
297 /* n_left = nhs[j].weight; */
298 /* vlib_counter_zero (&sum); */
307 fib_entry_from_fib_node (fib_node_t *node)
310 ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
312 return ((fib_entry_t*)node);
316 fib_entry_last_lock_gone (fib_node_t *node)
318 fib_forward_chain_type_t fct;
319 fib_entry_t *fib_entry;
321 fib_entry = fib_entry_from_fib_node(node);
323 FOR_EACH_FIB_FORW_CHAIN(fct)
325 dpo_reset(&fib_entry->fe_lb[fct]);
328 FIB_ENTRY_DBG(fib_entry, "last-lock");
330 fib_node_deinit(&fib_entry->fe_node);
331 // FIXME -RR Backwalk
332 pool_put(fib_entry_pool, fib_entry);
335 static fib_entry_src_t*
336 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
338 fib_entry_src_t *bsrc;
341 * the enum of sources is deliberately arranged in priority order
343 if (0 == vec_len(fib_entry->fe_srcs))
349 bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
356 fib_entry_src_get_source (const fib_entry_src_t *esrc)
360 return (esrc->fes_src);
362 return (FIB_SOURCE_MAX);
365 static fib_entry_flag_t
366 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
370 return (esrc->fes_entry_flags);
372 return (FIB_ENTRY_FLAG_NONE);
376 fib_entry_get_flags (fib_node_index_t fib_entry_index)
378 return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
382 * fib_entry_back_walk_notify
384 * A back walk has reach this entry.
386 static fib_node_back_walk_rc_t
387 fib_entry_back_walk_notify (fib_node_t *node,
388 fib_node_back_walk_ctx_t *ctx)
390 fib_entry_t *fib_entry;
392 fib_entry = fib_entry_from_fib_node(node);
394 if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason ||
395 FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason ||
396 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
397 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
398 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
400 fib_entry_src_action_reactivate(fib_entry,
401 fib_entry_get_best_source(
402 fib_entry_get_index(fib_entry)));
405 if (FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason)
408 * ADJ updates (complete<->incomplete) do not need to propagate to
410 * The only reason its needed as far back as here, is that the adj
411 * and the incomplete adj are a different DPO type, so the LBs need
414 return (FIB_NODE_BACK_WALK_CONTINUE);
419 * all other walk types can be reclassifed to a re-evaluate to
420 * all recursive dependents.
421 * By reclassifying we ensure that should any of these walk types meet
422 * they can be merged.
424 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
427 * propagate the backwalk further if we haven't already reached the
430 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
431 fib_entry_get_index(fib_entry),
435 return (FIB_NODE_BACK_WALK_CONTINUE);
439 fib_entry_show_memory (void)
441 u32 n_srcs = 0, n_exts = 0;
442 fib_entry_src_t *esrc;
445 fib_show_memory_usage("Entry",
446 pool_elts(fib_entry_pool),
447 pool_len(fib_entry_pool),
448 sizeof(fib_entry_t));
450 pool_foreach(entry, fib_entry_pool,
452 n_srcs += vec_len(entry->fe_srcs);
453 vec_foreach(esrc, entry->fe_srcs)
455 n_exts += vec_len(esrc->fes_path_exts);
459 fib_show_memory_usage("Entry Source",
460 n_srcs, n_srcs, sizeof(fib_entry_src_t));
461 fib_show_memory_usage("Entry Path-Extensions",
463 sizeof(fib_path_ext_t));
467 * The FIB path-list's graph node virtual function table
469 static const fib_node_vft_t fib_entry_vft = {
470 .fnv_get = fib_entry_get_node,
471 .fnv_last_lock = fib_entry_last_lock_gone,
472 .fnv_back_walk = fib_entry_back_walk_notify,
473 .fnv_mem_show = fib_entry_show_memory,
477 * @brief Contribute the set of Adjacencies that this entry forwards with
478 * to build the uRPF list of its children
481 fib_entry_contribute_urpf (fib_node_index_t entry_index,
484 fib_entry_t *fib_entry;
486 fib_entry = fib_entry_get(entry_index);
488 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
492 * fib_entry_contribute_forwarding
494 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
497 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
498 fib_forward_chain_type_t type,
501 fib_entry_t *fib_entry;
503 fib_entry = fib_entry_get(fib_entry_index);
506 * these are not the droids you are looking for...
508 type = fib_entry_chain_type_fixup(fib_entry, type);
510 if (!dpo_id_is_valid(&fib_entry->fe_lb[type]))
513 * on-demand create eos/non-eos.
514 * There is no on-demand delete because:
515 * - memory versus complexity & reliability:
516 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
517 * then up on the right trigger is more code. i favour the latter.
519 fib_entry_src_mk_lb(fib_entry,
520 fib_entry_get_best_src_i(fib_entry),
522 &fib_entry->fe_lb[type]);
525 dpo_copy(dpo, &fib_entry->fe_lb[type]);
529 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
531 fib_entry_t *fib_entry;
533 fib_entry = fib_entry_get(fib_entry_index);
535 return (&fib_entry->fe_lb[fib_entry_get_default_chain_type(fib_entry)]);
539 fib_entry_get_adj (fib_node_index_t fib_entry_index)
543 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
544 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
548 return (dpo->dpoi_index);
550 return (ADJ_INDEX_INVALID);
554 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
556 fib_entry_t *fib_entry;
558 fib_entry = fib_entry_get(fib_entry_index);
560 return (fib_entry->fe_parent);
564 fib_entry_child_add (fib_node_index_t fib_entry_index,
565 fib_node_type_t child_type,
566 fib_node_index_t child_index)
568 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
575 fib_entry_child_remove (fib_node_index_t fib_entry_index,
578 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
584 fib_entry_alloc (u32 fib_index,
585 const fib_prefix_t *prefix,
586 fib_node_index_t *fib_entry_index)
588 fib_forward_chain_type_t fct;
589 fib_entry_t *fib_entry;
591 pool_get(fib_entry_pool, fib_entry);
592 memset(fib_entry, 0, sizeof(*fib_entry));
594 fib_node_init(&fib_entry->fe_node,
595 FIB_NODE_TYPE_ENTRY);
597 fib_entry->fe_fib_index = fib_index;
598 fib_entry->fe_prefix = *prefix;
599 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
601 fib_entry->fe_prefix.fp_len = 21;
602 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
605 fib_entry->fe_export = FIB_NODE_INDEX_INVALID;
606 fib_entry->fe_import = FIB_NODE_INDEX_INVALID;
607 fib_entry->fe_covered = FIB_NODE_INDEX_INVALID;
608 FOR_EACH_FIB_FORW_CHAIN(fct)
610 dpo_reset(&fib_entry->fe_lb[fct]);
613 *fib_entry_index = fib_entry_get_index(fib_entry);
615 FIB_ENTRY_DBG(fib_entry, "alloc");
621 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
623 fib_entry_flag_t old_flags)
626 * handle changes to attached export for import entries
628 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
629 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
631 if (!was_import && is_import)
634 * transition from not exported to exported
638 * there is an assumption here that the entry resolves via only
639 * one interface and that it is the cross VRF interface.
641 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
643 fib_attached_export_import(fib_entry,
644 fib_table_get_index_for_sw_if_index(
645 fib_entry_get_proto(fib_entry),
648 else if (was_import && !is_import)
651 * transition from exported to not exported
653 fib_attached_export_purge(fib_entry);
657 * no change. nothing to do.
661 * handle changes to attached export for export entries
663 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
664 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
666 if (!was_attached && is_attached)
669 * transition to attached. time to export
677 fib_entry_post_install_actions (fib_entry_t *fib_entry,
679 fib_entry_flag_t old_flags)
681 fib_entry_post_flag_update_actions(fib_entry, source, old_flags);
682 fib_entry_src_action_installed(fib_entry, source);
686 fib_entry_create (u32 fib_index,
687 const fib_prefix_t *prefix,
689 fib_entry_flag_t flags,
690 const fib_route_path_t *paths)
692 fib_node_index_t fib_entry_index;
693 fib_entry_t *fib_entry;
695 ASSERT(0 < vec_len(paths));
697 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
700 * since this is a new entry create, we don't need to check for winning
701 * sources - there is only one.
703 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
706 fib_entry_get_proto(fib_entry))));
707 fib_entry_src_action_path_swap(fib_entry,
712 * handle possible realloc's by refetching the pointer
714 fib_entry = fib_entry_get(fib_entry_index);
715 fib_entry_src_action_activate(fib_entry, source);
717 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
719 return (fib_entry_index);
723 fib_entry_create_special (u32 fib_index,
724 const fib_prefix_t *prefix,
726 fib_entry_flag_t flags,
729 fib_node_index_t fib_entry_index;
730 fib_entry_t *fib_entry;
733 * create and initiliase the new enty
735 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
738 * create the path-list
740 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
741 fib_entry_src_action_activate(fib_entry, source);
743 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
745 return (fib_entry_index);
749 fib_entry_post_update_actions (fib_entry_t *fib_entry,
751 fib_entry_flag_t old_flags)
754 * backwalk to children to inform then of the change to forwarding.
756 fib_node_back_walk_ctx_t bw_ctx = {
757 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
760 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
763 * then inform any covered prefixes
765 fib_entry_cover_update_notify(fib_entry);
767 fib_entry_post_install_actions(fib_entry, source, old_flags);
771 fib_entry_special_add (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_add(fib_entry, source, flags, dpo);
790 * if the path list for the source passed is invalid,
791 * then we need to create a new one. else we are updating
794 if (source < best_source)
797 * we have a new winning source.
799 fib_entry_src_action_deactivate(fib_entry, best_source);
800 fib_entry_src_action_activate(fib_entry, source);
802 else if (source > best_source)
805 * the new source loses. nothing to do here.
806 * the data from the source is saved in the path-list created
813 * the new source is one this entry already has.
814 * But the path-list was updated, which will contribute new forwarding,
817 fib_entry_src_action_deactivate(fib_entry, source);
818 fib_entry_src_action_activate(fib_entry, source);
821 fib_entry_post_update_actions(fib_entry, source, bflags);
825 fib_entry_path_add (fib_node_index_t fib_entry_index,
827 fib_entry_flag_t flags,
828 const fib_route_path_t *rpath)
830 fib_source_t best_source;
831 fib_entry_flag_t bflags;
832 fib_entry_t *fib_entry;
833 fib_entry_src_t *bsrc;
835 ASSERT(1 == vec_len(rpath));
837 fib_entry = fib_entry_get(fib_entry_index);
838 ASSERT(NULL != fib_entry);
840 bsrc = fib_entry_get_best_src_i(fib_entry);
841 best_source = fib_entry_src_get_source(bsrc);
842 bflags = fib_entry_src_get_flags(bsrc);
844 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
847 * if the path list for the source passed is invalid,
848 * then we need to create a new one. else we are updating
851 if (source < best_source)
854 * we have a new winning source.
856 fib_entry_src_action_deactivate(fib_entry, best_source);
857 fib_entry_src_action_activate(fib_entry, source);
859 else if (source > best_source)
862 * the new source loses. nothing to do here.
863 * the data from the source is saved in the path-list created
870 * the new source is one this entry already has.
871 * But the path-list was updated, which will contribute new forwarding,
874 fib_entry_src_action_deactivate(fib_entry, source);
875 fib_entry_src_action_activate(fib_entry, source);
878 fib_entry_post_update_actions(fib_entry, source, bflags);
882 * fib_entry_path_remove
884 * remove a path from the entry.
885 * return the fib_entry's index if it is still present, INVALID otherwise.
888 fib_entry_path_remove (fib_node_index_t fib_entry_index,
890 const fib_route_path_t *rpath)
892 fib_entry_src_flag_t sflag;
893 fib_source_t best_source;
894 fib_entry_flag_t bflags;
895 fib_entry_t *fib_entry;
896 fib_entry_src_t *bsrc;
898 ASSERT(1 == vec_len(rpath));
900 fib_entry = fib_entry_get(fib_entry_index);
901 ASSERT(NULL != fib_entry);
903 bsrc = fib_entry_get_best_src_i(fib_entry);
904 best_source = fib_entry_src_get_source(bsrc);
905 bflags = fib_entry_src_get_flags(bsrc);
907 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
910 * if the path list for the source passed is invalid,
911 * then we need to create a new one. else we are updating
914 if (source < best_source )
917 * Que! removing a path from a source that is better than the
918 * one this entry is using.
922 else if (source > best_source )
925 * the source is not the best. nothing to do.
927 return (FIB_ENTRY_SRC_FLAG_ADDED);
932 * removing a path from the path-list we were using.
934 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
937 * the last path from the source was removed.
938 * fallback to lower source
940 bsrc = fib_entry_get_best_src_i(fib_entry);
941 best_source = fib_entry_src_get_source(bsrc);
943 if (FIB_SOURCE_MAX == best_source) {
945 * no more sources left. this entry is toast.
947 fib_entry_src_action_uninstall(fib_entry);
948 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
950 return (FIB_ENTRY_SRC_FLAG_NONE);
954 fib_entry_src_action_activate(fib_entry, best_source);
955 source = best_source;
961 * re-install the new forwarding information
963 fib_entry_src_action_deactivate(fib_entry, source);
964 fib_entry_src_action_activate(fib_entry, source);
968 fib_entry_post_update_actions(fib_entry, source, bflags);
973 return (FIB_ENTRY_SRC_FLAG_ADDED);
977 * fib_entry_special_remove
979 * remove a special source from the entry.
980 * return the fib_entry's index if it is still present, INVALID otherwise.
983 fib_entry_special_remove (fib_node_index_t fib_entry_index,
986 fib_entry_src_flag_t sflag;
987 fib_source_t best_source;
988 fib_entry_flag_t bflags;
989 fib_entry_t *fib_entry;
990 fib_entry_src_t *bsrc;
992 fib_entry = fib_entry_get(fib_entry_index);
993 ASSERT(NULL != fib_entry);
995 bsrc = fib_entry_get_best_src_i(fib_entry);
996 best_source = fib_entry_src_get_source(bsrc);
997 bflags = fib_entry_src_get_flags(bsrc);
999 sflag = fib_entry_src_action_remove(fib_entry, source);
1002 * if the path list for the source passed is invalid,
1003 * then we need to create a new one. else we are updating
1006 if (source < best_source )
1009 * Que! removing a path from a source that is better than the
1010 * one this entry is using. This can only mean it is a source
1011 * this prefix does not have.
1013 return (FIB_ENTRY_SRC_FLAG_ADDED);
1015 else if (source > best_source ) {
1017 * the source is not the best. nothing to do.
1019 return (FIB_ENTRY_SRC_FLAG_ADDED);
1023 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1026 * the source was removed. use the next best.
1028 bsrc = fib_entry_get_best_src_i(fib_entry);
1029 best_source = fib_entry_src_get_source(bsrc);
1031 if (FIB_SOURCE_MAX == best_source) {
1033 * no more sources left. this entry is toast.
1035 fib_entry_src_action_uninstall(fib_entry);
1036 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
1038 return (FIB_ENTRY_SRC_FLAG_NONE);
1042 fib_entry_src_action_activate(fib_entry, best_source);
1043 source = best_source;
1049 * re-install the new forwarding information
1051 fib_entry_src_action_reactivate(fib_entry, source);
1055 fib_entry_post_update_actions(fib_entry, source, bflags);
1058 * still have sources
1060 return (FIB_ENTRY_SRC_FLAG_ADDED);
1066 * The source is withdrawing all the paths it provided
1068 fib_entry_src_flag_t
1069 fib_entry_delete (fib_node_index_t fib_entry_index,
1070 fib_source_t source)
1072 return (fib_entry_special_remove(fib_entry_index, source));
1078 * The source has provided a new set of paths that will replace the old.
1081 fib_entry_update (fib_node_index_t fib_entry_index,
1082 fib_source_t source,
1083 fib_entry_flag_t flags,
1084 const fib_route_path_t *paths)
1086 fib_source_t best_source;
1087 fib_entry_flag_t bflags;
1088 fib_entry_t *fib_entry;
1089 fib_entry_src_t *bsrc;
1091 fib_entry = fib_entry_get(fib_entry_index);
1092 ASSERT(NULL != fib_entry);
1094 bsrc = fib_entry_get_best_src_i(fib_entry);
1095 best_source = fib_entry_src_get_source(bsrc);
1096 bflags = fib_entry_src_get_flags(bsrc);
1098 fib_entry_src_action_path_swap(fib_entry,
1103 * handle possible realloc's by refetching the pointer
1105 fib_entry = fib_entry_get(fib_entry_index);
1108 * if the path list for the source passed is invalid,
1109 * then we need to create a new one. else we are updating
1112 if (source < best_source)
1115 * we have a new winning source.
1117 fib_entry_src_action_deactivate(fib_entry, best_source);
1118 fib_entry_src_action_activate(fib_entry, source);
1120 else if (source > best_source) {
1122 * the new source loses. nothing to do here.
1123 * the data from the source is saved in the path-list created
1130 * the new source is one this entry already has.
1131 * But the path-list was updated, which will contribute new forwarding,
1134 fib_entry_src_action_deactivate(fib_entry, source);
1135 fib_entry_src_action_activate(fib_entry, source);
1138 fib_entry_post_update_actions(fib_entry, source, bflags);
1143 * fib_entry_cover_changed
1145 * this entry is tracking its cover and that cover has changed.
1148 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1150 fib_entry_src_cover_res_t res = {
1152 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1154 fib_source_t source, best_source;
1155 fib_entry_flag_t bflags;
1156 fib_entry_t *fib_entry;
1157 fib_entry_src_t *esrc;
1160 bflags = FIB_ENTRY_FLAG_NONE;
1161 best_source = FIB_SOURCE_FIRST;
1162 fib_entry = fib_entry_get(fib_entry_index);
1164 fib_attached_export_cover_change(fib_entry);
1167 * propagate the notificuation to each of the added sources
1170 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1175 * only the best source gets to set the back walk flags
1177 res = fib_entry_src_action_cover_change(fib_entry, source);
1178 bflags = fib_entry_src_get_flags(esrc);
1179 best_source = fib_entry_src_get_source(esrc);
1183 fib_entry_src_action_cover_change(fib_entry, source);
1190 fib_entry_src_action_reactivate(fib_entry,
1191 fib_entry_src_get_source(
1192 fib_entry_get_best_src_i(fib_entry)));
1193 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1197 fib_entry_src_action_uninstall(fib_entry);
1200 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1203 * time for walkies fido.
1205 fib_node_back_walk_ctx_t bw_ctx = {
1206 .fnbw_reason = res.bw_reason,
1209 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1214 * fib_entry_cover_updated
1216 * this entry is tracking its cover and that cover has been updated
1217 * (i.e. its forwarding information has changed).
1220 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1222 fib_entry_src_cover_res_t res = {
1224 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1226 fib_source_t source, best_source;
1227 fib_entry_flag_t bflags;
1228 fib_entry_t *fib_entry;
1229 fib_entry_src_t *esrc;
1232 bflags = FIB_ENTRY_FLAG_NONE;
1233 best_source = FIB_SOURCE_FIRST;
1234 fib_entry = fib_entry_get(fib_entry_index);
1236 fib_attached_export_cover_update(fib_entry);
1239 * propagate the notificuation to each of the added sources
1242 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1247 * only the best source gets to set the back walk flags
1249 res = fib_entry_src_action_cover_update(fib_entry, source);
1250 bflags = fib_entry_src_get_flags(esrc);
1251 best_source = fib_entry_src_get_source(esrc);
1255 fib_entry_src_action_cover_update(fib_entry, source);
1262 fib_entry_src_action_reactivate(fib_entry,
1263 fib_entry_src_get_source(
1264 fib_entry_get_best_src_i(fib_entry)));
1265 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1269 fib_entry_src_action_uninstall(fib_entry);
1272 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1275 * time for walkies fido.
1277 fib_node_back_walk_ctx_t bw_ctx = {
1278 .fnbw_reason = res.bw_reason,
1281 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1286 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1287 fib_node_index_t **entry_indicies)
1289 fib_entry_t *fib_entry;
1290 int was_looped, is_looped;
1292 fib_entry = fib_entry_get(entry_index);
1294 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1296 fib_node_index_t *entries = *entry_indicies;
1297 fib_forward_chain_type_t fct;
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 FOR_EACH_FIB_FORW_CHAIN(fct)
1314 if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
1316 fib_entry_src_mk_lb(fib_entry,
1317 fib_entry_get_best_src_i(fib_entry),
1319 &fib_entry->fe_lb[fct]);
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 fib_ip4_address_compare (ip4_address_t * a1,
1364 * IP addresses are unsiged ints. the return value here needs to be signed
1365 * a simple subtraction won't cut it.
1366 * If the addresses are the same, the sort order is undefiend, so phoey.
1368 return ((clib_net_to_host_u32(a1->data_u32) >
1369 clib_net_to_host_u32(a2->data_u32) ) ?
1374 fib_ip6_address_compare (ip6_address_t * a1,
1378 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1380 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1381 clib_net_to_host_u16 (a2->as_u16[i]));
1389 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1390 fib_node_index_t fib_entry_index2)
1392 fib_entry_t *fib_entry1, *fib_entry2;
1395 fib_entry1 = fib_entry_get(fib_entry_index1);
1396 fib_entry2 = fib_entry_get(fib_entry_index2);
1398 switch (fib_entry1->fe_prefix.fp_proto)
1400 case FIB_PROTOCOL_IP4:
1401 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1402 &fib_entry2->fe_prefix.fp_addr.ip4);
1404 case FIB_PROTOCOL_IP6:
1405 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1406 &fib_entry2->fe_prefix.fp_addr.ip6);
1408 case FIB_PROTOCOL_MPLS:
1409 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1413 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1419 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1425 fib_entry_cmp_for_sort (void *i1, void *i2)
1427 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1429 return (fib_entry_cmp(*fib_entry_index1,
1430 *fib_entry_index2));
1434 fib_entry_lock (fib_node_index_t fib_entry_index)
1436 fib_entry_t *fib_entry;
1438 fib_entry = fib_entry_get(fib_entry_index);
1440 fib_node_lock(&fib_entry->fe_node);
1444 fib_entry_unlock (fib_node_index_t fib_entry_index)
1446 fib_entry_t *fib_entry;
1448 fib_entry = fib_entry_get(fib_entry_index);
1450 fib_node_unlock(&fib_entry->fe_node);
1454 fib_entry_module_init (void)
1456 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1460 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1463 fib_entry_t *fib_entry;
1465 fib_entry = fib_entry_get(fib_entry_index);
1466 *pfx = fib_entry->fe_prefix;
1470 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1472 fib_entry_t *fib_entry;
1474 fib_entry = fib_entry_get(fib_entry_index);
1476 return (fib_entry->fe_fib_index);
1480 fib_entry_pool_size (void)
1482 return (pool_elts(fib_entry_pool));
1485 static clib_error_t *
1486 show_fib_entry_command (vlib_main_t * vm,
1487 unformat_input_t * input,
1488 vlib_cli_command_t * cmd)
1490 fib_node_index_t fei;
1492 if (unformat (input, "%d", &fei))
1495 * show one in detail
1497 if (!pool_is_free_index(fib_entry_pool, fei))
1499 vlib_cli_output (vm, "%d@%U",
1501 format_fib_entry, fei,
1502 FIB_ENTRY_FORMAT_DETAIL2);
1506 vlib_cli_output (vm, "entry %d invalid", fei);
1514 vlib_cli_output (vm, "FIB Entries:");
1515 pool_foreach_index(fei, fib_entry_pool,
1517 vlib_cli_output (vm, "%d@%U",
1519 format_fib_entry, fei,
1520 FIB_ENTRY_FORMAT_BRIEF);
1527 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1528 .path = "show fib entry",
1529 .function = show_fib_entry_command,
1530 .short_help = "show fib entry",