BIER

- see draft-ietf-bier-mpls-encapsulation-10
- midpoint, head and tail functions
- supported payload protocols; IPv4 and IPv6 only.

Change-Id: I59d7363bb6fdfdce8e4016a68a9c8f5a5e5791cb
Signed-off-by: Neale Ranns <nranns@cisco.com>

1 files changed, 527 insertions, 0 deletions

diff --git a/src/vnet/bier/bier_fmask.c b/src/vnet/bier/bier_fmask.c
new file mode 100644
index 00000000000..e30425cda4e
--- /dev/null
+++ b/src/vnet/bier/bier_fmask.c
@@ -0,0 +1,527 @@
+/*
+ * 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/fib/fib_entry.h>
+#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_walk.h>
+
+#include <vnet/bier/bier_table.h>
+#include <vnet/bier/bier_fmask.h>
+#include <vnet/bier/bier_bit_string.h>
+#include <vnet/bier/bier_disp_table.h>
+
+#include <vnet/mpls/mpls.h>
+#include <vnet/dpo/drop_dpo.h>
+#include <vnet/dpo/load_balance.h>
+
+/*
+ * attributes names for formatting
+ */
+static const char *const bier_fmask_attr_names[] = BIER_FMASK_ATTR_NAMES;
+
+/*
+ * pool of BIER fmask objects
+ */
+bier_fmask_t *bier_fmask_pool;
+
+static inline index_t
+bier_fmask_get_index (const bier_fmask_t *bfm)
+{
+    return (bfm - bier_fmask_pool);
+}
+
+static void
+bier_fmask_bits_init (bier_fmask_bits_t *bits,
+                      bier_hdr_len_id_t hlid)
+{
+    bits->bfmb_refs = clib_mem_alloc(sizeof(bits->bfmb_refs[0]) *
+                                     bier_hdr_len_id_to_num_bits(hlid));
+    memset(bits->bfmb_refs,
+           0,
+           (sizeof(bits->bfmb_refs[0]) *
+            bier_hdr_len_id_to_num_bits(hlid)));
+
+    bits->bfmb_input_reset_string.bbs_len =
+        bier_hdr_len_id_to_num_buckets(hlid);
+
+    /*
+     * The buckets are accessed in the switch path
+     */
+    bits->bfmb_input_reset_string.bbs_buckets =
+        clib_mem_alloc_aligned(
+            sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
+            bier_hdr_len_id_to_num_buckets(hlid),
+            CLIB_CACHE_LINE_BYTES);
+    memset(bits->bfmb_input_reset_string.bbs_buckets,
+           0,
+           sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
+           bier_hdr_len_id_to_num_buckets(hlid));
+}
+
+static void
+bier_fmask_stack (bier_fmask_t *bfm)
+{
+    dpo_id_t via_dpo = DPO_INVALID;
+
+    if (bfm->bfm_flags & BIER_FMASK_FLAG_DISP)
+    {
+        bier_disp_table_contribute_forwarding(bfm->bfm_disp,
+                                              &via_dpo);
+    }
+    else
+    {
+        fib_entry_contribute_forwarding(bfm->bfm_fei,
+                                        FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
+                                        &via_dpo);
+    }
+
+    /*
+     * If the via fib entry provides no forwarding (i.e. a drop)
+     * then niether does this fmask. That way children consider this fmask
+     * unresolved and other ECMP options are used instead.
+     */
+    if (dpo_is_drop(&via_dpo) ||
+        load_balance_is_drop(&via_dpo))
+    {
+        bfm->bfm_flags &= ~BIER_FMASK_FLAG_FORWARDING;
+    }
+    else
+    {
+        bfm->bfm_flags |= BIER_FMASK_FLAG_FORWARDING;
+    }
+
+    dpo_stack(DPO_BIER_FMASK,
+              DPO_PROTO_BIER,
+              &bfm->bfm_dpo,
+              &via_dpo);
+    dpo_reset(&via_dpo);
+}
+
+void
+bier_fmask_contribute_forwarding (index_t bfmi,
+                                  dpo_id_t *dpo)
+{
+    bier_fmask_t *bfm;
+
+    bfm = bier_fmask_get(bfmi);
+
+    if (bfm->bfm_flags & BIER_FMASK_FLAG_FORWARDING)
+    {
+        dpo_set(dpo,
+                DPO_BIER_FMASK,
+                DPO_PROTO_BIER,
+                bfmi);
+    }
+    else
+    {
+        dpo_copy(dpo, drop_dpo_get(DPO_PROTO_BIER));
+    }
+}
+
+static void
+bier_fmask_resolve (bier_fmask_t *bfm)
+{
+    if (bfm->bfm_flags & BIER_FMASK_FLAG_DISP)
+    {
+        bier_disp_table_lock(bfm->bfm_disp);
+    }
+    else
+    {
+        /*
+         * source a recursive route through which we resolve.
+         */
+        fib_prefix_t pfx = {
+            .fp_addr = bfm->bfm_id.bfmi_nh,
+            .fp_proto = (ip46_address_is_ip4(&(bfm->bfm_id.bfmi_nh)) ?
+                         FIB_PROTOCOL_IP4 :
+                         FIB_PROTOCOL_IP6),
+            .fp_len = (ip46_address_is_ip4(&(bfm->bfm_id.bfmi_nh)) ? 32 : 128),
+        };
+
+        bfm->bfm_fei = fib_table_entry_special_add(0, // default table
+                                                   &pfx,
+                                                   FIB_SOURCE_RR,
+                                                   FIB_ENTRY_FLAG_NONE);
+
+        bfm->bfm_sibling = fib_entry_child_add(bfm->bfm_fei,
+                                               FIB_NODE_TYPE_BIER_FMASK,
+                                               bier_fmask_get_index(bfm));
+    }
+
+    bier_fmask_stack(bfm);
+}
+
+static void
+bier_fmask_unresolve (bier_fmask_t *bfm)
+{
+    if (bfm->bfm_flags & BIER_FMASK_FLAG_DISP)
+    {
+        bier_disp_table_unlock(bfm->bfm_disp);
+    }
+    else
+    {
+        /*
+         * un-source the recursive route through which we resolve.
+         */
+        fib_prefix_t pfx = {
+            .fp_addr = bfm->bfm_id.bfmi_nh,
+            .fp_proto = (ip46_address_is_ip4(&(bfm->bfm_id.bfmi_nh)) ?
+                         FIB_PROTOCOL_IP4 :
+                         FIB_PROTOCOL_IP6),
+            .fp_len = (ip46_address_is_ip4(&(bfm->bfm_id.bfmi_nh)) ? 32 : 128),
+        };
+
+        fib_entry_child_remove(bfm->bfm_fei, bfm->bfm_sibling);
+        fib_table_entry_special_remove(0, &pfx, FIB_SOURCE_RR);
+    }
+    dpo_reset(&bfm->bfm_dpo);
+}
+
+u32
+bier_fmask_child_add (fib_node_index_t bfmi,
+                     fib_node_type_t child_type,
+                     fib_node_index_t child_index)
+{
+    return (fib_node_child_add(FIB_NODE_TYPE_BIER_FMASK,
+                               bfmi,
+                               child_type,
+                               child_index));
+};
+
+void
+bier_fmask_child_remove (fib_node_index_t bfmi,
+                         u32 sibling_index)
+{
+    fib_node_child_remove(FIB_NODE_TYPE_BIER_FMASK,
+                          bfmi,
+                          sibling_index);
+}
+
+static void
+bier_fmask_init (bier_fmask_t *bfm,
+                 const bier_fmask_id_t *fmid,
+                 index_t bti,
+                 const fib_route_path_t *rpath)
+{
+    const bier_table_id_t *btid;
+    mpls_label_t olabel;
+
+    bfm->bfm_id = *fmid;
+    bfm->bfm_fib_index = bti;
+    dpo_reset(&bfm->bfm_dpo);
+
+    if (ip46_address_is_zero(&(bfm->bfm_id.bfmi_nh)))
+    {
+        bfm->bfm_flags |= BIER_FMASK_FLAG_DISP;
+    }
+
+    if (!(bfm->bfm_flags & BIER_FMASK_FLAG_DISP))
+    {
+        olabel = rpath->frp_label_stack[0];
+        vnet_mpls_uc_set_label(&bfm->bfm_label, olabel);
+        vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
+        vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
+        vnet_mpls_uc_set_ttl(&bfm->bfm_label, 0xff);
+        bfm->bfm_label = clib_host_to_net_u32(bfm->bfm_label);
+    }
+    else
+    {
+        bfm->bfm_disp = rpath->frp_bier_fib_index;
+    }
+
+    btid = bier_table_get_id(bfm->bfm_fib_index);
+    bier_fmask_bits_init(&bfm->bfm_bits, btid->bti_hdr_len);
+    bier_fmask_resolve(bfm);
+}
+
+static void
+bier_fmask_destroy (bier_fmask_t *bfm)
+{
+    clib_mem_free(bfm->bfm_bits.bfmb_refs);
+    clib_mem_free(bfm->bfm_bits.bfmb_input_reset_string.bbs_buckets);
+
+    bier_fmask_db_remove(bfm->bfm_fib_index, &(bfm->bfm_id));
+    bier_fmask_unresolve(bfm);
+    pool_put(bier_fmask_pool, bfm);
+}
+
+void
+bier_fmask_unlock (index_t bfmi)
+{
+    bier_fmask_t *bfm;
+
+    if (INDEX_INVALID == bfmi)
+    {
+        return;
+    }
+
+    bfm = bier_fmask_get(bfmi);
+
+    fib_node_unlock(&bfm->bfm_node);
+}
+
+void
+bier_fmask_lock (index_t bfmi)
+{
+    bier_fmask_t *bfm;
+
+    if (INDEX_INVALID == bfmi)
+    {
+        return;
+    }
+
+    bfm = bier_fmask_get(bfmi);
+
+    fib_node_lock(&bfm->bfm_node);
+}
+
+index_t
+bier_fmask_create_and_lock (const bier_fmask_id_t *fmid,
+                            index_t bti,
+                            const fib_route_path_t *rpath)
+{
+    bier_fmask_t *bfm;
+
+    pool_get_aligned(bier_fmask_pool, bfm, CLIB_CACHE_LINE_BYTES);
+
+    memset(bfm, 0, sizeof(*bfm));
+
+    fib_node_init(&bfm->bfm_node, FIB_NODE_TYPE_BIER_FMASK);
+    bier_fmask_init(bfm, fmid, bti, rpath);
+
+    bier_fmask_lock(bier_fmask_get_index(bfm));
+
+    return (bier_fmask_get_index(bfm));
+}
+
+void
+bier_fmask_link (index_t bfmi,
+                 bier_bp_t bp)
+{
+    bier_fmask_t *bfm;
+
+    bfm = bier_fmask_get(bfmi);
+
+    if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
+    {
+        /*
+         * 0 -> 1 transistion - set the bit in the string
+         */
+        bier_bit_string_set_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
+    }
+
+    ++bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
+    ++bfm->bfm_bits.bfmb_count;
+}
+
+void
+bier_fmask_unlink (index_t bfmi,
+                   bier_bp_t bp)
+{
+    bier_fmask_t *bfm;
+
+    bfm = bier_fmask_get(bfmi);
+
+    --bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
+    --bfm->bfm_bits.bfmb_count;
+
+    if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
+    {
+        /*
+         * 1 -> 0 transistion - clear the bit in the string
+         */
+        bier_bit_string_clear_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
+    }
+}
+
+u8*
+format_bier_fmask (u8 *s, va_list *ap)
+{
+    index_t bfmi = va_arg(*ap, index_t);
+    u32 indent = va_arg(*ap, u32);
+    bier_fmask_attributes_t attr;
+    bier_fmask_t *bfm;
+
+    if (pool_is_free_index(bier_fmask_pool, bfmi))
+    {
+        return (format(s, "No BIER f-mask %d", bfmi));
+    }
+
+    bfm = bier_fmask_get(bfmi);
+
+    s = format(s, "fmask: nh:%U bs:%U locks:%d ",
+               format_ip46_address, &bfm->bfm_id.bfmi_nh, IP46_TYPE_ANY,
+               format_bier_bit_string, &bfm->bfm_bits.bfmb_input_reset_string,
+               bfm->bfm_node.fn_locks);
+    s = format(s, "flags:");
+    FOR_EACH_BIER_FMASK_ATTR(attr) {
+        if ((1<<attr) & bfm->bfm_flags) {
+            s = format (s, "%s,", bier_fmask_attr_names[attr]);
+        }
+    }
+    s = format(s, "\n%U%U",
+               format_white_space, indent,
+               format_dpo_id, &bfm->bfm_dpo, indent+2);
+
+    return (s);
+}
+
+
+static fib_node_t *
+bier_fmask_get_node (fib_node_index_t index)
+{
+    bier_fmask_t *bfm = bier_fmask_get(index);
+    return (&(bfm->bfm_node));
+}
+
+static bier_fmask_t*
+bier_fmask_get_from_node (fib_node_t *node)
+{
+    return ((bier_fmask_t*)(((char*)node) -
+                            STRUCT_OFFSET_OF(bier_fmask_t,
+                                             bfm_node)));
+}
+
+/*
+ * bier_fmask_last_lock_gone
+ */
+static void
+bier_fmask_last_lock_gone (fib_node_t *node)
+{
+    bier_fmask_destroy(bier_fmask_get_from_node(node));
+}
+
+/*
+ * bier_fmask_back_walk_notify
+ *
+ * A back walk has reached this BIER fmask
+ */
+static fib_node_back_walk_rc_t
+bier_fmask_back_walk_notify (fib_node_t *node,
+                             fib_node_back_walk_ctx_t *ctx)
+{
+    /*
+     * re-stack the fmask on the n-eos of the via
+     */
+    bier_fmask_t *bfm = bier_fmask_get_from_node(node);
+
+    bier_fmask_stack(bfm);
+
+    /*
+     * propagate further up the graph.
+     * we can do this synchronously since the fan out is small.
+     */
+    fib_walk_sync(FIB_NODE_TYPE_BIER_FMASK, bier_fmask_get_index(bfm), ctx);
+
+    return (FIB_NODE_BACK_WALK_CONTINUE);
+}
+
+/*
+ * The BIER fmask's graph node virtual function table
+ */
+static const fib_node_vft_t bier_fmask_vft = {
+    .fnv_get = bier_fmask_get_node,
+    .fnv_last_lock = bier_fmask_last_lock_gone,
+    .fnv_back_walk = bier_fmask_back_walk_notify,
+};
+
+static void
+bier_fmask_dpo_lock (dpo_id_t *dpo)
+{
+}
+
+static void
+bier_fmask_dpo_unlock (dpo_id_t *dpo)
+{
+}
+
+static void
+bier_fmask_dpo_mem_show (void)
+{
+    fib_show_memory_usage("BIER-fmask",
+                          pool_elts(bier_fmask_pool),
+                          pool_len(bier_fmask_pool),
+                          sizeof(bier_fmask_t));
+}
+
+const static dpo_vft_t bier_fmask_dpo_vft = {
+    .dv_lock = bier_fmask_dpo_lock,
+    .dv_unlock = bier_fmask_dpo_unlock,
+    .dv_mem_show = bier_fmask_dpo_mem_show,
+    .dv_format = format_bier_fmask,
+};
+
+const static char *const bier_fmask_mpls_nodes[] =
+{
+    "bier-output"
+};
+const static char * const * const bier_fmask_nodes[DPO_PROTO_NUM] =
+{
+    [DPO_PROTO_BIER] = bier_fmask_mpls_nodes,
+    [DPO_PROTO_MPLS] = bier_fmask_mpls_nodes,
+};
+
+clib_error_t *
+bier_fmask_module_init (vlib_main_t * vm)
+{
+    fib_node_register_type (FIB_NODE_TYPE_BIER_FMASK, &bier_fmask_vft);
+    dpo_register(DPO_BIER_FMASK, &bier_fmask_dpo_vft, bier_fmask_nodes);
+
+    return (NULL);
+}
+
+VLIB_INIT_FUNCTION (bier_fmask_module_init);
+
+static clib_error_t *
+bier_fmask_show (vlib_main_t * vm,
+                 unformat_input_t * input,
+                 vlib_cli_command_t * cmd)
+{
+    bier_fmask_t *bfm;
+    index_t bfmi;
+
+    bfmi = INDEX_INVALID;
+
+    while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
+        if (unformat (input, "%d", &bfmi))
+        {
+            ;
+        } else
+        {
+            break;
+        }
+    }
+
+    if (INDEX_INVALID == bfmi)
+    {
+        pool_foreach(bfm, bier_fmask_pool,
+        ({
+            vlib_cli_output (vm, "%U",
+                             format_bier_fmask, bier_fmask_get_index(bfm), 0);
+        }));
+    }
+    else
+    {
+        vlib_cli_output (vm, "%U", format_bier_fmask, bfmi, 0);
+    }
+
+    return (NULL);
+}
+
+VLIB_CLI_COMMAND (show_bier_fmask, static) = {
+    .path = "show bier fmask",
+    .short_help = "show bier fmask",
+    .function = bier_fmask_show,
+};