From 7cd468a3d7dee7d6c92f69a0bb7061ae208ec727 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Mon, 19 Dec 2016 23:05:39 +0100 Subject: Reorganize source tree to use single autotools instance Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23 Signed-off-by: Damjan Marion --- src/vnet/fib/fib_entry_src.c | 1456 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1456 insertions(+) create mode 100644 src/vnet/fib/fib_entry_src.c (limited to 'src/vnet/fib/fib_entry_src.c') diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c new file mode 100644 index 00000000..060fac94 --- /dev/null +++ b/src/vnet/fib/fib_entry_src.c @@ -0,0 +1,1456 @@ +/* + * 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 + +/* + * per-source type vft + */ +static fib_entry_src_vft_t fib_entry_src_vft[FIB_SOURCE_MAX]; + +static fib_protocol_t +fib_entry_get_proto (const fib_entry_t * fib_entry) +{ + return (fib_entry->fe_prefix.fp_proto); +} + +void +fib_entry_src_register (fib_source_t source, + const fib_entry_src_vft_t *vft) +{ + fib_entry_src_vft[source] = *vft; +} + +static int +fib_entry_src_cmp_for_sort (void * v1, + void * v2) +{ + fib_entry_src_t *esrc1 = v1, *esrc2 = v2; + + return (esrc1->fes_src - esrc2->fes_src); +} + +void +fib_entry_src_action_init (fib_entry_t *fib_entry, + fib_source_t source) + +{ + fib_entry_src_t esrc = { + .fes_pl = FIB_NODE_INDEX_INVALID, + .fes_flags = FIB_ENTRY_SRC_FLAG_NONE, + .fes_src = source, + }; + + if (NULL != fib_entry_src_vft[source].fesv_init) + { + fib_entry_src_vft[source].fesv_init(&esrc); + } + + vec_add1(fib_entry->fe_srcs, esrc); + vec_sort_with_function(fib_entry->fe_srcs, + fib_entry_src_cmp_for_sort); +} + +static fib_entry_src_t * +fib_entry_src_find (const fib_entry_t *fib_entry, + fib_source_t source, + u32 *index) + +{ + fib_entry_src_t *esrc; + int ii; + + ii = 0; + vec_foreach(esrc, fib_entry->fe_srcs) + { + if (esrc->fes_src == source) + { + if (NULL != index) + { + *index = ii; + } + return (esrc); + } + else + { + ii++; + } + } + + return (NULL); +} + +int +fib_entry_is_sourced (fib_node_index_t fib_entry_index, + fib_source_t source) +{ + fib_entry_t *fib_entry; + + fib_entry = fib_entry_get(fib_entry_index); + + return (NULL != fib_entry_src_find(fib_entry, source, NULL)); +} + +static fib_entry_src_t * +fib_entry_src_find_or_create (fib_entry_t *fib_entry, + fib_source_t source, + u32 *index) +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL == esrc) + { + fib_entry_src_action_init(fib_entry, source); + } + + return (fib_entry_src_find(fib_entry, source, NULL)); +} + +void +fib_entry_src_action_deinit (fib_entry_t *fib_entry, + fib_source_t source) + +{ + fib_entry_src_t *esrc; + u32 index = ~0; + + esrc = fib_entry_src_find(fib_entry, source, &index); + + ASSERT(NULL != esrc); + + if (NULL != fib_entry_src_vft[source].fesv_deinit) + { + fib_entry_src_vft[source].fesv_deinit(esrc); + } + + vec_free(esrc->fes_path_exts); + vec_del1(fib_entry->fe_srcs, index); +} + +fib_entry_src_cover_res_t +fib_entry_src_action_cover_change (fib_entry_t *fib_entry, + fib_source_t source) +{ + if (NULL != fib_entry_src_vft[source].fesv_cover_change) + { + return (fib_entry_src_vft[source].fesv_cover_change( + fib_entry_src_find(fib_entry, source, NULL), + fib_entry)); + } + + fib_entry_src_cover_res_t res = { + .install = !0, + .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE, + }; + return (res); +} + +fib_entry_src_cover_res_t +fib_entry_src_action_cover_update (fib_entry_t *fib_entry, + fib_source_t source) +{ + if (NULL != fib_entry_src_vft[source].fesv_cover_update) + { + return (fib_entry_src_vft[source].fesv_cover_update( + fib_entry_src_find(fib_entry, source, NULL), + fib_entry)); + } + + fib_entry_src_cover_res_t res = { + .install = !0, + .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE, + }; + return (res); +} + +typedef struct fib_entry_src_collect_forwarding_ctx_t_ +{ + load_balance_path_t * next_hops; + const fib_entry_t *fib_entry; + const fib_entry_src_t *esrc; + fib_forward_chain_type_t fct; + int is_recursive; +} fib_entry_src_collect_forwarding_ctx_t; + +/** + * @brief Determine whether this FIB entry should use a load-balance MAP + * to support PIC edge fast convergence + */ +load_balance_flags_t +fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx) +{ + /** + * We'll use a LB map is the path-list has recursive paths. + * recursive paths implies BGP, and hence scale. + */ + if (ctx->is_recursive) + { + return (LOAD_BALANCE_FLAG_USES_MAP); + } + return (LOAD_BALANCE_FLAG_NONE); +} + +static int +fib_entry_src_valid_out_label (mpls_label_t label) +{ + return ((MPLS_LABEL_IS_REAL(label) || + MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL == label || + MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL == label || + MPLS_IETF_IMPLICIT_NULL_LABEL == label)); +} + +/** + * @brief Turn the chain type requested by the client into the one they + * really wanted + */ +fib_forward_chain_type_t +fib_entry_chain_type_fixup (const fib_entry_t *entry, + fib_forward_chain_type_t fct) +{ + ASSERT(FIB_FORW_CHAIN_TYPE_MPLS_EOS == fct); + + /* + * The EOS chain is a tricky since one cannot know the adjacency + * to link to without knowing what the packets payload protocol + * will be once the label is popped. + */ + fib_forward_chain_type_t dfct; + + dfct = fib_entry_get_default_chain_type(entry); + + if (FIB_FORW_CHAIN_TYPE_MPLS_EOS == dfct) + { + /* + * If the entry being asked is a eos-MPLS label entry, + * then use the payload-protocol field, that we stashed there + * for just this purpose + */ + return (fib_forw_chain_type_from_dpo_proto( + entry->fe_prefix.fp_payload_proto)); + } + /* + * else give them what this entry would be by default. i.e. if it's a v6 + * entry, then the label its local labelled should be carrying v6 traffic. + * If it's a non-EOS label entry, then there are more labels and we want + * a non-eos chain. + */ + return (dfct); +} + +static int +fib_entry_src_collect_forwarding (fib_node_index_t pl_index, + fib_node_index_t path_index, + void *arg) +{ + fib_entry_src_collect_forwarding_ctx_t *ctx; + fib_path_ext_t *path_ext; + + ctx = arg; + + /* + * if the path is not resolved, don't include it. + */ + if (!fib_path_is_resolved(path_index)) + { + return (!0); + } + + if (fib_path_is_recursive(path_index)) + { + ctx->is_recursive = 1; + } + + /* + * get the matching path-extension for the path being visited. + */ + vec_foreach(path_ext, ctx->esrc->fes_path_exts) + { + if (path_ext->fpe_path_index == path_index) + break; + } + + if (NULL != path_ext && + path_ext->fpe_path_index == path_index && + fib_entry_src_valid_out_label(path_ext->fpe_label_stack[0])) + { + /* + * found a matching extension. stack it to obtain the forwarding + * info for this path. + */ + ctx->next_hops = fib_path_ext_stack(path_ext, ctx->fib_entry, ctx->fct, ctx->next_hops); + } + else + { + load_balance_path_t *nh; + + /* + * no extension => no out-going label for this path. that's OK + * in the case of an IP or EOS chain, but not for non-EOS + */ + switch (ctx->fct) + { + case FIB_FORW_CHAIN_TYPE_UNICAST_IP4: + case FIB_FORW_CHAIN_TYPE_UNICAST_IP6: + /* + * EOS traffic with no label to stack, we need the IP Adj + */ + vec_add2(ctx->next_hops, nh, 1); + + nh->path_index = path_index; + nh->path_weight = fib_path_get_weight(path_index); + fib_path_contribute_forwarding(path_index, ctx->fct, &nh->path_dpo); + + break; + case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS: + if (fib_path_is_exclusive(path_index) || + fib_path_is_deag(path_index)) + { + vec_add2(ctx->next_hops, nh, 1); + + nh->path_index = path_index; + nh->path_weight = fib_path_get_weight(path_index); + fib_path_contribute_forwarding(path_index, + FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS, + &nh->path_dpo); + } + break; + case FIB_FORW_CHAIN_TYPE_MPLS_EOS: + { + /* + * no label. we need a chain based on the payload. fixup. + */ + vec_add2(ctx->next_hops, nh, 1); + + nh->path_index = path_index; + nh->path_weight = fib_path_get_weight(path_index); + fib_path_contribute_forwarding(path_index, + fib_entry_chain_type_fixup(ctx->fib_entry, + ctx->fct), + &nh->path_dpo); + + break; + } + case FIB_FORW_CHAIN_TYPE_ETHERNET: + ASSERT(0); + break; + } + } + + return (!0); +} + +void +fib_entry_src_mk_lb (fib_entry_t *fib_entry, + const fib_entry_src_t *esrc, + fib_forward_chain_type_t fct, + dpo_id_t *dpo_lb) +{ + dpo_proto_t lb_proto; + + /* + * If the entry has path extensions then we construct a load-balance + * by stacking the extensions on the forwarding chains of the paths. + * Otherwise we use the load-balance of the path-list + */ + fib_entry_src_collect_forwarding_ctx_t ctx = { + .esrc = esrc, + .fib_entry = fib_entry, + .next_hops = NULL, + .is_recursive = 0, + .fct = fct, + }; + + lb_proto = fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto); + + fib_path_list_walk(esrc->fes_pl, + fib_entry_src_collect_forwarding, + &ctx); + + if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE) + { + /* + * the client provided the DPO that the entry should link to. + * all entries must link to a LB, so if it is an LB already + * then we can use it. + */ + if ((1 == vec_len(ctx.next_hops)) && + (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type)) + { + dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo); + dpo_reset(&ctx.next_hops[0].path_dpo); + return; + } + } + + if (!dpo_id_is_valid(dpo_lb)) + { + /* + * first time create + */ + flow_hash_config_t fhc; + + fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index, + dpo_proto_to_fib(lb_proto)); + dpo_set(dpo_lb, + DPO_LOAD_BALANCE, + lb_proto, + load_balance_create(0, lb_proto, fhc)); + } + + load_balance_multipath_update(dpo_lb, + ctx.next_hops, + fib_entry_calc_lb_flags(&ctx)); + vec_free(ctx.next_hops); + + /* + * if this entry is sourced by the uRPF-exempt source then we + * append the always present local0 interface (index 0) to the + * uRPF list so it is not empty. that way packets pass the loose check. + */ + index_t ui = fib_path_list_get_urpf(esrc->fes_pl); + + if (fib_entry_is_sourced(fib_entry_get_index(fib_entry), + FIB_SOURCE_URPF_EXEMPT) && + (0 == fib_urpf_check_size(ui))) + { + /* + * The uRPF list we get from the path-list is shared by all + * other users of the list, but the uRPF exemption applies + * only to this prefix. So we need our own list. + */ + ui = fib_urpf_list_alloc_and_lock(); + fib_urpf_list_append(ui, 0); + fib_urpf_list_bake(ui); + load_balance_set_urpf(dpo_lb->dpoi_index, ui); + fib_urpf_list_unlock(ui); + } + else + { + load_balance_set_urpf(dpo_lb->dpoi_index, ui); + } +} + +void +fib_entry_src_action_install (fib_entry_t *fib_entry, + fib_source_t source) +{ + /* + * Install the forwarding chain for the given source into the forwarding + * tables + */ + fib_forward_chain_type_t fct; + fib_entry_src_t *esrc; + int insert; + + fct = fib_entry_get_default_chain_type(fib_entry); + esrc = fib_entry_src_find(fib_entry, source, NULL); + + /* + * Every entry has its own load-balance object. All changes to the entry's + * forwarding result in an inplace modify of the load-balance. This means + * the load-balance object only needs to be added to the forwarding + * DB once, when it is created. + */ + insert = !dpo_id_is_valid(&fib_entry->fe_lb); + + fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb); + + ASSERT(dpo_id_is_valid(&fib_entry->fe_lb)); + FIB_ENTRY_DBG(fib_entry, "install: %d", fib_entry->fe_lb); + + /* + * insert the adj into the data-plane forwarding trie + */ + if (insert) + { + fib_table_fwding_dpo_update(fib_entry->fe_fib_index, + &fib_entry->fe_prefix, + &fib_entry->fe_lb); + } + + /* + * if any of the other chain types are already created they will need + * updating too + */ + fib_entry_delegate_type_t fdt; + fib_entry_delegate_t *fed; + + FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed, + { + fib_entry_src_mk_lb(fib_entry, esrc, + fib_entry_delegate_type_to_chain_type(fdt), + &fed->fd_dpo); + }); +} + +void +fib_entry_src_action_uninstall (fib_entry_t *fib_entry) +{ + /* + * uninstall the forwarding chain from the forwarding tables + */ + FIB_ENTRY_DBG(fib_entry, "uninstall: %d", + fib_entry->fe_adj_index); + + if (dpo_id_is_valid(&fib_entry->fe_lb)) + { + fib_table_fwding_dpo_remove( + fib_entry->fe_fib_index, + &fib_entry->fe_prefix, + &fib_entry->fe_lb); + + dpo_reset(&fib_entry->fe_lb); + } +} + +static void +fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index) +{ + fib_node_index_t *entries = NULL; + + fib_path_list_recursive_loop_detect(path_list_index, &entries); + + vec_free(entries); +} + +void +fib_entry_src_action_activate (fib_entry_t *fib_entry, + fib_source_t source) + +{ + int houston_we_are_go_for_install; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)); + ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED); + + esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE; + + if (NULL != fib_entry_src_vft[source].fesv_activate) + { + houston_we_are_go_for_install = + fib_entry_src_vft[source].fesv_activate(esrc, fib_entry); + } + else + { + /* + * the source is not providing an activate function, we'll assume + * therefore it has no objection to installing the entry + */ + houston_we_are_go_for_install = !0; + } + + /* + * link to the path-list provided by the source, and go check + * if that forms any loops in the graph. + */ + fib_entry->fe_parent = esrc->fes_pl; + fib_entry->fe_sibling = + fib_path_list_child_add(fib_entry->fe_parent, + FIB_NODE_TYPE_ENTRY, + fib_entry_get_index(fib_entry)); + + fib_entry_recursive_loop_detect_i(fib_entry->fe_parent); + + FIB_ENTRY_DBG(fib_entry, "activate: %d", + fib_entry->fe_parent); + + if (0 != houston_we_are_go_for_install) + { + fib_entry_src_action_install(fib_entry, source); + } + else + { + fib_entry_src_action_uninstall(fib_entry); + } +} + +void +fib_entry_src_action_deactivate (fib_entry_t *fib_entry, + fib_source_t source) + +{ + fib_node_index_t path_list_index; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE); + + if (NULL != fib_entry_src_vft[source].fesv_deactivate) + { + fib_entry_src_vft[source].fesv_deactivate(esrc, fib_entry); + } + + esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE; + + FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent); + + /* + * un-link from an old path-list. Check for any loops this will clear + */ + path_list_index = fib_entry->fe_parent; + fib_entry->fe_parent = FIB_NODE_INDEX_INVALID; + + fib_entry_recursive_loop_detect_i(path_list_index); + + /* + * this will unlock the path-list, so it may be invalid thereafter. + */ + fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling); + fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID; +} + +static void +fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry, + fib_source_t source) +{ + fib_entry_src_t *esrc; + + vec_foreach(esrc, fib_entry->fe_srcs) + { + if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update) + { + fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc, + fib_entry, + source); + } + } +} + +void +fib_entry_src_action_reactivate (fib_entry_t *fib_entry, + fib_source_t source) +{ + fib_node_index_t path_list_index; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE); + + FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d", + fib_entry->fe_parent, + esrc->fes_pl); + + if (fib_entry->fe_parent != esrc->fes_pl) + { + /* + * un-link from an old path-list. Check for any loops this will clear + */ + path_list_index = fib_entry->fe_parent; + fib_entry->fe_parent = FIB_NODE_INDEX_INVALID; + + /* + * temporary lock so it doesn't get deleted when this entry is no + * longer a child. + */ + fib_path_list_lock(path_list_index); + + /* + * this entry is no longer a child. after unlinking check if any loops + * were broken + */ + fib_path_list_child_remove(path_list_index, + fib_entry->fe_sibling); + + fib_entry_recursive_loop_detect_i(path_list_index); + + /* + * link to the path-list provided by the source, and go check + * if that forms any loops in the graph. + */ + fib_entry->fe_parent = esrc->fes_pl; + fib_entry->fe_sibling = + fib_path_list_child_add(fib_entry->fe_parent, + FIB_NODE_TYPE_ENTRY, + fib_entry_get_index(fib_entry)); + + fib_entry_recursive_loop_detect_i(fib_entry->fe_parent); + fib_path_list_unlock(path_list_index); + } + fib_entry_src_action_install(fib_entry, source); + fib_entry_src_action_fwd_update(fib_entry, source); +} + +void +fib_entry_src_action_installed (const fib_entry_t *fib_entry, + fib_source_t source) +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != fib_entry_src_vft[source].fesv_installed) + { + fib_entry_src_vft[source].fesv_installed(esrc, + fib_entry); + } + + fib_entry_src_action_fwd_update(fib_entry, source); +} + +/* + * fib_entry_src_action_add + * + * Adding a source can result in a new fib_entry being created, which + * can inturn mean the pool is realloc'd and thus the entry passed as + * an argument it also realloc'd + * @return the original entry + */ +fib_entry_t * +fib_entry_src_action_add (fib_entry_t *fib_entry, + fib_source_t source, + fib_entry_flag_t flags, + const dpo_id_t *dpo) +{ + fib_node_index_t fib_entry_index; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find_or_create(fib_entry, source, NULL); + + esrc->fes_ref_count++; + + if (1 != esrc->fes_ref_count) + { + /* + * we only want to add the source on the 0->1 transition + */ + return (fib_entry); + } + + esrc->fes_entry_flags = flags; + + /* + * save variable so we can recover from a fib_entry realloc. + */ + fib_entry_index = fib_entry_get_index(fib_entry); + + if (NULL != fib_entry_src_vft[source].fesv_add) + { + fib_entry_src_vft[source].fesv_add(esrc, + fib_entry, + flags, + fib_entry_get_proto(fib_entry), + dpo); + } + + fib_entry = fib_entry_get(fib_entry_index); + + esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED; + + fib_path_list_lock(esrc->fes_pl); + + /* + * the source owns a lock on the entry + */ + fib_entry_lock(fib_entry_get_index(fib_entry)); + + return (fib_entry); +} + +/* + * fib_entry_src_action_update + * + * Adding a source can result in a new fib_entry being created, which + * can inturn mean the pool is realloc'd and thus the entry passed as + * an argument it also realloc'd + * @return the original entry + */ +fib_entry_t * +fib_entry_src_action_update (fib_entry_t *fib_entry, + fib_source_t source, + fib_entry_flag_t flags, + const dpo_id_t *dpo) +{ + fib_node_index_t fib_entry_index, old_path_list_index; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find_or_create(fib_entry, source, NULL); + + if (NULL == esrc) + return (fib_entry_src_action_add(fib_entry, source, flags, dpo)); + + old_path_list_index = esrc->fes_pl; + esrc->fes_entry_flags = flags; + + /* + * save variable so we can recover from a fib_entry realloc. + */ + fib_entry_index = fib_entry_get_index(fib_entry); + + if (NULL != fib_entry_src_vft[source].fesv_add) + { + fib_entry_src_vft[source].fesv_add(esrc, + fib_entry, + flags, + fib_entry_get_proto(fib_entry), + dpo); + } + + fib_entry = fib_entry_get(fib_entry_index); + + esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED; + + fib_path_list_lock(esrc->fes_pl); + fib_path_list_unlock(old_path_list_index); + + return (fib_entry); +} + + +fib_entry_src_flag_t +fib_entry_src_action_remove (fib_entry_t *fib_entry, + fib_source_t source) + +{ + fib_node_index_t old_path_list; + fib_entry_src_flag_t sflags; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL == esrc) + return (FIB_ENTRY_SRC_FLAG_ACTIVE); + + esrc->fes_ref_count--; + sflags = esrc->fes_flags; + + if (0 != esrc->fes_ref_count) + { + /* + * only remove the source on the 1->0 transisition + */ + return (sflags); + } + + if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE) + { + fib_entry_src_action_deactivate(fib_entry, source); + } + + old_path_list = esrc->fes_pl; + + if (NULL != fib_entry_src_vft[source].fesv_remove) + { + fib_entry_src_vft[source].fesv_remove(esrc); + } + + fib_path_list_unlock(old_path_list); + fib_entry_unlock(fib_entry_get_index(fib_entry)); + + sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED; + fib_entry_src_action_deinit(fib_entry, source); + + return (sflags); +} + +static inline int +fib_route_recurses_via_self (const fib_prefix_t *prefix, + const fib_route_path_t *rpath) +{ + /* + * not all zeros next hop && + * is recursive path && + * nexthop is same as the route's address + */ + return ((!ip46_address_is_zero(&rpath->frp_addr)) && + (~0 == rpath->frp_sw_if_index) && + (0 == ip46_address_cmp(&rpath->frp_addr, &prefix->fp_addr))); + +} + +/* + * fib_route_attached_cross_table + * + * Return true the the route is attached via an interface that + * is not in the same table as the route + */ +static inline int +fib_route_attached_cross_table (const fib_entry_t *fib_entry, + const fib_route_path_t *rpath) +{ + /* + * - All zeros next-hop + * - a valid interface + * - entry's fib index not equeal to interface's index + */ + if (ip46_address_is_zero(&rpath->frp_addr) && + (~0 != rpath->frp_sw_if_index) && + (fib_entry->fe_fib_index != + fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry), + rpath->frp_sw_if_index))) + { + return (!0); + } + return (0); +} + +/* + * fib_route_attached_cross_table + * + * Return true the the route is attached via an interface that + * is not in the same table as the route + */ +static inline int +fib_path_is_attached (const fib_route_path_t *rpath) +{ + /* + * - All zeros next-hop + * - a valid interface + */ + if (ip46_address_is_zero(&rpath->frp_addr) && + (~0 != rpath->frp_sw_if_index)) + { + return (!0); + } + return (0); +} + +fib_path_list_flags_t +fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags) +{ + fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE; + + if (eflags & FIB_ENTRY_FLAG_DROP) + { + plf |= FIB_PATH_LIST_FLAG_DROP; + } + if (eflags & FIB_ENTRY_FLAG_LOCAL) + { + plf |= FIB_PATH_LIST_FLAG_LOCAL; + } + if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE) + { + plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE; + } + + return (plf); +} + +static void +fib_entry_flags_update (const fib_entry_t *fib_entry, + const fib_route_path_t *rpath, + fib_path_list_flags_t *pl_flags, + fib_entry_src_t *esrc) +{ + /* + * don't allow the addition of a recursive looped path for prefix + * via itself. + */ + if (fib_route_recurses_via_self(&fib_entry->fe_prefix, rpath)) + { + /* + * force the install of a drop path-list. + * we want the entry to have some path-list, mainly so + * the dodgy path can be rmeoved when the source stops playing + * silly buggers. + */ + *pl_flags |= FIB_PATH_LIST_FLAG_DROP; + } + else + { + *pl_flags &= ~FIB_PATH_LIST_FLAG_DROP; + } + + if ((esrc->fes_src == FIB_SOURCE_API) || + (esrc->fes_src == FIB_SOURCE_CLI)) + { + if (fib_path_is_attached(rpath)) + { + esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED; + } + else + { + esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED; + } + } + if (fib_route_attached_cross_table(fib_entry, rpath)) + { + esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT; + } + else + { + esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT; + } +} + +/* + * fib_entry_src_path_ext_add + * + * append a path extension to the entry's list + */ +static void +fib_entry_src_path_ext_append (fib_entry_src_t *esrc, + const fib_route_path_t *rpath) +{ + if (NULL != rpath->frp_label_stack) + { + fib_path_ext_t *path_ext; + + vec_add2(esrc->fes_path_exts, path_ext, 1); + + fib_path_ext_init(path_ext, esrc->fes_pl, rpath); + } +} + +/* + * fib_entry_src_path_ext_insert + * + * insert, sorted, a path extension to the entry's list. + * It's not strictly necessary in sort the path extensions, since each + * extension has the path index to which it resolves. However, by being + * sorted the load-balance produced has a deterministic order, not an order + * based on the sequence of extension additions. this is a considerable benefit. + */ +static void +fib_entry_src_path_ext_insert (fib_entry_src_t *esrc, + const fib_route_path_t *rpath) +{ + if (0 == vec_len(esrc->fes_path_exts)) + return (fib_entry_src_path_ext_append(esrc, rpath)); + + if (NULL != rpath->frp_label_stack) + { + fib_path_ext_t path_ext; + int i = 0; + + fib_path_ext_init(&path_ext, esrc->fes_pl, rpath); + + while (i < vec_len(esrc->fes_path_exts) && + (fib_path_ext_cmp(&esrc->fes_path_exts[i], rpath) < 0)) + { + i++; + } + + vec_insert_elts(esrc->fes_path_exts, &path_ext, 1, i); + } +} + +/* + * fib_entry_src_action_add + * + * Adding a source can result in a new fib_entry being created, which + * can inturn mean the pool is realloc'd and thus the entry passed as + * an argument it also realloc'd + * @return the entry + */ +fib_entry_t* +fib_entry_src_action_path_add (fib_entry_t *fib_entry, + fib_source_t source, + fib_entry_flag_t flags, + const fib_route_path_t *rpath) +{ + fib_node_index_t old_path_list, fib_entry_index; + fib_path_list_flags_t pl_flags; + fib_path_ext_t *path_ext; + fib_entry_src_t *esrc; + + /* + * save variable so we can recover from a fib_entry realloc. + */ + fib_entry_index = fib_entry_get_index(fib_entry); + + esrc = fib_entry_src_find(fib_entry, source, NULL); + if (NULL == esrc) + { + fib_entry = + fib_entry_src_action_add(fib_entry, + source, + flags, + drop_dpo_get( + fib_proto_to_dpo( + fib_entry_get_proto(fib_entry)))); + esrc = fib_entry_src_find(fib_entry, source, NULL); + } + + /* + * we are no doubt modifying a path-list. If the path-list + * is shared, and hence not modifiable, then the index returned + * will be for a different path-list. This FIB entry to needs + * to maintain its lock appropriately. + */ + old_path_list = esrc->fes_pl; + + ASSERT(NULL != fib_entry_src_vft[source].fesv_path_add); + + pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry)); + fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc); + + fib_entry_src_vft[source].fesv_path_add(esrc, fib_entry, pl_flags, rpath); + fib_entry = fib_entry_get(fib_entry_index); + + /* + * re-resolve all the path-extensions with the new path-list + */ + vec_foreach(path_ext, esrc->fes_path_exts) + { + fib_path_ext_resolve(path_ext, esrc->fes_pl); + } + /* + * if the path has a label we need to add a path extension + */ + fib_entry_src_path_ext_insert(esrc, rpath); + + fib_path_list_lock(esrc->fes_pl); + fib_path_list_unlock(old_path_list); + + return (fib_entry); +} + +/* + * fib_entry_src_action_swap + * + * The source is providing new paths to replace the old ones. + * Adding a source can result in a new fib_entry being created, which + * can inturn mean the pool is realloc'd and thus the entry passed as + * an argument it also realloc'd + * @return the entry + */ +fib_entry_t* +fib_entry_src_action_path_swap (fib_entry_t *fib_entry, + fib_source_t source, + fib_entry_flag_t flags, + const fib_route_path_t *rpaths) +{ + fib_node_index_t old_path_list, fib_entry_index; + fib_path_list_flags_t pl_flags; + const fib_route_path_t *rpath; + fib_path_ext_t *path_ext; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + /* + * save variable so we can recover from a fib_entry realloc. + */ + fib_entry_index = fib_entry_get_index(fib_entry); + + if (NULL == esrc) + { + fib_entry = fib_entry_src_action_add(fib_entry, + source, + flags, + drop_dpo_get( + fib_proto_to_dpo( + fib_entry_get_proto(fib_entry)))); + esrc = fib_entry_src_find(fib_entry, source, NULL); + } + + /* + * swapping paths may create a new path-list (or may use an existing shared) + * but we are certainly getting a different one. This FIB entry to needs + * to maintain its lock appropriately. + */ + old_path_list = esrc->fes_pl; + + ASSERT(NULL != fib_entry_src_vft[source].fesv_path_swap); + + pl_flags = fib_entry_src_flags_2_path_list_flags(flags); + + vec_foreach(rpath, rpaths) + { + fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc); + } + + fib_entry_src_vft[source].fesv_path_swap(esrc, + fib_entry, + pl_flags, + rpaths); + + vec_foreach(path_ext, esrc->fes_path_exts) + { + vec_free(path_ext->fpe_label_stack); + } + vec_free(esrc->fes_path_exts); + + vec_foreach(rpath, rpaths) + { + fib_entry_src_path_ext_append(esrc, rpath); + } + + fib_entry = fib_entry_get(fib_entry_index); + + fib_path_list_lock(esrc->fes_pl); + fib_path_list_unlock(old_path_list); + + return (fib_entry); +} + +fib_entry_src_flag_t +fib_entry_src_action_path_remove (fib_entry_t *fib_entry, + fib_source_t source, + const fib_route_path_t *rpath) +{ + fib_path_list_flags_t pl_flags; + fib_node_index_t old_path_list; + fib_path_ext_t *path_ext; + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + ASSERT(NULL != esrc); + ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED); + + /* + * we no doubt modifying a path-list. If the path-list + * is shared, and hence not modifiable, then the index returned + * will be for a different path-list. This FIB entry to needs + * to maintain its lock appropriately. + */ + old_path_list = esrc->fes_pl; + + ASSERT(NULL != fib_entry_src_vft[source].fesv_path_remove); + + pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry)); + fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc); + + fib_entry_src_vft[source].fesv_path_remove(esrc, pl_flags, rpath); + /* + * find the matching path extension and remove it + */ + vec_foreach(path_ext, esrc->fes_path_exts) + { + if (!fib_path_ext_cmp(path_ext, rpath)) + { + /* + * delete the element moving the remaining elements down 1 position. + * this preserves the sorted order. + */ + vec_free(path_ext->fpe_label_stack); + vec_delete(esrc->fes_path_exts, 1, (path_ext - esrc->fes_path_exts)); + break; + } + } + /* + * re-resolve all the path-extensions with the new path-list + */ + vec_foreach(path_ext, esrc->fes_path_exts) + { + fib_path_ext_resolve(path_ext, esrc->fes_pl); + } + + /* + * lock the new path-list, unlock the old if it had one + */ + fib_path_list_unlock(old_path_list); + + if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) { + fib_path_list_lock(esrc->fes_pl); + return (FIB_ENTRY_SRC_FLAG_ADDED); + } + else + { + /* + * no more paths left from this source + */ + fib_entry_src_action_remove(fib_entry, source); + return (FIB_ENTRY_SRC_FLAG_NONE); + } +} + +u8* +fib_entry_src_format (fib_entry_t *fib_entry, + fib_source_t source, + u8* s) +{ + fib_entry_src_t *esrc; + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != fib_entry_src_vft[source].fesv_format) + { + return (fib_entry_src_vft[source].fesv_format(esrc, s)); + } + return (s); +} + +adj_index_t +fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index, + fib_source_t source) +{ + fib_entry_t *fib_entry; + fib_entry_src_t *esrc; + + if (FIB_NODE_INDEX_INVALID == fib_entry_index) + return (ADJ_INDEX_INVALID); + + fib_entry = fib_entry_get(fib_entry_index); + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != esrc) + { + if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) + { + return (fib_path_list_get_adj( + esrc->fes_pl, + fib_entry_get_default_chain_type(fib_entry))); + } + } + return (ADJ_INDEX_INVALID); +} + +const int +fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index, + fib_source_t source, + dpo_id_t *dpo) +{ + fib_entry_t *fib_entry; + fib_entry_src_t *esrc; + + if (FIB_NODE_INDEX_INVALID == fib_entry_index) + return (0); + + fib_entry = fib_entry_get(fib_entry_index); + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != esrc) + { + if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) + { + fib_path_list_contribute_forwarding( + esrc->fes_pl, + fib_entry_get_default_chain_type(fib_entry), + dpo); + + return (dpo_id_is_valid(dpo)); + } + } + return (0); +} + +u32 +fib_entry_get_resolving_interface_for_source (fib_node_index_t entry_index, + fib_source_t source) +{ + fib_entry_t *fib_entry; + fib_entry_src_t *esrc; + + fib_entry = fib_entry_get(entry_index); + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != esrc) + { + if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) + { + return (fib_path_list_get_resolving_interface(esrc->fes_pl)); + } + } + return (~0); +} + +fib_entry_flag_t +fib_entry_get_flags_for_source (fib_node_index_t entry_index, + fib_source_t source) +{ + fib_entry_t *fib_entry; + fib_entry_src_t *esrc; + + fib_entry = fib_entry_get(entry_index); + + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != esrc) + { + return (esrc->fes_entry_flags); + } + + return (FIB_ENTRY_FLAG_NONE); +} + +fib_entry_flag_t +fib_entry_get_flags_i (const fib_entry_t *fib_entry) +{ + fib_entry_flag_t flags; + + /* + * the vector of sources is deliberately arranged in priority order + */ + if (0 == vec_len(fib_entry->fe_srcs)) + { + flags = FIB_ENTRY_FLAG_NONE; + } + else + { + fib_entry_src_t *esrc; + + esrc = vec_elt_at_index(fib_entry->fe_srcs, 0); + flags = esrc->fes_entry_flags; + } + + return (flags); +} + +void +fib_entry_set_source_data (fib_node_index_t fib_entry_index, + fib_source_t source, + const void *data) +{ + fib_entry_t *fib_entry; + fib_entry_src_t *esrc; + + fib_entry = fib_entry_get(fib_entry_index); + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != esrc && + NULL != fib_entry_src_vft[source].fesv_set_data) + { + fib_entry_src_vft[source].fesv_set_data(esrc, fib_entry, data); + } +} + +const void* +fib_entry_get_source_data (fib_node_index_t fib_entry_index, + fib_source_t source) +{ + fib_entry_t *fib_entry; + fib_entry_src_t *esrc; + + fib_entry = fib_entry_get(fib_entry_index); + esrc = fib_entry_src_find(fib_entry, source, NULL); + + if (NULL != esrc && + NULL != fib_entry_src_vft[source].fesv_get_data) + { + return (fib_entry_src_vft[source].fesv_get_data(esrc, fib_entry)); + } + return (NULL); +} + +void +fib_entry_src_module_init (void) +{ + fib_entry_src_rr_register(); + fib_entry_src_interface_register(); + fib_entry_src_default_route_register(); + fib_entry_src_special_register(); + fib_entry_src_api_register(); + fib_entry_src_adj_register(); + fib_entry_src_mpls_register(); + fib_entry_src_lisp_register(); +} -- cgit 1.2.3-korg From c0790cfef0bd1c56f4c75dc4f959584148386258 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Thu, 5 Jan 2017 01:01:47 -0800 Subject: FIB memory leaks (VPP-578) 1) vec_free the fe_srcs of a fib_entry_t when the fib_entry_t is itself reed 2) in the load-balance fixup if a drop path is required add this to a new vector of next-hops 'fixed_nhs'. This vector is managed by the load-balance function. The caller continues to manage its own set. The function is now const implying that the caller is safe to assume the next-hops do not change. Change-Id: I0f29203ee16b9a270f40edf237488fa99ba65320 Signed-off-by: Neale Ranns Signed-off-by: Neale Ranns --- src/vnet/dpo/load_balance.c | 33 ++++++++++++++++++--------------- src/vnet/dpo/load_balance.h | 2 +- src/vnet/fib/fib_entry.c | 1 + src/vnet/fib/fib_entry_src.c | 8 ++++++++ src/vnet/fib/fib_path_list.c | 26 ++++++++++++++++++-------- src/vnet/fib/fib_path_list.h | 2 ++ 6 files changed, 48 insertions(+), 24 deletions(-) (limited to 'src/vnet/fib/fib_entry_src.c') diff --git a/src/vnet/dpo/load_balance.c b/src/vnet/dpo/load_balance.c index a244776f..e70a7a30 100644 --- a/src/vnet/dpo/load_balance.c +++ b/src/vnet/dpo/load_balance.c @@ -279,8 +279,8 @@ load_balance_get_bucket (index_t lbi, } static int -next_hop_sort_by_weight (load_balance_path_t * n1, - load_balance_path_t * n2) +next_hop_sort_by_weight (const load_balance_path_t * n1, + const load_balance_path_t * n2) { return ((int) n1->path_weight - (int) n2->path_weight); } @@ -289,7 +289,7 @@ next_hop_sort_by_weight (load_balance_path_t * n1, with weights corresponding to the number of adjacencies for each next hop. Returns number of adjacencies in block. */ u32 -ip_multipath_normalize_next_hops (load_balance_path_t * raw_next_hops, +ip_multipath_normalize_next_hops (const load_balance_path_t * raw_next_hops, load_balance_path_t ** normalized_next_hops, u32 *sum_weight_in, f64 multipath_next_hop_error_tolerance) @@ -409,23 +409,25 @@ done: } static load_balance_path_t * -load_balance_multipath_next_hop_fixup (load_balance_path_t *nhs, +load_balance_multipath_next_hop_fixup (const load_balance_path_t *nhs, dpo_proto_t drop_proto) { if (0 == vec_len(nhs)) { - load_balance_path_t *nh; + load_balance_path_t *new_nhs = NULL, *nh; /* * we need something for the load-balance. so use the drop */ - vec_add2(nhs, nh, 1); + vec_add2(new_nhs, nh, 1); nh->path_weight = 1; dpo_copy(&nh->path_dpo, drop_dpo_get(drop_proto)); + + return (new_nhs); } - return (nhs); + return (NULL); } /* @@ -467,11 +469,11 @@ load_balance_set_n_buckets (load_balance_t *lb, void load_balance_multipath_update (const dpo_id_t *dpo, - load_balance_path_t * raw_next_hops, + const load_balance_path_t * raw_nhs, load_balance_flags_t flags) { - u32 sum_of_weights,n_buckets, ii; - load_balance_path_t * nh, * nhs; + load_balance_path_t *nh, *nhs, *fixed_nhs; + u32 sum_of_weights, n_buckets, ii; index_t lbmi, old_lbmi; load_balance_t *lb; dpo_id_t *tmp_dpo; @@ -480,16 +482,16 @@ load_balance_multipath_update (const dpo_id_t *dpo, ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type); lb = load_balance_get(dpo->dpoi_index); - raw_next_hops = - load_balance_multipath_next_hop_fixup(raw_next_hops, - lb->lb_proto); + fixed_nhs = load_balance_multipath_next_hop_fixup(raw_nhs, lb->lb_proto); n_buckets = - ip_multipath_normalize_next_hops(raw_next_hops, + ip_multipath_normalize_next_hops((NULL == fixed_nhs ? + raw_nhs : + fixed_nhs), &nhs, &sum_of_weights, multipath_next_hop_error_tolerance); - ASSERT (n_buckets >= vec_len (raw_next_hops)); + ASSERT (n_buckets >= vec_len (raw_nhs)); /* * Save the old load-balance map used, and get a new one if required. @@ -694,6 +696,7 @@ load_balance_multipath_update (const dpo_id_t *dpo, dpo_reset(&nh->path_dpo); } vec_free(nhs); + vec_free(fixed_nhs); load_balance_map_unlock(old_lbmi); } diff --git a/src/vnet/dpo/load_balance.h b/src/vnet/dpo/load_balance.h index dc6485e6..17996536 100644 --- a/src/vnet/dpo/load_balance.h +++ b/src/vnet/dpo/load_balance.h @@ -159,7 +159,7 @@ extern index_t load_balance_create(u32 num_buckets, flow_hash_config_t fhc); extern void load_balance_multipath_update( const dpo_id_t *dpo, - load_balance_path_t * raw_next_hops, + const load_balance_path_t * raw_next_hops, load_balance_flags_t flags); extern void load_balance_set_bucket(index_t lbi, diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c index 24b50637..3aa3632c 100644 --- a/src/vnet/fib/fib_entry.c +++ b/src/vnet/fib/fib_entry.c @@ -230,6 +230,7 @@ fib_entry_last_lock_gone (fib_node_t *node) ASSERT(0 == vec_len(fib_entry->fe_delegates)); vec_free(fib_entry->fe_delegates); + vec_free(fib_entry->fe_srcs); pool_put(fib_entry_pool, fib_entry); } diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c index 060fac94..1fb04060 100644 --- a/src/vnet/fib/fib_entry_src.c +++ b/src/vnet/fib/fib_entry_src.c @@ -382,6 +382,14 @@ fib_entry_src_mk_lb (fib_entry_t *fib_entry, .fct = fct, }; + /* + * As an optimisation we allocate the vector of next-hops to be sized + * equal to the maximum nuber of paths we will need, which is also the + * most likely number we will need, since in most cases the paths are 'up'. + */ + vec_validate(ctx.next_hops, fib_path_list_get_n_paths(esrc->fes_pl)); + vec_reset_length(ctx.next_hops); + lb_proto = fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto); fib_path_list_walk(esrc->fes_pl, diff --git a/src/vnet/fib/fib_path_list.c b/src/vnet/fib/fib_path_list.c index 5b35e9b8..db9d1af9 100644 --- a/src/vnet/fib/fib_path_list.c +++ b/src/vnet/fib/fib_path_list.c @@ -365,10 +365,10 @@ fib_path_list_mk_lb (fib_path_list_t *path_list, fib_forward_chain_type_t fct, dpo_id_t *dpo) { - load_balance_path_t *hash_key; + load_balance_path_t *nhs; fib_node_index_t *path_index; - hash_key = NULL; + nhs = NULL; if (!dpo_id_is_valid(dpo)) { @@ -388,21 +388,20 @@ fib_path_list_mk_lb (fib_path_list_t *path_list, */ vec_foreach (path_index, path_list->fpl_paths) { - hash_key = fib_path_append_nh_for_multipath_hash( - *path_index, - fct, - hash_key); + nhs = fib_path_append_nh_for_multipath_hash(*path_index, + fct, + nhs); } /* * Path-list load-balances, which if used, would be shared and hence * never need a load-balance map. */ - load_balance_multipath_update(dpo, hash_key, LOAD_BALANCE_FLAG_NONE); + load_balance_multipath_update(dpo, nhs, LOAD_BALANCE_FLAG_NONE); FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index); - vec_free(hash_key); + vec_free(nhs); } /** @@ -591,6 +590,17 @@ fib_path_list_resolve (fib_path_list_t *path_list) return (path_list); } +u32 +fib_path_list_get_n_paths (fib_node_index_t path_list_index) +{ + fib_path_list_t *path_list; + + path_list = fib_path_list_get(path_list_index); + + return (vec_len(path_list->fpl_paths)); +} + + u32 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index) { diff --git a/src/vnet/fib/fib_path_list.h b/src/vnet/fib/fib_path_list.h index 8bc1b20b..f4f94a1b 100644 --- a/src/vnet/fib/fib_path_list.h +++ b/src/vnet/fib/fib_path_list.h @@ -104,6 +104,8 @@ extern fib_node_index_t fib_path_list_copy_and_path_remove( fib_node_index_t pl_index, fib_path_list_flags_t flags, const fib_route_path_t *path); +extern u32 fib_path_list_get_n_paths(fib_node_index_t pl_index); + extern void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index, fib_forward_chain_type_t type, dpo_id_t *dpo); -- cgit 1.2.3-korg From 32e1c010b0c34fd0984f7fc45fae648a182025c5 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Tue, 22 Nov 2016 17:07:28 +0000 Subject: IP Multicast FIB (mfib) - IPv[46] mfib tables with support for (*,G/m), (*,G) and (S,G) exact and longest prefix match - Replication represented via a new replicate DPO. - RPF configuration and data-plane checking - data-plane signals sent to listening control planes. The functions of multicast forwarding entries differ from their unicast conterparts, so we introduce a new mfib_table_t and mfib_entry_t objects. However, we re-use the fib_path_list to resolve and build the entry's output list. the fib_path_list provides the service to construct a replicate DPO for multicast. 'make tests' is added to with two new suites; TEST=mfib, this is invocation of the CLI command 'test mfib' which deals with many path add/remove, flag set/unset scenarios, TEST=ip-mcast, data-plane forwarding tests. Updated applications to use the new MIFB functions; - IPv6 NS/RA. - DHCPv6 unit tests for these are undated accordingly. Change-Id: I49ec37b01f1b170335a5697541c8fd30e6d3a961 Signed-off-by: Neale Ranns --- src/scripts/vnet/mcast/ip4 | 22 + src/vat/api_format.c | 173 +++++ src/vnet.am | 35 +- src/vnet/adj/adj.c | 11 +- src/vnet/adj/adj.h | 1 - src/vnet/adj/adj_internal.h | 2 + src/vnet/adj/adj_mcast.c | 346 ++++++++++ src/vnet/adj/adj_mcast.h | 78 +++ src/vnet/adj/adj_nbr.c | 2 +- src/vnet/adj/adj_rewrite.c | 53 -- src/vnet/adj/adj_rewrite.h | 49 -- src/vnet/dhcpv6/proxy_node.c | 46 +- src/vnet/dpo/dpo.c | 2 + src/vnet/dpo/dpo.h | 8 +- src/vnet/dpo/load_balance.c | 13 +- src/vnet/dpo/load_balance.h | 8 + src/vnet/dpo/replicate_dpo.c | 759 ++++++++++++++++++++++ src/vnet/dpo/replicate_dpo.h | 143 +++++ src/vnet/ethernet/arp.c | 84 ++- src/vnet/ethernet/ethernet.h | 2 + src/vnet/ethernet/interface.c | 20 + src/vnet/fib/fib_attached_export.c | 4 +- src/vnet/fib/fib_entry.h | 2 +- src/vnet/fib/fib_entry_delegate.c | 3 + src/vnet/fib/fib_entry_src.c | 4 + src/vnet/fib/fib_node.h | 2 + src/vnet/fib/fib_path.c | 91 ++- src/vnet/fib/fib_path_list.c | 9 +- src/vnet/fib/fib_path_list.h | 6 + src/vnet/fib/fib_table.c | 69 +- src/vnet/fib/fib_table.h | 16 + src/vnet/fib/fib_test.c | 207 +++--- src/vnet/fib/fib_types.c | 4 + src/vnet/fib/fib_types.h | 14 + src/vnet/fib/fib_urpf_list.c | 20 +- src/vnet/fib/ip4_fib.c | 50 +- src/vnet/fib/ip4_fib.h | 9 + src/vnet/fib/ip6_fib.c | 117 ++-- src/vnet/fib/ip6_fib.h | 11 +- src/vnet/fib/mpls_fib.c | 17 +- src/vnet/fib/mpls_fib.h | 9 + src/vnet/ip/ip.api | 53 ++ src/vnet/ip/ip4.h | 24 + src/vnet/ip/ip4_forward.c | 498 +++++---------- src/vnet/ip/ip4_input.c | 4 +- src/vnet/ip/ip6.h | 27 + src/vnet/ip/ip6_forward.c | 83 ++- src/vnet/ip/ip6_input.c | 43 +- src/vnet/ip/ip6_neighbor.c | 134 ++-- src/vnet/ip/ip_api.c | 210 +++++++ src/vnet/ip/lookup.c | 171 +++++ src/vnet/ip/lookup.h | 82 +-- src/vnet/mcast/mcast.c | 565 ----------------- src/vnet/mcast/mcast.h | 50 -- src/vnet/mcast/mcast_test.c | 149 ----- src/vnet/mfib/ip4_mfib.c | 465 ++++++++++++++ src/vnet/mfib/ip4_mfib.h | 95 +++ src/vnet/mfib/ip6_mfib.c | 663 +++++++++++++++++++ src/vnet/mfib/ip6_mfib.h | 109 ++++ src/vnet/mfib/mfib_entry.c | 1096 ++++++++++++++++++++++++++++++++ src/vnet/mfib/mfib_entry.h | 172 +++++ src/vnet/mfib/mfib_forward.c | 512 +++++++++++++++ src/vnet/mfib/mfib_itf.c | 119 ++++ src/vnet/mfib/mfib_itf.h | 63 ++ src/vnet/mfib/mfib_signal.c | 201 ++++++ src/vnet/mfib/mfib_signal.h | 59 ++ src/vnet/mfib/mfib_table.c | 489 ++++++++++++++ src/vnet/mfib/mfib_table.h | 331 ++++++++++ src/vnet/mfib/mfib_test.c | 1225 ++++++++++++++++++++++++++++++++++++ src/vnet/mfib/mfib_types.c | 213 +++++++ src/vnet/mfib/mfib_types.h | 185 ++++++ src/vnet/misc.c | 3 + src/vnet/rewrite.h | 31 + src/vnet/sr/sr.c | 4 +- src/vnet/util/radix.c | 1104 ++++++++++++++++++++++++++++++++ src/vnet/util/radix.h | 147 +++++ src/vnet/vxlan/vxlan.c | 112 +++- src/vpp/api/api.c | 14 +- src/vppinfra.am | 2 +- src/vppinfra/dlist.h | 2 +- src/vppinfra/format.c | 8 +- src/vppinfra/format.h | 4 +- src/vppinfra/unformat.c | 16 +- test/test_dhcp.py | 16 - test/test_ip6.py | 131 ++-- test/test_ip_mcast.py | 612 ++++++++++++++++++ test/test_mfib.py | 23 + test/vpp_interface.py | 3 +- test/vpp_ip_route.py | 101 ++- test/vpp_papi_provider.py | 34 +- 90 files changed, 11211 insertions(+), 1767 deletions(-) create mode 100644 src/scripts/vnet/mcast/ip4 create mode 100644 src/vnet/adj/adj_mcast.c create mode 100644 src/vnet/adj/adj_mcast.h delete mode 100644 src/vnet/adj/adj_rewrite.c delete mode 100644 src/vnet/adj/adj_rewrite.h create mode 100644 src/vnet/dpo/replicate_dpo.c create mode 100644 src/vnet/dpo/replicate_dpo.h delete mode 100644 src/vnet/mcast/mcast.c delete mode 100644 src/vnet/mcast/mcast.h delete mode 100644 src/vnet/mcast/mcast_test.c create mode 100644 src/vnet/mfib/ip4_mfib.c create mode 100644 src/vnet/mfib/ip4_mfib.h create mode 100644 src/vnet/mfib/ip6_mfib.c create mode 100644 src/vnet/mfib/ip6_mfib.h create mode 100644 src/vnet/mfib/mfib_entry.c create mode 100644 src/vnet/mfib/mfib_entry.h create mode 100644 src/vnet/mfib/mfib_forward.c create mode 100644 src/vnet/mfib/mfib_itf.c create mode 100644 src/vnet/mfib/mfib_itf.h create mode 100644 src/vnet/mfib/mfib_signal.c create mode 100644 src/vnet/mfib/mfib_signal.h create mode 100644 src/vnet/mfib/mfib_table.c create mode 100644 src/vnet/mfib/mfib_table.h create mode 100644 src/vnet/mfib/mfib_test.c create mode 100644 src/vnet/mfib/mfib_types.c create mode 100644 src/vnet/mfib/mfib_types.h create mode 100644 src/vnet/util/radix.c create mode 100644 src/vnet/util/radix.h create mode 100644 test/test_ip_mcast.py create mode 100644 test/test_mfib.py (limited to 'src/vnet/fib/fib_entry_src.c') diff --git a/src/scripts/vnet/mcast/ip4 b/src/scripts/vnet/mcast/ip4 new file mode 100644 index 00000000..69f1ee00 --- /dev/null +++ b/src/scripts/vnet/mcast/ip4 @@ -0,0 +1,22 @@ +packet-generator new { + name x + limit 1 + node ip4-input + size 64-64 + no-recycle + data { + ICMP: 1.0.0.2 -> 232.1.1.1 + ICMP echo_request + incrementing 100 + } +} + +trace add pg-input 100 +loop create +loop create +set int state loop0 up +set int state loop1 up + +ip mroute add 232.1.1.1 via pg0 Accept +ip mroute add 232.1.1.1 via loop0 Forward +ip mroute add 232.1.1.1 via loop1 Forward diff --git a/src/vat/api_format.c b/src/vat/api_format.c index b83313de..4cfe4a58 100644 --- a/src/vat/api_format.c +++ b/src/vat/api_format.c @@ -48,6 +48,7 @@ #include #include #include +#include #include "vat/json_format.h" @@ -505,6 +506,53 @@ unformat_flow_classify_table_type (unformat_input_t * input, va_list * va) return 1; } +static const char *mfib_flag_names[] = MFIB_ENTRY_NAMES_SHORT; +static const char *mfib_flag_long_names[] = MFIB_ENTRY_NAMES_LONG; +static const char *mfib_itf_flag_long_names[] = MFIB_ITF_NAMES_LONG; +static const char *mfib_itf_flag_names[] = MFIB_ITF_NAMES_SHORT; + +uword +unformat_mfib_itf_flags (unformat_input_t * input, va_list * args) +{ + mfib_itf_flags_t old, *iflags = va_arg (*args, mfib_itf_flags_t *); + mfib_itf_attribute_t attr; + + old = *iflags; + FOR_EACH_MFIB_ITF_ATTRIBUTE (attr) + { + if (unformat (input, mfib_itf_flag_long_names[attr])) + *iflags |= (1 << attr); + } + FOR_EACH_MFIB_ITF_ATTRIBUTE (attr) + { + if (unformat (input, mfib_itf_flag_names[attr])) + *iflags |= (1 << attr); + } + + return (old == *iflags ? 0 : 1); +} + +uword +unformat_mfib_entry_flags (unformat_input_t * input, va_list * args) +{ + mfib_entry_flags_t old, *eflags = va_arg (*args, mfib_entry_flags_t *); + mfib_entry_attribute_t attr; + + old = *eflags; + FOR_EACH_MFIB_ATTRIBUTE (attr) + { + if (unformat (input, mfib_flag_long_names[attr])) + *eflags |= (1 << attr); + } + FOR_EACH_MFIB_ATTRIBUTE (attr) + { + if (unformat (input, mfib_flag_names[attr])) + *eflags |= (1 << attr); + } + + return (old == *eflags ? 0 : 1); +} + #if (VPP_API_TEST_BUILTIN==0) u8 * format_ip4_address (u8 * s, va_list * args) @@ -3592,6 +3640,7 @@ _(bridge_domain_add_del_reply) \ _(sw_interface_set_l2_xconnect_reply) \ _(l2fib_add_del_reply) \ _(ip_add_del_route_reply) \ +_(ip_mroute_add_del_reply) \ _(mpls_route_add_del_reply) \ _(mpls_ip_bind_unbind_reply) \ _(proxy_arp_add_del_reply) \ @@ -3792,6 +3841,7 @@ _(TAP_MODIFY_REPLY, tap_modify_reply) \ _(TAP_DELETE_REPLY, tap_delete_reply) \ _(SW_INTERFACE_TAP_DETAILS, sw_interface_tap_details) \ _(IP_ADD_DEL_ROUTE_REPLY, ip_add_del_route_reply) \ +_(IP_MROUTE_ADD_DEL_REPLY, ip_mroute_add_del_reply) \ _(MPLS_ROUTE_ADD_DEL_REPLY, mpls_route_add_del_reply) \ _(MPLS_IP_BIND_UNBIND_REPLY, mpls_ip_bind_unbind_reply) \ _(PROXY_ARP_ADD_DEL_REPLY, proxy_arp_add_del_reply) \ @@ -6383,6 +6433,126 @@ api_ip_add_del_route (vat_main_t * vam) return (vam->retval); } +static int +api_ip_mroute_add_del (vat_main_t * vam) +{ + unformat_input_t *i = vam->input; + vl_api_ip_mroute_add_del_t *mp; + f64 timeout; + u32 sw_if_index = ~0, vrf_id = 0; + u8 is_ipv6 = 0; + u8 is_local = 0; + u8 create_vrf_if_needed = 0; + u8 is_add = 1; + u8 address_set = 0; + u32 grp_address_length = 0; + ip4_address_t v4_grp_address, v4_src_address; + ip6_address_t v6_grp_address, v6_src_address; + mfib_itf_flags_t iflags = 0; + mfib_entry_flags_t eflags = 0; + + /* Parse args required to build the message */ + while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT) + { + if (unformat (i, "sw_if_index %d", &sw_if_index)) + ; + else if (unformat (i, "%U %U", + unformat_ip4_address, &v4_src_address, + unformat_ip4_address, &v4_grp_address)) + { + grp_address_length = 64; + address_set = 1; + is_ipv6 = 0; + } + else if (unformat (i, "%U %U", + unformat_ip6_address, &v6_src_address, + unformat_ip6_address, &v6_grp_address)) + { + grp_address_length = 256; + address_set = 1; + is_ipv6 = 1; + } + else if (unformat (i, "%U", unformat_ip4_address, &v4_grp_address)) + { + memset (&v4_src_address, 0, sizeof (v4_src_address)); + grp_address_length = 32; + address_set = 1; + is_ipv6 = 0; + } + else if (unformat (i, "%U", unformat_ip6_address, &v6_grp_address)) + { + memset (&v6_src_address, 0, sizeof (v6_src_address)); + grp_address_length = 128; + address_set = 1; + is_ipv6 = 1; + } + else if (unformat (i, "/%d", &grp_address_length)) + ; + else if (unformat (i, "local")) + { + is_local = 1; + } + else if (unformat (i, "del")) + is_add = 0; + else if (unformat (i, "add")) + is_add = 1; + else if (unformat (i, "vrf %d", &vrf_id)) + ; + else if (unformat (i, "create-vrf")) + create_vrf_if_needed = 1; + else if (unformat (i, "%U", unformat_mfib_itf_flags, &iflags)) + ; + else if (unformat (i, "%U", unformat_mfib_entry_flags, &eflags)) + ; + else + { + clib_warning ("parse error '%U'", format_unformat_error, i); + return -99; + } + } + + if (address_set == 0) + { + errmsg ("missing addresses\n"); + return -99; + } + + /* Construct the API message */ + M (IP_MROUTE_ADD_DEL, ip_mroute_add_del); + + mp->next_hop_sw_if_index = ntohl (sw_if_index); + mp->table_id = ntohl (vrf_id); + mp->create_vrf_if_needed = create_vrf_if_needed; + + mp->is_add = is_add; + mp->is_ipv6 = is_ipv6; + mp->is_local = is_local; + mp->itf_flags = ntohl (iflags); + mp->entry_flags = ntohl (eflags); + mp->grp_address_length = grp_address_length; + mp->grp_address_length = ntohs (mp->grp_address_length); + + if (is_ipv6) + { + clib_memcpy (mp->grp_address, &v6_grp_address, sizeof (v6_grp_address)); + clib_memcpy (mp->src_address, &v6_src_address, sizeof (v6_src_address)); + } + else + { + clib_memcpy (mp->grp_address, &v4_grp_address, sizeof (v4_grp_address)); + clib_memcpy (mp->src_address, &v4_src_address, sizeof (v4_src_address)); + + } + + /* send it... */ + S; + /* Wait for a reply... */ + W; + + /* Return the good/bad news */ + return (vam->retval); +} + static int api_mpls_route_add_del (vat_main_t * vam) { @@ -17512,6 +17682,9 @@ _(ip_add_del_route, \ "[ | sw_if_index ] [resolve-attempts ]\n" \ "[weight ] [drop] [local] [classify ] [del]\n" \ "[multipath] [count ]") \ +_(ip_mroute_add_del, \ + " / [table-id ]\n" \ + "[ | sw_if_index ] [local] [del]") \ _(mpls_route_add_del, \ "