acl-plugin: VPP-897: applying of large number of ACEs is slow 85/7385/2
authorAndrew Yourtchenko <ayourtch@gmail.com>
Mon, 3 Jul 2017 10:32:44 +0000 (12:32 +0200)
committerAndrew Yourtchenko <ayourtch@gmail.com>
Mon, 3 Jul 2017 10:52:04 +0000 (12:52 +0200)
commit204cf74aed51ca07933df7c606754abb4b26fd82
tree56c2838c9e879c187a492666a6881905c81e558e
parentbafa4d048439fdbcc0bd577e43a2784d1b89bfc5
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>
src/plugins/acl/hash_lookup.c
src/plugins/acl/hash_lookup_types.h