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, 94 insertions, 0 deletions

diff --git a/src/plugins/acl/hash_lookup_types.h b/src/plugins/acl/hash_lookup_types.h
new file mode 100644
index 00000000000..1c04459155c
--- /dev/null
+++ b/src/plugins/acl/hash_lookup_types.h
@@ -0,0 +1,94 @@
+/*
+ *------------------------------------------------------------------
+ * 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.
+ *------------------------------------------------------------------
+ */
+
+#ifndef _ACL_HASH_LOOKUP_TYPES_H_
+#define _ACL_HASH_LOOKUP_TYPES_H_
+
+/* The structure representing the single entry with hash representation */
+typedef struct {
+  /* these two entries refer to the original ACL# and rule# within that ACL */
+  u32 acl_index;
+  u32 ace_index;
+
+  u32 mask_type_index;
+  u8 src_portrange_not_powerof2;
+  u8 dst_portrange_not_powerof2;
+
+  fa_5tuple_t match;
+  u8 action;
+} hash_ace_info_t;
+
+/*
+ * The structure holding the information necessary for the hash-based ACL operation
+ */
+typedef struct {
+  /* The mask types present in this ACL */
+  uword *mask_type_index_bitmap;
+  hash_ace_info_t *rules;
+} hash_acl_info_t;
+
+typedef struct {
+  /* original non-compiled ACL */
+  u32 acl_index;
+  u32 ace_index;
+  /* the index of the hash_ace_info_t */
+  u32 hash_ace_info_index;
+  /*
+   * in case of the same key having multiple entries,
+   * this holds the index of the next entry.
+   */
+  u32 next_applied_entry_index;
+  /*
+   * previous entry in the list of the chained ones,
+   * if ~0 then this is entry in the hash.
+   */
+  u32 prev_applied_entry_index;
+  /*
+   * Action of this applied ACE
+   */
+  u8 action;
+} applied_hash_ace_entry_t;
+
+typedef struct {
+   /*
+    * A logical OR of all the applied_ace_hash_entry_t=>
+    *                            hash_ace_info_t=>mask_type_index bits set
+    */
+   uword *mask_type_index_bitmap;
+} applied_hash_acl_info_t;
+
+
+typedef union {
+  u64 as_u64;
+  struct {
+    u32 applied_entry_index;
+    u16 reserved_u16;
+    u8 reserved_u8;
+    /* means there is some other entry in front intersecting with this one */
+    u8 shadowed:1;
+    u8 need_portrange_check:1;
+    u8 reserved_flags:6;
+  };
+} hash_acl_lookup_value_t;
+
+#define CT_ASSERT_EQUAL(name, x,y) typedef int assert_ ## name ## _compile_time_assertion_failed[((x) == (y))-1]
+
+CT_ASSERT_EQUAL(hash_acl_lookup_value_t_is_u64, sizeof(hash_acl_lookup_value_t), sizeof(u64));
+
+#undef CT_ASSERT_EQUAL
+
+#endif