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

[Stefano Brivio <sbrivio@redhat.com>]

Hi Pablo,

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.
> 
> 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.
> 
> The .deactivate path looks for the last (possibly) active element. The
> .remove path depends on the element state: a) element is singleton (no
> pending elements), then erase from tree, b) element has a pending
> list, then replace the first element in the pending_list by this node,
> and splice pending_list (there might be more elements), c) this
> element is in the pending_list, the just remove it. This handles both
> commit (walks through the list of transaction forward direction) and
> abort path (walks through the list of transactions in backward
> direction).

I think that's brilliant, give me a couple of days to have a thorough
look at it.

-- 
Stefano