aboutsummaryrefslogtreecommitdiffstats
path: root/src/vnet/fib/fib_path_ext.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/vnet/fib/fib_path_ext.c')
-rw-r--r--src/vnet/fib/fib_path_ext.c438
1 files changed, 438 insertions, 0 deletions
diff --git a/src/vnet/fib/fib_path_ext.c b/src/vnet/fib/fib_path_ext.c
new file mode 100644
index 00000000..4438671b
--- /dev/null
+++ b/src/vnet/fib/fib_path_ext.c
@@ -0,0 +1,438 @@
+/*
+ * 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/mpls/mpls.h>
+#include <vnet/dpo/mpls_label_dpo.h>
+#include <vnet/dpo/load_balance.h>
+#include <vnet/dpo/drop_dpo.h>
+
+#include <vnet/fib/fib_path_ext.h>
+#include <vnet/fib/fib_entry_src.h>
+#include <vnet/fib/fib_path.h>
+#include <vnet/fib/fib_path_list.h>
+#include <vnet/fib/fib_internal.h>
+
+const char *fib_path_ext_adj_flags_names[] = FIB_PATH_EXT_ADJ_ATTR_NAMES;
+
+u8 *
+format_fib_path_ext (u8 * s, va_list * args)
+{
+ fib_path_ext_t *path_ext;
+ u32 ii;
+
+ path_ext = va_arg (*args, fib_path_ext_t *);
+
+ s = format(s, "path:%d ", path_ext->fpe_path_index);
+
+ switch (path_ext->fpe_type)
+ {
+ case FIB_PATH_EXT_MPLS:
+ s = format(s, "labels:",
+ path_ext->fpe_path_index);
+ for (ii = 0; ii < vec_len(path_ext->fpe_path.frp_label_stack); ii++)
+ {
+ s = format(s, "%U ",
+ format_mpls_unicast_label,
+ path_ext->fpe_path.frp_label_stack[ii]);
+ }
+ break;
+ case FIB_PATH_EXT_ADJ: {
+ fib_path_ext_adj_attr_t attr;
+
+ s = format(s, "adj-flags:");
+ if (path_ext->fpe_adj_flags)
+ {
+ FOR_EACH_PATH_EXT_ADJ_ATTR(attr)
+ {
+ s = format(s, "%s", fib_path_ext_adj_flags_names[attr]);
+ }
+ }
+ else
+ {
+ s = format(s, "None");
+ }
+ break;
+ }
+ }
+ return (s);
+}
+
+int
+fib_path_ext_cmp (fib_path_ext_t *path_ext,
+ const fib_route_path_t *rpath)
+{
+ return (fib_route_path_cmp(&path_ext->fpe_path, rpath));
+}
+
+static fib_path_list_walk_rc_t
+fib_path_ext_match (fib_node_index_t pl_index,
+ fib_node_index_t path_index,
+ void *ctx)
+{
+ fib_path_ext_t *path_ext = ctx;
+
+ if (!fib_path_cmp_w_route_path(path_index,
+ &path_ext->fpe_path))
+ {
+ path_ext->fpe_path_index = path_index;
+ return (FIB_PATH_LIST_WALK_STOP);
+ }
+ return (FIB_PATH_LIST_WALK_CONTINUE);
+}
+
+void
+fib_path_ext_resolve (fib_path_ext_t *path_ext,
+ fib_node_index_t path_list_index)
+{
+ /*
+ * Find the path on the path list that this is an extension for
+ */
+ path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
+ fib_path_list_walk(path_list_index,
+ fib_path_ext_match,
+ path_ext);
+}
+
+static void
+fib_path_ext_init (fib_path_ext_t *path_ext,
+ fib_node_index_t path_list_index,
+ fib_path_ext_type_t ext_type,
+ const fib_route_path_t *rpath)
+{
+ path_ext->fpe_path = *rpath;
+ path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
+ path_ext->fpe_adj_flags = FIB_PATH_EXT_ADJ_FLAG_NONE;
+ path_ext->fpe_type = ext_type;
+
+ fib_path_ext_resolve(path_ext, path_list_index);
+}
+
+/**
+ * @brief Return true if the label stack is implicit null
+ */
+static int
+fib_path_ext_is_imp_null (fib_path_ext_t *path_ext)
+{
+ return ((1 == vec_len(path_ext->fpe_label_stack)) &&
+ (MPLS_IETF_IMPLICIT_NULL_LABEL == path_ext->fpe_label_stack[0]));
+}
+
+load_balance_path_t *
+fib_path_ext_stack (fib_path_ext_t *path_ext,
+ fib_forward_chain_type_t child_fct,
+ fib_forward_chain_type_t imp_null_fct,
+ load_balance_path_t *nhs)
+{
+ fib_forward_chain_type_t parent_fct;
+ load_balance_path_t *nh;
+
+ if (!fib_path_is_resolved(path_ext->fpe_path_index))
+ return (nhs);
+
+ /*
+ * Since we are stacking this path-extension, it must have a valid out
+ * label. From the chain type request by the child, determine what
+ * chain type we will request from the parent.
+ */
+ switch (child_fct)
+ {
+ case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
+ {
+ /*
+ * The EOS chain is a tricky since, when the path has an imp NULL one cannot know
+ * the adjacency to link to without knowing what the packets payload protocol
+ * will be once the label is popped.
+ */
+ if (fib_path_ext_is_imp_null(path_ext))
+ {
+ parent_fct = imp_null_fct;
+ }
+ else
+ {
+ /*
+ * we have a label to stack. packets will thus be labelled when
+ * they encounter the child, ergo, non-eos.
+ */
+ parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
+ }
+ break;
+ }
+ case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
+ case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
+ if (fib_path_ext_is_imp_null(path_ext))
+ {
+ /*
+ * implicit-null label for the eos or IP chain, need to pick up
+ * the IP adj
+ */
+ parent_fct = child_fct;
+ }
+ else
+ {
+ /*
+ * we have a label to stack. packets will thus be labelled when
+ * they encounter the child, ergo, non-eos.
+ */
+ parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
+ }
+ break;
+ case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
+ parent_fct = child_fct;
+ break;
+ case FIB_FORW_CHAIN_TYPE_ETHERNET:
+ parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
+ break;
+ default:
+ return (nhs);
+ break;
+ }
+
+ dpo_id_t via_dpo = DPO_INVALID;
+
+ /*
+ * The next object in the graph after the imposition of the label
+ * will be the DPO contributed by the path through which the packets
+ * are to be sent. We stack the MPLS Label DPO on this path DPO
+ */
+ fib_path_contribute_forwarding(path_ext->fpe_path_index,
+ parent_fct,
+ &via_dpo);
+
+ if (dpo_is_drop(&via_dpo) ||
+ load_balance_is_drop(&via_dpo))
+ {
+ /*
+ * don't stack a path extension on a drop. doing so will create
+ * a LB bucket entry on drop, and we will lose a percentage of traffic.
+ */
+ }
+ else
+ {
+ vec_add2(nhs, nh, 1);
+ nh->path_weight = fib_path_get_weight(path_ext->fpe_path_index);
+ nh->path_index = path_ext->fpe_path_index;
+ dpo_copy(&nh->path_dpo, &via_dpo);
+
+ /*
+ * The label is stackable for this chain type
+ * construct the mpls header that will be imposed in the data-path
+ */
+ if (!fib_path_ext_is_imp_null(path_ext))
+ {
+ /*
+ * we use the parent protocol for the label so that
+ * we pickup the correct MPLS imposition nodes to do
+ * ip[46] processing.
+ */
+ dpo_proto_t chain_proto;
+ mpls_eos_bit_t eos;
+ index_t mldi;
+
+ eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
+ MPLS_NON_EOS :
+ MPLS_EOS);
+ chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);
+
+ mldi = mpls_label_dpo_create(path_ext->fpe_label_stack,
+ eos, 255, 0,
+ chain_proto,
+ &nh->path_dpo);
+
+ dpo_set(&nh->path_dpo,
+ DPO_MPLS_LABEL,
+ chain_proto,
+ mldi);
+ }
+ }
+ dpo_reset(&via_dpo);
+
+ return (nhs);
+}
+
+fib_path_ext_t *
+fib_path_ext_list_find (const fib_path_ext_list_t *list,
+ fib_path_ext_type_t ext_type,
+ const fib_route_path_t *rpath)
+{
+ fib_path_ext_t *path_ext;
+
+ vec_foreach(path_ext, list->fpel_exts)
+ {
+ if ((path_ext->fpe_type == ext_type) &&
+ !fib_path_ext_cmp(path_ext, rpath) )
+ {
+ return (path_ext);
+ }
+ }
+ return (NULL);
+}
+
+fib_path_ext_t *
+fib_path_ext_list_find_by_path_index (const fib_path_ext_list_t *list,
+ fib_node_index_t path_index)
+{
+ fib_path_ext_t *path_ext;
+
+ vec_foreach(path_ext, list->fpel_exts)
+ {
+ if (path_ext->fpe_path_index == path_index)
+ {
+ return (path_ext);
+ }
+ }
+ return (NULL);
+}
+
+
+fib_path_ext_t *
+fib_path_ext_list_push_back (fib_path_ext_list_t *list,
+ fib_node_index_t path_list_index,
+ fib_path_ext_type_t ext_type,
+ const fib_route_path_t *rpath)
+{
+ fib_path_ext_t *path_ext;
+
+ path_ext = fib_path_ext_list_find(list, ext_type, rpath);
+
+ if (NULL == path_ext)
+ {
+ vec_add2(list->fpel_exts, path_ext, 1);
+ fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
+ }
+
+ return (path_ext);
+}
+
+/*
+ * insert, sorted, a path extension to the entry's list.
+ * It's not strictly necessary to 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.
+ */
+fib_path_ext_t *
+fib_path_ext_list_insert (fib_path_ext_list_t *list,
+ fib_node_index_t path_list_index,
+ fib_path_ext_type_t ext_type,
+ const fib_route_path_t *rpath)
+{
+ fib_path_ext_t new_path_ext, *path_ext;
+ int i = 0;
+
+ if (0 == fib_path_ext_list_length(list))
+ {
+ return (fib_path_ext_list_push_back(list, path_list_index,
+ ext_type, rpath));
+ }
+
+ fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);
+
+ vec_foreach(path_ext, list->fpel_exts)
+ {
+ int res = fib_path_ext_cmp(path_ext, rpath);
+
+ if (0 == res)
+ {
+ /*
+ * don't add duplicate extensions. modify instead
+ */
+ vec_free(path_ext->fpe_label_stack);
+ *path_ext = new_path_ext;
+ goto done;
+ }
+ else if (res < 0)
+ {
+ i++;
+ }
+ else
+ {
+ break;
+ }
+ }
+ vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
+done:
+ return (&(list->fpel_exts[i]));
+}
+
+void
+fib_path_ext_list_resolve (fib_path_ext_list_t *list,
+ fib_node_index_t path_list_index)
+{
+ fib_path_ext_t *path_ext;
+
+ vec_foreach(path_ext, list->fpel_exts)
+ {
+ fib_path_ext_resolve(path_ext, path_list_index);
+ };
+}
+
+void
+fib_path_ext_list_remove (fib_path_ext_list_t *list,
+ fib_path_ext_type_t ext_type,
+ const fib_route_path_t *rpath)
+{
+ fib_path_ext_t *path_ext;
+
+ path_ext = fib_path_ext_list_find(list, ext_type, rpath);
+
+ if (NULL != path_ext)
+ {
+ /*
+ * delete the element moving the remaining elements down 1 position.
+ * this preserves the sorted order.
+ */
+ vec_free(path_ext->fpe_label_stack);
+ vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
+ }
+}
+
+void
+fib_path_ext_list_flush (fib_path_ext_list_t *list)
+{
+ fib_path_ext_t *path_ext;
+
+ vec_foreach(path_ext, list->fpel_exts)
+ {
+ vec_free(path_ext->fpe_label_stack);
+ };
+ vec_free(list->fpel_exts);
+ list->fpel_exts = NULL;
+}
+
+u8*
+format_fib_path_ext_list (u8 * s, va_list * args)
+{
+ fib_path_ext_list_t *list;
+ fib_path_ext_t *path_ext;
+
+ list = va_arg (*args, fib_path_ext_list_t *);
+
+ if (fib_path_ext_list_length(list))
+ {
+ s = format(s, " Extensions:");
+ vec_foreach(path_ext, list->fpel_exts)
+ {
+ s = format(s, "\n %U", format_fib_path_ext, path_ext);
+ };
+ }
+
+ return (s);
+}
+
+int
+fib_path_ext_list_length (const fib_path_ext_list_t *list)
+{
+ return (vec_len(list->fpel_exts));
+}