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

[Florian Westphal <fw@strlen.de>]

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 seen and slot 1 already replaced.

Assisted-by: Claude:claude-sonnet-5
Fixes: 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")
Signed-off-by: Florian Westphal <fw@strlen.de>
---
 Was not part of earlier RFC series.

 net/netfilter/ipset/ip_set_hash_gen.h        | 149 ++++++++++++++-----
 net/netfilter/ipset/ip_set_hash_netiface.c   |   1 -
 net/netfilter/ipset/ip_set_hash_netportnet.c |   1 -
 3 files changed, 113 insertions(+), 38 deletions(-)

diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
index f00c82acd7f0..8c79938410a0 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);
 }
@@ -1253,31 +1312,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));
@@ -1302,6 +1371,13 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
 		}
 #endif
 	}
+
+	if (read_seqcount_retry(&nets0->seq, seq0))
+		goto retry;
+#if IPSET_NET_COUNT == 2
+	if (read_seqcount_retry(&nets1->seq, seq1))
+		goto retry;
+#endif
 	ret = 0;
 unlock:
 	rcu_read_unlock_bh();
@@ -1707,6 +1783,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