[PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Pablo Neira Ayuso]

Chris Arges reports high memory consumption with thousands of
containers, this patch revisits the array allocation logic.

For anonymous sets, start by 16 slots (which takes 256 bytes on x86_64).
Expand it by x2 until threshold of 512 slots is reached, over that
threshold, expand it by x1.5.

For non-anonymous set, start by 1024 slots in the array (which takes 16
Kbytes initially on x86_64). Expand it by x1.5.

Use set->ndeact to subtract deactivated elements when calculating the
number of the slots in the array, otherwise the array size array gets
increased artifically. Add special case shrink logic to deal with flush
set too.

The shrink logic is skipped by anonymous sets.

Use check_add_overflow() to calculate the new array size.

Add a WARN_ON_ONCE check to make sure elements fit into the new array
size.

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>
---
v4: use maybe_grow: goto tag instead of grow:
    Add note in commit description: "The shrink logic is skipped by anonymous sets."

 net/netfilter/nft_set_rbtree.c | 91 +++++++++++++++++++++++++++-------
 1 file changed, 72 insertions(+), 19 deletions(-)

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index 4061c506be53..e4d2cf04efab 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -616,14 +616,12 @@ static struct nft_array *nft_array_alloc(u32 max_intervals)
 	return array;
 }
 
-#define NFT_ARRAY_EXTRA_SIZE	10240
-
 /* Similar to nft_rbtree_{u,k}size to hide details to userspace, but consider
  * packed representation coming from userspace for anonymous sets too.
  */
 static u32 nft_array_elems(const struct nft_set *set)
 {
-	u32 nelems = atomic_read(&set->nelems);
+	u32 nelems = atomic_read(&set->nelems) - set->ndeact;
 
 	/* Adjacent intervals are represented with a single start element in
 	 * anonymous sets, use the current element counter as is.
@@ -639,18 +637,80 @@ static u32 nft_array_elems(const struct nft_set *set)
 	return (nelems / 2) + 2;
 }
 
-static int nft_array_may_resize(const struct nft_set *set)
+#define NFT_ARRAY_INITIAL_SIZE		1024
+#define NFT_ARRAY_INITIAL_ANON_SIZE	16
+#define NFT_ARRAY_INITIAL_ANON_THRESH	(8192U / sizeof(struct nft_array_interval))
+
+static int nft_array_may_resize(const struct nft_set *set, bool flush)
 {
-	u32 nelems = nft_array_elems(set), new_max_intervals;
+	u32 initial_intervals, max_intervals, new_max_intervals, delta;
+	u32 shrinked_max_intervals, nelems = nft_array_elems(set);
 	struct nft_rbtree *priv = nft_set_priv(set);
 	struct nft_array *array;
 
-	if (!priv->array_next) {
-		if (priv->array)
+	if (nft_set_is_anonymous(set))
+		initial_intervals = NFT_ARRAY_INITIAL_ANON_SIZE;
+	else
+		initial_intervals = NFT_ARRAY_INITIAL_SIZE;
+
+	if (priv->array_next) {
+		max_intervals = priv->array_next->max_intervals;
+		new_max_intervals = priv->array_next->max_intervals;
+	} else {
+		if (priv->array) {
+			max_intervals = priv->array->max_intervals;
 			new_max_intervals = priv->array->max_intervals;
-		else
-			new_max_intervals = NFT_ARRAY_EXTRA_SIZE;
+		} else {
+			max_intervals = 0;
+			new_max_intervals = initial_intervals;
+		}
+	}
+
+	if (nft_set_is_anonymous(set))
+		goto maybe_grow;
+
+	if (flush) {
+		/* Set flush just started, nelems still report elements.*/
+		nelems = 0;
+		new_max_intervals = NFT_ARRAY_INITIAL_SIZE;
+		goto realloc_array;
+	}
+
+	if (check_add_overflow(new_max_intervals, new_max_intervals,
+			       &shrinked_max_intervals))
+		return -EOVERFLOW;
+
+	shrinked_max_intervals = DIV_ROUND_UP(shrinked_max_intervals, 3);
 
+	if (shrinked_max_intervals > NFT_ARRAY_INITIAL_SIZE &&
+	    nelems < shrinked_max_intervals) {
+		new_max_intervals = shrinked_max_intervals;
+		goto realloc_array;
+	}
+maybe_grow:
+	if (nelems > new_max_intervals) {
+		if (nft_set_is_anonymous(set) &&
+		    new_max_intervals < NFT_ARRAY_INITIAL_ANON_THRESH) {
+			new_max_intervals <<= 1;
+		} else {
+			delta = new_max_intervals >> 1;
+			if (check_add_overflow(new_max_intervals, delta,
+					       &new_max_intervals))
+				return -EOVERFLOW;
+		}
+	}
+
+realloc_array:
+	if (WARN_ON_ONCE(nelems > new_max_intervals))
+		return -ENOMEM;
+
+	if (priv->array_next) {
+		if (max_intervals == new_max_intervals)
+			return 0;
+
+		if (nft_array_intervals_alloc(priv->array_next, new_max_intervals) < 0)
+			return -ENOMEM;
+	} else {
 		array = nft_array_alloc(new_max_intervals);
 		if (!array)
 			return -ENOMEM;
@@ -658,13 +718,6 @@ static int nft_array_may_resize(const struct nft_set *set)
 		priv->array_next = array;
 	}
 
-	if (nelems < priv->array_next->max_intervals)
-		return 0;
-
-	new_max_intervals = priv->array_next->max_intervals + NFT_ARRAY_EXTRA_SIZE;
-	if (nft_array_intervals_alloc(priv->array_next, new_max_intervals) < 0)
-		return -ENOMEM;
-
 	return 0;
 }
 
@@ -680,7 +733,7 @@ static int nft_rbtree_insert(const struct net *net, const struct nft_set *set,
 
 	nft_rbtree_maybe_reset_start_cookie(priv, tstamp);
 
-	if (nft_array_may_resize(set) < 0)
+	if (nft_array_may_resize(set, false) < 0)
 		return -ENOMEM;
 
 	do {
@@ -791,7 +844,7 @@ nft_rbtree_deactivate(const struct net *net, const struct nft_set *set,
 	    nft_rbtree_interval_null(set, this))
 		priv->start_rbe_cookie = 0;
 
-	if (nft_array_may_resize(set) < 0)
+	if (nft_array_may_resize(set, false) < 0)
 		return NULL;
 
 	while (parent != NULL) {
@@ -862,7 +915,7 @@ static void nft_rbtree_walk(const struct nft_ctx *ctx,
 
 	switch (iter->type) {
 	case NFT_ITER_UPDATE_CLONE:
-		if (nft_array_may_resize(set) < 0) {
+		if (nft_array_may_resize(set, true) < 0) {
 			iter->err = -ENOMEM;
 			break;
 		}
-- 
2.47.3

Re: [PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Chris Arges]

On 2026-03-17 18:07:21, Pablo Neira Ayuso wrote:
> Chris Arges reports high memory consumption with thousands of
> containers, this patch revisits the array allocation logic.
> 
> For anonymous sets, start by 16 slots (which takes 256 bytes on x86_64).
> Expand it by x2 until threshold of 512 slots is reached, over that
> threshold, expand it by x1.5.
> 
> For non-anonymous set, start by 1024 slots in the array (which takes 16
> Kbytes initially on x86_64). Expand it by x1.5.
> 
> Use set->ndeact to subtract deactivated elements when calculating the
> number of the slots in the array, otherwise the array size array gets
> increased artifically. Add special case shrink logic to deal with flush
> set too.
> 
> The shrink logic is skipped by anonymous sets.
> 
> Use check_add_overflow() to calculate the new array size.
> 
> Add a WARN_ON_ONCE check to make sure elements fit into the new array
> size.
> 
> 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>
> ---
> v4: use maybe_grow: goto tag instead of grow:
>     Add note in commit description: "The shrink logic is skipped by anonymous sets."
> 

I will be able to testing this more in depth early next week. Just to confirm,
this patch requires this to be applied first?
https://lore.kernel.org/netfilter-devel/20260307001124.2897063-1-pablo@netfilter.org/

--chris

Re: [PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Florian Westphal]

Chris Arges <carges@cloudflare.com> wrote:
> > 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>
> > ---
> > v4: use maybe_grow: goto tag instead of grow:
> >     Add note in commit description: "The shrink logic is skipped by anonymous sets."
> > 
> 
> I will be able to testing this more in depth early next week.

Thanks, I will hold off on this patch and will defer it to next week
then.

Re: [PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Pablo Neira Ayuso]

On Wed, Mar 18, 2026 at 10:46:56AM -0500, Chris Arges wrote:
> On 2026-03-17 18:07:21, Pablo Neira Ayuso wrote:
> > Chris Arges reports high memory consumption with thousands of
> > containers, this patch revisits the array allocation logic.
> > 
> > For anonymous sets, start by 16 slots (which takes 256 bytes on x86_64).
> > Expand it by x2 until threshold of 512 slots is reached, over that
> > threshold, expand it by x1.5.
> > 
> > For non-anonymous set, start by 1024 slots in the array (which takes 16
> > Kbytes initially on x86_64). Expand it by x1.5.
> > 
> > Use set->ndeact to subtract deactivated elements when calculating the
> > number of the slots in the array, otherwise the array size array gets
> > increased artifically. Add special case shrink logic to deal with flush
> > set too.
> > 
> > The shrink logic is skipped by anonymous sets.
> > 
> > Use check_add_overflow() to calculate the new array size.
> > 
> > Add a WARN_ON_ONCE check to make sure elements fit into the new array
> > size.
> > 
> > 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>
> > ---
> > v4: use maybe_grow: goto tag instead of grow:
> >     Add note in commit description: "The shrink logic is skipped by anonymous sets."
> > 
> 
> I will be able to testing this more in depth early next week. Just to confirm,
> this patch requires this to be applied first?
> https://lore.kernel.org/netfilter-devel/20260307001124.2897063-1-pablo@netfilter.org/

Yes, it requires that fix to be applied first.

Re: [PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Chris Arges]

On 2026-03-18 17:57:54, Pablo Neira Ayuso wrote:
> On Wed, Mar 18, 2026 at 10:46:56AM -0500, Chris Arges wrote:
> > On 2026-03-17 18:07:21, Pablo Neira Ayuso wrote:
> > > Chris Arges reports high memory consumption with thousands of
> > > containers, this patch revisits the array allocation logic.
> > > 
> > > For anonymous sets, start by 16 slots (which takes 256 bytes on x86_64).
> > > Expand it by x2 until threshold of 512 slots is reached, over that
> > > threshold, expand it by x1.5.
> > > 
> > > For non-anonymous set, start by 1024 slots in the array (which takes 16
> > > Kbytes initially on x86_64). Expand it by x1.5.
> > > 
> > > Use set->ndeact to subtract deactivated elements when calculating the
> > > number of the slots in the array, otherwise the array size array gets
> > > increased artifically. Add special case shrink logic to deal with flush
> > > set too.
> > > 
> > > The shrink logic is skipped by anonymous sets.
> > > 
> > > Use check_add_overflow() to calculate the new array size.
> > > 
> > > Add a WARN_ON_ONCE check to make sure elements fit into the new array
> > > size.
> > > 
> > > 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>
> > > ---
> > > v4: use maybe_grow: goto tag instead of grow:
> > >     Add note in commit description: "The shrink logic is skipped by anonymous sets."
> > > 
> > 
> > I will be able to testing this more in depth early next week. Just to confirm,
> > this patch requires this to be applied first?
> > https://lore.kernel.org/netfilter-devel/20260307001124.2897063-1-pablo@netfilter.org/
> 
> Yes, it requires that fix to be applied first.

Thanks, these two patches applied on 6.18 stable show slab unreclaimable memory
leveling out at 1.5GB for my local reproducer. I'll be deploying this to a
wider set of machines for more real-world testing this week.

So far seems good.
--chris

Re: [PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Chris Arges]

On 2026-03-23 12:29:30, Chris Arges wrote:
> On 2026-03-18 17:57:54, Pablo Neira Ayuso wrote:
> > On Wed, Mar 18, 2026 at 10:46:56AM -0500, Chris Arges wrote:
> > > On 2026-03-17 18:07:21, Pablo Neira Ayuso wrote:
> > > > Chris Arges reports high memory consumption with thousands of
> > > > containers, this patch revisits the array allocation logic.
> > > > 
> > > > For anonymous sets, start by 16 slots (which takes 256 bytes on x86_64).
> > > > Expand it by x2 until threshold of 512 slots is reached, over that
> > > > threshold, expand it by x1.5.
> > > > 
> > > > For non-anonymous set, start by 1024 slots in the array (which takes 16
> > > > Kbytes initially on x86_64). Expand it by x1.5.
> > > > 
> > > > Use set->ndeact to subtract deactivated elements when calculating the
> > > > number of the slots in the array, otherwise the array size array gets
> > > > increased artifically. Add special case shrink logic to deal with flush
> > > > set too.
> > > > 
> > > > The shrink logic is skipped by anonymous sets.
> > > > 
> > > > Use check_add_overflow() to calculate the new array size.
> > > > 
> > > > Add a WARN_ON_ONCE check to make sure elements fit into the new array
> > > > size.
> > > > 
> > > > 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>
> > > > ---
> > > > v4: use maybe_grow: goto tag instead of grow:
> > > >     Add note in commit description: "The shrink logic is skipped by anonymous sets."
> > > > 
> > > 
> > > I will be able to testing this more in depth early next week. Just to confirm,
> > > this patch requires this to be applied first?
> > > https://lore.kernel.org/netfilter-devel/20260307001124.2897063-1-pablo@netfilter.org/
> > 
> > Yes, it requires that fix to be applied first.
> 
> Thanks, these two patches applied on 6.18 stable show slab unreclaimable memory
> leveling out at 1.5GB for my local reproducer. I'll be deploying this to a
> wider set of machines for more real-world testing this week.
> 
> So far seems good.
> --chris

We have deployed this successfully and memory usage looks good in production.

Tested-by: Chris Arges <carges@cloudflare.com>

--chris

Re: [PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Chris Arges]

On 2026-03-25 19:42:54, Chris Arges wrote:
> On 2026-03-23 12:29:30, Chris Arges wrote:
> > On 2026-03-18 17:57:54, Pablo Neira Ayuso wrote:
> > > On Wed, Mar 18, 2026 at 10:46:56AM -0500, Chris Arges wrote:
> > > > On 2026-03-17 18:07:21, Pablo Neira Ayuso wrote:
> > > > > Chris Arges reports high memory consumption with thousands of
> > > > > containers, this patch revisits the array allocation logic.
> > > > > 
> > > > > For anonymous sets, start by 16 slots (which takes 256 bytes on x86_64).
> > > > > Expand it by x2 until threshold of 512 slots is reached, over that
> > > > > threshold, expand it by x1.5.
> > > > > 
> > > > > For non-anonymous set, start by 1024 slots in the array (which takes 16
> > > > > Kbytes initially on x86_64). Expand it by x1.5.
> > > > > 
> > > > > Use set->ndeact to subtract deactivated elements when calculating the
> > > > > number of the slots in the array, otherwise the array size array gets
> > > > > increased artifically. Add special case shrink logic to deal with flush
> > > > > set too.
> > > > > 
> > > > > The shrink logic is skipped by anonymous sets.
> > > > > 
> > > > > Use check_add_overflow() to calculate the new array size.
> > > > > 
> > > > > Add a WARN_ON_ONCE check to make sure elements fit into the new array
> > > > > size.
> > > > > 
> > > > > 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>
> > > > > ---
> > > > > v4: use maybe_grow: goto tag instead of grow:
> > > > >     Add note in commit description: "The shrink logic is skipped by anonymous sets."
> > > > > 
> > > > 
> > > > I will be able to testing this more in depth early next week. Just to confirm,
> > > > this patch requires this to be applied first?
> > > > https://lore.kernel.org/netfilter-devel/20260307001124.2897063-1-pablo@netfilter.org/
> > > 
> > > Yes, it requires that fix to be applied first.
> > 
> > Thanks, these two patches applied on 6.18 stable show slab unreclaimable memory
> > leveling out at 1.5GB for my local reproducer. I'll be deploying this to a
> > wider set of machines for more real-world testing this week.
> > 
> > So far seems good.
> > --chris
> 
> We have deployed this successfully and memory usage looks good in production.
> 
> Tested-by: Chris Arges <carges@cloudflare.com>
> 
> --chris

Oh I see it's queued up here:
https://patchwork.ozlabs.org/project/netfilter-devel/patch/20260325222615.637793-8-pablo@netfilter.org/
Thanks for fixing this!
--chris

Re: [PATCH nf,v4] netfilter: nft_set_rbtree: revisit array resize logic

[Pablo Neira Ayuso]

On Wed, Mar 25, 2026 at 07:44:36PM -0500, Chris Arges wrote:
> On 2026-03-25 19:42:54, Chris Arges wrote:
> > On 2026-03-23 12:29:30, Chris Arges wrote:
> > > On 2026-03-18 17:57:54, Pablo Neira Ayuso wrote:
> > > > On Wed, Mar 18, 2026 at 10:46:56AM -0500, Chris Arges wrote:
> > > > > On 2026-03-17 18:07:21, Pablo Neira Ayuso wrote:
> > > > > > Chris Arges reports high memory consumption with thousands of
> > > > > > containers, this patch revisits the array allocation logic.
> > > > > > 
> > > > > > For anonymous sets, start by 16 slots (which takes 256 bytes on x86_64).
> > > > > > Expand it by x2 until threshold of 512 slots is reached, over that
> > > > > > threshold, expand it by x1.5.
> > > > > > 
> > > > > > For non-anonymous set, start by 1024 slots in the array (which takes 16
> > > > > > Kbytes initially on x86_64). Expand it by x1.5.
> > > > > > 
> > > > > > Use set->ndeact to subtract deactivated elements when calculating the
> > > > > > number of the slots in the array, otherwise the array size array gets
> > > > > > increased artifically. Add special case shrink logic to deal with flush
> > > > > > set too.
> > > > > > 
> > > > > > The shrink logic is skipped by anonymous sets.
> > > > > > 
> > > > > > Use check_add_overflow() to calculate the new array size.
> > > > > > 
> > > > > > Add a WARN_ON_ONCE check to make sure elements fit into the new array
> > > > > > size.
> > > > > > 
> > > > > > 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>
> > > > > > ---
> > > > > > v4: use maybe_grow: goto tag instead of grow:
> > > > > >     Add note in commit description: "The shrink logic is skipped by anonymous sets."
> > > > > > 
> > > > > 
> > > > > I will be able to testing this more in depth early next week. Just to confirm,
> > > > > this patch requires this to be applied first?
> > > > > https://lore.kernel.org/netfilter-devel/20260307001124.2897063-1-pablo@netfilter.org/
> > > > 
> > > > Yes, it requires that fix to be applied first.
> > > 
> > > Thanks, these two patches applied on 6.18 stable show slab unreclaimable memory
> > > leveling out at 1.5GB for my local reproducer. I'll be deploying this to a
> > > wider set of machines for more real-world testing this week.
> > > 
> > > So far seems good.
> > > --chris
> > 
> > We have deployed this successfully and memory usage looks good in production.
> > 
> > Tested-by: Chris Arges <carges@cloudflare.com>
> > 
> > --chris
> 
> Oh I see it's queued up here:
> https://patchwork.ozlabs.org/project/netfilter-devel/patch/20260325222615.637793-8-pablo@netfilter.org/
> Thanks for fixing this!

Yes, I did not get in time to add your Tested-by: tag.

Thanks for testing in any case!