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 <vnet/adj/adj.h>
17 #include <vnet/dpo/load_balance.h>
18 #include <vnet/dpo/mpls_label_dpo.h>
19 #include <vnet/dpo/drop_dpo.h>
20 #include <vnet/dpo/replicate_dpo.h>
22 #include <vnet/fib/fib_entry_src.h>
23 #include <vnet/fib/fib_table.h>
24 #include <vnet/fib/fib_path_ext.h>
25 #include <vnet/fib/fib_urpf_list.h>
30 static fib_entry_src_vft_t fib_entry_src_vft[FIB_SOURCE_MAX];
33 fib_entry_src_register (fib_source_t source,
34 const fib_entry_src_vft_t *vft)
36 fib_entry_src_vft[source] = *vft;
40 fib_entry_src_cmp_for_sort (void * v1,
43 fib_entry_src_t *esrc1 = v1, *esrc2 = v2;
45 return (esrc1->fes_src - esrc2->fes_src);
49 fib_entry_src_action_init (fib_entry_t *fib_entry,
53 fib_entry_src_t esrc = {
54 .fes_pl = FIB_NODE_INDEX_INVALID,
55 .fes_flags = FIB_ENTRY_SRC_FLAG_NONE,
59 if (NULL != fib_entry_src_vft[source].fesv_init)
61 fib_entry_src_vft[source].fesv_init(&esrc);
64 vec_add1(fib_entry->fe_srcs, esrc);
65 vec_sort_with_function(fib_entry->fe_srcs,
66 fib_entry_src_cmp_for_sort);
69 static fib_entry_src_t *
70 fib_entry_src_find (const fib_entry_t *fib_entry,
75 fib_entry_src_t *esrc;
79 vec_foreach(esrc, fib_entry->fe_srcs)
81 if (esrc->fes_src == source)
99 fib_entry_is_sourced (fib_node_index_t fib_entry_index,
102 fib_entry_t *fib_entry;
104 fib_entry = fib_entry_get(fib_entry_index);
106 return (NULL != fib_entry_src_find(fib_entry, source, NULL));
109 static fib_entry_src_t *
110 fib_entry_src_find_or_create (fib_entry_t *fib_entry,
113 fib_entry_src_t *esrc;
115 esrc = fib_entry_src_find(fib_entry, source, NULL);
119 fib_entry_src_action_init(fib_entry, source);
122 return (fib_entry_src_find(fib_entry, source, NULL));
126 fib_entry_src_action_deinit (fib_entry_t *fib_entry,
130 fib_entry_src_t *esrc;
133 esrc = fib_entry_src_find(fib_entry, source, &index);
135 ASSERT(NULL != esrc);
137 if (NULL != fib_entry_src_vft[source].fesv_deinit)
139 fib_entry_src_vft[source].fesv_deinit(esrc);
142 fib_path_ext_list_flush(&esrc->fes_path_exts);
143 vec_del1(fib_entry->fe_srcs, index);
146 fib_entry_src_cover_res_t
147 fib_entry_src_action_cover_change (fib_entry_t *fib_entry,
150 if (NULL != fib_entry_src_vft[source].fesv_cover_change)
152 return (fib_entry_src_vft[source].fesv_cover_change(
153 fib_entry_src_find(fib_entry, source, NULL),
157 fib_entry_src_cover_res_t res = {
159 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
164 fib_entry_src_cover_res_t
165 fib_entry_src_action_cover_update (fib_entry_t *fib_entry,
168 if (NULL != fib_entry_src_vft[source].fesv_cover_update)
170 return (fib_entry_src_vft[source].fesv_cover_update(
171 fib_entry_src_find(fib_entry, source, NULL),
175 fib_entry_src_cover_res_t res = {
177 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
182 typedef struct fib_entry_src_collect_forwarding_ctx_t_
184 load_balance_path_t *next_hops;
185 const fib_entry_t *fib_entry;
186 const fib_entry_src_t *esrc;
187 fib_forward_chain_type_t fct;
188 int n_recursive_constrained;
190 } fib_entry_src_collect_forwarding_ctx_t;
193 * @brief Determine whether this FIB entry should use a load-balance MAP
194 * to support PIC edge fast convergence
197 fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx)
200 * We'll use a LB map if the path-list has multiple recursive paths.
201 * recursive paths implies BGP, and hence scale.
203 if (ctx->n_recursive_constrained > 1 &&
204 fib_path_list_is_popular(ctx->esrc->fes_pl))
206 return (LOAD_BALANCE_FLAG_USES_MAP);
208 return (LOAD_BALANCE_FLAG_NONE);
212 fib_entry_src_valid_out_label (mpls_label_t label)
214 return ((MPLS_LABEL_IS_REAL(label) ||
215 MPLS_LABEL_POP == label ||
216 MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL == label ||
217 MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL == label ||
218 MPLS_IETF_IMPLICIT_NULL_LABEL == label));
222 * @brief Turn the chain type requested by the client into the one they
225 fib_forward_chain_type_t
226 fib_entry_chain_type_fixup (const fib_entry_t *entry,
227 fib_forward_chain_type_t fct)
230 * The EOS chain is a tricky since one cannot know the adjacency
231 * to link to without knowing what the packets payload protocol
232 * will be once the label is popped.
234 fib_forward_chain_type_t dfct;
236 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS != fct)
241 dfct = fib_entry_get_default_chain_type(entry);
243 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS == dfct)
246 * If the entry being asked is a eos-MPLS label entry,
247 * then use the payload-protocol field, that we stashed there
248 * for just this purpose
250 return (fib_forw_chain_type_from_dpo_proto(
251 entry->fe_prefix.fp_payload_proto));
254 * else give them what this entry would be by default. i.e. if it's a v6
255 * entry, then the label its local labelled should be carrying v6 traffic.
256 * If it's a non-EOS label entry, then there are more labels and we want
263 fib_prefix_get_payload_proto (const fib_prefix_t *pfx)
265 switch (pfx->fp_proto)
267 case FIB_PROTOCOL_IP4:
268 return (DPO_PROTO_IP4);
269 case FIB_PROTOCOL_IP6:
270 return (DPO_PROTO_IP6);
271 case FIB_PROTOCOL_MPLS:
272 return (pfx->fp_payload_proto);
276 return (DPO_PROTO_IP4);
280 fib_entry_src_get_path_forwarding (fib_node_index_t path_index,
281 fib_entry_src_collect_forwarding_ctx_t *ctx)
283 load_balance_path_t *nh;
286 * no extension => no out-going label for this path. that's OK
287 * in the case of an IP or EOS chain, but not for non-EOS
291 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
292 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
293 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
294 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
295 case FIB_FORW_CHAIN_TYPE_BIER:
297 * EOS traffic with no label to stack, we need the IP Adj
299 vec_add2(ctx->next_hops, nh, 1);
301 nh->path_index = path_index;
302 nh->path_weight = fib_path_get_weight(path_index);
303 fib_path_contribute_forwarding(path_index, ctx->fct, &nh->path_dpo);
306 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
307 if (fib_path_is_exclusive(path_index) ||
308 fib_path_is_deag(path_index))
310 vec_add2(ctx->next_hops, nh, 1);
312 nh->path_index = path_index;
313 nh->path_weight = fib_path_get_weight(path_index);
314 fib_path_contribute_forwarding(path_index,
315 FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
319 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
322 * no label. we need a chain based on the payload. fixup.
324 vec_add2(ctx->next_hops, nh, 1);
326 nh->path_index = path_index;
327 nh->path_weight = fib_path_get_weight(path_index);
328 fib_path_contribute_forwarding(path_index,
329 fib_entry_chain_type_fixup(ctx->fib_entry,
332 fib_path_stack_mpls_disp(path_index,
333 fib_prefix_get_payload_proto(&ctx->fib_entry->fe_prefix),
334 FIB_MPLS_LSP_MODE_PIPE,
339 case FIB_FORW_CHAIN_TYPE_ETHERNET:
340 case FIB_FORW_CHAIN_TYPE_NSH:
346 static fib_path_list_walk_rc_t
347 fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
348 fib_node_index_t path_index,
351 fib_entry_src_collect_forwarding_ctx_t *ctx;
352 fib_path_ext_t *path_ext;
357 * if the path is not resolved, don't include it.
359 if (!fib_path_is_resolved(path_index))
361 return (FIB_PATH_LIST_WALK_CONTINUE);
364 if (fib_path_is_recursive_constrained(path_index))
366 ctx->n_recursive_constrained += 1;
368 if (0xffff == ctx->preference)
371 * not set a preference yet, so the first path we encounter
372 * sets the preference we are collecting.
374 ctx->preference = fib_path_get_preference(path_index);
376 else if (ctx->preference != fib_path_get_preference(path_index))
379 * this path does not belong to the same preference as the
380 * previous paths encountered. we are done now.
382 return (FIB_PATH_LIST_WALK_STOP);
386 * get the matching path-extension for the path being visited.
388 path_ext = fib_path_ext_list_find_by_path_index(&ctx->esrc->fes_path_exts,
391 if (NULL != path_ext)
393 switch (path_ext->fpe_type)
395 case FIB_PATH_EXT_MPLS:
396 if (fib_entry_src_valid_out_label(path_ext->fpe_label_stack[0].fml_value))
399 * found a matching extension. stack it to obtain the forwarding
400 * info for this path.
403 fib_path_ext_stack(path_ext,
405 fib_entry_chain_type_fixup(ctx->fib_entry,
411 fib_entry_src_get_path_forwarding(path_index, ctx);
414 case FIB_PATH_EXT_ADJ:
415 if (FIB_PATH_EXT_ADJ_FLAG_REFINES_COVER & path_ext->fpe_adj_flags)
417 fib_entry_src_get_path_forwarding(path_index, ctx);
421 * the path does not refine the cover, meaning that
422 * the adjacency doesdoes not match the sub-net on the link.
423 * So this path does not contribute forwarding.
430 fib_entry_src_get_path_forwarding(path_index, ctx);
433 return (FIB_PATH_LIST_WALK_CONTINUE);
437 fib_entry_src_mk_lb (fib_entry_t *fib_entry,
438 const fib_entry_src_t *esrc,
439 fib_forward_chain_type_t fct,
442 dpo_proto_t lb_proto;
445 * If the entry has path extensions then we construct a load-balance
446 * by stacking the extensions on the forwarding chains of the paths.
447 * Otherwise we use the load-balance of the path-list
449 fib_entry_src_collect_forwarding_ctx_t ctx = {
451 .fib_entry = fib_entry,
453 .n_recursive_constrained = 0,
455 .preference = 0xffff,
459 * As an optimisation we allocate the vector of next-hops to be sized
460 * equal to the maximum nuber of paths we will need, which is also the
461 * most likely number we will need, since in most cases the paths are 'up'.
463 vec_validate(ctx.next_hops, fib_path_list_get_n_paths(esrc->fes_pl));
464 vec_reset_length(ctx.next_hops);
466 lb_proto = fib_forw_chain_type_to_dpo_proto(fct);
468 fib_path_list_walk(esrc->fes_pl,
469 fib_entry_src_collect_forwarding,
472 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE)
475 * the client provided the DPO that the entry should link to.
476 * all entries must link to a LB, so if it is an LB already
477 * then we can use it.
479 if ((1 == vec_len(ctx.next_hops)) &&
480 (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type))
482 dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo);
483 dpo_reset(&ctx.next_hops[0].path_dpo);
488 if (!dpo_id_is_valid(dpo_lb))
493 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
498 MPLS_IS_REPLICATE | replicate_create(0, lb_proto));
502 fib_protocol_t flow_hash_proto;
503 flow_hash_config_t fhc;
506 * if the protocol for the LB we are building does not match that
507 * of the fib_entry (i.e. we are build the [n]EOS LB for an IPv[46]
508 * then the fib_index is not an index that relates to the table
509 * type we need. So get the default flow-hash config instead.
511 flow_hash_proto = dpo_proto_to_fib(lb_proto);
512 if (fib_entry->fe_prefix.fp_proto != flow_hash_proto)
514 fhc = fib_table_get_default_flow_hash_config(flow_hash_proto);
518 fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index,
525 load_balance_create(0, lb_proto, fhc));
529 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
534 replicate_multipath_update(dpo_lb, ctx.next_hops);
538 load_balance_multipath_update(dpo_lb,
540 fib_entry_calc_lb_flags(&ctx));
541 vec_free(ctx.next_hops);
544 * if this entry is sourced by the uRPF-exempt source then we
545 * append the always present local0 interface (index 0) to the
546 * uRPF list so it is not empty. that way packets pass the loose check.
548 index_t ui = fib_path_list_get_urpf(esrc->fes_pl);
550 if ((fib_entry_is_sourced(fib_entry_get_index(fib_entry),
551 FIB_SOURCE_URPF_EXEMPT) ||
552 (esrc->fes_entry_flags & FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT))&&
553 (0 == fib_urpf_check_size(ui)))
556 * The uRPF list we get from the path-list is shared by all
557 * other users of the list, but the uRPF exemption applies
558 * only to this prefix. So we need our own list.
560 ui = fib_urpf_list_alloc_and_lock();
561 fib_urpf_list_append(ui, 0);
562 fib_urpf_list_bake(ui);
563 load_balance_set_urpf(dpo_lb->dpoi_index, ui);
564 fib_urpf_list_unlock(ui);
568 load_balance_set_urpf(dpo_lb->dpoi_index, ui);
570 load_balance_set_fib_entry_flags(dpo_lb->dpoi_index,
571 fib_entry_get_flags_i(fib_entry));
576 fib_entry_src_action_install (fib_entry_t *fib_entry,
580 * Install the forwarding chain for the given source into the forwarding
583 fib_forward_chain_type_t fct;
584 fib_entry_src_t *esrc;
587 fct = fib_entry_get_default_chain_type(fib_entry);
588 esrc = fib_entry_src_find(fib_entry, source, NULL);
591 * Every entry has its own load-balance object. All changes to the entry's
592 * forwarding result in an inplace modify of the load-balance. This means
593 * the load-balance object only needs to be added to the forwarding
594 * DB once, when it is created.
596 insert = !dpo_id_is_valid(&fib_entry->fe_lb);
598 fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb);
600 ASSERT(dpo_id_is_valid(&fib_entry->fe_lb));
601 FIB_ENTRY_DBG(fib_entry, "install: %d", fib_entry->fe_lb);
604 * insert the adj into the data-plane forwarding trie
608 fib_table_fwding_dpo_update(fib_entry->fe_fib_index,
609 &fib_entry->fe_prefix,
614 * if any of the other chain types are already created they will need
617 fib_entry_delegate_type_t fdt;
618 fib_entry_delegate_t *fed;
620 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
622 fib_entry_src_mk_lb(fib_entry, esrc,
623 fib_entry_delegate_type_to_chain_type(fdt),
629 fib_entry_src_action_uninstall (fib_entry_t *fib_entry)
632 * uninstall the forwarding chain from the forwarding tables
634 FIB_ENTRY_DBG(fib_entry, "uninstall: %d",
635 fib_entry->fe_adj_index);
637 if (dpo_id_is_valid(&fib_entry->fe_lb))
639 fib_table_fwding_dpo_remove(
640 fib_entry->fe_fib_index,
641 &fib_entry->fe_prefix,
644 dpo_reset(&fib_entry->fe_lb);
649 fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
651 fib_node_index_t *entries = NULL;
653 fib_path_list_recursive_loop_detect(path_list_index, &entries);
659 * fib_entry_src_action_copy
661 * copy a source data from another entry to this one
664 fib_entry_src_action_copy (fib_entry_t *fib_entry,
665 const fib_entry_src_t *orig_src)
667 fib_entry_src_t *esrc;
669 esrc = fib_entry_src_find_or_create(fib_entry, orig_src->fes_src);
672 esrc->fes_ref_count = 1;
673 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_INHERITED;
674 esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
675 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
678 * the source owns a lock on the entry
680 fib_path_list_lock(esrc->fes_pl);
681 fib_entry_lock(fib_entry_get_index(fib_entry));
687 * fib_entry_src_action_update
689 * copy a source data from another entry to this one
691 static fib_entry_src_t *
692 fib_entry_src_action_update_from_cover (fib_entry_t *fib_entry,
693 const fib_entry_src_t *orig_src)
695 fib_entry_src_t *esrc;
697 esrc = fib_entry_src_find_or_create(fib_entry, orig_src->fes_src);
700 * the source owns a lock on the entry
702 fib_path_list_unlock(esrc->fes_pl);
703 esrc->fes_pl = orig_src->fes_pl;
704 fib_path_list_lock(esrc->fes_pl);
709 static fib_table_walk_rc_t
710 fib_entry_src_covered_inherit_add_i (fib_entry_t *fib_entry,
711 const fib_entry_src_t *cover_src)
713 fib_entry_src_t *esrc;
715 esrc = fib_entry_src_find(fib_entry, cover_src->fes_src, NULL);
717 if (cover_src == esrc)
719 return (FIB_TABLE_WALK_CONTINUE);
725 * the covered entry already has this source.
727 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
730 * the covered source is itself a COVERED_INHERIT, i.e.
731 * it also pushes this source down the sub-tree.
732 * We consider this more specfic covered to be the owner
733 * of the sub-tree from this point down.
735 return (FIB_TABLE_WALK_SUB_TREE_STOP);
737 if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
740 * The covered's source data has been inherited, presumably
741 * from this cover, i.e. this is a modify.
743 esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
744 fib_entry_source_change(fib_entry, esrc->fes_src, esrc->fes_src);
749 * The covered's source was not inherited and it is also
750 * not inherting. Nevertheless, it still owns the sub-tree from
753 return (FIB_TABLE_WALK_SUB_TREE_STOP);
759 * The covered does not have this source - add it.
761 fib_source_t best_source;
763 best_source = fib_entry_get_best_source(
764 fib_entry_get_index(fib_entry));
766 fib_entry_src_action_copy(fib_entry, cover_src);
767 fib_entry_source_change(fib_entry, best_source, cover_src->fes_src);
770 return (FIB_TABLE_WALK_CONTINUE);
773 static fib_table_walk_rc_t
774 fib_entry_src_covered_inherit_walk_add (fib_node_index_t fei,
777 return (fib_entry_src_covered_inherit_add_i(fib_entry_get(fei), ctx));
780 static fib_table_walk_rc_t
781 fib_entry_src_covered_inherit_walk_remove (fib_node_index_t fei,
784 fib_entry_src_t *cover_src, *esrc;
785 fib_entry_t *fib_entry;
787 fib_entry = fib_entry_get(fei);
790 esrc = fib_entry_src_find(fib_entry, cover_src->fes_src, NULL);
792 if (cover_src == esrc)
794 return (FIB_TABLE_WALK_CONTINUE);
800 * the covered entry already has this source.
802 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
805 * the covered source is itself a COVERED_INHERIT, i.e.
806 * it also pushes this source down the sub-tree.
807 * We consider this more specfic covered to be the owner
808 * of the sub-tree from this point down.
810 return (FIB_TABLE_WALK_SUB_TREE_STOP);
812 if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
815 * The covered's source data has been inherited, presumably
818 fib_entry_src_flag_t remaining;
820 remaining = fib_entry_special_remove(fei, cover_src->fes_src);
822 ASSERT(FIB_ENTRY_SRC_FLAG_ADDED == remaining);
827 * The covered's source was not inherited and it is also
828 * not inherting. Nevertheless, it still owns the sub-tree from
831 return (FIB_TABLE_WALK_SUB_TREE_STOP);
837 * The covered does not have this source - that's an error,
838 * since it should have inherited, but there is nothing we can do
842 return (FIB_TABLE_WALK_CONTINUE);
846 fib_entry_src_inherit (const fib_entry_t *cover,
847 fib_entry_t *covered)
849 CLIB_UNUSED(fib_source_t source);
850 const fib_entry_src_t *src;
852 FOR_EACH_SRC_ADDED(cover, src, source,
854 if ((src->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
855 (src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
857 fib_entry_src_covered_inherit_add_i(covered, src);
863 fib_entry_src_covered_inherit_add (fib_entry_t *fib_entry,
867 fib_entry_src_t *esrc;
869 esrc = fib_entry_src_find(fib_entry, source, NULL);
871 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
873 if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
874 (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
876 fib_table_sub_tree_walk(fib_entry->fe_fib_index,
877 fib_entry->fe_prefix.fp_proto,
878 &fib_entry->fe_prefix,
879 fib_entry_src_covered_inherit_walk_add,
885 fib_entry_src_covered_inherit_remove (fib_entry_t *fib_entry,
886 fib_entry_src_t *esrc)
889 ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
891 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
893 fib_table_sub_tree_walk(fib_entry->fe_fib_index,
894 fib_entry->fe_prefix.fp_proto,
895 &fib_entry->fe_prefix,
896 fib_entry_src_covered_inherit_walk_remove,
902 fib_entry_src_action_activate (fib_entry_t *fib_entry,
906 int houston_we_are_go_for_install;
907 fib_entry_src_t *esrc;
909 esrc = fib_entry_src_find(fib_entry, source, NULL);
911 ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
912 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
914 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE;
916 if (NULL != fib_entry_src_vft[source].fesv_activate)
918 houston_we_are_go_for_install =
919 fib_entry_src_vft[source].fesv_activate(esrc, fib_entry);
924 * the source is not providing an activate function, we'll assume
925 * therefore it has no objection to installing the entry
927 houston_we_are_go_for_install = !0;
931 * link to the path-list provided by the source, and go check
932 * if that forms any loops in the graph.
934 fib_entry->fe_parent = esrc->fes_pl;
935 fib_entry->fe_sibling =
936 fib_path_list_child_add(fib_entry->fe_parent,
938 fib_entry_get_index(fib_entry));
940 fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
942 FIB_ENTRY_DBG(fib_entry, "activate: %d",
943 fib_entry->fe_parent);
946 * If this source should push its state to covered prefixs, do that now.
948 fib_entry_src_covered_inherit_add(fib_entry, source);
950 if (0 != houston_we_are_go_for_install)
952 fib_entry_src_action_install(fib_entry, source);
956 fib_entry_src_action_uninstall(fib_entry);
961 fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
965 fib_node_index_t path_list_index;
966 fib_entry_src_t *esrc;
968 esrc = fib_entry_src_find(fib_entry, source, NULL);
970 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
972 if (NULL != fib_entry_src_vft[source].fesv_deactivate)
974 fib_entry_src_vft[source].fesv_deactivate(esrc, fib_entry);
977 esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
979 FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
982 * If this source should pull its state from covered prefixs, do that now.
983 * If this source also has the INHERITED flag set then it has a cover
984 * that wants to push down forwarding. We only want the covereds to see
987 fib_entry_src_covered_inherit_remove(fib_entry, esrc);
990 * un-link from an old path-list. Check for any loops this will clear
992 path_list_index = fib_entry->fe_parent;
993 fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
995 fib_entry_recursive_loop_detect_i(path_list_index);
998 * this will unlock the path-list, so it may be invalid thereafter.
1000 fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
1001 fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
1005 fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
1006 fib_source_t source)
1008 fib_entry_src_t *esrc;
1010 vec_foreach(esrc, fib_entry->fe_srcs)
1012 if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update)
1014 fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc,
1022 fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
1023 fib_source_t source)
1025 fib_node_index_t path_list_index;
1026 fib_entry_src_t *esrc;
1028 esrc = fib_entry_src_find(fib_entry, source, NULL);
1030 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
1032 FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
1033 fib_entry->fe_parent,
1036 if (fib_entry->fe_parent != esrc->fes_pl)
1038 int remain_installed;
1041 * un-link from an old path-list. Check for any loops this will clear
1043 path_list_index = fib_entry->fe_parent;
1044 fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
1047 * temporary lock so it doesn't get deleted when this entry is no
1050 fib_path_list_lock(path_list_index);
1053 * this entry is no longer a child. after unlinking check if any loops
1056 fib_path_list_child_remove(path_list_index,
1057 fib_entry->fe_sibling);
1059 fib_entry_recursive_loop_detect_i(path_list_index);
1062 * link to the path-list provided by the source, and go check
1063 * if that forms any loops in the graph.
1065 fib_entry->fe_parent = esrc->fes_pl;
1066 fib_entry->fe_sibling =
1067 fib_path_list_child_add(fib_entry->fe_parent,
1068 FIB_NODE_TYPE_ENTRY,
1069 fib_entry_get_index(fib_entry));
1071 fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
1072 fib_path_list_unlock(path_list_index);
1075 * call the source to reactive and get the go/no-go to remain installed
1077 if (NULL != fib_entry_src_vft[source].fesv_reactivate)
1080 fib_entry_src_vft[source].fesv_reactivate(esrc, fib_entry);
1084 remain_installed = 1;
1088 * If this source should push its state to covered prefixs, do that now.
1090 fib_entry_src_covered_inherit_add(fib_entry, source);
1092 if (!remain_installed)
1094 fib_entry_src_action_uninstall(fib_entry);
1098 fib_entry_src_action_install(fib_entry, source);
1099 fib_entry_src_action_fwd_update(fib_entry, source);
1103 fib_entry_src_action_installed (const fib_entry_t *fib_entry,
1104 fib_source_t source)
1106 fib_entry_src_t *esrc;
1108 esrc = fib_entry_src_find(fib_entry, source, NULL);
1110 if (NULL != fib_entry_src_vft[source].fesv_installed)
1112 fib_entry_src_vft[source].fesv_installed(esrc,
1116 fib_entry_src_action_fwd_update(fib_entry, source);
1120 * fib_entry_src_action_add
1122 * Adding a source can result in a new fib_entry being created, which
1123 * can inturn mean the pool is realloc'd and thus the entry passed as
1124 * an argument it also realloc'd
1125 * @return the original entry
1128 fib_entry_src_action_add (fib_entry_t *fib_entry,
1129 fib_source_t source,
1130 fib_entry_flag_t flags,
1131 const dpo_id_t *dpo)
1133 fib_node_index_t fib_entry_index;
1134 fib_entry_src_t *esrc;
1136 esrc = fib_entry_src_find_or_create(fib_entry, source);
1138 esrc->fes_ref_count++;
1140 if (1 != esrc->fes_ref_count)
1143 * we only want to add the source on the 0->1 transition
1148 esrc->fes_entry_flags = flags;
1151 * save variable so we can recover from a fib_entry realloc.
1153 fib_entry_index = fib_entry_get_index(fib_entry);
1155 if (NULL != fib_entry_src_vft[source].fesv_add)
1157 fib_entry_src_vft[source].fesv_add(esrc,
1160 fib_entry_get_dpo_proto(fib_entry),
1164 fib_entry = fib_entry_get(fib_entry_index);
1166 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1168 fib_path_list_lock(esrc->fes_pl);
1171 * the source owns a lock on the entry
1173 fib_entry_lock(fib_entry_get_index(fib_entry));
1179 * fib_entry_src_action_update
1181 * Adding a source can result in a new fib_entry being created, which
1182 * can inturn mean the pool is realloc'd and thus the entry passed as
1183 * an argument it also realloc'd
1184 * @return the original entry
1187 fib_entry_src_action_update (fib_entry_t *fib_entry,
1188 fib_source_t source,
1189 fib_entry_flag_t flags,
1190 const dpo_id_t *dpo)
1192 fib_node_index_t fib_entry_index, old_path_list_index;
1193 fib_entry_src_t *esrc;
1195 esrc = fib_entry_src_find_or_create(fib_entry, source);
1199 return (fib_entry_src_action_add(fib_entry, source, flags, dpo));
1202 old_path_list_index = esrc->fes_pl;
1203 esrc->fes_entry_flags = flags;
1206 * save variable so we can recover from a fib_entry realloc.
1208 fib_entry_index = fib_entry_get_index(fib_entry);
1210 if (NULL != fib_entry_src_vft[source].fesv_add)
1212 fib_entry_src_vft[source].fesv_add(esrc,
1215 fib_entry_get_dpo_proto(fib_entry),
1219 fib_entry = fib_entry_get(fib_entry_index);
1221 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1223 fib_path_list_lock(esrc->fes_pl);
1224 fib_path_list_unlock(old_path_list_index);
1229 fib_entry_src_flag_t
1230 fib_entry_src_action_remove_or_update_inherit (fib_entry_t *fib_entry,
1231 fib_source_t source)
1233 fib_entry_src_t *esrc;
1235 esrc = fib_entry_src_find(fib_entry, source, NULL);
1238 return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1240 if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) &&
1241 (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
1243 fib_entry_src_t *cover_src;
1244 fib_node_index_t coveri;
1248 * this source was pushing inherited state, but so is its
1249 * cover. Now that this source is going away, we need to
1250 * pull the covers forwarding and use it to update the covereds.
1251 * Go grab the path-list from the cover, rather than start a walk from
1252 * the cover, so we don't recursively update this entry.
1254 coveri = fib_table_get_less_specific(fib_entry->fe_fib_index,
1255 &fib_entry->fe_prefix);
1258 * only the default route has itself as its own cover, but the
1259 * default route cannot have inherited from something else.
1261 ASSERT(coveri != fib_entry_get_index(fib_entry));
1263 cover = fib_entry_get(coveri);
1264 cover_src = fib_entry_src_find(cover, source, NULL);
1266 ASSERT(NULL != cover_src);
1268 esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
1269 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
1272 * Now push the new state from the cover down to the covereds
1274 fib_entry_src_covered_inherit_add(fib_entry, source);
1276 return (esrc->fes_flags);
1280 return (fib_entry_src_action_remove(fib_entry, source));
1284 fib_entry_src_flag_t
1285 fib_entry_src_action_remove (fib_entry_t *fib_entry,
1286 fib_source_t source)
1289 fib_node_index_t old_path_list;
1290 fib_entry_src_flag_t sflags;
1291 fib_entry_src_t *esrc;
1293 esrc = fib_entry_src_find(fib_entry, source, NULL);
1296 return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1298 esrc->fes_ref_count--;
1299 sflags = esrc->fes_flags;
1301 if (0 != esrc->fes_ref_count)
1304 * only remove the source on the 1->0 transisition
1309 if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
1311 fib_entry_src_action_deactivate(fib_entry, source);
1314 old_path_list = esrc->fes_pl;
1316 if (NULL != fib_entry_src_vft[source].fesv_remove)
1318 fib_entry_src_vft[source].fesv_remove(esrc);
1321 fib_path_list_unlock(old_path_list);
1322 fib_entry_unlock(fib_entry_get_index(fib_entry));
1324 sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
1325 fib_entry_src_action_deinit(fib_entry, source);
1331 * fib_route_attached_cross_table
1333 * Return true the the route is attached via an interface that
1334 * is not in the same table as the route
1337 fib_route_attached_cross_table (const fib_entry_t *fib_entry,
1338 const fib_route_path_t *rpath)
1341 * - All zeros next-hop
1342 * - a valid interface
1343 * - entry's fib index not equeal to interface's index
1345 if (ip46_address_is_zero(&rpath->frp_addr) &&
1346 (~0 != rpath->frp_sw_if_index) &&
1347 (fib_entry->fe_fib_index !=
1348 fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
1349 rpath->frp_sw_if_index)))
1357 * Return true if the path is attached
1360 fib_path_is_attached (const fib_route_path_t *rpath)
1363 * - All zeros next-hop
1364 * - a valid interface
1366 if (ip46_address_is_zero(&rpath->frp_addr) &&
1367 (~0 != rpath->frp_sw_if_index))
1371 else if (rpath->frp_flags & FIB_ROUTE_PATH_ATTACHED)
1378 fib_path_list_flags_t
1379 fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
1381 fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
1383 if (eflags & FIB_ENTRY_FLAG_DROP)
1385 plf |= FIB_PATH_LIST_FLAG_DROP;
1387 if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
1389 plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
1391 if (eflags & FIB_ENTRY_FLAG_LOCAL)
1393 plf |= FIB_PATH_LIST_FLAG_LOCAL;
1400 fib_entry_flags_update (const fib_entry_t *fib_entry,
1401 const fib_route_path_t *rpath,
1402 fib_path_list_flags_t *pl_flags,
1403 fib_entry_src_t *esrc)
1405 if ((esrc->fes_src == FIB_SOURCE_API) ||
1406 (esrc->fes_src == FIB_SOURCE_CLI))
1408 if (fib_path_is_attached(rpath))
1410 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
1414 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
1416 if (rpath->frp_flags & FIB_ROUTE_PATH_DEAG)
1418 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT;
1421 if (fib_route_attached_cross_table(fib_entry, rpath) &&
1422 !(esrc->fes_entry_flags & FIB_ENTRY_FLAG_NO_ATTACHED_EXPORT))
1424 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
1428 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
1433 * fib_entry_src_action_add
1435 * Adding a source can result in a new fib_entry being created, which
1436 * can inturn mean the pool is realloc'd and thus the entry passed as
1437 * an argument it also realloc'd
1441 fib_entry_src_action_path_add (fib_entry_t *fib_entry,
1442 fib_source_t source,
1443 fib_entry_flag_t flags,
1444 const fib_route_path_t *rpath)
1446 fib_node_index_t old_path_list, fib_entry_index;
1447 fib_path_list_flags_t pl_flags;
1448 fib_entry_src_t *esrc;
1451 * save variable so we can recover from a fib_entry realloc.
1453 fib_entry_index = fib_entry_get_index(fib_entry);
1455 esrc = fib_entry_src_find(fib_entry, source, NULL);
1459 fib_entry_src_action_add(fib_entry,
1463 fib_entry_get_dpo_proto(fib_entry)));
1464 esrc = fib_entry_src_find(fib_entry, source, NULL);
1468 * we are no doubt modifying a path-list. If the path-list
1469 * is shared, and hence not modifiable, then the index returned
1470 * will be for a different path-list. This FIB entry to needs
1471 * to maintain its lock appropriately.
1473 old_path_list = esrc->fes_pl;
1475 ASSERT(NULL != fib_entry_src_vft[source].fesv_path_add);
1477 pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1478 fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1480 fib_entry_src_vft[source].fesv_path_add(esrc, fib_entry, pl_flags, rpath);
1481 fib_entry = fib_entry_get(fib_entry_index);
1483 fib_path_list_lock(esrc->fes_pl);
1484 fib_path_list_unlock(old_path_list);
1490 * fib_entry_src_action_swap
1492 * The source is providing new paths to replace the old ones.
1493 * Adding a source can result in a new fib_entry being created, which
1494 * can inturn mean the pool is realloc'd and thus the entry passed as
1495 * an argument it also realloc'd
1499 fib_entry_src_action_path_swap (fib_entry_t *fib_entry,
1500 fib_source_t source,
1501 fib_entry_flag_t flags,
1502 const fib_route_path_t *rpaths)
1504 fib_node_index_t old_path_list, fib_entry_index;
1505 fib_path_list_flags_t pl_flags;
1506 const fib_route_path_t *rpath;
1507 fib_entry_src_t *esrc;
1509 esrc = fib_entry_src_find(fib_entry, source, NULL);
1512 * save variable so we can recover from a fib_entry realloc.
1514 fib_entry_index = fib_entry_get_index(fib_entry);
1518 fib_entry = fib_entry_src_action_add(fib_entry,
1522 fib_entry_get_dpo_proto(fib_entry)));
1523 esrc = fib_entry_src_find(fib_entry, source, NULL);
1527 esrc->fes_entry_flags = flags;
1531 * swapping paths may create a new path-list (or may use an existing shared)
1532 * but we are certainly getting a different one. This FIB entry to needs
1533 * to maintain its lock appropriately.
1535 old_path_list = esrc->fes_pl;
1537 ASSERT(NULL != fib_entry_src_vft[source].fesv_path_swap);
1539 pl_flags = fib_entry_src_flags_2_path_list_flags(flags);
1541 vec_foreach(rpath, rpaths)
1543 fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1546 fib_entry_src_vft[source].fesv_path_swap(esrc,
1551 fib_entry = fib_entry_get(fib_entry_index);
1553 fib_path_list_lock(esrc->fes_pl);
1554 fib_path_list_unlock(old_path_list);
1559 fib_entry_src_flag_t
1560 fib_entry_src_action_path_remove (fib_entry_t *fib_entry,
1561 fib_source_t source,
1562 const fib_route_path_t *rpath)
1564 fib_path_list_flags_t pl_flags;
1565 fib_node_index_t old_path_list;
1566 fib_entry_src_t *esrc;
1568 esrc = fib_entry_src_find(fib_entry, source, NULL);
1570 ASSERT(NULL != esrc);
1571 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
1574 * we no doubt modifying a path-list. If the path-list
1575 * is shared, and hence not modifiable, then the index returned
1576 * will be for a different path-list. This FIB entry to needs
1577 * to maintain its lock appropriately.
1579 old_path_list = esrc->fes_pl;
1581 ASSERT(NULL != fib_entry_src_vft[source].fesv_path_remove);
1583 pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1584 fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1586 fib_entry_src_vft[source].fesv_path_remove(esrc, pl_flags, rpath);
1589 * lock the new path-list, unlock the old if it had one
1591 fib_path_list_unlock(old_path_list);
1593 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) {
1594 fib_path_list_lock(esrc->fes_pl);
1595 return (FIB_ENTRY_SRC_FLAG_ADDED);
1600 * no more paths left from this source
1602 fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1603 return (FIB_ENTRY_SRC_FLAG_NONE);
1608 fib_entry_src_format (fib_entry_t *fib_entry,
1609 fib_source_t source,
1612 fib_entry_src_t *esrc;
1614 esrc = fib_entry_src_find(fib_entry, source, NULL);
1616 if (NULL != fib_entry_src_vft[source].fesv_format)
1618 return (fib_entry_src_vft[source].fesv_format(esrc, s));
1624 fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index,
1625 fib_source_t source)
1627 fib_entry_t *fib_entry;
1628 fib_entry_src_t *esrc;
1630 if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1631 return (ADJ_INDEX_INVALID);
1633 fib_entry = fib_entry_get(fib_entry_index);
1634 esrc = fib_entry_src_find(fib_entry, source, NULL);
1638 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1640 return (fib_path_list_get_adj(
1642 fib_entry_get_default_chain_type(fib_entry)));
1645 return (ADJ_INDEX_INVALID);
1649 fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
1650 fib_source_t source,
1653 fib_entry_t *fib_entry;
1654 fib_entry_src_t *esrc;
1656 if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1659 fib_entry = fib_entry_get(fib_entry_index);
1660 esrc = fib_entry_src_find(fib_entry, source, NULL);
1664 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1666 fib_path_list_contribute_forwarding(
1668 fib_entry_get_default_chain_type(fib_entry),
1669 FIB_PATH_LIST_FWD_FLAG_NONE,
1672 return (dpo_id_is_valid(dpo));
1679 fib_entry_get_resolving_interface_for_source (fib_node_index_t entry_index,
1680 fib_source_t source)
1682 fib_entry_t *fib_entry;
1683 fib_entry_src_t *esrc;
1685 fib_entry = fib_entry_get(entry_index);
1687 esrc = fib_entry_src_find(fib_entry, source, NULL);
1691 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1693 return (fib_path_list_get_resolving_interface(esrc->fes_pl));
1700 fib_entry_get_flags_for_source (fib_node_index_t entry_index,
1701 fib_source_t source)
1703 fib_entry_t *fib_entry;
1704 fib_entry_src_t *esrc;
1706 fib_entry = fib_entry_get(entry_index);
1708 esrc = fib_entry_src_find(fib_entry, source, NULL);
1712 return (esrc->fes_entry_flags);
1715 return (FIB_ENTRY_FLAG_NONE);
1719 fib_entry_get_flags_i (const fib_entry_t *fib_entry)
1721 fib_entry_flag_t flags;
1724 * the vector of sources is deliberately arranged in priority order
1726 if (0 == vec_len(fib_entry->fe_srcs))
1728 flags = FIB_ENTRY_FLAG_NONE;
1732 fib_entry_src_t *esrc;
1734 esrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
1735 flags = esrc->fes_entry_flags;
1742 fib_entry_set_source_data (fib_node_index_t fib_entry_index,
1743 fib_source_t source,
1746 fib_entry_t *fib_entry;
1747 fib_entry_src_t *esrc;
1749 fib_entry = fib_entry_get(fib_entry_index);
1750 esrc = fib_entry_src_find(fib_entry, source, NULL);
1753 NULL != fib_entry_src_vft[source].fesv_set_data)
1755 fib_entry_src_vft[source].fesv_set_data(esrc, fib_entry, data);
1760 fib_entry_get_source_data (fib_node_index_t fib_entry_index,
1761 fib_source_t source)
1763 fib_entry_t *fib_entry;
1764 fib_entry_src_t *esrc;
1766 fib_entry = fib_entry_get(fib_entry_index);
1767 esrc = fib_entry_src_find(fib_entry, source, NULL);
1770 NULL != fib_entry_src_vft[source].fesv_get_data)
1772 return (fib_entry_src_vft[source].fesv_get_data(esrc, fib_entry));
1778 fib_entry_src_module_init (void)
1780 fib_entry_src_rr_register();
1781 fib_entry_src_interface_register();
1782 fib_entry_src_default_route_register();
1783 fib_entry_src_special_register();
1784 fib_entry_src_api_register();
1785 fib_entry_src_adj_register();
1786 fib_entry_src_mpls_register();
1787 fib_entry_src_lisp_register();