Re: [PATCH nf] netfilter: nft_set_rbtree: bogus lookup/get on consecutive elements in named sets

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

On Sat, Dec 07, 2019 at 12:03:07PM +0100, Phil Sutter wrote:
> Hi Pablo,
> 
> On Fri, Dec 06, 2019 at 08:39:38PM +0100, Pablo Neira Ayuso wrote:
> > On Fri, Dec 06, 2019 at 08:26:47PM +0100, Pablo Neira Ayuso wrote:
> > > On Thu, Dec 05, 2019 at 11:04:08PM +0100, Phil Sutter wrote:
> > > > Hi Pablo,
> > > > 
> > > > On Thu, Dec 05, 2019 at 07:07:06PM +0100, Pablo Neira Ayuso wrote:
> > > > > The existing rbtree implementation might store consecutive elements
> > > > > where the closing element and the opening element might overlap, eg.
> > > > > 
> > > > > 	[ a, a+1) [ a+1, a+2)
> > > > > 
> > > > > This patch removes the optimization for non-anonymous sets in the exact
> > > > > matching case, where it is assumed to stop searching in case that the
> > > > > closing element is found. Instead, invalidate candidate interval and
> > > > > keep looking further in the tree.
> > > > > 
> > > > > This patch fixes the lookup and get operations.
> > > > 
> > > > I didn't get what the actual problem is?
> > > 
> > > The lookup/get results false, while there is an element in the rbtree.
> > > Moreover, the get operation returns true as if a+2 would be in the
> > > tree. This happens with named sets after several set updates, I could
> > > reproduce the issue with several elements mixed with insertion and
> > > deletions in one batch.
> > 
> > To extend the problem description: The issue is that the existing
> > lookup optimization (that only works for the anonymous sets) might not
> > reach the opening [ a+1, ... element if the closing ... , a+1) is
> > found in first place when walking over the rbtree. Hence, walking the
> > full tree in that case is needed.
> 
> Ah! Thanks a lot for your elaborations. It was really hard to grasp what
> all this is about from the initial commit message. :)

I'll append this to the description before applying, no problem,
thanks for asking.

> Sometimes I wonder if we should do more set optimizations under the hood
> when adding elements. Right now, we don't touch existing ones although
> it would make sense. And we could be more intelligent for example if a
> set contains 20-30 and a user adds 25-35.

Yes, if 'automerge' is set on, then nft should start doing some more
intelligent stuff. Basically the idea is: check if this interval
overlaps with an existing one, if so transaction looks like this:

        [ delete 25-35 | add 20-35 ]

With the existing transaction infrastructure in place, I think it
should not be too hard. There's already a routine to check for
overlaps. If this is a data mapping, this needs to be careful to not
merge intervals that have different data on the right hand side.

There's another problem, I think incremental userspace cache is still
incomplete. I can probably scratch time and look into this, this might
not happen before 2020 though.

Thanks.