Re: [PATCH nf,v4 1/2] netfilter: nft_set_rbtree: Switch to node list walk for overlap detection

[Stefano Brivio <sbrivio@redhat.com>]

On Wed, 18 Jan 2023 16:18:38 +0100
Pablo Neira Ayuso <pablo@netfilter.org> 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.
> 
> To speed up the overlap check, descent the tree to find a greater
> element that is closer to the key value to insert. Then walk down the
> node list for overlap detection. Starting the overlap check from
> rb_first() unconditionally is slow, it takes 10 times longer due to the
> full linear traversal of the list.
> 
> Moreover, perform garbage collection of expired elements when walking
> down the node list to avoid bogus overlap reports.
> 
> 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.
> 
> Based on initial patch from Stefano Brivio, including text from the
> original patch description too.
> 
> Fixes: 7c84d41416d8 ("netfilter: nft_set_rbtree: Detect partial overlaps on insertion")
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> ---
> v4: - s/Descent/Descend in comments as per Stefano.
>     - reintroduce nft_rbtree_update_first().

Reviewed-by: Stefano Brivio <sbrivio@redhat.com>

-- 
Stefano