Re: [PATCH nf] nft_set_rbtree: Switch to node list walk for overlap detection

[Stefano Brivio <sbrivio@redhat.com>]

On Mon, 27 Jun 2022 18:59:06 +0200
Pablo Neira Ayuso <pablo@netfilter.org> wrote:

> Hi Stefano,
> 
> On Tue, Jun 14, 2022 at 03:07:04AM +0200, Stefano Brivio wrote:
> > ...instead of a tree descent, which became overly complicated in an
> > attempt to cover cases where expired or inactive elements would
> > affect comparisons with the new element being inserted.
> >
> > Further, it turned out that it's probably impossible to cover all
> > those cases, as inactive nodes might entirely hide subtrees
> > consisting of a complete interval plus a node that makes the current
> > insertion not overlap.
> >
> > For the insertion operation itself, this essentially reverts back to
> > the implementation before commit 7c84d41416d8
> > ("netfilter: nft_set_rbtree: Detect partial overlaps on insertion"),
> > except that cases of complete overlap are already handled in the
> > overlap detection phase itself, which slightly simplifies the loop to
> > find the insertion point.
> >
> > Reported-by: Pablo Neira Ayuso <pablo@netfilter.org>
> > Fixes: 7c84d41416d8 ("netfilter: nft_set_rbtree: Detect partial overlaps on insertion")
> > Signed-off-by: Stefano Brivio <sbrivio@redhat.com>
> > ---
> >  net/netfilter/nft_set_rbtree.c | 194 ++++++++++-----------------------
> >  1 file changed, 58 insertions(+), 136 deletions(-)  
> 
> When running tests this is increasing the time to detect overlaps in
> my testbed, because of the linear list walk for each element.

...by the way, I observed it as well, and I was wondering: how bad is
too bad? My guess was that as long as we insert a few thousand elements
(with more, I expect hash or pipapo to be used) in a few seconds, it
should be good enough.

> So I have been looking at an alternative approach (see attached patch) to
> address your comments. The idea is to move out the overlapping nodes
> from the element in the tree, instead keep them in a list.
> 
>                         root
>                         /  \
>                      elem   elem -> update -> update
>                             /  \
>                          elem  elem
> 
> Each rbtree element in the tree .has pending_list which stores the
> element that supersede the existing (inactive) element. There is also a
> .list which is used to add the element to the .pending_list. Elements
> in the tree might have a .pending_list with one or more elements.

I see a problem with this, that perhaps you already solved, but I don't
understand how.

The original issue here was that we have inactive elements in the tree
affecting the way we descend it to look for overlaps. Those inactive
elements are not necessarily overlapping with anything.

If they overlap, the issue is solved with your patch. But if they
don't...?

Sure, we'll grant insertion of overlapping elements in case the overlap
is with an inactive one, but this solves the particular case of
matching elements, not overlapping intervals.

At a first reading, I thought you found some magic way to push out all
inactive elements to some parallel, linked structure, which we can
ignore as we look for overlapping _intervals_. But that doesn't seem to
be the case, right?

-- 
Stefano