summaryrefslogtreecommitdiffstats
path: root/src/vnet/bier
diff options
context:
space:
mode:
Diffstat (limited to 'src/vnet/bier')
-rw-r--r--src/vnet/bier/bier.api268
-rw-r--r--src/vnet/bier/bier_api.c690
-rw-r--r--src/vnet/bier/bier_bit_string.c109
-rw-r--r--src/vnet/bier/bier_bit_string.h107
-rw-r--r--src/vnet/bier/bier_disp_dispatch_node.c150
-rw-r--r--src/vnet/bier/bier_disp_entry.c385
-rw-r--r--src/vnet/bier/bier_disp_entry.h81
-rw-r--r--src/vnet/bier/bier_disp_lookup_node.c147
-rw-r--r--src/vnet/bier/bier_disp_table.c396
-rw-r--r--src/vnet/bier/bier_disp_table.h110
-rw-r--r--src/vnet/bier/bier_drop.c101
-rw-r--r--src/vnet/bier/bier_entry.c388
-rw-r--r--src/vnet/bier/bier_entry.h94
-rw-r--r--src/vnet/bier/bier_fmask.c527
-rw-r--r--src/vnet/bier/bier_fmask.h198
-rw-r--r--src/vnet/bier/bier_fmask_db.c161
-rw-r--r--src/vnet/bier/bier_fmask_db.h61
-rw-r--r--src/vnet/bier/bier_hdr_inlines.h217
-rw-r--r--src/vnet/bier/bier_imp.c288
-rw-r--r--src/vnet/bier/bier_imp.h87
-rw-r--r--src/vnet/bier/bier_imp_node.c217
-rw-r--r--src/vnet/bier/bier_input.c175
-rw-r--r--src/vnet/bier/bier_input_error.def19
-rw-r--r--src/vnet/bier/bier_lookup.c367
-rw-r--r--src/vnet/bier/bier_lookup_error.def18
-rw-r--r--src/vnet/bier/bier_output.c195
-rw-r--r--src/vnet/bier/bier_output_error.def17
-rw-r--r--src/vnet/bier/bier_table.c744
-rw-r--r--src/vnet/bier/bier_table.h172
-rw-r--r--src/vnet/bier/bier_test.c951
-rw-r--r--src/vnet/bier/bier_types.c190
-rw-r--r--src/vnet/bier/bier_types.h507
-rw-r--r--src/vnet/bier/bier_update.c182
-rw-r--r--src/vnet/bier/bier_update.h24
34 files changed, 8343 insertions, 0 deletions
diff --git a/src/vnet/bier/bier.api b/src/vnet/bier/bier.api
new file mode 100644
index 00000000000..466524cc6a3
--- /dev/null
+++ b/src/vnet/bier/bier.api
@@ -0,0 +1,268 @@
+/*
+ * 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.
+ */
+
+/** \file
+
+ This file defines vpp BIER control-plane API messages which are generally
+ called through a shared memory interface.
+*/
+vl_api_version 1.0.0
+
+/** \brief BIER Table Indentifier
+ @param bt_set
+ @param bt_sub_domain
+ @param bt_bit_header_length
+*/
+typeonly define bier_table_id
+{
+ u8 bt_set;
+ u8 bt_sub_domain;
+ u8 bt_hdr_len_id;
+};
+
+/** \brief BIER Table Add / del route
+ @param client_index - opaque cookie to identify the sender
+ @param context - sender context, to match reply w/ request
+ @param bt_tbl_id - The BIER table-id the route is added in
+ @param bt_mpls_label - The MPLS label for the table
+ @param bt_is_add - Is this a route add or delete
+*/
+autoreply define bier_table_add_del
+{
+ u32 client_index;
+ u32 context;
+ vl_api_bier_table_id_t bt_tbl_id;
+ u32 bt_label;
+ u8 bt_is_add;
+};
+
+define bier_table_dump
+{
+ u32 client_index;
+ u32 context;
+};
+
+define bier_table_details
+{
+ u32 context;
+ u32 bt_label;
+ vl_api_bier_table_id_t bt_tbl_id;
+};
+
+/** \brief FIB path
+ @param sw_if_index - index of the interface
+ @param weight - The weight, for UCMP
+ @param preference - The preference of the path. lowest preference is prefered
+ @param is_local - local if non-zero, else remote
+ @param is_drop - Drop the packet
+ @param is_unreach - Drop the packet and rate limit send ICMP unreachable
+ @param is_prohibit - Drop the packet and rate limit send ICMP prohibited
+ @param afi - the afi of the next hop, IP46_TYPE_IP4=1, IP46_TYPE_IP6=2
+ @param next_hop[16] - the next hop address
+
+ WARNING: this type is replicated, pending cleanup completion
+*/
+typeonly define fib_path3
+{
+ u32 sw_if_index;
+ u32 table_id;
+ u8 weight;
+ u8 preference;
+ u8 is_local;
+ u8 is_drop;
+ u8 is_unreach;
+ u8 is_prohibit;
+ u8 afi;
+ u8 next_hop[16];
+ u32 rpf_id;
+ u8 n_labels;
+ u32 label_stack[16];
+};
+
+/** \brief BIER Route Add / del route
+ @param client_index - opaque cookie to identify the sender
+ @param context - sender context, to match reply w/ request
+ @param br_bp - The Bit-position value
+ @param br_tbl_id - The BIER table-id the route is added in
+ @param br_is_add - Is this a route add or delete
+ @param br_is_replace - Are the paths specfied replacing those already
+ present or are they to be combined.
+ @param br_n_paths - The number of paths
+ @param br_paths - The array of paths
+*/
+autoreply define bier_route_add_del
+{
+ u32 client_index;
+ u32 context;
+ u16 br_bp;
+ u8 br_is_add;
+ u8 br_is_replace;
+ vl_api_bier_table_id_t br_tbl_id;
+ u8 br_n_paths;
+ vl_api_fib_path3_t br_paths[br_n_paths];
+};
+
+define bier_route_dump
+{
+ u32 client_index;
+ u32 context;
+ vl_api_bier_table_id_t br_tbl_id;
+};
+
+define bier_route_details
+{
+ u32 client_index;
+ u32 context;
+ u16 br_bp;
+ vl_api_bier_table_id_t br_tbl_id;
+ u32 br_n_paths;
+ vl_api_fib_path3_t br_paths[br_n_paths];
+};
+
+/** \brief BIER Imposition Add
+ @param client_index - opaque cookie to identify the sender
+ @param context - sender context, to match reply w/ request
+ @param bi_tbl_id - The BIER table-id used to forward post encap
+ @param bi_src - The source Bit-position in the encap.
+ @param bi_is_add - Is this a route add or delete
+ @param bi_n_bytes - The number of bytes in the following bit-string
+ @param bi_bytes - The bit-string represented as a byte array
+*/
+define bier_imp_add
+{
+ u32 client_index;
+ u32 context;
+ vl_api_bier_table_id_t bi_tbl_id;
+ u16 bi_src;
+ u8 bi_is_add;
+ u8 bi_n_bytes;
+ u8 bi_bytes[bi_n_bytes];
+};
+
+/** \brief Reply for BIER route add / del request
+ @param context - returned sender context, to match reply w/ request
+ @param retval - return code
+ @param bi_index - The index of the created imposition object.
+*/
+define bier_imp_add_reply
+{
+ u32 context;
+ i32 retval;
+ u32 bi_index;
+};
+
+/** \brief BIER Imposition Del
+ @param client_index - opaque cookie to identify the sender
+ @param context - sender context, to match reply w/ request
+ @param bi_index - The index of the imposition object (as returned
+ from the ADD)
+*/
+autoreply define bier_imp_del
+{
+ u32 client_index;
+ u32 context;
+ u32 bi_index;
+};
+
+define bier_imp_dump
+{
+ u32 client_index;
+ u32 context;
+};
+
+define bier_imp_details
+{
+ u32 client_index;
+ u32 context;
+ vl_api_bier_table_id_t bi_tbl_id;
+ u16 bi_src;
+ u8 bi_n_bytes;
+ u8 bi_bytes[bi_n_bytes];
+};
+
+/** \brief BIER Disposition Table Add / del route
+ @param client_index - opaque cookie to identify the sender
+ @param context - sender context, to match reply w/ request
+ @param bt_tbl_id - The BIER Disposition table-id.
+*/
+autoreply define bier_disp_table_add_del
+{
+ u32 client_index;
+ u32 context;
+ u32 bdt_tbl_id;
+ u8 bdt_is_add;
+};
+
+define bier_disp_table_dump
+{
+ u32 client_index;
+ u32 context;
+};
+
+define bier_disp_table_details
+{
+ u32 context;
+ u32 bdt_tbl_id;
+};
+
+/** \brief BIER Disposition Entry Add / del
+ @param client_index - opaque cookie to identify the sender
+ @param context - sender context, to match reply w/ request
+ @param bde_bp - The Bit-position value for the entry
+ @param bde_tbl_id - The BIER dispositiontable-id the route is added in
+ @param bde_next_hop_sw_if_index - the nextop interface
+ @param bde_is_add - Is this a route add or delete
+ @param bde_payload_proto - The payload protocol for which the next-hop
+ is added
+ @param bde_next_hop_table_id - The table ID for the next-hop
+ @param bde_next_hop_proto_is_ip4 - The next-hop is IPV4
+ @param bde_next_hop[16] - the nextop address.
+ Set this to all 0s for dispostion.
+*/
+autoreply define bier_disp_entry_add_del
+{
+ u32 client_index;
+ u32 context;
+ u16 bde_bp;
+ u32 bde_tbl_id;
+ u8 bde_is_add;
+ u8 bde_payload_proto;
+ u8 bde_n_paths;
+ vl_api_fib_path3_t bde_paths[bde_n_paths];
+};
+
+define bier_disp_entry_dump
+{
+ u32 client_index;
+ u32 context;
+ u32 bde_tbl_id;
+};
+
+define bier_disp_entry_details
+{
+ u32 context;
+ u16 bde_bp;
+ u32 bde_tbl_id;
+ u8 bde_is_add;
+ u8 bde_payload_proto;
+ u8 bde_n_paths;
+ vl_api_fib_path3_t bde_paths[bde_n_paths];
+};
+
+/*
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vnet/bier/bier_api.c b/src/vnet/bier/bier_api.c
new file mode 100644
index 00000000000..aacee0910bf
--- /dev/null
+++ b/src/vnet/bier/bier_api.c
@@ -0,0 +1,690 @@
+/*
+ *------------------------------------------------------------------
+ * bier_api.c - vnet BIER api
+ *
+ * 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/vnet.h>
+#include <vlibmemory/api.h>
+
+#include <vnet/api_errno.h>
+#include <vnet/bier/bier_table.h>
+#include <vnet/bier/bier_imp.h>
+#include <vnet/bier/bier_disp_table.h>
+#include <vnet/bier/bier_disp_entry.h>
+#include <vnet/bier/bier_bit_string.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+#include <vnet/fib/fib_path_list.h>
+#include <vnet/fib/fib_api.h>
+#include <vnet/fib/fib_table.h>
+#include <vnet/mfib/mfib_table.h>
+
+#include <vnet/vnet_msg_enum.h>
+
+#define vl_typedefs /* define message structures */
+#include <vnet/vnet_all_api_h.h>
+#undef vl_typedefs
+
+#define vl_endianfun /* define message structures */
+#include <vnet/vnet_all_api_h.h>
+#undef vl_endianfun
+
+/* instantiate all the print functions we know about */
+#define vl_print(handle, ...) vlib_cli_output (handle, __VA_ARGS__)
+#define vl_printfun
+#include <vnet/vnet_all_api_h.h>
+#undef vl_printfun
+
+#include <vlibapi/api_helper_macros.h>
+
+#define foreach_bier_api_msg \
+ _(BIER_TABLE_ADD_DEL, bier_table_add_del) \
+ _(BIER_TABLE_DUMP, bier_table_dump) \
+ _(BIER_ROUTE_ADD_DEL, bier_route_add_del) \
+ _(BIER_ROUTE_DUMP, bier_route_dump) \
+ _(BIER_IMP_ADD, bier_imp_add) \
+ _(BIER_IMP_DEL, bier_imp_del) \
+ _(BIER_IMP_DUMP, bier_imp_dump) \
+ _(BIER_DISP_TABLE_ADD_DEL, bier_disp_table_add_del) \
+ _(BIER_DISP_TABLE_DUMP, bier_disp_table_dump) \
+ _(BIER_DISP_ENTRY_ADD_DEL, bier_disp_entry_add_del) \
+ _(BIER_DISP_ENTRY_DUMP, bier_disp_entry_dump)
+
+static void
+vl_api_bier_table_add_del_t_handler (vl_api_bier_table_add_del_t * mp)
+{
+ vl_api_bier_table_add_del_reply_t *rmp;
+ vnet_main_t *vnm;
+ int rv;
+
+ vnm = vnet_get_main ();
+ vnm->api_errno = 0;
+
+ bier_table_id_t bti = {
+ .bti_set = mp->bt_tbl_id.bt_set,
+ .bti_sub_domain = mp->bt_tbl_id.bt_sub_domain,
+ .bti_hdr_len = mp->bt_tbl_id.bt_hdr_len_id,
+ .bti_type = BIER_TABLE_MPLS_SPF,
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+
+ if (mp->bt_is_add)
+ {
+ bier_table_add_or_lock(&bti, ntohl(mp->bt_label));
+ }
+ else
+ {
+ bier_table_unlock(&bti);
+ }
+
+ rv = vnm->api_errno;
+
+ REPLY_MACRO (VL_API_BIER_TABLE_ADD_DEL_REPLY);
+}
+
+static void
+send_bier_table_details (unix_shared_memory_queue_t * q,
+ u32 context,
+ const bier_table_t *bt)
+{
+ vl_api_bier_table_details_t *mp;
+
+ mp = vl_msg_api_alloc(sizeof(*mp));
+ if (!mp)
+ return;
+ memset(mp, 0, sizeof(*mp));
+ mp->_vl_msg_id = ntohs(VL_API_BIER_TABLE_DETAILS);
+ mp->context = context;
+
+ mp->bt_label = bt->bt_ll;
+ mp->bt_tbl_id.bt_set = bt->bt_id.bti_set;
+ mp->bt_tbl_id.bt_sub_domain = bt->bt_id.bti_sub_domain;
+ mp->bt_tbl_id.bt_hdr_len_id = bt->bt_id.bti_hdr_len;
+
+ vl_msg_api_send_shmem (q, (u8 *) & mp);
+}
+
+static void
+vl_api_bier_table_dump_t_handler (vl_api_bier_table_dump_t * mp)
+{
+ unix_shared_memory_queue_t *q;
+ bier_table_t *bt;
+
+ q = vl_api_client_index_to_input_queue (mp->client_index);
+ if (q == 0)
+ return;
+
+ pool_foreach(bt, bier_table_pool,
+ ({
+ /*
+ * skip the ecmp tables.
+ */
+ if (bier_table_is_main(bt))
+ {
+ send_bier_table_details(q, mp->context, bt);
+ }
+ }));
+}
+
+static void
+vl_api_bier_route_add_del_t_handler (vl_api_bier_route_add_del_t * mp)
+{
+ vl_api_bier_route_add_del_reply_t *rmp;
+ fib_route_path_t *brpaths, *brpath;
+ vnet_main_t *vnm;
+ bier_bp_t bp;
+ int rv = 0;
+ u8 ii, jj;
+
+ vnm = vnet_get_main ();
+ vnm->api_errno = 0;
+
+ bp = ntohs(mp->br_bp);
+ brpaths = NULL;
+
+ if (0 == bp || bp > 0xffff)
+ {
+ rv = -1;
+ goto done;
+ }
+
+ bier_table_id_t bti = {
+ .bti_set = mp->br_tbl_id.bt_set,
+ .bti_sub_domain = mp->br_tbl_id.bt_sub_domain,
+ .bti_hdr_len = mp->br_tbl_id.bt_hdr_len_id,
+ .bti_type = BIER_TABLE_MPLS_SPF,
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+
+ vec_validate(brpaths, mp->br_n_paths - 1);
+
+ vec_foreach_index(ii, brpaths)
+ {
+ brpath = &brpaths[ii];
+ memset(brpath, 0, sizeof(*brpath));
+ brpath->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
+
+ vec_validate(brpath->frp_label_stack,
+ mp->br_paths[ii].n_labels);
+ for (jj = 0; jj < mp->br_paths[ii].n_labels; jj++)
+ {
+ brpath->frp_label_stack[jj] =
+ ntohl(mp->br_paths[ii].label_stack[jj]);
+ }
+
+ if (0 == mp->br_paths[ii].afi)
+ {
+ clib_memcpy (&brpath->frp_addr.ip4,
+ mp->br_paths[ii].next_hop,
+ sizeof (brpath->frp_addr.ip4));
+ }
+ else
+ {
+ clib_memcpy (&brpath->frp_addr.ip6,
+ mp->br_paths[ii].next_hop,
+ sizeof (brpath->frp_addr.ip6));
+ }
+ if (ip46_address_is_zero(&brpath->frp_addr))
+ {
+ index_t bdti;
+
+ bdti = bier_disp_table_find(ntohl(mp->br_paths[ii].table_id));
+
+ if (INDEX_INVALID != bdti)
+ brpath->frp_fib_index = bdti;
+ else
+ {
+ rv = VNET_API_ERROR_NO_SUCH_FIB;
+ goto done;
+ }
+ }
+ }
+
+ if (mp->br_is_add)
+ {
+ bier_table_route_add(&bti, ntohs(mp->br_bp), brpaths);
+ }
+ else
+ {
+ bier_table_route_remove(&bti, ntohs(mp->br_bp), brpaths);
+ }
+
+done:
+ vec_free(brpaths);
+ rv = (rv == 0) ? vnm->api_errno : rv;
+
+ REPLY_MACRO (VL_API_BIER_ROUTE_ADD_DEL_REPLY);
+}
+
+typedef struct bier_route_details_walk_t_
+{
+ unix_shared_memory_queue_t * q;
+ u32 context;
+} bier_route_details_walk_t;
+
+static void
+send_bier_route_details (const bier_table_t *bt,
+ const bier_entry_t *be,
+ void *args)
+{
+ fib_route_path_encode_t *api_rpaths = NULL, *api_rpath;
+ bier_route_details_walk_t *ctx = args;
+ vl_api_bier_route_details_t *mp;
+ vl_api_fib_path3_t *fp;
+ u32 n_paths, m_size;
+
+ n_paths = fib_path_list_get_n_paths(be->be_path_list);
+ m_size = sizeof(*mp) + (n_paths * sizeof(vl_api_fib_path3_t));
+ mp = vl_msg_api_alloc(m_size);
+ if (!mp)
+ return;
+
+ memset(mp, 0, m_size);
+ mp->_vl_msg_id = ntohs(VL_API_BIER_ROUTE_DETAILS);
+ mp->context = ctx->context;
+
+ mp->br_tbl_id.bt_set = bt->bt_id.bti_set;
+ mp->br_tbl_id.bt_sub_domain = bt->bt_id.bti_sub_domain;
+ mp->br_tbl_id.bt_hdr_len_id = bt->bt_id.bti_hdr_len;
+ mp->br_bp = htons(be->be_bp);
+ mp->br_n_paths = htonl(n_paths);
+
+ fib_path_list_walk(be->be_path_list, fib_path_encode, &api_rpaths);
+
+ fp = mp->br_paths;
+ vec_foreach (api_rpath, api_rpaths)
+ {
+ fp->weight = api_rpath->rpath.frp_weight;
+ fp->preference = api_rpath->rpath.frp_preference;
+ fp->sw_if_index = htonl (api_rpath->rpath.frp_sw_if_index);
+ fp->n_labels = 0;
+ copy_fib_next_hop (api_rpath, fp);
+ fp++;
+ }
+
+ vl_msg_api_send_shmem (ctx->q, (u8 *) & mp);
+}
+
+static void
+vl_api_bier_route_dump_t_handler (vl_api_bier_route_dump_t * mp)
+{
+ unix_shared_memory_queue_t *q;
+
+ q = vl_api_client_index_to_input_queue (mp->client_index);
+ if (q == 0)
+ return;
+
+ bier_table_id_t bti = {
+ .bti_set = mp->br_tbl_id.bt_set,
+ .bti_sub_domain = mp->br_tbl_id.bt_sub_domain,
+ .bti_hdr_len = mp->br_tbl_id.bt_hdr_len_id,
+ .bti_type = BIER_TABLE_MPLS_SPF,
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+ bier_route_details_walk_t ctx = {
+ .q = q,
+ .context = mp->context,
+ };
+ bier_table_walk(&bti, send_bier_route_details, &ctx);
+}
+
+static void
+vl_api_bier_imp_add_t_handler (vl_api_bier_imp_add_t * mp)
+{
+ vl_api_bier_imp_add_reply_t *rmp;
+ vnet_main_t *vnm;
+ index_t bii;
+ int rv = 0;
+
+ vnm = vnet_get_main ();
+ vnm->api_errno = 0;
+
+ bier_table_id_t bti = {
+ .bti_set = mp->bi_tbl_id.bt_set,
+ .bti_sub_domain = mp->bi_tbl_id.bt_sub_domain,
+ .bti_hdr_len = mp->bi_tbl_id.bt_hdr_len_id,
+ .bti_type = BIER_TABLE_MPLS_SPF,
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+ bier_bit_string_t bs = {
+ .bbs_len = mp->bi_n_bytes,
+ .bbs_buckets = mp->bi_bytes,
+ };
+
+ bii = bier_imp_add_or_lock(&bti, ntohs(mp->bi_src), &bs);
+
+ /* *INDENT-OFF* */
+ REPLY_MACRO2 (VL_API_BIER_IMP_ADD_REPLY,
+ ({
+ rmp->bi_index = bii;
+ }));
+ /* *INDENT-OM* */
+}
+
+static void
+vl_api_bier_imp_del_t_handler (vl_api_bier_imp_del_t * mp)
+{
+ vl_api_bier_imp_del_reply_t *rmp;
+ vnet_main_t *vnm;
+ int rv = 0;
+
+ vnm = vnet_get_main ();
+ vnm->api_errno = 0;
+
+ bier_imp_unlock(ntohl(mp->bi_index));
+
+ REPLY_MACRO(VL_API_BIER_IMP_DEL_REPLY);
+}
+
+static void
+send_bier_imp_details (unix_shared_memory_queue_t * q,
+ u32 context,
+ const bier_imp_t *bi)
+{
+ vl_api_bier_imp_details_t *mp;
+ bier_hdr_t copy;
+ u8 n_bytes;
+
+ copy = bi->bi_hdr;
+ bier_hdr_ntoh(&copy);
+
+ n_bytes = bier_hdr_len_id_to_num_bytes(
+ bier_hdr_get_len_id(&copy));
+ mp = vl_msg_api_alloc(sizeof(*mp) + n_bytes);
+ if (!mp)
+ return;
+ memset(mp, 0, sizeof(*mp)+n_bytes);
+ mp->_vl_msg_id = ntohs(VL_API_BIER_IMP_DETAILS);
+ mp->context = context;
+
+ mp->bi_tbl_id.bt_set = bi->bi_tbl.bti_set;
+ mp->bi_tbl_id.bt_sub_domain = bi->bi_tbl.bti_sub_domain;
+ mp->bi_tbl_id.bt_hdr_len_id = bi->bi_tbl.bti_hdr_len;
+
+
+ mp->bi_src = htons(bier_hdr_get_src_id(&copy));
+ mp->bi_n_bytes = n_bytes;
+ memcpy(mp->bi_bytes, bi->bi_bits.bits, n_bytes);
+
+ vl_msg_api_send_shmem (q, (u8 *) & mp);
+}
+
+static void
+vl_api_bier_imp_dump_t_handler (vl_api_bier_imp_dump_t * mp)
+{
+ unix_shared_memory_queue_t *q;
+ bier_imp_t *bi;
+
+ q = vl_api_client_index_to_input_queue (mp->client_index);
+ if (q == 0)
+ return;
+
+ pool_foreach(bi, bier_imp_pool,
+ ({
+ send_bier_imp_details(q, mp->context, bi);
+ }));
+}
+
+static void
+vl_api_bier_disp_table_add_del_t_handler (vl_api_bier_disp_table_add_del_t * mp)
+{
+ vl_api_bier_disp_table_add_del_reply_t *rmp;
+ vnet_main_t *vnm;
+ u32 table_id;
+ int rv;
+
+ vnm = vnet_get_main ();
+ vnm->api_errno = 0;
+ table_id = ntohl(mp->bdt_tbl_id);
+
+ if (mp->bdt_is_add)
+ {
+ bier_disp_table_add_or_lock(table_id);
+ }
+ else
+ {
+ bier_disp_table_unlock_w_table_id(table_id);
+ }
+
+ rv = vnm->api_errno;
+
+ REPLY_MACRO (VL_API_BIER_DISP_TABLE_ADD_DEL_REPLY);
+}
+
+static void
+send_bier_disp_table_details (unix_shared_memory_queue_t * q,
+ u32 context,
+ const bier_disp_table_t *bdt)
+{
+ vl_api_bier_disp_table_details_t *mp;
+
+ mp = vl_msg_api_alloc(sizeof(*mp));
+ if (!mp)
+ return;
+ memset(mp, 0, sizeof(*mp));
+ mp->_vl_msg_id = ntohs(VL_API_BIER_DISP_TABLE_DETAILS);
+ mp->context = context;
+
+ mp->bdt_tbl_id = htonl(bdt->bdt_table_id);
+
+ vl_msg_api_send_shmem (q, (u8 *) & mp);
+}
+
+static void
+vl_api_bier_disp_table_dump_t_handler (vl_api_bier_disp_table_dump_t * mp)
+{
+ unix_shared_memory_queue_t *q;
+ bier_disp_table_t *bdt;
+
+ q = vl_api_client_index_to_input_queue (mp->client_index);
+ if (q == 0)
+ return;
+
+ pool_foreach(bdt, bier_disp_table_pool,
+ ({
+ send_bier_disp_table_details(q, mp->context, bdt);
+ }));
+}
+
+static void
+vl_api_bier_disp_entry_add_del_t_handler (vl_api_bier_disp_entry_add_del_t * mp)
+{
+ vl_api_bier_disp_entry_add_del_reply_t *rmp;
+ fib_route_path_t *brps = NULL, *brp;
+ vnet_main_t *vnm;
+ bier_bp_t bp;
+ u32 table_id;
+ int rv = 0;
+ u32 ii;
+
+ vnm = vnet_get_main ();
+ vnm->api_errno = 0;
+ table_id = ntohl(mp->bde_tbl_id);
+ bp = ntohs(mp->bde_bp);
+
+ if (0 == bp || bp > 0xffff)
+ {
+ rv = -1;
+ goto done;
+ }
+
+ vec_validate(brps, mp->bde_n_paths - 1);
+ vec_foreach_index(ii, brps)
+ {
+ brp = &brps[ii];
+ brp->frp_fib_index = ntohl(mp->bde_paths[ii].table_id);
+ brp->frp_sw_if_index = ntohl(mp->bde_paths[ii].sw_if_index);
+
+ if (~0 != ntohl(mp->bde_paths[ii].rpf_id))
+ {
+ brp->frp_flags = FIB_ROUTE_PATH_RPF_ID;
+ brp->frp_rpf_id = ntohl(mp->bde_paths[ii].rpf_id);
+ }
+
+ if (0 == mp->bde_paths[ii].afi)
+ {
+ clib_memcpy (&brp->frp_addr.ip4,
+ mp->bde_paths[ii].next_hop,
+ sizeof (brp->frp_addr.ip4));
+ }
+ else
+ {
+ clib_memcpy (&brp->frp_addr.ip6,
+ mp->bde_paths[ii].next_hop,
+ sizeof (brp->frp_addr.ip6));
+ }
+ if (ip46_address_is_zero(&brp->frp_addr))
+ {
+ index_t fti;
+
+ switch (mp->bde_payload_proto)
+ {
+ case BIER_HDR_PROTO_INVALID:
+ case BIER_HDR_PROTO_MPLS_DOWN_STREAM:
+ case BIER_HDR_PROTO_MPLS_UP_STREAM:
+ case BIER_HDR_PROTO_ETHERNET:
+ case BIER_HDR_PROTO_VXLAN:
+ case BIER_HDR_PROTO_CTRL:
+ case BIER_HDR_PROTO_OAM:
+ rv = VNET_API_ERROR_UNSUPPORTED;
+ goto done;
+ break;
+ case BIER_HDR_PROTO_IPV4:
+ case BIER_HDR_PROTO_IPV6:
+ {
+ fib_protocol_t fproto;
+
+ fproto = (mp->bde_payload_proto == BIER_HDR_PROTO_IPV4 ?
+ FIB_PROTOCOL_IP4 :
+ FIB_PROTOCOL_IP6);
+
+ if (brp->frp_flags & FIB_ROUTE_PATH_RPF_ID)
+ {
+ fti = mfib_table_find (fproto,
+ ntohl (mp->bde_paths[ii].table_id));
+ }
+ else
+ {
+ fti = fib_table_find (fproto,
+ ntohl (mp->bde_paths[ii].table_id));
+ }
+
+ if (INDEX_INVALID != fti)
+ {
+ brp->frp_fib_index = fti;
+ }
+ else
+ {
+ rv = VNET_API_ERROR_NO_SUCH_FIB;
+ goto done;
+ }
+ break;
+ }
+ }
+ }
+ }
+
+ if (mp->bde_is_add)
+ {
+ bier_disp_table_entry_path_add(table_id, bp,
+ mp->bde_payload_proto,
+ brps);
+ }
+ else
+ {
+ bier_disp_table_entry_path_remove(table_id, bp,
+ mp->bde_payload_proto,
+ brps);
+ }
+
+done:
+ vec_free(brps);
+ rv = (rv == 0) ? vnm->api_errno : rv;
+
+ REPLY_MACRO (VL_API_BIER_DISP_ENTRY_ADD_DEL_REPLY);
+}
+
+typedef struct bier_disp_entry_details_walk_t_
+{
+ unix_shared_memory_queue_t * q;
+ u32 context;
+} bier_disp_entry_details_walk_t;
+
+static void
+send_bier_disp_entry_details (const bier_disp_table_t *bdt,
+ const bier_disp_entry_t *bde,
+ u16 bp,
+ void *args)
+{
+ fib_route_path_encode_t *api_rpaths = NULL, *api_rpath;
+ bier_disp_entry_details_walk_t *ctx = args;
+ vl_api_bier_disp_entry_details_t *mp;
+ bier_hdr_proto_id_t pproto;
+ vl_api_fib_path3_t *fp;
+ u32 n_paths, m_size;
+
+ FOR_EACH_BIER_HDR_PROTO(pproto)
+ {
+ fib_node_index_t pl = bde->bde_pl[pproto];
+ if (INDEX_INVALID != pl)
+ {
+ n_paths = fib_path_list_get_n_paths(pl);
+ m_size = sizeof(*mp) + (n_paths * sizeof(vl_api_fib_path3_t));
+ mp = vl_msg_api_alloc(m_size);
+ if (!mp)
+ return;
+
+ memset(mp, 0, m_size);
+ mp->_vl_msg_id = ntohs(VL_API_BIER_DISP_ENTRY_DETAILS);
+ mp->context = ctx->context;
+
+ mp->bde_tbl_id = htonl(bdt->bdt_table_id);
+ mp->bde_n_paths = htonl(n_paths);
+ mp->bde_payload_proto = pproto;
+ mp->bde_bp = htons(bp);
+
+ fib_path_list_walk(pl, fib_path_encode, &api_rpaths);
+
+ fp = mp->bde_paths;
+ vec_foreach (api_rpath, api_rpaths)
+ {
+ fp->weight = api_rpath->rpath.frp_weight;
+ fp->preference = api_rpath->rpath.frp_preference;
+ fp->sw_if_index = htonl (api_rpath->rpath.frp_sw_if_index);
+ fp->n_labels = 0;
+ copy_fib_next_hop (api_rpath, fp);
+ fp++;
+ }
+
+ vl_msg_api_send_shmem (ctx->q, (u8 *) & mp);
+ }
+ }
+}
+
+static void
+vl_api_bier_disp_entry_dump_t_handler (vl_api_bier_disp_entry_dump_t * mp)
+{
+ unix_shared_memory_queue_t *q;
+
+ q = vl_api_client_index_to_input_queue (mp->client_index);
+ if (q == 0)
+ return;
+
+ bier_disp_entry_details_walk_t ctx = {
+ .q = q,
+ .context = mp->context,
+ };
+ bier_disp_table_walk(ntohl(mp->bde_tbl_id),
+ send_bier_disp_entry_details,
+ &ctx);
+}
+
+#define vl_msg_name_crc_list
+#include <vnet/bier/bier.api.h>
+#undef vl_msg_name_crc_list
+
+static void
+setup_message_id_table (api_main_t * am)
+{
+#define _(id,n,crc) vl_msg_api_add_msg_name_crc (am, #n "_" #crc, id);
+ foreach_vl_msg_name_crc_bier;
+#undef _
+}
+
+static clib_error_t *
+bier_api_hookup (vlib_main_t * vm)
+{
+ api_main_t *am = &api_main;
+
+#define _(N,n) \
+ vl_msg_api_set_handlers(VL_API_##N, #n, \
+ vl_api_##n##_t_handler, \
+ vl_noop_handler, \
+ vl_api_##n##_t_endian, \
+ vl_api_##n##_t_print, \
+ sizeof(vl_api_##n##_t), 1);
+ foreach_bier_api_msg;
+#undef _
+
+ /*
+ * Set up the (msg_name, crc, message-id) table
+ */
+ setup_message_id_table (am);
+
+ return 0;
+}
+
+VLIB_API_INIT_FUNCTION (bier_api_hookup);
diff --git a/src/vnet/bier/bier_bit_string.c b/src/vnet/bier/bier_bit_string.c
new file mode 100644
index 00000000000..aa42e083be8
--- /dev/null
+++ b/src/vnet/bier/bier_bit_string.c
@@ -0,0 +1,109 @@
+/*
+ * 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/vnet.h>
+
+#include <vnet/bier/bier_types.h>
+#include <vnet/bier/bier_bit_string.h>
+
+/*
+ * the first bit in the first byte is bit position 1.
+ * bit position 0 is not valid
+ */
+#define BIER_GET_STRING_POS(_bp, _byte, _bit, _str) \
+{ \
+ _bp--; \
+ _byte = ((BIER_BBS_LEN_TO_BUCKETS((_str)->bbs_len) - 1 ) - \
+ (_bp / BIER_BIT_MASK_BITS_PER_BUCKET)); \
+ _bit = _bp % BIER_BIT_MASK_BITS_PER_BUCKET; \
+}
+
+static inline int
+bier_bit_pos_is_valid (bier_bp_t bp, const bier_bit_string_t *bbs)
+{
+ if (!((bp <= BIER_BBS_LEN_TO_BITS((bbs)->bbs_len)) &&
+ (bp >= 1))) {
+ return (0);
+ }
+ return (1);
+}
+
+/*
+ * Validate a bit poistion
+ */
+#define BIER_BIT_POS_IS_VALID(_bp, _str) \
+{ \
+ if (!bier_bit_pos_is_valid(_bp, _str)) return; \
+}
+
+void
+bier_bit_string_set_bit (bier_bit_string_t *bit_string,
+ bier_bp_t bp)
+{
+ bier_bit_mask_bucket_t bmask;
+ uint16_t byte_pos, bit_pos;
+
+ BIER_BIT_POS_IS_VALID(bp, bit_string);
+ BIER_GET_STRING_POS(bp, byte_pos, bit_pos, bit_string);
+
+ bmask = ((bier_bit_mask_bucket_t)1 << bit_pos);
+ bit_string->bbs_buckets[byte_pos] |= bmask;
+}
+
+void
+bier_bit_string_clear_bit (bier_bit_string_t *bit_string,
+ bier_bp_t bp)
+{
+ uint16_t byte_pos, bit_pos;
+
+ BIER_BIT_POS_IS_VALID(bp, bit_string);
+ BIER_GET_STRING_POS(bp, byte_pos, bit_pos, bit_string);
+
+ bit_string->bbs_buckets[byte_pos] &= ~(1 << bit_pos);
+}
+
+u8 *
+format_bier_bit_string (u8 * string,
+ va_list * args)
+{
+ bier_bit_string_t *bs = va_arg(*args, bier_bit_string_t *);
+ int leading_marker = 0;
+ int suppress_zero = 0;
+ u16 index;
+ u32 *ptr;
+
+ ptr = (u32 *)bs->bbs_buckets;
+
+ string = format(string, "%d#", (8 * bs->bbs_len));
+
+ for (index = 0; index < (bs->bbs_len/4); index++) {
+ if (!ptr[index]) {
+ if (!leading_marker) {
+ leading_marker = 1;
+ suppress_zero = 1;
+ string = format(string, ":");
+ continue;
+ }
+ if (suppress_zero) continue;
+ } else {
+ suppress_zero = 0;
+ }
+
+ string = format(string, "%s%X", index ? ":" : "",
+ clib_net_to_host_u32(ptr[index]));
+ }
+
+ return (string);
+}
diff --git a/src/vnet/bier/bier_bit_string.h b/src/vnet/bier/bier_bit_string.h
new file mode 100644
index 00000000000..9baebfa6e69
--- /dev/null
+++ b/src/vnet/bier/bier_bit_string.h
@@ -0,0 +1,107 @@
+/*
+ * 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.
+ */
+
+#ifndef __BIER_BIT_STRING_H__
+#define __BIER_BIT_STRING_H__
+
+#include <vppinfra/byte_order.h>
+#include <vppinfra/format.h>
+
+#include <vnet/bier/bier_types.h>
+
+#define BIER_BBS_LEN_TO_BUCKETS(_len) (_len)
+#define BIER_BBS_LEN_TO_BITS(_len) (_len * 8)
+#define BIER_BBS_LEN_TO_INTS(_len) ((_len) / sizeof(int))
+#define BIER_BIT_MASK_BITS_PER_INT (sizeof(int) * 8)
+
+/*
+ * bier_find_first_bit_set
+ *
+ * find the position of the first bit set in a long
+ */
+static inline int
+bier_find_first_bit_string_set (int mask)
+{
+ return (__builtin_ffs(clib_net_to_host_u32(mask)));
+}
+
+extern void bier_bit_string_set_bit(bier_bit_string_t *mask,
+ bier_bp_t bp);
+
+
+extern void bier_bit_string_clear_bit(bier_bit_string_t *mask,
+ bier_bp_t bp);
+
+
+extern u8 *format_bier_bit_string(u8 * s, va_list * args);
+
+#define BIER_BBS_NUM_INT_BUKCETS(_bbs) \
+ (BIER_BBS_LEN_TO_BUCKETS(_bbs->bbs_len) / sizeof(int))
+
+always_inline int
+bier_bit_string_is_zero (const bier_bit_string_t *src)
+{
+ uint16_t index;
+
+ for (index = 0;
+ index < BIER_BBS_NUM_INT_BUKCETS(src);
+ index++) {
+ if (((int*)src->bbs_buckets)[index] != 0) {
+ return (0);
+ }
+ }
+ return (1);
+}
+
+always_inline void
+bier_bit_string_clear_string (const bier_bit_string_t *src,
+ bier_bit_string_t *dest)
+{
+ uint16_t index;
+
+ ASSERT(src->bbs_len == dest->bbs_len);
+
+ for (index = 0;
+ index < BIER_BBS_NUM_INT_BUKCETS(src);
+ index++) {
+ ((int*)dest->bbs_buckets)[index] &= ~(((int*)src->bbs_buckets)[index]);
+ }
+}
+
+always_inline void
+bier_bit_string_logical_and_string (const bier_bit_string_t *src,
+ bier_bit_string_t *dest)
+{
+ uint16_t index;
+
+ ASSERT(src->bbs_len == dest->bbs_len);
+
+ for (index = 0;
+ index < BIER_BBS_NUM_INT_BUKCETS(src);
+ index++) {
+ ((int*)dest->bbs_buckets)[index] &= ((int*)src->bbs_buckets)[index];
+ }
+}
+
+always_inline void
+bier_bit_string_init (bier_bit_string_t *bbs,
+ bier_hdr_len_id_t len,
+ bier_bit_mask_bucket_t *buckets)
+{
+ bbs->bbs_len = bier_hdr_len_id_to_num_bytes(len);
+ bbs->bbs_buckets = buckets;
+}
+
+#endif
diff --git a/src/vnet/bier/bier_disp_dispatch_node.c b/src/vnet/bier/bier_disp_dispatch_node.c
new file mode 100644
index 00000000000..a00c2eea5f9
--- /dev/null
+++ b/src/vnet/bier/bier_disp_dispatch_node.c
@@ -0,0 +1,150 @@
+/*
+ * 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/bier/bier_disp_entry.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+
+/**
+ * @brief A struct to hold tracing information for the MPLS label imposition
+ * node.
+ */
+typedef struct bier_disp_dispatch_trace_t_
+{
+ /**
+ * BIER payload protocol used to dispatch
+ */
+ bier_hdr_proto_id_t pproto;
+
+ /**
+ * RPF-ID packet is tagged with
+ */
+ u32 rpf_id;
+} bier_disp_dispatch_trace_t;
+
+always_inline uword
+bier_disp_dispatch_inline (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * from_frame)
+{
+ u32 n_left_from, next_index, * from, * to_next;
+
+ from = vlib_frame_vector_args (from_frame);
+ n_left_from = from_frame->n_vectors;
+
+ next_index = node->cached_next_index;
+
+ while (n_left_from > 0)
+ {
+ u32 n_left_to_next;
+
+ vlib_get_next_frame(vm, node, next_index, to_next, n_left_to_next);
+
+ while (n_left_from > 0 && n_left_to_next > 0)
+ {
+ bier_hdr_proto_id_t pproto0;
+ bier_disp_entry_t *bde0;
+ u32 next0, bi0, bdei0;
+ const dpo_id_t *dpo0;
+ vlib_buffer_t * b0;
+ bier_hdr_t *hdr0;
+ u32 entropy0;
+
+ bi0 = from[0];
+ to_next[0] = bi0;
+ from += 1;
+ to_next += 1;
+ n_left_from -= 1;
+ n_left_to_next -= 1;
+
+ b0 = vlib_get_buffer (vm, bi0);
+ bdei0 = vnet_buffer(b0)->ip.adj_index[VLIB_TX];
+ hdr0 = vlib_buffer_get_current(b0);
+ bde0 = bier_disp_entry_get(bdei0);
+
+ /*
+ * header is in network order - flip it, we are about to
+ * consume it anyway
+ */
+ bier_hdr_ntoh(hdr0);
+ pproto0 = bier_hdr_get_proto_id(hdr0);
+ entropy0 = bier_hdr_get_entropy(hdr0);
+
+ /*
+ * strip the header and copy the entropy value into
+ * the packets flow-hash field
+ * DSCP mumble mumble...
+ */
+ vlib_buffer_advance(b0, (vnet_buffer(b0)->bier.n_bytes +
+ sizeof(*hdr0)));
+ vnet_buffer(b0)->ip.flow_hash = entropy0;
+
+ /*
+ * use the payload proto to dispatch to the
+ * correct stacked DPO.
+ */
+ dpo0 = &bde0->bde_fwd[pproto0].bde_dpo;
+ next0 = dpo0->dpoi_next_node;
+ vnet_buffer(b0)->ip.adj_index[VLIB_TX] = dpo0->dpoi_index;
+ vnet_buffer(b0)->ip.rpf_id = bde0->bde_fwd[pproto0].bde_rpf_id;
+
+ if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
+ {
+ bier_disp_dispatch_trace_t *tr =
+ vlib_add_trace (vm, node, b0, sizeof (*tr));
+ tr->pproto = pproto0;
+ tr->rpf_id = vnet_buffer(b0)->ip.rpf_id;
+ }
+
+ vlib_validate_buffer_enqueue_x1(vm, node, next_index, to_next,
+ n_left_to_next, bi0, next0);
+ }
+ vlib_put_next_frame (vm, node, next_index, n_left_to_next);
+ }
+ return from_frame->n_vectors;
+}
+
+static u8 *
+format_bier_disp_dispatch_trace (u8 * s, va_list * args)
+{
+ CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
+ CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
+ bier_disp_dispatch_trace_t * t;
+
+ t = va_arg (*args, bier_disp_dispatch_trace_t *);
+ s = format (s, "%U", format_bier_hdr_proto, t->pproto);
+
+ return (s);
+}
+
+static uword
+bier_disp_dispatch (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * frame)
+{
+ return (bier_disp_dispatch_inline(vm, node, frame));
+}
+
+VLIB_REGISTER_NODE (bier_disp_dispatch_node) = {
+ .function = bier_disp_dispatch,
+ .name = "bier-disp-dispatch",
+ .vector_size = sizeof (u32),
+
+ .format_trace = format_bier_disp_dispatch_trace,
+ .n_next_nodes = 1,
+ .next_nodes = {
+ [0] = "bier-drop",
+ }
+};
+VLIB_NODE_FUNCTION_MULTIARCH (bier_disp_dispatch_node, bier_disp_dispatch)
diff --git a/src/vnet/bier/bier_disp_entry.c b/src/vnet/bier/bier_disp_entry.c
new file mode 100644
index 00000000000..3326aba2f86
--- /dev/null
+++ b/src/vnet/bier/bier_disp_entry.c
@@ -0,0 +1,385 @@
+/*
+ * Copyright (c) 2017 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.
+ */
+/**
+ * bier_dispositon : The BIER dispositon object
+ *
+ * A BIER dispositon object is present in the IP mcast output list
+ * and represents the dispositon of a BIER bitmask. After BIER header
+ * dispositon the packet is forward within the appropriate/specifid
+ * BIER table
+ */
+
+#include <vnet/bier/bier_disp_entry.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+#include <vnet/fib/fib_path_list.h>
+#include <vnet/dpo/drop_dpo.h>
+
+/**
+ * The memory pool of all imp objects
+ */
+bier_disp_entry_t *bier_disp_entry_pool;
+
+/**
+ * When constructing the BIER imp ID from an index and BSL, shift
+ * the BSL this far
+ */
+#define BIER_DISP_ENTRY_ID_HLEN_SHIFT 24
+
+static void
+bier_disp_entry_lock_i (bier_disp_entry_t *bde)
+{
+ bde->bde_locks++;
+}
+
+void
+bier_disp_entry_lock (index_t bdei)
+{
+ bier_disp_entry_lock_i(bier_disp_entry_get(bdei));
+}
+
+static index_t
+bier_disp_entry_get_index(bier_disp_entry_t *bde)
+{
+ return (bde - bier_disp_entry_pool);
+}
+
+index_t
+bier_disp_entry_add_or_lock (void)
+{
+ dpo_id_t invalid = DPO_INVALID;
+ bier_hdr_proto_id_t pproto;
+ bier_disp_entry_t *bde;
+
+ pool_get_aligned(bier_disp_entry_pool, bde, CLIB_CACHE_LINE_BYTES);
+
+ bde->bde_locks = 0;
+
+ FOR_EACH_BIER_HDR_PROTO(pproto)
+ {
+ bde->bde_fwd[pproto].bde_dpo = invalid;
+ bde->bde_fwd[pproto].bde_rpf_id = ~0;
+ bde->bde_pl[pproto] = FIB_NODE_INDEX_INVALID;
+ }
+
+ bier_disp_entry_lock_i(bde);
+ return (bier_disp_entry_get_index(bde));
+}
+
+void
+bier_disp_entry_unlock (index_t bdei)
+{
+ bier_disp_entry_t *bde;
+
+ if (INDEX_INVALID == bdei)
+ {
+ return;
+ }
+
+ bde = bier_disp_entry_get(bdei);
+
+ bde->bde_locks--;
+
+ if (0 == bde->bde_locks)
+ {
+ bier_hdr_proto_id_t pproto;
+
+ FOR_EACH_BIER_HDR_PROTO(pproto)
+ {
+ dpo_unlock(&bde->bde_fwd[pproto].bde_dpo);
+ bde->bde_fwd[pproto].bde_rpf_id = ~0;
+ fib_path_list_unlock(bde->bde_pl[pproto]);
+ }
+ pool_put(bier_disp_entry_pool, bde);
+ }
+}
+
+typedef struct bier_disp_entry_path_list_walk_ctx_t_
+{
+ u32 bdew_rpf_id;
+} bier_disp_entry_path_list_walk_ctx_t;
+
+static fib_path_list_walk_rc_t
+bier_disp_entry_path_list_walk (fib_node_index_t pl_index,
+ fib_node_index_t path_index,
+ void *arg)
+{
+ bier_disp_entry_path_list_walk_ctx_t *ctx = arg;
+
+ ctx->bdew_rpf_id = fib_path_get_rpf_id(path_index);
+
+ if (~0 != ctx->bdew_rpf_id)
+ {
+ return (FIB_PATH_LIST_WALK_STOP);
+ }
+ return (FIB_PATH_LIST_WALK_CONTINUE);
+}
+
+static void
+bier_disp_entry_restack (bier_disp_entry_t *bde,
+ bier_hdr_proto_id_t pproto)
+{
+ dpo_id_t via_dpo = DPO_INVALID;
+ fib_node_index_t pli;
+
+ pli = bde->bde_pl[pproto];
+
+ if (FIB_NODE_INDEX_INVALID == pli)
+ {
+ dpo_copy(&via_dpo,
+ drop_dpo_get(bier_hdr_proto_to_dpo(pproto)));
+ }
+ else
+ {
+ fib_path_list_contribute_forwarding(pli,
+ fib_forw_chain_type_from_dpo_proto(
+ bier_hdr_proto_to_dpo(pproto)),
+ &via_dpo);
+
+ bier_disp_entry_path_list_walk_ctx_t ctx = {
+ .bdew_rpf_id = ~0,
+ };
+
+ fib_path_list_walk(pli, bier_disp_entry_path_list_walk, &ctx);
+ bde->bde_fwd[pproto].bde_rpf_id = ctx.bdew_rpf_id;
+ }
+
+ dpo_stack(DPO_BIER_DISP_ENTRY,
+ DPO_PROTO_BIER,
+ &bde->bde_fwd[pproto].bde_dpo,
+ &via_dpo);
+}
+
+void
+bier_disp_entry_path_add (index_t bdei,
+ bier_hdr_proto_id_t pproto,
+ const fib_route_path_t *rpaths)
+{
+ fib_node_index_t *pli, old_pli;
+ bier_disp_entry_t *bde;
+
+ bde = bier_disp_entry_get(bdei);
+ pli = &bde->bde_pl[pproto];
+ old_pli = *pli;
+
+ /*
+ * create a new or update the exisitng path-list for this
+ * payload protocol
+ */
+ if (FIB_NODE_INDEX_INVALID == *pli)
+ {
+ *pli = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
+ FIB_PATH_LIST_FLAG_NO_URPF),
+ rpaths);
+ }
+ else
+ {
+ *pli = fib_path_list_copy_and_path_add(old_pli,
+ (FIB_PATH_LIST_FLAG_SHARED |
+ FIB_PATH_LIST_FLAG_NO_URPF),
+ rpaths);
+ }
+
+ fib_path_list_lock(*pli);
+ fib_path_list_unlock(old_pli);
+
+ bier_disp_entry_restack(bde, pproto);
+}
+
+int
+bier_disp_entry_path_remove (index_t bdei,
+ bier_hdr_proto_id_t pproto,
+ const fib_route_path_t *rpaths)
+{
+ fib_node_index_t *pli, old_pli;
+ bier_disp_entry_t *bde;
+
+ bde = bier_disp_entry_get(bdei);
+ pli = &bde->bde_pl[pproto];
+ old_pli = *pli;
+
+ /*
+ * update the exisitng path-list for this payload protocol
+ */
+ if (FIB_NODE_INDEX_INVALID != *pli)
+ {
+ *pli = fib_path_list_copy_and_path_remove(old_pli,
+ (FIB_PATH_LIST_FLAG_SHARED |
+ FIB_PATH_LIST_FLAG_NO_URPF),
+ rpaths);
+
+ fib_path_list_lock(*pli);
+ fib_path_list_unlock(old_pli);
+
+ bier_disp_entry_restack(bde, pproto);
+ }
+
+ /*
+ * if there are no path-list defined for any payload protocol
+ * then this entry is OK for removal
+ */
+ int remove = 1;
+
+ FOR_EACH_BIER_HDR_PROTO(pproto)
+ {
+ if (FIB_NODE_INDEX_INVALID != bde->bde_pl[pproto])
+ {
+ remove = 0;
+ break;
+ }
+ }
+
+ return (remove);
+}
+
+u8*
+format_bier_disp_entry (u8* s, va_list *args)
+{
+ index_t bdei = va_arg (*args, index_t);
+ u32 indent = va_arg(*args, u32);
+ bier_show_flags_t flags = va_arg(*args, bier_show_flags_t);
+ bier_hdr_proto_id_t pproto;
+ bier_disp_entry_t *bde;
+
+ bde = bier_disp_entry_get(bdei);
+
+ s = format(s, "bier-disp:[%d]", bdei);
+
+ FOR_EACH_BIER_HDR_PROTO(pproto)
+ {
+ if (INDEX_INVALID != bde->bde_pl[pproto])
+ {
+ s = format(s, "\n");
+ s = fib_path_list_format(bde->bde_pl[pproto], s);
+
+ if (flags & BIER_SHOW_DETAIL)
+ {
+ s = format(s, "\n%UForwarding:",
+ format_white_space, indent);
+ s = format(s, "\n%Urpf-id:%d",
+ format_white_space, indent+1,
+ bde->bde_fwd[pproto].bde_rpf_id);
+ s = format(s, "\n%U%U",
+ format_white_space, indent+1,
+ format_dpo_id, &bde->bde_fwd[pproto].bde_dpo, indent+2);
+ }
+ }
+ }
+ return (s);
+}
+
+void
+bier_disp_entry_contribute_forwarding (index_t bdei,
+ dpo_id_t *dpo)
+{
+ dpo_set(dpo, DPO_BIER_DISP_ENTRY, DPO_PROTO_BIER, bdei);
+}
+
+const static char* const bier_disp_entry_bier_nodes[] =
+{
+ "bier-disp-dispatch",
+ NULL,
+};
+
+const static char* const * const bier_disp_entry_nodes[DPO_PROTO_NUM] =
+{
+ [DPO_PROTO_BIER] = bier_disp_entry_bier_nodes,
+};
+
+static void
+bier_disp_entry_dpo_lock (dpo_id_t *dpo)
+{
+ bier_disp_entry_lock(dpo->dpoi_index);
+}
+
+static void
+bier_disp_entry_dpo_unlock (dpo_id_t *dpo)
+{
+ bier_disp_entry_unlock(dpo->dpoi_index);
+}
+
+static void
+bier_disp_entry_dpo_mem_show (void)
+{
+ fib_show_memory_usage("BIER dispositon",
+ pool_elts(bier_disp_entry_pool),
+ pool_len(bier_disp_entry_pool),
+ sizeof(bier_disp_entry_t));
+}
+
+static u8*
+format_bier_disp_entry_dpo (u8* s, va_list *ap)
+{
+ index_t index = va_arg(*ap, index_t);
+ u32 indent = va_arg(*ap, u32);
+
+ s = format(s, "%U", format_bier_disp_entry, index, indent, BIER_SHOW_DETAIL);
+
+ return (s);
+}
+
+const static dpo_vft_t bier_disp_entry_vft = {
+ .dv_lock = bier_disp_entry_dpo_lock,
+ .dv_unlock = bier_disp_entry_dpo_unlock,
+ .dv_format = format_bier_disp_entry_dpo,
+ .dv_mem_show = bier_disp_entry_dpo_mem_show,
+};
+
+clib_error_t *
+bier_disp_entry_db_module_init (vlib_main_t *vm)
+{
+ dpo_register(DPO_BIER_DISP_ENTRY,
+ &bier_disp_entry_vft,
+ bier_disp_entry_nodes);
+
+ return (NULL);
+}
+
+VLIB_INIT_FUNCTION (bier_disp_entry_db_module_init);
+
+static clib_error_t *
+show_bier_disp_entry (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd)
+{
+ index_t bdei;
+
+ bdei = INDEX_INVALID;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
+ if (unformat (input, "%d", &bdei))
+ ;
+ else
+ {
+ break;
+ }
+ }
+
+ if (INDEX_INVALID == bdei)
+ {
+ return (NULL);
+ }
+ else
+ {
+ vlib_cli_output(vm, "%U", format_bier_disp_entry, bdei, 1,
+ BIER_SHOW_DETAIL);
+ }
+ return (NULL);
+}
+
+VLIB_CLI_COMMAND (show_bier_disp_entry_node, static) = {
+ .path = "show bier disp entry",
+ .short_help = "show bier disp entry index",
+ .function = show_bier_disp_entry,
+};
diff --git a/src/vnet/bier/bier_disp_entry.h b/src/vnet/bier/bier_disp_entry.h
new file mode 100644
index 00000000000..34ca5d4a09a
--- /dev/null
+++ b/src/vnet/bier/bier_disp_entry.h
@@ -0,0 +1,81 @@
+/*
+ * 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.
+ */
+/**
+ * bier_dispositon : The BIER dispositon object
+ *
+ * A BIER dispositon object is used to pop the BIER header for for-us
+ * packets and steer the packet down the payload protocol specific graph
+ */
+
+#ifndef __BIER_DISP_ENTRY_H__
+#define __BIER_DISP_ENTRY_H__
+
+#include <vnet/bier/bier_types.h>
+#include <vnet/fib/fib_types.h>
+#include <vnet/dpo/dpo.h>
+
+/**
+ * The BIER dispositon object
+ */
+typedef struct bier_disp_entry_t_ {
+ /**
+ * The DPO contirubted from the per-payload protocol parents
+ * on cachline 1.
+ */
+ struct
+ {
+ dpo_id_t bde_dpo;
+ u32 bde_rpf_id;
+ } bde_fwd[BIER_HDR_N_PROTO];
+
+ /**
+ * number of locks
+ */
+ u32 bde_locks;
+
+ /**
+ * The path-lists used by per-payload protocol parents.
+ * We don't add the disp entry to the graph as a sibling
+ * since there is nothing we can do with the updates to
+ * forwarding.
+ */
+ fib_node_index_t bde_pl[BIER_HDR_N_PROTO];
+} bier_disp_entry_t;
+
+extern index_t bier_disp_entry_add_or_lock(void);
+extern void bier_disp_entry_path_add(index_t bdei,
+ bier_hdr_proto_id_t pproto,
+ const fib_route_path_t *rpaths);
+extern int bier_disp_entry_path_remove(index_t bdei,
+ bier_hdr_proto_id_t pproto,
+ const fib_route_path_t *rpaths);
+
+extern void bier_disp_entry_unlock(index_t bdi);
+extern void bier_disp_entry_lock(index_t bdi);
+
+extern u8* format_bier_disp_entry(u8* s, va_list *ap);
+
+extern void bier_disp_entry_contribute_forwarding(index_t bdi,
+ dpo_id_t *dpo);
+
+extern bier_disp_entry_t *bier_disp_entry_pool;
+
+always_inline bier_disp_entry_t*
+bier_disp_entry_get (index_t bdi)
+{
+ return (pool_elt_at_index(bier_disp_entry_pool, bdi));
+}
+
+#endif
diff --git a/src/vnet/bier/bier_disp_lookup_node.c b/src/vnet/bier/bier_disp_lookup_node.c
new file mode 100644
index 00000000000..15515f467ca
--- /dev/null
+++ b/src/vnet/bier/bier_disp_lookup_node.c
@@ -0,0 +1,147 @@
+/*
+ * 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/bier/bier_disp_table.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+
+/**
+ * @brief A struct to hold tracing information for the MPLS label imposition
+ * node.
+ */
+typedef struct bier_disp_lookup_trace_t_
+{
+ /**
+ * BIER source BP used in the lookup - host order
+ */
+ bier_bp_t bp;
+ /**
+ * BIER disp table
+ */
+ index_t bdti;
+} bier_disp_lookup_trace_t;
+
+/**
+ * Next nodes from BIER disposition lookup
+ */
+typedef enum bier_disp_lookup_next_t_
+{
+ BIER_DISP_LOOKUP_NEXT_DROP,
+ BIER_DISP_LOOKUP_NEXT_DISPATCH,
+} bier_disp_lookup_next_t;
+#define BIER_DISP_LOOKUP_N_NEXT (BIER_DISP_LOOKUP_NEXT_DISPATCH+1)
+
+always_inline uword
+bier_disp_lookup_inline (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * from_frame)
+{
+ u32 n_left_from, next_index, * from, * to_next;
+
+ from = vlib_frame_vector_args (from_frame);
+ n_left_from = from_frame->n_vectors;
+
+ next_index = node->cached_next_index;
+
+ while (n_left_from > 0)
+ {
+ u32 n_left_to_next;
+
+ vlib_get_next_frame(vm, node, next_index, to_next, n_left_to_next);
+
+ while (n_left_from > 0 && n_left_to_next > 0)
+ {
+ const bier_hdr_t *hdr0;
+ vlib_buffer_t * b0;
+ u32 bdei0, bdti0;
+ u32 next0, bi0;
+
+ bi0 = from[0];
+ to_next[0] = bi0;
+ from += 1;
+ to_next += 1;
+ n_left_from -= 1;
+ n_left_to_next -= 1;
+
+ b0 = vlib_get_buffer (vm, bi0);
+
+ bdti0 = vnet_buffer(b0)->ip.adj_index[VLIB_TX];
+ hdr0 = vlib_buffer_get_current(b0);
+
+ /*
+ * lookup - source is in network order.
+ */
+ bdei0 = bier_disp_table_lookup(bdti0, bier_hdr_get_src_id(hdr0));
+
+ if (PREDICT_FALSE(INDEX_INVALID == bdei0))
+ {
+ next0 = BIER_DISP_LOOKUP_NEXT_DROP;
+ }
+ else
+ {
+ next0 = BIER_DISP_LOOKUP_NEXT_DISPATCH;
+ }
+
+ vnet_buffer(b0)->ip.adj_index[VLIB_TX] = bdei0;
+
+ if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
+ {
+ bier_disp_lookup_trace_t *tr =
+ vlib_add_trace (vm, node, b0, sizeof (*tr));
+ tr->bp = clib_net_to_host_u16(bier_hdr_get_src_id(hdr0));
+ tr->bdti = bdti0;
+ }
+
+ vlib_validate_buffer_enqueue_x1(vm, node, next_index, to_next,
+ n_left_to_next, bi0, next0);
+ }
+ vlib_put_next_frame (vm, node, next_index, n_left_to_next);
+ }
+ return from_frame->n_vectors;
+}
+
+static u8 *
+format_bier_disp_lookup_trace (u8 * s, va_list * args)
+{
+ CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
+ CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
+ bier_disp_lookup_trace_t * t;
+
+ t = va_arg (*args, bier_disp_lookup_trace_t *);
+ s = format (s, "tbl:%d src:%d", t->bdti, t->bp);
+
+ return (s);
+}
+
+static uword
+bier_disp_lookup (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * frame)
+{
+ return (bier_disp_lookup_inline(vm, node, frame));
+}
+
+VLIB_REGISTER_NODE (bier_disp_lookup_node) = {
+ .function = bier_disp_lookup,
+ .name = "bier-disp-lookup",
+ .vector_size = sizeof (u32),
+
+ .format_trace = format_bier_disp_lookup_trace,
+ .n_next_nodes = BIER_DISP_LOOKUP_N_NEXT,
+ .next_nodes = {
+ [BIER_DISP_LOOKUP_NEXT_DROP] = "bier-drop",
+ [BIER_DISP_LOOKUP_NEXT_DISPATCH] = "bier-disp-dispatch",
+ }
+};
+VLIB_NODE_FUNCTION_MULTIARCH (bier_disp_lookup_node, bier_disp_lookup)
diff --git a/src/vnet/bier/bier_disp_table.c b/src/vnet/bier/bier_disp_table.c
new file mode 100644
index 00000000000..5caf86d3705
--- /dev/null
+++ b/src/vnet/bier/bier_disp_table.c
@@ -0,0 +1,396 @@
+/*
+ * Copyright (c) 2017 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/bier/bier_disp_table.h>
+#include <vnet/bier/bier_disp_entry.h>
+
+/**
+ * memory pool for disposition tables
+ */
+bier_disp_table_t *bier_disp_table_pool;
+
+/**
+ * Hash table to map client table IDs to VPP index
+ */
+static uword *bier_disp_table_id_to_index;
+
+static index_t
+bier_disp_table_get_index (const bier_disp_table_t *bdt)
+{
+ return (bdt - bier_disp_table_pool);
+}
+
+static void
+bier_disp_table_lock_i (bier_disp_table_t *bdt)
+{
+ bdt->bdt_locks++;
+}
+
+index_t
+bier_disp_table_find(u32 table_id)
+{
+ uword *p;
+
+ p = hash_get(bier_disp_table_id_to_index, table_id);
+
+ if (NULL != p)
+ {
+ return (p[0]);
+ }
+
+ return (INDEX_INVALID);
+}
+
+index_t
+bier_disp_table_add_or_lock (u32 table_id)
+{
+ bier_disp_table_t *bdt;
+ index_t bdti;
+
+ bdti = bier_disp_table_find(table_id);
+
+ if (INDEX_INVALID == bdti)
+ {
+ pool_get_aligned(bier_disp_table_pool, bdt,
+ CLIB_CACHE_LINE_BYTES);
+
+ bdt->bdt_table_id = table_id;
+ bdt->bdt_locks = 0;
+
+ hash_set(bier_disp_table_id_to_index, table_id,
+ bier_disp_table_get_index(bdt));
+
+ /**
+ * Set the result for each entry in the DB to be invalid
+ */
+ memset(bdt->bdt_db, 0xff, sizeof(bdt->bdt_db));
+ }
+ else
+ {
+ bdt = pool_elt_at_index(bier_disp_table_pool, bdti);
+ }
+
+ bier_disp_table_lock_i(bdt);
+
+ return (bier_disp_table_get_index(bdt));
+}
+
+void
+bier_disp_table_unlock_w_table_id (u32 table_id)
+{
+ index_t bdti;
+
+ bdti = bier_disp_table_find(table_id);
+
+ if (INDEX_INVALID != bdti)
+ {
+ bier_disp_table_unlock(bdti);
+ }
+}
+
+void
+bier_disp_table_unlock (index_t bdti)
+{
+ bier_disp_table_t *bdt;
+
+ bdt = bier_disp_table_get(bdti);
+
+ bdt->bdt_locks--;
+
+ if (0 == bdt->bdt_locks)
+ {
+ u32 ii;
+
+ for (ii = 0; ii < BIER_BP_MAX; ii++)
+ {
+ bier_disp_entry_unlock(bdt->bdt_db[ii]);
+ }
+ hash_unset(bier_disp_table_id_to_index, bdt->bdt_table_id);
+ pool_put(bier_disp_table_pool, bdt);
+ }
+}
+
+void
+bier_disp_table_lock (index_t bdti)
+{
+ bier_disp_table_lock_i(bier_disp_table_get(bdti));
+}
+
+void
+bier_disp_table_contribute_forwarding (index_t bdti,
+ dpo_id_t *dpo)
+{
+ dpo_set(dpo,
+ DPO_BIER_DISP_TABLE,
+ DPO_PROTO_BIER,
+ bdti);
+}
+
+
+u8*
+format_bier_disp_table (u8* s, va_list *ap)
+{
+ index_t bdti = va_arg(*ap, index_t);
+ u32 indent = va_arg(*ap, u32);
+ bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
+ bier_disp_table_t *bdt;
+
+ bdt = bier_disp_table_get(bdti);
+
+ s = format(s, "bier-disp-table:[%d]; table-id:%d locks:%d",
+ bdti, bdt->bdt_table_id, bdt->bdt_locks);
+
+ if (flags & BIER_SHOW_DETAIL)
+ {
+ u32 ii;
+
+ for (ii = 0; ii < BIER_BP_MAX; ii++)
+ {
+ if (INDEX_INVALID != bdt->bdt_db[ii])
+ {
+ u16 src = ii;
+ s = format(s, "\n%Usrc:%d", format_white_space, indent,
+ clib_host_to_net_u16(src));
+ s = format(s, "\n%U%U", format_white_space, indent+2,
+ format_bier_disp_entry, bdt->bdt_db[ii],
+ indent+4, BIER_SHOW_BRIEF);
+ }
+ }
+ }
+ return (s);
+}
+
+static u8*
+format_bier_disp_table_dpo (u8* s, va_list *ap)
+{
+ index_t bdti = va_arg(*ap, index_t);
+ u32 indent = va_arg(*ap, u32);
+
+ return (format(s, "%U",
+ format_bier_disp_table, bdti, indent,
+ BIER_SHOW_BRIEF));
+}
+
+static void
+bier_disp_table_entry_insert (index_t bdti,
+ bier_bp_t src,
+ index_t bdei)
+{
+ bier_disp_table_t *bdt;
+
+ bdt = bier_disp_table_get(bdti);
+ bdt->bdt_db[clib_host_to_net_u16(src)] = bdei;
+}
+
+static void
+bier_disp_table_entry_remove (index_t bdti,
+ bier_bp_t src)
+{
+ bier_disp_table_t *bdt;
+
+ bdt = bier_disp_table_get(bdti);
+ bdt->bdt_db[clib_host_to_net_u16(src)] = INDEX_INVALID;
+}
+
+static index_t
+bier_disp_table_lookup_hton(index_t bdti,
+ bier_bp_t src)
+{
+ return (bier_disp_table_lookup(bdti, clib_host_to_net_u16(src)));
+}
+
+void
+bier_disp_table_entry_path_add (u32 table_id,
+ bier_bp_t src,
+ bier_hdr_proto_id_t payload_proto,
+ const fib_route_path_t *rpaths)
+{
+ index_t bdti, bdei;
+
+ bdti = bier_disp_table_find(table_id);
+
+ if (INDEX_INVALID == bdti)
+ {
+ return;
+ }
+
+ bdei = bier_disp_table_lookup_hton(bdti, src);
+
+ if (INDEX_INVALID == bdei)
+ {
+ bdei = bier_disp_entry_add_or_lock();
+ bier_disp_table_entry_insert(bdti, src, bdei);
+ }
+
+ bier_disp_entry_path_add(bdei, payload_proto, rpaths);
+}
+
+void
+bier_disp_table_entry_path_remove (u32 table_id,
+ bier_bp_t src,
+ bier_hdr_proto_id_t payload_proto,
+ const fib_route_path_t *rpath)
+{
+ index_t bdti, bdei;
+
+ bdti = bier_disp_table_find(table_id);
+
+ if (INDEX_INVALID == bdti)
+ {
+ return;
+ }
+
+ bdei = bier_disp_table_lookup_hton(bdti, src);
+
+ if (INDEX_INVALID != bdei)
+ {
+ int remove;
+
+ remove = bier_disp_entry_path_remove(bdei, payload_proto, rpath);
+
+ if (remove)
+ {
+ bier_disp_table_entry_remove(bdti, src);
+ bier_disp_entry_unlock(bdei);
+ }
+ }
+}
+
+void
+bier_disp_table_walk (u32 table_id,
+ bier_disp_table_walk_fn_t fn,
+ void *ctx)
+{
+ const bier_disp_table_t *bdt;
+ const bier_disp_entry_t *bde;
+ index_t bdti;
+ u32 ii;
+
+ bdti = bier_disp_table_find(table_id);
+
+ if (INDEX_INVALID != bdti)
+ {
+ bdt = bier_disp_table_get(bdti);
+
+ for (ii = 0; ii < BIER_BP_MAX; ii++)
+ {
+ if (INDEX_INVALID != bdt->bdt_db[ii])
+ {
+ u16 src = ii;
+
+ bde = bier_disp_entry_get(bdt->bdt_db[ii]);
+
+ fn(bdt, bde, clib_host_to_net_u16(src), ctx);
+ }
+ }
+ }
+}
+
+static void
+bier_disp_table_dpo_lock (dpo_id_t *dpo)
+{
+ bier_disp_table_lock(dpo->dpoi_index);
+}
+
+static void
+bier_disp_table_dpo_unlock (dpo_id_t *dpo)
+{
+ bier_disp_table_unlock(dpo->dpoi_index);
+}
+
+static void
+bier_disp_table_dpo_mem_show (void)
+{
+ fib_show_memory_usage("BIER disposition table",
+ pool_elts(bier_disp_table_pool),
+ pool_len(bier_disp_table_pool),
+ sizeof(bier_disp_table_t));
+}
+
+const static dpo_vft_t bier_disp_table_dpo_vft = {
+ .dv_lock = bier_disp_table_dpo_lock,
+ .dv_unlock = bier_disp_table_dpo_unlock,
+ .dv_mem_show = bier_disp_table_dpo_mem_show,
+ .dv_format = format_bier_disp_table_dpo,
+};
+
+const static char *const bier_disp_table_bier_nodes[] =
+{
+ "bier-disp-lookup"
+};
+
+const static char * const * const bier_disp_table_nodes[DPO_PROTO_NUM] =
+{
+ [DPO_PROTO_BIER] = bier_disp_table_bier_nodes,
+};
+
+clib_error_t *
+bier_disp_table_module_init (vlib_main_t *vm)
+{
+ dpo_register(DPO_BIER_DISP_TABLE,
+ &bier_disp_table_dpo_vft,
+ bier_disp_table_nodes);
+
+ bier_disp_table_id_to_index = hash_create(0, sizeof(index_t));
+
+ return (NULL);
+}
+
+VLIB_INIT_FUNCTION (bier_disp_table_module_init);
+
+static clib_error_t *
+show_bier_disp_table (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd)
+{
+ bier_disp_table_t *bdt;
+ index_t bdti;
+
+ bdti = INDEX_INVALID;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
+ if (unformat (input, "%d", &bdti))
+ ;
+ else if (unformat (input, "%d", &bdti))
+ ;
+ else
+ {
+ break;
+ }
+ }
+
+ if (INDEX_INVALID == bdti)
+ {
+ pool_foreach(bdt, bier_disp_table_pool,
+ ({
+ vlib_cli_output(vm, "%U", format_bier_disp_table,
+ bier_disp_table_get_index(bdt),
+ 1,
+ BIER_SHOW_BRIEF);
+ }));
+ }
+ else
+ {
+ vlib_cli_output(vm, "%U", format_bier_disp_table, bdti, 1,
+ BIER_SHOW_DETAIL);
+ }
+ return (NULL);
+}
+
+VLIB_CLI_COMMAND (show_bier_disp_table_node, static) = {
+ .path = "show bier disp table",
+ .short_help = "show bier disp table [index]",
+ .function = show_bier_disp_table,
+};
diff --git a/src/vnet/bier/bier_disp_table.h b/src/vnet/bier/bier_disp_table.h
new file mode 100644
index 00000000000..18726c8ee6a
--- /dev/null
+++ b/src/vnet/bier/bier_disp_table.h
@@ -0,0 +1,110 @@
+/*
+ * 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.
+ */
+
+#ifndef __BIER_DISP_TABLE_H__
+#define __BIER_DISP_TABLE_H__
+
+#include <vnet/ip/ip.h>
+#include <vnet/adj/adj.h>
+#include <vnet/dpo/replicate_dpo.h>
+
+#include <vnet/bier/bier_types.h>
+#include <vnet/bier/bier_disp_entry.h>
+
+/**
+ * @brief
+ * A protocol Independent IP multicast FIB table
+ */
+typedef struct bier_disp_table_t_
+{
+ /**
+ * number of locks on the table
+ */
+ u16 bdt_locks;
+
+ /**
+ * Table ID (hash key) for this FIB.
+ */
+ u32 bdt_table_id;
+
+ /**
+ * The lookup DB based on sender BP. Value is the index of the
+ * BIER disp object.
+ */
+ index_t bdt_db[BIER_BP_MAX];
+} bier_disp_table_t;
+
+/**
+ * @brief
+ * Format the description/name of the table
+ */
+extern u8* format_bier_disp_table(u8* s, va_list *ap);
+
+extern void bier_disp_table_entry_path_add(u32 table_id,
+ bier_bp_t src,
+ bier_hdr_proto_id_t payload_proto,
+ const fib_route_path_t *rpath);
+
+extern void bier_disp_table_entry_path_remove(u32 table_id,
+ bier_bp_t src,
+ bier_hdr_proto_id_t payload_proto,
+ const fib_route_path_t *paths);
+
+extern index_t bier_disp_table_find(u32 table_id);
+
+
+extern index_t bier_disp_table_add_or_lock(u32 table_id);
+extern void bier_disp_table_unlock_w_table_id(u32 table_id);
+
+extern void bier_disp_table_unlock(index_t bdti);
+extern void bier_disp_table_lock(index_t bdti);
+extern void bier_disp_table_contribute_forwarding(index_t bdti,
+ dpo_id_t *dpo);
+
+/**
+ * Types and functions to walk all the entries in one BIER Table
+ */
+typedef void (*bier_disp_table_walk_fn_t)(const bier_disp_table_t *bdt,
+ const bier_disp_entry_t *bde,
+ u16 bp,
+ void *ctx);
+extern void bier_disp_table_walk(u32 table_id,
+ bier_disp_table_walk_fn_t fn,
+ void *ctx);
+
+/**
+ * @brief
+ * Get a pointer to a FIB table
+ */
+extern bier_disp_table_t *bier_disp_table_pool;
+
+static inline bier_disp_table_t *
+bier_disp_table_get (index_t bdti)
+{
+ return (pool_elt_at_index(bier_disp_table_pool, bdti));
+}
+
+static inline index_t
+bier_disp_table_lookup (index_t bdti,
+ bier_bp_t src)
+{
+ bier_disp_table_t *bdt;
+
+ bdt = bier_disp_table_get(bdti);
+
+ return (bdt->bdt_db[src]);
+}
+
+#endif
diff --git a/src/vnet/bier/bier_drop.c b/src/vnet/bier/bier_drop.c
new file mode 100644
index 00000000000..eb873acf7ba
--- /dev/null
+++ b/src/vnet/bier/bier_drop.c
@@ -0,0 +1,101 @@
+/*
+ * 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/buffer.h>
+#include <vlib/vlib.h>
+#include <vnet/dpo/dpo.h>
+
+#include <vnet/bier/bier_hdr_inlines.h>
+
+typedef struct bier_drop_trace_t_
+{
+ index_t dpi;
+} bier_drop_trace_t;
+
+static void
+bier_drop_trace (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * frame)
+{
+ u32 *from, n_left;
+
+ n_left = frame->n_vectors;
+ from = vlib_frame_vector_args (frame);
+ while (n_left >= 1)
+ {
+ u32 bi0;
+ vlib_buffer_t *b0;
+ bier_drop_trace_t *t0;
+
+ bi0 = from[0];
+
+ b0 = vlib_get_buffer (vm, bi0);
+
+ if (b0->flags & VLIB_BUFFER_IS_TRACED)
+ {
+ t0 = vlib_add_trace (vm, node, b0, sizeof(*t0));
+
+ t0->dpi = vnet_buffer (b0)->ip.adj_index[VLIB_TX];
+ }
+ from += 1;
+ n_left -= 1;
+ }
+}
+
+static uword
+bier_drop (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * frame)
+{
+ u32 *buffers = vlib_frame_vector_args (frame);
+ uword n_packets = frame->n_vectors;
+
+ vlib_error_drop_buffers (vm, node, buffers,
+ /* stride */ 1,
+ n_packets,
+ /* next */ 0,
+ 0, // bier_input_node.index,
+ 0);
+
+ if (node->flags & VLIB_NODE_FLAG_TRACE)
+ bier_drop_trace (vm, node, frame);
+
+ return n_packets;
+}
+
+static u8 *
+format_bier_drop_trace (u8 * s, va_list * args)
+{
+ CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
+ CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
+ bier_drop_trace_t *t = va_arg (*args, bier_drop_trace_t *);
+
+ s = format (s, "dpo-idx %d", t->dpi);
+
+ return s;
+}
+
+/* *INDENT-OFF* */
+VLIB_REGISTER_NODE (bier_drop_node, static) =
+{
+ .function = bier_drop,.
+ name = "bier-drop",
+ .vector_size = sizeof (u32),
+ .format_trace = format_bier_drop_trace,
+ .n_next_nodes = 1,
+ .next_nodes = {
+ [0] = "error-drop",
+ },
+};
diff --git a/src/vnet/bier/bier_entry.c b/src/vnet/bier/bier_entry.c
new file mode 100644
index 00000000000..88be8125f51
--- /dev/null
+++ b/src/vnet/bier/bier_entry.c
@@ -0,0 +1,388 @@
+/*
+ * 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/bier/bier_entry.h>
+#include <vnet/bier/bier_update.h>
+
+#include <vnet/fib/fib_path_list.h>
+
+#include <vnet/bier/bier_fmask_db.h>
+#include <vnet/bier/bier_fmask.h>
+#include <vnet/bier/bier_table.h>
+
+bier_entry_t *bier_entry_pool;
+
+static index_t
+bier_entry_get_index (const bier_entry_t *be)
+{
+ return (be - bier_entry_pool);
+}
+
+static fib_path_list_walk_rc_t
+bier_entry_link_walk (fib_node_index_t pl_index,
+ fib_node_index_t path_index,
+ void *arg)
+{
+ bier_entry_t *be = arg;
+ index_t bfmi;
+
+ bfmi = fib_path_get_resolving_index(path_index);
+ bier_fmask_link(bfmi, be->be_bp);
+
+ return (FIB_PATH_LIST_WALK_CONTINUE);
+}
+
+static fib_path_list_walk_rc_t
+bier_entry_unlink_walk (fib_node_index_t pl_index,
+ fib_node_index_t path_index,
+ void *arg)
+{
+ bier_entry_t *be = arg;
+ index_t bfmi;
+
+ bfmi = fib_path_get_resolving_index(path_index);
+ bier_fmask_unlink(bfmi, be->be_bp);
+
+ return (FIB_PATH_LIST_WALK_CONTINUE);
+}
+
+index_t
+bier_entry_create (index_t bti,
+ bier_bp_t bp)
+{
+ bier_entry_t *be;
+
+ pool_get(bier_entry_pool, be);
+
+ be->be_bp = bp;
+ be->be_bti = bti;
+ be->be_path_list = FIB_NODE_INDEX_INVALID;
+
+ return (bier_entry_get_index(be));
+}
+
+void
+bier_entry_delete (index_t bei)
+{
+ bier_entry_t *be;
+
+ be = bier_entry_get(bei);
+
+ /*
+ * if we still ahve a path-list, unlink from it
+ */
+ if (FIB_NODE_INDEX_INVALID != be->be_path_list)
+ {
+ fib_path_list_walk(be->be_path_list,
+ bier_entry_unlink_walk,
+ be);
+ fib_path_list_child_remove(be->be_path_list,
+ be->be_sibling_index);
+ }
+
+ pool_put(bier_entry_pool, be);
+}
+
+static void
+bier_entry_table_ecmp_walk_add_fmask (index_t btei,
+ void *arg)
+{
+ bier_entry_t *be = arg;;
+
+ /*
+ * choose a fmask from the entry's resolved set to add
+ * to ECMP table's lookup table
+ */
+ if (FIB_NODE_INDEX_INVALID != be->be_path_list)
+ {
+ const bier_table_id_t *btid;
+ dpo_id_t dpo = DPO_INVALID;
+ const dpo_id_t *choice;
+ load_balance_t *lb;
+
+ btid = bier_table_get_id(btei);
+
+ fib_path_list_contribute_forwarding(be->be_path_list,
+ FIB_FORW_CHAIN_TYPE_BIER,
+ &dpo);
+
+ /*
+ * select the appropriate bucket from the LB
+ */
+ ASSERT(dpo.dpoi_type == DPO_LOAD_BALANCE);
+
+ lb = load_balance_get(dpo.dpoi_index);
+
+ choice = load_balance_get_bucket_i(lb,
+ btid->bti_ecmp &
+ (lb->lb_n_buckets_minus_1));
+
+ if (choice->dpoi_type == DPO_BIER_FMASK)
+ {
+ bier_table_ecmp_set_fmask(btei, be->be_bp,
+ choice->dpoi_index);
+ }
+ else
+ {
+ /*
+ * any other type results in a drop, which we represent
+ * with an empty bucket
+ */
+ bier_table_ecmp_set_fmask(btei, be->be_bp,
+ INDEX_INVALID);
+ }
+
+ dpo_reset(&dpo);
+ }
+ else
+ {
+ /*
+ * no fmasks left. insert a drop
+ */
+ bier_table_ecmp_set_fmask(btei, be->be_bp, INDEX_INVALID);
+ }
+}
+
+void
+bier_entry_path_add (index_t bei,
+ const fib_route_path_t *rpaths)
+{
+ fib_node_index_t old_pl_index;
+ bier_entry_t *be;
+
+ be = bier_entry_get(bei);
+ old_pl_index = be->be_path_list;
+
+ /*
+ * lock the path-list so it does not go away before we unlink
+ * from its resolved fmasks
+ */
+ fib_path_list_lock(old_pl_index);
+
+ if (FIB_NODE_INDEX_INVALID == be->be_path_list)
+ {
+ old_pl_index = FIB_NODE_INDEX_INVALID;
+ be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
+ FIB_PATH_LIST_FLAG_NO_URPF),
+ rpaths);
+ be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
+ FIB_NODE_TYPE_BIER_ENTRY,
+ bier_entry_get_index(be));
+ }
+ else
+ {
+
+ old_pl_index = be->be_path_list;
+
+ be->be_path_list =
+ fib_path_list_copy_and_path_add(old_pl_index,
+ (FIB_PATH_LIST_FLAG_SHARED |
+ FIB_PATH_LIST_FLAG_NO_URPF),
+ rpaths);
+
+ fib_path_list_child_remove(old_pl_index,
+ be->be_sibling_index);
+ be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
+ FIB_NODE_TYPE_BIER_ENTRY,
+ bier_entry_get_index(be));
+ }
+ /*
+ * link the entry's bit-position to each fmask in the new path-list
+ * then unlink from the old.
+ */
+ fib_path_list_walk(be->be_path_list,
+ bier_entry_link_walk,
+ be);
+ if (FIB_NODE_INDEX_INVALID != old_pl_index)
+ {
+ fib_path_list_walk(old_pl_index,
+ bier_entry_unlink_walk,
+ be);
+ }
+
+ /*
+ * update the ECNP tables with the new choice
+ */
+ bier_table_ecmp_walk(be->be_bti,
+ bier_entry_table_ecmp_walk_add_fmask,
+ be);
+
+ /*
+ * symmetric unlock. The old path-list may not exist hereinafter
+ */
+ fib_path_list_unlock(old_pl_index);
+}
+
+int
+bier_entry_path_remove (index_t bei,
+ const fib_route_path_t *rpaths)
+{
+ fib_node_index_t old_pl_index;
+ bier_entry_t *be;
+
+ be = bier_entry_get(bei);
+ old_pl_index = be->be_path_list;
+
+ fib_path_list_lock(old_pl_index);
+
+ ASSERT (FIB_NODE_INDEX_INVALID != be->be_path_list);
+
+ be->be_path_list =
+ fib_path_list_copy_and_path_remove(old_pl_index,
+ (FIB_PATH_LIST_FLAG_SHARED |
+ FIB_PATH_LIST_FLAG_NO_URPF),
+ rpaths);
+
+ if (be->be_path_list != old_pl_index)
+ {
+ /*
+ * a path was removed
+ */
+ fib_path_list_child_remove(old_pl_index,
+ be->be_sibling_index);
+
+ if (FIB_NODE_INDEX_INVALID != be->be_path_list)
+ {
+ /*
+ * link the entry's bit-position to each fmask in the new path-list
+ * then unlink from the old.
+ */
+ fib_path_list_walk(be->be_path_list,
+ bier_entry_link_walk,
+ be);
+ be->be_sibling_index =
+ fib_path_list_child_add(be->be_path_list,
+ FIB_NODE_TYPE_BIER_ENTRY,
+ bier_entry_get_index(be));
+ }
+
+ fib_path_list_walk(old_pl_index,
+ bier_entry_unlink_walk,
+ be);
+ }
+ fib_path_list_unlock(old_pl_index);
+
+
+ /*
+ * update the ECNP tables with the new choice
+ */
+ bier_table_ecmp_walk(be->be_bti,
+ bier_entry_table_ecmp_walk_add_fmask,
+ be);
+
+ return (fib_path_list_get_n_paths(be->be_path_list));
+}
+
+void
+bier_entry_contribute_forwarding(index_t bei,
+ dpo_id_t *dpo)
+{
+ bier_entry_t *be = bier_entry_get(bei);
+
+ fib_path_list_contribute_forwarding(be->be_path_list,
+ FIB_FORW_CHAIN_TYPE_BIER,
+ dpo);
+}
+
+u8*
+format_bier_entry (u8* s, va_list *ap)
+{
+ index_t bei = va_arg(*ap, index_t);
+ bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
+
+ bier_entry_t *be = bier_entry_get(bei);
+
+ s = format(s, " bp:%d\n", be->be_bp);
+ s = fib_path_list_format(be->be_path_list, s);
+
+ if (flags & BIER_SHOW_DETAIL)
+ {
+ dpo_id_t dpo = DPO_INVALID;
+
+ bier_entry_contribute_forwarding(bei, &dpo);
+
+ s = format(s, " forwarding:\n");
+ s = format(s, " %U",
+ format_dpo_id, &dpo, 2);
+ s = format(s, "\n");
+ }
+
+ return (s);
+}
+
+static fib_node_t *
+bier_entry_get_node (fib_node_index_t index)
+{
+ bier_entry_t *be = bier_entry_get(index);
+ return (&(be->be_node));
+}
+
+static bier_entry_t*
+bier_entry_get_from_node (fib_node_t *node)
+{
+ return ((bier_entry_t*)(((char*)node) -
+ STRUCT_OFFSET_OF(bier_entry_t,
+ be_node)));
+}
+
+static void
+bier_entry_last_lock_gone (fib_node_t *node)
+{
+ /*
+ * the lifetime of the entry is managed by the table.
+ */
+ ASSERT(0);
+}
+
+/*
+ * A back walk has reached this BIER entry
+ */
+static fib_node_back_walk_rc_t
+bier_entry_back_walk_notify (fib_node_t *node,
+ fib_node_back_walk_ctx_t *ctx)
+{
+ /*
+ * re-populate the ECMP tables with new choices
+ */
+ bier_entry_t *be = bier_entry_get_from_node(node);
+
+ bier_table_ecmp_walk(be->be_bti,
+ bier_entry_table_ecmp_walk_add_fmask,
+ be);
+
+ /*
+ * no need to propagate further up the graph.
+ */
+ return (FIB_NODE_BACK_WALK_CONTINUE);
+}
+
+/*
+ * The BIER fmask's graph node virtual function table
+ */
+static const fib_node_vft_t bier_entry_vft = {
+ .fnv_get = bier_entry_get_node,
+ .fnv_last_lock = bier_entry_last_lock_gone,
+ .fnv_back_walk = bier_entry_back_walk_notify,
+};
+
+clib_error_t *
+bier_entry_module_init (vlib_main_t * vm)
+{
+ fib_node_register_type (FIB_NODE_TYPE_BIER_ENTRY, &bier_entry_vft);
+
+ return (NULL);
+}
+
+VLIB_INIT_FUNCTION (bier_entry_module_init);
diff --git a/src/vnet/bier/bier_entry.h b/src/vnet/bier/bier_entry.h
new file mode 100644
index 00000000000..e514c64bb24
--- /dev/null
+++ b/src/vnet/bier/bier_entry.h
@@ -0,0 +1,94 @@
+/*
+ * 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.
+ */
+/**
+ * bier_entry : The BIER entry
+ *
+ * The interface to the BIER entry is through a bier_entry_t* rather
+ * than an index. This is becuase the BIER table allocates the entries
+ * in a contiguous array once and only once when the table is created.
+ * this is done for forwarding performance. The entry is thus not subject
+ * to realloc, and does not need to be malloc'd when a route to that
+ * bit-position is first learned.
+ *
+ */
+
+#ifndef __BIER_ENTRY_H__
+#define __BIER_ENTRY_H__
+
+#include <vlib/vlib.h>
+#include <vnet/fib/fib_node.h>
+#include <vnet/bier/bier_types.h>
+
+/**
+ * Forward declarations
+ */
+struct bier_route_update_t_;
+struct bier_fmask_db_t_;
+
+/**
+ * The BIER entry
+ *
+ * the BIER entry is the representation of a BIER forwarding egress router (BFER)
+ * (or the egress PE) that is assigned a bit position.
+ */
+typedef struct bier_entry_t_ {
+ /**
+ * linkage into the FIB graph
+ */
+ fib_node_t be_node;
+
+ /**
+ * The index of the BIER table in which this entry resides
+ */
+ index_t be_bti;
+
+ /**
+ * the bit position this entry represents.
+ * this is the key table insertion
+ */
+ bier_bp_t be_bp;
+
+ /**
+ * the FIB path-list this entry resolves through.
+ * the path-list is itself resoved on the entry's fmasks
+ */
+ fib_node_index_t be_path_list;
+ /**
+ * sibling index on the path list
+ */
+ fib_node_index_t be_sibling_index;
+} bier_entry_t;
+
+extern index_t bier_entry_create(index_t bti,
+ bier_bp_t bp);
+extern void bier_entry_delete(index_t bei);
+
+extern void bier_entry_path_add(index_t bei,
+ const fib_route_path_t *brp);
+
+extern int bier_entry_path_remove(index_t bei,
+ const fib_route_path_t *brp);
+
+extern u8* format_bier_entry(u8* s, va_list *ap);
+
+extern void bier_entry_contribute_forwarding(index_t bei,
+ dpo_id_t *dpo);
+
+extern bier_entry_t *bier_entry_pool;
+always_inline bier_entry_t* bier_entry_get(index_t bei)
+{
+ return (&bier_entry_pool[bei]);
+}
+#endif
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,
+};
diff --git a/src/vnet/bier/bier_fmask.h b/src/vnet/bier/bier_fmask.h
new file mode 100644
index 00000000000..d5ff4590ffe
--- /dev/null
+++ b/src/vnet/bier/bier_fmask.h
@@ -0,0 +1,198 @@
+/*
+ * 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.
+ */
+/**
+ * @brief bier_fmask : The BIER fmask
+ *
+ * The BIER fmask contains the bitString that is applied to packets that
+ * egress towards the next-hop. As such the fmask is part of the rewrite
+ * (adj) for that next-hop. It it thus an extension of the next-hop and in
+ * no way associated with the bit-position(s) that are reachable through it.
+ * Fmasks are thus shared by bit-positions that egress throught the same
+ * nh (BFR-NBR).
+ * Deag fmasks are also shread in the event that a router has local
+ * bit-positions. This is necessary to prevent the router recieving two copies
+ * of each packet. Consequently it also means that they share the same
+ * disposition data for the global data.
+ */
+
+#ifndef __BIER_FMASK_H__
+#define __BIER_FMASK_H__
+
+#include <vlib/vlib.h>
+
+#include <vnet/fib/fib_node.h>
+#include <vnet/mpls/packet.h>
+#include <vnet/dpo/dpo.h>
+
+#include <vnet/bier/bier_types.h>
+#include <vnet/bier/bier_fmask_db.h>
+
+/**
+ * A struct that represents the reference counting of the bits
+ */
+typedef struct bier_fmask_bits_t_ {
+ /**
+ * each bit in the mask needs to be reference counted
+ * and set/cleared on the 0->1 and 1->0 transitions.
+ */
+ bier_bit_string_t bfmb_input_reset_string;
+ u32 *bfmb_refs;
+
+ /**
+ * The total number of references to bits set on this mask
+ * in effect a count of the number of children.
+ */
+ uint32_t bfmb_count;
+} bier_fmask_bits_t;
+
+/**
+ * Flags on fmask
+ */
+typedef enum bier_fmask_attributes_t_
+{
+ BIER_FMASK_ATTR_FIRST,
+ BIER_FMASK_ATTR_FORWARDING = BIER_FMASK_ATTR_FIRST,
+ BIER_FMASK_ATTR_DISP,
+ BIER_FMASK_ATTR_LAST = BIER_FMASK_ATTR_DISP,
+} bier_fmask_attributes_t;
+
+#define BIER_FMASK_ATTR_NAMES { \
+ [BIER_FMASK_ATTR_FORWARDING] = "forwarding", \
+ [BIER_FMASK_ATTR_DISP] = "disposition", \
+}
+
+#define FOR_EACH_BIER_FMASK_ATTR(_item) \
+ for (_item = BIER_FMASK_ATTR_FIRST; \
+ _item <= BIER_FMASK_ATTR_LAST; \
+ _item++)
+
+typedef enum bier_fmask_flags_t_
+{
+ BIER_FMASK_FLAG_FORWARDING = (1 << BIER_FMASK_ATTR_FORWARDING),
+ BIER_FMASK_FLAG_DISP = (1 << BIER_FMASK_ATTR_DISP),
+} bier_fmask_flags_t;
+
+/**
+ * An outgoing BIER mask. aka forwarding bit mask (in the RFCs)
+ *
+ * This mask's function is two-fold
+ * 1 - it is logical-AND with the input packet header to produce the
+ * output packet header
+ * 2 - it is logical NAND with the input packet header to modify the bit-mask
+ * for the next lookup
+ */
+typedef struct bier_fmask_t_ {
+ /**
+ * The BIER fmask is a child of a FIB entry in the FIB graph.
+ */
+ fib_node_t bfm_node;
+
+ /**
+ * operational/state flags on the fmask
+ */
+ bier_fmask_flags_t bfm_flags;
+
+ /**
+ * The bits, and their ref counts, that are set on this mask
+ * This mask changes as BIER entries link to and from this fmask
+ */
+ bier_fmask_bits_t bfm_bits;
+
+ struct
+ {
+ /**
+ * The key to this fmask - used for store/lookup in the DB
+ */
+ bier_fmask_id_t bfm_id;
+
+ /**
+ * The BIER Table this Fmask is used in
+ */
+ index_t bfm_fib_index;
+ };
+
+ union
+ {
+ /**
+ * For forwarding via a next-hop
+ */
+ struct
+ {
+ /**
+ * The parent fib entry
+ */
+ fib_node_index_t bfm_fei;
+ /**
+ * The MPLS label to paint on the header during forwarding
+ */
+ mpls_label_t bfm_label;
+ };
+
+ /**
+ * For disposition
+ */
+ struct
+ {
+ /**
+ * The parent disposition table object
+ */
+ index_t bfm_disp;
+ };
+ };
+
+ /**
+ * the index of this fmask in the parent's child list.
+ */
+ u32 bfm_sibling;
+
+ /**
+ * The index into the adj table for the adj that
+ * this fmask resolves via
+ */
+ dpo_id_t bfm_dpo;
+} bier_fmask_t;
+
+extern void bier_fmask_link(index_t bfmi, bier_bp_t bp);
+extern void bier_fmask_unlink(index_t bfmi, bier_bp_t bp);
+extern void bier_fmask_unlock(index_t bfmi);
+extern void bier_fmask_lock(index_t bfmi);
+
+extern index_t bier_fmask_create_and_lock(const bier_fmask_id_t *fmid,
+ index_t bti,
+ const fib_route_path_t *rpath);
+
+extern u8* format_bier_fmask(u8 *s, va_list *ap);
+
+extern void bier_fmask_contribute_forwarding(index_t bfmi,
+ dpo_id_t *dpo);
+
+extern u32 bier_fmask_child_add (fib_node_index_t fib_entry_index,
+ fib_node_type_t child_type,
+ fib_node_index_t child_index);
+extern void bier_fmask_child_remove (fib_node_index_t fib_entry_index,
+ u32 sibling_index);
+
+/*
+ * provided for fast data-path access
+ */
+bier_fmask_t *bier_fmask_pool;
+
+static inline bier_fmask_t *
+bier_fmask_get (u32 index)
+{
+ return (pool_elt_at_index(bier_fmask_pool, index));
+}
+
+#endif
diff --git a/src/vnet/bier/bier_fmask_db.c b/src/vnet/bier/bier_fmask_db.c
new file mode 100644
index 00000000000..37cbb365897
--- /dev/null
+++ b/src/vnet/bier/bier_fmask_db.c
@@ -0,0 +1,161 @@
+/*
+ * 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/bier/bier_fmask_db.h>
+#include <vnet/bier/bier_fmask.h>
+
+/**
+ * Global Table of fmask objects
+ * The key into this table includes the table's key and the fmask's key,
+ * so there could be a DB per-table. But it is more efficient
+ * at forwarding time to extract the fmask from a single global table
+ * which is hot in dcache.
+ *
+ * The table's key is part of this DB key, since the fmasks therein build up
+ * their forwarding mask based on the routes that resolve through
+ * it, so cross polination would be bad.
+ */
+typedef struct bier_fmask_db_t_ {
+ /**
+ * hash table for underlying storage
+ */
+ mhash_t bfdb_hash;
+
+ /**
+ * Pool for memory
+ */
+ struct bier_fmask_t_ *bfdb_pool;
+} bier_fmask_db_t;
+
+/**
+ * The key used in the fmask DB to compare fmask objects.
+ * There is one global DB, so we need to use the table's ID and the fmasks ID
+ */
+typedef struct bier_fmask_db_key_t_ {
+ bier_fmask_id_t bfmdbk_fm_id;
+ index_t bfmdbk_tbl_id;
+} bier_fmask_db_key_t;
+// TODO packed?
+
+/**
+ * Single fmask DB
+ */
+static bier_fmask_db_t bier_fmask_db;
+
+
+u32
+bier_fmask_get_index (const bier_fmask_t *bfm)
+{
+ return (bfm - bier_fmask_db.bfdb_pool);
+}
+
+u32
+bier_fmask_db_find_or_create_and_lock (index_t bti,
+ const bier_fmask_id_t *fmid,
+ const fib_route_path_t *rpath)
+{
+ bier_fmask_db_key_t key;
+ u32 index;
+ uword *p;
+
+ /*
+ * there be padding in that thar key, and it's
+ * used as a memcmp in the mhash.
+ */
+ memset(&key, 0, sizeof(key));
+ key.bfmdbk_tbl_id = bti;
+ key.bfmdbk_fm_id = *fmid;
+
+ index = INDEX_INVALID;
+ p = mhash_get (&bier_fmask_db.bfdb_hash, &key);
+
+ if (NULL == p)
+ {
+ /*
+ * adding a new fmask object
+ */
+ index = bier_fmask_create_and_lock(fmid, bti, rpath);
+
+ mhash_set (&bier_fmask_db.bfdb_hash, &key, index, 0 /*old_value*/);
+ }
+ else
+ {
+ index = p[0];
+ bier_fmask_lock(index);
+ }
+
+ return (index);
+}
+
+u32
+bier_fmask_db_find (index_t bti,
+ const bier_fmask_id_t *fmid)
+{
+ bier_fmask_db_key_t key;
+ u32 index;
+ uword *p;
+
+ /*
+ * there be padding in that thar key, and it's
+ * used as a memcmp in the mhash.
+ */
+ memset(&key, 0, sizeof(key));
+ key.bfmdbk_tbl_id = bti;
+ key.bfmdbk_fm_id = *fmid;
+
+ index = INDEX_INVALID;
+ p = mhash_get(&bier_fmask_db.bfdb_hash, &key);
+
+ if (NULL != p)
+ {
+ index = p[0];
+ }
+
+ return (index);
+}
+
+void
+bier_fmask_db_remove (index_t bti,
+ const bier_fmask_id_t *fmid)
+{
+ bier_fmask_db_key_t key = {
+ .bfmdbk_tbl_id = bti,
+ .bfmdbk_fm_id = *fmid,
+ };
+ uword *p;
+
+ p = mhash_get (&bier_fmask_db.bfdb_hash, &key);
+
+ if (NULL == p) {
+ /*
+ * remove a non-exitant entry - oops
+ */
+ ASSERT (!"remove non-existant fmask");
+ } else {
+ mhash_unset (&(bier_fmask_db.bfdb_hash), &key, 0);
+ }
+}
+
+clib_error_t *
+bier_fmask_db_module_init (vlib_main_t *vm)
+{
+ mhash_init (&bier_fmask_db.bfdb_hash,
+ sizeof(uword),
+ sizeof(bier_fmask_db_key_t));
+
+ return (NULL);
+}
+
+VLIB_INIT_FUNCTION (bier_fmask_db_module_init);
diff --git a/src/vnet/bier/bier_fmask_db.h b/src/vnet/bier/bier_fmask_db.h
new file mode 100644
index 00000000000..6ba40f3a839
--- /dev/null
+++ b/src/vnet/bier/bier_fmask_db.h
@@ -0,0 +1,61 @@
+/*
+ * 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.
+ */
+/**
+ * @brief bier_fmask_db : The BIER fmask Database
+ */
+
+#ifndef __BIER_FMASK_DB_H__
+#define __BIER_FMASK_DB_H__
+
+#include <vnet/ip/ip.h>
+
+#include <vnet/bier/bier_types.h>
+
+/**
+ * Foward declarations
+ */
+struct bier_fmask_t_;
+
+typedef enum bier_hdr_type_t_ {
+ BIER_HDR_IN_IP6,
+ BIER_HDR_O_MPLS,
+} bier_hdr_type_t;
+
+typedef struct bier_fmask_id_t_ {
+ /**
+ * Type of BIER header this fmask supports
+ */
+ bier_hdr_type_t bfmi_hdr_type;
+
+ /**
+ * next-hop of the peer
+ */
+ ip46_address_t bfmi_nh;
+} bier_fmask_id_t;
+
+extern u32
+bier_fmask_db_find_or_create_and_lock(index_t bti,
+ const bier_fmask_id_t *fmid,
+ const fib_route_path_t *rpath);
+
+extern u32
+bier_fmask_db_find(index_t bti,
+ const bier_fmask_id_t *fmid);
+
+extern void
+bier_fmask_db_remove(index_t bti,
+ const bier_fmask_id_t *fmid);
+
+#endif
diff --git a/src/vnet/bier/bier_hdr_inlines.h b/src/vnet/bier/bier_hdr_inlines.h
new file mode 100644
index 00000000000..4437dc82e24
--- /dev/null
+++ b/src/vnet/bier/bier_hdr_inlines.h
@@ -0,0 +1,217 @@
+/*
+ * 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.
+ */
+/**
+ * @brief The BIER inline functions acting on the bier header
+ */
+
+#ifndef __BIER_HDR_INLINES_H__
+#define __BIER_HDR_INLINES_H__
+
+#include <vppinfra/byte_order.h>
+#include <vppinfra/string.h>
+
+#include <vnet/bier/bier_types.h>
+#include <vnet/bier/bier_bit_string.h>
+#include <vnet/ip/ip6_packet.h>
+
+/**
+ * Mask and shift values for the fields incorporated
+ * into the header's first word
+ */
+#define BIER_HDR_1ST_NIBBLE_MASK 0xf0000000
+#define BIER_HDR_VERSION_FIELD_MASK 0x0f000000
+#define BIER_HDR_LEN_FIELD_MASK 0x00f00000
+#define BIER_HDR_ENTROPY_FIELD_MASK 0x000fffff
+
+#define BIER_HDR_1ST_NIBBLE_SHIFT 28
+#define BIER_HDR_VERSION_FIELD_SHIFT 24
+#define BIER_HDR_LEN_FIELD_SHIFT 20
+#define BIER_HDR_ENTROPY_FIELD_SHIFT 0
+
+#define BIER_HDR_1ST_NIBBLE_VALUE 0x5
+
+/**
+ * Mask and shift values for fields in the headers trainling word
+ */
+#define BIER_HDR_PROTO_FIELD_MASK 0x003f
+#define BIER_HDR_OAM_FIELD_MASK 0xc000
+#define BIER_HDR_DSCP_FIELD_MASK 0x0fc0
+#define BIER_HDR_DSCP_FIELD_SHIFT 6
+#define BIER_HDR_PROTO_FIELD_SHIFT 0
+#define BIER_HDR_OAM_FIELD_SHIFT 14
+
+static inline bier_hdr_version_t
+bier_hdr_get_version (const bier_hdr_t *bier_hdr)
+{
+ return ((bier_hdr->bh_first_word &
+ BIER_HDR_VERSION_FIELD_MASK) >>
+ BIER_HDR_VERSION_FIELD_SHIFT);
+}
+
+static inline bier_hdr_len_id_t
+bier_hdr_get_len_id (const bier_hdr_t *bier_hdr)
+{
+ return ((bier_hdr->bh_first_word &
+ BIER_HDR_LEN_FIELD_MASK) >>
+ BIER_HDR_LEN_FIELD_SHIFT);
+}
+
+static inline bier_hdr_entropy_t
+bier_hdr_get_entropy (const bier_hdr_t *bier_hdr)
+{
+ return ((bier_hdr->bh_first_word &
+ BIER_HDR_ENTROPY_FIELD_MASK) >>
+ BIER_HDR_ENTROPY_FIELD_SHIFT);
+}
+
+static inline void
+bier_hdr_1st_nibble (bier_hdr_t *hdr)
+{
+ hdr->bh_first_word &= ~(BIER_HDR_1ST_NIBBLE_MASK);
+ hdr->bh_first_word |= (BIER_HDR_1ST_NIBBLE_VALUE <<
+ BIER_HDR_1ST_NIBBLE_SHIFT);
+}
+
+static inline u8
+bier_hdr_get_1st_nibble (bier_hdr_t *hdr)
+{
+ return ((hdr->bh_first_word & BIER_HDR_1ST_NIBBLE_MASK) >>
+ BIER_HDR_1ST_NIBBLE_SHIFT);
+}
+
+static inline void
+bier_hdr_set_version (bier_hdr_t *hdr,
+ bier_hdr_version_t version)
+{
+ hdr->bh_first_word &= ~(BIER_HDR_VERSION_FIELD_MASK);
+ hdr->bh_first_word |= (version << BIER_HDR_VERSION_FIELD_SHIFT);
+}
+
+static inline void
+bier_hdr_set_len_id (bier_hdr_t *hdr,
+ bier_hdr_len_id_t len)
+{
+ hdr->bh_first_word &= ~(BIER_HDR_LEN_FIELD_MASK);
+ hdr->bh_first_word |= (len << BIER_HDR_LEN_FIELD_SHIFT);
+}
+
+static inline void
+bier_hdr_set_entropy (bier_hdr_t *hdr,
+ bier_hdr_entropy_t entropy)
+{
+ entropy = entropy & BIER_HDR_ENTROPY_FIELD_MASK;
+ hdr->bh_first_word &= ~(BIER_HDR_ENTROPY_FIELD_MASK);
+ hdr->bh_first_word |= (entropy << BIER_HDR_ENTROPY_FIELD_SHIFT);
+}
+
+#define BIER_HDR_FIRST_WORD(version, len, entropy) \
+ ((BIER_HDR_1ST_NIBBLE_VALUE << \
+ BIER_HDR_1ST_NIBBLE_SHIFT) | \
+ (version << BIER_HDR_VERSION_FIELD_SHIFT) | \
+ (len << BIER_HDR_LEN_FIELD_SHIFT) | \
+ ((entropy & BIER_HDR_ENTROPY_FIELD_MASK) \
+ << BIER_HDR_ENTROPY_FIELD_SHIFT))
+
+static inline void
+bier_hdr_ntoh (bier_hdr_t *bier_hdr)
+{
+ bier_hdr->bh_first_word = clib_net_to_host_u32(bier_hdr->bh_first_word);
+ bier_hdr->bh_oam_dscp_proto = clib_net_to_host_u16(bier_hdr->bh_oam_dscp_proto);
+ bier_hdr->bh_bfr_id = clib_net_to_host_u16(bier_hdr->bh_bfr_id);
+}
+
+static inline void
+bier_hdr_hton (bier_hdr_t *bier_hdr)
+{
+ bier_hdr->bh_first_word = clib_host_to_net_u32(bier_hdr->bh_first_word);
+ bier_hdr->bh_oam_dscp_proto = clib_host_to_net_u16(bier_hdr->bh_oam_dscp_proto);
+ bier_hdr->bh_bfr_id = clib_host_to_net_u16(bier_hdr->bh_bfr_id);
+}
+
+static inline bier_hdr_src_id_t
+bier_hdr_get_src_id (const bier_hdr_t *bier_hdr)
+{
+ return (bier_hdr->bh_bfr_id);
+}
+
+static inline void
+bier_hdr_set_src_id (bier_hdr_t *bier_hdr,
+ bier_hdr_src_id_t src_id)
+{
+ bier_hdr->bh_bfr_id = src_id;
+}
+static inline void
+bier_hdr_set_proto_id (bier_hdr_t *bier_hdr,
+ bier_hdr_proto_id_t proto)
+{
+ bier_hdr->bh_oam_dscp_proto &= ~(BIER_HDR_PROTO_FIELD_MASK);
+ bier_hdr->bh_oam_dscp_proto |= (proto << BIER_HDR_PROTO_FIELD_SHIFT);
+}
+
+static inline bier_hdr_proto_id_t
+bier_hdr_get_proto_id (const bier_hdr_t *bier_hdr)
+{
+ return ((bier_hdr->bh_oam_dscp_proto & BIER_HDR_PROTO_FIELD_MASK) >>
+ BIER_HDR_PROTO_FIELD_SHIFT);
+}
+
+static inline void
+bier_hdr_clear (bier_hdr_t *bier_hdr)
+{
+ memset(&bier_hdr->bh_bit_string, 0,
+ bier_hdr_len_id_to_num_buckets(
+ bier_hdr_get_len_id(bier_hdr)));
+}
+
+static inline void
+bier_hdr_init (bier_hdr_t *bier_hdr,
+ bier_hdr_version_t version,
+ bier_hdr_proto_id_t proto,
+ bier_hdr_len_id_t len,
+ bier_hdr_entropy_t entropy,
+ bier_bp_t src)
+{
+ bier_hdr_1st_nibble(bier_hdr);
+ bier_hdr_set_version(bier_hdr, version);
+ bier_hdr_set_len_id(bier_hdr, len);
+ bier_hdr_set_entropy(bier_hdr, entropy);
+ bier_hdr_set_proto_id(bier_hdr, proto);
+ bier_hdr_set_src_id(bier_hdr, src);
+ bier_hdr_clear(bier_hdr);
+}
+
+static inline size_t
+bier_hdr_str_num_bytes (const bier_hdr_t *bier_hdr)
+{
+ return (bier_hdr_len_id_to_num_bytes(
+ bier_hdr_get_len_id(bier_hdr)));
+}
+
+static inline size_t
+bier_hdr_num_bytes (const bier_hdr_t *bier_hdr)
+{
+ return (sizeof(bier_hdr_t) +
+ bier_hdr_str_num_bytes(bier_hdr));
+}
+
+static inline void
+bier_bit_string_init_from_hdr (bier_hdr_t *bier_hdr,
+ bier_bit_string_t *bit_string)
+{
+ bit_string->bbs_len = bier_hdr_str_num_bytes(bier_hdr);
+ bit_string->bbs_buckets = bier_hdr->bh_bit_string;
+}
+
+#endif
diff --git a/src/vnet/bier/bier_imp.c b/src/vnet/bier/bier_imp.c
new file mode 100644
index 00000000000..c51dede9c0a
--- /dev/null
+++ b/src/vnet/bier/bier_imp.c
@@ -0,0 +1,288 @@
+/*
+ * Copyright (c) 2017 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.
+ */
+/**
+ * bier_imposition : The BIER imposition object
+ *
+ * A BIER imposition object is present in the IP mcast output list
+ * and represents the imposition of a BIER bitmask. After BIER header
+ * imposition the packet is forward within the appropriate/specifid
+ * BIER table
+ */
+
+#include <vnet/bier/bier_imp.h>
+#include <vnet/bier/bier_table.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+#include <vnet/fib/fib_node.h>
+#include <vnet/mpls/mpls_types.h>
+
+/**
+ * The memory pool of all imp objects
+ */
+bier_imp_t *bier_imp_pool;
+
+/**
+ * When constructing the BIER imp ID from an index and BSL, shift
+ * the BSL this far
+ */
+#define BIER_IMP_ID_HLEN_SHIFT 24
+
+static void
+bier_imp_lock_i (bier_imp_t *bi)
+{
+ bi->bi_locks++;
+}
+
+void
+bier_imp_lock (index_t bii)
+{
+ bier_imp_lock_i(bier_imp_get(bii));
+}
+
+static index_t
+bier_imp_get_index(bier_imp_t *bi)
+{
+ return (bi - bier_imp_pool);
+}
+
+index_t
+bier_imp_add_or_lock (const bier_table_id_t *bti,
+ bier_bp_t sender,
+ const bier_bit_string_t *bs)
+{
+ bier_imp_t *bi = NULL;
+ fib_protocol_t fproto;
+ index_t btii;
+
+ pool_get_aligned(bier_imp_pool, bi, CLIB_CACHE_LINE_BYTES);
+
+ bi->bi_tbl = *bti;
+ btii = bier_table_add_or_lock(bti, MPLS_LABEL_INVALID);
+
+ /*
+ * init the BIER header we will paint on in the data plane
+ */
+ bier_hdr_init(&bi->bi_hdr,
+ BIER_HDR_VERSION_1,
+ BIER_HDR_PROTO_INVALID, // filled in later
+ bti->bti_hdr_len,
+ 0, // entropy
+ sender);
+ bier_hdr_hton(&bi->bi_hdr);
+ clib_memcpy(&bi->bi_bits, bs->bbs_buckets, bs->bbs_len);
+
+ bier_imp_lock_i(bi);
+
+ /*
+ * get and stack on the forwarding info from the table
+ */
+ FOR_EACH_FIB_IP_PROTOCOL(fproto)
+ {
+ /*
+ * initialise to invalid first, lest we pick up garbage
+ * from the pool alloc
+ */
+ dpo_id_t dpo = DPO_INVALID;
+ bi->bi_dpo[fproto] = dpo;
+
+ bier_table_contribute_forwarding(btii, &dpo);
+ dpo_stack(DPO_BIER_IMP, fib_proto_to_dpo(fproto),
+ &bi->bi_dpo[fproto],
+ &dpo);
+ dpo_reset(&dpo);
+ }
+
+ return (bier_imp_get_index(bi));
+}
+
+void
+bier_imp_unlock (index_t bii)
+{
+ fib_protocol_t fproto;
+ bier_imp_t *bi;
+
+ if (INDEX_INVALID == bii)
+ {
+ return;
+ }
+
+ bi = bier_imp_get(bii);
+
+ bi->bi_locks--;
+
+ if (0 == bi->bi_locks)
+ {
+ bier_table_unlock(&bi->bi_tbl);
+
+ FOR_EACH_FIB_IP_PROTOCOL(fproto)
+ {
+ dpo_reset(&bi->bi_dpo[fproto]);
+ }
+ pool_put(bier_imp_pool, bi);
+ }
+}
+
+u8*
+format_bier_imp (u8* s, va_list *args)
+{
+ index_t bii = va_arg (*args, index_t);
+ u32 indent = va_arg(*args, u32);
+ bier_show_flags_t flags = va_arg(*args, bier_show_flags_t);
+ bier_imp_t *bi;
+
+ bi = bier_imp_get(bii);
+
+ s = format(s, "bier-imp:[%d]: tbl:[%U] hdr:[%U]",
+ bier_imp_get_index(bi),
+ format_bier_table_id, &bi->bi_tbl,
+ format_bier_hdr, &bi->bi_hdr);
+
+ if (BIER_SHOW_DETAIL & flags)
+ {
+ bier_bit_string_t bbs;
+ bier_hdr_t copy;
+
+ copy = bi->bi_hdr;
+ bier_hdr_ntoh(&copy);
+ bier_bit_string_init(&bbs,
+ bier_hdr_get_len_id(&copy),
+ bi->bi_bits.bits);
+
+ s = format(s, "\n%U%U",
+ format_white_space, indent,
+ format_bier_bit_string, &bbs);
+ s = format(s, "\n%U%U",
+ format_white_space, indent,
+ format_dpo_id, &bi->bi_dpo, indent+2);
+ }
+
+ return (s);
+}
+
+void
+bier_imp_contribute_forwarding (index_t bii,
+ dpo_proto_t proto,
+ dpo_id_t *dpo)
+{
+ dpo_set(dpo, DPO_BIER_IMP, proto, bii);
+}
+
+const static char* const bier_imp_ip4_nodes[] =
+{
+ "bier-imp-ip4",
+ NULL,
+};
+const static char* const bier_imp_ip6_nodes[] =
+{
+ "bier-imp-ip6",
+ NULL,
+};
+
+const static char* const * const bier_imp_nodes[DPO_PROTO_NUM] =
+{
+ [DPO_PROTO_IP4] = bier_imp_ip4_nodes,
+ [DPO_PROTO_IP6] = bier_imp_ip6_nodes,
+};
+
+static void
+bier_imp_dpo_lock (dpo_id_t *dpo)
+{
+ bier_imp_lock(dpo->dpoi_index);
+}
+
+static void
+bier_imp_dpo_unlock (dpo_id_t *dpo)
+{
+ bier_imp_unlock(dpo->dpoi_index);
+}
+
+static void
+bier_imp_dpo_mem_show (void)
+{
+ fib_show_memory_usage("BIER imposition",
+ pool_elts(bier_imp_pool),
+ pool_len(bier_imp_pool),
+ sizeof(bier_imp_t));
+}
+
+static u8*
+format_bier_imp_dpo (u8* s, va_list *ap)
+{
+ index_t index = va_arg(*ap, index_t);
+ u32 indent = va_arg(*ap, u32);
+
+ s = format(s, "%U", format_bier_imp, index, indent, BIER_SHOW_DETAIL);
+
+ return (s);
+}
+
+const static dpo_vft_t bier_imp_vft = {
+ .dv_lock = bier_imp_dpo_lock,
+ .dv_unlock = bier_imp_dpo_unlock,
+ .dv_format = format_bier_imp_dpo,
+ .dv_mem_show = bier_imp_dpo_mem_show,
+};
+
+clib_error_t *
+bier_imp_db_module_init (vlib_main_t *vm)
+{
+ dpo_register(DPO_BIER_IMP, &bier_imp_vft, bier_imp_nodes);
+
+ return (NULL);
+}
+
+VLIB_INIT_FUNCTION (bier_imp_db_module_init);
+
+static clib_error_t *
+show_bier_imp (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd)
+{
+ bier_imp_t *bi;
+ index_t bii;
+
+ bii = INDEX_INVALID;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
+ if (unformat (input, "%d", &bii))
+ ;
+ else
+ {
+ break;
+ }
+ }
+
+ if (INDEX_INVALID == bii)
+ {
+ pool_foreach(bi, bier_imp_pool,
+ ({
+ vlib_cli_output(vm, "%U", format_bier_imp,
+ bier_imp_get_index(bi),
+ 1,
+ BIER_SHOW_BRIEF);
+ }));
+ }
+ else
+ {
+ vlib_cli_output(vm, "%U", format_bier_imp, bii, 1,
+ BIER_SHOW_DETAIL);
+ }
+ return (NULL);
+}
+
+VLIB_CLI_COMMAND (show_bier_imp_node, static) = {
+ .path = "show bier imp",
+ .short_help = "show bier imp [index]",
+ .function = show_bier_imp,
+};
diff --git a/src/vnet/bier/bier_imp.h b/src/vnet/bier/bier_imp.h
new file mode 100644
index 00000000000..fa53989fc93
--- /dev/null
+++ b/src/vnet/bier/bier_imp.h
@@ -0,0 +1,87 @@
+/*
+ * 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.
+ */
+/**
+ * bier_imposition : The BIER imposition object
+ *
+ * A BIER imposition object is present in the IP mcast output list
+ * and represents the imposition of a BIER bitmask. After BIER header
+ * imposition the packet is forward within the appropriate/specifid
+ * BIER table
+ */
+
+#ifndef __BIER_IMPOSITION_H__
+#define __BIER_IMPOSITION_H__
+
+#include <vnet/bier/bier_types.h>
+#include <vnet/fib/fib_types.h>
+#include <vnet/dpo/dpo.h>
+
+/**
+ * The BIER imposition object
+ */
+typedef struct bier_imp_t_ {
+ /**
+ * The BIER table into which to forward the post imposed packet
+ */
+ bier_table_id_t bi_tbl;
+
+ /**
+ * number of locks
+ */
+ u32 bi_locks;
+
+ /**
+ * The DPO contirubted from the resolving BIER table.
+ * One per-IP protocol. This allows us to share a BIER imposition
+ * object for a IPv4 and IPv6 mfib path.
+ */
+ dpo_id_t bi_dpo[FIB_PROTOCOL_IP_MAX];
+
+ /**
+ * The Header to impose.
+ */
+ bier_hdr_t bi_hdr;
+
+ /**
+ * The bit string.
+ * This is a memory v. speed tradeoff. We inline here the
+ * largest header type so as the bitstring is on the same
+ * cacheline as the header.
+ */
+ bier_bit_mask_4096_t bi_bits;
+} bier_imp_t;
+
+extern index_t bier_imp_add_or_lock(const bier_table_id_t *bt,
+ bier_bp_t sender,
+ const bier_bit_string_t *bs);
+
+extern void bier_imp_unlock(index_t bii);
+extern void bier_imp_lock(index_t bii);
+
+extern u8* format_bier_imp(u8* s, va_list *ap);
+
+extern void bier_imp_contribute_forwarding(index_t bii,
+ dpo_proto_t proto,
+ dpo_id_t *dpo);
+
+extern bier_imp_t *bier_imp_pool;
+
+always_inline bier_imp_t*
+bier_imp_get (index_t bii)
+{
+ return (pool_elt_at_index(bier_imp_pool, bii));
+}
+
+#endif
diff --git a/src/vnet/bier/bier_imp_node.c b/src/vnet/bier/bier_imp_node.c
new file mode 100644
index 00000000000..e9aae93b460
--- /dev/null
+++ b/src/vnet/bier/bier_imp_node.c
@@ -0,0 +1,217 @@
+/*
+ * 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/bier/bier_imp.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+#include <vnet/ip/ip.h>
+
+/**
+ * @brief A struct to hold tracing information for the BIER imposition
+ * node.
+ */
+typedef struct bier_imp_trace_t_
+{
+ /**
+ * BIER imposition object hit
+ */
+ index_t imp;
+
+ /**
+ * BIER hdr applied
+ */
+ bier_hdr_t hdr;
+} bier_imp_trace_t;
+
+always_inline uword
+bier_imp_dpo_inline (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * from_frame,
+ fib_protocol_t fproto,
+ bier_hdr_proto_id_t bproto)
+{
+ u32 n_left_from, next_index, * from, * to_next;
+
+ from = vlib_frame_vector_args (from_frame);
+ n_left_from = from_frame->n_vectors;
+
+ next_index = node->cached_next_index;
+
+ while (n_left_from > 0)
+ {
+ u32 n_left_to_next;
+
+ vlib_get_next_frame(vm, node, next_index, to_next, n_left_to_next);
+
+ while (n_left_from > 0 && n_left_to_next > 0)
+ {
+ vlib_buffer_t * b0;
+ bier_imp_t *bimp0;
+ bier_hdr_t *hdr0;
+ u32 bi0, bii0;
+ u32 next0;
+
+ bi0 = from[0];
+ to_next[0] = bi0;
+ from += 1;
+ to_next += 1;
+ n_left_from -= 1;
+ n_left_to_next -= 1;
+
+ b0 = vlib_get_buffer (vm, bi0);
+
+ bii0 = vnet_buffer(b0)->ip.adj_index[VLIB_TX];
+ bimp0 = bier_imp_get(bii0);
+
+ if (FIB_PROTOCOL_IP4 == fproto)
+ {
+ /*
+ * decrement the TTL on ingress to the BIER domain
+ */
+ ip4_header_t * ip0 = vlib_buffer_get_current(b0);
+ u32 checksum0;
+
+ checksum0 = ip0->checksum + clib_host_to_net_u16 (0x0100);
+ checksum0 += checksum0 >= 0xffff;
+
+ ip0->checksum = checksum0;
+ ip0->ttl -= 1;
+
+ /*
+ * calculate an entropy
+ */
+ if (0 == vnet_buffer(b0)->ip.flow_hash)
+ {
+ vnet_buffer(b0)->ip.flow_hash =
+ ip4_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
+ }
+ }
+ if (FIB_PROTOCOL_IP6 == fproto)
+ {
+ /*
+ * decrement the TTL on ingress to the BIER domain
+ */
+ ip6_header_t * ip0 = vlib_buffer_get_current(b0);
+
+ ip0->hop_limit -= 1;
+
+ /*
+ * calculate an entropy
+ */
+ if (0 == vnet_buffer(b0)->ip.flow_hash)
+ {
+ vnet_buffer(b0)->ip.flow_hash =
+ ip6_compute_flow_hash (ip0, IP_FLOW_HASH_DEFAULT);
+ }
+ }
+
+ /* Paint the BIER header */
+ vlib_buffer_advance(b0, -(sizeof(bier_hdr_t) +
+ bier_hdr_len_id_to_num_bytes(bimp0->bi_tbl.bti_hdr_len)));
+ hdr0 = vlib_buffer_get_current(b0);
+ clib_memcpy(hdr0, &bimp0->bi_hdr,
+ (sizeof(bier_hdr_t) +
+ bier_hdr_len_id_to_num_bytes(bimp0->bi_tbl.bti_hdr_len)));
+ /*
+ * Fixup the entropy and protocol, both of which have a
+ * zero value post the paint job
+ */
+ hdr0->bh_oam_dscp_proto |=
+ clib_host_to_net_u16(bproto << BIER_HDR_PROTO_FIELD_SHIFT);
+ hdr0->bh_first_word |=
+ clib_host_to_net_u32((vnet_buffer(b0)->ip.flow_hash &
+ BIER_HDR_ENTROPY_FIELD_MASK) <<
+ BIER_HDR_ENTROPY_FIELD_SHIFT);
+
+ /* next node */
+ next0 = bimp0->bi_dpo[fproto].dpoi_next_node;
+ vnet_buffer(b0)->ip.adj_index[VLIB_TX] =
+ bimp0->bi_dpo[fproto].dpoi_index;
+
+ if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
+ {
+ bier_imp_trace_t *tr =
+ vlib_add_trace (vm, node, b0, sizeof (*tr));
+ tr->imp = bii0;
+ tr->hdr = *hdr0;
+ }
+
+ vlib_validate_buffer_enqueue_x1(vm, node, next_index, to_next,
+ n_left_to_next, bi0, next0);
+ }
+ vlib_put_next_frame (vm, node, next_index, n_left_to_next);
+ }
+ return from_frame->n_vectors;
+}
+
+static u8 *
+format_bier_imp_trace (u8 * s, va_list * args)
+{
+ CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
+ CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
+ bier_imp_trace_t * t;
+ u32 indent;
+
+ t = va_arg (*args, bier_imp_trace_t *);
+ indent = format_get_indent (s);
+
+ s = format (s, "%U", format_bier_imp, t->imp, indent, BIER_SHOW_BRIEF);
+ return (s);
+}
+
+static uword
+bier_imp_ip4 (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * frame)
+{
+ return (bier_imp_dpo_inline(vm, node, frame,
+ FIB_PROTOCOL_IP4,
+ BIER_HDR_PROTO_IPV4));
+}
+
+VLIB_REGISTER_NODE (bier_imp_ip4_node) = {
+ .function = bier_imp_ip4,
+ .name = "bier-imp-ip4",
+ .vector_size = sizeof (u32),
+
+ .format_trace = format_bier_imp_trace,
+ .n_next_nodes = 1,
+ .next_nodes = {
+ [0] = "error-drop",
+ }
+};
+VLIB_NODE_FUNCTION_MULTIARCH (bier_imp_ip4_node, bier_imp_ip4)
+
+static uword
+bier_imp_ip6 (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * frame)
+{
+ return (bier_imp_dpo_inline(vm, node, frame,
+ FIB_PROTOCOL_IP6,
+ BIER_HDR_PROTO_IPV6));
+}
+
+VLIB_REGISTER_NODE (bier_imp_ip6_node) = {
+ .function = bier_imp_ip6,
+ .name = "bier-imp-ip6",
+ .vector_size = sizeof (u32),
+
+ .format_trace = format_bier_imp_trace,
+ .n_next_nodes = 1,
+ .next_nodes = {
+ [0] = "error-drop",
+ }
+};
+VLIB_NODE_FUNCTION_MULTIARCH (bier_imp_ip6_node, bier_imp_ip6)
diff --git a/src/vnet/bier/bier_input.c b/src/vnet/bier/bier_input.c
new file mode 100644
index 00000000000..88b37fc80c0
--- /dev/null
+++ b/src/vnet/bier/bier_input.c
@@ -0,0 +1,175 @@
+/*
+ * 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/buffer.h>
+
+#include <vnet/bier/bier_table.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+
+typedef enum {
+#define bier_error(n,s) BIER_INPUT_ERROR_##n,
+#include <vnet/bier/bier_input_error.def>
+#undef bier_error
+ BIER_INPUT_N_ERROR,
+} bier_input_error_t;
+
+static char * bier_error_strings[] = {
+#define bier_error(n,s) s,
+#include <vnet/bier/bier_input_error.def>
+#undef bier_error
+};
+
+typedef enum bier_input_next_t_ {
+ BIER_INPUT_NEXT_BIER_LOOKUP,
+ BIER_INPUT_NEXT_DROP,
+ BIER_INPUT_N_NEXT,
+} bier_input_next_t;
+
+vlib_node_registration_t bier_input_node;
+
+/**
+ * @brief Packet trace recoed for a BIER output
+ */
+typedef struct bier_input_trace_t_
+{
+ u32 next_index;
+ u32 bt_index;
+} bier_input_trace_t;
+
+static int
+bier_hdr_validate (bier_hdr_t *bier_hdr,
+ bier_hdr_len_id_t expected_length)
+{
+ /*
+ * checks:
+ * - the version field must be 1
+ * - the header length matches the length expected
+ */
+ if (PREDICT_FALSE((BIER_HDR_VERSION_1 != bier_hdr_get_version(bier_hdr)) ||
+ (expected_length != bier_hdr_get_len_id(bier_hdr)))) {
+ return (0);
+ }
+
+ return (1);
+}
+
+static uword
+bier_input (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * from_frame)
+{
+ u32 n_left_from, next_index, * from, * to_next;
+
+ from = vlib_frame_vector_args (from_frame);
+ n_left_from = from_frame->n_vectors;
+
+ /*
+ * objection your honour! speculation!
+ */
+ next_index = node->cached_next_index;
+
+ while (n_left_from > 0)
+ {
+ u32 n_left_to_next;
+
+ vlib_get_next_frame (vm, node, next_index,
+ to_next, n_left_to_next);
+
+ while (n_left_from > 0 && n_left_to_next > 0)
+ {
+ const bier_table_t *bt0;
+ vlib_buffer_t * b0;
+ bier_hdr_t * bh0;
+ u32 bi0, next0;
+ u32 bt_index0;
+
+ bi0 = from[0];
+ to_next[0] = bi0;
+ from += 1;
+ to_next += 1;
+ n_left_from -= 1;
+ n_left_to_next -= 1;
+
+ b0 = vlib_get_buffer (vm, bi0);
+ bh0 = vlib_buffer_get_current (b0);
+ bier_hdr_ntoh(bh0);
+
+ /*
+ * In the MPLS decap node we squirelled away the
+ * index for the BIER table as the tx adjacency
+ */
+ bt_index0 = vnet_buffer(b0)->ip.adj_index[VLIB_TX];
+ bt0 = bier_table_get(bt_index0);
+
+ if (PREDICT_TRUE(bier_hdr_validate(bh0, bt0->bt_id.bti_hdr_len)))
+ {
+ next0 = BIER_INPUT_NEXT_BIER_LOOKUP;
+ } else {
+ next0 = BIER_INPUT_NEXT_DROP;
+ b0->error = node->errors[BIER_INPUT_ERROR_INVALID_HEADER];
+ }
+
+ if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
+ {
+ bier_input_trace_t *tr;
+
+ tr = vlib_add_trace (vm, node, b0, sizeof (*tr));
+ tr->next_index = next0;
+ tr->bt_index = bt_index0;
+ }
+
+ vlib_validate_buffer_enqueue_x1 (vm, node, next_index,
+ to_next, n_left_to_next,
+ bi0, next0);
+ }
+
+ vlib_put_next_frame (vm, node, next_index, n_left_to_next);
+ }
+
+ vlib_node_increment_counter (vm, bier_input_node.index,
+ BIER_INPUT_ERROR_PKTS_VALID,
+ from_frame->n_vectors);
+ return (from_frame->n_vectors);
+}
+
+static u8 *
+format_bier_input_trace (u8 * s, va_list * args)
+{
+ CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
+ CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
+ bier_input_trace_t * t = va_arg (*args, bier_input_trace_t *);
+
+ s = format (s, " next [%d], BIER Table index %d",
+ t->next_index, t->bt_index);
+ return s;
+}
+
+VLIB_REGISTER_NODE (bier_input_node) = {
+ .function = bier_input,
+ .name = "bier-input",
+ /* Takes a vector of packets. */
+ .vector_size = sizeof (u32),
+
+ .n_errors = BIER_INPUT_N_ERROR,
+ .error_strings = bier_error_strings,
+
+ .n_next_nodes = BIER_INPUT_N_NEXT,
+ .next_nodes = {
+ [BIER_INPUT_NEXT_BIER_LOOKUP] = "bier-lookup",
+ [BIER_INPUT_NEXT_DROP] = "bier-drop",
+ },
+
+ .format_trace = format_bier_input_trace,
+};
diff --git a/src/vnet/bier/bier_input_error.def b/src/vnet/bier/bier_input_error.def
new file mode 100644
index 00000000000..6f0034316f0
--- /dev/null
+++ b/src/vnet/bier/bier_input_error.def
@@ -0,0 +1,19 @@
+/*
+ * 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.
+ */
+
+bier_error (NONE, "no error")
+bier_error (TABLE_NOT_FOUND, "table not found")
+bier_error (INVALID_HEADER, "invalid header")
+bier_error (PKTS_VALID, "BIER input packets")
diff --git a/src/vnet/bier/bier_lookup.c b/src/vnet/bier/bier_lookup.c
new file mode 100644
index 00000000000..4cf29f886e4
--- /dev/null
+++ b/src/vnet/bier/bier_lookup.c
@@ -0,0 +1,367 @@
+/*
+ * 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/buffer.h>
+#include <vnet/vnet.h>
+
+#include <vnet/bier/bier_fmask.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+#include <vnet/bier/bier_table.h>
+#include <vnet/bier/bier_fmask.h>
+
+/**
+ * Struct maintining the per-worker thread data for BIER lookups
+ */
+typedef struct bier_lookup_main_t_
+{
+ /* per-cpu vector of cloned packets */
+ u32 **blm_clones;
+ /* per-cpu vector of BIER fmasks */
+ u32 **blm_fmasks;
+} bier_lookup_main_t;
+
+/**
+ * Single instance of the lookup main
+ */
+static bier_lookup_main_t bier_lookup_main;
+
+static char * bier_lookup_error_strings[] = {
+#define bier_error(n,s) s,
+#include <vnet/bier/bier_lookup_error.def>
+#undef bier_error
+};
+
+/*
+ * Keep these values sematically the same as BIER lookup
+ */
+#define foreach_bier_lookup_next \
+ _(DROP, "bier-drop") \
+ _(OUTPUT, "bier-output")
+
+typedef enum {
+#define _(s,n) BIER_LOOKUP_NEXT_##s,
+ foreach_bier_lookup_next
+#undef _
+ BIER_LOOKUP_N_NEXT,
+} bier_lookup_next_t;
+
+typedef enum {
+#define bier_error(n,s) BIER_LOOKUP_ERROR_##n,
+#include <vnet/bier/bier_lookup_error.def>
+#undef bier_error
+ BIER_LOOKUP_N_ERROR,
+} bier_lookup_error_t;
+
+vlib_node_registration_t bier_lookup_node;
+
+/**
+ * @brief Packet trace recoed for a BIER lookup
+ */
+typedef struct bier_lookup_trace_t_
+{
+ u32 next_index;
+ index_t bt_index;
+ index_t bfm_index;
+} bier_lookup_trace_t;
+
+static uword
+bier_lookup (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * from_frame)
+{
+ u32 n_left_from, next_index, * from, * to_next;
+ bier_lookup_main_t *blm = &bier_lookup_main;
+ u32 thread_index = vlib_get_thread_index();
+
+ from = vlib_frame_vector_args (from_frame);
+ n_left_from = from_frame->n_vectors;
+ next_index = BIER_LOOKUP_NEXT_DROP;
+
+ while (n_left_from > 0)
+ {
+ u32 n_left_to_next;
+
+ vlib_get_next_frame (vm, node, next_index,
+ to_next, n_left_to_next);
+
+ while (n_left_from > 0 && n_left_to_next > 0)
+ {
+ bier_bit_mask_bucket_t buckets_copy[BIER_HDR_BUCKETS_256];
+ u32 next0, bi0, n_bytes, bti0, bfmi0;
+ const bier_fmask_t *bfm0;
+ const bier_table_t *bt0;
+ u16 index, num_buckets;
+ const bier_hdr_t *bh0;
+ bier_bit_string_t bbs;
+ vlib_buffer_t *b0;
+ bier_bp_t fbs;
+ int bucket;
+
+ bi0 = from[0];
+ from += 1;
+ n_left_from -= 1;
+
+ b0 = vlib_get_buffer (vm, bi0);
+ bh0 = vlib_buffer_get_current (b0);
+ bti0 = vnet_buffer(b0)->ip.adj_index[VLIB_TX];
+
+ /*
+ * default to drop so that if no bits are matched then
+ * that is where we go - DROP.
+ */
+ next0 = BIER_LOOKUP_NEXT_DROP;
+
+ /*
+ * At the imposition or input node,
+ * we stored the BIER Table index in the TX adjacency
+ */
+ bt0 = bier_table_get(vnet_buffer(b0)->ip.adj_index[VLIB_TX]);
+
+ /*
+ * we should only forward via one for the ECMP tables
+ */
+ ASSERT(!bier_table_is_main(bt0));
+
+ /*
+ * number of integer sized buckets
+ */
+ n_bytes = bier_hdr_len_id_to_num_buckets(bt0->bt_id.bti_hdr_len);
+ vnet_buffer(b0)->bier.n_bytes = n_bytes;
+ vnet_buffer(b0)->sw_if_index[VLIB_TX] = ~0;
+ num_buckets = n_bytes / sizeof(int);
+ bier_bit_string_init(&bbs,
+ bt0->bt_id.bti_hdr_len,
+ buckets_copy);
+ memcpy(bbs.bbs_buckets, bh0->bh_bit_string, bbs.bbs_len);
+
+ /*
+ * reset the fmask and clone storage vectors
+ */
+ vec_reset_length (blm->blm_fmasks[thread_index]);
+ vec_reset_length (blm->blm_clones[thread_index]);
+
+ /*
+ * Loop through the buckets in the header
+ */
+ for (index = 0; index < num_buckets; index++) {
+ /*
+ * loop through each bit in the bucket
+ */
+ bucket = ((int*)bbs.bbs_buckets)[index];
+
+ while (bucket) {
+ fbs = bier_find_first_bit_string_set(bucket);
+ fbs += (((num_buckets - 1) - index) *
+ BIER_BIT_MASK_BITS_PER_INT);
+
+ bfmi0 = bier_table_fwd_lookup(bt0, fbs);
+
+ /*
+ * whatever happens, the bit we just looked for
+ * MUST be cleared from the packet
+ * otherwise we could be in this loop a while ...
+ */
+ bier_bit_string_clear_bit(&bbs, fbs);
+
+ if (PREDICT_TRUE(INDEX_INVALID != bfmi0))
+ {
+ bfm0 = bier_fmask_get(bfmi0);
+ vnet_buffer (b0)->ip.adj_index[VLIB_TX] = bfmi0;
+
+ /*
+ * use the bit-string on the fmask to reset
+ * the bits in the header we are walking
+ */
+ bier_bit_string_clear_string(
+ &bfm0->bfm_bits.bfmb_input_reset_string,
+ &bbs);
+ bucket = ((int*)bbs.bbs_buckets)[index];
+
+ /*
+ * the fmask is resolved so replicate a
+ * packet its way
+ */
+ next0 = BIER_LOOKUP_NEXT_OUTPUT;
+
+ vec_add1 (blm->blm_fmasks[thread_index], bfmi0);
+ } else {
+ /*
+ * go to the next bit-position set
+ */
+ bucket = ((int*)bbs.bbs_buckets)[index];
+ continue;
+ }
+ }
+ }
+
+ /*
+ * Full mask now processed.
+ * Create the number of clones we need based on the number
+ * of fmasks we are sending to.
+ */
+ u8 num_cloned, clone;
+ u32 n_clones;
+
+ n_clones = vec_len(blm->blm_fmasks[thread_index]);
+
+ if (PREDICT_TRUE(0 != n_clones))
+ {
+ ASSERT(n_clones < 256);
+ num_cloned = vlib_buffer_clone(vm, bi0,
+ blm->blm_clones[thread_index],
+ n_clones, 128);
+
+ if (num_cloned != n_clones)
+ {
+ vlib_node_increment_counter
+ (vm, node->node_index,
+ BIER_LOOKUP_ERROR_BUFFER_ALLOCATION_FAILURE, 1);
+ }
+
+ for (clone = 0; clone < num_cloned; clone++)
+ {
+ vlib_buffer_t *c0;
+ u32 ci0;
+
+ ci0 = blm->blm_clones[thread_index][clone];
+ c0 = vlib_get_buffer(vm, ci0);
+
+ to_next[0] = ci0;
+ to_next += 1;
+ n_left_to_next -= 1;
+
+ if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
+ {
+ bier_lookup_trace_t *tr;
+
+ vlib_trace_buffer (vm, node, next0, c0, 0);
+ tr = vlib_add_trace (vm, node, c0, sizeof (*tr));
+ tr->bt_index = bti0;
+ tr->bfm_index = blm->blm_fmasks[thread_index][clone];
+
+ c0->flags |= VLIB_BUFFER_IS_TRACED;
+ }
+
+ vlib_validate_buffer_enqueue_x1(vm, node, next_index,
+ to_next, n_left_to_next,
+ ci0, next0);
+
+ /*
+ * After the enqueue it is possible that we over-flow the
+ * frame of the to-next node. When this happens we need to
+ * 'put' that full frame to the node and get a fresh empty
+ * one. Note that these are macros with side effects that
+ * change to_next & n_left_to_next
+ */
+ if (PREDICT_FALSE(0 == n_left_to_next))
+ {
+ vlib_put_next_frame (vm, node, next_index,
+ n_left_to_next);
+ vlib_get_next_frame (vm, node, next_index,
+ to_next, n_left_to_next);
+ }
+ }
+ }
+ else
+ {
+ /*
+ * no clones/replications required. drop this packet
+ */
+ next0 = BIER_LOOKUP_NEXT_DROP;
+ to_next[0] = bi0;
+ to_next += 1;
+ n_left_to_next -= 1;
+
+ if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
+ {
+ bier_lookup_trace_t *tr;
+
+ tr = vlib_add_trace (vm, node, b0, sizeof (*tr));
+
+ tr->bt_index = bti0;
+ tr->bfm_index = ~0;
+ }
+
+ vlib_validate_buffer_enqueue_x1(vm, node, next_index,
+ to_next, n_left_to_next,
+ bi0, next0);
+ }
+ }
+
+ vlib_put_next_frame (vm, node, next_index, n_left_to_next);
+ }
+
+ vlib_node_increment_counter (vm, bier_lookup_node.index,
+ BIER_LOOKUP_ERROR_NONE,
+ from_frame->n_vectors);
+ return (from_frame->n_vectors);
+}
+
+static u8 *
+format_bier_lookup_trace (u8 * s, va_list * args)
+{
+ CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
+ CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
+ bier_lookup_trace_t * t = va_arg (*args, bier_lookup_trace_t *);
+
+ s = format (s, "BIER: next [%d], tbl:%d BFM:%d",
+ t->next_index,
+ t->bt_index,
+ t->bfm_index);
+ return s;
+}
+
+VLIB_REGISTER_NODE (bier_lookup_node) = {
+ .function = bier_lookup,
+ .name = "bier-lookup",
+ /* Takes a vector of packets. */
+ .vector_size = sizeof (u32),
+
+ .n_errors = BIER_LOOKUP_N_ERROR,
+ .error_strings = bier_lookup_error_strings,
+
+ .format_trace = format_bier_lookup_trace,
+ .n_next_nodes = BIER_LOOKUP_N_NEXT,
+ .next_nodes = {
+ [BIER_LOOKUP_NEXT_DROP] = "bier-drop",
+ [BIER_LOOKUP_NEXT_OUTPUT] = "bier-output",
+ },
+};
+
+clib_error_t *
+bier_lookup_module_init (vlib_main_t * vm)
+{
+ bier_lookup_main_t *blm = &bier_lookup_main;
+ u32 thread_index;
+
+ vec_validate (blm->blm_clones, vlib_num_workers());
+ vec_validate (blm->blm_fmasks, vlib_num_workers());
+
+ for (thread_index = 0;
+ thread_index <= vlib_num_workers();
+ thread_index++)
+ {
+ /*
+ * 4096 is the most we will ever need to support
+ * a Bit-Mask length of 4096
+ */
+ vec_validate(blm->blm_fmasks[thread_index], 4095);
+ vec_validate(blm->blm_clones[thread_index], 4095);
+ }
+
+ return 0;
+}
+
+VLIB_INIT_FUNCTION (bier_lookup_module_init);
diff --git a/src/vnet/bier/bier_lookup_error.def b/src/vnet/bier/bier_lookup_error.def
new file mode 100644
index 00000000000..a0510b40ca3
--- /dev/null
+++ b/src/vnet/bier/bier_lookup_error.def
@@ -0,0 +1,18 @@
+/*
+ * 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.
+ */
+
+bier_error (NONE, "no error")
+bier_error (FMASK_UNRES, "fmask unresolved")
+bier_error (BUFFER_ALLOCATION_FAILURE, "Buffer Allocation Failure")
diff --git a/src/vnet/bier/bier_output.c b/src/vnet/bier/bier_output.c
new file mode 100644
index 00000000000..fce6c50b309
--- /dev/null
+++ b/src/vnet/bier/bier_output.c
@@ -0,0 +1,195 @@
+/*
+ * 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/buffer.h>
+
+#include <vnet/bier/bier_fmask.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+#include <vlib/vlib.h>
+
+static char * bier_output_error_strings[] = {
+#define bier_error(n,s) s,
+#include <vnet/bier/bier_output_error.def>
+#undef bier_error
+};
+
+/*
+ * Keep these values sematically the same as BIER output
+ */
+#define foreach_bier_output_next \
+ _(DROP, "bier-drop")
+
+typedef enum {
+#define _(s,n) BIER_OUTPUT_NEXT_##s,
+ foreach_bier_output_next
+#undef _
+ BIER_OUTPUT_N_NEXT,
+} bier_output_next_t;
+
+typedef enum {
+#define bier_error(n,s) BIER_OUTPUT_ERROR_##n,
+#include <vnet/bier/bier_output_error.def>
+#undef bier_error
+ BIER_OUTPUT_N_ERROR,
+} bier_output_error_t;
+
+/**
+ * Forward declaration
+ */
+vlib_node_registration_t bier_output_node;
+
+/**
+ * @brief Packet trace recoed for a BIER output
+ */
+typedef struct bier_output_trace_t_
+{
+ u32 next_index;
+ index_t bfm_index;
+} bier_output_trace_t;
+
+static uword
+bier_output (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * from_frame)
+{
+ u32 n_left_from, next_index, * from, * to_next;
+
+ from = vlib_frame_vector_args (from_frame);
+ n_left_from = from_frame->n_vectors;
+
+ // vnet_buffer(b0)->sw_if_index[VLIB_TX] = d0->tx_fib_index;
+
+ /*
+ * objection your honour! speculation!
+ */
+ next_index = node->cached_next_index;
+
+ while (n_left_from > 0)
+ {
+ u32 n_left_to_next;
+
+ vlib_get_next_frame (vm, node, next_index,
+ to_next, n_left_to_next);
+
+ while (n_left_from > 0 && n_left_to_next > 0)
+ {
+ bier_output_next_t next0;
+ bier_bit_string_t bbs;
+ vlib_buffer_t * b0;
+ bier_fmask_t *bfm0;
+ bier_hdr_t *bh0;
+ u32 bi0, *h0;
+ u32 bfmi0;
+
+ bi0 = from[0];
+ to_next[0] = bi0;
+ from += 1;
+ to_next += 1;
+ n_left_from -= 1;
+ n_left_to_next -= 1;
+
+ b0 = vlib_get_buffer (vm, bi0);
+ bh0 = vlib_buffer_get_current (b0);
+ bier_bit_string_init_from_hdr(bh0, &bbs);
+
+ /*
+ * In the BIER Lookup node we squirelled away the
+ * BIER fmask index as the adj index
+ */
+ bfmi0 = vnet_buffer (b0)->ip.adj_index[VLIB_TX];
+ bfm0 = bier_fmask_get(bfmi0);
+
+ /*
+ * perform the logical AND of the packet's mask with
+ * that of the fmask objects, to reset the bits that
+ * are only on the shortest path the the fmask NH.
+ */
+ bier_bit_string_logical_and_string(
+ &bfm0->bfm_bits.bfmb_input_reset_string,
+ &bbs);
+
+ /*
+ * this is the last time we touch the BIER header
+ * so flip to network order
+ */
+ bier_hdr_hton(bh0);
+
+ /*
+ * paint the BIER peer's label
+ */
+ if (!(bfm0->bfm_flags & BIER_FMASK_FLAG_DISP))
+ {
+ vlib_buffer_advance(b0, -(word)sizeof(mpls_label_t));
+ h0 = vlib_buffer_get_current(b0);
+ h0[0] = bfm0->bfm_label;
+ }
+
+ /*
+ * setup next graph node
+ */
+ next0 = bfm0->bfm_dpo.dpoi_next_node;
+ vnet_buffer(b0)->ip.adj_index[VLIB_TX] = bfm0->bfm_dpo.dpoi_index;
+
+ if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
+ {
+ bier_output_trace_t *tr;
+
+ tr = vlib_add_trace (vm, node, b0, sizeof (*tr));
+ tr->next_index = next0;
+ tr->bfm_index = bfmi0;
+ }
+
+ vlib_validate_buffer_enqueue_x1 (vm, node, next_index,
+ to_next, n_left_to_next,
+ bi0, next0);
+ }
+
+ vlib_put_next_frame (vm, node, next_index, n_left_to_next);
+ }
+
+ vlib_node_increment_counter (vm, bier_output_node.index,
+ BIER_OUTPUT_ERROR_NONE,
+ from_frame->n_vectors);
+ return (from_frame->n_vectors);
+}
+
+static u8 *
+format_bier_output_trace (u8 * s, va_list * args)
+{
+ CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
+ CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
+ bier_output_trace_t * t = va_arg (*args, bier_output_trace_t *);
+
+ s = format (s, " next [%d], BFM index %d",
+ t->next_index, t->bfm_index);
+ return s;
+}
+
+VLIB_REGISTER_NODE (bier_output_node) = {
+ .function = bier_output,
+ .name = "bier-output",
+ /* Takes a vector of packets. */
+ .vector_size = sizeof (u32),
+
+ .n_errors = BIER_OUTPUT_N_ERROR,
+ .error_strings = bier_output_error_strings,
+
+ .n_next_nodes = BIER_OUTPUT_N_NEXT,
+ .next_nodes = {
+ [BIER_OUTPUT_NEXT_DROP] = "bier-drop",
+ },
+
+ .format_trace = format_bier_output_trace,
+};
diff --git a/src/vnet/bier/bier_output_error.def b/src/vnet/bier/bier_output_error.def
new file mode 100644
index 00000000000..983c13c0c2d
--- /dev/null
+++ b/src/vnet/bier/bier_output_error.def
@@ -0,0 +1,17 @@
+/*
+ * 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.
+ */
+
+bier_error (NONE, "no error")
+bier_error (FMASK_UNRES, "fmask unresolved")
diff --git a/src/vnet/bier/bier_table.c b/src/vnet/bier/bier_table.c
new file mode 100644
index 00000000000..74a09910601
--- /dev/null
+++ b/src/vnet/bier/bier_table.c
@@ -0,0 +1,744 @@
+/*
+ * 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 <vppinfra/vec.h>
+
+#include <vnet/bier/bier_table.h>
+#include <vnet/bier/bier_entry.h>
+#include <vnet/bier/bier_update.h>
+#include <vnet/bier/bier_fmask_db.h>
+#include <vnet/bier/bier_fmask.h>
+
+#include <vnet/fib/mpls_fib.h>
+#include <vnet/mpls/mpls.h>
+#include <vnet/fib/fib_path_list.h>
+
+/**
+ * Memory pool of all the allocated tables
+ */
+bier_table_t *bier_table_pool;
+
+/**
+ * DB store of all BIER tables index by SD/set/hdr-len
+ */
+static uword *bier_tables_by_key;
+
+/**
+ * The magic number of BIER ECMP tables to create.
+ * The load-balance distribution algorithm will use a power of 2
+ * for the number of buckets, which constrains the choice.
+ */
+#define BIER_N_ECMP_TABLES 16
+
+static inline index_t
+bier_table_get_index (const bier_table_t *bt)
+{
+ return (bt - bier_table_pool);
+}
+
+int
+bier_table_is_main (const bier_table_t *bt)
+{
+ return (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp);
+}
+
+/*
+ * Construct the key to use to find a BIER table
+ * in the global hash map
+ */
+static u32
+bier_table_mk_key (const bier_table_id_t *id)
+{
+ /*
+ * the set and sub-domain Ids are 8 bit values.
+ * we have space for ECMP table ID and talbe type (SPF/TE)
+ * for later
+ */
+ u32 key = ((id->bti_sub_domain << 24) |
+ (id->bti_set << 16) |
+ (id->bti_ecmp << 8) |
+ (id->bti_hdr_len << 4) |
+ (id->bti_type));
+
+ return (key);
+}
+
+static void
+bier_table_init (bier_table_t *bt,
+ const bier_table_id_t *id,
+ mpls_label_t ll)
+{
+ u32 num_entries;
+
+ bt->bt_lfei = FIB_NODE_INDEX_INVALID;
+ bt->bt_id = *id;
+ bt->bt_ll = ll;
+ num_entries = bier_hdr_len_id_to_num_bits(bt->bt_id.bti_hdr_len);
+
+ /*
+ * create the lookup table of entries.
+ */
+ if (bier_table_is_main(bt))
+ {
+ vec_validate_init_empty_aligned(bt->bt_entries,
+ num_entries,
+ INDEX_INVALID,
+ CLIB_CACHE_LINE_BYTES);
+ fib_table_find_or_create_and_lock(FIB_PROTOCOL_MPLS,
+ MPLS_FIB_DEFAULT_TABLE_ID,
+ FIB_SOURCE_BIER);
+ }
+ else
+ {
+ vec_validate_init_empty_aligned(bt->bt_fmasks,
+ num_entries,
+ INDEX_INVALID,
+ CLIB_CACHE_LINE_BYTES);
+ }
+}
+
+static void
+bier_table_rm_lfib (bier_table_t *bt)
+{
+ if (FIB_NODE_INDEX_INVALID != bt->bt_lfei)
+ {
+ fib_table_entry_delete_index(bt->bt_lfei,
+ FIB_SOURCE_BIER);
+ }
+ bt->bt_lfei = FIB_NODE_INDEX_INVALID;
+}
+
+static void
+bier_table_destroy (bier_table_t *bt)
+{
+ if (bier_table_is_main(bt))
+ {
+ index_t *bei;
+
+ fib_path_list_unlock(bt->bt_pl);
+ bt->bt_pl = FIB_NODE_INDEX_INVALID;
+ /*
+ * unresolve/remove all entries from the table
+ */
+ vec_foreach (bei, bt->bt_entries)
+ {
+ if (INDEX_INVALID != *bei)
+ {
+ bier_entry_delete(*bei);
+ }
+ }
+ vec_free (bt->bt_entries);
+ fib_table_unlock(fib_table_find(FIB_PROTOCOL_MPLS,
+ MPLS_FIB_DEFAULT_TABLE_ID),
+ FIB_PROTOCOL_MPLS,
+ FIB_SOURCE_BIER);
+ }
+ else
+ {
+ index_t *bfmi;
+
+ /*
+ * unlock any fmasks
+ */
+ vec_foreach (bfmi, bt->bt_fmasks)
+ {
+ bier_fmask_unlock(*bfmi);
+ }
+ vec_free(bt->bt_fmasks);
+ }
+
+ hash_unset(bier_tables_by_key,
+ bier_table_mk_key(&bt->bt_id));
+ pool_put(bier_table_pool, bt);
+}
+
+static void
+bier_table_lock_i (bier_table_t *bt)
+{
+ bt->bt_locks++;
+}
+
+static void
+bier_table_unlock_i (bier_table_t *bt)
+{
+ bt->bt_locks--;
+
+ if (0 == bt->bt_locks)
+ {
+ bier_table_rm_lfib(bt);
+ bier_table_destroy(bt);
+ }
+}
+
+void
+bier_table_unlock (const bier_table_id_t *bti)
+{
+ uword *p;
+ u32 key;
+
+ key = bier_table_mk_key(bti);
+
+ p = hash_get (bier_tables_by_key, key);
+
+ if (NULL != p) {
+ bier_table_unlock_i(bier_table_get(p[0]));
+ }
+}
+
+static void
+bier_table_mk_lfib (bier_table_t *bt)
+{
+ /*
+ * Add a new MPLS lfib entry
+ */
+ if (MPLS_LABEL_INVALID != bt->bt_ll) {
+ fib_prefix_t pfx = {
+ .fp_proto = FIB_PROTOCOL_MPLS,
+ .fp_len = 21,
+ .fp_label = bt->bt_ll,
+ .fp_eos = MPLS_EOS,
+ .fp_payload_proto = DPO_PROTO_BIER,
+ };
+ u32 mpls_fib_index;
+ dpo_id_t dpo = DPO_INVALID;
+
+ /*
+ * stack the entry on the forwarding chain prodcued by the
+ * path-list via the ECMP tables.
+ */
+ fib_path_list_contribute_forwarding(bt->bt_pl,
+ FIB_FORW_CHAIN_TYPE_BIER,
+ &dpo);
+
+ mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
+ MPLS_FIB_DEFAULT_TABLE_ID);
+ bt->bt_lfei = fib_table_entry_special_dpo_add(mpls_fib_index,
+ &pfx,
+ FIB_SOURCE_BIER,
+ FIB_ENTRY_FLAG_EXCLUSIVE,
+ &dpo);
+ dpo_reset(&dpo);
+ }
+}
+
+static bier_table_t *
+bier_table_find (const bier_table_id_t *bti)
+{
+ uword *p;
+ u32 key;
+
+ key = bier_table_mk_key(bti);
+
+ p = hash_get(bier_tables_by_key, key);
+
+ if (NULL != p)
+ {
+ return (bier_table_get(p[0]));
+ }
+
+ return (NULL);
+}
+
+static bier_table_t *
+bier_table_mk_ecmp (index_t bti)
+{
+ fib_route_path_t *rpaths;
+ fib_node_index_t pli;
+ bier_table_t *bt;
+ int ii;
+
+ rpaths = NULL;
+ bt = bier_table_get(bti);
+
+ vec_validate(rpaths, BIER_N_ECMP_TABLES-1);
+
+ vec_foreach_index(ii, rpaths)
+ {
+ rpaths[ii].frp_bier_tbl = bt->bt_id;
+ rpaths[ii].frp_bier_tbl.bti_ecmp = ii;
+ rpaths[ii].frp_flags = FIB_ROUTE_PATH_BIER_TABLE;
+ }
+
+ /*
+ * no oppotunity to share, this the resolving ECMP tables are unique
+ * to this table.
+ * no need to be a child of the path list, we can do nothing with any
+ * notifications it would generate [not that it will].
+ */
+ pli = fib_path_list_create(FIB_PATH_LIST_FLAG_NO_URPF, rpaths);
+ fib_path_list_lock(pli);
+
+ /*
+ * constructing the path-list will have created many more BIER tables,
+ * so this main table will no doubt have re-alloc.
+ */
+ bt = bier_table_get(bti);
+ bt->bt_pl = pli;
+
+ vec_free(rpaths);
+
+ return (bt);
+}
+
+index_t
+bier_table_add_or_lock (const bier_table_id_t *btid,
+ mpls_label_t local_label)
+{
+ bier_table_t *bt;
+ index_t bti;
+
+ bt = bier_table_find(btid);
+
+ if (NULL != bt) {
+ /*
+ * modify an existing table.
+ * change the lfib entry to the new local label
+ */
+ if (bier_table_is_main(bt) &&
+ (local_label != MPLS_LABEL_INVALID))
+ {
+ bier_table_rm_lfib(bt);
+
+ bt->bt_ll = local_label;
+ bier_table_mk_lfib(bt);
+ }
+ bti = bier_table_get_index(bt);
+ }
+ else
+ {
+ /*
+ * add a new table
+ */
+ u32 key;
+
+ key = bier_table_mk_key(btid);
+
+ pool_get_aligned(bier_table_pool, bt, CLIB_CACHE_LINE_BYTES);
+ bier_table_init(bt, btid, local_label);
+
+ hash_set(bier_tables_by_key, key, bier_table_get_index(bt));
+ bti = bier_table_get_index(bt);
+
+ if (bier_table_is_main(bt))
+ {
+ bt = bier_table_mk_ecmp(bti);
+ bier_table_mk_lfib(bt);
+ }
+ }
+
+ bier_table_lock_i(bt);
+
+ return (bti);
+}
+
+index_t
+bier_table_ecmp_create_and_lock (const bier_table_id_t *btid)
+{
+ return (bier_table_add_or_lock(btid, MPLS_LABEL_INVALID));
+}
+
+void
+bier_table_ecmp_unlock (index_t bti)
+{
+ bier_table_unlock_i(bier_table_get(bti));
+}
+
+static void
+bier_table_dpo_lock (dpo_id_t *dpo)
+{
+}
+
+static void
+bier_table_dpo_unlock (dpo_id_t *dpo)
+{
+}
+
+static void
+bier_table_dpo_mem_show (void)
+{
+ fib_show_memory_usage("BIER-table",
+ pool_elts(bier_table_pool),
+ pool_len(bier_table_pool),
+ sizeof(bier_table_t));
+}
+static u8 *
+format_bier_table_dpo (u8 *s, va_list *ap)
+{
+ index_t bti = va_arg(*ap, index_t);
+ bier_table_t *bt;
+
+ bt = bier_table_get(bti);
+
+ return (format(s, "[%U]", format_bier_table_id, &bt->bt_id));
+}
+
+const static dpo_vft_t bier_table_dpo_vft = {
+ .dv_lock = bier_table_dpo_lock,
+ .dv_unlock = bier_table_dpo_unlock,
+ .dv_format = format_bier_table_dpo,
+ .dv_mem_show = bier_table_dpo_mem_show,
+};
+
+const static char *const bier_table_mpls_nodes[] =
+{
+ "bier-input"
+};
+const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
+{
+ [DPO_PROTO_BIER] = bier_table_mpls_nodes,
+};
+
+static clib_error_t *
+bier_table_module_init (vlib_main_t *vm)
+{
+ dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
+
+ return (NULL);
+}
+
+VLIB_INIT_FUNCTION (bier_table_module_init);
+
+const bier_table_id_t *
+bier_table_get_id (index_t bti)
+{
+ bier_table_t *bt;
+
+ bt = bier_table_get(bti);
+
+ return (&bt->bt_id);
+}
+
+static void
+bier_table_insert (bier_table_t *bt,
+ bier_bp_t bp,
+ index_t bei)
+{
+ bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
+}
+
+static void
+bier_table_remove (bier_table_t *bt,
+ bier_bp_t bp)
+{
+ bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
+}
+
+void
+bier_table_route_add (const bier_table_id_t *btid,
+ bier_bp_t bp,
+ fib_route_path_t *brps)
+{
+ index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
+ fib_route_path_t *brp;
+ bier_table_t *bt;
+
+ bt = bier_table_find(btid);
+
+ if (NULL == bt) {
+ return;
+ }
+
+ bti = bier_table_get_index(bt);
+ bei = bier_table_lookup(bt, bp);
+
+ /*
+ * set the FIB index in the path to the BIER table index
+ */
+ vec_foreach(brp, brps)
+ {
+ bier_fmask_id_t fmid = {
+ .bfmi_nh = brp->frp_addr,
+ .bfmi_hdr_type = BIER_HDR_O_MPLS,
+ };
+ bfmi = bier_fmask_db_find_or_create_and_lock(bier_table_get_index(bt),
+ &fmid,
+ brp);
+
+ brp->frp_bier_fib_index = bti;
+ vec_add1(bfmis, bfmi);
+ }
+
+ if (INDEX_INVALID == bei)
+ {
+ bei = bier_entry_create(bti, bp);
+ bier_table_insert(bt, bp, bei);
+ }
+ bier_entry_path_add(bei, brps);
+
+ vec_foreach(bfmip, bfmis)
+ {
+ bier_fmask_unlock(*bfmip);
+ }
+ vec_free(bfmis);
+}
+
+void
+bier_table_route_remove (const bier_table_id_t *bti,
+ bier_bp_t bp,
+ fib_route_path_t *brps)
+{
+ fib_route_path_t *brp = NULL;
+ bier_table_t *bt;
+ index_t bei;
+
+ bt = bier_table_find(bti);
+
+ if (NULL == bt) {
+ return;
+ }
+
+ bei = bier_table_lookup(bt, bp);
+
+ if (INDEX_INVALID == bei)
+ {
+ /* no such entry */
+ return;
+ }
+
+ vec_foreach(brp, brps)
+ {
+ brp->frp_bier_fib_index = bier_table_get_index(bt);
+ }
+
+ if (0 == bier_entry_path_remove(bei, brps))
+ {
+ /* 0 remaining paths */
+ bier_table_remove(bt, bp);
+ bier_entry_delete(bei);
+ }
+}
+
+void
+bier_table_contribute_forwarding (index_t bti,
+ dpo_id_t *dpo)
+{
+ bier_table_t *bt;
+
+ bt = bier_table_get(bti);
+
+ if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
+ {
+ /*
+ * return the load-balance for the ECMP tables
+ */
+ fib_path_list_contribute_forwarding(bt->bt_pl,
+ FIB_FORW_CHAIN_TYPE_BIER,
+ dpo);
+ }
+ else
+ {
+ dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
+ }
+}
+
+typedef struct bier_table_ecmp_walk_ctx_t_
+{
+ bier_table_ecmp_walk_fn_t fn;
+ void *ctx;
+} bier_table_ecmp_walk_ctx_t;
+
+static fib_path_list_walk_rc_t
+bier_table_ecmp_walk_path_list (fib_node_index_t pl_index,
+ fib_node_index_t path_index,
+ void *arg)
+{
+ bier_table_ecmp_walk_ctx_t *ctx = arg;
+
+ ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
+ /* continue */
+ return (FIB_PATH_LIST_WALK_CONTINUE);
+}
+
+void
+bier_table_ecmp_walk (index_t bti,
+ bier_table_ecmp_walk_fn_t fn,
+ void *ctx)
+{
+ bier_table_ecmp_walk_ctx_t ewc = {
+ .fn = fn,
+ .ctx = ctx,
+ };
+ bier_table_t *bt;
+
+ bt = bier_table_get(bti);
+
+ fib_path_list_walk(bt->bt_pl,
+ bier_table_ecmp_walk_path_list,
+ &ewc);
+}
+
+void
+bier_table_ecmp_set_fmask (index_t bti,
+ bier_bp_t bp,
+ index_t bfmi)
+{
+ bier_table_t *bt;
+
+ bt = bier_table_get(bti);
+
+ /*
+ * we hold a lock for fmasks in the table
+ */
+ bier_fmask_lock(bfmi);
+ bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
+
+ bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
+}
+
+u8 *
+format_bier_table_entry (u8 *s, va_list *ap)
+{
+ index_t bti = va_arg(*ap, index_t);
+ bier_bp_t bp = va_arg(*ap, bier_bp_t);
+ bier_table_t *bt;
+ bt = bier_table_get(bti);
+
+ if (bier_table_is_main(bt))
+ {
+ index_t bei;
+
+ bei = bier_table_lookup(bier_table_get(bti), bp);
+
+ if (INDEX_INVALID != bei)
+ {
+ s = format(s, "%U", format_bier_entry, bei,
+ BIER_SHOW_DETAIL);
+ }
+ }
+ else
+ {
+ index_t bfmi;
+
+ bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
+
+ if (INDEX_INVALID != bfmi)
+ {
+ s = format(s, "%U", format_bier_fmask, bfmi,
+ BIER_SHOW_DETAIL);
+ }
+ }
+ return (s);
+}
+
+u8 *
+format_bier_table (u8 *s, va_list *ap)
+{
+ index_t bti = va_arg(*ap, index_t);
+ bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
+ bier_table_t *bt;
+
+ if (pool_is_free_index(bier_table_pool, bti))
+ {
+ return (format(s, "No BIER f-mask %d", bti));
+ }
+
+ bt = bier_table_get(bti);
+
+ s = format(s, "[@%d] bier-table:[%U local-label:%U]",
+ bti,
+ format_bier_table_id, &bt->bt_id,
+ format_mpls_unicast_label, bt->bt_ll);
+
+ if (flags & BIER_SHOW_DETAIL)
+ {
+ s = format(s, " locks:%d", bt->bt_locks);
+ }
+ s = format(s, "]");
+
+ if (flags & BIER_SHOW_DETAIL)
+ {
+ if (bier_table_is_main(bt))
+ {
+ index_t *bei;
+
+ vec_foreach (bei, bt->bt_entries)
+ {
+ if (INDEX_INVALID != *bei)
+ {
+ s = format(s, "\n%U", format_bier_entry, *bei, 2);
+ }
+ }
+ }
+ else
+ {
+ u32 ii;
+
+ vec_foreach_index (ii, bt->bt_fmasks)
+ {
+ if (INDEX_INVALID != bt->bt_fmasks[ii])
+ {
+ s = format(s, "\n bp:%d\n %U", ii,
+ format_bier_fmask, bt->bt_fmasks[ii], 2);
+ }
+ }
+ }
+ }
+
+ return (s);
+}
+
+void
+bier_table_show_all (vlib_main_t * vm,
+ bier_show_flags_t flags)
+{
+ if (!pool_elts(bier_table_pool))
+ {
+ vlib_cli_output (vm, "No BIER tables");
+ }
+ else
+ {
+ int ii;
+
+ pool_foreach_index(ii, bier_table_pool,
+ ({
+ vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
+ }));
+ }
+}
+
+void
+bier_tables_walk (bier_tables_walk_fn_t fn,
+ void *ctx)
+{
+ ASSERT(0);
+}
+
+
+void
+bier_table_walk (const bier_table_id_t *bti,
+ bier_table_walk_fn_t fn,
+ void *ctx)
+{
+ bier_table_t *bt;
+ bier_entry_t *be;
+ index_t *bei;
+
+ bt = bier_table_find(bti);
+
+ if (NULL == bt)
+ {
+ return;
+ }
+
+ vec_foreach (bei, bt->bt_entries)
+ {
+ if (INDEX_INVALID != *bei)
+ {
+ be = bier_entry_get(*bei);
+
+ fn(bt, be, ctx);
+ }
+ }
+}
diff --git a/src/vnet/bier/bier_table.h b/src/vnet/bier/bier_table.h
new file mode 100644
index 00000000000..a22e2e335b2
--- /dev/null
+++ b/src/vnet/bier/bier_table.h
@@ -0,0 +1,172 @@
+/*
+ * 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.
+ */
+
+#ifndef __BIER_TABLE_H__
+#define __BIER_TABLE_H__
+
+#include <vlib/vlib.h>
+#include <vnet/fib/fib_types.h>
+#include <vnet/bier/bier_types.h>
+#include <vnet/bier/bier_entry.h>
+
+#include <vnet/dpo/dpo.h>
+
+/**
+ * Forward declarations
+ */
+struct bier_route_update_t_;
+
+/**
+ * A BIER Table is the bit-indexed forwarding table.
+ * Each entry (bit-position) represents one destination, and its reachability
+ *
+ * The number of entries in a table is thus the maximum supported
+ * bit-position. Since this is smal <4096, the table is a flat arry
+ */
+typedef struct bier_table_t_ {
+ /**
+ * Save the MPLS local label associated with the table
+ */
+ mpls_label_t bt_ll;
+
+ /**
+ * The path-list used for the ECMP-tables
+ */
+ fib_node_index_t bt_pl;
+
+ /**
+ * The index of the lfib entry created for this table.
+ * Only the EOS is required.
+ */
+ fib_node_index_t bt_lfei;
+
+ /**
+ * Number of locks on the table
+ */
+ u16 bt_locks;
+
+ /**
+ * Entries in the table
+ * This is a vector sized to the appropriate number of entries
+ * given the table's supported Bit-string length
+ */
+ index_t *bt_entries;
+
+ /**
+ * Everything before this declaration is unused in the switch path
+ */
+ CLIB_CACHE_LINE_ALIGN_MARK(cacheline0);
+
+ /**
+ * The identity/key or the table. we need the hdr_len in the data-path
+ */
+ bier_table_id_t bt_id;
+
+ /**
+ * f-masks in the ECMP table
+ * This is a vector sized to the appropriate number of entries
+ * given the table's supported Bit-string length.
+ * In the ECMP table the LB choice has been pre-resolved, so each entry
+ * links to just one f-mask, i.e. there is a 1:1 mapping of bit-position to
+ * fmask. For efficient forwarding we collapse the fmasks up to the table.
+ */
+ index_t *bt_fmasks;
+} bier_table_t;
+
+STATIC_ASSERT((sizeof(bier_table_t) <= 2*CLIB_CACHE_LINE_BYTES),
+ "BIER table fits on 2 cache lines");
+
+extern index_t bier_table_add_or_lock(const bier_table_id_t *id,
+ mpls_label_t ll);
+extern void bier_table_unlock(const bier_table_id_t *id);
+
+extern void bier_table_route_add(const bier_table_id_t *bti,
+ bier_bp_t bp,
+ fib_route_path_t *brp);
+extern void bier_table_route_remove(const bier_table_id_t *bti,
+ bier_bp_t bp,
+ fib_route_path_t *brp);
+
+extern void bier_table_show_all(vlib_main_t * vm,
+ bier_show_flags_t flags);
+
+extern const bier_table_id_t *bier_table_get_id(index_t bti);
+
+extern u8 *format_bier_table (u8 *s, va_list *args);
+extern u8 *format_bier_table_entry (u8 *s, va_list *args);
+
+extern index_t bier_table_ecmp_create_and_lock(const bier_table_id_t *id);
+extern void bier_table_ecmp_unlock(index_t bti);
+extern void bier_table_ecmp_set_fmask(index_t bti,
+ bier_bp_t bp,
+ index_t bfmi);
+
+extern void bier_table_contribute_forwarding(index_t bti,
+ dpo_id_t *dpo);
+
+/**
+ * Types and functions to walk the ECMP tables of a main table
+ */
+typedef void (*bier_table_ecmp_walk_fn_t)(index_t btei,
+ void *ctx);
+extern void bier_table_ecmp_walk(index_t bti,
+ bier_table_ecmp_walk_fn_t fn,
+ void *ctx);
+extern int bier_table_is_main (const bier_table_t *bt);
+
+/**
+ * Types and functions to walk all the BIER Tables
+ */
+typedef void (*bier_tables_walk_fn_t)(const bier_table_t *bt,
+ void *ctx);
+extern void bier_tables_walk(bier_tables_walk_fn_t fn,
+ void *ctx);
+
+/**
+ * Types and functions to walk all the entries in one BIER Table
+ */
+typedef void (*bier_table_walk_fn_t)(const bier_table_t *bt,
+ const bier_entry_t *be,
+ void *ctx);
+extern void bier_table_walk(const bier_table_id_t *id,
+ bier_table_walk_fn_t fn,
+ void *ctx);
+
+/*
+ * provided for fast data plane access.
+ */
+extern bier_table_t *bier_table_pool;
+
+static inline bier_table_t *
+bier_table_get (index_t bti)
+{
+ return (pool_elt_at_index(bier_table_pool, bti));
+}
+
+static inline const index_t
+bier_table_lookup (const bier_table_t *bt,
+ bier_bp_t bp)
+{
+ return (bt->bt_entries[BIER_BP_TO_INDEX(bp)]);
+}
+
+static inline const index_t
+bier_table_fwd_lookup (const bier_table_t *bt,
+ bier_bp_t bp)
+{
+ return (bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
+}
+
+#endif
diff --git a/src/vnet/bier/bier_test.c b/src/vnet/bier/bier_test.c
new file mode 100644
index 00000000000..6119410edfa
--- /dev/null
+++ b/src/vnet/bier/bier_test.c
@@ -0,0 +1,951 @@
+/*
+ * 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/bier/bier_table.h>
+#include <vnet/bier/bier_entry.h>
+#include <vnet/bier/bier_fmask.h>
+#include <vnet/bier/bier_bit_string.h>
+#include <vnet/bier/bier_imp.h>
+#include <vnet/bier/bier_disp_table.h>
+#include <vnet/bier/bier_disp_entry.h>
+#include <vnet/fib/fib_entry.h>
+#include <vnet/fib/fib_table.h>
+#include <vnet/fib/mpls_fib.h>
+#include <vnet/dpo/load_balance.h>
+#include <vnet/dpo/drop_dpo.h>
+#include <vnet/dpo/lookup_dpo.h>
+#include <vnet/mfib/mfib_table.h>
+
+#include <vnet/fib/fib_test.h>
+
+/*
+ * Add debugs for passing tests
+ */
+static int bier_test_do_debug;
+
+#define BIER_TEST_I(_cond, _comment, _args...) \
+({ \
+ int _evald = (_cond); \
+ if (!(_evald)) { \
+ fformat(stderr, "FAIL:%d: " _comment "\n", \
+ __LINE__, ##_args); \
+ } else { \
+ if (bier_test_do_debug) \
+ fformat(stderr, "PASS:%d: " _comment "\n", \
+ __LINE__, ##_args); \
+ } \
+ _evald; \
+})
+#define BIER_TEST(_cond, _comment, _args...) \
+{ \
+ if (!BIER_TEST_I(_cond, _comment, ##_args)) { \
+ return 1; \
+ ASSERT(!("FAIL: " _comment)); \
+ } \
+}
+
+/**
+ * A 'i'm not fussed is this is not efficient' store of test data
+ */
+typedef struct test_main_t_ {
+ /**
+ * HW if indicies
+ */
+ u32 hw_if_indicies[4];
+ /**
+ * HW interfaces
+ */
+ vnet_hw_interface_t * hw[4];
+
+} test_main_t;
+static test_main_t test_main;
+
+/* fake ethernet device class, distinct from "fake-ethX" */
+static u8 * format_test_interface_name (u8 * s, va_list * args)
+{
+ u32 dev_instance = va_arg (*args, u32);
+ return format (s, "test-eth%d", dev_instance);
+}
+
+static uword dummy_interface_tx (vlib_main_t * vm,
+ vlib_node_runtime_t * node,
+ vlib_frame_t * frame)
+{
+ clib_warning ("you shouldn't be here, leaking buffers...");
+ return frame->n_vectors;
+}
+
+VNET_DEVICE_CLASS (test_interface_device_class,static) = {
+ .name = "Test interface",
+ .format_device_name = format_test_interface_name,
+ .tx_function = dummy_interface_tx,
+};
+
+static u8 *hw_address;
+
+static int
+bier_test_mk_intf (u32 ninterfaces)
+{
+ clib_error_t * error = NULL;
+ test_main_t *tm = &test_main;
+ u8 byte;
+ u32 i;
+
+ ASSERT(ninterfaces <= ARRAY_LEN(tm->hw_if_indicies));
+
+ for (i=0; i<6; i++)
+ {
+ byte = 0xd0+i;
+ vec_add1(hw_address, byte);
+ }
+
+ for (i = 0; i < ninterfaces; i++)
+ {
+ hw_address[5] = i;
+
+ error = ethernet_register_interface(vnet_get_main(),
+ test_interface_device_class.index,
+ i /* instance */,
+ hw_address,
+ &tm->hw_if_indicies[i],
+ /* flag change */ 0);
+
+ BIER_TEST((NULL == error), "ADD interface %d", i);
+
+ tm->hw[i] = vnet_get_hw_interface(vnet_get_main(),
+ tm->hw_if_indicies[i]);
+ vec_validate (ip4_main.fib_index_by_sw_if_index, tm->hw[i]->sw_if_index);
+ vec_validate (ip6_main.fib_index_by_sw_if_index, tm->hw[i]->sw_if_index);
+ ip4_main.fib_index_by_sw_if_index[tm->hw[i]->sw_if_index] = 0;
+ ip6_main.fib_index_by_sw_if_index[tm->hw[i]->sw_if_index] = 0;
+ error = vnet_sw_interface_set_flags(vnet_get_main(),
+ tm->hw[i]->sw_if_index,
+ VNET_SW_INTERFACE_FLAG_ADMIN_UP);
+ BIER_TEST((NULL == error), "UP interface %d", i);
+ }
+ /*
+ * re-eval after the inevitable realloc
+ */
+ for (i = 0; i < ninterfaces; i++)
+ {
+ tm->hw[i] = vnet_get_hw_interface(vnet_get_main(),
+ tm->hw_if_indicies[i]);
+ }
+
+ return (0);
+}
+
+#define BIER_TEST_LB(_cond, _comment, _args...) \
+{ \
+ if (!BIER_TEST_I(_cond, _comment, ##_args)) { \
+ return (0); \
+ } \
+}
+
+static int
+bier_test_validate_entry (index_t bei,
+ u16 n_buckets,
+ ...)
+{
+ dpo_id_t dpo = DPO_INVALID;
+ const load_balance_t *lb;
+ va_list ap;
+ int res;
+
+ va_start(ap, n_buckets);
+
+ bier_entry_contribute_forwarding(bei, &dpo);
+
+ BIER_TEST_LB((DPO_LOAD_BALANCE == dpo.dpoi_type),
+ "Entry links to %U",
+ format_dpo_type, dpo.dpoi_type);
+
+ lb = load_balance_get(dpo.dpoi_index);
+ res = fib_test_validate_lb_v(lb, n_buckets, &ap);
+
+ dpo_reset(&dpo);
+
+ va_end(ap);
+
+ return (res);
+}
+
+static int
+bier_test_mpls_spf (void)
+{
+ fib_node_index_t lfei, fei, bti;
+ u32 mpls_fib_index;
+ test_main_t *tm;
+ int lb_count;
+
+ lb_count = pool_elts(load_balance_pool);
+ tm = &test_main;
+#define N_BIER_ECMP_TABLES 16
+ int ii;
+
+ /*
+ * Add the BIER Main table
+ */
+ const bier_table_id_t bt_0_0_0_256 = {
+ .bti_set = 0,
+ .bti_sub_domain = 0,
+ .bti_hdr_len = BIER_HDR_LEN_256,
+ .bti_type = BIER_TABLE_MPLS_SPF,
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+
+ bti = bier_table_add_or_lock(&bt_0_0_0_256, 1600);
+
+ fib_test_lb_bucket_t l_o_bt[N_BIER_ECMP_TABLES];
+ bier_table_id_t bt_ecmp_0_0_0_256 = bt_0_0_0_256;
+
+ for (ii = 0; ii < N_BIER_ECMP_TABLES; ii++)
+ {
+ bt_ecmp_0_0_0_256.bti_ecmp = ii;
+
+ l_o_bt[ii].type = FT_LB_BIER_TABLE;
+ l_o_bt[ii].bier.table =
+ bier_table_ecmp_create_and_lock(&bt_ecmp_0_0_0_256);
+ };
+ const fib_prefix_t pfx_1600_neos = {
+ .fp_len = 21,
+ .fp_proto = FIB_PROTOCOL_MPLS,
+ .fp_label = 1600,
+ .fp_eos = MPLS_NON_EOS,
+ .fp_payload_proto = DPO_PROTO_BIER,
+ };
+ const fib_prefix_t pfx_1600_eos = {
+ .fp_len = 21,
+ .fp_proto = FIB_PROTOCOL_MPLS,
+ .fp_label = 1600,
+ .fp_eos = MPLS_EOS,
+ .fp_payload_proto = DPO_PROTO_BIER,
+ };
+
+ mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
+ MPLS_FIB_DEFAULT_TABLE_ID);
+
+ lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_neos);
+ BIER_TEST(FIB_NODE_INDEX_INVALID == lfei, "1600/0 is not present");
+
+ lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_eos);
+ BIER_TEST(fib_test_validate_entry(lfei, FIB_FORW_CHAIN_TYPE_MPLS_EOS,
+ 16,
+ &l_o_bt[0],
+ &l_o_bt[1],
+ &l_o_bt[2],
+ &l_o_bt[3],
+ &l_o_bt[4],
+ &l_o_bt[5],
+ &l_o_bt[6],
+ &l_o_bt[7],
+ &l_o_bt[8],
+ &l_o_bt[9],
+ &l_o_bt[10],
+ &l_o_bt[11],
+ &l_o_bt[12],
+ &l_o_bt[13],
+ &l_o_bt[14],
+ &l_o_bt[15]),
+ "1600/1 LB stacks on BIER table %d", bti);
+
+ /*
+ * modify the table's local label - keep the lock count accurate
+ */
+ const fib_prefix_t pfx_1601_eos = {
+ .fp_len = 21,
+ .fp_proto = FIB_PROTOCOL_MPLS,
+ .fp_label = 1601,
+ .fp_eos = MPLS_EOS,
+ .fp_payload_proto = DPO_PROTO_BIER,
+ };
+ bti = bier_table_add_or_lock(&bt_0_0_0_256, 1601);
+ bier_table_unlock(&bt_0_0_0_256);
+
+ lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_eos);
+ BIER_TEST(FIB_NODE_INDEX_INVALID == lfei, "1600/1 is deleted");
+
+ lfei = fib_table_lookup(mpls_fib_index, &pfx_1601_eos);
+ BIER_TEST(fib_test_validate_entry(lfei, FIB_FORW_CHAIN_TYPE_MPLS_EOS,
+ 16,
+ &l_o_bt[0],
+ &l_o_bt[1],
+ &l_o_bt[2],
+ &l_o_bt[3],
+ &l_o_bt[4],
+ &l_o_bt[5],
+ &l_o_bt[6],
+ &l_o_bt[7],
+ &l_o_bt[8],
+ &l_o_bt[9],
+ &l_o_bt[10],
+ &l_o_bt[11],
+ &l_o_bt[12],
+ &l_o_bt[13],
+ &l_o_bt[14],
+ &l_o_bt[15]),
+ "1601/1 LB stacks on BIER table %d", bti);
+
+ /*
+ * add a route to the table. the via IP route does not exist.
+ */
+ const ip46_address_t nh_1_1_1_1 = {
+ .ip4 = {
+ .as_u32 = clib_host_to_net_u32(0x01010101),
+ },
+ };
+ fib_route_path_t *paths_1_1_1_1 = NULL;
+ fib_route_path_t path_1_1_1_1 = {
+ .frp_addr = nh_1_1_1_1,
+ .frp_bier_fib_index = bti,
+ .frp_flags = FIB_ROUTE_PATH_BIER_FMASK,
+ };
+ vec_add1(path_1_1_1_1.frp_label_stack, 500);
+ vec_add1(paths_1_1_1_1, path_1_1_1_1);
+ const fib_prefix_t pfx_1_1_1_1_s_32 = {
+ .fp_addr = nh_1_1_1_1,
+ .fp_len = 32,
+ .fp_proto = FIB_PROTOCOL_IP4,
+ };
+ const bier_fmask_id_t bfm_id_1_1_1_1 = {
+ .bfmi_hdr_type = BIER_HDR_O_MPLS,
+ .bfmi_nh = nh_1_1_1_1,
+ };
+ index_t bei_1;
+
+ bier_table_route_add(&bt_0_0_0_256, 1, paths_1_1_1_1);
+ bei_1 = bier_table_lookup(bier_table_get(bti), 1);
+
+ BIER_TEST((INDEX_INVALID != bei_1), "BP:1 present");
+
+ /*
+ * the newly created fmask should stack on the non-eos chain
+ * of the via-fib-entry
+ */
+ dpo_id_t neos_dpo_1_1_1_1 = DPO_INVALID;
+ bier_fmask_t *bfm_1_1_1_1;
+ index_t bfmi_1_1_1_1;
+
+ fei = fib_table_lookup_exact_match(0, &pfx_1_1_1_1_s_32);
+ fib_entry_contribute_forwarding(fei,
+ FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
+ &neos_dpo_1_1_1_1);
+
+ bfmi_1_1_1_1 = bier_fmask_db_find(bti, &bfm_id_1_1_1_1);
+ bfm_1_1_1_1 = bier_fmask_get(bfmi_1_1_1_1);
+
+ BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_1, &bfm_1_1_1_1->bfm_dpo),
+ "Fmask via 1.1.1.1 stacks on neos from 1.1.1.1/32");
+
+ /*
+ * and that n-eos LB at this stage is a drop..
+ */
+ const fib_test_lb_bucket_t bucket_drop = {
+ .type = FT_LB_DROP,
+ };
+ BIER_TEST(fib_test_validate_lb(&neos_dpo_1_1_1_1, 1, &bucket_drop),
+ "1.1.1.1/32 n-eos LB 1 buckets via: DROP");
+
+ /*
+ * The BIER entry should stack on the forwarding chain of the fmask
+ */
+ const fib_test_lb_bucket_t dpo_o_bfm_1_1_1_1 = {
+ .type = FT_LB_BIER_FMASK,
+ .bier = {
+ .fmask = bfmi_1_1_1_1,
+ },
+ };
+ BIER_TEST(bier_test_validate_entry(bei_1, 1, &bucket_drop),
+ "BP:1 stacks on bier drop");
+
+ /*
+ * give 1.1.1.1/32 a path and hence a interesting n-eos chain
+ */
+ ip46_address_t nh_10_10_10_1 = {
+ .ip4 = {
+ .as_u32 = clib_host_to_net_u32(0x0a0a0a01),
+ },
+ };
+ adj_index_t ai_mpls_10_10_10_1;
+ ai_mpls_10_10_10_1 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4,
+ VNET_LINK_MPLS,
+ &nh_10_10_10_1,
+ tm->hw[0]->sw_if_index);
+
+ fib_test_lb_bucket_t bucket_neos_99_via_10_10_10_1 = {
+ .type = FT_LB_LABEL_O_ADJ,
+ .label_o_adj = {
+ .label = 99,
+ .eos = MPLS_NON_EOS,
+ .adj = ai_mpls_10_10_10_1,
+ .ttl = 255,
+ },
+ };
+ mpls_label_t *out_lbl_99 = NULL;
+ vec_add1(out_lbl_99, 99);
+
+ fei = fib_table_entry_update_one_path(0,
+ &pfx_1_1_1_1_s_32,
+ FIB_SOURCE_API,
+ FIB_ENTRY_FLAG_NONE,
+ DPO_PROTO_IP4,
+ &nh_10_10_10_1,
+ tm->hw[0]->sw_if_index,
+ ~0, // invalid fib index
+ 1,
+ out_lbl_99,
+ FIB_ROUTE_PATH_FLAG_NONE);
+ fib_entry_contribute_forwarding(fei,
+ FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
+ &neos_dpo_1_1_1_1);
+ BIER_TEST(fib_test_validate_lb(&neos_dpo_1_1_1_1, 1,
+ &bucket_neos_99_via_10_10_10_1),
+ "1.1.1.1/32 n-eos LB 1 buckets via: 99 + 10.10.10.1");
+ BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_1,
+ &bfm_1_1_1_1->bfm_dpo),
+ "Fmask via 1.1.1.1 stacks on updated non-eos of 1.1.1.1/32");
+ BIER_TEST(bier_test_validate_entry(bei_1, 1, &dpo_o_bfm_1_1_1_1),
+ "BP:1 stacks on fmask 1.1.1.1");
+
+ /*
+ * add another path to the via entry.
+ * this makes the via-entry instantiate a new load-balance with
+ * 2 buckets. and the back-walk to the BIER entry will need to
+ * re-stack on it.
+ */
+ ip46_address_t nh_10_10_10_2 = {
+ .ip4 = {
+ .as_u32 = clib_host_to_net_u32(0x0a0a0a02),
+ },
+ };
+ adj_index_t ai_mpls_10_10_10_2;
+
+ ai_mpls_10_10_10_2 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4,
+ VNET_LINK_MPLS,
+ &nh_10_10_10_2,
+ tm->hw[0]->sw_if_index);
+
+ fib_test_lb_bucket_t bucket_neos_100_via_10_10_10_2 = {
+ .type = FT_LB_LABEL_O_ADJ,
+ .label_o_adj = {
+ .label = 100,
+ .eos = MPLS_NON_EOS,
+ .adj = ai_mpls_10_10_10_2,
+ .ttl = 255,
+ },
+ };
+ mpls_label_t *out_lbl_100 = NULL;
+ vec_add1(out_lbl_100, 100);
+
+ fei = fib_table_entry_path_add(0,
+ &pfx_1_1_1_1_s_32,
+ FIB_SOURCE_API,
+ FIB_ENTRY_FLAG_NONE,
+ DPO_PROTO_IP4,
+ &nh_10_10_10_2,
+ tm->hw[0]->sw_if_index,
+ ~0, // invalid fib index
+ 1,
+ out_lbl_100,
+ FIB_ROUTE_PATH_FLAG_NONE);
+
+ fib_entry_contribute_forwarding(fei,
+ FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
+ &neos_dpo_1_1_1_1);
+ BIER_TEST(fib_test_validate_lb(&neos_dpo_1_1_1_1, 2,
+ &bucket_neos_99_via_10_10_10_1,
+ &bucket_neos_100_via_10_10_10_2),
+ "1.1.1.1/32 n-eos LB 2 buckets "
+ "via: 99 + 10.10.10.1, "
+ "via: 100 + 10.10.10.2");
+ BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_1,
+ &bfm_1_1_1_1->bfm_dpo),
+ "Fmask via 1.1.1.1 stacks on updated non-eos of 1.1.1.1/32");
+
+ /*
+ * add another bier bit-position via the same next-hop
+ * since its the same next hop, the two bit-positions should link
+ * to the same fmask
+ */
+ index_t bei_2;
+
+ bier_table_route_add(&bt_0_0_0_256, 2, paths_1_1_1_1);
+ bei_2 = bier_table_lookup(bier_table_get(bti), 2);
+
+ BIER_TEST(bier_test_validate_entry(bei_2, 1, &dpo_o_bfm_1_1_1_1),
+ "BP:2 stacks on fmask 1.1.1.1");
+
+ /*
+ * now add a bit-position via a different next hop and expect to
+ * link via a different fmask
+ */
+ const ip46_address_t nh_1_1_1_2 = {
+ .ip4 = {
+ .as_u32 = clib_host_to_net_u32(0x01010102),
+ },
+ };
+ const fib_prefix_t pfx_1_1_1_2_s_32 = {
+ .fp_addr = nh_1_1_1_2,
+ .fp_len = 32,
+ .fp_proto = FIB_PROTOCOL_IP4,
+ };
+ fib_route_path_t *paths_1_1_1_2 = NULL, path_1_1_1_2 = {
+ .frp_addr = nh_1_1_1_2,
+ .frp_bier_fib_index = bti,
+ .frp_flags = FIB_ROUTE_PATH_BIER_FMASK,
+ };
+ vec_add1(path_1_1_1_2.frp_label_stack, 501);
+ vec_add1(paths_1_1_1_2, path_1_1_1_2);
+ const bier_fmask_id_t bfm_id_1_1_1_2 = {
+ .bfmi_hdr_type = BIER_HDR_O_MPLS,
+ .bfmi_nh = nh_1_1_1_2,
+ };
+ index_t bei_3;
+
+ mpls_label_t *out_lbl_101 = NULL;
+ vec_add1(out_lbl_101, 101);
+ fei = fib_table_entry_path_add(0,
+ &pfx_1_1_1_2_s_32,
+ FIB_SOURCE_API,
+ FIB_ENTRY_FLAG_NONE,
+ DPO_PROTO_IP4,
+ &nh_10_10_10_2,
+ tm->hw[0]->sw_if_index,
+ ~0, // invalid fib index
+ 1,
+ out_lbl_101,
+ FIB_ROUTE_PATH_FLAG_NONE);
+ bier_table_route_add(&bt_0_0_0_256, 3, paths_1_1_1_2);
+ bei_3 = bier_table_lookup(bier_table_get(bti), 3);
+
+ BIER_TEST((INDEX_INVALID != bei_3), "BP:3 present");
+
+ /*
+ * the newly created fmask should stack on the non-eos chain
+ * of the via-fib-entry
+ */
+ dpo_id_t neos_dpo_1_1_1_2 = DPO_INVALID;
+ bier_fmask_t *bfm_1_1_1_2;
+ index_t bfmi_1_1_1_2;
+
+ fei = fib_table_lookup_exact_match(0, &pfx_1_1_1_2_s_32);
+ fib_entry_contribute_forwarding(fei,
+ FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
+ &neos_dpo_1_1_1_2);
+
+ bfmi_1_1_1_2 = bier_fmask_db_find(bti, &bfm_id_1_1_1_2);
+ bfm_1_1_1_2 = bier_fmask_get(bfmi_1_1_1_2);
+
+ BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_2,
+ &bfm_1_1_1_2->bfm_dpo),
+ "Fmask via 1.1.1.2 stacks on non-eos of 1.1.1.2/32");
+
+ /*
+ * The BIER entry should stack on the forwarding chain of the fmask
+ */
+ const fib_test_lb_bucket_t dpo_o_bfm_1_1_1_2 = {
+ .type = FT_LB_BIER_FMASK,
+ .bier = {
+ .fmask = bfmi_1_1_1_2,
+ },
+ };
+ BIER_TEST(bier_test_validate_entry(bei_3, 1, &dpo_o_bfm_1_1_1_2),
+ "BP:3 stacks on fmask 1.1.1.2");
+
+ /*
+ * Load-balance BP:3 over both next-hops
+ */
+ bier_table_route_add(&bt_0_0_0_256, 3, paths_1_1_1_1);
+
+ BIER_TEST(bier_test_validate_entry(bei_3, 2,
+ &dpo_o_bfm_1_1_1_1,
+ &dpo_o_bfm_1_1_1_2),
+ "BP:3 stacks on fmask 1.1.1.2 & 1.1.1.1");
+
+ /*
+ * test that the ECMP choices for BP:3 have been spread over the
+ * ECMP tables
+ */
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
+ bfmi_1_1_1_1),
+ "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
+ bfmi_1_1_1_2),
+ "fwd lookup for BP:3 ECMP:1 is 1.1.1.2");
+
+ /*
+ * Withdraw one of the via FIB and thus bring down the fmask
+ * expect the bier0entry forwarding to remove this from the set
+ */
+ fib_table_entry_delete(0, &pfx_1_1_1_2_s_32, FIB_SOURCE_API);
+
+ BIER_TEST(bier_test_validate_entry(bei_3, 1,
+ &dpo_o_bfm_1_1_1_1),
+ "BP:3 post 1.1.1.2 removal stacks on fmask 1.1.1.1");
+
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
+ bfmi_1_1_1_1),
+ "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
+ bfmi_1_1_1_1),
+ "fwd lookup for BP:3 ECMP:1 is 1.1.1.1");
+
+ /*
+ * add the via back
+ */
+ out_lbl_101 = NULL;
+ vec_add1(out_lbl_101, 101);
+ fei = fib_table_entry_path_add(0,
+ &pfx_1_1_1_2_s_32,
+ FIB_SOURCE_API,
+ FIB_ENTRY_FLAG_NONE,
+ DPO_PROTO_IP4,
+ &nh_10_10_10_2,
+ tm->hw[0]->sw_if_index,
+ ~0, // invalid fib index
+ 1,
+ out_lbl_101,
+ FIB_ROUTE_PATH_FLAG_NONE);
+ /* suspend so the update walk kicks int */
+ vlib_process_suspend(vlib_get_main(), 1e-5);
+
+ BIER_TEST(bier_test_validate_entry(bei_3, 2,
+ &dpo_o_bfm_1_1_1_1,
+ &dpo_o_bfm_1_1_1_2),
+ "BP:3 stacks on fmask 1.1.1.2 & 1.1.1.1");
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
+ bfmi_1_1_1_1),
+ "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
+ bfmi_1_1_1_2),
+ "fwd lookup for BP:3 ECMP:1 is 1.1.1.2");
+
+ /*
+ * remove the original 1.1.1.2 fmask from BP:3
+ */
+ bier_table_route_remove(&bt_0_0_0_256, 3, paths_1_1_1_2);
+ BIER_TEST(bier_test_validate_entry(bei_3, 1,
+ &dpo_o_bfm_1_1_1_1),
+ "BP:3 stacks on fmask 1.1.1.1");
+ /*
+ * test that the ECMP choices for BP:3 have been updated
+ */
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
+ bfmi_1_1_1_1),
+ "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
+ BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
+ bfmi_1_1_1_1),
+ "fwd lookup for BP:3 ECMP:1 is 1.1.1.1");
+
+ /*
+ * remove the routes added
+ */
+ bier_table_route_remove(&bt_0_0_0_256, 2, paths_1_1_1_1);
+ bier_table_route_remove(&bt_0_0_0_256, 3, paths_1_1_1_2);
+ bier_table_route_remove(&bt_0_0_0_256, 3, paths_1_1_1_1);
+ bier_table_route_remove(&bt_0_0_0_256, 1, paths_1_1_1_1);
+
+
+ /*
+ * delete the table
+ */
+ bier_table_unlock(&bt_0_0_0_256);
+
+ /*
+ * test resources are freed
+ */
+ for (ii = 0; ii < N_BIER_ECMP_TABLES; ii++)
+ {
+ bier_table_ecmp_unlock(l_o_bt[ii].bier.table);
+ };
+ BIER_TEST(0 == pool_elts(bier_table_pool), "BIER table pool empty");
+ BIER_TEST(0 == pool_elts(bier_fmask_pool), "BIER fmask pool empty");
+ BIER_TEST(0 == pool_elts(bier_entry_pool), "BIER entry pool empty");
+
+ adj_unlock(ai_mpls_10_10_10_1);
+ adj_unlock(ai_mpls_10_10_10_2);
+ dpo_reset(&neos_dpo_1_1_1_1);
+ dpo_reset(&neos_dpo_1_1_1_2);
+ fib_table_entry_delete(0, &pfx_1_1_1_1_s_32, FIB_SOURCE_API);
+ fib_table_entry_delete(0, &pfx_1_1_1_2_s_32, FIB_SOURCE_API);
+
+ /* +1 to account for the one time alloc'd drop LB in the MPLS fibs */
+ BIER_TEST(lb_count+1 == pool_elts(load_balance_pool),
+ "Load-balance resources freed ");
+ BIER_TEST((0 == adj_nbr_db_size()), "ADJ DB size is %d",
+ adj_nbr_db_size());
+
+ vec_free(paths_1_1_1_1);
+ vec_free(paths_1_1_1_2);
+
+ return (0);
+}
+
+static int
+bier_test_mpls_imp (void)
+{
+ fib_node_index_t bii;
+ /* test_main_t *tm; */
+
+ /* tm = &test_main; */
+
+ /*
+ * Add the BIER Main table
+ */
+ const bier_table_id_t bt_0_0_0_256 = {
+ .bti_set = 0,
+ .bti_sub_domain = 0,
+ .bti_hdr_len = BIER_HDR_LEN_256,
+ .bti_type = BIER_TABLE_MPLS_SPF,
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+
+ bier_table_add_or_lock(&bt_0_0_0_256, 1600);
+
+ /*
+ * A bit-string for imp 1.
+ */
+ bier_bit_string_t bbs_256;
+ u8 buckets[BIER_HDR_BUCKETS_256];
+ memset(buckets, 0x5, BIER_HDR_BUCKETS_256);
+
+ bier_bit_string_init(&bbs_256, BIER_HDR_LEN_256, buckets);
+
+ bii = bier_imp_add_or_lock(&bt_0_0_0_256, 1, &bbs_256);
+
+ /*
+ * An mfib entry that resolves via the BIER imposition
+ */
+ const mfib_prefix_t pfx_1_1_1_1_c_239_1_1_1 = {
+ .fp_len = 64,
+ .fp_proto = FIB_PROTOCOL_IP4,
+ .fp_grp_addr = {
+ .ip4.as_u32 = clib_host_to_net_u32(0xef010101),
+ },
+ .fp_src_addr = {
+ .ip4.as_u32 = clib_host_to_net_u32(0x01010101),
+ },
+ };
+ fib_route_path_t path_via_bier_imp_1 = {
+ .frp_proto = DPO_PROTO_BIER,
+ .frp_bier_imp = bii,
+ .frp_weight = 0,
+ .frp_flags = FIB_ROUTE_PATH_BIER_IMP,
+ };
+ mfib_table_entry_path_update(0, // default table
+ &pfx_1_1_1_1_c_239_1_1_1 ,
+ MFIB_SOURCE_API,
+ &path_via_bier_imp_1,
+ MFIB_ITF_FLAG_FORWARD);
+ mfib_table_entry_delete(0,
+ &pfx_1_1_1_1_c_239_1_1_1 ,
+ MFIB_SOURCE_API);
+
+ bier_imp_unlock(bii);
+ bier_table_unlock(&bt_0_0_0_256);
+
+ BIER_TEST(0 == pool_elts(bier_imp_pool),
+ "BIER imposition resources freed ");
+ BIER_TEST(0 == pool_elts(bier_table_pool),
+ "BIER table resources freed ");
+
+ return (0);
+}
+
+static int
+bier_test_mpls_disp (void)
+{
+ /* test_main_t *tm; */
+
+ /* tm = &test_main; */
+
+ /*
+ * Add the BIER Main table
+ */
+ const bier_table_id_t bt_0_0_0_256 = {
+ .bti_set = 0,
+ .bti_sub_domain = 0,
+ .bti_hdr_len = BIER_HDR_LEN_256,
+ .bti_type = BIER_TABLE_MPLS_SPF,
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+ index_t bti;
+
+ bti = bier_table_add_or_lock(&bt_0_0_0_256, 1600);
+
+ /*
+ * Add a BIER dispoition table
+ */
+ const u32 bier_disp_tbl_id = 1;
+ index_t bdti1;
+
+ bdti1 = bier_disp_table_add_or_lock(bier_disp_tbl_id);
+
+ /*
+ * add a bit-poistion in the table that resolves via
+ * DISP table, i.e. a for-us bit-position
+ */
+ fib_route_path_t *paths_via_disp = NULL, path_via_disp = {
+ // .frp_addr = all-zeros
+ .frp_bier_fib_index = bdti1,
+ .frp_flags = FIB_ROUTE_PATH_BIER_FMASK,
+ };
+ vec_add1(paths_via_disp, path_via_disp);
+
+ bier_table_route_add(&bt_0_0_0_256, 3, paths_via_disp);
+
+ /*
+ * the fmask should stack on the BIER disp table
+ */
+ const bier_fmask_id_t bfm_id_0_0_0_0 = {
+ .bfmi_hdr_type = BIER_HDR_O_MPLS,
+ };
+ bier_fmask_t *bfm_0_0_0_0;
+ index_t bfmi_0_0_0_0;
+ dpo_id_t dpo_disp_tbl_1 = DPO_INVALID;
+
+ bier_disp_table_contribute_forwarding(bdti1, &dpo_disp_tbl_1);
+
+ bfmi_0_0_0_0 = bier_fmask_db_find(bti, &bfm_id_0_0_0_0);
+ bfm_0_0_0_0 = bier_fmask_get(bfmi_0_0_0_0);
+
+ BIER_TEST(!dpo_cmp(&dpo_disp_tbl_1, &bfm_0_0_0_0->bfm_dpo),
+ "Fmask via 0.0.0.0 stacks on BIER disp table 1");
+
+ /*
+ * and a deag entry into the disposition table
+ */
+ fib_route_path_t *rpaths = NULL, path_via_mfib = {
+ .frp_proto = DPO_PROTO_IP4,
+ .frp_addr = zero_addr,
+ .frp_fib_index = 0, // default MFIB table
+ .frp_rpf_id = 9, // some non-zero value
+ .frp_flags = FIB_ROUTE_PATH_RPF_ID,
+ };
+ u16 src = 99;
+ vec_add1(rpaths, path_via_mfib);
+ bier_disp_table_entry_path_add(bier_disp_tbl_id, src,
+ BIER_HDR_PROTO_IPV4, rpaths);
+
+ /* which should stack on a lookup in the mfib table */
+ const dpo_id_t *dpo_disp_entry_lb;
+ const dpo_id_t *dpo_disp_entry_v4;
+ bier_disp_entry_t *bde_99;
+ index_t bdei;
+
+ bdei = bier_disp_table_lookup(bdti1, clib_host_to_net_u16(src));
+ bde_99 = bier_disp_entry_get(bdei);
+ dpo_disp_entry_lb = &bde_99->bde_fwd[BIER_HDR_PROTO_IPV4].bde_dpo;
+
+ BIER_TEST(dpo_disp_entry_lb->dpoi_type == DPO_LOAD_BALANCE,
+ "BIER Disp entry stacks on LB");
+
+ load_balance_t *lb;
+ lb = load_balance_get(dpo_disp_entry_lb->dpoi_index);
+ dpo_disp_entry_v4 = load_balance_get_bucket_i(lb, 0);
+
+ lookup_dpo_t *lkd = lookup_dpo_get(dpo_disp_entry_v4->dpoi_index);
+
+ BIER_TEST((bdti1 == lkd->lkd_fib_index),
+ "disp is deag in %d %U",
+ lkd->lkd_fib_index,
+ format_dpo_id, dpo_disp_entry_v4, 0);
+ BIER_TEST((LOOKUP_INPUT_DST_ADDR == lkd->lkd_input),
+ "disp is destination deag in %d %U",
+ lkd->lkd_input,
+ format_dpo_id, dpo_disp_entry_v4, 0);
+ BIER_TEST((LOOKUP_MULTICAST == lkd->lkd_cast),
+ "disp is multicast deag in %d %U",
+ lkd->lkd_input,
+ format_dpo_id, dpo_disp_entry_v4, 0);
+
+ /*
+ * cleanup
+ */
+ dpo_reset(&dpo_disp_tbl_1);
+
+ bier_disp_table_entry_path_remove(bier_disp_tbl_id, src,
+ BIER_HDR_PROTO_IPV4, rpaths);
+ bier_table_route_remove(&bt_0_0_0_256, 3, paths_via_disp);
+
+ bier_disp_table_unlock_w_table_id(bier_disp_tbl_id);
+
+ bier_table_unlock(&bt_0_0_0_256);
+
+ BIER_TEST(0 == pool_elts(bier_fmask_pool),
+ "BIER fmask resources freed ");
+ BIER_TEST(0 == pool_elts(bier_table_pool),
+ "BIER table resources freed ");
+ BIER_TEST(0 == pool_elts(bier_disp_table_pool),
+ "BIER Disposition table resources freed ");
+ BIER_TEST(0 == pool_elts(bier_disp_entry_pool),
+ "BIER Disposition entry resources freed ");
+
+ vec_free(paths_via_disp);
+ return (0);
+}
+
+static clib_error_t *
+bier_test (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd_arg)
+{
+ int res = 0;
+
+ res += bier_test_mk_intf(4);
+
+ if (unformat (input, "debug"))
+ {
+ bier_test_do_debug = 1;
+ }
+
+ if (unformat (input, "mid"))
+ res += bier_test_mpls_spf();
+ else if (unformat (input, "head"))
+ res += bier_test_mpls_imp();
+ else if (unformat (input, "tail"))
+ res += bier_test_mpls_disp();
+ else
+ {
+ res += bier_test_mpls_spf();
+ res += bier_test_mpls_imp();
+ res += bier_test_mpls_disp();
+ }
+
+ if (res)
+ {
+ return clib_error_return(0, "BIER Unit Test Failed");
+ }
+ else
+ {
+ return (NULL);
+ }
+}
+
+VLIB_CLI_COMMAND (test_route_command, static) = {
+ .path = "test bier",
+ .short_help = "bier unit tests",
+ .function = bier_test,
+};
+
+clib_error_t *
+bier_test_init (vlib_main_t *vm)
+{
+ return 0;
+}
+
+VLIB_INIT_FUNCTION (bier_test_init);
diff --git a/src/vnet/bier/bier_types.c b/src/vnet/bier/bier_types.c
new file mode 100644
index 00000000000..0d27524aeb1
--- /dev/null
+++ b/src/vnet/bier/bier_types.c
@@ -0,0 +1,190 @@
+/*
+ * 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 <vppinfra/types.h>
+#include <vnet/bier/bier_types.h>
+#include <vnet/bier/bier_hdr_inlines.h>
+
+/*
+ * enum to string conversions
+ */
+const static char* const bier_hdr_len_id_names[] = BIER_HDR_LEN_IDS;
+const static char* const bier_hdr_proto_names[] = BIER_HDR_PROTO_ID_NAMES;
+
+const static u16 bier_hdr_len_num_buckets[] = {
+ [BIER_HDR_LEN_INVALID] = 0,
+ [BIER_HDR_LEN_64] = 8,
+ [BIER_HDR_LEN_128] = 16,
+ [BIER_HDR_LEN_256] = 32,
+ [BIER_HDR_LEN_512] = 64,
+ [BIER_HDR_LEN_1024] = 128,
+ [BIER_HDR_LEN_2048] = 256,
+ [BIER_HDR_LEN_4096] = 512,
+};
+
+const static u16 bier_hdr_len_num_bits[] = {
+ [BIER_HDR_LEN_INVALID] = 0,
+ [BIER_HDR_LEN_64] = 64,
+ [BIER_HDR_LEN_128] = 128,
+ [BIER_HDR_LEN_256] = 256,
+ [BIER_HDR_LEN_512] = 512,
+ [BIER_HDR_LEN_1024] = 1024,
+ [BIER_HDR_LEN_2048] = 2048,
+ [BIER_HDR_LEN_4096] = 4096,
+};
+
+const static u16 bier_hdr_len_prefix_len[] = {
+ [BIER_HDR_LEN_INVALID] = 0,
+ [BIER_HDR_LEN_64] = 7,
+ [BIER_HDR_LEN_128] = 8,
+ [BIER_HDR_LEN_256] = 9,
+ [BIER_HDR_LEN_512] = 10,
+ [BIER_HDR_LEN_1024] = 11,
+ [BIER_HDR_LEN_2048] = 12,
+ [BIER_HDR_LEN_4096] = 13,
+};
+
+uint32_t
+bier_hdr_len_id_to_num_buckets (bier_hdr_len_id_t id)
+{
+ return (bier_hdr_len_num_buckets[id]);
+}
+
+uint32_t
+bier_hdr_len_id_to_num_bytes (bier_hdr_len_id_t id)
+{
+ return (bier_hdr_len_id_to_num_buckets(id));
+}
+
+uint32_t
+bier_hdr_len_id_to_max_bucket (bier_hdr_len_id_t id)
+{
+ return (bier_hdr_len_id_to_num_buckets(id) - 1);
+}
+
+uint32_t
+bier_hdr_len_id_to_num_bits (bier_hdr_len_id_t id)
+{
+ return (bier_hdr_len_num_bits[id]);
+}
+
+uint32_t
+bier_hdr_len_id_to_max_bit (bier_hdr_len_id_t id)
+{
+ return (bier_hdr_len_id_to_num_bits(id));
+}
+
+uint32_t
+bier_hdr_len_id_to_prefix_len (bier_hdr_len_id_t id)
+{
+ return (bier_hdr_len_prefix_len[id]);
+}
+
+u8 *
+format_bier_hdr_len_id (u8 *s, va_list *ap)
+{
+ bier_hdr_len_id_t hli = va_arg(*ap, int); // int promotion of bier_hdr_len_id_t
+
+ return (format(s, "%s", bier_hdr_len_id_names[hli]));
+}
+
+u8 *
+format_bier_hdr_proto (u8 *s, va_list *ap)
+{
+ bier_hdr_proto_id_t pi = va_arg(*ap, int);
+
+ return (format(s, "%s", bier_hdr_proto_names[pi]));
+}
+
+int
+bier_table_id_cmp (const bier_table_id_t *btid1,
+ const bier_table_id_t *btid2)
+{
+ int res;
+
+ res = (btid1->bti_set - btid2->bti_set);
+
+ if (0 == res)
+ {
+ res = (btid1->bti_sub_domain - btid2->bti_sub_domain);
+ }
+ if (0 == res)
+ {
+ res = (btid1->bti_ecmp - btid2->bti_ecmp);
+ }
+ if (0 == res)
+ {
+ res = (btid1->bti_hdr_len - btid2->bti_hdr_len);
+ }
+ if (0 == res)
+ {
+ res = (btid1->bti_type - btid2->bti_type);
+ }
+ return (res);
+}
+
+dpo_proto_t
+bier_hdr_proto_to_dpo (bier_hdr_proto_id_t bproto)
+{
+ switch (bproto)
+ {
+ case BIER_HDR_PROTO_INVALID:
+ case BIER_HDR_PROTO_CTRL:
+ case BIER_HDR_PROTO_OAM:
+ ASSERT(0);
+ break;
+ case BIER_HDR_PROTO_MPLS_DOWN_STREAM:
+ case BIER_HDR_PROTO_MPLS_UP_STREAM:
+ return (DPO_PROTO_MPLS);
+ case BIER_HDR_PROTO_ETHERNET:
+ case BIER_HDR_PROTO_VXLAN:
+ return (DPO_PROTO_ETHERNET);
+ case BIER_HDR_PROTO_IPV4:
+ return (DPO_PROTO_IP4);
+ case BIER_HDR_PROTO_IPV6:
+ return (DPO_PROTO_IP4);
+ }
+
+ return (DPO_PROTO_NUM);
+}
+
+u8 *
+format_bier_table_id (u8 *s, va_list *ap)
+{
+ bier_table_id_t *btid = va_arg(*ap, bier_table_id_t *);
+
+ return (format(s, "sub-domain:%d set:%d ecmp:%d bsl:%U",
+ btid->bti_sub_domain,
+ btid->bti_set,
+ btid->bti_ecmp,
+ format_bier_hdr_len_id, btid->bti_hdr_len));
+}
+
+u8 *
+format_bier_hdr (u8 *s, va_list *ap)
+{
+ bier_hdr_t *bh = va_arg(*ap, bier_hdr_t *);
+ bier_hdr_t copy = *bh;
+
+ bier_hdr_ntoh(&copy);
+
+ return (format(s, "nibble:%d version:%d hdr-len:%U entropy:%d proto:%U src:%d",
+ bier_hdr_get_1st_nibble(&copy),
+ bier_hdr_get_version(&copy),
+ format_bier_hdr_len_id, bier_hdr_get_len_id(&copy),
+ bier_hdr_get_entropy(&copy),
+ format_bier_hdr_proto, bier_hdr_get_proto_id(&copy),
+ bier_hdr_get_src_id(&copy)));
+}
diff --git a/src/vnet/bier/bier_types.h b/src/vnet/bier/bier_types.h
new file mode 100644
index 00000000000..fa1cd423278
--- /dev/null
+++ b/src/vnet/bier/bier_types.h
@@ -0,0 +1,507 @@
+/*
+ * 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.
+ */
+
+#ifndef __BIER_TYPES_H__
+#define __BIER_TYPES_H__
+
+#include <vlib/vlib.h>
+#include <vnet/dpo/dpo.h>
+
+/**
+ * @brief Flags to control show output
+ */
+typedef enum bier_show_flags_t_ {
+ BIER_SHOW_BRIEF,
+ BIER_SHOW_DETAIL = (1 << 0),
+} bier_show_flags_t;
+
+/**
+ * Types of BIER tables
+ */
+typedef enum bier_table_type_t_ {
+ /**
+ * BIER over MPLS with SPF
+ */
+ BIER_TABLE_MPLS_SPF,
+
+ /**
+ * BIER over MPLS for TE
+ */
+ BIER_TABLE_MPLS_TE,
+} __attribute__((packed)) bier_table_type_t;
+
+#define BIER_TABLE_TYPES { \
+ [BIER_TABLE_MPLS_SPF] = "mpls-spf", \
+ [BIER_TABLE_MPLS_TE] = "mpls-te", \
+}
+
+/**
+ * bier_hdr_len_id_t enumerator
+ **/
+typedef enum bier_hdr_len_id_t_ {
+ BIER_HDR_LEN_64 = 0,
+ BIER_HDR_LEN_128,
+ BIER_HDR_LEN_256,
+ BIER_HDR_LEN_512,
+ BIER_HDR_LEN_1024,
+ BIER_HDR_LEN_2048,
+ BIER_HDR_LEN_4096,
+ BIER_HDR_LEN_INVALID,
+} __attribute__((packed)) bier_hdr_len_id_t;
+
+#define BIER_HDR_LEN_IDS { \
+ [BIER_HDR_LEN_INVALID] = "invalid",\
+ [BIER_HDR_LEN_64] = "64", \
+ [BIER_HDR_LEN_128] = "128", \
+ [BIER_HDR_LEN_256] = "256", \
+ [BIER_HDR_LEN_512] = "512", \
+ [BIER_HDR_LEN_1024] = "1024", \
+ [BIER_HDR_LEN_2048] = "2048", \
+ [BIER_HDR_LEN_4096] = "4096", \
+}
+
+#define FOR_EACH_BIER_HDR_LEN(_len) \
+ for (_item = BIER_HDR_LEN_64; \
+ _item <= BIER_HDR_LEN_4096; \
+ _item++)
+
+/**
+ * Format the header length field
+ */
+extern u8 *format_bier_hdr_len_id(u8 *s, va_list *ap);
+
+/*
+ * convert from prefix len to hdr ID
+ */
+static inline bier_hdr_len_id_t
+bier_prefix_len_to_hdr_id (u16 prfx_len) {
+
+ switch (prfx_len) {
+ case 7:
+ return (BIER_HDR_LEN_64);
+ case 8:
+ return (BIER_HDR_LEN_128);
+ case 9:
+ return (BIER_HDR_LEN_256);
+ case 10:
+ return (BIER_HDR_LEN_512);
+ case 11:
+ return (BIER_HDR_LEN_1024);
+ case 12:
+ return (BIER_HDR_LEN_2048);
+ case 13:
+ return (BIER_HDR_LEN_4096);
+ default:
+ break;
+ }
+
+ return (BIER_HDR_LEN_INVALID);
+}
+
+static inline bier_hdr_len_id_t
+bier_hdr_byte_len_to_id (u32 bytes)
+{
+ switch (bytes) {
+ case 8:
+ return (BIER_HDR_LEN_64);
+ case 16:
+ return (BIER_HDR_LEN_128);
+ case 32:
+ return (BIER_HDR_LEN_256);
+ case 64:
+ return (BIER_HDR_LEN_512);
+ case 128:
+ return (BIER_HDR_LEN_1024);
+ case 256:
+ return (BIER_HDR_LEN_2048);
+ case 512:
+ return (BIER_HDR_LEN_4096);
+ }
+
+ return (BIER_HDR_LEN_INVALID);
+}
+
+static inline bier_hdr_len_id_t
+bier_hdr_bit_len_to_id (u32 bytes)
+{
+ switch (bytes) {
+ case 64:
+ return (BIER_HDR_LEN_64);
+ case 128:
+ return (BIER_HDR_LEN_128);
+ case 256:
+ return (BIER_HDR_LEN_256);
+ case 512:
+ return (BIER_HDR_LEN_512);
+ case 1024:
+ return (BIER_HDR_LEN_1024);
+ case 2048:
+ return (BIER_HDR_LEN_2048);
+ case 4096:
+ return (BIER_HDR_LEN_4096);
+ }
+
+ return (BIER_HDR_LEN_INVALID);
+}
+
+/**
+ * bier_hdr_len_num_buckets_t enumerator
+ **/
+typedef enum bier_hdr_len_num_buckets_t_ {
+ BIER_HDR_BUCKETS_64 = 8,
+ BIER_HDR_BUCKETS_128 = 16,
+ BIER_HDR_BUCKETS_256 = 32,
+ BIER_HDR_BUCKETS_512 = 64,
+ BIER_HDR_BUCKETS_1024 = 128,
+ BIER_HDR_BUCKETS_2048 = 256,
+ BIER_HDR_BUCKETS_4096 = 512,
+} bier_hdr_len_num_buckets_t;
+
+/**
+ * BIER header protocol payload types
+ **/
+typedef enum bier_hdr_proto_id_t_ {
+ BIER_HDR_PROTO_INVALID = 0,
+ BIER_HDR_PROTO_MPLS_DOWN_STREAM,
+ BIER_HDR_PROTO_MPLS_UP_STREAM,
+ BIER_HDR_PROTO_ETHERNET,
+ BIER_HDR_PROTO_IPV4,
+ BIER_HDR_PROTO_IPV6,
+ BIER_HDR_PROTO_VXLAN,
+ BIER_HDR_PROTO_CTRL,
+ BIER_HDR_PROTO_OAM,
+} __attribute__((packed)) bier_hdr_proto_id_t;
+
+#define BIER_HDR_N_PROTO (BIER_HDR_PROTO_OAM + 1)
+
+#define BIER_HDR_PROTO_ID_NAMES { \
+ [BIER_HDR_PROTO_INVALID] = "invalid", \
+ [BIER_HDR_PROTO_MPLS_DOWN_STREAM] = "mpls-down-stream", \
+ [BIER_HDR_PROTO_MPLS_UP_STREAM] = "mpls-up-stream", \
+ [BIER_HDR_PROTO_ETHERNET] = "ethernet", \
+ [BIER_HDR_PROTO_IPV4] = "ipv4", \
+ [BIER_HDR_PROTO_IPV6] = "ipv6", \
+ [BIER_HDR_PROTO_VXLAN] = "vxlan", \
+ [BIER_HDR_PROTO_CTRL] = "control-plane", \
+ [BIER_HDR_PROTO_OAM] = "oam", \
+}
+
+#define FOR_EACH_BIER_HDR_PROTO(_proto) \
+ for (_proto = BIER_HDR_PROTO_MPLS_DOWN_STREAM; \
+ _proto <= BIER_HDR_PROTO_OAM; \
+ _proto++)
+
+/**
+ * Format the header length field
+ */
+extern u8 *format_bier_hdr_proto(u8 *s, va_list *ap);
+
+/**
+ * Convert from BIER next-hop proto to DPO proto
+ */
+extern dpo_proto_t bier_hdr_proto_to_dpo(bier_hdr_proto_id_t bproto);
+
+/**
+ * BIER header versions
+ **/
+typedef enum bier_hdr_version_t_ {
+ BIER_HDR_VERSION_1 = 0,
+} __attribute__((packed)) bier_hdr_version_t;
+
+/**
+ * bier_hdr_code_t enumerator
+ **/
+typedef enum bier_hdr_code_t_ {
+ BIER_HDR_CODE_OAM_IPV4 = 0,
+ BIER_HDR_CODE_OAM_IPV6 = 1,
+ BIER_HDR_CODE_CTRL_IPV4 = 2,
+ BIER_HDR_CODE_CTRL_IPV6 = 3,
+} __attribute__((packed)) bier_hdr_code_t;
+
+/**
+ * bier_hdr_oam_sub_code_t enumerator
+ */
+typedef enum bier_hdr_oam_sub_code_t_ {
+ BIER_HDR_SUB_CODE_OAM_PING_REQ = 0,
+ BIER_HDR_SUB_CODE_OAM_PING_RESP = 1,
+} __attribute__((packed)) bier_hdr_oam_sub_code_t;
+
+/**
+ * bier_hdr_ctrl_sub_code_t enumerator
+ */
+typedef enum bier_hdr_ctrl_sub_code_t_ {
+ BIER_HDR_SUB_CODE_CTRL_MEMBER_REQ = 0,
+ BIER_HDR_SUB_CODE_CTRL_ATTACHED_NET = 1,
+} __attribute__((packed)) bier_hdr_ctrl_sub_code_t;
+
+/**
+ * A bucket is a byte. The byte string is thus always in network byte order.
+ */
+typedef u8 bier_bit_mask_bucket_t;
+
+/**
+ * A BIER Bit-String value of length 64 bits.
+ */
+typedef struct bier_bit_mask_64_t_ {
+ bier_bit_mask_bucket_t bits[BIER_HDR_BUCKETS_64];
+} bier_bit_mask_64_t;
+
+/**
+ * A BIER Bit-String value of length 128 bits.
+ */
+typedef struct bier_bit_mask_128_t_ {
+ bier_bit_mask_bucket_t bits[BIER_HDR_BUCKETS_128];
+} bier_bit_mask_128_t;
+
+/**
+ * A BIER Bit-String value of length 256 bits.
+ */
+typedef struct bier_bit_mask_256_t_ {
+ bier_bit_mask_bucket_t bits[BIER_HDR_BUCKETS_256];
+} bier_bit_mask_256_t;
+
+/**
+ * A BIER Bit-String value of length 512 bits.
+ */
+typedef struct bier_bit_mask_512_t_ {
+ bier_bit_mask_bucket_t bits[BIER_HDR_BUCKETS_512];
+} bier_bit_mask_512_t;
+
+/**
+ * A BIER Bit-String value of length 1024 bits.
+ */
+typedef struct bier_bit_mask_1024_t_ {
+ bier_bit_mask_bucket_t bits[BIER_HDR_BUCKETS_1024];
+} bier_bit_mask_1024_t;
+
+/**
+ * A BIER Bit-String value of length 2048 bits.
+ */
+typedef struct bier_bit_mask_2048_t_ {
+ bier_bit_mask_bucket_t bits[BIER_HDR_BUCKETS_2048];
+} bier_bit_mask_2048_t;
+
+/**
+ * A BIER Bit-String value of length 4096 bits.
+ */
+typedef struct bier_bit_mask_4096_t_ {
+ bier_bit_mask_bucket_t bits[BIER_HDR_BUCKETS_4096];
+} bier_bit_mask_4096_t;
+
+
+/**
+ * 256 bits = 32 bytes
+ */
+#define BIER_BIT_MASK_NUM_BUCKETS 32
+#define BIER_BIT_MASK_MAX_BUCKET (BIER_BIT_MASK_NUM_BUCKETS - 1)
+
+/**
+ * number of bits in a bucket
+ */
+#define BIER_BIT_MASK_BITS_PER_BUCKET 8
+
+/**
+ * Supported bit-posiotn range
+ */
+#define BIER_BIT_MASK_MIN_POS (1)
+
+/**
+ * A Variable length BitString
+ */
+typedef struct bier_bit_string_t_ {
+ /**
+ * The length of the string in BYTES
+ */
+ u16 bbs_len;
+
+ /**
+ * The buckets in the string
+ */
+ bier_bit_mask_bucket_t *bbs_buckets;
+} bier_bit_string_t;
+
+/**
+ * A BIER Bit-mask value
+ *
+ * The size of this mask represents this platforms BIER capabilities
+ */
+typedef bier_bit_mask_256_t bier_bit_mask_t;
+
+/**
+ * A bit positon
+ * as assigned to egress PEs
+ */
+typedef u32 bier_bp_t;
+
+#define BIER_BP_TO_INDEX(bp) (bp - 1)
+
+/**
+ * The maximum BP that can be assigned
+ */
+#define BIER_BP_MAX 0x10000
+
+/**
+ * An identifier of the sender of BIER packets
+ * this is the source of the 'tree' - the BFIR
+ */
+typedef u16 bier_hdr_src_id_t;
+
+/**
+ * An entropy value in a BIER header
+ */
+typedef u32 bier_hdr_entropy_t;
+
+#define BIER_BP_INVALID 0
+
+/**
+ * A BIER header of variable length
+ * The encoding follows:
+ * https://tools.ietf.org/html/draft-ietf-bier-mpls-encapsulation-10
+ */
+typedef struct bier_hdr_t_ {
+ /**
+ * The first nibble is always set to 0101
+ * to ensure that when carried over MPLS, the BIER packet
+ * is not mistaken for IPv[46]:
+ * type: bier_hdr_version_t
+ *
+ * The second nibble is the version - this is 0:
+ * type: bier_hdr_version_t
+ *
+ * The third nibble is header length ID
+ * type: bier_hdr_len_id_t
+ *
+ * The next 20 bits are entropy
+ * An entropy value, calculated by the head end, used
+ * at the head and mid-points for load-balance hash
+ * type: bier_hdr_entropy_t
+ */
+ u32 bh_first_word;
+
+ /**
+ * The second word comprises:
+ * 2 bits of OAM for passive perf measurement
+ * 2 reserved bits;
+ * 6 bits of DSCP
+ * 6 bits for the next-proto field of type;
+ * bier_hdr_proto_id_t
+ */
+ u16 bh_oam_dscp_proto;
+
+ /**
+ * The BFR-ID of the sender
+ */
+ u16 bh_bfr_id;
+
+ /**
+ * The variable length bit-string
+ */
+ bier_bit_mask_bucket_t bh_bit_string[0];
+} bier_hdr_t;
+
+/**
+ * Format a BIER header
+ */
+extern u8 *format_bier_hdr(u8 *s, va_list *ap);
+
+/**
+ * The BIER Set ID assigned to a BIER table
+ */
+typedef u32 bier_table_set_id_t;
+
+#define BIER_TABLE_SET_INVALID_ID 0xffffffff
+
+/**
+ * The BIER Sub-domain ID assigned to a BIER table
+ */
+typedef u32 bier_table_sub_domain_id_t;
+
+#define BIER_TABLE_SUB_DOMAIN_INVALID_ID 0xffffffff
+
+/**
+ * An ID or instance number of a BIER sub-table
+ */
+typedef u32 bier_table_ecmp_id_t;
+
+/**
+ * Definition of the ID of the BIER main table
+ */
+#define BIER_ECMP_TABLE_ID_MAIN 0xFFFF
+
+/**
+ * The ID of a table
+ */
+typedef struct bier_table_id_t_ {
+ /**
+ * The SET-ID
+ * The control plane divdies the bit-position space
+ * into sets in the case the max bit-position is greater
+ * than the table's bit-string size
+ */
+ bier_table_set_id_t bti_set;
+
+ /**
+ * The Sub-Domain-ID
+ * The control plane has the configuration option to specify multiple
+ * domains or topologies.
+ */
+ bier_table_sub_domain_id_t bti_sub_domain;
+
+ /**
+ * The SUB/ECMP-ID
+ * Constructed by FIB to achieve ECMP between BFR-NBRs
+ */
+ bier_table_ecmp_id_t bti_ecmp;
+
+ /**
+ * The size of the bit string processed by this table.
+ */
+ bier_hdr_len_id_t bti_hdr_len;
+
+ /**
+ * The type of the table; SPF or TE, MPLS or IPv6
+ */
+ bier_table_type_t bti_type;
+} bier_table_id_t;
+
+/**
+ * Format a BIER table ID
+ */
+extern u8 *format_bier_table_id(u8 *s, va_list *ap);
+
+/**
+ * Compare to BIER table IDs for equality
+ */
+extern int bier_table_id_cmp(const bier_table_id_t *btid1,
+ const bier_table_id_t *btid2);
+
+/**
+ * Conversion functions for the enumerated bit-string length
+ * values, to bit and bytes
+ */
+extern u32 bier_hdr_len_id_to_num_buckets(bier_hdr_len_id_t id);
+extern u32 bier_hdr_len_id_to_num_bytes(bier_hdr_len_id_t id);
+extern u32 bier_hdr_len_id_to_max_bucket(bier_hdr_len_id_t id);
+extern u32 bier_hdr_len_id_to_num_bits(bier_hdr_len_id_t id);
+extern u32 bier_hdr_len_id_to_max_bit(bier_hdr_len_id_t id);
+extern u32 bier_hdr_len_id_to_prefix_len(bier_hdr_len_id_t id);
+
+#define BIER_OK 0
+#define BIER_ERR_NO_TABLE 1
+#define BIER_ERR_DUPLICATE_TABLE 2
+#define BIER_ERR_PANIC 3
+typedef int bier_rc;
+
+#endif /* __BIER_TYPES_H__ */
diff --git a/src/vnet/bier/bier_update.c b/src/vnet/bier/bier_update.c
new file mode 100644
index 00000000000..ddbdd72f8ee
--- /dev/null
+++ b/src/vnet/bier/bier_update.c
@@ -0,0 +1,182 @@
+/*
+ * 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/vnet.h>
+#include <vnet/mpls/mpls.h>
+
+#include <vnet/bier/bier_table.h>
+#include <vnet/bier/bier_types.h>
+#include <vnet/bier/bier_update.h>
+
+clib_error_t *
+vnet_bier_table_cmd (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd)
+{
+ u32 hdr_len, local_label;
+ clib_error_t * error = 0;
+ bier_table_id_t bti = {
+ .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
+ };
+ u32 is_add = 0;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
+ if (unformat (input, "del")) {
+ is_add = 0;
+ } else if (unformat (input, "add")) {
+ is_add = 1;
+ } else if (unformat (input, "sd %d", &bti.bti_sub_domain)) {
+ } else if (unformat (input, "set %d", &bti.bti_set)) {
+ } else if (unformat (input, "bsl %d", &hdr_len)) {
+ } else if (unformat (input, "mpls %d", &local_label)) {
+ } else {
+ error = unformat_parse_error (input);
+ goto done;
+ }
+ }
+
+ bti.bti_hdr_len = bier_hdr_bit_len_to_id(hdr_len);
+ // FIXME
+ bti.bti_type = BIER_TABLE_MPLS_SPF;
+
+ if (is_add)
+ {
+ bier_table_add_or_lock(&bti, local_label);
+ }
+ else
+ {
+ bier_table_unlock(&bti);
+ }
+
+done:
+ return (error);
+}
+
+VLIB_CLI_COMMAND (bier_table_command) = {
+ .path = "bier table",
+ .short_help = "Add/delete BIER Tables",
+ .function = vnet_bier_table_cmd,
+};
+
+clib_error_t *
+vnet_bier_route_cmd (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd)
+{
+ clib_error_t * error = NULL;
+ fib_route_path_t brp = {
+ .frp_flags = FIB_ROUTE_PATH_BIER_FMASK,
+ };
+ bier_table_id_t bti = {
+ };
+ mpls_label_t out_label;
+ bier_bp_t bp;
+ u32 hdr_len;
+ u32 add = 1;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
+ if (unformat (input, "del")) {
+ add = 0;
+ } else if (unformat (input, "sd %d", &bti.bti_sub_domain)) {
+ } else if (unformat (input, "set %d", &bti.bti_set)) {
+ } else if (unformat (input, "bsl %d", &hdr_len)) {
+ } else if (unformat (input, "bp %d", &bp)) {
+ } else if (unformat (input, "v4-nh %U",
+ unformat_ip46_address,
+ &brp.frp_addr, 0)) {
+ } else if (unformat (input, "mpls %d", &out_label)) {
+ vec_add1(brp.frp_label_stack, out_label);
+ } else {
+ error = unformat_parse_error (input);
+ goto done;
+ }
+ }
+
+ bti.bti_hdr_len = bier_hdr_bit_len_to_id(hdr_len);
+ // FIXME
+ bti.bti_type = BIER_TABLE_MPLS_SPF;
+
+ if (add)
+ {
+ bier_table_route_add(&bti, bp, &brp);
+ }
+ else
+ {
+ bier_table_route_remove(&bti, bp, &brp);
+ }
+
+done:
+ return (error);
+}
+
+VLIB_CLI_COMMAND (bier_route_command) = {
+ .path = "bier route",
+ .short_help = "Add/delete BIER Routes",
+ .function = vnet_bier_route_cmd,
+};
+
+static clib_error_t *
+show_bier_fib_command_fn (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd)
+{
+ bier_show_flags_t flags;
+ index_t bti, bei;
+ bier_bp_t bp;
+
+ bp = BIER_BP_INVALID;
+ bti = bei = INDEX_INVALID;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
+ if (unformat (input, "%d %d", &bti, &bp))
+ {
+ flags = BIER_SHOW_DETAIL;
+ }
+ else if (unformat (input, "%d", &bti))
+ {
+ flags = BIER_SHOW_DETAIL;
+ }
+ else
+ {
+ break;
+ }
+ }
+
+ if (INDEX_INVALID == bti)
+ {
+ bier_table_show_all(vm, flags);
+ }
+ else
+ {
+ if (!pool_is_free_index(bier_table_pool, bti))
+ {
+ if (BIER_BP_INVALID == bp)
+ {
+ vlib_cli_output (vm, "%U", format_bier_table, bti, flags);
+ }
+ else
+ {
+ vlib_cli_output (vm, "%U", format_bier_table_entry, bti, bp);
+ }
+ }
+ }
+ return (NULL);
+}
+
+VLIB_CLI_COMMAND (show_bier_fib_command, static) = {
+ .path = "show bier fib",
+ .short_help = "show bier fib [table-index] [bit-position]",
+ .function = show_bier_fib_command_fn,
+};
diff --git a/src/vnet/bier/bier_update.h b/src/vnet/bier/bier_update.h
new file mode 100644
index 00000000000..b4bee9fef72
--- /dev/null
+++ b/src/vnet/bier/bier_update.h
@@ -0,0 +1,24 @@
+/*
+ * 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.
+ */
+
+#ifndef __BIER_UPDATE_H__
+#define __BIER_UPDATE_H__
+
+#include <vppinfra/types.h>
+#include <vnet/bier/bier_types.h>
+#include <vnet/ip/ip.h>
+
+
+#endif