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

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

[Florian Westphal]

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

Do in-place substitution:  When /cidr reaches 0 count (no more elements in
the range), move ranges stored 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.

Also update comments to mention the possible presence of ignored
0-count-0-cidr structures at the end and need for seqcount.

seqcount is used to restart.  This avoids bogus range misses.
Given:  [0]: /29 [1]: /24
cpu1 reads slot 0. then, right after, cpu2 removes /29. count drops to 0,
so it updates array to: [0], /24, [1], /0 (count 0).

cpu1 then skips /28: slot 0 was already visited, but slot 1 already replaced.

Note that mtype_add() doesn't check mtype_add_cidr() return value.
Doing this here is useless noise as this code is extensively rewritten
in the rhashtable replacement patch.

Assisted-by: Claude:claude-sonnet-5
Fixes: 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 v4: really retry even for match case
 v3: Fix double increment.
 v2:
  - detach from ipset rhashtable patchset, that needs more soak time
  - remove mtype_flush allocation and zero out like in mtype_del.
  - add seqcount retry even for match case to handle 'nomatch' entries
    that might have been skipped.

 net/netfilter/ipset/ip_set_hash_gen.h        | 168 +++++++++++++------
 net/netfilter/ipset/ip_set_hash_netiface.c   |   1 -
 net/netfilter/ipset/ip_set_hash_netportnet.c |   1 -
 3 files changed, 121 insertions(+), 49 deletions(-)

diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
index f00c82acd7f0..80ca523f304b 100644
--- a/net/netfilter/ipset/ip_set_hash_gen.h
+++ b/net/netfilter/ipset/ip_set_hash_gen.h
@@ -8,6 +8,7 @@
 #include <linux/rcupdate_wait.h>
 #include <linux/jhash.h>
 #include <linux/types.h>
+#include <linux/seqlock.h>
 #include <linux/netfilter/nfnetlink.h>
 #include <linux/netfilter/ipset/ip_set.h>
 
@@ -98,14 +99,34 @@ struct htable {
 #define IPSET_NET_COUNT		1
 #endif
 
-/* Book-keeping of the prefixes added to the set */
+/**
+ * struct net_prefix - Representation of a network prefix.
+ * @cidr: The CIDR prefix length.
+ * @count: Number of occurrences.
+ */
 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 - A collection of network prefixes.
+ * @rcu: RCU head
+ * @seq: Sequence counter guarding in-place reordering of @nets
+ * @len: Number of entries in the array.
+ * @nets: Array of net_prefix structures (sorted by CIDR descending).
+ *
+ * @nets entries are updated in place under @set's lock. A single entry's
+ * cidr/count pair is always updated atomically via READ_ONCE()/WRITE_ONCE(),
+ * but removing an entry also shifts every following entry down by one slot.
+ * Lockless readers that scan the whole array (i.e. more than a single
+ * indexed slot) must use @seq to detect and retry across such a shift.
+ */
 struct net_prefixes {
 	struct rcu_head rcu;
+	seqcount_spinlock_t seq;
 	u8 len;
 	struct net_prefix nets[] __counted_by(len);
 };
@@ -143,8 +164,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 */
@@ -318,27 +342,43 @@ struct mtype_resize_ad {
 };
 
 #ifdef IP_SET_HASH_WITH_NETS
-/* Network cidr size book keeping when the hash stores different
- * sized networks. cidr == real cidr + 1 to support /0.
+/**
+ * mtype_add_cidr - Add a CIDR entry to hash table bookkeeping
+ * @set: Pointer to the ip_set
+ * @h: Pointer to the htype
+ * @cidr: The CIDR prefix length
+ * @n: The index of the net_prefix array to add @cidr to
+ *
+ * Performs an update if @cidr is found, otherwise performs COW-style
+ * allocation and replacement via RCU.
+ *
+ * Return: 0 on success, negative error code on failure.
  */
 static int
 mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 {
-	struct net_prefixes *nets, *tmp;
 	int i, j, found, len = 0, ret = 0;
+	struct net_prefixes *nets, *tmp;
+	struct net_prefix np;
 
 	spin_lock_bh(&set->lock);
 	nets = __ipset_dereference(h->rnets[n]);
 	/* Add in increasing prefix order, so larger cidr first */
 	for (i = 0, found = -1; i < nets->len; i++) {
-		if (nets->nets[i].count)
+		np = READ_ONCE(nets->nets[i]);
+		if (np.count)
 			len++;
 		if (found != -1) {
 			continue;
-		} else if (nets->nets[i].cidr < cidr) {
+		} else if (np.cidr < cidr) {
 			found = i;
-		} else if (nets->nets[i].cidr == cidr) {
-			nets->nets[i].count++;
+		} else if (np.cidr == cidr) {
+			if (np.count < CIDR_MAX_COUNT) {
+				np.count++;
+				WRITE_ONCE(nets->nets[i], np);
+			} else {
+				ret = -EOVERFLOW;
+			}
 			goto unlock;
 		}
 	}
@@ -350,6 +390,7 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 	}
 
 	tmp->len = len;
+	seqcount_spinlock_init(&tmp->seq, &set->lock);
 	for (i = 0, j = 0; i < nets->len; i++) {
 		if (i == found) {
 			tmp->nets[j].cidr = cidr;
@@ -371,42 +412,60 @@ mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n)
 	return ret;
 }
 
+/**
+ * mtype_del_cidr - Remove CIDR entry and maintain array integrity.
+ * @set: Pointer to the ip_set.
+ * @h: Pointer to the htype.
+ * @cidr: The CIDR prefix length.
+ * @n: The index of the net_prefix array to remove @cidr from
+ *
+ * If CIDR entry count falls to 0, this function performs a "shift-left"
+ * operation on all following elements. This ensures that the array remains
+ * contiguous and maintains its descending order by CIDR. The vacated slot
+ * at the end of the array is zeroed out (cidr=0, count=0).
+ */
 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;
+	write_seqcount_begin(&nets->seq);
 	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){});
+	write_seqcount_end(&nets->seq);
 unlock:
 	spin_unlock_bh(&set->lock);
 }
@@ -451,7 +510,7 @@ mtype_flush(struct ip_set *set)
 {
 	struct htype *h = set->data;
 #ifdef IP_SET_HASH_WITH_NETS
-	struct net_prefixes *nets, *tmp;
+	struct net_prefixes *nets;
 #endif
 	struct htable *t;
 	struct hbucket *n;
@@ -477,17 +536,15 @@ mtype_flush(struct ip_set *set)
 	}
 #ifdef IP_SET_HASH_WITH_NETS
 	for (i = 0; i < IPSET_NET_COUNT; i++) {
-		nets = ipset_dereference_nfnl(h->rnets[i]);
-		tmp = kzalloc_obj(*tmp, GFP_ATOMIC);
-		if (!tmp) {
-			u8 j;
+		u8 j;
 
-			for (j = 0; j < nets->len; j++)
-				nets->nets[j].count = 0;
-		} else {
-			rcu_assign_pointer(h->rnets[i], tmp);
-			kfree_rcu(nets, rcu);
-		}
+		spin_lock_bh(&set->lock);
+		nets = ipset_dereference_nfnl(h->rnets[i]);
+		write_seqcount_begin(&nets->seq);
+		for (j = 0; j < nets->len; j++)
+			WRITE_ONCE(nets->nets[j], (struct net_prefix){});
+		write_seqcount_end(&nets->seq);
+		spin_unlock_bh(&set->lock);
 	}
 #endif
 }
@@ -1253,31 +1310,41 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
 #if IPSET_NET_COUNT == 2
 	struct net_prefixes *nets1;
 	struct mtype_elem orig = *d;
+	unsigned int seq1;
 	int ret, i, j, k;
 #else
 	int ret, i, j;
 #endif
-	u32 key, multi = 0;
+	unsigned int seq0;
+	u32 key, multi;
 	u8 pos;
 
 	pr_debug("test by nets\n");
 	rcu_read_lock_bh();
+retry:
+	multi = 0;
 	nets0 = rcu_dereference_bh(h->rnets[0]);
+	seq0 = read_seqcount_begin(&nets0->seq);
 #if IPSET_NET_COUNT == 2
 	nets1 = rcu_dereference_bh(h->rnets[1]);
+	seq1 = read_seqcount_begin(&nets1->seq);
 #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));
@@ -1304,6 +1371,12 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
 	}
 	ret = 0;
 unlock:
+	if (read_seqcount_retry(&nets0->seq, seq0))
+		goto retry;
+#if IPSET_NET_COUNT == 2
+	if (read_seqcount_retry(&nets1->seq, seq1))
+		goto retry;
+#endif
 	rcu_read_unlock_bh();
 	return ret;
 }
@@ -1707,6 +1780,7 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set,
 				kfree(rcu_dereference_raw(h->rnets[--i]));
 			goto free_hregion;
 		}
+		seqcount_spinlock_init(&nets->seq, &set->lock);
 		RCU_INIT_POINTER(h->rnets[i], nets);
 	}
 #endif
diff --git a/net/netfilter/ipset/ip_set_hash_netiface.c b/net/netfilter/ipset/ip_set_hash_netiface.c
index b44b95f766b7..b602cc43565d 100644
--- a/net/netfilter/ipset/ip_set_hash_netiface.c
+++ b/net/netfilter/ipset/ip_set_hash_netiface.c
@@ -38,7 +38,6 @@ MODULE_ALIAS("ip_set_hash:net,iface");
 #define HTYPE		hash_netiface
 #define IP_SET_HASH_WITH_NETS
 #define IP_SET_HASH_WITH_MULTI
-#define IP_SET_HASH_WITH_NET0
 
 #define STRSCPY(a, b)	strscpy(a, b, IFNAMSIZ)
 
diff --git a/net/netfilter/ipset/ip_set_hash_netportnet.c b/net/netfilter/ipset/ip_set_hash_netportnet.c
index 6291532be7a5..61af1ce27127 100644
--- a/net/netfilter/ipset/ip_set_hash_netportnet.c
+++ b/net/netfilter/ipset/ip_set_hash_netportnet.c
@@ -36,7 +36,6 @@ MODULE_ALIAS("ip_set_hash:net,port,net");
 #define IP_SET_HASH_WITH_PROTO
 #define IP_SET_HASH_WITH_NETS
 #define IPSET_NET_COUNT 2
-#define IP_SET_HASH_WITH_NET0
 
 /* IPv4 variant */
 
-- 
2.54.0

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

[Florian Westphal]

Florian Westphal <fw@strlen.de> wrote:
> +		write_seqcount_end(&nets->seq);
> +		spin_unlock_bh(&set->lock);
>  	}
>  #endif
>  }
> @@ -1253,31 +1310,41 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
>  #if IPSET_NET_COUNT == 2
>  	struct net_prefixes *nets1;
>  	struct mtype_elem orig = *d;
> +	unsigned int seq1;
>  	int ret, i, j, k;
>  #else
>  	int ret, i, j;
>  #endif
> -	u32 key, multi = 0;
> +	unsigned int seq0;
> +	u32 key, multi;
>  	u8 pos;
>  
>  	pr_debug("test by nets\n");
>  	rcu_read_lock_bh();
> +retry:
> +	multi = 0;
>  	nets0 = rcu_dereference_bh(h->rnets[0]);
> +	seq0 = read_seqcount_begin(&nets0->seq);
[..]
>  unlock:
> +	if (read_seqcount_retry(&nets0->seq, seq0))
> +		goto retry;

Sashiko now says this retry loop causes double-count
on match, yet v3 said not doing this causes possible
miss of a nomatch entry.

I think missing nomatch entry is worse and doublecount
is ok.

The restart is rare enough anyway because write_seqcount_begin()
is only called when set is flushed or a element deletion brings
a cidr count value down to 0.

Another option is to prellocate all possible CIDRs but I'd
like to avoid it, this means checking up to 128 possible CIDRs
in ipv6 case.

Pre-sampling all values into local on-stack array is a non-starter
too due to stack cost.

What one COULD do is to use pcpu stash area for this, needs
local bh / local_lock.

But I think its a bit "too much" for this problem.

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

[Jozsef Kadlecsik]

Hi Florian,

On Fri, 7 Aug 2026, Florian Westphal wrote:

> Florian Westphal <fw@strlen.de> wrote:
> > +		write_seqcount_end(&nets->seq);
> > +		spin_unlock_bh(&set->lock);
> >  	}
> >  #endif
> >  }
> > @@ -1253,31 +1310,41 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
> >  #if IPSET_NET_COUNT == 2
> >  	struct net_prefixes *nets1;
> >  	struct mtype_elem orig = *d;
> > +	unsigned int seq1;
> >  	int ret, i, j, k;
> >  #else
> >  	int ret, i, j;
> >  #endif
> > -	u32 key, multi = 0;
> > +	unsigned int seq0;
> > +	u32 key, multi;
> >  	u8 pos;
> >  
> >  	pr_debug("test by nets\n");
> >  	rcu_read_lock_bh();
> > +retry:
> > +	multi = 0;
> >  	nets0 = rcu_dereference_bh(h->rnets[0]);
> > +	seq0 = read_seqcount_begin(&nets0->seq);
> [..]
> >  unlock:
> > +	if (read_seqcount_retry(&nets0->seq, seq0))
> > +		goto retry;
> 
> Sashiko now says this retry loop causes double-count on match, yet v3 
> said not doing this causes possible miss of a nomatch entry.
> 
> I think missing nomatch entry is worse and doublecount is ok.
> 
> The restart is rare enough anyway because write_seqcount_begin() is only 
> called when set is flushed or a element deletion brings a cidr count 
> value down to 0.

Yes, exactly. [Somehow flush seems to "ask" to create a new empty set, 
switch to it and release the old one after, but then again, we might be 
out of memory to allocate.]
 
> Another option is to prellocate all possible CIDRs but I'd like to avoid 
> it, this means checking up to 128 possible CIDRs in ipv6 case.
> 
> Pre-sampling all values into local on-stack array is a non-starter too 
> due to stack cost.
> 
> What one COULD do is to use pcpu stash area for this, needs local bh / 
> local_lock.

I was thinking on pcpu as well: keep preallocated max size "struct 
net_prefixes" per cpu, signal end of lookup by the zero count value of 
"struct net_prefix". But then we'd just keep a lot of stash areas. But the 
arrays are not huge - I refrained to use linked lists both because struct 
net_prefix is small and also to count on the prefetching of the array 
elements.

> But I think its a bit "too much" for this problem.

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