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_entry.c | 388 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 388 insertions(+) create mode 100644 src/vnet/bier/bier_entry.c (limited to 'src/vnet/bier/bier_entry.c') 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 +#include + +#include + +#include +#include +#include + +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); -- cgit 1.2.3-korg