Re: [PATCH nf] netfilter: nft_set_rbtree: do not pair an expired start with another interval's end

[Pablo Neira Ayuso]

On Sat, Oct 31, 2026 at 06:44:43PM +0100, Pablo Neira Ayuso wrote:
> On Sat, Oct 31, 2026 at 03:54:05PM +0000, Joas Antonio dos Santos via B4 Relay wrote:
> > From: Joas Antonio dos Santos <joasantonio108@xxxxxxxxx>
> > 
> > Garbage collection of an expired interval start element also removes its
> > end element. Both the insertion path, nft_rbtree_gc_elem(), and the
> > commit path, nft_rbtree_gc_scan(), find that end element by its position
> > in the tree, and both can pick the end element of a different, live
> > interval:
> >
> > - nft_rbtree_gc_elem() walks towards higher keys and skips end elements
> >   that are not active in both generations. If the end element of the
> >   expired interval is being deleted in the same transaction, the walk
> >   skips it, passes the start element of the next interval and takes that
> >   interval's end element instead.
> > 
> > - nft_rbtree_gc_scan() remembers the last end element it visited in
> >   rbe_end, but does not clear it when it visits a live start element. An
> >   expired start element without an end element (a start-only element, or
> >   an interval whose end element was already removed) then takes the end
> >   element of the live interval above it.
> > 
> > In both cases the live interval [S, E) loses E: the set no longer holds
> > the interval that userspace added, and deleting [S, E) later fails with
> > ENOENT.
> > 
> > In the insertion path, stop the walk at the first element that is active
> > in the current generation. Elements added by this transaction are still
> > skipped, as intended by commit 60c0c230c6f0 ("netfilter: nft_set_rbtree:
> > skip end interval element from gc"). If that element is a start element,
> > the expired interval has no end element. If it is an end element that
> > this transaction is removing, leave it to the transaction. In the commit
> > path, clear rbe_end when a live start element is visited.
> > 
> > Reproduced on current mainline under QEMU (arm64, KASAN), from an
> > unprivileged user in a new user and network namespace:
> > 
> > - insertion path: add [10,20) with a 50ms timeout and [30,40), wait,
> >   then in one batch delete the end element 20 and add [12,13).
> 
> I don't follow.
> 
> You add [10,20) with 50ms...
> 
> and [30,40) with... what timeout?
> 
> you wait how long?
> 
> You follow up with another batch an you only delete 20?
> 
> >   Before: a GET for 45 finds an element, the end element 40 is gone and
> >   deleting [30,40) fails with ENOENT. After: 45 is not found, 40 is
> >   present and the delete succeeds.
> > 
> > - commit path: add [30,40) and a start-only element 10 with a 50ms
> >   timeout to a set with a 100ms gc interval, wait, then add [200,201),
> >   whose insertion walk stops at the highest element, so only the
> >   commit-time scan reaches 10. Before: the end element 40 is gone and
> >   deleting [30,40) fails with ENOENT. After: both work.
> > 
> > Normal expiry, and a new interval whose end element shares the key of an
> > expired start element (the case handled by 60c0c230c6f0), behave the same
> > before and after. About 39000 random batches on interval sets with
> > timeouts, with and without slab/page allocation fault injection, showed
> > no KASAN, lockdep or WARN reports with the patch applied.

Hm, no KASAN, no splat, what's the issue, really?

> > The insertion path issue was found with a small nfnetlink fuzzer. Both
> > paths had been pointed out earlier by the netdev AI review of commit
> > 86b6471e690c ("netfilter: nft_set_rbtree: skip transaction elements
> > during GC"), see the Link below.
> > 
> > Fixes: f718863aca46 ("netfilter: nft_set_rbtree: fix overlap expiration walk")
> > Fixes: 8d8540c4f5e0 ("netfilter: nft_set_rbtree: add timeout support")
> > Link: https://lore.kernel.org/all/179063970372.3145.17414936987144600093@xxxxxxxxxx/
> > Signed-off-by: Joas Antonio dos Santos <joasantonio108@xxxxxxxxx>
> > ---
> > Tool-use note: the fuzzer, the directed tests and the analysis were
> > prepared with help from an LLM-based assistant; I reviewed the change
> > and built and ran all tests myself. Test harness available on request.
> > 
> > This is a resend through the kernel.org web endpoint: my earlier
> > submission of this patch was blocked by my mail provider and never
> > reached the lists.
> > ---
> >  net/netfilter/nft_set_rbtree.c | 23 +++++++++++++++++++----
> >  1 file changed, 19 insertions(+), 4 deletions(-)
> > 
> > diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> > index fbe1750f1..086823067 100644
> > --- a/net/netfilter/nft_set_rbtree.c
> > +++ b/net/netfilter/nft_set_rbtree.c
> > @@ -215,17 +215,25 @@ nft_rbtree_gc_elem(const struct nft_set *__set, struct nft_rbtree *priv,
> >  	struct nft_set *set = (struct nft_set *)__set;
> >  	struct rb_node *prev = rb_prev(&rbe->node);
> >  	struct net *net = read_pnet(&set->net);
> > +	u8 cur_genmask = nft_genmask_cur(net);
> >  	struct nft_rbtree_elem *rbe_prev;
> >  
> >  	/* search for end interval coming before this element.
> >  	 * end intervals don't carry a timeout extension, they
> >  	 * are coupled with the interval start element.
> > +	 *
> > +	 * Skip elements added in this transaction. The first element
> > +	 * that is active in the current generation is either the end
> > +	 * element of this interval or the start element of another
> > +	 * interval, in which case this interval has no end element.
> >  	 */
> >  	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))
> > +		if (nft_set_elem_active(&rbe_prev->ext, cur_genmask)) {
> > +			if (!nft_rbtree_interval_end(rbe_prev))
> > +				prev = NULL;
> >  			break;
> > +		}
> >  
> >  		prev = rb_prev(prev);
> >  	}
> > @@ -233,7 +241,11 @@ nft_rbtree_gc_elem(const struct nft_set *__set, struct nft_rbtree *priv,
> >  	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);
> > +		/* end element is being removed by this transaction */
> > +		if (nft_set_elem_active(&rbe_prev->ext, NFT_GENMASK_ANY))
> > +			nft_rbtree_gc_elem_move(net, set, priv, rbe_prev);
> > +		else
> > +			rbe_prev = NULL;
> >  	}
> >  
> >  	nft_rbtree_gc_elem_move(net, set, priv, rbe);
> > @@ -911,8 +923,11 @@ static void nft_rbtree_gc_scan(struct nft_set *set)
> >  			rbe_end = rbe;
> >  			continue;
> >  		}
> > -		if (!__nft_set_elem_expired(&rbe->ext, tstamp))
> > +		if (!__nft_set_elem_expired(&rbe->ext, tstamp)) {
> > +			/* rbe_end belongs to this live interval */
> > +			rbe_end = NULL;
> >  			continue;
> > +		}
> >  
> >  		/* end element needs to be removed first, it has
> >  		 * no timeout extension.
> > 
> > ---
> > base-commit: c339f4010dea8b0d754f84ace70cd1b089878ef8
> > change-id: 20261031-b4-nft-rbtree-gc-1d9c72dba2bd
> > 
> > Best regards,
> > -- 
> > Joas Antonio dos Santos <joasantonio108@xxxxxxxxx>
> > 
> > 
>