summaryrefslogtreecommitdiffstats
path: root/vnet/vnet/fib/fib_entry_src.c
diff options
context:
space:
mode:
Diffstat (limited to 'vnet/vnet/fib/fib_entry_src.c')
-rw-r--r--vnet/vnet/fib/fib_entry_src.c1278
1 files changed, 1278 insertions, 0 deletions
diff --git a/vnet/vnet/fib/fib_entry_src.c b/vnet/vnet/fib/fib_entry_src.c
new file mode 100644
index 00000000000..f7d84e5ea34
--- /dev/null
+++ b/vnet/vnet/fib/fib_entry_src.c
@@ -0,0 +1,1278 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vnet/adj/adj.h>
+#include <vnet/dpo/load_balance.h>
+#include <vnet/dpo/mpls_label_dpo.h>
+#include <vnet/dpo/drop_dpo.h>
+
+#include "fib_entry_src.h"
+#include "fib_table.h"
+#include "fib_path_ext.h"
+
+/*
+ * per-source type vft
+ */
+static fib_entry_src_vft_t fib_entry_src_vft[FIB_SOURCE_MAX];
+
+static fib_protocol_t
+fib_entry_get_proto (const fib_entry_t * fib_entry)
+{
+ return (fib_entry->fe_prefix.fp_proto);
+}
+
+void
+fib_entry_src_register (fib_source_t source,
+ const fib_entry_src_vft_t *vft)
+{
+ fib_entry_src_vft[source] = *vft;
+}
+
+static int
+fib_entry_src_cmp_for_sort (void * v1,
+ void * v2)
+{
+ fib_entry_src_t *esrc1 = v1, *esrc2 = v2;
+
+ return (esrc1->fes_src - esrc2->fes_src);
+}
+
+void
+fib_entry_src_action_init (fib_entry_t *fib_entry,
+ fib_source_t source)
+
+{
+ fib_entry_src_t esrc = {
+ .fes_pl = FIB_NODE_INDEX_INVALID,
+ .fes_flags = FIB_ENTRY_SRC_FLAG_NONE,
+ .fes_src = source,
+ };
+
+ if (NULL != fib_entry_src_vft[source].fesv_init)
+ {
+ fib_entry_src_vft[source].fesv_init(&esrc);
+ }
+
+ vec_add1(fib_entry->fe_srcs, esrc);
+ vec_sort_with_function(fib_entry->fe_srcs,
+ fib_entry_src_cmp_for_sort);
+}
+
+static fib_entry_src_t *
+fib_entry_src_find (const fib_entry_t *fib_entry,
+ fib_source_t source,
+ u32 *index)
+
+{
+ fib_entry_src_t *esrc;
+ int ii;
+
+ ii = 0;
+ vec_foreach(esrc, fib_entry->fe_srcs)
+ {
+ if (esrc->fes_src == source)
+ {
+ if (NULL != index)
+ {
+ *index = ii;
+ }
+ return (esrc);
+ }
+ else
+ {
+ ii++;
+ }
+ }
+
+ return (NULL);
+}
+
+int
+fib_entry_is_sourced (fib_node_index_t fib_entry_index,
+ fib_source_t source)
+{
+ fib_entry_t *fib_entry;
+
+ fib_entry = fib_entry_get(fib_entry_index);
+
+ return (NULL != fib_entry_src_find(fib_entry, source, NULL));
+}
+
+static fib_entry_src_t *
+fib_entry_src_find_or_create (fib_entry_t *fib_entry,
+ fib_source_t source,
+ u32 *index)
+{
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL == esrc)
+ {
+ fib_entry_src_action_init(fib_entry, source);
+ }
+
+ return (fib_entry_src_find(fib_entry, source, NULL));
+}
+
+void
+fib_entry_src_action_deinit (fib_entry_t *fib_entry,
+ fib_source_t source)
+
+{
+ fib_entry_src_t *esrc;
+ u32 index = ~0;
+
+ esrc = fib_entry_src_find(fib_entry, source, &index);
+
+ ASSERT(NULL != esrc);
+
+ if (NULL != fib_entry_src_vft[source].fesv_deinit)
+ {
+ fib_entry_src_vft[source].fesv_deinit(esrc);
+ }
+
+ vec_free(esrc->fes_path_exts);
+ vec_del1(fib_entry->fe_srcs, index);
+}
+
+fib_entry_src_cover_res_t
+fib_entry_src_action_cover_change (fib_entry_t *fib_entry,
+ fib_source_t source)
+{
+ if (NULL != fib_entry_src_vft[source].fesv_cover_change)
+ {
+ return (fib_entry_src_vft[source].fesv_cover_change(
+ fib_entry_src_find(fib_entry, source, NULL),
+ fib_entry));
+ }
+
+ fib_entry_src_cover_res_t res = {
+ .install = !0,
+ .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
+ };
+ return (res);
+}
+
+fib_entry_src_cover_res_t
+fib_entry_src_action_cover_update (fib_entry_t *fib_entry,
+ fib_source_t source)
+{
+ if (NULL != fib_entry_src_vft[source].fesv_cover_update)
+ {
+ return (fib_entry_src_vft[source].fesv_cover_update(
+ fib_entry_src_find(fib_entry, source, NULL),
+ fib_entry));
+ }
+
+ fib_entry_src_cover_res_t res = {
+ .install = !0,
+ .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
+ };
+ return (res);
+}
+
+typedef struct fib_entry_src_collect_forwarding_ctx_t_
+{
+ load_balance_path_t * next_hops;
+ const fib_entry_t *fib_entry;
+ const fib_entry_src_t *esrc;
+ fib_forward_chain_type_t fct;
+ int is_recursive;
+} fib_entry_src_collect_forwarding_ctx_t;
+
+/**
+ * @brief Determine whether this FIB entry should use a load-balance MAP
+ * to support PIC edge fast convergence
+ */
+load_balance_flags_t
+fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx)
+{
+ /**
+ * We'll use a LB map is the path-list has recursive paths.
+ * recursive paths implies BGP, and hence scale.
+ */
+ if (ctx->is_recursive)
+ {
+ return (LOAD_BALANCE_FLAG_USES_MAP);
+ }
+ return (LOAD_BALANCE_FLAG_NONE);
+}
+
+static int
+fib_entry_src_valid_out_label (mpls_label_t label)
+{
+ return ((MPLS_LABEL_IS_REAL(label) ||
+ MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL == label ||
+ MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL == label ||
+ MPLS_IETF_IMPLICIT_NULL_LABEL == label));
+}
+
+static int
+fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
+ fib_node_index_t path_index,
+ void *arg)
+{
+ fib_entry_src_collect_forwarding_ctx_t *ctx;
+ fib_path_ext_t *path_ext;
+
+ ctx = arg;
+
+ /*
+ * if the path is not resolved, don't include it.
+ */
+ if (!fib_path_is_resolved(path_index))
+ {
+ return (!0);
+ }
+
+ if (fib_path_is_recursive(path_index))
+ {
+ ctx->is_recursive = 1;
+ }
+
+ /*
+ * get the matching path-extension for the path being visited.
+ */
+ vec_foreach(path_ext, ctx->esrc->fes_path_exts)
+ {
+ if (path_ext->fpe_path_index == path_index)
+ break;
+ }
+
+ if (NULL != path_ext &&
+ path_ext->fpe_path_index == path_index &&
+ fib_entry_src_valid_out_label(path_ext->fpe_label))
+ {
+ /*
+ * found a matching extension. stack it to obtain the forwarding
+ * info for this path.
+ */
+ ctx->next_hops = fib_path_ext_stack(path_ext, ctx->fct, ctx->next_hops);
+ }
+ else
+ {
+ load_balance_path_t *nh;
+
+ /*
+ * no extension => no out-going label for this path. that's OK
+ * in the case of an IP or EOS chain, but not for non-EOS
+ */
+ switch (ctx->fct)
+ {
+ case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
+ case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
+ /*
+ * EOS traffic with no label to stack, we need the IP Adj
+ */
+ vec_add2(ctx->next_hops, nh, 1);
+
+ nh->path_index = path_index;
+ nh->path_weight = fib_path_get_weight(path_index);
+ fib_path_contribute_forwarding(path_index, ctx->fct, &nh->path_dpo);
+
+ break;
+ case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
+ if (fib_path_is_exclusive(path_index) ||
+ fib_path_is_deag(path_index))
+ {
+ vec_add2(ctx->next_hops, nh, 1);
+
+ nh->path_index = path_index;
+ nh->path_weight = fib_path_get_weight(path_index);
+ fib_path_contribute_forwarding(path_index,
+ FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
+ &nh->path_dpo);
+ }
+ break;
+ case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
+ ASSERT(0);
+ break;
+ }
+ }
+
+ return (!0);
+}
+
+void
+fib_entry_src_mk_lb (fib_entry_t *fib_entry,
+ const fib_entry_src_t *esrc,
+ fib_forward_chain_type_t fct,
+ dpo_id_t *dpo_lb)
+{
+ dpo_proto_t lb_proto;
+
+ /*
+ * If the entry has path extensions then we construct a load-balance
+ * by stacking the extensions on the forwarding chains of the paths.
+ * Otherwise we use the load-balance of the path-list
+ */
+ fib_entry_src_collect_forwarding_ctx_t ctx = {
+ .esrc = esrc,
+ .fib_entry = fib_entry,
+ .next_hops = NULL,
+ .is_recursive = 0,
+ .fct = fct,
+ };
+
+ lb_proto = fib_proto_to_dpo(fib_entry_get_proto(fib_entry));
+
+ fib_path_list_walk(esrc->fes_pl,
+ fib_entry_src_collect_forwarding,
+ &ctx);
+
+ if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE)
+ {
+ /*
+ * the client provided the DPO that the entry should link to.
+ * all entries must link to a LB, so if it is an LB already
+ * then we can use it.
+ */
+ if ((1 == vec_len(ctx.next_hops)) &&
+ (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type))
+ {
+ dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo);
+ dpo_reset(&ctx.next_hops[0].path_dpo);
+ return;
+ }
+ }
+
+ if (!dpo_id_is_valid(dpo_lb))
+ {
+ /*
+ * first time create
+ */
+ flow_hash_config_t fhc;
+
+ fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index,
+ dpo_proto_to_fib(lb_proto));
+ dpo_set(dpo_lb,
+ DPO_LOAD_BALANCE,
+ lb_proto,
+ load_balance_create(0, lb_proto, fhc));
+ }
+
+ load_balance_multipath_update(dpo_lb,
+ ctx.next_hops,
+ fib_entry_calc_lb_flags(&ctx));
+}
+
+void
+fib_entry_src_action_install (fib_entry_t *fib_entry,
+ fib_source_t source)
+{
+ /*
+ * Install the forwarding chain for the given source into the forwarding
+ * tables
+ */
+ fib_forward_chain_type_t fct;
+ fib_entry_src_t *esrc;
+
+ fct = fib_entry_get_default_chain_type(fib_entry);
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb[fct]);
+
+ FIB_ENTRY_DBG(fib_entry, "install: %d",
+ fib_entry->fe_lb[fct]);
+
+ /*
+ * insert the adj into the data-plane forwarding trie
+ */
+ fib_table_fwding_dpo_update(fib_entry->fe_fib_index,
+ &fib_entry->fe_prefix,
+ &fib_entry->fe_lb[fct]);
+
+ if (FIB_FORW_CHAIN_TYPE_UNICAST_IP4 == fct ||
+ FIB_FORW_CHAIN_TYPE_UNICAST_IP6 == fct)
+ {
+ for (fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
+ fct <= FIB_FORW_CHAIN_TYPE_MPLS_EOS;
+ fct++)
+ {
+ /*
+ * if any of the other chain types are already created they will need
+ * updating too
+ */
+ if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
+ {
+ fib_entry_src_mk_lb(fib_entry,
+ esrc,
+ fct,
+ &fib_entry->fe_lb[fct]);
+ }
+ }
+ }
+}
+
+void
+fib_entry_src_action_uninstall (fib_entry_t *fib_entry)
+{
+ fib_forward_chain_type_t fct;
+
+ fct = fib_entry_get_default_chain_type(fib_entry);
+ /*
+ * uninstall the forwarding chain for the given source from the
+ * forwarding tables
+ */
+ FIB_ENTRY_DBG(fib_entry, "uninstall: %d",
+ fib_entry->fe_adj_index);
+
+ if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
+ {
+ /* fib_forward_chain_type_t fct; */
+ /* fib_path_ext_t *path_ext; */
+
+ fib_table_fwding_dpo_remove(
+ fib_entry->fe_fib_index,
+ &fib_entry->fe_prefix,
+ &fib_entry->fe_lb[fct]);
+
+ dpo_reset(&fib_entry->fe_lb[fct]);
+ }
+}
+
+static void
+fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
+{
+ fib_node_index_t *entries = NULL;
+
+ fib_path_list_recursive_loop_detect(path_list_index, &entries);
+
+ vec_free(entries);
+}
+
+void
+fib_entry_src_action_activate (fib_entry_t *fib_entry,
+ fib_source_t source)
+
+{
+ int houston_we_are_go_for_install;
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
+ ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
+
+ esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE;
+
+ if (NULL != fib_entry_src_vft[source].fesv_activate)
+ {
+ houston_we_are_go_for_install =
+ fib_entry_src_vft[source].fesv_activate(esrc, fib_entry);
+ }
+ else
+ {
+ /*
+ * the source is not providing an activate function, we'll assume
+ * therefore it has no objection to installing the entry
+ */
+ houston_we_are_go_for_install = !0;
+ }
+
+ /*
+ * link to the path-list provided by the source, and go check
+ * if that forms any loops in the graph.
+ */
+ fib_entry->fe_parent = esrc->fes_pl;
+ fib_entry->fe_sibling =
+ fib_path_list_child_add(fib_entry->fe_parent,
+ FIB_NODE_TYPE_ENTRY,
+ fib_entry_get_index(fib_entry));
+
+ fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
+
+ FIB_ENTRY_DBG(fib_entry, "activate: %d",
+ fib_entry->fe_parent);
+
+ if (0 != houston_we_are_go_for_install)
+ {
+ fib_entry_src_action_install(fib_entry, source);
+ }
+ else
+ {
+ fib_entry_src_action_uninstall(fib_entry);
+ }
+}
+
+void
+fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
+ fib_source_t source)
+
+{
+ fib_node_index_t path_list_index;
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
+
+ if (NULL != fib_entry_src_vft[source].fesv_deactivate)
+ {
+ fib_entry_src_vft[source].fesv_deactivate(esrc, fib_entry);
+ }
+
+ esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
+
+ FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
+
+ /*
+ * un-link from an old path-list. Check for any loops this will clear
+ */
+ path_list_index = fib_entry->fe_parent;
+ fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
+
+ fib_entry_recursive_loop_detect_i(path_list_index);
+
+ /*
+ * this will unlock the path-list, so it may be invalid thereafter.
+ */
+ fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
+ fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
+}
+
+static void
+fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
+ fib_source_t source)
+{
+ fib_entry_src_t *esrc;
+
+ vec_foreach(esrc, fib_entry->fe_srcs)
+ {
+ if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update)
+ {
+ fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc,
+ fib_entry,
+ source);
+ }
+ }
+}
+
+void
+fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
+ fib_source_t source)
+{
+ fib_node_index_t path_list_index;
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
+
+ FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
+ fib_entry->fe_parent,
+ esrc->fes_pl);
+
+ if (fib_entry->fe_parent != esrc->fes_pl)
+ {
+ /*
+ * un-link from an old path-list. Check for any loops this will clear
+ */
+ path_list_index = fib_entry->fe_parent;
+ fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
+
+ /*
+ * temporary lock so it doesn't get deleted when this entry is no
+ * longer a child.
+ */
+ fib_path_list_lock(path_list_index);
+
+ /*
+ * this entry is no longer a child. after unlinking check if any loops
+ * were broken
+ */
+ fib_path_list_child_remove(path_list_index,
+ fib_entry->fe_sibling);
+
+ fib_entry_recursive_loop_detect_i(path_list_index);
+
+ /*
+ * link to the path-list provided by the source, and go check
+ * if that forms any loops in the graph.
+ */
+ fib_entry->fe_parent = esrc->fes_pl;
+ fib_entry->fe_sibling =
+ fib_path_list_child_add(fib_entry->fe_parent,
+ FIB_NODE_TYPE_ENTRY,
+ fib_entry_get_index(fib_entry));
+
+ fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
+ fib_path_list_unlock(path_list_index);
+ }
+ fib_entry_src_action_install(fib_entry, source);
+ fib_entry_src_action_fwd_update(fib_entry, source);
+}
+
+void
+fib_entry_src_action_installed (const fib_entry_t *fib_entry,
+ fib_source_t source)
+{
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL != fib_entry_src_vft[source].fesv_installed)
+ {
+ fib_entry_src_vft[source].fesv_installed(esrc,
+ fib_entry);
+ }
+
+ fib_entry_src_action_fwd_update(fib_entry, source);
+}
+
+/*
+ * fib_entry_src_action_add
+ *
+ * Adding a source can result in a new fib_entry being created, which
+ * can inturn mean the pool is realloc'd and thus the entry passed as
+ * an argument it also realloc'd
+ * @return the original entry
+ */
+fib_entry_t *
+fib_entry_src_action_add (fib_entry_t *fib_entry,
+ fib_source_t source,
+ fib_entry_flag_t flags,
+ const dpo_id_t *dpo)
+{
+ fib_node_index_t fib_entry_index;
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find_or_create(fib_entry, source, NULL);
+
+ esrc->fes_ref_count++;
+
+ if (1 != esrc->fes_ref_count)
+ {
+ /*
+ * we only want to add the source on the 0->1 transition
+ */
+ return (fib_entry);
+ }
+
+ esrc->fes_entry_flags = flags;
+
+ /*
+ * save variable so we can recover from a fib_entry realloc.
+ */
+ fib_entry_index = fib_entry_get_index(fib_entry);
+
+ if (NULL != fib_entry_src_vft[source].fesv_add)
+ {
+ fib_entry_src_vft[source].fesv_add(esrc,
+ fib_entry,
+ flags,
+ fib_entry_get_proto(fib_entry),
+ dpo);
+ }
+
+ fib_entry = fib_entry_get(fib_entry_index);
+
+ esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
+
+ fib_path_list_lock(esrc->fes_pl);
+
+ /*
+ * the source owns a lock on the entry
+ */
+ fib_entry_lock(fib_entry_get_index(fib_entry));
+
+ return (fib_entry);
+}
+
+fib_entry_src_flag_t
+fib_entry_src_action_remove (fib_entry_t *fib_entry,
+ fib_source_t source)
+
+{
+ fib_node_index_t old_path_list;
+ fib_entry_src_flag_t sflags;
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL == esrc)
+ return (FIB_ENTRY_SRC_FLAG_ACTIVE);
+
+ esrc->fes_ref_count--;
+ sflags = esrc->fes_flags;
+
+ if (0 != esrc->fes_ref_count)
+ {
+ /*
+ * only remove the source on the 1->0 transisition
+ */
+ return (sflags);
+ }
+
+ if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
+ {
+ fib_entry_src_action_deactivate(fib_entry, source);
+ }
+
+ old_path_list = esrc->fes_pl;
+
+ if (NULL != fib_entry_src_vft[source].fesv_remove)
+ {
+ fib_entry_src_vft[source].fesv_remove(esrc);
+ }
+
+ fib_path_list_unlock(old_path_list);
+ fib_entry_unlock(fib_entry_get_index(fib_entry));
+
+ sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
+ fib_entry_src_action_deinit(fib_entry, source);
+
+ return (sflags);
+}
+
+static inline int
+fib_route_recurses_via_self (const fib_prefix_t *prefix,
+ const fib_route_path_t *rpath)
+{
+ /*
+ * not all zeros next hop &&
+ * is recursive path &&
+ * nexthop is same as the route's address
+ */
+ return ((!ip46_address_is_zero(&rpath->frp_addr)) &&
+ (~0 == rpath->frp_sw_if_index) &&
+ (0 == ip46_address_cmp(&rpath->frp_addr, &prefix->fp_addr)));
+
+}
+
+/*
+ * fib_route_attached_cross_table
+ *
+ * Return true the the route is attached via an interface that
+ * is not in the same table as the route
+ */
+static inline int
+fib_route_attached_cross_table (const fib_entry_t *fib_entry,
+ const fib_route_path_t *rpath)
+{
+ /*
+ * - All zeros next-hop
+ * - a valid interface
+ * - entry's fib index not equeal to interface's index
+ */
+ if (ip46_address_is_zero(&rpath->frp_addr) &&
+ (~0 != rpath->frp_sw_if_index) &&
+ (fib_entry->fe_fib_index !=
+ fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
+ rpath->frp_sw_if_index)))
+ {
+ return (!0);
+ }
+ return (0);
+}
+
+/*
+ * fib_route_attached_cross_table
+ *
+ * Return true the the route is attached via an interface that
+ * is not in the same table as the route
+ */
+static inline int
+fib_path_is_attached (const fib_route_path_t *rpath)
+{
+ /*
+ * - All zeros next-hop
+ * - a valid interface
+ */
+ if (ip46_address_is_zero(&rpath->frp_addr) &&
+ (~0 != rpath->frp_sw_if_index))
+ {
+ return (!0);
+ }
+ return (0);
+}
+
+fib_path_list_flags_t
+fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
+{
+ fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
+
+ if (eflags & FIB_ENTRY_FLAG_DROP)
+ {
+ plf |= FIB_PATH_LIST_FLAG_DROP;
+ }
+ if (eflags & FIB_ENTRY_FLAG_LOCAL)
+ {
+ plf |= FIB_PATH_LIST_FLAG_LOCAL;
+ }
+ if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
+ {
+ plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
+ }
+
+ return (plf);
+}
+
+static void
+fib_entry_flags_update (const fib_entry_t *fib_entry,
+ const fib_route_path_t *rpath,
+ fib_path_list_flags_t *pl_flags,
+ fib_entry_src_t *esrc)
+{
+ /*
+ * don't allow the addition of a recursive looped path for prefix
+ * via itself.
+ */
+ if (fib_route_recurses_via_self(&fib_entry->fe_prefix, rpath))
+ {
+ /*
+ * force the install of a drop path-list.
+ * we want the entry to have some path-list, mainly so
+ * the dodgy path can be rmeoved when the source stops playing
+ * silly buggers.
+ */
+ *pl_flags |= FIB_PATH_LIST_FLAG_DROP;
+ }
+ else
+ {
+ *pl_flags &= ~FIB_PATH_LIST_FLAG_DROP;
+ }
+
+ if ((esrc->fes_src == FIB_SOURCE_API) ||
+ (esrc->fes_src == FIB_SOURCE_CLI))
+ {
+ if (fib_path_is_attached(rpath))
+ {
+ esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
+ }
+ else
+ {
+ esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
+ }
+ }
+ if (fib_route_attached_cross_table(fib_entry, rpath))
+ {
+ esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
+ }
+ else
+ {
+ esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
+ }
+}
+
+/*
+ * fib_entry_src_path_ext_add
+ *
+ * append a path extension to the entry's list
+ */
+static void
+fib_entry_src_path_ext_append (fib_entry_src_t *esrc,
+ const fib_route_path_t *rpath)
+{
+ if (MPLS_LABEL_INVALID != rpath->frp_label)
+ {
+ fib_path_ext_t *path_ext;
+
+ vec_add2(esrc->fes_path_exts, path_ext, 1);
+
+ fib_path_ext_init(path_ext, esrc->fes_pl, rpath);
+ }
+}
+
+/*
+ * fib_entry_src_path_ext_insert
+ *
+ * insert, sorted, a path extension to the entry's list.
+ * It's not strictly necessary in sort the path extensions, since each
+ * extension has the path index to which it resolves. However, by being
+ * sorted the load-balance produced has a deterministic order, not an order
+ * based on the sequence of extension additions. this is a considerable benefit.
+ */
+static void
+fib_entry_src_path_ext_insert (fib_entry_src_t *esrc,
+ const fib_route_path_t *rpath)
+{
+ if (0 == vec_len(esrc->fes_path_exts))
+ return (fib_entry_src_path_ext_append(esrc, rpath));
+
+ if (MPLS_LABEL_INVALID != rpath->frp_label)
+ {
+ fib_path_ext_t path_ext;
+ int i = 0;
+
+ fib_path_ext_init(&path_ext, esrc->fes_pl, rpath);
+
+ while (i < vec_len(esrc->fes_path_exts) &&
+ (fib_path_ext_cmp(&esrc->fes_path_exts[i], rpath) < 0))
+ {
+ i++;
+ }
+
+ vec_insert_elts(esrc->fes_path_exts, &path_ext, 1, i);
+ }
+}
+
+/*
+ * fib_entry_src_action_add
+ *
+ * Adding a source can result in a new fib_entry being created, which
+ * can inturn mean the pool is realloc'd and thus the entry passed as
+ * an argument it also realloc'd
+ * @return the entry
+ */
+fib_entry_t*
+fib_entry_src_action_path_add (fib_entry_t *fib_entry,
+ fib_source_t source,
+ fib_entry_flag_t flags,
+ const fib_route_path_t *rpath)
+{
+ fib_node_index_t old_path_list, fib_entry_index;
+ fib_path_list_flags_t pl_flags;
+ fib_path_ext_t *path_ext;
+ fib_entry_src_t *esrc;
+
+ /*
+ * save variable so we can recover from a fib_entry realloc.
+ */
+ fib_entry_index = fib_entry_get_index(fib_entry);
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+ if (NULL == esrc)
+ {
+ fib_entry =
+ fib_entry_src_action_add(fib_entry,
+ source,
+ flags,
+ drop_dpo_get(
+ fib_proto_to_dpo(
+ fib_entry_get_proto(fib_entry))));
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+ }
+
+ /*
+ * we are no doubt modifying a path-list. If the path-list
+ * is shared, and hence not modifiable, then the index returned
+ * will be for a different path-list. This FIB entry to needs
+ * to maintain its lock appropriately.
+ */
+ old_path_list = esrc->fes_pl;
+
+ ASSERT(NULL != fib_entry_src_vft[source].fesv_path_add);
+
+ pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
+ fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
+
+ fib_entry_src_vft[source].fesv_path_add(esrc, fib_entry, pl_flags, rpath);
+ fib_entry = fib_entry_get(fib_entry_index);
+
+ /*
+ * re-resolve all the path-extensions with the new path-list
+ */
+ vec_foreach(path_ext, esrc->fes_path_exts)
+ {
+ fib_path_ext_resolve(path_ext, esrc->fes_pl);
+ }
+ /*
+ * if the path has a label we need to add a path extension
+ */
+ fib_entry_src_path_ext_insert(esrc, rpath);
+
+ fib_path_list_lock(esrc->fes_pl);
+ fib_path_list_unlock(old_path_list);
+
+ return (fib_entry);
+}
+
+/*
+ * fib_entry_src_action_swap
+ *
+ * The source is providing new paths to replace the old ones.
+ * Adding a source can result in a new fib_entry being created, which
+ * can inturn mean the pool is realloc'd and thus the entry passed as
+ * an argument it also realloc'd
+ * @return the entry
+ */
+fib_entry_t*
+fib_entry_src_action_path_swap (fib_entry_t *fib_entry,
+ fib_source_t source,
+ fib_entry_flag_t flags,
+ const fib_route_path_t *rpaths)
+{
+ fib_node_index_t old_path_list, fib_entry_index;
+ fib_path_list_flags_t pl_flags;
+ const fib_route_path_t *rpath;
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ /*
+ * save variable so we can recover from a fib_entry realloc.
+ */
+ fib_entry_index = fib_entry_get_index(fib_entry);
+
+ if (NULL == esrc)
+ {
+ fib_entry = fib_entry_src_action_add(fib_entry,
+ source,
+ flags,
+ drop_dpo_get(
+ fib_proto_to_dpo(
+ fib_entry_get_proto(fib_entry))));
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+ }
+
+ /*
+ * swapping paths may create a new path-list (or may use an existing shared)
+ * but we are certainly getting a different one. This FIB entry to needs
+ * to maintain its lock appropriately.
+ */
+ old_path_list = esrc->fes_pl;
+
+ ASSERT(NULL != fib_entry_src_vft[source].fesv_path_swap);
+
+ pl_flags = fib_entry_src_flags_2_path_list_flags(
+ fib_entry_get_flags_i(fib_entry));
+ vec_foreach(rpath, rpaths)
+ {
+ fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
+ }
+
+ fib_entry_src_vft[source].fesv_path_swap(esrc,
+ fib_entry,
+ pl_flags,
+ rpaths);
+
+ vec_free(esrc->fes_path_exts);
+ vec_foreach(rpath, rpaths)
+ {
+ fib_entry_src_path_ext_append(esrc, rpath);
+ }
+
+ fib_entry = fib_entry_get(fib_entry_index);
+
+ fib_path_list_lock(esrc->fes_pl);
+ fib_path_list_unlock(old_path_list);
+
+ return (fib_entry);
+}
+
+fib_entry_src_flag_t
+fib_entry_src_action_path_remove (fib_entry_t *fib_entry,
+ fib_source_t source,
+ const fib_route_path_t *rpath)
+{
+ fib_path_list_flags_t pl_flags;
+ fib_node_index_t old_path_list;
+ fib_path_ext_t *path_ext;
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ ASSERT(NULL != esrc);
+ ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
+
+ /*
+ * we no doubt modifying a path-list. If the path-list
+ * is shared, and hence not modifiable, then the index returned
+ * will be for a different path-list. This FIB entry to needs
+ * to maintain its lock appropriately.
+ */
+ old_path_list = esrc->fes_pl;
+
+ ASSERT(NULL != fib_entry_src_vft[source].fesv_path_remove);
+
+ pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
+ fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
+
+ fib_entry_src_vft[source].fesv_path_remove(esrc, pl_flags, rpath);
+ /*
+ * find the matching path extension and remove it
+ */
+ vec_foreach(path_ext, esrc->fes_path_exts)
+ {
+ if (!fib_path_ext_cmp(path_ext, rpath))
+ {
+ /*
+ * delete the element moving the remaining elements down 1 position.
+ * this preserves the sorted order.
+ */
+ vec_delete(esrc->fes_path_exts, 1, (path_ext - esrc->fes_path_exts));
+ break;
+ }
+ }
+ /*
+ * re-resolve all the path-extensions with the new path-list
+ */
+ vec_foreach(path_ext, esrc->fes_path_exts)
+ {
+ fib_path_ext_resolve(path_ext, esrc->fes_pl);
+ }
+
+ /*
+ * lock the new path-list, unlock the old if it had one
+ */
+ fib_path_list_unlock(old_path_list);
+
+ if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) {
+ fib_path_list_lock(esrc->fes_pl);
+ return (FIB_ENTRY_SRC_FLAG_ADDED);
+ }
+ else
+ {
+ /*
+ * no more paths left from this source
+ */
+ fib_entry_src_action_remove(fib_entry, source);
+ return (FIB_ENTRY_SRC_FLAG_NONE);
+ }
+}
+
+u8*
+fib_entry_src_format (fib_entry_t *fib_entry,
+ fib_source_t source,
+ u8* s)
+{
+ fib_entry_src_t *esrc;
+
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL != fib_entry_src_vft[source].fesv_format)
+ {
+ return (fib_entry_src_vft[source].fesv_format(esrc, s));
+ }
+ return (s);
+}
+
+adj_index_t
+fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index,
+ fib_source_t source)
+{
+ fib_entry_t *fib_entry;
+ fib_entry_src_t *esrc;
+
+ if (FIB_NODE_INDEX_INVALID == fib_entry_index)
+ return (ADJ_INDEX_INVALID);
+
+ fib_entry = fib_entry_get(fib_entry_index);
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL != esrc)
+ {
+ if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
+ {
+ return (fib_path_list_get_adj(
+ esrc->fes_pl,
+ fib_entry_get_default_chain_type(fib_entry)));
+ }
+ }
+ return (ADJ_INDEX_INVALID);
+}
+
+const int
+fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
+ fib_source_t source,
+ dpo_id_t *dpo)
+{
+ fib_entry_t *fib_entry;
+ fib_entry_src_t *esrc;
+
+ if (FIB_NODE_INDEX_INVALID == fib_entry_index)
+ return (0);
+
+ fib_entry = fib_entry_get(fib_entry_index);
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL != esrc)
+ {
+ if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
+ {
+ fib_path_list_contribute_forwarding(
+ esrc->fes_pl,
+ fib_entry_get_default_chain_type(fib_entry),
+ dpo);
+
+ return (dpo_id_is_valid(dpo));
+ }
+ }
+ return (0);
+}
+
+fib_entry_flag_t
+fib_entry_get_flags_i (const fib_entry_t *fib_entry)
+{
+ fib_entry_flag_t flags;
+
+ /*
+ * the vector of sources is deliberately arranged in priority order
+ */
+ if (0 == vec_len(fib_entry->fe_srcs))
+ {
+ flags = FIB_ENTRY_FLAG_NONE;
+ }
+ else
+ {
+ fib_entry_src_t *esrc;
+
+ esrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
+ flags = esrc->fes_entry_flags;
+ }
+
+ return (flags);
+}
+
+void
+fib_entry_set_source_data (fib_node_index_t fib_entry_index,
+ fib_source_t source,
+ const void *data)
+{
+ fib_entry_t *fib_entry;
+ fib_entry_src_t *esrc;
+
+ fib_entry = fib_entry_get(fib_entry_index);
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL != esrc &&
+ NULL != fib_entry_src_vft[source].fesv_set_data)
+ {
+ fib_entry_src_vft[source].fesv_set_data(esrc, fib_entry, data);
+ }
+}
+
+const void*
+fib_entry_get_source_data (fib_node_index_t fib_entry_index,
+ fib_source_t source)
+{
+ fib_entry_t *fib_entry;
+ fib_entry_src_t *esrc;
+
+ fib_entry = fib_entry_get(fib_entry_index);
+ esrc = fib_entry_src_find(fib_entry, source, NULL);
+
+ if (NULL != esrc &&
+ NULL != fib_entry_src_vft[source].fesv_get_data)
+ {
+ return (fib_entry_src_vft[source].fesv_get_data(esrc, fib_entry));
+ }
+ return (NULL);
+}
+
+void
+fib_entry_src_module_init (void)
+{
+ fib_entry_src_rr_register();
+ fib_entry_src_interface_register();
+ fib_entry_src_default_route_register();
+ fib_entry_src_special_register();
+ fib_entry_src_api_register();
+ fib_entry_src_adj_register();
+ fib_entry_src_mpls_register();
+ fib_entry_src_lisp_register();
+}