From 9128637ee8f7b0d903551f165a1447d427e8dd19 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Tue, 5 Dec 2017 13:24:04 -0800 Subject: [PATCH] BIER in non-MPLS netowrks as decsribed in section 2.2 ihttps://tools.ietf.org/html/draft-ietf-bier-mpls-encapsulation-10 with BIFT encoding from: https://tools.ietf.org/html/draft-wijnandsxu-bier-non-mpls-bift-encoding-00 changes: 1 - introduce the new BIFT lookup table. BIER tables that have an associated MPLS label are added to the MPLS-FIB. Those that don't are added to the BIER table 2 - BIER routes that have no associated output MPLS label will add a BIFT label. 3 - The BIER FMask has a path-list as a member to resolve via any possible path. Change-Id: I1fd4d9dbd074f0e855c16e9329b81460ebe1efce Signed-off-by: Neale Ranns --- src/vnet.am | 3 +- src/vnet/bier/bier.api | 13 +- src/vnet/bier/bier_api.c | 61 ++++--- src/vnet/bier/bier_bift_table.c | 290 ++++++++++++++++++++++++++++++++ src/vnet/bier/bier_bift_table.h | 58 +++++++ src/vnet/bier/bier_disp_dispatch_node.c | 2 +- src/vnet/bier/bier_disp_entry.c | 15 +- src/vnet/bier/bier_disp_table.c | 9 +- src/vnet/bier/bier_entry.c | 20 ++- src/vnet/bier/bier_fmask.c | 185 ++++++++++---------- src/vnet/bier/bier_fmask.h | 59 ++----- src/vnet/bier/bier_fmask_db.c | 123 +++++++------- src/vnet/bier/bier_fmask_db.h | 54 ++++-- src/vnet/bier/bier_imp_node.c | 6 + src/vnet/bier/bier_input.c | 2 +- src/vnet/bier/bier_lookup.c | 5 +- src/vnet/bier/bier_output.c | 10 +- src/vnet/bier/bier_table.c | 127 +++++++++++--- src/vnet/bier/bier_test.c | 88 ++++------ src/vnet/bier/bier_types.c | 43 +++++ src/vnet/bier/bier_types.h | 28 +++ src/vnet/bier/bier_update.c | 13 +- src/vnet/buffer.h | 20 +-- src/vnet/dpo/load_balance.c | 10 ++ src/vnet/dpo/load_balance.h | 1 + src/vnet/fib/fib_entry_src.c | 1 + src/vnet/fib/fib_path.c | 181 ++++++++------------ src/vnet/fib/fib_path.h | 7 +- src/vnet/fib/fib_path_list.c | 57 ++++--- src/vnet/fib/fib_path_list.h | 12 ++ src/vnet/fib/fib_types.h | 5 + src/vnet/lisp-gpe/lisp_gpe_fwd_entry.c | 2 + src/vnet/mpls/mpls_output.c | 14 -- src/vnet/udp/udp.h | 1 + src/vnet/udp/udp_encap.c | 13 +- test/patches/scapy-2.3.3/bier.patch | 20 ++- test/test_bier.py | 203 ++++++++++++++++++++-- test/vpp_bier.py | 18 +- test/vpp_papi_provider.py | 24 +-- 39 files changed, 1249 insertions(+), 554 deletions(-) create mode 100644 src/vnet/bier/bier_bift_table.c create mode 100644 src/vnet/bier/bier_bift_table.h diff --git a/src/vnet.am b/src/vnet.am index bd7efb24c4b..ae125bc57ef 100644 --- a/src/vnet.am +++ b/src/vnet.am @@ -1175,7 +1175,8 @@ libvnet_la_SOURCES += \ vnet/bier/bier_disp_entry.c \ vnet/bier/bier_disp_lookup_node.c \ vnet/bier/bier_disp_dispatch_node.c \ - vnet/bier/bier_disp_table.c + vnet/bier/bier_disp_table.c \ + vnet/bier/bier_bift_table.c nobase_include_HEADERS += \ vnet/bier/bier_types.h \ diff --git a/src/vnet/bier/bier.api b/src/vnet/bier/bier.api index 466524cc6a3..e4edfa1768a 100644 --- a/src/vnet/bier/bier.api +++ b/src/vnet/bier/bier.api @@ -36,7 +36,9 @@ typeonly define bier_table_id @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_label - The MPLS label for the table (0 or all ones means not set) + If the label is not set, then it is assumed that non-MPLS + encoding is used. @param bt_is_add - Is this a route add or delete */ autoreply define bier_table_add_del @@ -67,10 +69,11 @@ define bier_table_details @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 is_udp_encap - The path describes a UDP-o-IP encapsulation. @param afi - the afi of the next hop, IP46_TYPE_IP4=1, IP46_TYPE_IP6=2 @param next_hop[16] - the next hop address + @param next_hop_id - Used when the path resolves via an object that has a unique + identifier. e.g. the UDP encap object WARNING: this type is replicated, pending cleanup completion */ @@ -82,10 +85,10 @@ typeonly define fib_path3 u8 preference; u8 is_local; u8 is_drop; - u8 is_unreach; - u8 is_prohibit; + u8 is_udp_encap; u8 afi; u8 next_hop[16]; + u32 next_hop_id; u32 rpf_id; u8 n_labels; u32 label_stack[16]; diff --git a/src/vnet/bier/bier_api.c b/src/vnet/bier/bier_api.c index cd1f40b1eaa..67c70462540 100644 --- a/src/vnet/bier/bier_api.c +++ b/src/vnet/bier/bier_api.c @@ -83,7 +83,17 @@ vl_api_bier_table_add_del_t_handler (vl_api_bier_table_add_del_t * mp) if (mp->bt_is_add) { - bier_table_add_or_lock(&bti, ntohl(mp->bt_label)); + mpls_label_t label = ntohl(mp->bt_label); + + /* + * convert acceptable 'don't want a label' values from + * the API to the correct internal INVLID value + */ + if ((0 == label) || (~0 == label)) + { + label = MPLS_LABEL_INVALID; + } + bier_table_add_or_lock(&bti, label); } else { @@ -175,7 +185,7 @@ vl_api_bier_route_add_del_t_handler (vl_api_bier_route_add_del_t * mp) { brpath = &brpaths[ii]; memset(brpath, 0, sizeof(*brpath)); - brpath->frp_flags = FIB_ROUTE_PATH_BIER_FMASK; + brpath->frp_sw_if_index = ~0; vec_validate(brpath->frp_label_stack, mp->br_paths[ii].n_labels - 1); @@ -185,30 +195,41 @@ vl_api_bier_route_add_del_t_handler (vl_api_bier_route_add_del_t * mp) ntohl(mp->br_paths[ii].label_stack[jj]); } - if (0 == mp->br_paths[ii].afi) + if (mp->br_paths[ii].is_udp_encap) { - clib_memcpy (&brpath->frp_addr.ip4, - mp->br_paths[ii].next_hop, - sizeof (brpath->frp_addr.ip4)); + brpath->frp_flags |= FIB_ROUTE_PATH_UDP_ENCAP; + brpath->frp_udp_encap_id = ntohl(mp->br_paths[ii].next_hop_id); } 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; + 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 { - rv = VNET_API_ERROR_NO_SUCH_FIB; - goto done; + 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; + brpath->frp_proto = DPO_PROTO_BIER; + } + else + { + rv = VNET_API_ERROR_NO_SUCH_FIB; + goto done; + } } } } diff --git a/src/vnet/bier/bier_bift_table.c b/src/vnet/bier/bier_bift_table.c new file mode 100644 index 00000000000..e0f6c64ea59 --- /dev/null +++ b/src/vnet/bier/bier_bift_table.c @@ -0,0 +1,290 @@ +/* + * 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 +#include +#include + +typedef enum { +#define bier_error(n,s) BIER_INPUT_ERROR_##n, +#include +#undef bier_error + BIER_INPUT_N_ERROR, +} bier_input_error_t; + +static char * bier_error_strings[] = { +#define bier_error(n,s) s, +#include +#undef bier_error +}; + +/** + * Global BIFT table + */ +bier_bfit_table_t *bier_bift_table; + +/** + * Forward declare the node + */ +vlib_node_registration_t bier_bift_input_node; + +void +bier_bift_table_entry_add (bier_bift_id_t id, + const dpo_id_t *dpo) +{ + if (NULL == bier_bift_table) + { + u32 ii; + + /* + * allocate the table and + * set each of the entries therein to a BIER drop + */ + bier_bift_table = clib_mem_alloc_aligned(sizeof(*bier_bift_table), + CLIB_CACHE_LINE_BYTES); + memset(bier_bift_table, 0, sizeof(*bier_bift_table)); + + for (ii = 0; ii < BIER_BIFT_N_ENTRIES; ii++) + { + dpo_stack_from_node(bier_bift_input_node.index, + &bier_bift_table->bblt_dpos[ii], + drop_dpo_get(DPO_PROTO_BIER)); + } + + /* + * register to handle packets that arrive on the assigned + * UDP port + */ + udp_register_dst_port(vlib_get_main(), + UDP_DST_PORT_BIER, + bier_bift_input_node.index, + 0); + udp_register_dst_port(vlib_get_main(), + UDP_DST_PORT_BIER, + bier_bift_input_node.index, + 1); + } + + dpo_stack_from_node(bier_bift_input_node.index, + &bier_bift_table->bblt_dpos[id], + dpo); + + bier_bift_table->bblt_n_entries++; +} + +void +bier_bift_table_entry_remove (bier_bift_id_t id) +{ + ASSERT(NULL != bier_bift_table); + + dpo_reset(&bier_bift_table->bblt_dpos[id]); + + bier_bift_table->bblt_n_entries--; + + if (0 == bier_bift_table->bblt_n_entries) + { + udp_unregister_dst_port(vlib_get_main(), + UDP_DST_PORT_BIER, + 0); + udp_unregister_dst_port(vlib_get_main(), + UDP_DST_PORT_BIER, + 1); + + clib_mem_free(bier_bift_table); + bier_bift_table = NULL; + } +} + +/** + * @brief Packet trace record for BIER input + */ +typedef struct bier_bift_input_trace_t_ +{ + u32 bift_id; +} bier_bift_input_trace_t; + +static uword +bier_bift_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; + 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_bift_id_t *biftp0, bift0; + const dpo_id_t *dpo0; + vlib_buffer_t * b0; + u32 bi0, 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); + biftp0 = vlib_buffer_get_current (b0); + vlib_buffer_advance(b0, sizeof(bift0)); + bift0 = clib_net_to_host_u32(*biftp0); + + /* + * Do the lookup based on the first 20 bits, i.e. the + * encoding of the set, sub-domain and BSL + */ + dpo0 = bier_bift_dp_lookup(bift0); + + /* + * save the TTL for later during egress + */ + vnet_buffer(b0)->mpls.ttl = vnet_mpls_uc_get_ttl(bift0); + + next0 = dpo0->dpoi_next_node; + vnet_buffer(b0)->ip.adj_index[VLIB_TX] = dpo0->dpoi_index; + + if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED)) + { + bier_bift_input_trace_t *tr; + + tr = vlib_add_trace(vm, node, b0, sizeof (*tr)); + tr->bift_id = bift0; + } + + 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_bift_input_node.index, + BIER_INPUT_ERROR_PKTS_VALID, + from_frame->n_vectors); + return (from_frame->n_vectors); +} + +static u8 * +format_bier_bift_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_bift_input_trace_t * t = va_arg (*args, bier_bift_input_trace_t *); + + s = format (s, "BIFT-ID:[%U]", format_bier_bift_id, + vnet_mpls_uc_get_label(t->bift_id)); + return s; +} + +VLIB_REGISTER_NODE (bier_bift_input_node) = { + .function = bier_bift_input, + .name = "bier-bift-input", + /* Takes a vector of packets. */ + .vector_size = sizeof (u32), + .n_errors = BIER_INPUT_N_ERROR, + .error_strings = bier_error_strings, + .n_next_nodes = 0, + .format_trace = format_bier_bift_input_trace, +}; + +clib_error_t * +show_bier_bift_cmd (vlib_main_t * vm, + unformat_input_t * input, + vlib_cli_command_t * cmd) +{ + clib_error_t * error = NULL; + u32 hdr_len, set, sub_domain; + + set = hdr_len = sub_domain = ~0; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) { + if (unformat (input, "sd %d", &sub_domain)) { + ; + } else if (unformat (input, "set %d", &set)) { + ; + } else if (unformat (input, "bsl %d", &hdr_len)) { + ; + } + else + { + error = unformat_parse_error (input); + goto done; + } + } + + if (NULL == bier_bift_table) + { + vlib_cli_output(vm, "no BIFT entries"); + } + + if (~0 == set) + { + u32 ii; + + for (ii = 0; ii < BIER_BIFT_N_ENTRIES; ii++) + { + if (!dpo_is_drop(&bier_bift_table->bblt_dpos[ii])) + { + bier_hdr_len_id_t bsl; + + bier_bift_id_decode(ii, &set, &sub_domain, &bsl); + + vlib_cli_output(vm, "set: %d, sub-domain:%d, BSL:%U", + set, sub_domain, + format_bier_hdr_len_id, bsl); + vlib_cli_output(vm, " %U", + format_dpo_id, + &bier_bift_table->bblt_dpos[ii], 0); + } + } + } + else + { + bier_bift_id_t id; + + id = bier_bift_id_encode(set, sub_domain, + bier_hdr_bit_len_to_id(hdr_len)); + + if (!dpo_is_drop(&bier_bift_table->bblt_dpos[id])) + { + vlib_cli_output(vm, "set: %d, sub-domain:%d, BSL:%U", + set, sub_domain, + format_bier_hdr_len_id, hdr_len); + vlib_cli_output(vm, " %U", + format_dpo_id, + &bier_bift_table->bblt_dpos[id], 0); + } + } +done: + return (error); +} + +VLIB_CLI_COMMAND (show_bier_bift_command, static) = { + .path = "show bier bift", + .short_help = "show bier bift [set sd bsl ]", + .function = show_bier_bift_cmd, +}; diff --git a/src/vnet/bier/bier_bift_table.h b/src/vnet/bier/bier_bift_table.h new file mode 100644 index 00000000000..bc77c37ae3a --- /dev/null +++ b/src/vnet/bier/bier_bift_table.h @@ -0,0 +1,58 @@ +/* + * 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_BIFT_TABLE_H__ +#define __BIER_BIFT_TABLE_H__ + +#include +#include +#include + +/* + * the lookup table used to get from a BFIT_ID to a load-balance. + * As per-draft draft-ietf-bier-mpls-encapsulation-10 this isthe + * use case for non-MPLS networks + */ +#define BIER_BIFT_N_ENTRIES (1 << 20) +typedef struct bier_bfit_table_t_ +{ + /** + * Forwarding information for each BIFT ID + */ + dpo_id_t bblt_dpos[BIER_BIFT_N_ENTRIES]; + + /** + * The number of entries in the table + */ + u32 bblt_n_entries; +} bier_bfit_table_t; + + +extern void bier_bift_table_entry_add(bier_bift_id_t id, + const dpo_id_t *dpo); + +extern void bier_bift_table_entry_remove(bier_bift_id_t id); + +/** + * Global BIFT table + */ +extern bier_bfit_table_t *bier_bift_table; + +static inline const dpo_id_t* +bier_bift_dp_lookup (bier_bift_id_t key_host_order) +{ + return (&bier_bift_table->bblt_dpos[vnet_mpls_uc_get_label(key_host_order)]); +} +#endif diff --git a/src/vnet/bier/bier_disp_dispatch_node.c b/src/vnet/bier/bier_disp_dispatch_node.c index a00c2eea5f9..40d0a293658 100644 --- a/src/vnet/bier/bier_disp_dispatch_node.c +++ b/src/vnet/bier/bier_disp_dispatch_node.c @@ -86,7 +86,7 @@ bier_disp_dispatch_inline (vlib_main_t * vm, * the packets flow-hash field * DSCP mumble mumble... */ - vlib_buffer_advance(b0, (vnet_buffer(b0)->bier.n_bytes + + vlib_buffer_advance(b0, (vnet_buffer(b0)->mpls.bier.n_bytes + sizeof(*hdr0))); vnet_buffer(b0)->ip.flow_hash = entropy0; diff --git a/src/vnet/bier/bier_disp_entry.c b/src/vnet/bier/bier_disp_entry.c index 3326aba2f86..2fe2e4ab909 100644 --- a/src/vnet/bier/bier_disp_entry.c +++ b/src/vnet/bier/bier_disp_entry.c @@ -145,6 +145,7 @@ bier_disp_entry_restack (bier_disp_entry_t *bde, fib_path_list_contribute_forwarding(pli, fib_forw_chain_type_from_dpo_proto( bier_hdr_proto_to_dpo(pproto)), + FIB_PATH_LIST_FWD_FLAG_COLLAPSE, &via_dpo); bier_disp_entry_path_list_walk_ctx_t ctx = { @@ -254,24 +255,26 @@ format_bier_disp_entry (u8* s, va_list *args) bde = bier_disp_entry_get(bdei); - s = format(s, "bier-disp:[%d]", bdei); + s = format(s, "%Ubier-disp:[%d]", format_white_space, indent, 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); + s = format(s, "\n%U%U\n", + format_white_space, indent+2, + format_bier_hdr_proto, pproto); + s = format(s, "%U", format_fib_path_list, bde->bde_pl[pproto], indent+4); if (flags & BIER_SHOW_DETAIL) { s = format(s, "\n%UForwarding:", - format_white_space, indent); + format_white_space, indent+4); s = format(s, "\n%Urpf-id:%d", - format_white_space, indent+1, + format_white_space, indent+6, bde->bde_fwd[pproto].bde_rpf_id); s = format(s, "\n%U%U", - format_white_space, indent+1, + format_white_space, indent+6, format_dpo_id, &bde->bde_fwd[pproto].bde_dpo, indent+2); } } diff --git a/src/vnet/bier/bier_disp_table.c b/src/vnet/bier/bier_disp_table.c index 47d23e8ac3b..db4a2a82d2b 100644 --- a/src/vnet/bier/bier_disp_table.c +++ b/src/vnet/bier/bier_disp_table.c @@ -161,9 +161,9 @@ format_bier_disp_table (u8* s, va_list *ap) if (INDEX_INVALID != bdt->bdt_db[ii]) { u16 src = ii; - s = format(s, "\n%Usrc:%d", format_white_space, indent, + s = format(s, "\n%Usrc:%d", format_white_space, indent+1, clib_host_to_net_u16(src)); - s = format(s, "\n%U%U", format_white_space, indent+2, + s = format(s, "\n%U", format_bier_disp_entry, bdt->bdt_db[ii], indent+4, BIER_SHOW_BRIEF); } @@ -380,13 +380,12 @@ show_bier_disp_table (vlib_main_t * vm, ({ vlib_cli_output(vm, "%U", format_bier_disp_table, bier_disp_table_get_index(bdt), - 1, - BIER_SHOW_BRIEF); + 0, BIER_SHOW_BRIEF); })); } else { - vlib_cli_output(vm, "%U", format_bier_disp_table, bdti, 1, + vlib_cli_output(vm, "%U", format_bier_disp_table, bdti, 0, BIER_SHOW_DETAIL); } return (NULL); diff --git a/src/vnet/bier/bier_entry.c b/src/vnet/bier/bier_entry.c index 88be8125f51..2f8d25008cc 100644 --- a/src/vnet/bier/bier_entry.c +++ b/src/vnet/bier/bier_entry.c @@ -116,18 +116,23 @@ bier_entry_table_ecmp_walk_add_fmask (index_t btei, fib_path_list_contribute_forwarding(be->be_path_list, FIB_FORW_CHAIN_TYPE_BIER, + FIB_PATH_LIST_FWD_FLAG_COLLAPSE, &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 (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)); + } + else + { + choice = &dpo; + } if (choice->dpoi_type == DPO_BIER_FMASK) { @@ -293,6 +298,7 @@ bier_entry_contribute_forwarding(index_t bei, fib_path_list_contribute_forwarding(be->be_path_list, FIB_FORW_CHAIN_TYPE_BIER, + FIB_PATH_LIST_FWD_FLAG_COLLAPSE, dpo); } diff --git a/src/vnet/bier/bier_fmask.c b/src/vnet/bier/bier_fmask.c index 32bece0c665..2fc24dca819 100644 --- a/src/vnet/bier/bier_fmask.c +++ b/src/vnet/bier/bier_fmask.c @@ -16,6 +16,7 @@ #include #include #include +#include #include #include @@ -74,26 +75,27 @@ static void bier_fmask_stack (bier_fmask_t *bfm) { dpo_id_t via_dpo = DPO_INVALID; + fib_forward_chain_type_t fct; - if (bfm->bfm_flags & BIER_FMASK_FLAG_DISP) + if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS) { - bier_disp_table_contribute_forwarding(bfm->bfm_disp, - &via_dpo); + fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS; } else { - fib_entry_contribute_forwarding(bfm->bfm_fei, - FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS, - &via_dpo); + fct = FIB_FORW_CHAIN_TYPE_BIER; } + fib_path_list_contribute_forwarding(bfm->bfm_pl, fct, + FIB_PATH_LIST_FWD_FLAG_COLLAPSE, + &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 + * If the via PL entry provides no forwarding (i.e. a drop) + * then neither 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)) + if (dpo_is_drop(&via_dpo)) { bfm->bfm_flags &= ~BIER_FMASK_FLAG_FORWARDING; } @@ -130,65 +132,6 @@ bier_fmask_contribute_forwarding (index_t bfmi, } } -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, @@ -204,6 +147,11 @@ void bier_fmask_child_remove (fib_node_index_t bfmi, u32 sibling_index) { + if (INDEX_INVALID == bfmi) + { + return; + } + fib_node_child_remove(FIB_NODE_TYPE_BIER_FMASK, bfmi, sibling_index); @@ -212,38 +160,64 @@ bier_fmask_child_remove (fib_node_index_t bfmi, 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 fib_route_path_t *rpaths) { const bier_table_id_t *btid; mpls_label_t olabel; - bfm->bfm_id = *fmid; - bfm->bfm_fib_index = bti; + *bfm->bfm_id = *fmid; dpo_reset(&bfm->bfm_dpo); + btid = bier_table_get_id(bfm->bfm_id->bfmi_bti); + bier_fmask_bits_init(&bfm->bfm_bits, btid->bti_hdr_len); - if (ip46_address_is_zero(&(bfm->bfm_id.bfmi_nh))) + 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; + /* + * leave this label in host byte order so we can OR in the TTL + */ + if (NULL != rpaths->frp_label_stack) + { + olabel = rpaths->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, 0); + bfm->bfm_flags |= BIER_FMASK_FLAG_MPLS; + } + else + { + bier_bift_id_t id; + + /* + * not an MPLS label + */ + bfm->bfm_flags &= ~BIER_FMASK_FLAG_MPLS; + + /* + * use a label as encoded for BIFT value + */ + id = bier_bift_id_encode(btid->bti_set, + btid->bti_sub_domain, + btid->bti_hdr_len); + vnet_mpls_uc_set_label(&bfm->bfm_label, id); + vnet_mpls_uc_set_s(&bfm->bfm_label, 1); + vnet_mpls_uc_set_exp(&bfm->bfm_label, 0); + } } - btid = bier_table_get_id(bfm->bfm_fib_index); - bier_fmask_bits_init(&bfm->bfm_bits, btid->bti_hdr_len); - bier_fmask_resolve(bfm); + bfm->bfm_pl = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED | + FIB_PATH_LIST_FLAG_NO_URPF), + rpaths); + bfm->bfm_sibling = fib_path_list_child_add(bfm->bfm_pl, + FIB_NODE_TYPE_BIER_FMASK, + bier_fmask_get_index(bfm)); + + bier_fmask_stack(bfm); } static void @@ -252,8 +226,11 @@ 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); + bier_fmask_db_remove(bfm->bfm_id); + fib_path_list_child_remove(bfm->bfm_pl, + bfm->bfm_sibling); + dpo_reset(&bfm->bfm_dpo); + clib_mem_free(bfm->bfm_id); pool_put(bier_fmask_pool, bfm); } @@ -289,8 +266,7 @@ bier_fmask_lock (index_t bfmi) index_t bier_fmask_create_and_lock (const bier_fmask_id_t *fmid, - index_t bti, - const fib_route_path_t *rpath) + const fib_route_path_t *rpaths) { bier_fmask_t *bfm; @@ -298,8 +274,11 @@ bier_fmask_create_and_lock (const bier_fmask_id_t *fmid, memset(bfm, 0, sizeof(*bfm)); + bfm->bfm_id = clib_mem_alloc(sizeof(*bfm->bfm_id)); + + ASSERT(1 == vec_len(rpaths)); fib_node_init(&bfm->bfm_node, FIB_NODE_TYPE_BIER_FMASK); - bier_fmask_init(bfm, fmid, bti, rpath); + bier_fmask_init(bfm, fmid, rpaths); bier_fmask_lock(bier_fmask_get_index(bfm)); @@ -362,7 +341,7 @@ format_bier_fmask (u8 *s, va_list *ap) 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_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:"); @@ -371,7 +350,22 @@ format_bier_fmask (u8 *s, va_list *ap) s = format (s, "%s,", bier_fmask_attr_names[attr]); } } - s = format(s, "\n%U%U", + s = format(s, "\n"); + s = fib_path_list_format(bfm->bfm_pl, s); + + if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS) + { + s = format(s, " output-label:%U", + format_mpls_unicast_label, + vnet_mpls_uc_get_label(bfm->bfm_label)); + } + else + { + s = format(s, " output-bfit:[%U]", + format_bier_bift_id, + vnet_mpls_uc_get_label(bfm->bfm_label)); + } + s = format(s, "\n %U%U", format_white_space, indent, format_dpo_id, &bfm->bfm_dpo, indent+2); @@ -509,7 +503,8 @@ bier_fmask_show (vlib_main_t * vm, { pool_foreach(bfm, bier_fmask_pool, ({ - vlib_cli_output (vm, "%U", + vlib_cli_output (vm, "[@%d] %U", + bier_fmask_get_index(bfm), format_bier_fmask, bier_fmask_get_index(bfm), 0); })); } diff --git a/src/vnet/bier/bier_fmask.h b/src/vnet/bier/bier_fmask.h index 13eab5360e1..81b3923f54c 100644 --- a/src/vnet/bier/bier_fmask.h +++ b/src/vnet/bier/bier_fmask.h @@ -65,12 +65,14 @@ 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_MPLS, 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", \ + [BIER_FMASK_ATTR_MPLS] = "mpls", \ } #define FOR_EACH_BIER_FMASK_ATTR(_item) \ @@ -82,6 +84,7 @@ 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_FLAG_MPLS = (1 << BIER_FMASK_ATTR_MPLS), } bier_fmask_flags_t; /** @@ -110,47 +113,20 @@ typedef struct bier_fmask_t_ { */ 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 key to this fmask - used for store/lookup in the DB + */ + bier_fmask_id_t *bfm_id; + + /** + * The MPLS label to paint on the header during forwarding + */ + mpls_label_t bfm_label; + + /** + * The path-list + */ + fib_node_index_t bfm_pl; /** * the index of this fmask in the parent's child list. @@ -170,7 +146,6 @@ 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); diff --git a/src/vnet/bier/bier_fmask_db.c b/src/vnet/bier/bier_fmask_db.c index 37cbb365897..67d3bd1cf85 100644 --- a/src/vnet/bier/bier_fmask_db.c +++ b/src/vnet/bier/bier_fmask_db.c @@ -39,16 +39,6 @@ typedef struct bier_fmask_db_t_ { 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 */ @@ -61,82 +51,93 @@ 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) +static void +bier_fmask_db_mk_key (index_t bti, + const fib_route_path_t *rpath, + bier_fmask_id_t *key) { - 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. + * Depending on what the ID is there may be padding. + * This key will be memcmp'd in the mhash, so make sure it's all 0 */ - 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); + memset(key, 0, sizeof(*key)); - if (NULL == p) + /* + * Pick the attributes from the path that make the FMask unique + */ + if (FIB_ROUTE_PATH_UDP_ENCAP & rpath->frp_flags) { - /* - * 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*/); + key->bfmi_id = rpath->frp_udp_encap_id; } else { - index = p[0]; - bier_fmask_lock(index); + key->bfmi_sw_if_index = rpath->frp_sw_if_index; + memcpy(&key->bfmi_nh, &rpath->frp_addr, sizeof(rpath->frp_addr)); + } + if (NULL == rpath->frp_label_stack) + { + key->bfmi_hdr_type = BIER_HDR_O_OTHER; + } + else + { + key->bfmi_hdr_type = BIER_HDR_O_MPLS; } - - return (index); } u32 bier_fmask_db_find (index_t bti, - const bier_fmask_id_t *fmid) + const fib_route_path_t *rpath) { - bier_fmask_db_key_t key; - u32 index; + bier_fmask_id_t fmid; 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); + bier_fmask_db_mk_key(bti, rpath, &fmid); + p = mhash_get(&bier_fmask_db.bfdb_hash, &fmid); if (NULL != p) + { + return (p[0]); + } + + return (INDEX_INVALID); +} + +u32 +bier_fmask_db_find_or_create_and_lock (index_t bti, + const fib_route_path_t *rpath) +{ + bier_fmask_id_t fmid; + u32 index; + uword *p; + + bier_fmask_db_mk_key(bti, rpath, &fmid); + p = mhash_get(&bier_fmask_db.bfdb_hash, &fmid); + + if (NULL == p) + { + bier_fmask_t *bfm; + /* + * adding a new fmask object + */ + index = bier_fmask_create_and_lock(&fmid, rpath); + bfm = bier_fmask_get(index); + mhash_set(&bier_fmask_db.bfdb_hash, bfm->bfm_id, index, 0); + } + else { index = p[0]; + bier_fmask_lock(index); } return (index); } void -bier_fmask_db_remove (index_t bti, - const bier_fmask_id_t *fmid) +bier_fmask_db_remove (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); + p = mhash_get(&bier_fmask_db.bfdb_hash, fmid); if (NULL == p) { /* @@ -144,16 +145,16 @@ bier_fmask_db_remove (index_t bti, */ ASSERT (!"remove non-existant fmask"); } else { - mhash_unset (&(bier_fmask_db.bfdb_hash), &key, 0); + mhash_unset(&(bier_fmask_db.bfdb_hash), (void*)fmid, 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)); + mhash_init(&bier_fmask_db.bfdb_hash, + sizeof(index_t), + sizeof(bier_fmask_id_t)); return (NULL); } diff --git a/src/vnet/bier/bier_fmask_db.h b/src/vnet/bier/bier_fmask_db.h index 6ba40f3a839..a7f29c2b6a6 100644 --- a/src/vnet/bier/bier_fmask_db.h +++ b/src/vnet/bier/bier_fmask_db.h @@ -21,18 +21,27 @@ #include -#include +#include /** - * Foward declarations + * BIER header encapulsation types */ -struct bier_fmask_t_; - typedef enum bier_hdr_type_t_ { - BIER_HDR_IN_IP6, + /** + * BIER Header in MPLS networks + */ BIER_HDR_O_MPLS, + + /** + * BIER header in non-MPLS networks + */ + BIER_HDR_O_OTHER, } bier_hdr_type_t; +/** + * A key/ID for a BIER forwarding Mas (FMask). + * This is a simplified version of a fib_route_path_t. + */ typedef struct bier_fmask_id_t_ { /** * Type of BIER header this fmask supports @@ -40,22 +49,35 @@ typedef struct bier_fmask_id_t_ { bier_hdr_type_t bfmi_hdr_type; /** - * next-hop of the peer + * The BIER table this fmask is in + */ + index_t bfmi_bti; + + union { + /** + * next-hop of the peer + */ + ip46_address_t bfmi_nh; + + /** + * ID of the next-hop object, e.g. a UDP-encap + */ + u32 bfmi_id; + }; + + /** + * Software interface index */ - ip46_address_t bfmi_nh; -} bier_fmask_id_t; + u32 bfmi_sw_if_index; +} __attribute__((packed)) bier_fmask_id_t; -extern u32 +extern index_t bier_fmask_db_find_or_create_and_lock(index_t bti, - const bier_fmask_id_t *fmid, const fib_route_path_t *rpath); +extern index_t bier_fmask_db_find (index_t bti, + 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 (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_imp_node.c b/src/vnet/bier/bier_imp_node.c index e9aae93b460..9c09d6722bc 100644 --- a/src/vnet/bier/bier_imp_node.c +++ b/src/vnet/bier/bier_imp_node.c @@ -134,6 +134,12 @@ bier_imp_dpo_inline (vlib_main_t * vm, BIER_HDR_ENTROPY_FIELD_MASK) << BIER_HDR_ENTROPY_FIELD_SHIFT); + /* + * use TTL 64 for the post enacp MPLS label/BIFT-ID + * this we be decremeted in bier_output node. + */ + vnet_buffer(b0)->mpls.ttl = 65; + /* next node */ next0 = bimp0->bi_dpo[fproto].dpoi_next_node; vnet_buffer(b0)->ip.adj_index[VLIB_TX] = diff --git a/src/vnet/bier/bier_input.c b/src/vnet/bier/bier_input.c index 88b37fc80c0..dca990d07f6 100644 --- a/src/vnet/bier/bier_input.c +++ b/src/vnet/bier/bier_input.c @@ -40,7 +40,7 @@ typedef enum bier_input_next_t_ { vlib_node_registration_t bier_input_node; /** - * @brief Packet trace recoed for a BIER output + * @brief Packet trace record for BIER input */ typedef struct bier_input_trace_t_ { diff --git a/src/vnet/bier/bier_lookup.c b/src/vnet/bier/bier_lookup.c index 4cf29f886e4..817dcc6f3e8 100644 --- a/src/vnet/bier/bier_lookup.c +++ b/src/vnet/bier/bier_lookup.c @@ -138,7 +138,7 @@ bier_lookup (vlib_main_t * vm, * 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)->mpls.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, @@ -178,7 +178,6 @@ bier_lookup (vlib_main_t * vm, 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 @@ -237,6 +236,8 @@ bier_lookup (vlib_main_t * vm, ci0 = blm->blm_clones[thread_index][clone]; c0 = vlib_get_buffer(vm, ci0); + vnet_buffer(c0)->ip.adj_index[VLIB_TX] = + blm->blm_fmasks[thread_index][clone]; to_next[0] = ci0; to_next += 1; diff --git a/src/vnet/bier/bier_output.c b/src/vnet/bier/bier_output.c index fce6c50b309..db115d3ad5e 100644 --- a/src/vnet/bier/bier_output.c +++ b/src/vnet/bier/bier_output.c @@ -89,9 +89,10 @@ bier_output (vlib_main_t * vm, bier_bit_string_t bbs; vlib_buffer_t * b0; bier_fmask_t *bfm0; + mpls_label_t *h0; bier_hdr_t *bh0; - u32 bi0, *h0; u32 bfmi0; + u32 bi0; bi0 = from[0]; to_next[0] = bi0; @@ -131,9 +132,16 @@ bier_output (vlib_main_t * vm, */ if (!(bfm0->bfm_flags & BIER_FMASK_FLAG_DISP)) { + /* + * since a BIFT value and a MPLS label are formated the + * same, this painting works OK. + */ vlib_buffer_advance(b0, -(word)sizeof(mpls_label_t)); h0 = vlib_buffer_get_current(b0); + h0[0] = bfm0->bfm_label; + vnet_mpls_uc_set_ttl(h0, vnet_buffer(b0)->mpls.ttl - 1); + h0[0] = clib_host_to_net_u32(h0[0]); } /* diff --git a/src/vnet/bier/bier_table.c b/src/vnet/bier/bier_table.c index 191ac01e373..0f0f37677e9 100644 --- a/src/vnet/bier/bier_table.c +++ b/src/vnet/bier/bier_table.c @@ -20,6 +20,7 @@ #include #include #include +#include #include #include @@ -96,9 +97,6 @@ bier_table_init (bier_table_t *bt, 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 { @@ -109,6 +107,33 @@ bier_table_init (bier_table_t *bt, } } +static void +bier_table_rm_bift (bier_table_t *bt) +{ + ASSERT(MPLS_LABEL_INVALID == bt->bt_ll); + + bier_bift_table_entry_remove(bier_bift_id_encode(bt->bt_id.bti_set, + bt->bt_id.bti_sub_domain, + bt->bt_id.bti_hdr_len)); +} + +static void +bier_table_mk_bift (bier_table_t *bt) +{ + dpo_id_t dpo = DPO_INVALID; + + ASSERT(MPLS_LABEL_INVALID == bt->bt_ll); + + bier_table_contribute_forwarding(bier_table_get_index(bt), &dpo); + + bier_bift_table_entry_add(bier_bift_id_encode(bt->bt_id.bti_set, + bt->bt_id.bti_sub_domain, + bt->bt_id.bti_hdr_len), + &dpo); + + dpo_reset(&dpo); +} + static void bier_table_rm_lfib (bier_table_t *bt) { @@ -116,6 +141,9 @@ bier_table_rm_lfib (bier_table_t *bt) { fib_table_entry_delete_index(bt->bt_lfei, FIB_SOURCE_BIER); + fib_table_unlock(MPLS_FIB_DEFAULT_TABLE_ID, + FIB_PROTOCOL_MPLS, + FIB_SOURCE_BIER); } bt->bt_lfei = FIB_NODE_INDEX_INVALID; } @@ -127,6 +155,15 @@ bier_table_destroy (bier_table_t *bt) { index_t *bei; + if (MPLS_LABEL_INVALID != bt->bt_ll) + { + bier_table_rm_lfib(bt); + } + else + { + bier_table_rm_bift(bt); + } + fib_path_list_unlock(bt->bt_pl); bt->bt_pl = FIB_NODE_INDEX_INVALID; /* @@ -140,10 +177,6 @@ bier_table_destroy (bier_table_t *bt) } } 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 { @@ -177,7 +210,6 @@ bier_table_unlock_i (bier_table_t *bt) if (0 == bt->bt_locks) { - bier_table_rm_lfib(bt); bier_table_destroy(bt); } } @@ -214,12 +246,17 @@ bier_table_mk_lfib (bier_table_t *bt) u32 mpls_fib_index; dpo_id_t dpo = DPO_INVALID; + fib_table_find_or_create_and_lock(FIB_PROTOCOL_MPLS, + MPLS_FIB_DEFAULT_TABLE_ID, + FIB_SOURCE_BIER); + /* * 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, + FIB_PATH_LIST_FWD_FLAG_COLLAPSE, &dpo); mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS, @@ -306,13 +343,37 @@ bier_table_add_or_lock (const bier_table_id_t *btid, * modify an existing table. * change the lfib entry to the new local label */ - if (bier_table_is_main(bt) && - (local_label != MPLS_LABEL_INVALID)) + if (bier_table_is_main(bt)) { - bier_table_rm_lfib(bt); + /* + * remove the mpls-fib or bift entry + */ + if (MPLS_LABEL_INVALID != bt->bt_ll) + { + bier_table_rm_lfib(bt); + } + else + { + bier_table_rm_bift(bt); + } + + /* + * reset + */ + bt->bt_ll = MPLS_LABEL_INVALID; - bt->bt_ll = local_label; - bier_table_mk_lfib(bt); + /* + * add whichever mpls-fib or bift we need + */ + if (local_label != MPLS_LABEL_INVALID) + { + bt->bt_ll = local_label; + bier_table_mk_lfib(bt); + } + else + { + bier_table_mk_bift(bt); + } } bti = bier_table_get_index(bt); } @@ -334,7 +395,19 @@ bier_table_add_or_lock (const bier_table_id_t *btid, if (bier_table_is_main(bt)) { bt = bier_table_mk_ecmp(bti); - bier_table_mk_lfib(bt); + + /* + * add whichever mpls-fib or bift we need + */ + if (local_label != MPLS_LABEL_INVALID) + { + bt->bt_ll = local_label; + bier_table_mk_lfib(bt); + } + else + { + bier_table_mk_bift(bt); + } } } @@ -459,16 +532,19 @@ bier_table_route_add (const bier_table_id_t *btid, */ 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; + /* + * First use the path to find or construct an FMask object + * via the next-hop + */ + bfmi = bier_fmask_db_find_or_create_and_lock(bti, brp); vec_add1(bfmis, bfmi); + + /* + * then modify the path to resolve via this fmask object + * and use it to resolve the BIER entry. + */ + brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK; + brp->frp_bier_fmask = bfmi; } if (INDEX_INVALID == bei) @@ -536,6 +612,7 @@ bier_table_contribute_forwarding (index_t bti, */ fib_path_list_contribute_forwarding(bt->bt_pl, FIB_FORW_CHAIN_TYPE_BIER, + FIB_PATH_LIST_FWD_FLAG_COLLAPSE, dpo); } else @@ -642,12 +719,12 @@ format_bier_table (u8 *s, va_list *ap) if (pool_is_free_index(bier_table_pool, bti)) { - return (format(s, "No BIER f-mask %d", bti)); + return (format(s, "No BIER table %d", bti)); } bt = bier_table_get(bti); - s = format(s, "[@%d] bier-table:[%U local-label:%U]", + 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); diff --git a/src/vnet/bier/bier_test.c b/src/vnet/bier/bier_test.c index f0e7b0cab2f..cf75c2eb072 100644 --- a/src/vnet/bier/bier_test.c +++ b/src/vnet/bier/bier_test.c @@ -312,7 +312,7 @@ bier_test_mpls_spf (void) 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, + .frp_sw_if_index = ~0, }; vec_add1(path_1_1_1_1.frp_label_stack, 500); vec_add1(paths_1_1_1_1, path_1_1_1_1); @@ -321,10 +321,6 @@ bier_test_mpls_spf (void) .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); @@ -345,20 +341,12 @@ bier_test_mpls_spf (void) 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); + bfmi_1_1_1_1 = bier_fmask_db_find(bti, &path_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"); + BIER_TEST(!dpo_cmp(drop_dpo_get(DPO_PROTO_MPLS), + &bfm_1_1_1_1->bfm_dpo), + "Fmask via 1.1.1.1 stacks on MPLS drop"); /* * The BIER entry should stack on the forwarding chain of the fmask @@ -369,8 +357,11 @@ bier_test_mpls_spf (void) .fmask = bfmi_1_1_1_1, }, }; - BIER_TEST(bier_test_validate_entry(bei_1, 1, &bucket_drop), - "BP:1 stacks on bier drop"); + dpo_id_t dpo_bei = DPO_INVALID; + bier_entry_contribute_forwarding(bei_1, &dpo_bei); + + BIER_TEST(!dpo_cmp(&dpo_bei, drop_dpo_get(DPO_PROTO_BIER)), + "BP:1 stacks on bier drop"); /* * give 1.1.1.1/32 a path and hence a interesting n-eos chain @@ -418,7 +409,8 @@ bier_test_mpls_spf (void) 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), + bier_entry_contribute_forwarding(bei_1, &dpo_bei); + BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1), "BP:1 stacks on fmask 1.1.1.1"); /* @@ -486,8 +478,9 @@ bier_test_mpls_spf (void) 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"); + bier_entry_contribute_forwarding(bei_2, &dpo_bei); + BIER_TEST((dpo_bei.dpoi_index == bfmi_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 @@ -506,14 +499,10 @@ bier_test_mpls_spf (void) 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, + .frp_sw_if_index = ~0, }; 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; @@ -547,7 +536,7 @@ bier_test_mpls_spf (void) 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); + bfmi_1_1_1_2 = bier_fmask_db_find(bti, &path_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, @@ -563,12 +552,14 @@ bier_test_mpls_spf (void) .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"); + bier_entry_contribute_forwarding(bei_3, &dpo_bei); + BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_2), + "BP:2 stacks on fmask 1.1.1.2"); /* * Load-balance BP:3 over both next-hops */ + paths_1_1_1_1[0] = path_1_1_1_1; bier_table_route_add(&bt_0_0_0_256, 3, paths_1_1_1_1); BIER_TEST(bier_test_validate_entry(bei_3, 2, @@ -589,13 +580,13 @@ bier_test_mpls_spf (void) /* * Withdraw one of the via FIB and thus bring down the fmask - * expect the bier0entry forwarding to remove this from the set + * expect the bier-entry 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_entry_contribute_forwarding(bei_3, &dpo_bei); + BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1), + "BP:3 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), @@ -638,9 +629,10 @@ bier_test_mpls_spf (void) * 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), + bier_entry_contribute_forwarding(bei_3, &dpo_bei); + BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1), "BP:3 stacks on fmask 1.1.1.1"); + /* * test that the ECMP choices for BP:3 have been updated */ @@ -659,7 +651,6 @@ bier_test_mpls_spf (void) 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 */ @@ -668,6 +659,7 @@ bier_test_mpls_spf (void) /* * test resources are freed */ + dpo_reset(&dpo_bei); for (ii = 0; ii < N_BIER_ECMP_TABLES; ii++) { bier_table_ecmp_unlock(l_o_bt[ii].bier.table); @@ -769,10 +761,6 @@ bier_test_mpls_imp (void) static int bier_test_mpls_disp (void) { - /* test_main_t *tm; */ - - /* tm = &test_main; */ - /* * Add the BIER Main table */ @@ -801,8 +789,9 @@ bier_test_mpls_disp (void) */ fib_route_path_t *paths_via_disp = NULL, path_via_disp = { // .frp_addr = all-zeros + .frp_proto = DPO_PROTO_BIER, .frp_bier_fib_index = bdti1, - .frp_flags = FIB_ROUTE_PATH_BIER_FMASK, + .frp_sw_if_index = ~0, }; vec_add1(paths_via_disp, path_via_disp); @@ -811,16 +800,13 @@ bier_test_mpls_disp (void) /* * 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); + bfmi_0_0_0_0 = bier_fmask_db_find(bti, &path_via_disp); 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), @@ -842,21 +828,13 @@ bier_test_mpls_disp (void) 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); + dpo_disp_entry_v4 = &bde_99->bde_fwd[BIER_HDR_PROTO_IPV4].bde_dpo; lookup_dpo_t *lkd = lookup_dpo_get(dpo_disp_entry_v4->dpoi_index); diff --git a/src/vnet/bier/bier_types.c b/src/vnet/bier/bier_types.c index 680182de597..5c812a4557d 100644 --- a/src/vnet/bier/bier_types.c +++ b/src/vnet/bier/bier_types.c @@ -160,6 +160,35 @@ bier_hdr_proto_to_dpo (bier_hdr_proto_id_t bproto) return (DPO_PROTO_NUM); } +bier_bift_id_t +bier_bift_id_encode (bier_table_set_id_t set, + bier_table_sub_domain_id_t sd, + bier_hdr_len_id_t bsl) +{ + bier_bift_id_t id; + + id = bsl; + id = id << 8; + id |= sd; + id = id << 8; + id |= set; + + return (id); +} + +void +bier_bift_id_decode (bier_bift_id_t id, + bier_table_set_id_t *set, + bier_table_sub_domain_id_t *sd, + bier_hdr_len_id_t *bsl) +{ + *set = id & 0xff; + id = id >> 8; + *sd = id & 0xff; + id = id >> 8; + *bsl = id; +} + u8 * format_bier_table_id (u8 *s, va_list *ap) { @@ -188,3 +217,17 @@ format_bier_hdr (u8 *s, va_list *ap) format_bier_hdr_proto, bier_hdr_get_proto_id(©), bier_hdr_get_src_id(©))); } + + u8* + format_bier_bift_id(u8 *s, va_list *ap) + { + bier_bift_id_t id = va_arg(*ap, bier_bift_id_t); + bier_table_sub_domain_id_t sd; + bier_table_set_id_t set; + bier_hdr_len_id_t bsl; + + bier_bift_id_decode(id, &set, &sd, &bsl); + + return (format(s, "0x%x -> set:%d sd:%d hdr-len:%U", + id, set, sd, format_bier_hdr_len_id, bsl)); + } diff --git a/src/vnet/bier/bier_types.h b/src/vnet/bier/bier_types.h index fa1cd423278..d484ba9ed03 100644 --- a/src/vnet/bier/bier_types.h +++ b/src/vnet/bier/bier_types.h @@ -504,4 +504,32 @@ extern u32 bier_hdr_len_id_to_prefix_len(bier_hdr_len_id_t id); #define BIER_ERR_PANIC 3 typedef int bier_rc; +/** + * The BIER universal 'label' + */ +typedef u32 bier_bift_id_t; + +/** + * An invalid value for the BIFT ID + * all ones implies a BSL that's invalid. + */ +#define BIER_BIFT_ID_INVALID (~0) + +extern u16 bier_bfit_id_get_sub_domain(bier_bift_id_t bift_id); +extern u16 bier_bfit_id_get_set(bier_bift_id_t bift_id); +extern bier_hdr_proto_id_t bier_bift_id_get_bit_string_length(bier_bift_id_t bift_id); + +/** + * Encode a BIFT-ID as per draft-wijnandsxu-bier-non-mpls-bift-encoding-00.txt + */ +extern bier_bift_id_t bier_bift_id_encode(bier_table_set_id_t set, + bier_table_sub_domain_id_t sd, + bier_hdr_len_id_t bsl); +extern void bier_bift_id_decode(bier_bift_id_t id, + bier_table_set_id_t *set, + bier_table_sub_domain_id_t *sd, + bier_hdr_len_id_t *bsl); + +extern u8* format_bier_bift_id(u8 *s, va_list *ap); + #endif /* __BIER_TYPES_H__ */ diff --git a/src/vnet/bier/bier_update.c b/src/vnet/bier/bier_update.c index c66090f3cba..326f8bf3f0b 100644 --- a/src/vnet/bier/bier_update.c +++ b/src/vnet/bier/bier_update.c @@ -32,6 +32,8 @@ vnet_bier_table_cmd (vlib_main_t * vm, }; u32 is_add = 0; + local_label = MPLS_LABEL_INVALID; + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) { if (unformat (input, "del")) { is_add = 0; @@ -66,7 +68,7 @@ done: VLIB_CLI_COMMAND (bier_table_command) = { .path = "bier table", - .short_help = "Add/delete BIER Tables", + .short_help = "bier table [add|del] sd set bsl [mpls