[PATCH nf-next,v1 0/3] convert rbtree to binary search array

[Pablo Neira Ayuso <pablo@netfilter.org>]

Hi,

Florian reported that there is currently an issue with interval matching
in the rbtree, allowing for false negative lookup during transaction.

This series addresses this issue by translating the rbtree, which keeps
the intervals in order, to binary search. The array is published to
packet path through RCU. The idea is to keep using the rbtree
datastructure for control plane, which needs to deal with updates, then
generating a array using this rbtree for binary search lookups.

There is a corner case worth mention: Anonymous maps result in
consecutive start elements in case of contiguous intervals, this needs
a special handling which is documented in the new .commit function.

With 100k elements, this shows a little more overhead to build this
array, mainly due to the memory allocation.

This approach allows to compact the start and end elements in one single
intervals in the array, which speeds up packet lookups by ~50% according
to the existing performance script in selftests.

This is approach does not require the spinlock anymore, which is only
needed by control plane. Although I think it can be removed if .walk
is translated to dump the set content using the new array.

This also allows to remove the seqcount_t in a later patch.

Patch #1 allows to call .remove in case .abort is defined, which is
needed by this new approach. Only pipapo needs to skip .remove to speed.

Patch #2 add the binary search array approach for interval matching.

Patch #3 updates .get to use the binary search array to find for
(closest or exact) interval matching.

This series passes tests/shell successfully, but more tests on this
would be good to have because this is a bit of new code.

This series is an alternative proposal to Florian's approach.

Pablo Neira Ayuso (3):
  netfilter: nf_tables: add .abort_skip_removal flag for set types
  netfilter: nft_set_rbtree: translate rbtree to array for binary search
  netfilter: nft_set_rbtree: use binary search array in get command

 include/net/netfilter/nf_tables.h |   1 +
 net/netfilter/nf_tables_api.c     |   2 +-
 net/netfilter/nft_set_pipapo.c    |   2 +
 net/netfilter/nft_set_rbtree.c    | 421 ++++++++++++++++++++----------
 4 files changed, 287 insertions(+), 139 deletions(-)

-- 
2.47.3