From 7f4d577d6bc243f53a044d92ca9367b3f1fa170e Mon Sep 17 00:00:00 2001 From: Andrew Yourtchenko Date: Wed, 24 May 2017 13:20:47 +0200 Subject: acl-plugin: bihash-based ACL lookup Add a bihash-based ACL lookup mechanism and make it a new default. This changes the time required to lookup a 5-tuple match from O(total_N_entries) to O(total_N_mask_types), where "mask type" is an overall mask on the 5-tuple required to represent an ACE. For testing/comparison there is a temporary debug CLI "set acl-plugin use-hash-acl-matching {0|1}", which, when set to 0, makes the plugin use the "old" linear lookup, and when set to 1, makes it use the hash-based lookup. Based on the discussions on vpp-dev mailing list, prevent assigning the ACL index to an interface, when the ACL with that index is not defined, also prevent deleting an ACL if that ACL is applied. Also, for the easier debugging of the state, there are new debug CLI commands to see the ACL plugin state at several layers: "show acl-plugin acl [index N]" - show a high-level ACL representation, used for the linear lookup and as a base for building the hashtable-based lookup. Also shows if a given ACL is applied somewhere. "show acl-plugin interface [sw_if_index N]" - show which interfaces have which ACL(s) applied. "show acl-plugin tables" - a lower-level debug command used to see the state of all of the related data structures at once. There are specifiers possible, which make for a more focused and maybe augmented output: "show acl-plugin tables acl [index N]" show the "bitmask-ready" representations of the ACLs, we well as the mask types and their associated indices. "show acl-plutin tables mask" show the derived mask types and their indices only. "show acl-plugin tables applied [sw_if_index N]" show the table of all of the ACEs applied for a given sw_if_index or all interfaces. "show acl-plugin tables hash [verbose N]" show the 48x8 bihash used for the ACL lookup. Change-Id: I89fff051424cb44bcb189e3cee04c1b8f76efc28 Signed-off-by: Andrew Yourtchenko --- src/plugins/acl/hash_lookup_private.h | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100644 src/plugins/acl/hash_lookup_private.h (limited to 'src/plugins/acl/hash_lookup_private.h') diff --git a/src/plugins/acl/hash_lookup_private.h b/src/plugins/acl/hash_lookup_private.h new file mode 100644 index 00000000..7b6449cd --- /dev/null +++ b/src/plugins/acl/hash_lookup_private.h @@ -0,0 +1,27 @@ +/* + *------------------------------------------------------------------ + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + *------------------------------------------------------------------ + */ + +#define ACL_HASH_LOOKUP_DEBUG 0 + +#if ACL_HASH_LOOKUP_DEBUG == 1 +#define DBG(...) clib_warning(__VA_ARGS__) +#define DBG_UNIX_LOG(...) clib_unix_warning(__VA_ARGS__) +#else +#define DBG(...) +#define DBG_UNIX_LOG(...) +#endif + -- cgit 1.2.3-korg From 6d157c2f91a5cf334968df5a6ac4963fedb8c706 Mon Sep 17 00:00:00 2001 From: Andrew Yourtchenko Date: Fri, 18 Aug 2017 19:10:39 +0200 Subject: acl-plugin: warning printed when acl_add_replace already applied ACLs (complete the fix for VPP-935) The fix for VPP-935 missed the case that hash_acl_add() and hash_acl_delete() may be called during the replacement of the existing applied ACL, as a result the "applied" logic needs to be replicated for the hash acls separately, since it is a lower layer. Change-Id: I7dcb2b120fcbdceb5e59acb5029f9eb77bd0f240 Signed-off-by: Andrew Yourtchenko (cherry picked from commit ce9714032d36d18abe72981552219dff871ff392) --- src/plugins/acl/acl.c | 2 ++ src/plugins/acl/hash_lookup.c | 55 ++++++++++++++++++++++++----------- src/plugins/acl/hash_lookup_private.h | 6 ++++ src/plugins/acl/hash_lookup_types.h | 3 ++ 4 files changed, 49 insertions(+), 17 deletions(-) (limited to 'src/plugins/acl/hash_lookup_private.h') diff --git a/src/plugins/acl/acl.c b/src/plugins/acl/acl.c index 2448a928..7790b30b 100644 --- a/src/plugins/acl/acl.c +++ b/src/plugins/acl/acl.c @@ -2421,6 +2421,8 @@ acl_show_aclplugin_fn (vlib_main_t * vm, } hash_acl_info_t *ha = &am->hash_acl_infos[i]; out0 = format(out0, "acl-index %u bitmask-ready layout\n", i); + out0 = format(out0, " applied inbound on sw_if_index list: %U\n", format_vec32, ha->inbound_sw_if_index_list, "%d"); + out0 = format(out0, " applied outbound on sw_if_index list: %U\n", format_vec32, ha->outbound_sw_if_index_list, "%d"); out0 = format(out0, " mask type index bitmap: %U\n", format_bitmap_hex, ha->mask_type_index_bitmap); for(j=0; jrules); j++) { hash_ace_info_t *pa = &ha->rules[j]; diff --git a/src/plugins/acl/hash_lookup.c b/src/plugins/acl/hash_lookup.c index a2edb9f3..f987b36e 100644 --- a/src/plugins/acl/hash_lookup.c +++ b/src/plugins/acl/hash_lookup.c @@ -308,16 +308,13 @@ hash_acl_apply(acl_main_t *am, u32 sw_if_index, u8 is_input, int acl_index) { int i; - DBG("HASH ACL apply: sw_if_index %d is_input %d acl %d", sw_if_index, is_input, acl_index); + DBG0("HASH ACL apply: sw_if_index %d is_input %d acl %d", sw_if_index, is_input, acl_index); if (!am->acl_lookup_hash_initialized) { BV (clib_bihash_init) (&am->acl_lookup_hash, "ACL plugin rule lookup bihash", 65536, 2 << 25); am->acl_lookup_hash_initialized = 1; } - u32 *acl_vec = is_input ? *vec_elt_at_index(am->input_acl_vec_by_sw_if_index, sw_if_index) - : *vec_elt_at_index(am->output_acl_vec_by_sw_if_index, sw_if_index); - void *oldheap = hash_acl_set_heap(am); if (is_input) { vec_validate(am->input_hash_entry_vec_by_sw_if_index, sw_if_index); @@ -327,9 +324,9 @@ hash_acl_apply(acl_main_t *am, u32 sw_if_index, u8 is_input, int acl_index) vec_validate(am->hash_acl_infos, acl_index); applied_hash_ace_entry_t **applied_hash_aces = get_applied_hash_aces(am, is_input, sw_if_index); - u32 order_index = vec_search(acl_vec, acl_index); hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index); - ASSERT(order_index != ~0); + u32 **hash_acl_applied_sw_if_index = is_input ? &ha->inbound_sw_if_index_list + : &ha->outbound_sw_if_index_list; int base_offset = vec_len(*applied_hash_aces); @@ -348,6 +345,13 @@ hash_acl_apply(acl_main_t *am, u32 sw_if_index, u8 is_input, int acl_index) goto done; } vec_add1(pal->applied_acls, acl_index); + u32 index2 = vec_search((*hash_acl_applied_sw_if_index), sw_if_index); + if (index2 != ~0) { + clib_warning("BUG: trying to apply twice acl_index %d on (sw_if_index %d) is_input %d", + acl_index, sw_if_index, is_input); + goto done; + } + vec_add1((*hash_acl_applied_sw_if_index), sw_if_index); pal->mask_type_index_bitmap = clib_bitmap_or(pal->mask_type_index_bitmap, ha->mask_type_index_bitmap); @@ -524,11 +528,15 @@ hash_acl_unapply(acl_main_t *am, u32 sw_if_index, u8 is_input, int acl_index) { int i; - DBG("HASH ACL unapply: sw_if_index %d is_input %d acl %d", sw_if_index, is_input, acl_index); + DBG0("HASH ACL unapply: sw_if_index %d is_input %d acl %d", sw_if_index, is_input, acl_index); applied_hash_acl_info_t **applied_hash_acls = is_input ? &am->input_applied_hash_acl_info_by_sw_if_index : &am->output_applied_hash_acl_info_by_sw_if_index; applied_hash_acl_info_t *pal = vec_elt_at_index((*applied_hash_acls), sw_if_index); + hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index); + u32 **hash_acl_applied_sw_if_index = is_input ? &ha->inbound_sw_if_index_list + : &ha->outbound_sw_if_index_list; + /* remove this acl# from the list of applied hash acls */ u32 index = vec_search(pal->applied_acls, acl_index); if (index == ~0) { @@ -538,7 +546,14 @@ hash_acl_unapply(acl_main_t *am, u32 sw_if_index, u8 is_input, int acl_index) } vec_del1(pal->applied_acls, index); - hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index); + u32 index2 = vec_search((*hash_acl_applied_sw_if_index), sw_if_index); + if (index2 == ~0) { + clib_warning("BUG: trying to unapply twice acl_index %d on (sw_if_index %d) is_input %d", + acl_index, sw_if_index, is_input); + return; + } + vec_del1((*hash_acl_applied_sw_if_index), index2); + applied_hash_ace_entry_t **applied_hash_aces = get_applied_hash_aces(am, is_input, sw_if_index); for(i=0; i < vec_len((*applied_hash_aces)); i++) { @@ -602,7 +617,7 @@ hash_acl_reapply(acl_main_t *am, u32 sw_if_index, u8 is_input, int acl_index) ASSERT(start_index < vec_len(*applied_acls)); /* unapply all the ACLs till the current one */ - for(i = vec_len(*applied_acls) - 1; i >= start_index; i--) { + for(i = vec_len(*applied_acls) - 1; i > start_index; i--) { hash_acl_unapply(am, sw_if_index, is_input, *vec_elt_at_index(*applied_acls, i)); } for(i = start_index; i < vec_len(*applied_acls); i++) { @@ -815,7 +830,7 @@ void hash_acl_add(acl_main_t *am, int acl_index) void hash_acl_delete(acl_main_t *am, int acl_index) { void *oldheap = hash_acl_set_heap(am); - DBG("HASH ACL delete : %d", acl_index); + DBG0("HASH ACL delete : %d", acl_index); /* * If the ACL is applied somewhere, remove the references of it (call hash_acl_unapply) * this is a different behavior from the linear lookup where an empty ACL is "deny all", @@ -823,16 +838,23 @@ void hash_acl_delete(acl_main_t *am, int acl_index) * However, following vpp-dev discussion the ACL that is referenced elsewhere * should not be possible to delete, and the change adding this also adds * the safeguards to that respect, so this is not a problem. + * + * The part to rememeber is that this routine is called in process of reapplication + * during the acl_add_replace() API call - the old acl ruleset is deleted, then + * the new one is added, without the change in the applied ACLs - so this case + * has to be handled. */ - if (acl_index < vec_len(am->input_sw_if_index_vec_by_acl)) { + hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index); + u32 *interface_list_copy = 0; + { u32 *sw_if_index; - vec_foreach(sw_if_index, am->input_sw_if_index_vec_by_acl[acl_index]) { + interface_list_copy = vec_dup(ha->inbound_sw_if_index_list); + vec_foreach(sw_if_index, interface_list_copy) { hash_acl_unapply(am, *sw_if_index, 1, acl_index); } - } - if (acl_index < vec_len(am->output_sw_if_index_vec_by_acl)) { - u32 *sw_if_index; - vec_foreach(sw_if_index, am->output_sw_if_index_vec_by_acl[acl_index]) { + vec_free(interface_list_copy); + interface_list_copy = vec_dup(ha->outbound_sw_if_index_list); + vec_foreach(sw_if_index, interface_list_copy) { hash_acl_unapply(am, *sw_if_index, 0, acl_index); } } @@ -840,7 +862,6 @@ void hash_acl_delete(acl_main_t *am, int acl_index) /* walk the mask types for the ACL about-to-be-deleted, and decrease * the reference count, possibly freeing up some of them */ int i; - hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index); for(i=0; i < vec_len(ha->rules); i++) { release_mask_type_index(am, ha->rules[i].mask_type_index); } diff --git a/src/plugins/acl/hash_lookup_private.h b/src/plugins/acl/hash_lookup_private.h index 7b6449cd..bc621416 100644 --- a/src/plugins/acl/hash_lookup_private.h +++ b/src/plugins/acl/hash_lookup_private.h @@ -18,9 +18,15 @@ #define ACL_HASH_LOOKUP_DEBUG 0 #if ACL_HASH_LOOKUP_DEBUG == 1 +#define DBG0(...) clib_warning(__VA_ARGS__) +#define DBG(...) +#define DBG_UNIX_LOG(...) +#elif ACL_HASH_LOOKUP_DEBUG == 2 +#define DBG0(...) clib_warning(__VA_ARGS__) #define DBG(...) clib_warning(__VA_ARGS__) #define DBG_UNIX_LOG(...) clib_unix_warning(__VA_ARGS__) #else +#define DBG0(...) #define DBG(...) #define DBG_UNIX_LOG(...) #endif diff --git a/src/plugins/acl/hash_lookup_types.h b/src/plugins/acl/hash_lookup_types.h index 837cc0a8..f7110007 100644 --- a/src/plugins/acl/hash_lookup_types.h +++ b/src/plugins/acl/hash_lookup_types.h @@ -38,6 +38,9 @@ typedef struct { typedef struct { /* The mask types present in this ACL */ uword *mask_type_index_bitmap; + /* hash ACL applied on these interfaces */ + u32 *inbound_sw_if_index_list; + u32 *outbound_sw_if_index_list; hash_ace_info_t *rules; } hash_acl_info_t; -- cgit 1.2.3-korg