diff options
Diffstat (limited to 'src/vnet/bier')
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(©); + + n_bytes = bier_hdr_len_id_to_num_bytes( + bier_hdr_get_len_id(©)); + 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(©)); + 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(©); + bier_bit_string_init(&bbs, + bier_hdr_get_len_id(©), + 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(©); + + return (format(s, "nibble:%d version:%d hdr-len:%U entropy:%d proto:%U src:%d", + bier_hdr_get_1st_nibble(©), + bier_hdr_get_version(©), + format_bier_hdr_len_id, bier_hdr_get_len_id(©), + bier_hdr_get_entropy(©), + format_bier_hdr_proto, bier_hdr_get_proto_id(©), + bier_hdr_get_src_id(©))); +} 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 |