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

Pablo Neira Ayuso
2026-03-12T01:14:33Z

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