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

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

[Pablo Neira Ayuso]

Start by 8192 slots in the array and expand it by pow of 2 to simplify
growth and shrink logic.

Use set->ndeact to subtract deactivated elements when calculating the
number of the slots in the array.

Add shrink logic to deal with flush+add set, otherwise the array size
array gets increased artifically.

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>
---
Chris, I'm posting this patch, but I am not sure it fits into the
scenario you described.

 net/netfilter/nft_set_rbtree.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index bdcea649467f..b0a3503bbd81 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -616,14 +616,14 @@ static struct nft_array *nft_array_alloc(u32 max_intervals)
 	return array;
 }
 
-#define NFT_ARRAY_EXTRA_SIZE	10240
+#define NFT_ARRAY_INITIAL_SIZE	8192
 
 /* 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.
@@ -649,7 +649,7 @@ static int nft_array_may_resize(const struct nft_set *set)
 		if (priv->array)
 			new_max_intervals = priv->array->max_intervals;
 		else
-			new_max_intervals = NFT_ARRAY_EXTRA_SIZE;
+			new_max_intervals = NFT_ARRAY_INITIAL_SIZE;
 
 		array = nft_array_alloc(new_max_intervals);
 		if (!array)
@@ -658,10 +658,18 @@ static int nft_array_may_resize(const struct nft_set *set)
 		priv->array_next = array;
 	}
 
+	if (nelems >= NFT_ARRAY_INITIAL_SIZE && nelems < (priv->array_next->max_intervals >> 1)) {
+		new_max_intervals = priv->array_next->max_intervals >> 1;
+		if (nft_array_intervals_alloc(priv->array_next, new_max_intervals) < 0)
+			return -ENOMEM;
+
+		return 0;
+	}
+
 	if (nelems < priv->array_next->max_intervals)
 		return 0;
 
-	new_max_intervals = priv->array_next->max_intervals + NFT_ARRAY_EXTRA_SIZE;
+	new_max_intervals = priv->array_next->max_intervals << 1;
 	if (nft_array_intervals_alloc(priv->array_next, new_max_intervals) < 0)
 		return -ENOMEM;
 
-- 
2.47.3

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

[Chris Arges]

On 2026-03-12 02:14:23, Pablo Neira Ayuso wrote:
> Start by 8192 slots in the array and expand it by pow of 2 to simplify
> growth and shrink logic.
> 
> Use set->ndeact to subtract deactivated elements when calculating the
> number of the slots in the array.
> 
> Add shrink logic to deal with flush+add set, otherwise the array size
> array gets increased artifically.
> 
> 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>
> ---
> Chris, I'm posting this patch, but I am not sure it fits into the
> scenario you described.
>

Pablo,

Thank you, I was able to test this and here are my results:

* v6.18.13 (before nft_set_rbtree patches)
Slab unreclaimable memory increases to 1.4G then levels off.

* v6.18.17 (no patches)
Slab unreclaimable memory increases to 4.9G then levels off.

* v6.18.17 + this patch + nft_set_rbtree: allocate same array size on updates
Slab unreclaimable memory increases to 3.1G then levels off.

* v6.18.17 + this patch + nft_set_rbtree: allocate same array size on updates +
 NFT_ARRAY_INITIAL_SIZE 1024

Slab unreclaimable memory increases to 1.6G then levels off.

So looks like this patch is a huge improvement! One modification I was able to
test was setting NFT_ARRAY_INITIAL_SIZE to 1024. With that change I was getting
a memory profile similar to before this patch:
- 7e43e0a1141d netfilter: nft_set_rbtree: translate rbtree to array for binary search

--chris