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 * fib_entry_contribute_forwarding
479 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
482 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
483 fib_forward_chain_type_t type,
486 fib_entry_t *fib_entry;
488 fib_entry = fib_entry_get(fib_entry_index);
491 * these are not the droids you are looking for...
493 type = fib_entry_chain_type_fixup(fib_entry, type);
495 if (!dpo_id_is_valid(&fib_entry->fe_lb[type]))
498 * on-demand create eos/non-eos.
499 * There is no on-demand delete because:
500 * - memory versus complexity & reliability:
501 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
502 * then up on the right trigger is more code. i favour the latter.
504 fib_entry_src_mk_lb(fib_entry,
505 fib_entry_get_best_src_i(fib_entry),
507 &fib_entry->fe_lb[type]);
510 dpo_copy(dpo, &fib_entry->fe_lb[type]);
514 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
516 fib_entry_t *fib_entry;
518 fib_entry = fib_entry_get(fib_entry_index);
520 return (&fib_entry->fe_lb[fib_entry_get_default_chain_type(fib_entry)]);
524 fib_entry_get_adj (fib_node_index_t fib_entry_index)
528 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
529 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
533 return (dpo->dpoi_index);
535 return (ADJ_INDEX_INVALID);
539 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
541 fib_entry_t *fib_entry;
543 fib_entry = fib_entry_get(fib_entry_index);
545 return (fib_entry->fe_parent);
549 fib_entry_child_add (fib_node_index_t fib_entry_index,
550 fib_node_type_t child_type,
551 fib_node_index_t child_index)
553 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
560 fib_entry_child_remove (fib_node_index_t fib_entry_index,
563 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
569 fib_entry_alloc (u32 fib_index,
570 const fib_prefix_t *prefix,
571 fib_node_index_t *fib_entry_index)
573 fib_forward_chain_type_t fct;
574 fib_entry_t *fib_entry;
576 pool_get(fib_entry_pool, fib_entry);
577 memset(fib_entry, 0, sizeof(*fib_entry));
579 fib_node_init(&fib_entry->fe_node,
580 FIB_NODE_TYPE_ENTRY);
582 fib_entry->fe_fib_index = fib_index;
583 fib_entry->fe_prefix = *prefix;
584 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
586 fib_entry->fe_prefix.fp_len = 21;
587 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
590 fib_entry->fe_export = FIB_NODE_INDEX_INVALID;
591 fib_entry->fe_import = FIB_NODE_INDEX_INVALID;
592 fib_entry->fe_covered = FIB_NODE_INDEX_INVALID;
593 FOR_EACH_FIB_FORW_CHAIN(fct)
595 dpo_reset(&fib_entry->fe_lb[fct]);
598 *fib_entry_index = fib_entry_get_index(fib_entry);
600 FIB_ENTRY_DBG(fib_entry, "alloc");
606 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
608 fib_entry_flag_t old_flags)
611 * handle changes to attached export for import entries
613 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
614 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
616 if (!was_import && is_import)
619 * transition from not exported to exported
623 * there is an assumption here that the entry resolves via only
624 * one interface and that it is the cross VRF interface.
626 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
628 fib_attached_export_import(fib_entry,
629 fib_table_get_index_for_sw_if_index(
630 fib_entry_get_proto(fib_entry),
633 else if (was_import && !is_import)
636 * transition from exported to not exported
638 fib_attached_export_purge(fib_entry);
642 * no change. nothing to do.
646 * handle changes to attached export for export entries
648 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
649 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
651 if (!was_attached && is_attached)
654 * transition to attached. time to export
662 fib_entry_post_install_actions (fib_entry_t *fib_entry,
664 fib_entry_flag_t old_flags)
666 fib_entry_post_flag_update_actions(fib_entry, source, old_flags);
667 fib_entry_src_action_installed(fib_entry, source);
671 fib_entry_create (u32 fib_index,
672 const fib_prefix_t *prefix,
674 fib_entry_flag_t flags,
675 const fib_route_path_t *paths)
677 fib_node_index_t fib_entry_index;
678 fib_entry_t *fib_entry;
680 ASSERT(0 < vec_len(paths));
682 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
685 * since this is a new entry create, we don't need to check for winning
686 * sources - there is only one.
688 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
691 fib_entry_get_proto(fib_entry))));
692 fib_entry_src_action_path_swap(fib_entry,
697 * handle possible realloc's by refetching the pointer
699 fib_entry = fib_entry_get(fib_entry_index);
700 fib_entry_src_action_activate(fib_entry, source);
702 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
704 return (fib_entry_index);
708 fib_entry_create_special (u32 fib_index,
709 const fib_prefix_t *prefix,
711 fib_entry_flag_t flags,
714 fib_node_index_t fib_entry_index;
715 fib_entry_t *fib_entry;
718 * create and initiliase the new enty
720 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
723 * create the path-list
725 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
726 fib_entry_src_action_activate(fib_entry, source);
728 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
730 return (fib_entry_index);
734 fib_entry_post_update_actions (fib_entry_t *fib_entry,
736 fib_entry_flag_t old_flags)
739 * backwalk to children to inform then of the change to forwarding.
741 fib_node_back_walk_ctx_t bw_ctx = {
742 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
745 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
748 * then inform any covered prefixes
750 fib_entry_cover_update_notify(fib_entry);
752 fib_entry_post_install_actions(fib_entry, source, old_flags);
756 fib_entry_special_add (fib_node_index_t fib_entry_index,
758 fib_entry_flag_t flags,
761 fib_source_t best_source;
762 fib_entry_flag_t bflags;
763 fib_entry_t *fib_entry;
764 fib_entry_src_t *bsrc;
766 fib_entry = fib_entry_get(fib_entry_index);
768 bsrc = fib_entry_get_best_src_i(fib_entry);
769 best_source = fib_entry_src_get_source(bsrc);
770 bflags = fib_entry_src_get_flags(bsrc);
772 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
775 * if the path list for the source passed is invalid,
776 * then we need to create a new one. else we are updating
779 if (source < best_source)
782 * we have a new winning source.
784 fib_entry_src_action_deactivate(fib_entry, best_source);
785 fib_entry_src_action_activate(fib_entry, source);
787 else if (source > best_source)
790 * the new source loses. nothing to do here.
791 * the data from the source is saved in the path-list created
798 * the new source is one this entry already has.
799 * But the path-list was updated, which will contribute new forwarding,
802 fib_entry_src_action_deactivate(fib_entry, source);
803 fib_entry_src_action_activate(fib_entry, source);
806 fib_entry_post_update_actions(fib_entry, source, bflags);
810 fib_entry_path_add (fib_node_index_t fib_entry_index,
812 fib_entry_flag_t flags,
813 const fib_route_path_t *rpath)
815 fib_source_t best_source;
816 fib_entry_flag_t bflags;
817 fib_entry_t *fib_entry;
818 fib_entry_src_t *bsrc;
820 ASSERT(1 == vec_len(rpath));
822 fib_entry = fib_entry_get(fib_entry_index);
823 ASSERT(NULL != fib_entry);
825 bsrc = fib_entry_get_best_src_i(fib_entry);
826 best_source = fib_entry_src_get_source(bsrc);
827 bflags = fib_entry_src_get_flags(bsrc);
829 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
832 * if the path list for the source passed is invalid,
833 * then we need to create a new one. else we are updating
836 if (source < best_source)
839 * we have a new winning source.
841 fib_entry_src_action_deactivate(fib_entry, best_source);
842 fib_entry_src_action_activate(fib_entry, source);
844 else if (source > best_source)
847 * the new source loses. nothing to do here.
848 * the data from the source is saved in the path-list created
855 * the new source is one this entry already has.
856 * But the path-list was updated, which will contribute new forwarding,
859 fib_entry_src_action_deactivate(fib_entry, source);
860 fib_entry_src_action_activate(fib_entry, source);
863 fib_entry_post_update_actions(fib_entry, source, bflags);
867 * fib_entry_path_remove
869 * remove a path from the entry.
870 * return the fib_entry's index if it is still present, INVALID otherwise.
873 fib_entry_path_remove (fib_node_index_t fib_entry_index,
875 const fib_route_path_t *rpath)
877 fib_entry_src_flag_t sflag;
878 fib_source_t best_source;
879 fib_entry_flag_t bflags;
880 fib_entry_t *fib_entry;
881 fib_entry_src_t *bsrc;
883 ASSERT(1 == vec_len(rpath));
885 fib_entry = fib_entry_get(fib_entry_index);
886 ASSERT(NULL != fib_entry);
888 bsrc = fib_entry_get_best_src_i(fib_entry);
889 best_source = fib_entry_src_get_source(bsrc);
890 bflags = fib_entry_src_get_flags(bsrc);
892 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
895 * if the path list for the source passed is invalid,
896 * then we need to create a new one. else we are updating
899 if (source < best_source )
902 * Que! removing a path from a source that is better than the
903 * one this entry is using.
907 else if (source > best_source )
910 * the source is not the best. nothing to do.
912 return (FIB_ENTRY_SRC_FLAG_ADDED);
917 * removing a path from the path-list we were using.
919 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
922 * the last path from the source was removed.
923 * fallback to lower source
925 bsrc = fib_entry_get_best_src_i(fib_entry);
926 best_source = fib_entry_src_get_source(bsrc);
928 if (FIB_SOURCE_MAX == best_source) {
930 * no more sources left. this entry is toast.
932 fib_entry_src_action_uninstall(fib_entry);
933 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
935 return (FIB_ENTRY_SRC_FLAG_NONE);
939 fib_entry_src_action_activate(fib_entry, best_source);
940 source = best_source;
946 * re-install the new forwarding information
948 fib_entry_src_action_deactivate(fib_entry, source);
949 fib_entry_src_action_activate(fib_entry, source);
953 fib_entry_post_update_actions(fib_entry, source, bflags);
958 return (FIB_ENTRY_SRC_FLAG_ADDED);
962 * fib_entry_special_remove
964 * remove a special source from the entry.
965 * return the fib_entry's index if it is still present, INVALID otherwise.
968 fib_entry_special_remove (fib_node_index_t fib_entry_index,
971 fib_entry_src_flag_t sflag;
972 fib_source_t best_source;
973 fib_entry_flag_t bflags;
974 fib_entry_t *fib_entry;
975 fib_entry_src_t *bsrc;
977 fib_entry = fib_entry_get(fib_entry_index);
978 ASSERT(NULL != fib_entry);
980 bsrc = fib_entry_get_best_src_i(fib_entry);
981 best_source = fib_entry_src_get_source(bsrc);
982 bflags = fib_entry_src_get_flags(bsrc);
984 sflag = fib_entry_src_action_remove(fib_entry, source);
987 * if the path list for the source passed is invalid,
988 * then we need to create a new one. else we are updating
991 if (source < best_source )
994 * Que! removing a path from a source that is better than the
995 * one this entry is using. This can only mean it is a source
996 * this prefix does not have.
998 return (FIB_ENTRY_SRC_FLAG_ADDED);
1000 else if (source > best_source ) {
1002 * the source is not the best. nothing to do.
1004 return (FIB_ENTRY_SRC_FLAG_ADDED);
1008 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1011 * the source was removed. use the next best.
1013 bsrc = fib_entry_get_best_src_i(fib_entry);
1014 best_source = fib_entry_src_get_source(bsrc);
1016 if (FIB_SOURCE_MAX == best_source) {
1018 * no more sources left. this entry is toast.
1020 fib_entry_src_action_uninstall(fib_entry);
1021 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
1023 return (FIB_ENTRY_SRC_FLAG_NONE);
1027 fib_entry_src_action_activate(fib_entry, best_source);
1028 source = best_source;
1034 * re-install the new forwarding information
1036 fib_entry_src_action_reactivate(fib_entry, source);
1040 fib_entry_post_update_actions(fib_entry, source, bflags);
1043 * still have sources
1045 return (FIB_ENTRY_SRC_FLAG_ADDED);
1051 * The source is withdrawing all the paths it provided
1053 fib_entry_src_flag_t
1054 fib_entry_delete (fib_node_index_t fib_entry_index,
1055 fib_source_t source)
1057 return (fib_entry_special_remove(fib_entry_index, source));
1063 * The source has provided a new set of paths that will replace the old.
1066 fib_entry_update (fib_node_index_t fib_entry_index,
1067 fib_source_t source,
1068 fib_entry_flag_t flags,
1069 const fib_route_path_t *paths)
1071 fib_source_t best_source;
1072 fib_entry_flag_t bflags;
1073 fib_entry_t *fib_entry;
1074 fib_entry_src_t *bsrc;
1076 fib_entry = fib_entry_get(fib_entry_index);
1077 ASSERT(NULL != fib_entry);
1079 bsrc = fib_entry_get_best_src_i(fib_entry);
1080 best_source = fib_entry_src_get_source(bsrc);
1081 bflags = fib_entry_src_get_flags(bsrc);
1083 fib_entry_src_action_path_swap(fib_entry,
1088 * handle possible realloc's by refetching the pointer
1090 fib_entry = fib_entry_get(fib_entry_index);
1093 * if the path list for the source passed is invalid,
1094 * then we need to create a new one. else we are updating
1097 if (source < best_source)
1100 * we have a new winning source.
1102 fib_entry_src_action_deactivate(fib_entry, best_source);
1103 fib_entry_src_action_activate(fib_entry, source);
1105 else if (source > best_source) {
1107 * the new source loses. nothing to do here.
1108 * the data from the source is saved in the path-list created
1115 * the new source is one this entry already has.
1116 * But the path-list was updated, which will contribute new forwarding,
1119 fib_entry_src_action_deactivate(fib_entry, source);
1120 fib_entry_src_action_activate(fib_entry, source);
1123 fib_entry_post_update_actions(fib_entry, source, bflags);
1128 * fib_entry_cover_changed
1130 * this entry is tracking its cover and that cover has changed.
1133 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1135 fib_entry_src_cover_res_t res = {
1137 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1139 fib_source_t source, best_source;
1140 fib_entry_flag_t bflags;
1141 fib_entry_t *fib_entry;
1142 fib_entry_src_t *esrc;
1145 bflags = FIB_ENTRY_FLAG_NONE;
1146 best_source = FIB_SOURCE_FIRST;
1147 fib_entry = fib_entry_get(fib_entry_index);
1149 fib_attached_export_cover_change(fib_entry);
1152 * propagate the notificuation to each of the added sources
1155 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1160 * only the best source gets to set the back walk flags
1162 res = fib_entry_src_action_cover_change(fib_entry, source);
1163 bflags = fib_entry_src_get_flags(esrc);
1164 best_source = fib_entry_src_get_source(esrc);
1168 fib_entry_src_action_cover_change(fib_entry, source);
1175 fib_entry_src_action_reactivate(fib_entry,
1176 fib_entry_src_get_source(
1177 fib_entry_get_best_src_i(fib_entry)));
1178 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1182 fib_entry_src_action_uninstall(fib_entry);
1185 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1188 * time for walkies fido.
1190 fib_node_back_walk_ctx_t bw_ctx = {
1191 .fnbw_reason = res.bw_reason,
1194 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1199 * fib_entry_cover_updated
1201 * this entry is tracking its cover and that cover has been updated
1202 * (i.e. its forwarding information has changed).
1205 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1207 fib_entry_src_cover_res_t res = {
1209 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1211 fib_source_t source, best_source;
1212 fib_entry_flag_t bflags;
1213 fib_entry_t *fib_entry;
1214 fib_entry_src_t *esrc;
1217 bflags = FIB_ENTRY_FLAG_NONE;
1218 best_source = FIB_SOURCE_FIRST;
1219 fib_entry = fib_entry_get(fib_entry_index);
1221 fib_attached_export_cover_update(fib_entry);
1224 * propagate the notificuation to each of the added sources
1227 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1232 * only the best source gets to set the back walk flags
1234 res = fib_entry_src_action_cover_update(fib_entry, source);
1235 bflags = fib_entry_src_get_flags(esrc);
1236 best_source = fib_entry_src_get_source(esrc);
1240 fib_entry_src_action_cover_update(fib_entry, source);
1247 fib_entry_src_action_reactivate(fib_entry,
1248 fib_entry_src_get_source(
1249 fib_entry_get_best_src_i(fib_entry)));
1250 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1254 fib_entry_src_action_uninstall(fib_entry);
1257 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1260 * time for walkies fido.
1262 fib_node_back_walk_ctx_t bw_ctx = {
1263 .fnbw_reason = res.bw_reason,
1266 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1271 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1272 fib_node_index_t **entry_indicies)
1274 fib_entry_t *fib_entry;
1275 int was_looped, is_looped;
1277 fib_entry = fib_entry_get(entry_index);
1279 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1281 fib_node_index_t *entries = *entry_indicies;
1282 fib_forward_chain_type_t fct;
1284 vec_add1(entries, entry_index);
1285 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1286 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1289 *entry_indicies = entries;
1291 if (!!was_looped != !!is_looped)
1294 * re-evaluate all the entry's forwarding
1295 * NOTE: this is an inplace modify
1297 FOR_EACH_FIB_FORW_CHAIN(fct)
1299 if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
1301 fib_entry_src_mk_lb(fib_entry,
1302 fib_entry_get_best_src_i(fib_entry),
1304 &fib_entry->fe_lb[fct]);
1312 * the entry is currently not linked to a path-list. this happens
1313 * when it is this entry that is re-linking path-lists and has thus
1323 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1325 fib_entry_t *fib_entry;
1327 fib_entry = fib_entry_get(entry_index);
1329 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1333 fib_entry_get_best_source (fib_node_index_t entry_index)
1335 fib_entry_t *fib_entry;
1336 fib_entry_src_t *bsrc;
1338 fib_entry = fib_entry_get(entry_index);
1340 bsrc = fib_entry_get_best_src_i(fib_entry);
1341 return (fib_entry_src_get_source(bsrc));
1345 fib_ip4_address_compare (ip4_address_t * a1,
1349 * IP addresses are unsiged ints. the return value here needs to be signed
1350 * a simple subtraction won't cut it.
1351 * If the addresses are the same, the sort order is undefiend, so phoey.
1353 return ((clib_net_to_host_u32(a1->data_u32) >
1354 clib_net_to_host_u32(a2->data_u32) ) ?
1359 fib_ip6_address_compare (ip6_address_t * a1,
1363 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1365 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1366 clib_net_to_host_u16 (a2->as_u16[i]));
1374 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1375 fib_node_index_t fib_entry_index2)
1377 fib_entry_t *fib_entry1, *fib_entry2;
1380 fib_entry1 = fib_entry_get(fib_entry_index1);
1381 fib_entry2 = fib_entry_get(fib_entry_index2);
1383 switch (fib_entry1->fe_prefix.fp_proto)
1385 case FIB_PROTOCOL_IP4:
1386 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1387 &fib_entry2->fe_prefix.fp_addr.ip4);
1389 case FIB_PROTOCOL_IP6:
1390 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1391 &fib_entry2->fe_prefix.fp_addr.ip6);
1393 case FIB_PROTOCOL_MPLS:
1394 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1398 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1404 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1410 fib_entry_cmp_for_sort (void *i1, void *i2)
1412 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1414 return (fib_entry_cmp(*fib_entry_index1,
1415 *fib_entry_index2));
1419 fib_entry_lock (fib_node_index_t fib_entry_index)
1421 fib_entry_t *fib_entry;
1423 fib_entry = fib_entry_get(fib_entry_index);
1425 fib_node_lock(&fib_entry->fe_node);
1429 fib_entry_unlock (fib_node_index_t fib_entry_index)
1431 fib_entry_t *fib_entry;
1433 fib_entry = fib_entry_get(fib_entry_index);
1435 fib_node_unlock(&fib_entry->fe_node);
1439 fib_entry_module_init (void)
1441 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1445 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1448 fib_entry_t *fib_entry;
1450 fib_entry = fib_entry_get(fib_entry_index);
1451 *pfx = fib_entry->fe_prefix;
1455 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1457 fib_entry_t *fib_entry;
1459 fib_entry = fib_entry_get(fib_entry_index);
1461 return (fib_entry->fe_fib_index);
1465 fib_entry_pool_size (void)
1467 return (pool_elts(fib_entry_pool));
1470 static clib_error_t *
1471 show_fib_entry_command (vlib_main_t * vm,
1472 unformat_input_t * input,
1473 vlib_cli_command_t * cmd)
1475 fib_node_index_t fei;
1477 if (unformat (input, "%d", &fei))
1480 * show one in detail
1482 if (!pool_is_free_index(fib_entry_pool, fei))
1484 vlib_cli_output (vm, "%d@%U",
1486 format_fib_entry, fei,
1487 FIB_ENTRY_FORMAT_DETAIL2);
1491 vlib_cli_output (vm, "entry %d invalid", fei);
1499 vlib_cli_output (vm, "FIB Entries:");
1500 pool_foreach_index(fei, fib_entry_pool,
1502 vlib_cli_output (vm, "%d@%U",
1504 format_fib_entry, fei,
1505 FIB_ENTRY_FORMAT_BRIEF);
1512 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1513 .path = "show fib entry",
1514 .function = show_fib_entry_command,
1515 .short_help = "show fib entry",