acl-plugin: VPP-897: applying of large number of ACEs is slow

When applying ACEs, in the new hash-based scheme, for each ACE
the lookup in the hash table is done, and either that ACE is added
to the end of the existing list if there is a match,
or a new list is created if there is no match.

Usually ACEs do not overlap, so this operation is fast, however,
the fragment-permit entries in case of a large number of ACLs
create a huge list which needs to be traversed for every other
ACE being added, slowing down the process dramatically.

The solution is to add an explicit flag to denote the first
element of the chain, and use the "prev" index of that
element to point to the tail element. The "next" field
of the last element is still ~0 and if we touch that
one, we do the linear search to find the first one,
but that is a relatively infrequent operation.

Change-Id: I352a3becd7854cf39aae65f0950afad7d18a70aa
Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>
(cherry picked from commit 204cf74aed51ca07933df7c606754abb4b26fd82)

1 files changed, 6 insertions, 2 deletions

diff --git a/src/plugins/acl/hash_lookup_types.h b/src/plugins/acl/hash_lookup_types.h
index 1c04459155c..1848c5ffc6a 100644
--- a/src/plugins/acl/hash_lookup_types.h
+++ b/src/plugins/acl/hash_lookup_types.h
@@ -53,11 +53,15 @@ typedef struct {
    */
   u32 next_applied_entry_index;
   /*
-   * previous entry in the list of the chained ones,
-   * if ~0 then this is entry in the hash.
+   * previous entry in the ring list of the chained ones.
    */
   u32 prev_applied_entry_index;
   /*
+   * 1 if it is the very first entry in the list,
+   * referenced from the hash.
+   */
+  u8 is_first_entry;
+  /*
    * Action of this applied ACE
    */
   u8 action;