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 <ayourtch@gmail.com>

1 files changed, 30 insertions, 0 deletions

diff --git a/src/plugins/acl/acl.h b/src/plugins/acl/acl.h
index 65bc9e74ead..c9f403e9d1b 100644
--- a/src/plugins/acl/acl.h
+++ b/src/plugins/acl/acl.h
@@ -24,8 +24,10 @@
 #include <vppinfra/error.h>
 #include <vppinfra/bitmap.h>
 #include <vppinfra/elog.h>
+#include <vppinfra/bihash_48_8.h>
 #include "bihash_40_8.h"
 #include "fa_node.h"
+#include "hash_lookup_types.h"
 
 #define  ACL_PLUGIN_VERSION_MAJOR 1
 #define  ACL_PLUGIN_VERSION_MINOR 3
@@ -109,17 +111,45 @@ typedef struct
   u32 l2_table_index;
 } macip_acl_list_t;
 
+/*
+ * An element describing a particular configuration fo the mask,
+ * and how many times it has been used.
+ */
+typedef struct
+{
+  fa_5tuple_t mask;
+  u32 refcount;
+} ace_mask_type_entry_t;
+
 typedef struct {
   /* API message ID base */
   u16 msg_id_base;
 
   acl_list_t *acls;	/* Pool of ACLs */
+  hash_acl_info_t *hash_acl_infos; /* corresponding hash matching housekeeping info */
+  clib_bihash_48_8_t acl_lookup_hash; /* ACL lookup hash table. */
+  int acl_lookup_hash_initialized;
+  applied_hash_ace_entry_t **input_hash_entry_vec_by_sw_if_index;
+  applied_hash_ace_entry_t **output_hash_entry_vec_by_sw_if_index;
+  applied_hash_acl_info_t *input_applied_hash_acl_info_by_sw_if_index;
+  applied_hash_acl_info_t *output_applied_hash_acl_info_by_sw_if_index;
+
   macip_acl_list_t *macip_acls;	/* Pool of MAC-IP ACLs */
 
   /* ACLs associated with interfaces */
   u32 **input_acl_vec_by_sw_if_index;
   u32 **output_acl_vec_by_sw_if_index;
 
+  /* interfaces on which given ACLs are applied */
+  u32 **input_sw_if_index_vec_by_acl;
+  u32 **output_sw_if_index_vec_by_acl;
+
+  /* Do we use hash-based ACL matching or linear */
+  int use_hash_acl_matching;
+
+  /* a pool of all mask types present in all ACEs */
+  ace_mask_type_entry_t *ace_mask_type_pool;
+
   /*
    * Classify tables used to grab the packets for the ACL check,
    * and serving as the 5-tuple session tables at the same time