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_IETF_IPV4_EXPLICIT_NULL_LABEL == label ||
216 MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL == label ||
217 MPLS_IETF_IMPLICIT_NULL_LABEL == label));
221 * @brief Turn the chain type requested by the client into the one they
224 fib_forward_chain_type_t
225 fib_entry_chain_type_fixup (const fib_entry_t *entry,
226 fib_forward_chain_type_t fct)
229 * The EOS chain is a tricky since one cannot know the adjacency
230 * to link to without knowing what the packets payload protocol
231 * will be once the label is popped.
233 fib_forward_chain_type_t dfct;
235 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS != fct)
240 dfct = fib_entry_get_default_chain_type(entry);
242 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS == dfct)
245 * If the entry being asked is a eos-MPLS label entry,
246 * then use the payload-protocol field, that we stashed there
247 * for just this purpose
249 return (fib_forw_chain_type_from_dpo_proto(
250 entry->fe_prefix.fp_payload_proto));
253 * else give them what this entry would be by default. i.e. if it's a v6
254 * entry, then the label its local labelled should be carrying v6 traffic.
255 * If it's a non-EOS label entry, then there are more labels and we want
262 fib_prefix_get_payload_proto (const fib_prefix_t *pfx)
264 switch (pfx->fp_proto)
266 case FIB_PROTOCOL_IP4:
267 return (DPO_PROTO_IP4);
268 case FIB_PROTOCOL_IP6:
269 return (DPO_PROTO_IP6);
270 case FIB_PROTOCOL_MPLS:
271 return (pfx->fp_payload_proto);
275 return (DPO_PROTO_IP4);
279 fib_entry_src_get_path_forwarding (fib_node_index_t path_index,
280 fib_entry_src_collect_forwarding_ctx_t *ctx)
282 load_balance_path_t *nh;
285 * no extension => no out-going label for this path. that's OK
286 * in the case of an IP or EOS chain, but not for non-EOS
290 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
291 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
292 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
293 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
294 case FIB_FORW_CHAIN_TYPE_BIER:
296 * EOS traffic with no label to stack, we need the IP Adj
298 vec_add2(ctx->next_hops, nh, 1);
300 nh->path_index = path_index;
301 nh->path_weight = fib_path_get_weight(path_index);
302 fib_path_contribute_forwarding(path_index, ctx->fct, &nh->path_dpo);
305 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
306 if (fib_path_is_exclusive(path_index) ||
307 fib_path_is_deag(path_index))
309 vec_add2(ctx->next_hops, nh, 1);
311 nh->path_index = path_index;
312 nh->path_weight = fib_path_get_weight(path_index);
313 fib_path_contribute_forwarding(path_index,
314 FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
318 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
321 * no label. we need a chain based on the payload. fixup.
323 vec_add2(ctx->next_hops, nh, 1);
325 nh->path_index = path_index;
326 nh->path_weight = fib_path_get_weight(path_index);
327 fib_path_contribute_forwarding(path_index,
328 fib_entry_chain_type_fixup(ctx->fib_entry,
331 fib_path_stack_mpls_disp(path_index,
332 fib_prefix_get_payload_proto(&ctx->fib_entry->fe_prefix),
337 case FIB_FORW_CHAIN_TYPE_ETHERNET:
338 case FIB_FORW_CHAIN_TYPE_NSH:
344 static fib_path_list_walk_rc_t
345 fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
346 fib_node_index_t path_index,
349 fib_entry_src_collect_forwarding_ctx_t *ctx;
350 fib_path_ext_t *path_ext;
355 * if the path is not resolved, don't include it.
357 if (!fib_path_is_resolved(path_index))
359 return (FIB_PATH_LIST_WALK_CONTINUE);
362 if (fib_path_is_recursive_constrained(path_index))
364 ctx->n_recursive_constrained += 1;
366 if (0xffff == ctx->preference)
369 * not set a preference yet, so the first path we encounter
370 * sets the preference we are collecting.
372 ctx->preference = fib_path_get_preference(path_index);
374 else if (ctx->preference != fib_path_get_preference(path_index))
377 * this path does not belong to the same preference as the
378 * previous paths encountered. we are done now.
380 return (FIB_PATH_LIST_WALK_STOP);
384 * get the matching path-extension for the path being visited.
386 path_ext = fib_path_ext_list_find_by_path_index(&ctx->esrc->fes_path_exts,
389 if (NULL != path_ext)
391 switch (path_ext->fpe_type)
393 case FIB_PATH_EXT_MPLS:
394 if (fib_entry_src_valid_out_label(path_ext->fpe_label_stack[0]))
397 * found a matching extension. stack it to obtain the forwarding
398 * info for this path.
401 fib_path_ext_stack(path_ext,
403 fib_entry_chain_type_fixup(ctx->fib_entry,
409 fib_entry_src_get_path_forwarding(path_index, ctx);
412 case FIB_PATH_EXT_ADJ:
413 if (FIB_PATH_EXT_ADJ_FLAG_REFINES_COVER & path_ext->fpe_adj_flags)
415 fib_entry_src_get_path_forwarding(path_index, ctx);
419 * the path does not refine the cover, meaning that
420 * the adjacency doesdoes not match the sub-net on the link.
421 * So this path does not contribute forwarding.
428 fib_entry_src_get_path_forwarding(path_index, ctx);
431 return (FIB_PATH_LIST_WALK_CONTINUE);
435 fib_entry_src_mk_lb (fib_entry_t *fib_entry,
436 const fib_entry_src_t *esrc,
437 fib_forward_chain_type_t fct,
440 dpo_proto_t lb_proto;
443 * If the entry has path extensions then we construct a load-balance
444 * by stacking the extensions on the forwarding chains of the paths.
445 * Otherwise we use the load-balance of the path-list
447 fib_entry_src_collect_forwarding_ctx_t ctx = {
449 .fib_entry = fib_entry,
451 .n_recursive_constrained = 0,
453 .preference = 0xffff,
457 * As an optimisation we allocate the vector of next-hops to be sized
458 * equal to the maximum nuber of paths we will need, which is also the
459 * most likely number we will need, since in most cases the paths are 'up'.
461 vec_validate(ctx.next_hops, fib_path_list_get_n_paths(esrc->fes_pl));
462 vec_reset_length(ctx.next_hops);
464 lb_proto = fib_forw_chain_type_to_dpo_proto(fct);
466 fib_path_list_walk(esrc->fes_pl,
467 fib_entry_src_collect_forwarding,
470 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE)
473 * the client provided the DPO that the entry should link to.
474 * all entries must link to a LB, so if it is an LB already
475 * then we can use it.
477 if ((1 == vec_len(ctx.next_hops)) &&
478 (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type))
480 dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo);
481 dpo_reset(&ctx.next_hops[0].path_dpo);
486 if (!dpo_id_is_valid(dpo_lb))
491 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
496 MPLS_IS_REPLICATE | replicate_create(0, lb_proto));
500 fib_protocol_t flow_hash_proto;
501 flow_hash_config_t fhc;
504 * if the protocol for the LB we are building does not match that
505 * of the fib_entry (i.e. we are build the [n]EOS LB for an IPv[46]
506 * then the fib_index is not an index that relates to the table
507 * type we need. So get the default flow-hash config instead.
509 flow_hash_proto = dpo_proto_to_fib(lb_proto);
510 if (fib_entry->fe_prefix.fp_proto != flow_hash_proto)
512 fhc = fib_table_get_default_flow_hash_config(flow_hash_proto);
516 fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index,
523 load_balance_create(0, lb_proto, fhc));
527 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
532 replicate_multipath_update(dpo_lb, ctx.next_hops);
536 load_balance_multipath_update(dpo_lb,
538 fib_entry_calc_lb_flags(&ctx));
539 vec_free(ctx.next_hops);
542 * if this entry is sourced by the uRPF-exempt source then we
543 * append the always present local0 interface (index 0) to the
544 * uRPF list so it is not empty. that way packets pass the loose check.
546 index_t ui = fib_path_list_get_urpf(esrc->fes_pl);
548 if ((fib_entry_is_sourced(fib_entry_get_index(fib_entry),
549 FIB_SOURCE_URPF_EXEMPT) ||
550 (esrc->fes_entry_flags & FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT))&&
551 (0 == fib_urpf_check_size(ui)))
554 * The uRPF list we get from the path-list is shared by all
555 * other users of the list, but the uRPF exemption applies
556 * only to this prefix. So we need our own list.
558 ui = fib_urpf_list_alloc_and_lock();
559 fib_urpf_list_append(ui, 0);
560 fib_urpf_list_bake(ui);
561 load_balance_set_urpf(dpo_lb->dpoi_index, ui);
562 fib_urpf_list_unlock(ui);
566 load_balance_set_urpf(dpo_lb->dpoi_index, ui);
568 load_balance_set_fib_entry_flags(dpo_lb->dpoi_index,
569 fib_entry_get_flags_i(fib_entry));
574 fib_entry_src_action_install (fib_entry_t *fib_entry,
578 * Install the forwarding chain for the given source into the forwarding
581 fib_forward_chain_type_t fct;
582 fib_entry_src_t *esrc;
585 fct = fib_entry_get_default_chain_type(fib_entry);
586 esrc = fib_entry_src_find(fib_entry, source, NULL);
589 * Every entry has its own load-balance object. All changes to the entry's
590 * forwarding result in an inplace modify of the load-balance. This means
591 * the load-balance object only needs to be added to the forwarding
592 * DB once, when it is created.
594 insert = !dpo_id_is_valid(&fib_entry->fe_lb);
596 fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb);
598 ASSERT(dpo_id_is_valid(&fib_entry->fe_lb));
599 FIB_ENTRY_DBG(fib_entry, "install: %d", fib_entry->fe_lb);
602 * insert the adj into the data-plane forwarding trie
606 fib_table_fwding_dpo_update(fib_entry->fe_fib_index,
607 &fib_entry->fe_prefix,
612 * if any of the other chain types are already created they will need
615 fib_entry_delegate_type_t fdt;
616 fib_entry_delegate_t *fed;
618 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
620 fib_entry_src_mk_lb(fib_entry, esrc,
621 fib_entry_delegate_type_to_chain_type(fdt),
627 fib_entry_src_action_uninstall (fib_entry_t *fib_entry)
630 * uninstall the forwarding chain from the forwarding tables
632 FIB_ENTRY_DBG(fib_entry, "uninstall: %d",
633 fib_entry->fe_adj_index);
635 if (dpo_id_is_valid(&fib_entry->fe_lb))
637 fib_table_fwding_dpo_remove(
638 fib_entry->fe_fib_index,
639 &fib_entry->fe_prefix,
642 dpo_reset(&fib_entry->fe_lb);
647 fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
649 fib_node_index_t *entries = NULL;
651 fib_path_list_recursive_loop_detect(path_list_index, &entries);
657 * fib_entry_src_action_copy
659 * copy a source data from another entry to this one
662 fib_entry_src_action_copy (fib_entry_t *fib_entry,
663 const fib_entry_src_t *orig_src)
665 fib_entry_src_t *esrc;
667 esrc = fib_entry_src_find_or_create(fib_entry, orig_src->fes_src);
670 esrc->fes_ref_count = 1;
671 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_INHERITED;
672 esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
673 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
676 * the source owns a lock on the entry
678 fib_path_list_lock(esrc->fes_pl);
679 fib_entry_lock(fib_entry_get_index(fib_entry));
685 * fib_entry_src_action_update
687 * copy a source data from another entry to this one
689 static fib_entry_src_t *
690 fib_entry_src_action_update_from_cover (fib_entry_t *fib_entry,
691 const fib_entry_src_t *orig_src)
693 fib_entry_src_t *esrc;
695 esrc = fib_entry_src_find_or_create(fib_entry, orig_src->fes_src);
698 * the source owns a lock on the entry
700 fib_path_list_unlock(esrc->fes_pl);
701 esrc->fes_pl = orig_src->fes_pl;
702 fib_path_list_lock(esrc->fes_pl);
707 static fib_table_walk_rc_t
708 fib_entry_src_covered_inherit_add_i (fib_entry_t *fib_entry,
709 const fib_entry_src_t *cover_src)
711 fib_entry_src_t *esrc;
713 esrc = fib_entry_src_find(fib_entry, cover_src->fes_src, NULL);
715 if (cover_src == esrc)
717 return (FIB_TABLE_WALK_CONTINUE);
723 * the covered entry already has this source.
725 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
728 * the covered source is itself a COVERED_INHERIT, i.e.
729 * it also pushes this source down the sub-tree.
730 * We consider this more specfic covered to be the owner
731 * of the sub-tree from this point down.
733 return (FIB_TABLE_WALK_SUB_TREE_STOP);
735 if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
738 * The covered's source data has been inherited, presumably
739 * from this cover, i.e. this is a modify.
741 esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
742 fib_entry_source_change(fib_entry, esrc->fes_src, esrc->fes_src);
747 * The covered's source was not inherited and it is also
748 * not inherting. Nevertheless, it still owns the sub-tree from
751 return (FIB_TABLE_WALK_SUB_TREE_STOP);
757 * The covered does not have this source - add it.
759 fib_source_t best_source;
761 best_source = fib_entry_get_best_source(
762 fib_entry_get_index(fib_entry));
764 fib_entry_src_action_copy(fib_entry, cover_src);
765 fib_entry_source_change(fib_entry, best_source, cover_src->fes_src);
768 return (FIB_TABLE_WALK_CONTINUE);
771 static fib_table_walk_rc_t
772 fib_entry_src_covered_inherit_walk_add (fib_node_index_t fei,
775 return (fib_entry_src_covered_inherit_add_i(fib_entry_get(fei), ctx));
778 static fib_table_walk_rc_t
779 fib_entry_src_covered_inherit_walk_remove (fib_node_index_t fei,
782 fib_entry_src_t *cover_src, *esrc;
783 fib_entry_t *fib_entry;
785 fib_entry = fib_entry_get(fei);
788 esrc = fib_entry_src_find(fib_entry, cover_src->fes_src, NULL);
790 if (cover_src == esrc)
792 return (FIB_TABLE_WALK_CONTINUE);
798 * the covered entry already has this source.
800 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
803 * the covered source is itself a COVERED_INHERIT, i.e.
804 * it also pushes this source down the sub-tree.
805 * We consider this more specfic covered to be the owner
806 * of the sub-tree from this point down.
808 return (FIB_TABLE_WALK_SUB_TREE_STOP);
810 if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
813 * The covered's source data has been inherited, presumably
816 fib_entry_src_flag_t remaining;
818 remaining = fib_entry_special_remove(fei, cover_src->fes_src);
820 ASSERT(FIB_ENTRY_SRC_FLAG_ADDED == remaining);
825 * The covered's source was not inherited and it is also
826 * not inherting. Nevertheless, it still owns the sub-tree from
829 return (FIB_TABLE_WALK_SUB_TREE_STOP);
835 * The covered does not have this source - that's an error,
836 * since it should have inherited, but there is nothing we can do
840 return (FIB_TABLE_WALK_CONTINUE);
844 fib_entry_src_inherit (const fib_entry_t *cover,
845 fib_entry_t *covered)
847 CLIB_UNUSED(fib_source_t source);
848 const fib_entry_src_t *src;
850 FOR_EACH_SRC_ADDED(cover, src, source,
852 if ((src->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
853 (src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
855 fib_entry_src_covered_inherit_add_i(covered, src);
861 fib_entry_src_covered_inherit_add (fib_entry_t *fib_entry,
865 fib_entry_src_t *esrc;
867 esrc = fib_entry_src_find(fib_entry, source, NULL);
869 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
871 if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
872 (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
874 fib_table_sub_tree_walk(fib_entry->fe_fib_index,
875 fib_entry->fe_prefix.fp_proto,
876 &fib_entry->fe_prefix,
877 fib_entry_src_covered_inherit_walk_add,
883 fib_entry_src_covered_inherit_remove (fib_entry_t *fib_entry,
884 fib_entry_src_t *esrc)
887 ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
889 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
891 fib_table_sub_tree_walk(fib_entry->fe_fib_index,
892 fib_entry->fe_prefix.fp_proto,
893 &fib_entry->fe_prefix,
894 fib_entry_src_covered_inherit_walk_remove,
900 fib_entry_src_action_activate (fib_entry_t *fib_entry,
904 int houston_we_are_go_for_install;
905 fib_entry_src_t *esrc;
907 esrc = fib_entry_src_find(fib_entry, source, NULL);
909 ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
910 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
912 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE;
914 if (NULL != fib_entry_src_vft[source].fesv_activate)
916 houston_we_are_go_for_install =
917 fib_entry_src_vft[source].fesv_activate(esrc, fib_entry);
922 * the source is not providing an activate function, we'll assume
923 * therefore it has no objection to installing the entry
925 houston_we_are_go_for_install = !0;
929 * link to the path-list provided by the source, and go check
930 * if that forms any loops in the graph.
932 fib_entry->fe_parent = esrc->fes_pl;
933 fib_entry->fe_sibling =
934 fib_path_list_child_add(fib_entry->fe_parent,
936 fib_entry_get_index(fib_entry));
938 fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
940 FIB_ENTRY_DBG(fib_entry, "activate: %d",
941 fib_entry->fe_parent);
944 * If this source should push its state to covered prefixs, do that now.
946 fib_entry_src_covered_inherit_add(fib_entry, source);
948 if (0 != houston_we_are_go_for_install)
950 fib_entry_src_action_install(fib_entry, source);
954 fib_entry_src_action_uninstall(fib_entry);
959 fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
963 fib_node_index_t path_list_index;
964 fib_entry_src_t *esrc;
966 esrc = fib_entry_src_find(fib_entry, source, NULL);
968 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
970 if (NULL != fib_entry_src_vft[source].fesv_deactivate)
972 fib_entry_src_vft[source].fesv_deactivate(esrc, fib_entry);
975 esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
977 FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
980 * If this source should pull its state from covered prefixs, do that now.
981 * If this source also has the INHERITED flag set then it has a cover
982 * that wants to push down forwarding. We only want the covereds to see
985 fib_entry_src_covered_inherit_remove(fib_entry, esrc);
988 * un-link from an old path-list. Check for any loops this will clear
990 path_list_index = fib_entry->fe_parent;
991 fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
993 fib_entry_recursive_loop_detect_i(path_list_index);
996 * this will unlock the path-list, so it may be invalid thereafter.
998 fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
999 fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
1003 fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
1004 fib_source_t source)
1006 fib_entry_src_t *esrc;
1008 vec_foreach(esrc, fib_entry->fe_srcs)
1010 if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update)
1012 fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc,
1020 fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
1021 fib_source_t source)
1023 fib_node_index_t path_list_index;
1024 fib_entry_src_t *esrc;
1026 esrc = fib_entry_src_find(fib_entry, source, NULL);
1028 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
1030 FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
1031 fib_entry->fe_parent,
1034 if (fib_entry->fe_parent != esrc->fes_pl)
1036 int remain_installed;
1039 * un-link from an old path-list. Check for any loops this will clear
1041 path_list_index = fib_entry->fe_parent;
1042 fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
1045 * temporary lock so it doesn't get deleted when this entry is no
1048 fib_path_list_lock(path_list_index);
1051 * this entry is no longer a child. after unlinking check if any loops
1054 fib_path_list_child_remove(path_list_index,
1055 fib_entry->fe_sibling);
1057 fib_entry_recursive_loop_detect_i(path_list_index);
1060 * link to the path-list provided by the source, and go check
1061 * if that forms any loops in the graph.
1063 fib_entry->fe_parent = esrc->fes_pl;
1064 fib_entry->fe_sibling =
1065 fib_path_list_child_add(fib_entry->fe_parent,
1066 FIB_NODE_TYPE_ENTRY,
1067 fib_entry_get_index(fib_entry));
1069 fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
1070 fib_path_list_unlock(path_list_index);
1073 * call the source to reactive and get the go/no-go to remain installed
1075 if (NULL != fib_entry_src_vft[source].fesv_reactivate)
1078 fib_entry_src_vft[source].fesv_reactivate(esrc, fib_entry);
1082 remain_installed = 1;
1086 * If this source should push its state to covered prefixs, do that now.
1088 fib_entry_src_covered_inherit_add(fib_entry, source);
1090 if (!remain_installed)
1092 fib_entry_src_action_uninstall(fib_entry);
1096 fib_entry_src_action_install(fib_entry, source);
1097 fib_entry_src_action_fwd_update(fib_entry, source);
1101 fib_entry_src_action_installed (const fib_entry_t *fib_entry,
1102 fib_source_t source)
1104 fib_entry_src_t *esrc;
1106 esrc = fib_entry_src_find(fib_entry, source, NULL);
1108 if (NULL != fib_entry_src_vft[source].fesv_installed)
1110 fib_entry_src_vft[source].fesv_installed(esrc,
1114 fib_entry_src_action_fwd_update(fib_entry, source);
1118 * fib_entry_src_action_add
1120 * Adding a source can result in a new fib_entry being created, which
1121 * can inturn mean the pool is realloc'd and thus the entry passed as
1122 * an argument it also realloc'd
1123 * @return the original entry
1126 fib_entry_src_action_add (fib_entry_t *fib_entry,
1127 fib_source_t source,
1128 fib_entry_flag_t flags,
1129 const dpo_id_t *dpo)
1131 fib_node_index_t fib_entry_index;
1132 fib_entry_src_t *esrc;
1134 esrc = fib_entry_src_find_or_create(fib_entry, source);
1136 esrc->fes_ref_count++;
1138 if (1 != esrc->fes_ref_count)
1141 * we only want to add the source on the 0->1 transition
1146 esrc->fes_entry_flags = flags;
1149 * save variable so we can recover from a fib_entry realloc.
1151 fib_entry_index = fib_entry_get_index(fib_entry);
1153 if (NULL != fib_entry_src_vft[source].fesv_add)
1155 fib_entry_src_vft[source].fesv_add(esrc,
1158 fib_entry_get_dpo_proto(fib_entry),
1162 fib_entry = fib_entry_get(fib_entry_index);
1164 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1166 fib_path_list_lock(esrc->fes_pl);
1169 * the source owns a lock on the entry
1171 fib_entry_lock(fib_entry_get_index(fib_entry));
1177 * fib_entry_src_action_update
1179 * Adding a source can result in a new fib_entry being created, which
1180 * can inturn mean the pool is realloc'd and thus the entry passed as
1181 * an argument it also realloc'd
1182 * @return the original entry
1185 fib_entry_src_action_update (fib_entry_t *fib_entry,
1186 fib_source_t source,
1187 fib_entry_flag_t flags,
1188 const dpo_id_t *dpo)
1190 fib_node_index_t fib_entry_index, old_path_list_index;
1191 fib_entry_src_t *esrc;
1193 esrc = fib_entry_src_find_or_create(fib_entry, source);
1197 return (fib_entry_src_action_add(fib_entry, source, flags, dpo));
1200 old_path_list_index = esrc->fes_pl;
1201 esrc->fes_entry_flags = flags;
1204 * save variable so we can recover from a fib_entry realloc.
1206 fib_entry_index = fib_entry_get_index(fib_entry);
1208 if (NULL != fib_entry_src_vft[source].fesv_add)
1210 fib_entry_src_vft[source].fesv_add(esrc,
1213 fib_entry_get_dpo_proto(fib_entry),
1217 fib_entry = fib_entry_get(fib_entry_index);
1219 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1221 fib_path_list_lock(esrc->fes_pl);
1222 fib_path_list_unlock(old_path_list_index);
1227 fib_entry_src_flag_t
1228 fib_entry_src_action_remove_or_update_inherit (fib_entry_t *fib_entry,
1229 fib_source_t source)
1231 fib_entry_src_t *esrc;
1233 esrc = fib_entry_src_find(fib_entry, source, NULL);
1236 return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1238 if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) &&
1239 (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
1241 fib_entry_src_t *cover_src;
1242 fib_node_index_t coveri;
1246 * this source was pushing inherited state, but so is its
1247 * cover. Now that this source is going away, we need to
1248 * pull the covers forwarding and use it to update the covereds.
1249 * Go grab the path-list from the cover, rather than start a walk from
1250 * the cover, so we don't recursively update this entry.
1252 coveri = fib_table_get_less_specific(fib_entry->fe_fib_index,
1253 &fib_entry->fe_prefix);
1256 * only the default route has itself as its own cover, but the
1257 * default route cannot have inherited from something else.
1259 ASSERT(coveri != fib_entry_get_index(fib_entry));
1261 cover = fib_entry_get(coveri);
1262 cover_src = fib_entry_src_find(cover, source, NULL);
1264 ASSERT(NULL != cover_src);
1266 esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
1267 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
1270 * Now push the new state from the cover down to the covereds
1272 fib_entry_src_covered_inherit_add(fib_entry, source);
1274 return (esrc->fes_flags);
1278 return (fib_entry_src_action_remove(fib_entry, source));
1282 fib_entry_src_flag_t
1283 fib_entry_src_action_remove (fib_entry_t *fib_entry,
1284 fib_source_t source)
1287 fib_node_index_t old_path_list;
1288 fib_entry_src_flag_t sflags;
1289 fib_entry_src_t *esrc;
1291 esrc = fib_entry_src_find(fib_entry, source, NULL);
1294 return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1296 esrc->fes_ref_count--;
1297 sflags = esrc->fes_flags;
1299 if (0 != esrc->fes_ref_count)
1302 * only remove the source on the 1->0 transisition
1307 if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
1309 fib_entry_src_action_deactivate(fib_entry, source);
1312 old_path_list = esrc->fes_pl;
1314 if (NULL != fib_entry_src_vft[source].fesv_remove)
1316 fib_entry_src_vft[source].fesv_remove(esrc);
1319 fib_path_list_unlock(old_path_list);
1320 fib_entry_unlock(fib_entry_get_index(fib_entry));
1322 sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
1323 fib_entry_src_action_deinit(fib_entry, source);
1329 * fib_route_attached_cross_table
1331 * Return true the the route is attached via an interface that
1332 * is not in the same table as the route
1335 fib_route_attached_cross_table (const fib_entry_t *fib_entry,
1336 const fib_route_path_t *rpath)
1339 * - All zeros next-hop
1340 * - a valid interface
1341 * - entry's fib index not equeal to interface's index
1343 if (ip46_address_is_zero(&rpath->frp_addr) &&
1344 (~0 != rpath->frp_sw_if_index) &&
1345 (fib_entry->fe_fib_index !=
1346 fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
1347 rpath->frp_sw_if_index)))
1355 * fib_route_attached_cross_table
1357 * Return true the the route is attached via an interface that
1358 * is not in the same table as the route
1361 fib_path_is_attached (const fib_route_path_t *rpath)
1364 * - All zeros next-hop
1365 * - a valid interface
1367 if (ip46_address_is_zero(&rpath->frp_addr) &&
1368 (~0 != rpath->frp_sw_if_index))
1372 else if (rpath->frp_flags & FIB_ROUTE_PATH_ATTACHED)
1379 fib_path_list_flags_t
1380 fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
1382 fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
1384 if (eflags & FIB_ENTRY_FLAG_DROP)
1386 plf |= FIB_PATH_LIST_FLAG_DROP;
1388 if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
1390 plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
1392 if (eflags & FIB_ENTRY_FLAG_LOCAL)
1394 plf |= FIB_PATH_LIST_FLAG_LOCAL;
1401 fib_entry_flags_update (const fib_entry_t *fib_entry,
1402 const fib_route_path_t *rpath,
1403 fib_path_list_flags_t *pl_flags,
1404 fib_entry_src_t *esrc)
1406 if ((esrc->fes_src == FIB_SOURCE_API) ||
1407 (esrc->fes_src == FIB_SOURCE_CLI))
1409 if (fib_path_is_attached(rpath))
1411 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
1415 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
1417 if (rpath->frp_flags & FIB_ROUTE_PATH_DEAG)
1419 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT;
1422 if (fib_route_attached_cross_table(fib_entry, rpath))
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();