[PATCH nf] netfilter: ipset: remove need to allocate memory on delete operations

[PATCH nf] netfilter: ipset: remove need to allocate memory on delete operations

[Florian Westphal]

Allocating mem via GFP_ATOMIC on delete is problematic, delete operations
should always succedd.

Do in-place substitution:  When /cidr reaches 0 count (no more elements
in the range), move ranges stores later in the array forward and keep
the count 0 ones at the end.

INIT_CIDR() can then check count == 0 without a need to search
next element in the array.

To avoid problems on weakly ordered architectures, pack the structure
so it is only 32bit wide, then use READ/WRITE_ONCE to store both cidr
and count atomically.

_add path is unchanged: like the del path it acquires set->lock, i.e.
we are only writer.

Fixes: 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 Won't apply, this is supposed to go on top of the pending
 nf PR.  In case that PR needs a v2, this could be squashed.

 net/netfilter/ipset/ip_set_hash_gen.h | 71 ++++++++++++++++-----------
 1 file changed, 43 insertions(+), 28 deletions(-)

diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
index 784e6d4a00ea..b2089ff6f1dc 100644
--- a/net/netfilter/ipset/ip_set_hash_gen.h
+++ b/net/netfilter/ipset/ip_set_hash_gen.h
@@ -101,9 +101,10 @@ struct htable {
 
 /* Book-keeping of the prefixes added to the set */
 struct net_prefix {
-	u8 cidr;			/* the cidr value */
-	u32 count;			/* number of elements of this cidr */
+	u32 cidr:8;
+	u32 count:24;
 };
+#define CIDR_MAX_COUNT ((1 << 24) - 1)
 
 struct net_prefixes {
 	struct rcu_head rcu;
@@ -144,8 +145,11 @@ htable_size(u8 hbits)
 #endif
 
 #define INIT_CIDR(n, host_mask) ({				\
-	const struct net_prefixes *__n = rcu_dereference(n);		\
-	DCIDR_PUT((__n)->len ? (__n)->nets[0].cidr : host_mask);\
+	const struct net_prefixes *__n = rcu_dereference(n);	\
+	struct net_prefix __p =					\
+		__n->len ? READ_ONCE(__n->nets[0])		\
+			 : (struct net_prefix){};		\
+	DCIDR_PUT(__p.count ? __p.cidr : host_mask);		\
 })
 
 #endif /* IP_SET_HASH_WITH_NETS */
@@ -436,7 +440,10 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 		} else if (nets->nets[i].cidr < cidr) {
 			found = i;
 		} else if (nets->nets[i].cidr == cidr) {
-			nets->nets[i].count++;
+			if (nets->nets[i].count < CIDR_MAX_COUNT)
+				nets->nets[i].count++;
+			else
+				ret = -EOVERFLOW;
 			goto unlock;
 		}
 	}
@@ -472,39 +479,43 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 static void
 mtype_del_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 {
-	struct net_prefixes *nets, *tmp;
-	u8 i, j, len = 0;
+	struct net_prefixes *nets;
+	struct net_prefix np;
 	int found;
+	u8 i, j;
+
+	BUILD_BUG_ON(sizeof(struct net_prefix) != sizeof(u32));
 
 	spin_lock_bh(&set->lock);
 	nets = __ipset_dereference(h->rnets[n]);
 	for (i = 0, found = -1; i < nets->len; i++) {
-		if (nets->nets[i].count)
-			len++;
-		if (nets->nets[i].cidr == cidr)
+		np = READ_ONCE(nets->nets[i]);
+		if (np.count && np.cidr == cidr) {
+			np.count--;
 			found = i;
+			break;
+		}
 	}
 	if (unlikely(found == -1))
 		goto unlock;
 
-	nets->nets[found].count--;
-	if (nets->nets[found].count)
-		goto unlock;
-	len--;
-	tmp = kzalloc_flex(*tmp, nets, len, GFP_ATOMIC);
-	if (!tmp)
-		/* Leave a hole */
+	if (np.count) {
+		WRITE_ONCE(nets->nets[found], np);
 		goto unlock;
+	}
 
-	tmp->len = len;
 	for (i = 0, j = 0; i < nets->len; i++) {
-		if (!nets->nets[i].count || i == found)
+		if (i == found)
 			continue;
-		tmp->nets[j].cidr = nets->nets[i].cidr;
-		tmp->nets[j++].count = nets->nets[i].count;
+
+		np = READ_ONCE(nets->nets[i]);
+		if (i != j)
+			WRITE_ONCE(nets->nets[j], np);
+		j++;
 	}
-	rcu_assign_pointer(h->rnets[n], tmp);
-	kfree_rcu(nets, rcu);
+
+	while (j < nets->len)
+		WRITE_ONCE(nets->nets[j++], (struct net_prefix){});
 unlock:
 	spin_unlock_bh(&set->lock);
 }
@@ -1381,17 +1392,21 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
 	nets1 = rcu_dereference_bh(h->rnets[1]);
 #endif
 	for (j = 0; j < nets0->len && !multi; j++) {
-		if (!nets0->nets[j].count)
+		struct net_prefix p0 = READ_ONCE(nets0->nets[j]);
+
+		if (!p0.count)
 			continue;
 #if IPSET_NET_COUNT == 2
 		mtype_data_reset_elem(d, &orig);
-		mtype_data_netmask(d, nets0->nets[j].cidr, false);
+		mtype_data_netmask(d, p0.cidr, false);
 		for (k = 0; k < nets1->len && !multi; k++) {
-			if (!nets1->nets[k].count)
+			struct net_prefix p1 = READ_ONCE(nets1->nets[k]);
+
+			if (!p1.count)
 				continue;
-			mtype_data_netmask(d, nets1->nets[k].cidr, true);
+			mtype_data_netmask(d, p1.cidr, true);
 #else
-		mtype_data_netmask(d, nets0->nets[j].cidr);
+		mtype_data_netmask(d, p0.cidr);
 #endif
 		key = HKEY(d, h->initval, t->htable_bits);
 		n = rcu_dereference_bh(hbucket(t, key));
-- 
2.54.0

Re: [PATCH nf] netfilter: ipset: remove need to allocate memory on delete operations

[Jozsef Kadlecsik]

Hi Florian,

On Tue, 4 Aug 2026, Florian Westphal wrote:

> Allocating mem via GFP_ATOMIC on delete is problematic, delete operations
> should always succedd.
> 
> Do in-place substitution:  When /cidr reaches 0 count (no more elements
> in the range), move ranges stores later in the array forward and keep
> the count 0 ones at the end.
> 
> INIT_CIDR() can then check count == 0 without a need to search
> next element in the array.
> 
> To avoid problems on weakly ordered architectures, pack the structure
> so it is only 32bit wide, then use READ/WRITE_ONCE to store both cidr
> and count atomically.
> 
> _add path is unchanged: like the del path it acquires set->lock, i.e.
> we are only writer.
> 
> Fixes: 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  Won't apply, this is supposed to go on top of the pending
>  nf PR.  In case that PR needs a v2, this could be squashed.
> 
>  net/netfilter/ipset/ip_set_hash_gen.h | 71 ++++++++++++++++-----------
>  1 file changed, 43 insertions(+), 28 deletions(-)
> 
> diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
> index 784e6d4a00ea..b2089ff6f1dc 100644
> --- a/net/netfilter/ipset/ip_set_hash_gen.h
> +++ b/net/netfilter/ipset/ip_set_hash_gen.h
> @@ -101,9 +101,10 @@ struct htable {
>  
>  /* Book-keeping of the prefixes added to the set */
>  struct net_prefix {
> -	u8 cidr;			/* the cidr value */
> -	u32 count;			/* number of elements of this cidr */
> +	u32 cidr:8;
> +	u32 count:24;
>  };
> +#define CIDR_MAX_COUNT ((1 << 24) - 1)

Could it be changed to

struct net_prefix {
     u64 cidr:8;
     u64 count:24;
};
#define CIDR_MAX_COUNT ((1 << 56) - 1)

(and the other required changes below)?

2**24 is a lot but still a reachable limit.
 
>  struct net_prefixes {
>  	struct rcu_head rcu;
> @@ -144,8 +145,11 @@ htable_size(u8 hbits)
>  #endif
>  
>  #define INIT_CIDR(n, host_mask) ({				\
> -	const struct net_prefixes *__n = rcu_dereference(n);		\
> -	DCIDR_PUT((__n)->len ? (__n)->nets[0].cidr : host_mask);\
> +	const struct net_prefixes *__n = rcu_dereference(n);	\
> +	struct net_prefix __p =					\
> +		__n->len ? READ_ONCE(__n->nets[0])		\
> +			 : (struct net_prefix){};		\
> +	DCIDR_PUT(__p.count ? __p.cidr : host_mask);		\
>  })
>  
>  #endif /* IP_SET_HASH_WITH_NETS */
> @@ -436,7 +440,10 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
>  		} else if (nets->nets[i].cidr < cidr) {
>  			found = i;
>  		} else if (nets->nets[i].cidr == cidr) {
> -			nets->nets[i].count++;
> +			if (nets->nets[i].count < CIDR_MAX_COUNT)
> +				nets->nets[i].count++;
> +			else
> +				ret = -EOVERFLOW;
>  			goto unlock;
>  		}
>  	}
> @@ -472,39 +479,43 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
>  static void
>  mtype_del_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
>  {
> -	struct net_prefixes *nets, *tmp;
> -	u8 i, j, len = 0;
> +	struct net_prefixes *nets;
> +	struct net_prefix np;
>  	int found;
> +	u8 i, j;
> +
> +	BUILD_BUG_ON(sizeof(struct net_prefix) != sizeof(u32));
>  
>  	spin_lock_bh(&set->lock);
>  	nets = __ipset_dereference(h->rnets[n]);
>  	for (i = 0, found = -1; i < nets->len; i++) {
> -		if (nets->nets[i].count)
> -			len++;
> -		if (nets->nets[i].cidr == cidr)
> +		np = READ_ONCE(nets->nets[i]);
> +		if (np.count && np.cidr == cidr) {
> +			np.count--;
>  			found = i;
> +			break;
> +		}
>  	}
>  	if (unlikely(found == -1))
>  		goto unlock;
>  
> -	nets->nets[found].count--;
> -	if (nets->nets[found].count)
> -		goto unlock;
> -	len--;
> -	tmp = kzalloc_flex(*tmp, nets, len, GFP_ATOMIC);
> -	if (!tmp)
> -		/* Leave a hole */
> +	if (np.count) {
> +		WRITE_ONCE(nets->nets[found], np);
>  		goto unlock;
> +	}
>  
> -	tmp->len = len;
>  	for (i = 0, j = 0; i < nets->len; i++) {
> -		if (!nets->nets[i].count || i == found)
> +		if (i == found)
>  			continue;
> -		tmp->nets[j].cidr = nets->nets[i].cidr;
> -		tmp->nets[j++].count = nets->nets[i].count;
> +
> +		np = READ_ONCE(nets->nets[i]);
> +		if (i != j)
> +			WRITE_ONCE(nets->nets[j], np);
> +		j++;
>  	}
> -	rcu_assign_pointer(h->rnets[n], tmp);
> -	kfree_rcu(nets, rcu);
> +
> +	while (j < nets->len)
> +		WRITE_ONCE(nets->nets[j++], (struct net_prefix){});
>  unlock:
>  	spin_unlock_bh(&set->lock);
>  }
> @@ -1381,17 +1392,21 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
>  	nets1 = rcu_dereference_bh(h->rnets[1]);
>  #endif
>  	for (j = 0; j < nets0->len && !multi; j++) {
> -		if (!nets0->nets[j].count)
> +		struct net_prefix p0 = READ_ONCE(nets0->nets[j]);
> +
> +		if (!p0.count)
>  			continue;
>  #if IPSET_NET_COUNT == 2
>  		mtype_data_reset_elem(d, &orig);
> -		mtype_data_netmask(d, nets0->nets[j].cidr, false);
> +		mtype_data_netmask(d, p0.cidr, false);
>  		for (k = 0; k < nets1->len && !multi; k++) {
> -			if (!nets1->nets[k].count)
> +			struct net_prefix p1 = READ_ONCE(nets1->nets[k]);
> +
> +			if (!p1.count)
>  				continue;
> -			mtype_data_netmask(d, nets1->nets[k].cidr, true);
> +			mtype_data_netmask(d, p1.cidr, true);
>  #else
> -		mtype_data_netmask(d, nets0->nets[j].cidr);
> +		mtype_data_netmask(d, p0.cidr);
>  #endif
>  		key = HKEY(d, h->initval, t->htable_bits);
>  		n = rcu_dereference_bh(hbucket(t, key));
> -- 

Best regards,
Jozsef
-- 
E-mail : kadlec@netfilter.org, kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.hu
Address: Wigner Research Centre for Physics
         H-1525 Budapest 114, POB. 49, Hungary

Re: [PATCH nf] netfilter: ipset: remove need to allocate memory on delete operations

[Florian Westphal]

Jozsef Kadlecsik <kadlec@netfilter.org> wrote:
> >  /* Book-keeping of the prefixes added to the set */
> >  struct net_prefix {
> > -	u8 cidr;			/* the cidr value */
> > -	u32 count;			/* number of elements of this cidr */
> > +	u32 cidr:8;
> > +	u32 count:24;
> >  };
> > +#define CIDR_MAX_COUNT ((1 << 24) - 1)
> 
> Could it be changed to
> 
> struct net_prefix {
>      u64 cidr:8;
>      u64 count:24;
> };
> #define CIDR_MAX_COUNT ((1 << 56) - 1)
> 
> (and the other required changes below)?

Only for 64bit builds, because WRITE_ONCE() is not atomic on 32bit.
If we do it for 32 bit builds, all read side paths would need to
switch to write seqcount use (including the normal case, i.e.
nets[i]->count++ / count.  ATM only the "it became 0 and has
to be moved) uses  the sequence write lock, so read side never
retries for typical updates.

> 2**24 is a lot but still a reachable limit.

Hmm. 16m entries...  I guess its possible for very small prefix
lengths?  We could use BITS_PER_LONG == 64 but it gets more ugly then.

> > +	if (np.count) {
> > +		WRITE_ONCE(nets->nets[found], np);
> >  		goto unlock;

This should be the typical case, which doesn't change the
write seq side, hence no retry on reader side.

This would have to be changed if we no longer rely
on READ/WRITE_ONCE.

Re: [PATCH nf] netfilter: ipset: remove need to allocate memory on delete operations

[Jozsef Kadlecsik]

Hi Florian,

On Sun, 9 Aug 2026, Florian Westphal wrote:

>> 2**24 is a lot but still a reachable limit.
>
> Hmm. 16m entries...  I guess its possible for very small prefix
> lengths?  We could use BITS_PER_LONG == 64 but it gets more ugly then.

I was thinking on IPv6 where it's more possible. But hash:ip has no such 
limitation with same-size prefixes so there are other solutions to store 
large number of same-size prefixes.

Best regards,
Jozsef