acl-plugin: tm: optimize multi-lookups and prepare to add tuplemerge

- instantiate the per-use mask type entry for a given hash ACE
  this prepares to adding tuplemerge where the applied ACE may
  have a different mask type due to relaxing of the tuples

- store the vector of the colliding rules for linear lookups
  rather than traversing the linked list.

- store the lowest rule index for a given mask type inside
  the structure. This allows to skip looking up at the later
  mask types if we already matched an entry that is in front
  of the very first entry in the new candidate mask type,
  thus saving a worthless hash table lookup.

- use a vector of mask type indices rather than bitmap,
  in the sorted order (by construction) of ascending
  lowest rule index - this allows to terminate the lookups
  early.

- adapt the debug cli outputs accordingly to show the data

- propagate the is_ip6 into the inner calls

Change-Id: I7a67b271e66785c6eab738b632b432d5886a0a8a
Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>

1 files changed, 32 insertions, 15 deletions

diff --git a/src/plugins/acl/hash_lookup_types.h b/src/plugins/acl/hash_lookup_types.h
index 1a20ebff8f8..3efcf4e372c 100644
--- a/src/plugins/acl/hash_lookup_types.h
+++ b/src/plugins/acl/hash_lookup_types.h
@@ -18,17 +18,17 @@
 #ifndef _ACL_HASH_LOOKUP_TYPES_H_
 #define _ACL_HASH_LOOKUP_TYPES_H_
 
+#include "types.h"
+
 /* The structure representing the single entry with hash representation */
 typedef struct {
+  fa_5tuple_t match;
   /* 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;
+  u32 base_mask_type_index;
 
-  fa_5tuple_t match;
   u8 action;
 } hash_ace_info_t;
 
@@ -36,8 +36,6 @@ typedef struct {
  * 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 ACL applied on these lookup contexts */
   u32 *lc_index_list;
   hash_ace_info_t *rules;
@@ -45,12 +43,23 @@ typedef struct {
   int hash_acl_exists;
 } hash_acl_info_t;
 
+
+typedef struct {
+  acl_rule_t rule;
+  u32 acl_index;
+  u32 ace_index;
+  u32 acl_position;
+  u32 applied_entry_index;
+} collision_match_rule_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;
+  /* applied mask type index */
+  u32 mask_type_index;
   /*
    * in case of the same key having multiple entries,
    * this holds the index of the next entry.
@@ -66,6 +75,10 @@ typedef struct {
    */
   u32 tail_applied_entry_index;
   /*
+   * Collision rule vector for matching - set only on head entry
+   */
+  collision_match_rule_t *colliding_rules;
+  /*
    * number of hits on this entry
    */
   u64 hitcount;
@@ -80,11 +93,7 @@ typedef struct {
 } 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 ACLs so we can track them independently from main ACL module */
    u32 *applied_acls;
 } applied_hash_acl_info_t;
@@ -96,13 +105,21 @@ typedef union {
     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;
+    u8 reserved_flags:8;
   };
 } hash_acl_lookup_value_t;
 
+
+typedef struct {
+   u32 mask_type_index;
+   /* first rule # for this mask */
+   u32 first_rule_index;
+   /* Debug Information */
+   u32 num_entries;
+   u32 max_collisions;
+} hash_applied_mask_info_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));