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

Hi Florian,

On Thu, 6 Aug 2026, Florian Westphal wrote:

> 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.

Sigh. It's getting more and more complicated to maintain a fairly simple 
data structure.

What do you think which is better for the test (match) case (not 
add/del), performance-wise:

- seqcount and retry
- holes left [and INIT_CIDR() converted to a function to skip the holes
  and find the first entry for add/del]

Best regards,
Jozsef
 
> Assisted-by: Claude:claude-sonnet-5
> Fixes: 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")
> Signed-off-by: Florian Westphal <[email protected]>
> ---
>  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
> 
> 

-- 
E-mail : [email protected], [email protected], [email protected]
Address: Wigner Research Centre for Physics
         H-1525 Budapest 114, POB. 49, Hungary