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_get_proto (const fib_entry_t * fib_entry)
35 return (fib_entry->fe_prefix.fp_proto);
39 fib_entry_src_register (fib_source_t source,
40 const fib_entry_src_vft_t *vft)
42 fib_entry_src_vft[source] = *vft;
46 fib_entry_src_cmp_for_sort (void * v1,
49 fib_entry_src_t *esrc1 = v1, *esrc2 = v2;
51 return (esrc1->fes_src - esrc2->fes_src);
55 fib_entry_src_action_init (fib_entry_t *fib_entry,
59 fib_entry_src_t esrc = {
60 .fes_pl = FIB_NODE_INDEX_INVALID,
61 .fes_flags = FIB_ENTRY_SRC_FLAG_NONE,
65 if (NULL != fib_entry_src_vft[source].fesv_init)
67 fib_entry_src_vft[source].fesv_init(&esrc);
70 vec_add1(fib_entry->fe_srcs, esrc);
71 vec_sort_with_function(fib_entry->fe_srcs,
72 fib_entry_src_cmp_for_sort);
75 static fib_entry_src_t *
76 fib_entry_src_find (const fib_entry_t *fib_entry,
81 fib_entry_src_t *esrc;
85 vec_foreach(esrc, fib_entry->fe_srcs)
87 if (esrc->fes_src == source)
105 fib_entry_is_sourced (fib_node_index_t fib_entry_index,
108 fib_entry_t *fib_entry;
110 fib_entry = fib_entry_get(fib_entry_index);
112 return (NULL != fib_entry_src_find(fib_entry, source, NULL));
115 static fib_entry_src_t *
116 fib_entry_src_find_or_create (fib_entry_t *fib_entry,
120 fib_entry_src_t *esrc;
122 esrc = fib_entry_src_find(fib_entry, source, NULL);
126 fib_entry_src_action_init(fib_entry, source);
129 return (fib_entry_src_find(fib_entry, source, NULL));
133 fib_entry_src_action_deinit (fib_entry_t *fib_entry,
137 fib_entry_src_t *esrc;
140 esrc = fib_entry_src_find(fib_entry, source, &index);
142 ASSERT(NULL != esrc);
144 if (NULL != fib_entry_src_vft[source].fesv_deinit)
146 fib_entry_src_vft[source].fesv_deinit(esrc);
149 vec_free(esrc->fes_path_exts);
150 vec_del1(fib_entry->fe_srcs, index);
153 fib_entry_src_cover_res_t
154 fib_entry_src_action_cover_change (fib_entry_t *fib_entry,
157 if (NULL != fib_entry_src_vft[source].fesv_cover_change)
159 return (fib_entry_src_vft[source].fesv_cover_change(
160 fib_entry_src_find(fib_entry, source, NULL),
164 fib_entry_src_cover_res_t res = {
166 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
171 fib_entry_src_cover_res_t
172 fib_entry_src_action_cover_update (fib_entry_t *fib_entry,
175 if (NULL != fib_entry_src_vft[source].fesv_cover_update)
177 return (fib_entry_src_vft[source].fesv_cover_update(
178 fib_entry_src_find(fib_entry, source, NULL),
182 fib_entry_src_cover_res_t res = {
184 .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
189 typedef struct fib_entry_src_collect_forwarding_ctx_t_
191 load_balance_path_t * next_hops;
192 const fib_entry_t *fib_entry;
193 const fib_entry_src_t *esrc;
194 fib_forward_chain_type_t fct;
195 int n_recursive_constrained;
196 } fib_entry_src_collect_forwarding_ctx_t;
199 * @brief Determine whether this FIB entry should use a load-balance MAP
200 * to support PIC edge fast convergence
203 fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx)
206 * We'll use a LB map if the path-list has multiple recursive paths.
207 * recursive paths implies BGP, and hence scale.
209 if (ctx->n_recursive_constrained > 1 &&
210 fib_path_list_is_popular(ctx->esrc->fes_pl))
212 return (LOAD_BALANCE_FLAG_USES_MAP);
214 return (LOAD_BALANCE_FLAG_NONE);
218 fib_entry_src_valid_out_label (mpls_label_t label)
220 return ((MPLS_LABEL_IS_REAL(label) ||
221 MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL == label ||
222 MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL == label ||
223 MPLS_IETF_IMPLICIT_NULL_LABEL == label));
227 * @brief Turn the chain type requested by the client into the one they
230 fib_forward_chain_type_t
231 fib_entry_chain_type_fixup (const fib_entry_t *entry,
232 fib_forward_chain_type_t fct)
235 * The EOS chain is a tricky since one cannot know the adjacency
236 * to link to without knowing what the packets payload protocol
237 * will be once the label is popped.
239 fib_forward_chain_type_t dfct;
241 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS != fct)
246 dfct = fib_entry_get_default_chain_type(entry);
248 if (FIB_FORW_CHAIN_TYPE_MPLS_EOS == dfct)
251 * If the entry being asked is a eos-MPLS label entry,
252 * then use the payload-protocol field, that we stashed there
253 * for just this purpose
255 return (fib_forw_chain_type_from_dpo_proto(
256 entry->fe_prefix.fp_payload_proto));
259 * else give them what this entry would be by default. i.e. if it's a v6
260 * entry, then the label its local labelled should be carrying v6 traffic.
261 * If it's a non-EOS label entry, then there are more labels and we want
268 fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
269 fib_node_index_t path_index,
272 fib_entry_src_collect_forwarding_ctx_t *ctx;
273 fib_path_ext_t *path_ext;
279 * if the path is not resolved, don't include it.
281 if (!fib_path_is_resolved(path_index))
286 if (fib_path_is_recursive_constrained(path_index))
288 ctx->n_recursive_constrained += 1;
292 * get the matching path-extension for the path being visited.
295 vec_foreach(path_ext, ctx->esrc->fes_path_exts)
297 if (path_ext->fpe_path_index == path_index)
305 fib_entry_src_valid_out_label(path_ext->fpe_label_stack[0]))
308 * found a matching extension. stack it to obtain the forwarding
309 * info for this path.
312 fib_path_ext_stack(path_ext,
314 fib_entry_chain_type_fixup(ctx->fib_entry,
320 load_balance_path_t *nh;
323 * no extension => no out-going label for this path. that's OK
324 * in the case of an IP or EOS chain, but not for non-EOS
328 case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
329 case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
330 case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
331 case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
333 * EOS traffic with no label to stack, we need the IP Adj
335 vec_add2(ctx->next_hops, nh, 1);
337 nh->path_index = path_index;
338 nh->path_weight = fib_path_get_weight(path_index);
339 fib_path_contribute_forwarding(path_index, ctx->fct, &nh->path_dpo);
342 case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
343 if (fib_path_is_exclusive(path_index) ||
344 fib_path_is_deag(path_index))
346 vec_add2(ctx->next_hops, nh, 1);
348 nh->path_index = path_index;
349 nh->path_weight = fib_path_get_weight(path_index);
350 fib_path_contribute_forwarding(path_index,
351 FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
355 case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
358 * no label. we need a chain based on the payload. fixup.
360 vec_add2(ctx->next_hops, nh, 1);
362 nh->path_index = path_index;
363 nh->path_weight = fib_path_get_weight(path_index);
364 fib_path_contribute_forwarding(path_index,
365 fib_entry_chain_type_fixup(ctx->fib_entry,
368 fib_path_stack_mpls_disp(path_index,
369 ctx->fib_entry->fe_prefix.fp_payload_proto,
374 case FIB_FORW_CHAIN_TYPE_ETHERNET:
375 case FIB_FORW_CHAIN_TYPE_NSH:
385 fib_entry_src_mk_lb (fib_entry_t *fib_entry,
386 const fib_entry_src_t *esrc,
387 fib_forward_chain_type_t fct,
390 dpo_proto_t lb_proto;
393 * If the entry has path extensions then we construct a load-balance
394 * by stacking the extensions on the forwarding chains of the paths.
395 * Otherwise we use the load-balance of the path-list
397 fib_entry_src_collect_forwarding_ctx_t ctx = {
399 .fib_entry = fib_entry,
401 .n_recursive_constrained = 0,
406 * As an optimisation we allocate the vector of next-hops to be sized
407 * equal to the maximum nuber of paths we will need, which is also the
408 * most likely number we will need, since in most cases the paths are 'up'.
410 vec_validate(ctx.next_hops, fib_path_list_get_n_paths(esrc->fes_pl));
411 vec_reset_length(ctx.next_hops);
413 lb_proto = fib_forw_chain_type_to_dpo_proto(fct);
415 fib_path_list_walk(esrc->fes_pl,
416 fib_entry_src_collect_forwarding,
419 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE)
422 * the client provided the DPO that the entry should link to.
423 * all entries must link to a LB, so if it is an LB already
424 * then we can use it.
426 if ((1 == vec_len(ctx.next_hops)) &&
427 (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type))
429 dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo);
430 dpo_reset(&ctx.next_hops[0].path_dpo);
435 if (!dpo_id_is_valid(dpo_lb))
440 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
445 MPLS_IS_REPLICATE | replicate_create(0, lb_proto));
449 flow_hash_config_t fhc;
453 * if the protocol for the LB we are building does not match that
454 * of the fib_entry (i.e. we are build the [n]EOS LB for an IPv[46]
455 * then the fib_index is not an index that relates to the table
456 * type we need. So get the default flow-hash config instead.
458 fp = dpo_proto_to_fib(lb_proto);
460 if (fib_entry->fe_prefix.fp_proto != fp)
462 fhc = fib_table_get_default_flow_hash_config(fp);
466 fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index, fp);
471 load_balance_create(0, lb_proto, fhc));
475 if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
480 replicate_multipath_update(dpo_lb, ctx.next_hops);
484 load_balance_multipath_update(dpo_lb,
486 fib_entry_calc_lb_flags(&ctx));
487 vec_free(ctx.next_hops);
490 * if this entry is sourced by the uRPF-exempt source then we
491 * append the always present local0 interface (index 0) to the
492 * uRPF list so it is not empty. that way packets pass the loose check.
494 index_t ui = fib_path_list_get_urpf(esrc->fes_pl);
496 if ((fib_entry_is_sourced(fib_entry_get_index(fib_entry),
497 FIB_SOURCE_URPF_EXEMPT) ||
498 (esrc->fes_entry_flags & FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT))&&
499 (0 == fib_urpf_check_size(ui)))
502 * The uRPF list we get from the path-list is shared by all
503 * other users of the list, but the uRPF exemption applies
504 * only to this prefix. So we need our own list.
506 ui = fib_urpf_list_alloc_and_lock();
507 fib_urpf_list_append(ui, 0);
508 fib_urpf_list_bake(ui);
509 load_balance_set_urpf(dpo_lb->dpoi_index, ui);
510 fib_urpf_list_unlock(ui);
514 load_balance_set_urpf(dpo_lb->dpoi_index, ui);
516 load_balance_set_fib_entry_flags(dpo_lb->dpoi_index,
517 fib_entry_get_flags_i(fib_entry));
522 fib_entry_src_action_install (fib_entry_t *fib_entry,
526 * Install the forwarding chain for the given source into the forwarding
529 fib_forward_chain_type_t fct;
530 fib_entry_src_t *esrc;
533 fct = fib_entry_get_default_chain_type(fib_entry);
534 esrc = fib_entry_src_find(fib_entry, source, NULL);
537 * Every entry has its own load-balance object. All changes to the entry's
538 * forwarding result in an inplace modify of the load-balance. This means
539 * the load-balance object only needs to be added to the forwarding
540 * DB once, when it is created.
542 insert = !dpo_id_is_valid(&fib_entry->fe_lb);
544 fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb);
546 ASSERT(dpo_id_is_valid(&fib_entry->fe_lb));
547 FIB_ENTRY_DBG(fib_entry, "install: %d", fib_entry->fe_lb);
550 * insert the adj into the data-plane forwarding trie
554 fib_table_fwding_dpo_update(fib_entry->fe_fib_index,
555 &fib_entry->fe_prefix,
560 * if any of the other chain types are already created they will need
563 fib_entry_delegate_type_t fdt;
564 fib_entry_delegate_t *fed;
566 FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
568 fib_entry_src_mk_lb(fib_entry, esrc,
569 fib_entry_delegate_type_to_chain_type(fdt),
575 fib_entry_src_action_uninstall (fib_entry_t *fib_entry)
578 * uninstall the forwarding chain from the forwarding tables
580 FIB_ENTRY_DBG(fib_entry, "uninstall: %d",
581 fib_entry->fe_adj_index);
583 if (dpo_id_is_valid(&fib_entry->fe_lb))
585 fib_table_fwding_dpo_remove(
586 fib_entry->fe_fib_index,
587 &fib_entry->fe_prefix,
590 dpo_reset(&fib_entry->fe_lb);
595 fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
597 fib_node_index_t *entries = NULL;
599 fib_path_list_recursive_loop_detect(path_list_index, &entries);
605 fib_entry_src_action_activate (fib_entry_t *fib_entry,
609 int houston_we_are_go_for_install;
610 fib_entry_src_t *esrc;
612 esrc = fib_entry_src_find(fib_entry, source, NULL);
614 ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
615 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
617 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE;
619 if (NULL != fib_entry_src_vft[source].fesv_activate)
621 houston_we_are_go_for_install =
622 fib_entry_src_vft[source].fesv_activate(esrc, fib_entry);
627 * the source is not providing an activate function, we'll assume
628 * therefore it has no objection to installing the entry
630 houston_we_are_go_for_install = !0;
634 * link to the path-list provided by the source, and go check
635 * if that forms any loops in the graph.
637 fib_entry->fe_parent = esrc->fes_pl;
638 fib_entry->fe_sibling =
639 fib_path_list_child_add(fib_entry->fe_parent,
641 fib_entry_get_index(fib_entry));
643 fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
645 FIB_ENTRY_DBG(fib_entry, "activate: %d",
646 fib_entry->fe_parent);
648 if (0 != houston_we_are_go_for_install)
650 fib_entry_src_action_install(fib_entry, source);
654 fib_entry_src_action_uninstall(fib_entry);
659 fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
663 fib_node_index_t path_list_index;
664 fib_entry_src_t *esrc;
666 esrc = fib_entry_src_find(fib_entry, source, NULL);
668 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
670 if (NULL != fib_entry_src_vft[source].fesv_deactivate)
672 fib_entry_src_vft[source].fesv_deactivate(esrc, fib_entry);
675 esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
677 FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
680 * un-link from an old path-list. Check for any loops this will clear
682 path_list_index = fib_entry->fe_parent;
683 fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
685 fib_entry_recursive_loop_detect_i(path_list_index);
688 * this will unlock the path-list, so it may be invalid thereafter.
690 fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
691 fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
695 fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
698 fib_entry_src_t *esrc;
700 vec_foreach(esrc, fib_entry->fe_srcs)
702 if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update)
704 fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc,
712 fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
715 fib_node_index_t path_list_index;
716 fib_entry_src_t *esrc;
718 esrc = fib_entry_src_find(fib_entry, source, NULL);
720 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
722 FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
723 fib_entry->fe_parent,
726 if (fib_entry->fe_parent != esrc->fes_pl)
729 * un-link from an old path-list. Check for any loops this will clear
731 path_list_index = fib_entry->fe_parent;
732 fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
735 * temporary lock so it doesn't get deleted when this entry is no
738 fib_path_list_lock(path_list_index);
741 * this entry is no longer a child. after unlinking check if any loops
744 fib_path_list_child_remove(path_list_index,
745 fib_entry->fe_sibling);
747 fib_entry_recursive_loop_detect_i(path_list_index);
750 * link to the path-list provided by the source, and go check
751 * if that forms any loops in the graph.
753 fib_entry->fe_parent = esrc->fes_pl;
754 fib_entry->fe_sibling =
755 fib_path_list_child_add(fib_entry->fe_parent,
757 fib_entry_get_index(fib_entry));
759 fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
760 fib_path_list_unlock(path_list_index);
762 fib_entry_src_action_install(fib_entry, source);
763 fib_entry_src_action_fwd_update(fib_entry, source);
767 fib_entry_src_action_installed (const fib_entry_t *fib_entry,
770 fib_entry_src_t *esrc;
772 esrc = fib_entry_src_find(fib_entry, source, NULL);
774 if (NULL != fib_entry_src_vft[source].fesv_installed)
776 fib_entry_src_vft[source].fesv_installed(esrc,
780 fib_entry_src_action_fwd_update(fib_entry, source);
784 * fib_entry_src_action_add
786 * Adding a source can result in a new fib_entry being created, which
787 * can inturn mean the pool is realloc'd and thus the entry passed as
788 * an argument it also realloc'd
789 * @return the original entry
792 fib_entry_src_action_add (fib_entry_t *fib_entry,
794 fib_entry_flag_t flags,
797 fib_node_index_t fib_entry_index;
798 fib_entry_src_t *esrc;
800 esrc = fib_entry_src_find_or_create(fib_entry, source, NULL);
802 esrc->fes_ref_count++;
804 if (1 != esrc->fes_ref_count)
807 * we only want to add the source on the 0->1 transition
812 esrc->fes_entry_flags = flags;
815 * save variable so we can recover from a fib_entry realloc.
817 fib_entry_index = fib_entry_get_index(fib_entry);
819 if (NULL != fib_entry_src_vft[source].fesv_add)
821 fib_entry_src_vft[source].fesv_add(esrc,
824 fib_entry_get_proto(fib_entry),
828 fib_entry = fib_entry_get(fib_entry_index);
830 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
832 fib_path_list_lock(esrc->fes_pl);
835 * the source owns a lock on the entry
837 fib_entry_lock(fib_entry_get_index(fib_entry));
843 * fib_entry_src_action_update
845 * Adding a source can result in a new fib_entry being created, which
846 * can inturn mean the pool is realloc'd and thus the entry passed as
847 * an argument it also realloc'd
848 * @return the original entry
851 fib_entry_src_action_update (fib_entry_t *fib_entry,
853 fib_entry_flag_t flags,
856 fib_node_index_t fib_entry_index, old_path_list_index;
857 fib_entry_src_t *esrc;
859 esrc = fib_entry_src_find_or_create(fib_entry, source, NULL);
862 return (fib_entry_src_action_add(fib_entry, source, flags, dpo));
864 old_path_list_index = esrc->fes_pl;
865 esrc->fes_entry_flags = flags;
868 * save variable so we can recover from a fib_entry realloc.
870 fib_entry_index = fib_entry_get_index(fib_entry);
872 if (NULL != fib_entry_src_vft[source].fesv_add)
874 fib_entry_src_vft[source].fesv_add(esrc,
877 fib_entry_get_proto(fib_entry),
881 fib_entry = fib_entry_get(fib_entry_index);
883 esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
885 fib_path_list_lock(esrc->fes_pl);
886 fib_path_list_unlock(old_path_list_index);
893 fib_entry_src_action_remove (fib_entry_t *fib_entry,
897 fib_node_index_t old_path_list;
898 fib_entry_src_flag_t sflags;
899 fib_entry_src_t *esrc;
901 esrc = fib_entry_src_find(fib_entry, source, NULL);
904 return (FIB_ENTRY_SRC_FLAG_ACTIVE);
906 esrc->fes_ref_count--;
907 sflags = esrc->fes_flags;
909 if (0 != esrc->fes_ref_count)
912 * only remove the source on the 1->0 transisition
917 if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
919 fib_entry_src_action_deactivate(fib_entry, source);
922 old_path_list = esrc->fes_pl;
924 if (NULL != fib_entry_src_vft[source].fesv_remove)
926 fib_entry_src_vft[source].fesv_remove(esrc);
929 fib_path_list_unlock(old_path_list);
930 fib_entry_unlock(fib_entry_get_index(fib_entry));
932 sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
933 fib_entry_src_action_deinit(fib_entry, source);
939 * fib_route_attached_cross_table
941 * Return true the the route is attached via an interface that
942 * is not in the same table as the route
945 fib_route_attached_cross_table (const fib_entry_t *fib_entry,
946 const fib_route_path_t *rpath)
949 * - All zeros next-hop
950 * - a valid interface
951 * - entry's fib index not equeal to interface's index
953 if (ip46_address_is_zero(&rpath->frp_addr) &&
954 (~0 != rpath->frp_sw_if_index) &&
955 (fib_entry->fe_fib_index !=
956 fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
957 rpath->frp_sw_if_index)))
965 * fib_route_attached_cross_table
967 * Return true the the route is attached via an interface that
968 * is not in the same table as the route
971 fib_path_is_attached (const fib_route_path_t *rpath)
974 * - All zeros next-hop
975 * - a valid interface
977 if (ip46_address_is_zero(&rpath->frp_addr) &&
978 (~0 != rpath->frp_sw_if_index))
982 else if (rpath->frp_flags & FIB_ROUTE_PATH_ATTACHED)
989 fib_path_list_flags_t
990 fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
992 fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
994 if (eflags & FIB_ENTRY_FLAG_DROP)
996 plf |= FIB_PATH_LIST_FLAG_DROP;
998 if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
1000 plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
1002 if (eflags & FIB_ENTRY_FLAG_LOCAL)
1004 plf |= FIB_PATH_LIST_FLAG_LOCAL;
1011 fib_entry_flags_update (const fib_entry_t *fib_entry,
1012 const fib_route_path_t *rpath,
1013 fib_path_list_flags_t *pl_flags,
1014 fib_entry_src_t *esrc)
1016 if ((esrc->fes_src == FIB_SOURCE_API) ||
1017 (esrc->fes_src == FIB_SOURCE_CLI))
1019 if (fib_path_is_attached(rpath))
1021 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
1025 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
1028 if (fib_route_attached_cross_table(fib_entry, rpath))
1030 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
1034 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
1039 * fib_entry_src_path_ext_add
1041 * append a path extension to the entry's list
1044 fib_entry_src_path_ext_append (fib_entry_src_t *esrc,
1045 const fib_route_path_t *rpath)
1047 if (NULL != rpath->frp_label_stack)
1049 fib_path_ext_t *path_ext;
1051 vec_add2(esrc->fes_path_exts, path_ext, 1);
1053 fib_path_ext_init(path_ext, esrc->fes_pl, rpath);
1058 * fib_entry_src_path_ext_insert
1060 * insert, sorted, a path extension to the entry's list.
1061 * It's not strictly necessary in sort the path extensions, since each
1062 * extension has the path index to which it resolves. However, by being
1063 * sorted the load-balance produced has a deterministic order, not an order
1064 * based on the sequence of extension additions. this is a considerable benefit.
1067 fib_entry_src_path_ext_insert (fib_entry_src_t *esrc,
1068 const fib_route_path_t *rpath)
1070 if (0 == vec_len(esrc->fes_path_exts))
1071 return (fib_entry_src_path_ext_append(esrc, rpath));
1073 if (NULL != rpath->frp_label_stack)
1075 fib_path_ext_t path_ext;
1078 fib_path_ext_init(&path_ext, esrc->fes_pl, rpath);
1080 while (i < vec_len(esrc->fes_path_exts) &&
1081 (fib_path_ext_cmp(&esrc->fes_path_exts[i], rpath) < 0))
1086 vec_insert_elts(esrc->fes_path_exts, &path_ext, 1, i);
1091 * fib_entry_src_action_add
1093 * Adding a source can result in a new fib_entry being created, which
1094 * can inturn mean the pool is realloc'd and thus the entry passed as
1095 * an argument it also realloc'd
1099 fib_entry_src_action_path_add (fib_entry_t *fib_entry,
1100 fib_source_t source,
1101 fib_entry_flag_t flags,
1102 const fib_route_path_t *rpath)
1104 fib_node_index_t old_path_list, fib_entry_index;
1105 fib_path_list_flags_t pl_flags;
1106 fib_path_ext_t *path_ext;
1107 fib_entry_src_t *esrc;
1110 * save variable so we can recover from a fib_entry realloc.
1112 fib_entry_index = fib_entry_get_index(fib_entry);
1114 esrc = fib_entry_src_find(fib_entry, source, NULL);
1118 fib_entry_src_action_add(fib_entry,
1123 fib_entry_get_proto(fib_entry))));
1124 esrc = fib_entry_src_find(fib_entry, source, NULL);
1128 * we are no doubt modifying a path-list. If the path-list
1129 * is shared, and hence not modifiable, then the index returned
1130 * will be for a different path-list. This FIB entry to needs
1131 * to maintain its lock appropriately.
1133 old_path_list = esrc->fes_pl;
1135 ASSERT(NULL != fib_entry_src_vft[source].fesv_path_add);
1137 pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1138 fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1140 fib_entry_src_vft[source].fesv_path_add(esrc, fib_entry, pl_flags, rpath);
1141 fib_entry = fib_entry_get(fib_entry_index);
1144 * re-resolve all the path-extensions with the new path-list
1146 vec_foreach(path_ext, esrc->fes_path_exts)
1148 fib_path_ext_resolve(path_ext, esrc->fes_pl);
1151 * if the path has a label we need to add a path extension
1153 fib_entry_src_path_ext_insert(esrc, rpath);
1155 fib_path_list_lock(esrc->fes_pl);
1156 fib_path_list_unlock(old_path_list);
1162 * fib_entry_src_action_swap
1164 * The source is providing new paths to replace the old ones.
1165 * Adding a source can result in a new fib_entry being created, which
1166 * can inturn mean the pool is realloc'd and thus the entry passed as
1167 * an argument it also realloc'd
1171 fib_entry_src_action_path_swap (fib_entry_t *fib_entry,
1172 fib_source_t source,
1173 fib_entry_flag_t flags,
1174 const fib_route_path_t *rpaths)
1176 fib_node_index_t old_path_list, fib_entry_index;
1177 fib_path_list_flags_t pl_flags;
1178 const fib_route_path_t *rpath;
1179 fib_path_ext_t *path_ext;
1180 fib_entry_src_t *esrc;
1182 esrc = fib_entry_src_find(fib_entry, source, NULL);
1185 * save variable so we can recover from a fib_entry realloc.
1187 fib_entry_index = fib_entry_get_index(fib_entry);
1191 fib_entry = fib_entry_src_action_add(fib_entry,
1196 fib_entry_get_proto(fib_entry))));
1197 esrc = fib_entry_src_find(fib_entry, source, NULL);
1201 * swapping paths may create a new path-list (or may use an existing shared)
1202 * but we are certainly getting a different one. This FIB entry to needs
1203 * to maintain its lock appropriately.
1205 old_path_list = esrc->fes_pl;
1207 ASSERT(NULL != fib_entry_src_vft[source].fesv_path_swap);
1209 pl_flags = fib_entry_src_flags_2_path_list_flags(flags);
1211 vec_foreach(rpath, rpaths)
1213 fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1216 fib_entry_src_vft[source].fesv_path_swap(esrc,
1221 vec_foreach(path_ext, esrc->fes_path_exts)
1223 vec_free(path_ext->fpe_label_stack);
1225 vec_free(esrc->fes_path_exts);
1227 vec_foreach(rpath, rpaths)
1229 fib_entry_src_path_ext_append(esrc, rpath);
1232 fib_entry = fib_entry_get(fib_entry_index);
1234 fib_path_list_lock(esrc->fes_pl);
1235 fib_path_list_unlock(old_path_list);
1240 fib_entry_src_flag_t
1241 fib_entry_src_action_path_remove (fib_entry_t *fib_entry,
1242 fib_source_t source,
1243 const fib_route_path_t *rpath)
1245 fib_path_list_flags_t pl_flags;
1246 fib_node_index_t old_path_list;
1247 fib_path_ext_t *path_ext;
1248 fib_entry_src_t *esrc;
1250 esrc = fib_entry_src_find(fib_entry, source, NULL);
1252 ASSERT(NULL != esrc);
1253 ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
1256 * we no doubt modifying a path-list. If the path-list
1257 * is shared, and hence not modifiable, then the index returned
1258 * will be for a different path-list. This FIB entry to needs
1259 * to maintain its lock appropriately.
1261 old_path_list = esrc->fes_pl;
1263 ASSERT(NULL != fib_entry_src_vft[source].fesv_path_remove);
1265 pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1266 fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1268 fib_entry_src_vft[source].fesv_path_remove(esrc, pl_flags, rpath);
1270 * find the matching path extension and remove it
1272 vec_foreach(path_ext, esrc->fes_path_exts)
1274 if (!fib_path_ext_cmp(path_ext, rpath))
1277 * delete the element moving the remaining elements down 1 position.
1278 * this preserves the sorted order.
1280 vec_free(path_ext->fpe_label_stack);
1281 vec_delete(esrc->fes_path_exts, 1, (path_ext - esrc->fes_path_exts));
1286 * re-resolve all the path-extensions with the new path-list
1288 vec_foreach(path_ext, esrc->fes_path_exts)
1290 fib_path_ext_resolve(path_ext, esrc->fes_pl);
1294 * lock the new path-list, unlock the old if it had one
1296 fib_path_list_unlock(old_path_list);
1298 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) {
1299 fib_path_list_lock(esrc->fes_pl);
1300 return (FIB_ENTRY_SRC_FLAG_ADDED);
1305 * no more paths left from this source
1307 fib_entry_src_action_remove(fib_entry, source);
1308 return (FIB_ENTRY_SRC_FLAG_NONE);
1313 fib_entry_src_format (fib_entry_t *fib_entry,
1314 fib_source_t source,
1317 fib_entry_src_t *esrc;
1319 esrc = fib_entry_src_find(fib_entry, source, NULL);
1321 if (NULL != fib_entry_src_vft[source].fesv_format)
1323 return (fib_entry_src_vft[source].fesv_format(esrc, s));
1329 fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index,
1330 fib_source_t source)
1332 fib_entry_t *fib_entry;
1333 fib_entry_src_t *esrc;
1335 if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1336 return (ADJ_INDEX_INVALID);
1338 fib_entry = fib_entry_get(fib_entry_index);
1339 esrc = fib_entry_src_find(fib_entry, source, NULL);
1343 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1345 return (fib_path_list_get_adj(
1347 fib_entry_get_default_chain_type(fib_entry)));
1350 return (ADJ_INDEX_INVALID);
1354 fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
1355 fib_source_t source,
1358 fib_entry_t *fib_entry;
1359 fib_entry_src_t *esrc;
1361 if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1364 fib_entry = fib_entry_get(fib_entry_index);
1365 esrc = fib_entry_src_find(fib_entry, source, NULL);
1369 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1371 fib_path_list_contribute_forwarding(
1373 fib_entry_get_default_chain_type(fib_entry),
1376 return (dpo_id_is_valid(dpo));
1383 fib_entry_get_resolving_interface_for_source (fib_node_index_t entry_index,
1384 fib_source_t source)
1386 fib_entry_t *fib_entry;
1387 fib_entry_src_t *esrc;
1389 fib_entry = fib_entry_get(entry_index);
1391 esrc = fib_entry_src_find(fib_entry, source, NULL);
1395 if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1397 return (fib_path_list_get_resolving_interface(esrc->fes_pl));
1404 fib_entry_get_flags_for_source (fib_node_index_t entry_index,
1405 fib_source_t source)
1407 fib_entry_t *fib_entry;
1408 fib_entry_src_t *esrc;
1410 fib_entry = fib_entry_get(entry_index);
1412 esrc = fib_entry_src_find(fib_entry, source, NULL);
1416 return (esrc->fes_entry_flags);
1419 return (FIB_ENTRY_FLAG_NONE);
1423 fib_entry_get_flags_i (const fib_entry_t *fib_entry)
1425 fib_entry_flag_t flags;
1428 * the vector of sources is deliberately arranged in priority order
1430 if (0 == vec_len(fib_entry->fe_srcs))
1432 flags = FIB_ENTRY_FLAG_NONE;
1436 fib_entry_src_t *esrc;
1438 esrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
1439 flags = esrc->fes_entry_flags;
1446 fib_entry_set_source_data (fib_node_index_t fib_entry_index,
1447 fib_source_t source,
1450 fib_entry_t *fib_entry;
1451 fib_entry_src_t *esrc;
1453 fib_entry = fib_entry_get(fib_entry_index);
1454 esrc = fib_entry_src_find(fib_entry, source, NULL);
1457 NULL != fib_entry_src_vft[source].fesv_set_data)
1459 fib_entry_src_vft[source].fesv_set_data(esrc, fib_entry, data);
1464 fib_entry_get_source_data (fib_node_index_t fib_entry_index,
1465 fib_source_t source)
1467 fib_entry_t *fib_entry;
1468 fib_entry_src_t *esrc;
1470 fib_entry = fib_entry_get(fib_entry_index);
1471 esrc = fib_entry_src_find(fib_entry, source, NULL);
1474 NULL != fib_entry_src_vft[source].fesv_get_data)
1476 return (fib_entry_src_vft[source].fesv_get_data(esrc, fib_entry));
1482 fib_entry_src_module_init (void)
1484 fib_entry_src_rr_register();
1485 fib_entry_src_interface_register();
1486 fib_entry_src_default_route_register();
1487 fib_entry_src_special_register();
1488 fib_entry_src_api_register();
1489 fib_entry_src_adj_register();
1490 fib_entry_src_mpls_register();
1491 fib_entry_src_lisp_register();