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

[Stefano Brivio <sbrivio@redhat.com>]

On Fri, 15 Jul 2022 13:13:52 +0200
Pablo Neira Ayuso <pablo@netfilter.org> wrote:

> On Wed, Jul 06, 2022 at 11:12:42PM +0200, Stefano Brivio wrote:
> > On Tue, 5 Jul 2022 13:53:47 +0200
> > Pablo Neira Ayuso <pablo@netfilter.org> wrote:  
> [...]
> > This simplifies the handling of those cases, we wouldn't need all those
> > clauses anymore, but I really think that the existing problem comes from
> > the fact we can *not* descend the tree just by selecting key values.  
> 
> Thanks for explaining.
> 
> The traversal rbtree via rb_first() and rb_next() is like an ordered
> linear list walk, maybe it is possible to reduce the number of
> elements to find an overlap?

Hah, yes, that's what I was also thinking about, but:

> I'm attaching an incremental patch on top of yours, idea is:
> 
> 1) find the closest element whose key is less than the new element
>    by descending the tree. This provides the first node to walk.

this step is also prone to the original issue, that is, the choice of
the first node to walk might also be affected by inactive elements.

Now, I _guess_ the way you implemented it (not checking if elements
are active in this step) should be correct in any case, because the
tree ordering is always correct, so any active element that might be
"hidden" should become part of the walk anyway.

But give me a couple of days to think about it and if there might be
other corner cases.

> 2) annotate closest active element that is less than the new element,
>    walking over the ordered list.
> 
> 3) annotate closest active element that is more than the new element,
>    Stop walking the ordered list.
> 
> 4) if new element is an exact match, then EEXIST.
> 
> 5) if new element is end and closest less than element is end, or
>    if new element is start and closest less than element is start, or
>    if new element is end and closest more than element is end,
>    Then ENOTEMPTY.

All these look safe (and correct) to me.

> Inactive/expired elements are skipped while walking the ordered linear
> list as usual.
> 
> With this incremental patch, I don't observe longer time to load
> interval sets.

Thanks a lot. I'll get back to you in a bit.

-- 
Stefano