Re: [net-next,08/11] netfilter: nft_set_rbtree: check for partial overlaps in anonymous sets

[Jakub Kicinski <kuba@kernel.org>]

This is an AI-generated review of your patch. The human sending this
email has considered the AI review valid, or at least plausible.

For local reproduction steps see https://netdev-ai.bots.linux.dev/ai-local.html
---
netfilter: nft_set_rbtree: check for partial overlaps in anonymous sets

Userspace provides an optimized representation in case intervals are
adjacent, where the end element is omitted. The existing partial overlap
detection logic skips anonymous set checks on start elements for this
reason. However, it is possible to add intervals that overlap to this
anonymous where two start elements with the same, eg. A-B, A-C where C < B.
This patch restores the check on overlapping start elements to report an
overlap.

> diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> --- a/net/netfilter/nft_set_rbtree.c
> +++ b/net/netfilter/nft_set_rbtree.c
> @@ -251,11 +251,22 @@ static bool nft_rbtree_update_first(const struct nft_set *set,
>  	return false;
>  }
>
> +static struct nft_rbtree_elem *nft_rbtree_prev_active(struct nft_rbtree_elem *rbe)
> +{
> +	struct rb_node *node;
> +
> +	node = rb_prev(&rbe->node);
> +	if (!node)
> +		return NULL;
> +
> +	return rb_entry(node, struct nft_rbtree_elem, node);
> +}
> +

Does nft_rbtree_prev_active() need to check whether the element is
actually active? The function name suggests it should return only active
elements, but it doesn't call nft_set_elem_active() to filter inactive ones.

Looking at the main overlap detection loop in __nft_rbtree_insert()
(lines 311-378), elements are filtered explicitly with 'if
(!nft_set_elem_active(&rbe->ext, genmask)) continue;' to ensure overlap
detection only considers elements that will be active after the commit.

However, when nft_rbtree_prev_active() is called at line 416, it returns
the previous element without checking if it's active. If this element is
inactive (being deleted in the current transaction), should it still affect
overlap detection?

The similar code pattern in nft_rbtree_gc_elem() shows explicit active
checking:

    while (prev) {
        rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node);
        if (nft_rbtree_interval_end(rbe_prev) &&
            nft_set_elem_active(&rbe_prev->ext, NFT_GENMASK_ANY))
            break;
        prev = rb_prev(prev);
    }

Could an inactive end interval element incorrectly trigger the overlap
check at line 417-418, causing a valid insertion to be rejected with
-ENOTEMPTY during a transaction where an old end element is being deleted
and a new start element is being inserted?

>  static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
>  			       struct nft_rbtree_elem *new,
>  			       struct nft_elem_priv **elem_priv)
>  {
> -	struct nft_rbtree_elem *rbe, *rbe_le = NULL, *rbe_ge = NULL;
> +	struct nft_rbtree_elem *rbe, *rbe_le = NULL, *rbe_ge = NULL, *rbe_prev;
>  	struct rb_node *node, *next, *parent, **p, *first = NULL;
>  	struct nft_rbtree *priv = nft_set_priv(set);
>  	u8 cur_genmask = nft_genmask_cur(net);

[ ... ]

>  	/* - new start element with existing closest, less or equal key value
>  	 *   being a start element: partial overlap, reported as -ENOTEMPTY.
>  	 *   Anonymous sets allow for two consecutive start element since they
> -	 *   are constant, skip them to avoid bogus overlap reports.
> +	 *   are constant, but validate that this new start element does not
> +	 *   sit in between an existing new and end elements: partial overlap,

This isn't a bug, but the phrase 'existing new and end elements' is
confusing. Should this say 'existing start and end elements' or 'existing
interval's start and end elements'?

> +	 *   reported as -ENOTEMPTY.
>  	 */
> -	if (!nft_set_is_anonymous(set) && rbe_le &&
> -	    nft_rbtree_interval_start(rbe_le) && nft_rbtree_interval_start(new))
> -		return -ENOTEMPTY;
> +	if (rbe_le &&
> +	    nft_rbtree_interval_start(rbe_le) && nft_rbtree_interval_start(new)) {
> +		if (!nft_set_is_anonymous(set))
> +			return -ENOTEMPTY;
> +
> +		rbe_prev = nft_rbtree_prev_active(rbe_le);
> +		if (rbe_prev && nft_rbtree_interval_end(rbe_prev))
> +			return -ENOTEMPTY;
> +	}

The Fixes tag references commit 7c84d41416d8, but wasn't the anonymous set
exception logic ('!nft_set_is_anonymous(set) && rbe_le && ...') actually
introduced by commit c9e6978e2725 ("netfilter: nft_set_rbtree: Switch to
node list walk for overlap detection")? That commit added the check being
modified here. While 7c84d41416d8 introduced the initial overlap detection,
c9e6978e2725 rewrote the logic and added the anonymous set exception that
turned out to be incorrect.