[PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Pablo Neira Ayuso]

The array resize function increments the size of the array in
NFT_ARRAY_EXTRA_SIZE slots for each update, this is unnecesarily
increasing the array size.

To determine the number of array slots:

- Use NFT_ARRAY_EXTRA_SIZE for new sets.
- Use the current maximum number of intervals in the live array.

Reported-by: Chris Arges <carges@cloudflare.com>
Fixes: 7e43e0a1141d ("netfilter: nft_set_rbtree: translate rbtree to array for binary search")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
v2: fix crash with new sets, reported by Florian.

 net/netfilter/nft_set_rbtree.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 853ff30a208c..bdcea649467f 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -646,7 +646,12 @@ static int nft_array_may_resize(const struct nft_set *set)
 	struct nft_array *array;
 
 	if (!priv->array_next) {
-		array = nft_array_alloc(nelems + NFT_ARRAY_EXTRA_SIZE);
+		if (priv->array)
+			new_max_intervals = priv->array->max_intervals;
+		else
+			new_max_intervals = NFT_ARRAY_EXTRA_SIZE;
+
+		array = nft_array_alloc(new_max_intervals);
 		if (!array)
 			return -ENOMEM;
 
-- 
2.47.3

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> v2: fix crash with new sets, reported by Florian.
> 
>  net/netfilter/nft_set_rbtree.c | 7 ++++++-
>  1 file changed, 6 insertions(+), 1 deletion(-)
> 
> diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> index 853ff30a208c..bdcea649467f 100644
> --- a/net/netfilter/nft_set_rbtree.c
> +++ b/net/netfilter/nft_set_rbtree.c
> @@ -646,7 +646,12 @@ static int nft_array_may_resize(const struct nft_set *set)
>  	struct nft_array *array;
>  
>  	if (!priv->array_next) {
> -		array = nft_array_alloc(nelems + NFT_ARRAY_EXTRA_SIZE);
> +		if (priv->array)
> +			new_max_intervals = priv->array->max_intervals;
> +		else
> +			new_max_intervals = NFT_ARRAY_EXTRA_SIZE;
> +
> +		array = nft_array_alloc(new_max_intervals);
>  		if (!array)
>  			return -ENOMEM;
>  

I wonder if rbtree code should try harder to compact memory.

We can't defer allocation to commit hook because commit hook can't fail.
But its the only location where we know the exact memory size needed:

1. To-be-removed elements have been unlinked from the tree
2. Expired elements have been unlinked too

So, after the tree walk, num_intervals is the actual needed count and
no longer a worst-case estimate.

What if this would check num_intervals vs.
priv->array_next->num_intervals, and, if the difference is say, more
than 10% or more than 1 page of memory, try to allocate a better size?

If the allocation fails, too bad, use the existing one.
If it works, copy the elements over, free the larger allocation and
use the "better fit".

netlink has similar approach via netlink_trim() to avoid stuffing
large allocations into socket queues.

An even better way would be to just kvrealloc() but in the vmalloc case
this code path doesn't shrink the VM area in case new requested size
is smaller than the existing one, so that would require work on mm side
first.

One issue is that if you have a large rbtree, and the userspace pattern
is:

"flush set t s; add element t s { $huge }" then rbtree will roughly have
double the memory size that it would actually need: it will
first allocate the existing element size, then continue to realloc to
accomodate the new incoming elements, but, since the flush only takes
effect post-commit, can't account for the reduced size post-commit.

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Pablo Neira Ayuso]

On Sat, Mar 07, 2026 at 10:07:12AM +0100, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > v2: fix crash with new sets, reported by Florian.
> > 
> >  net/netfilter/nft_set_rbtree.c | 7 ++++++-
> >  1 file changed, 6 insertions(+), 1 deletion(-)
> > 
> > diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> > index 853ff30a208c..bdcea649467f 100644
> > --- a/net/netfilter/nft_set_rbtree.c
> > +++ b/net/netfilter/nft_set_rbtree.c
> > @@ -646,7 +646,12 @@ static int nft_array_may_resize(const struct nft_set *set)
> >  	struct nft_array *array;
> >  
> >  	if (!priv->array_next) {
> > -		array = nft_array_alloc(nelems + NFT_ARRAY_EXTRA_SIZE);
> > +		if (priv->array)
> > +			new_max_intervals = priv->array->max_intervals;
> > +		else
> > +			new_max_intervals = NFT_ARRAY_EXTRA_SIZE;
> > +
> > +		array = nft_array_alloc(new_max_intervals);
> >  		if (!array)
> >  			return -ENOMEM;
> >  
> 
> I wonder if rbtree code should try harder to compact memory.
> 
> We can't defer allocation to commit hook because commit hook can't fail.
> But its the only location where we know the exact memory size needed:
> 
> 1. To-be-removed elements have been unlinked from the tree
> 2. Expired elements have been unlinked too
> 
> So, after the tree walk, num_intervals is the actual needed count and
> no longer a worst-case estimate.
> 
> What if this would check num_intervals vs.
> priv->array_next->num_intervals, and, if the difference is say, more
> than 10% or more than 1 page of memory, try to allocate a better size?
> 
> If the allocation fails, too bad, use the existing one.
> If it works, copy the elements over, free the larger allocation and
> use the "better fit".
> 
> netlink has similar approach via netlink_trim() to avoid stuffing
> large allocations into socket queues.
> 
> An even better way would be to just kvrealloc() but in the vmalloc case
> this code path doesn't shrink the VM area in case new requested size
> is smaller than the existing one, so that would require work on mm side
> first.
> 
> One issue is that if you have a large rbtree, and the userspace pattern
> is:
> 
> "flush set t s; add element t s { $huge }" then rbtree will roughly have
> double the memory size that it would actually need: it will
> first allocate the existing element size, then continue to realloc to
> accomodate the new incoming elements, but, since the flush only takes
> effect post-commit, can't account for the reduced size post-commit.

There is also set->ndeact that provides a hint on deactivated
elements.

And NFT_ARRAY_EXTRA_SIZE and resize can be revisited to allocate
memory areas that fit into the corresponding kmalloc slab.

So yes, there are smarter things that can be done here, but as for
this patch, my initial approach in this fix series was intentionally
simple.

As for this patch, I am just targetting at fixing the current linear
growth in memory consumption of this array on each update.

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> There is also set->ndeact that provides a hint on deactivated
> elements.

Oh, right, I fogot about that.

So we even have an estimate of how many elements will disappear.
> 
> So yes, there are smarter things that can be done here, but as for
> this patch, my initial approach in this fix series was intentionally
> simple.

Sure, its better to use a simple patch for nf, rest can be expiremented
with in nf-next, I did not want to hold up this patch and I intend to
pick it up for nf.

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Pablo Neira Ayuso]

On Sat, Mar 07, 2026 at 02:06:23PM +0100, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > There is also set->ndeact that provides a hint on deactivated
> > elements.
> 
> Oh, right, I fogot about that.
> 
> So we even have an estimate of how many elements will disappear.
>
> > So yes, there are smarter things that can be done here, but as for
> > this patch, my initial approach in this fix series was intentionally
> > simple.
> 
> Sure, its better to use a simple patch for nf, rest can be expiremented
> with in nf-next, I did not want to hold up this patch and I intend to
> pick it up for nf.

I promise take a look into this in nf-next patch.

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Chris Arges]

On 2026-03-07 01:11:24, Pablo Neira Ayuso wrote:
> The array resize function increments the size of the array in
> NFT_ARRAY_EXTRA_SIZE slots for each update, this is unnecesarily
> increasing the array size.
> 
> To determine the number of array slots:
> 
> - Use NFT_ARRAY_EXTRA_SIZE for new sets.
> - Use the current maximum number of intervals in the live array.
> 
> Reported-by: Chris Arges <carges@cloudflare.com>
> Fixes: 7e43e0a1141d ("netfilter: nft_set_rbtree: translate rbtree to array for binary search")
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> ---
> v2: fix crash with new sets, reported by Florian.
> 
>  net/netfilter/nft_set_rbtree.c | 7 ++++++-
>  1 file changed, 6 insertions(+), 1 deletion(-)
> 

Pablo,

I was able to test with this patch applied on top of v6.18.16; however the
memory consumption remained high and similar to v6.18.16 without this patch.

My VM reproducer runs the services and checks for slab memory increases. In a
passing test case, the unreclaimable slab memory reaches about 1.4G and
stabilizes. In a failure test case unreclaimable slab memory goes beyond 4.4G
then the process gets OOM killed due to cgroup memory limits.

Also, using this reproducer I re-verified that this patch is what changes
slab memory.stat characteristics from within the cgroup:
- 7e43e0a1141d netfilter: nft_set_rbtree: translate rbtree to array for binary search

Finally, I reverted the following patches from v6.18.16 and re-tested using my
reproducer:
- 648946966a08 netfilter: nft_set_rbtree: validate open interval overlap
- 782f2688128e netfilter: nft_set_rbtree: validate element belonging to interval
- 35f83a75529a netfilter: nft_set_rbtree: don't gc elements on insert
- 5599fa810b50 netfilter: nft_set_rbtree: remove seqcount_rwlock_t
- 2aa34191f06f netfilter: nft_set_rbtree: use binary search array in get command
- 7e43e0a1141d netfilter: nft_set_rbtree: translate rbtree to array for binary search
In this instance memory allocations were again around 1.4G.

Any suggestions for other tests, I can rebuild with memory debugging config as
well.

Also, could there be an option here to opt-out of this performance optimization
in favor of retaining existing memory characteristics?

Thanks,
--chris

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Pablo Neira Ayuso]

On Wed, Mar 11, 2026 at 11:29:59AM -0500, Chris Arges wrote:
> On 2026-03-07 01:11:24, Pablo Neira Ayuso wrote:
> > The array resize function increments the size of the array in
> > NFT_ARRAY_EXTRA_SIZE slots for each update, this is unnecesarily
> > increasing the array size.
> > 
> > To determine the number of array slots:
> > 
> > - Use NFT_ARRAY_EXTRA_SIZE for new sets.
> > - Use the current maximum number of intervals in the live array.
> > 
> > Reported-by: Chris Arges <carges@cloudflare.com>
> > Fixes: 7e43e0a1141d ("netfilter: nft_set_rbtree: translate rbtree to array for binary search")
> > Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> > ---
> > v2: fix crash with new sets, reported by Florian.
> > 
> >  net/netfilter/nft_set_rbtree.c | 7 ++++++-
> >  1 file changed, 6 insertions(+), 1 deletion(-)
> > 
> 
> Pablo,

Chris,

> I was able to test with this patch applied on top of v6.18.16; however the
> memory consumption remained high and similar to v6.18.16 without this patch.

Makes no sense to me.

> My VM reproducer runs the services and checks for slab memory increases. In a
> passing test case, the unreclaimable slab memory reaches about 1.4G and
> stabilizes. In a failure test case unreclaimable slab memory goes beyond 4.4G
> then the process gets OOM killed due to cgroup memory limits.

I have to review again what I posted. You mean, memory keeps for each
dynamic update, increasing until it reaches OOM?

> Also, using this reproducer I re-verified that this patch is what changes
> slab memory.stat characteristics from within the cgroup:
> - 7e43e0a1141d netfilter: nft_set_rbtree: translate rbtree to array for binary search
> 
> Finally, I reverted the following patches from v6.18.16 and re-tested using my
> reproducer:
> - 648946966a08 netfilter: nft_set_rbtree: validate open interval overlap
> - 782f2688128e netfilter: nft_set_rbtree: validate element belonging to interval
> - 35f83a75529a netfilter: nft_set_rbtree: don't gc elements on insert

Are you using timeout in your set?

> - 5599fa810b50 netfilter: nft_set_rbtree: remove seqcount_rwlock_t
> - 2aa34191f06f netfilter: nft_set_rbtree: use binary search array in get command
> - 7e43e0a1141d netfilter: nft_set_rbtree: translate rbtree to array for binary search
> In this instance memory allocations were again around 1.4G.
> 
> Any suggestions for other tests, I can rebuild with memory debugging config as
> well.
> 
> Also, could there be an option here to opt-out of this performance optimization
> in favor of retaining existing memory characteristics?

This series is fixing a real bug, now you may experience possible
false negatives in lookups with what you have reverted.

I am going to collect memory numbers and post them here, I will try to
mimic a script from your description.

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Chris Arges]

On 2026-03-11 17:43:27, Pablo Neira Ayuso wrote:
> On Wed, Mar 11, 2026 at 11:29:59AM -0500, Chris Arges wrote:
> > On 2026-03-07 01:11:24, Pablo Neira Ayuso wrote:
> > > The array resize function increments the size of the array in
> > > NFT_ARRAY_EXTRA_SIZE slots for each update, this is unnecesarily
> > > increasing the array size.
> > > 
> > > To determine the number of array slots:
> > > 
> > > - Use NFT_ARRAY_EXTRA_SIZE for new sets.
> > > - Use the current maximum number of intervals in the live array.
> > > 
> > > Reported-by: Chris Arges <carges@cloudflare.com>
> > > Fixes: 7e43e0a1141d ("netfilter: nft_set_rbtree: translate rbtree to array for binary search")
> > > Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> > > ---
> > > v2: fix crash with new sets, reported by Florian.
> > > 
> > >  net/netfilter/nft_set_rbtree.c | 7 ++++++-
> > >  1 file changed, 6 insertions(+), 1 deletion(-)
> > > 
> > 
> > Pablo,
> 
> Chris,
> 
> > I was able to test with this patch applied on top of v6.18.16; however the
> > memory consumption remained high and similar to v6.18.16 without this patch.
> 
> Makes no sense to me.
> 

I did something like this:
```
git checkout v6.18.16
patch -p1 < this.patch
vng -b
```
Then ran my reproducer; unreclaimable slab memory went up past 4G showing
the high memory consumption.

> > My VM reproducer runs the services and checks for slab memory increases. In a
> > passing test case, the unreclaimable slab memory reaches about 1.4G and
> > stabilizes. In a failure test case unreclaimable slab memory goes beyond 4.4G
> > then the process gets OOM killed due to cgroup memory limits.
> 
> I have to review again what I posted. You mean, memory keeps for each
> dynamic update, increasing until it reaches OOM?
> 

Correct.

> > Also, using this reproducer I re-verified that this patch is what changes
> > slab memory.stat characteristics from within the cgroup:
> > - 7e43e0a1141d netfilter: nft_set_rbtree: translate rbtree to array for binary search
> > 
> > Finally, I reverted the following patches from v6.18.16 and re-tested using my
> > reproducer:
> > - 648946966a08 netfilter: nft_set_rbtree: validate open interval overlap
> > - 782f2688128e netfilter: nft_set_rbtree: validate element belonging to interval
> > - 35f83a75529a netfilter: nft_set_rbtree: don't gc elements on insert
> 
> Are you using timeout in your set?
>
No.
 
> > - 5599fa810b50 netfilter: nft_set_rbtree: remove seqcount_rwlock_t
> > - 2aa34191f06f netfilter: nft_set_rbtree: use binary search array in get command
> > - 7e43e0a1141d netfilter: nft_set_rbtree: translate rbtree to array for binary search
> > In this instance memory allocations were again around 1.4G.
> > 
> > Any suggestions for other tests, I can rebuild with memory debugging config as
> > well.
> > 
> > Also, could there be an option here to opt-out of this performance optimization
> > in favor of retaining existing memory characteristics?
> 
> This series is fixing a real bug, now you may experience possible
> false negatives in lookups with what you have reverted.
> 

Understood, we want to use these patches in the long run; once memory usage
issues are fixed.

> I am going to collect memory numbers and post them here, I will try to
> mimic a script from your description.

Sure, I can provide more details if needed, but should be similar as
explained in https://lore.kernel.org/all/aahw_h5DdmYZeeqw@20HS2G4/.

Thanks,
--chris

[PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Pablo Neira Ayuso]

The array resize function increments the size of the array in
NFT_ARRAY_EXTRA_SIZE slots for each update, this is unnecesarily
increasing the array size.

To determine the number of array slots:

- Use NFT_ARRAY_EXTRA_SIZE for new sets.
- Use the current maximum number of intervals in the live array.

Reported-by: Chris Arges <carges@cloudflare.com>
Fixes: 7e43e0a1141d ("netfilter: nft_set_rbtree: translate rbtree to array for binary search")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
v2: fix crash with new sets, reported by Florian.

 net/netfilter/nft_set_rbtree.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 853ff30a208c..bdcea649467f 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -646,7 +646,12 @@ static int nft_array_may_resize(const struct nft_set *set)
 	struct nft_array *array;
 
 	if (!priv->array_next) {
-		array = nft_array_alloc(nelems + NFT_ARRAY_EXTRA_SIZE);
+		if (priv->array)
+			new_max_intervals = priv->array->max_intervals;
+		else
+			new_max_intervals = NFT_ARRAY_EXTRA_SIZE;
+
+		array = nft_array_alloc(new_max_intervals);
 		if (!array)
 			return -ENOMEM;
 
-- 
2.47.3

Re: [PATCH nf,v2] netfilter: nft_set_rbtree: allocate same array size on updates

[Pablo Neira Ayuso]

This is an incorrect resend, apologies.

On Sun, Mar 08, 2026 at 12:23:41PM +0100, Pablo Neira Ayuso wrote:
> The array resize function increments the size of the array in
> NFT_ARRAY_EXTRA_SIZE slots for each update, this is unnecesarily
> increasing the array size.
> 
> To determine the number of array slots:
> 
> - Use NFT_ARRAY_EXTRA_SIZE for new sets.
> - Use the current maximum number of intervals in the live array.
> 
> Reported-by: Chris Arges <carges@cloudflare.com>
> Fixes: 7e43e0a1141d ("netfilter: nft_set_rbtree: translate rbtree to array for binary search")
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> ---
> v2: fix crash with new sets, reported by Florian.
> 
>  net/netfilter/nft_set_rbtree.c | 7 ++++++-
>  1 file changed, 6 insertions(+), 1 deletion(-)
> 
> diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
> index 853ff30a208c..bdcea649467f 100644
> --- a/net/netfilter/nft_set_rbtree.c
> +++ b/net/netfilter/nft_set_rbtree.c
> @@ -646,7 +646,12 @@ static int nft_array_may_resize(const struct nft_set *set)
>  	struct nft_array *array;
>  
>  	if (!priv->array_next) {
> -		array = nft_array_alloc(nelems + NFT_ARRAY_EXTRA_SIZE);
> +		if (priv->array)
> +			new_max_intervals = priv->array->max_intervals;
> +		else
> +			new_max_intervals = NFT_ARRAY_EXTRA_SIZE;
> +
> +		array = nft_array_alloc(new_max_intervals);
>  		if (!array)
>  			return -ENOMEM;
>  
> -- 
> 2.47.3
> 
>