Re: [PATCH net 08/11] netfilter: nft_set_rbtree: skip transaction elements during GC

[netdev-bot+sashiko@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential
issue(s) to consider.

Critical: 0 · High: 1 (1) · Medium: 0 · Low: 0

If you believe none of the issues are legitimate, please reply to each
issue of Medium severity or higher and explain why the AI is wrong.
If any of them are legitimate and you plan to respin, please let patchwork
know by including "pw-bot: cr" as a separate line at the end of your reply
(one such reply per series is enough).

- [High] The patch does not fix the stale end pairing in
  nft_rbtree_gc_scan() (net/netfilter/nft_set_rbtree.c).

Pre-existing issues:
- [High] This problem wasn't introduced by this patch, but the insertion-
  time GC path has the same wrong-end pairing, and this commit leaves it…

--

netfilter: nft_set_rbtree: skip transaction elements during GC

This patch makes nft_rbtree_gc_scan() skip any element that is not fully
active in both generations. The goal is to keep elements added by the
transaction being committed out of the scan. Without that, a new end
element could be paired with an unrelated expired start and freed before
it is activated.

> diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> index 9894832281c4b..12431b55752fb 100644
> --- a/net/netfilter/nft_set_rbtree.c
> +++ b/net/netfilter/nft_set_rbtree.c
> @@ -900,6 +900,8 @@ static void nft_rbtree_gc_scan(struct nft_set *set)
>  		next = rb_next(node);
>  
>  		rbe = rb_entry(node, struct nft_rbtree_elem, node);
> +		if (!nft_set_elem_active(&rbe->ext, NFT_GENMASK_ANY))
> +			continue;

[Severity: High]
The commit message says this change "preserves interval pairing across
skipped elements". Is that the case in nft_rbtree_gc_scan()?

rbe_end is only cleared after a GC move. When the scan reaches a fully
active start that has not expired, rbe_end still points at that start's
own end:

	if (nft_rbtree_interval_end(rbe)) {
		rbe_end = rbe;
		continue;
	}
	if (!__nft_set_elem_expired(&rbe->ext, tstamp))
		continue;

The new skip also leaves rbe_end unchanged. Suppose the scan then reaches
an expired start with no end directly above it. This code then moves the
other interval's live end to priv->expired, and nft_rbtree_gc_queue()
frees it later:

	if (rbe_end) {
		nft_rbtree_gc_elem_move(net, set, priv, rbe_end);
		rbe_end = NULL;
	}

Take the reported trigger shape: a live interval above, the new elements
skipped, then an expired start without an end. Here the patch seems to
change only which end gets taken. Before, the new end element was taken,
which caused the UAF. Now it is the older, fully active end of the
interval above.

Can an orphaned expired start like this be created with the stock nft
tool? Running nft destroy element on an interval whose start has expired
seems to be enough:

nf_tables_delsetelem()
  nft_rbtree_deactivate() on the start
    -> returns NULL for the expired start, and start_rbe_cookie is
       reset to 0
    -> the -ENOENT is ignored for NFT_MSG_DESTROYSETELEM
  nft_rbtree_deactivate() on the end
    -> nft_rbtree_deactivate_same_interval() returns true because
       start_rbe_cookie is 0, so the end is deactivated

nft_set_commit_update() then removes the end from the tree with
nft_trans_elems_remove(). That happens before set->ops->commit() runs
nft_rbtree_gc_scan(). A crafted start-only NEWSETELEM placed in a gap is
also accepted by __nft_rbtree_insert() and gives the same shape.

In that case the higher interval [S_hi, E_hi) loses E_hi.
nft_rbtree_commit() then rebuilds it as [S_hi, next start). If it is the
topmost interval, it becomes open-ended (to == NULL).

Once S_hi expires, the next scan takes the end of the next live interval
above it. A later nft delete element on [S_hi, E_hi) also fails with
ENOENT because E_hi is gone.

Would it make sense to also clear rbe_end when a fully active start has
not expired?

	if (!__nft_set_elem_expired(&rbe->ext, tstamp)) {
		rbe_end = NULL;
		continue;
	}

[ ... ]

[Severity: High]
This is a pre-existing issue, not one introduced by this patch. The
insertion-time GC path appears to have the same wrong-end pairing, and
this patch leaves it unchanged.

__nft_rbtree_insert() calls nft_rbtree_gc_elem() when it finds an
expired start that is active in the current generation. The rb_prev()
walk stops at the first fully active end, whatever interval that end
belongs to:

net/netfilter/nft_set_rbtree.c:nft_rbtree_gc_elem() {
    ...
	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);
	}

	rbe_prev = NULL;
	if (prev) {
		rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node);
		nft_rbtree_gc_elem_move(net, set, priv, rbe_prev);
	}
    ...
}

The comment says end intervals "are coupled with the interval start
element", but nothing checks that coupling.

Consider a tree that, walked from high to low keys, holds:

  E_w (active), S_w (live), E_x, S_x (expired)

E_x is either pending deletion in the same batch or already removed by an
earlier nft destroy element. When an insertion walk reaches S_x, can the
rb_prev() walk skip E_x and S_w and pick E_w?

If so, nft_rbtree_gc_elem_move() erases E_w, the live end of
[S_w, E_w), and queues it on priv->expired. The next commit frees it and
rebuilds S_w as a wider or open-ended interval.

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260927220816.268206-2-pablo%40netfilter.org