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_MPLS_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_MPLS_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_ADJ_DOWN & ctx->fnbw_reason ||
397 FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason ||
398 FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason ||
399 FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
401 fib_entry_src_action_reactivate(fib_entry,
402 fib_entry_get_best_source(
403 fib_entry_get_index(fib_entry)));
407 * all other walk types can be reclassifed to a re-evaluate to
408 * all recursive dependents.
409 * By reclassifying we ensure that should any of these walk types meet
410 * they can be merged.
412 ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
415 * ... and nothing is forced sync from now on.
417 ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
420 * propagate the backwalk further if we haven't already reached the
423 fib_walk_sync(FIB_NODE_TYPE_ENTRY,
424 fib_entry_get_index(fib_entry),
427 return (FIB_NODE_BACK_WALK_CONTINUE);
431 fib_entry_show_memory (void)
433 u32 n_srcs = 0, n_exts = 0;
434 fib_entry_src_t *esrc;
437 fib_show_memory_usage("Entry",
438 pool_elts(fib_entry_pool),
439 pool_len(fib_entry_pool),
440 sizeof(fib_entry_t));
442 pool_foreach(entry, fib_entry_pool,
444 n_srcs += vec_len(entry->fe_srcs);
445 vec_foreach(esrc, entry->fe_srcs)
447 n_exts += vec_len(esrc->fes_path_exts);
451 fib_show_memory_usage("Entry Source",
452 n_srcs, n_srcs, sizeof(fib_entry_src_t));
453 fib_show_memory_usage("Entry Path-Extensions",
455 sizeof(fib_path_ext_t));
459 * The FIB path-list's graph node virtual function table
461 static const fib_node_vft_t fib_entry_vft = {
462 .fnv_get = fib_entry_get_node,
463 .fnv_last_lock = fib_entry_last_lock_gone,
464 .fnv_back_walk = fib_entry_back_walk_notify,
465 .fnv_mem_show = fib_entry_show_memory,
469 * @brief Contribute the set of Adjacencies that this entry forwards with
470 * to build the uRPF list of its children
473 fib_entry_contribute_urpf (fib_node_index_t entry_index,
476 fib_entry_t *fib_entry;
478 fib_entry = fib_entry_get(entry_index);
480 return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
484 * fib_entry_contribute_forwarding
486 * Get an lock the forwarding information (DPO) contributed by the FIB entry.
489 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
490 fib_forward_chain_type_t type,
493 fib_entry_t *fib_entry;
495 fib_entry = fib_entry_get(fib_entry_index);
498 * these are not the droids you are looking for...
500 type = fib_entry_chain_type_fixup(fib_entry, type);
502 if (!dpo_id_is_valid(&fib_entry->fe_lb[type]))
505 * on-demand create eos/non-eos.
506 * There is no on-demand delete because:
507 * - memory versus complexity & reliability:
508 * leaving unrequired [n]eos LB arounds wastes memory, cleaning
509 * then up on the right trigger is more code. i favour the latter.
511 fib_entry_src_mk_lb(fib_entry,
512 fib_entry_get_best_src_i(fib_entry),
514 &fib_entry->fe_lb[type]);
517 dpo_copy(dpo, &fib_entry->fe_lb[type]);
521 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
523 fib_entry_t *fib_entry;
525 fib_entry = fib_entry_get(fib_entry_index);
527 return (&fib_entry->fe_lb[fib_entry_get_default_chain_type(fib_entry)]);
531 fib_entry_get_adj (fib_node_index_t fib_entry_index)
535 dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
536 dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
540 return (dpo->dpoi_index);
542 return (ADJ_INDEX_INVALID);
546 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
548 fib_entry_t *fib_entry;
550 fib_entry = fib_entry_get(fib_entry_index);
552 return (fib_entry->fe_parent);
556 fib_entry_child_add (fib_node_index_t fib_entry_index,
557 fib_node_type_t child_type,
558 fib_node_index_t child_index)
560 return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
567 fib_entry_child_remove (fib_node_index_t fib_entry_index,
570 fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
576 fib_entry_alloc (u32 fib_index,
577 const fib_prefix_t *prefix,
578 fib_node_index_t *fib_entry_index)
580 fib_forward_chain_type_t fct;
581 fib_entry_t *fib_entry;
583 pool_get(fib_entry_pool, fib_entry);
584 memset(fib_entry, 0, sizeof(*fib_entry));
586 fib_node_init(&fib_entry->fe_node,
587 FIB_NODE_TYPE_ENTRY);
589 fib_entry->fe_fib_index = fib_index;
590 fib_entry->fe_prefix = *prefix;
591 if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
593 fib_entry->fe_prefix.fp_len = 21;
594 ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
597 fib_entry->fe_export = FIB_NODE_INDEX_INVALID;
598 fib_entry->fe_import = FIB_NODE_INDEX_INVALID;
599 fib_entry->fe_covered = FIB_NODE_INDEX_INVALID;
600 FOR_EACH_FIB_FORW_MPLS_CHAIN(fct)
602 dpo_reset(&fib_entry->fe_lb[fct]);
605 *fib_entry_index = fib_entry_get_index(fib_entry);
607 FIB_ENTRY_DBG(fib_entry, "alloc");
613 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
615 fib_entry_flag_t old_flags)
618 * handle changes to attached export for import entries
620 int is_import = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
621 int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
623 if (!was_import && is_import)
626 * transition from not exported to exported
630 * there is an assumption here that the entry resolves via only
631 * one interface and that it is the cross VRF interface.
633 u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
635 fib_attached_export_import(fib_entry,
636 fib_table_get_index_for_sw_if_index(
637 fib_entry_get_proto(fib_entry),
640 else if (was_import && !is_import)
643 * transition from exported to not exported
645 fib_attached_export_purge(fib_entry);
649 * no change. nothing to do.
653 * handle changes to attached export for export entries
655 int is_attached = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
656 int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
658 if (!was_attached && is_attached)
661 * transition to attached. time to export
669 fib_entry_post_install_actions (fib_entry_t *fib_entry,
671 fib_entry_flag_t old_flags)
673 fib_entry_post_flag_update_actions(fib_entry, source, old_flags);
674 fib_entry_src_action_installed(fib_entry, source);
678 fib_entry_create (u32 fib_index,
679 const fib_prefix_t *prefix,
681 fib_entry_flag_t flags,
682 const fib_route_path_t *paths)
684 fib_node_index_t fib_entry_index;
685 fib_entry_t *fib_entry;
687 ASSERT(0 < vec_len(paths));
689 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
692 * since this is a new entry create, we don't need to check for winning
693 * sources - there is only one.
695 fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
698 fib_entry_get_proto(fib_entry))));
699 fib_entry_src_action_path_swap(fib_entry,
704 * handle possible realloc's by refetching the pointer
706 fib_entry = fib_entry_get(fib_entry_index);
707 fib_entry_src_action_activate(fib_entry, source);
709 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
711 return (fib_entry_index);
715 fib_entry_create_special (u32 fib_index,
716 const fib_prefix_t *prefix,
718 fib_entry_flag_t flags,
721 fib_node_index_t fib_entry_index;
722 fib_entry_t *fib_entry;
725 * create and initiliase the new enty
727 fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
730 * create the path-list
732 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
733 fib_entry_src_action_activate(fib_entry, source);
735 fib_entry_post_install_actions(fib_entry, source, FIB_ENTRY_FLAG_NONE);
737 return (fib_entry_index);
741 fib_entry_post_update_actions (fib_entry_t *fib_entry,
743 fib_entry_flag_t old_flags)
746 * backwalk to children to inform then of the change to forwarding.
748 fib_node_back_walk_ctx_t bw_ctx = {
749 .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
752 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
755 * then inform any covered prefixes
757 fib_entry_cover_update_notify(fib_entry);
759 fib_entry_post_install_actions(fib_entry, source, old_flags);
763 fib_entry_source_change (fib_entry_t *fib_entry,
764 fib_source_t best_source,
765 fib_source_t new_source,
766 fib_entry_flag_t old_flags)
769 * if the path list for the source passed is invalid,
770 * then we need to create a new one. else we are updating
773 if (new_source < best_source)
776 * we have a new winning source.
778 fib_entry_src_action_deactivate(fib_entry, best_source);
779 fib_entry_src_action_activate(fib_entry, new_source);
781 else if (new_source > best_source)
784 * the new source loses. nothing to do here.
785 * the data from the source is saved in the path-list created
792 * the new source is one this entry already has.
793 * But the path-list was updated, which will contribute new forwarding,
796 fib_entry_src_action_deactivate(fib_entry, new_source);
797 fib_entry_src_action_activate(fib_entry, new_source);
800 fib_entry_post_update_actions(fib_entry, new_source, old_flags);
804 fib_entry_special_add (fib_node_index_t fib_entry_index,
806 fib_entry_flag_t flags,
809 fib_source_t best_source;
810 fib_entry_flag_t bflags;
811 fib_entry_t *fib_entry;
812 fib_entry_src_t *bsrc;
814 fib_entry = fib_entry_get(fib_entry_index);
816 bsrc = fib_entry_get_best_src_i(fib_entry);
817 best_source = fib_entry_src_get_source(bsrc);
818 bflags = fib_entry_src_get_flags(bsrc);
820 fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
821 fib_entry_source_change(fib_entry, best_source, source, bflags);
825 fib_entry_special_update (fib_node_index_t fib_entry_index,
827 fib_entry_flag_t flags,
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 fib_entry = fib_entry_get(fib_entry_index);
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_update(fib_entry, source, flags, dpo);
842 fib_entry_source_change(fib_entry, best_source, source, bflags);
847 fib_entry_path_add (fib_node_index_t fib_entry_index,
849 fib_entry_flag_t flags,
850 const fib_route_path_t *rpath)
852 fib_source_t best_source;
853 fib_entry_flag_t bflags;
854 fib_entry_t *fib_entry;
855 fib_entry_src_t *bsrc;
857 ASSERT(1 == vec_len(rpath));
859 fib_entry = fib_entry_get(fib_entry_index);
860 ASSERT(NULL != fib_entry);
862 bsrc = fib_entry_get_best_src_i(fib_entry);
863 best_source = fib_entry_src_get_source(bsrc);
864 bflags = fib_entry_src_get_flags(bsrc);
866 fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpath);
869 * if the path list for the source passed is invalid,
870 * then we need to create a new one. else we are updating
873 if (source < best_source)
876 * we have a new winning source.
878 fib_entry_src_action_deactivate(fib_entry, best_source);
879 fib_entry_src_action_activate(fib_entry, source);
881 else if (source > best_source)
884 * the new source loses. nothing to do here.
885 * the data from the source is saved in the path-list created
892 * the new source is one this entry already has.
893 * But the path-list was updated, which will contribute new forwarding,
896 fib_entry_src_action_deactivate(fib_entry, source);
897 fib_entry_src_action_activate(fib_entry, source);
900 fib_entry_post_update_actions(fib_entry, source, bflags);
904 * fib_entry_path_remove
906 * remove a path from the entry.
907 * return the fib_entry's index if it is still present, INVALID otherwise.
910 fib_entry_path_remove (fib_node_index_t fib_entry_index,
912 const fib_route_path_t *rpath)
914 fib_entry_src_flag_t sflag;
915 fib_source_t best_source;
916 fib_entry_flag_t bflags;
917 fib_entry_t *fib_entry;
918 fib_entry_src_t *bsrc;
920 ASSERT(1 == vec_len(rpath));
922 fib_entry = fib_entry_get(fib_entry_index);
923 ASSERT(NULL != fib_entry);
925 bsrc = fib_entry_get_best_src_i(fib_entry);
926 best_source = fib_entry_src_get_source(bsrc);
927 bflags = fib_entry_src_get_flags(bsrc);
929 sflag = fib_entry_src_action_path_remove(fib_entry, source, rpath);
932 * if the path list for the source passed is invalid,
933 * then we need to create a new one. else we are updating
936 if (source < best_source )
939 * Que! removing a path from a source that is better than the
940 * one this entry is using.
944 else if (source > best_source )
947 * the source is not the best. nothing to do.
949 return (FIB_ENTRY_SRC_FLAG_ADDED);
954 * removing a path from the path-list we were using.
956 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
959 * the last path from the source was removed.
960 * fallback to lower source
962 bsrc = fib_entry_get_best_src_i(fib_entry);
963 best_source = fib_entry_src_get_source(bsrc);
965 if (FIB_SOURCE_MAX == best_source) {
967 * no more sources left. this entry is toast.
969 fib_entry_src_action_uninstall(fib_entry);
970 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
972 return (FIB_ENTRY_SRC_FLAG_NONE);
976 fib_entry_src_action_activate(fib_entry, best_source);
977 source = best_source;
983 * re-install the new forwarding information
985 fib_entry_src_action_deactivate(fib_entry, source);
986 fib_entry_src_action_activate(fib_entry, source);
990 fib_entry_post_update_actions(fib_entry, source, bflags);
995 return (FIB_ENTRY_SRC_FLAG_ADDED);
999 * fib_entry_special_remove
1001 * remove a special source from the entry.
1002 * return the fib_entry's index if it is still present, INVALID otherwise.
1004 fib_entry_src_flag_t
1005 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1006 fib_source_t source)
1008 fib_entry_src_flag_t sflag;
1009 fib_source_t best_source;
1010 fib_entry_flag_t bflags;
1011 fib_entry_t *fib_entry;
1012 fib_entry_src_t *bsrc;
1014 fib_entry = fib_entry_get(fib_entry_index);
1015 ASSERT(NULL != fib_entry);
1017 bsrc = fib_entry_get_best_src_i(fib_entry);
1018 best_source = fib_entry_src_get_source(bsrc);
1019 bflags = fib_entry_src_get_flags(bsrc);
1021 sflag = fib_entry_src_action_remove(fib_entry, source);
1024 * if the path list for the source passed is invalid,
1025 * then we need to create a new one. else we are updating
1028 if (source < best_source )
1031 * Que! removing a path from a source that is better than the
1032 * one this entry is using. This can only mean it is a source
1033 * this prefix does not have.
1035 return (FIB_ENTRY_SRC_FLAG_ADDED);
1037 else if (source > best_source ) {
1039 * the source is not the best. nothing to do.
1041 return (FIB_ENTRY_SRC_FLAG_ADDED);
1045 if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1048 * the source was removed. use the next best.
1050 bsrc = fib_entry_get_best_src_i(fib_entry);
1051 best_source = fib_entry_src_get_source(bsrc);
1053 if (FIB_SOURCE_MAX == best_source) {
1055 * no more sources left. this entry is toast.
1057 fib_entry_src_action_uninstall(fib_entry);
1058 fib_entry_post_flag_update_actions(fib_entry, source, bflags);
1060 return (FIB_ENTRY_SRC_FLAG_NONE);
1064 fib_entry_src_action_activate(fib_entry, best_source);
1065 source = best_source;
1071 * re-install the new forwarding information
1073 fib_entry_src_action_reactivate(fib_entry, source);
1077 fib_entry_post_update_actions(fib_entry, source, bflags);
1080 * still have sources
1082 return (FIB_ENTRY_SRC_FLAG_ADDED);
1088 * The source is withdrawing all the paths it provided
1090 fib_entry_src_flag_t
1091 fib_entry_delete (fib_node_index_t fib_entry_index,
1092 fib_source_t source)
1094 return (fib_entry_special_remove(fib_entry_index, source));
1100 * The source has provided a new set of paths that will replace the old.
1103 fib_entry_update (fib_node_index_t fib_entry_index,
1104 fib_source_t source,
1105 fib_entry_flag_t flags,
1106 const fib_route_path_t *paths)
1108 fib_source_t best_source;
1109 fib_entry_flag_t bflags;
1110 fib_entry_t *fib_entry;
1111 fib_entry_src_t *bsrc;
1113 fib_entry = fib_entry_get(fib_entry_index);
1114 ASSERT(NULL != fib_entry);
1116 bsrc = fib_entry_get_best_src_i(fib_entry);
1117 best_source = fib_entry_src_get_source(bsrc);
1118 bflags = fib_entry_src_get_flags(bsrc);
1120 fib_entry_src_action_path_swap(fib_entry,
1125 * handle possible realloc's by refetching the pointer
1127 fib_entry = fib_entry_get(fib_entry_index);
1130 * if the path list for the source passed is invalid,
1131 * then we need to create a new one. else we are updating
1134 if (source < best_source)
1137 * we have a new winning source.
1139 fib_entry_src_action_deactivate(fib_entry, best_source);
1140 fib_entry_src_action_activate(fib_entry, source);
1142 else if (source > best_source) {
1144 * the new source loses. nothing to do here.
1145 * the data from the source is saved in the path-list created
1152 * the new source is one this entry already has.
1153 * But the path-list was updated, which will contribute new forwarding,
1156 fib_entry_src_action_deactivate(fib_entry, source);
1157 fib_entry_src_action_activate(fib_entry, source);
1160 fib_entry_post_update_actions(fib_entry, source, bflags);
1165 * fib_entry_cover_changed
1167 * this entry is tracking its cover and that cover has changed.
1170 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1172 fib_entry_src_cover_res_t res = {
1174 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1176 fib_source_t source, best_source;
1177 fib_entry_flag_t bflags;
1178 fib_entry_t *fib_entry;
1179 fib_entry_src_t *esrc;
1182 bflags = FIB_ENTRY_FLAG_NONE;
1183 best_source = FIB_SOURCE_FIRST;
1184 fib_entry = fib_entry_get(fib_entry_index);
1186 fib_attached_export_cover_change(fib_entry);
1189 * propagate the notificuation to each of the added sources
1192 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1197 * only the best source gets to set the back walk flags
1199 res = fib_entry_src_action_cover_change(fib_entry, source);
1200 bflags = fib_entry_src_get_flags(esrc);
1201 best_source = fib_entry_src_get_source(esrc);
1205 fib_entry_src_action_cover_change(fib_entry, source);
1212 fib_entry_src_action_reactivate(fib_entry,
1213 fib_entry_src_get_source(
1214 fib_entry_get_best_src_i(fib_entry)));
1215 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1219 fib_entry_src_action_uninstall(fib_entry);
1222 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1225 * time for walkies fido.
1227 fib_node_back_walk_ctx_t bw_ctx = {
1228 .fnbw_reason = res.bw_reason,
1231 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1236 * fib_entry_cover_updated
1238 * this entry is tracking its cover and that cover has been updated
1239 * (i.e. its forwarding information has changed).
1242 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1244 fib_entry_src_cover_res_t res = {
1246 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1248 fib_source_t source, best_source;
1249 fib_entry_flag_t bflags;
1250 fib_entry_t *fib_entry;
1251 fib_entry_src_t *esrc;
1254 bflags = FIB_ENTRY_FLAG_NONE;
1255 best_source = FIB_SOURCE_FIRST;
1256 fib_entry = fib_entry_get(fib_entry_index);
1258 fib_attached_export_cover_update(fib_entry);
1261 * propagate the notificuation to each of the added sources
1264 FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1269 * only the best source gets to set the back walk flags
1271 res = fib_entry_src_action_cover_update(fib_entry, source);
1272 bflags = fib_entry_src_get_flags(esrc);
1273 best_source = fib_entry_src_get_source(esrc);
1277 fib_entry_src_action_cover_update(fib_entry, source);
1284 fib_entry_src_action_reactivate(fib_entry,
1285 fib_entry_src_get_source(
1286 fib_entry_get_best_src_i(fib_entry)));
1287 fib_entry_post_install_actions(fib_entry, best_source, bflags);
1291 fib_entry_src_action_uninstall(fib_entry);
1294 if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1297 * time for walkies fido.
1299 fib_node_back_walk_ctx_t bw_ctx = {
1300 .fnbw_reason = res.bw_reason,
1303 fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1308 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1309 fib_node_index_t **entry_indicies)
1311 fib_entry_t *fib_entry;
1312 int was_looped, is_looped;
1314 fib_entry = fib_entry_get(entry_index);
1316 if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1318 fib_node_index_t *entries = *entry_indicies;
1319 fib_forward_chain_type_t fct;
1321 vec_add1(entries, entry_index);
1322 was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1323 is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1326 *entry_indicies = entries;
1328 if (!!was_looped != !!is_looped)
1331 * re-evaluate all the entry's forwarding
1332 * NOTE: this is an inplace modify
1334 FOR_EACH_FIB_FORW_MPLS_CHAIN(fct)
1336 if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
1338 fib_entry_src_mk_lb(fib_entry,
1339 fib_entry_get_best_src_i(fib_entry),
1341 &fib_entry->fe_lb[fct]);
1349 * the entry is currently not linked to a path-list. this happens
1350 * when it is this entry that is re-linking path-lists and has thus
1360 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1362 fib_entry_t *fib_entry;
1364 fib_entry = fib_entry_get(entry_index);
1366 return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1370 fib_entry_get_best_source (fib_node_index_t entry_index)
1372 fib_entry_t *fib_entry;
1373 fib_entry_src_t *bsrc;
1375 fib_entry = fib_entry_get(entry_index);
1377 bsrc = fib_entry_get_best_src_i(fib_entry);
1378 return (fib_entry_src_get_source(bsrc));
1382 fib_ip4_address_compare (ip4_address_t * a1,
1386 * IP addresses are unsiged ints. the return value here needs to be signed
1387 * a simple subtraction won't cut it.
1388 * If the addresses are the same, the sort order is undefiend, so phoey.
1390 return ((clib_net_to_host_u32(a1->data_u32) >
1391 clib_net_to_host_u32(a2->data_u32) ) ?
1396 fib_ip6_address_compare (ip6_address_t * a1,
1400 for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1402 int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1403 clib_net_to_host_u16 (a2->as_u16[i]));
1411 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1412 fib_node_index_t fib_entry_index2)
1414 fib_entry_t *fib_entry1, *fib_entry2;
1417 fib_entry1 = fib_entry_get(fib_entry_index1);
1418 fib_entry2 = fib_entry_get(fib_entry_index2);
1420 switch (fib_entry1->fe_prefix.fp_proto)
1422 case FIB_PROTOCOL_IP4:
1423 cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1424 &fib_entry2->fe_prefix.fp_addr.ip4);
1426 case FIB_PROTOCOL_IP6:
1427 cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1428 &fib_entry2->fe_prefix.fp_addr.ip6);
1430 case FIB_PROTOCOL_MPLS:
1431 cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1435 cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1441 cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1447 fib_entry_cmp_for_sort (void *i1, void *i2)
1449 fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1451 return (fib_entry_cmp(*fib_entry_index1,
1452 *fib_entry_index2));
1456 fib_entry_lock (fib_node_index_t fib_entry_index)
1458 fib_entry_t *fib_entry;
1460 fib_entry = fib_entry_get(fib_entry_index);
1462 fib_node_lock(&fib_entry->fe_node);
1466 fib_entry_unlock (fib_node_index_t fib_entry_index)
1468 fib_entry_t *fib_entry;
1470 fib_entry = fib_entry_get(fib_entry_index);
1472 fib_node_unlock(&fib_entry->fe_node);
1476 fib_entry_module_init (void)
1478 fib_node_register_type (FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1482 fib_entry_get_prefix (fib_node_index_t fib_entry_index,
1485 fib_entry_t *fib_entry;
1487 fib_entry = fib_entry_get(fib_entry_index);
1488 *pfx = fib_entry->fe_prefix;
1492 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1494 fib_entry_t *fib_entry;
1496 fib_entry = fib_entry_get(fib_entry_index);
1498 return (fib_entry->fe_fib_index);
1502 fib_entry_pool_size (void)
1504 return (pool_elts(fib_entry_pool));
1507 static clib_error_t *
1508 show_fib_entry_command (vlib_main_t * vm,
1509 unformat_input_t * input,
1510 vlib_cli_command_t * cmd)
1512 fib_node_index_t fei;
1514 if (unformat (input, "%d", &fei))
1517 * show one in detail
1519 if (!pool_is_free_index(fib_entry_pool, fei))
1521 vlib_cli_output (vm, "%d@%U",
1523 format_fib_entry, fei,
1524 FIB_ENTRY_FORMAT_DETAIL2);
1528 vlib_cli_output (vm, "entry %d invalid", fei);
1536 vlib_cli_output (vm, "FIB Entries:");
1537 pool_foreach_index(fei, fib_entry_pool,
1539 vlib_cli_output (vm, "%d@%U",
1541 format_fib_entry, fei,
1542 FIB_ENTRY_FORMAT_BRIEF);
1549 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1550 .path = "show fib entry",
1551 .function = show_fib_entry_command,
1552 .short_help = "show fib entry",