From d792d9c01e60656cbfe1b0f1fd6a9b125f5dab0c Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Sat, 21 Oct 2017 10:53:20 -0700 Subject: BIER - see draft-ietf-bier-mpls-encapsulation-10 - midpoint, head and tail functions - supported payload protocols; IPv4 and IPv6 only. Change-Id: I59d7363bb6fdfdce8e4016a68a9c8f5a5e5791cb Signed-off-by: Neale Ranns --- src/vnet/bier/bier_table.c | 744 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 744 insertions(+) create mode 100644 src/vnet/bier/bier_table.c (limited to 'src/vnet/bier/bier_table.c') 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 + +#include +#include +#include +#include +#include + +#include +#include +#include + +/** + * 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); + } + } +} -- cgit 1.2.3-korg