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

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

[Joas Antonio dos Santos via B4 Relay]

From: Joas Antonio dos Santos <joasantonio108@gmail.com>

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

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@kernel.org/
Signed-off-by: Joas Antonio dos Santos <joasantonio108@gmail.com>
---
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@gmail.com>

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 03:54:05PM +0000, Joas Antonio dos Santos via B4 Relay wrote:
> From: Joas Antonio dos Santos <joasantonio108@gmail.com>
> 
> 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.
> 
> 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@kernel.org/
> Signed-off-by: Joas Antonio dos Santos <joasantonio108@gmail.com>
> ---
> 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@gmail.com>
> 
> 

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@gmail.com>
> > 
> > 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@kernel.org/
> > Signed-off-by: Joas Antonio dos Santos <joasantonio108@gmail.com>
> > ---
> > 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@gmail.com>
> > 
> > 
> 

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

[Joas Antonio]

Hi Pablo,

Sorry, the description was too terse. Answering both mails here.

There is no memory safety issue, and I should have said so explicitly.
It is a correctness problem: after GC the set no longer holds what was
committed, and the packet path matches keys that were never added.

Exact sequence, raw nfnetlink. The set has NFT_SET_INTERVAL |
NFT_SET_TIMEOUT, an ipv4_addr key, no default timeout, and
NFTA_SET_GC_INTERVAL = 3600000, so the commit-time scan does not run and
only the insertion path is involved.

Batch 1 (NEWSETELEM): start 10 with a 50ms timeout, end 20 with no
timeout, start 30 and end 40 with no timeout. Only start 10 expires;
[30,40) is permanent.

Wait 200ms.

Batch 2: DELSETELEM of end 20 only, then NEWSETELEM of [12,13). This is
not something nft(8) generates, but the kernel accepts it. Inserting 12
runs nft_rbtree_gc_elem() on the expired start 10. The walk skips end
20 because it is being deleted in this transaction, passes start 30 and
takes end 40 as the end of 10. 10 and 40 are removed, and start 30 is
left without an end.

At commit, nft_rbtree_commit() turns 30 into an interval with ->from =
30 and ->to = NULL, and nft_array_lookup_cmp() treats ->to == NULL as
open-ended. So nft_rbtree_lookup() matches every key >= 30, while
userspace believes the set holds only [30,40). Reading back with
GETSETELEM, which uses the same array: without the patch 45 is found,
end 40 is gone and deleting [30,40) fails with ENOENT; with the patch
45 is not found, 40 is present and the delete succeeds.

To be fair about the limits: the only trigger I have is crafted
nfnetlink from whoever already owns the ruleset (CAP_NET_ADMIN in that
netns), so it does not cross a privilege boundary, and I have not found
an nft(8) command sequence that reaches the insertion-path case. The
commit-path case (nft_rbtree_gc_scan() not clearing rbe_end) uses a
different sequence without the lone end delete; I can send it in the
same detail if useful.

If you consider sets built from such batches unsupported, I think the
better fix is to reject deleting a lone interval end element, and I can
send that instead; or drop this if it is not worth the churn.

Thanks,
Joas

Em sáb., 31 de out. de 2026 às 14:50, Pablo Neira Ayuso
<pablo@netfilter.org> escreveu:
>
> 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@gmail.com>
> > >
> > > 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@kernel.org/
> > > Signed-off-by: Joas Antonio dos Santos <joasantonio108@gmail.com>
> > > ---
> > > 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@gmail.com>
> > >
> > >
> >



-- 
Joas Antonio dos Santos
Cyber Security Specialist and Ethical Hacker
joasantonio108@gmail.com
LinkedIn