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?
> 
> 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.

I think this is almost correct, but we need to modify it slightly.
Consider this tree:

      A: 1 (s, a)
       /        \
      /          \
B: 1 (s, i)    C: 3 (e, i)

where, again, 's': starts, 'e': ends, 'a': active, 'i': inactive. Nodes
are additionally named.

We want to insert 2 as a start element, and 'first' in your patch
becomes leaf B, "1 (s, i)" -- not the A node, "1 (s, a)".

Now, depending on the red-black tree insertion implementation (I didn't
bother to check, I guess it should be independent), in the list walk,
A might come before or after B.

If B is before A, fine, we'll meet A and mark it as "rbe_le" (closest
from left).

If A comes before B, we won't meet A, and we won't have a closest
element from the left. This affects the overlapping decision.

The only ambiguity here is represented by elements having the same key,
and a set of such elements is allowed in the tree iff at most one is
active. So we just need to avoid replacing an active "first" by an
inactive node with the same key. Eventually, we'll visit all the nodes
having the same keys, if any:

> +	parent = NULL;
> +	p = &priv->root.rb_node;
> +	while (*p != NULL) {
> +		parent = *p;
> +		rbe = rb_entry(parent, struct nft_rbtree_elem, node);
> +		d = nft_rbtree_cmp(set, rbe, new);
> +
> +		if (d < 0)
> +			p = &parent->rb_left;
> +		else if (d > 0) {
> +			first = &rbe->node;

			if (!first || nft_rbtree_cmp(set, rbe, first) ||
			    nft_set_elem_expired(&first->ext)) ||
			    !nft_set_elem_active(&first->ext, genmask))
				first = &rbe->node;

> +			p = &parent->rb_right;
> +		} else {
> +			first = &rbe->node;

...and the same here. Maybe we should re-introduce the "expired or
inactive" helper.

> +			if (nft_rbtree_interval_end(rbe))
> +				p = &parent->rb_left;
> +			else
> +				p = &parent->rb_right;
> +		}
> +	}
> +
> +	if (!first)
> +		first = rb_first(&priv->root);

> 2) annotate closest active element that is less than the new element,
>    walking over the ordered list.

The description looks correct to me, but I'm not sure why you add a
break here:

> -		if (d <= 0 && (!rbe_le || nft_rbtree_cmp(set, rbe, rbe_le) > 0))
> +		/* annotate element coming before new element. */
> +		if (d < 0 && (!rbe_le || nft_rbtree_cmp(set, rbe, rbe_le) > 0)) {
>  			rbe_le = rbe;
> +			break;
> +		}

we should stop here iff rbe_ge is already set, right? Otherwise we are
skipping step 3) below.

> 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.
> 
> 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.

Everything else looks good to me, thanks a lot, I hope we're finally
sorting this for good :)

-- 
Stefano