netfilter: ipset: remove need to allocate memory on delete operations operations
Subsystems (2)
Florian Westphal
maintainerPATCH v4 1/1 netfilter: ipset: remove need to allocate memory on delete operations operations
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.
---
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(-)
net/netfilter/ipset/ip_set_hash_gen.h +121 -47
@@ -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
net/netfilter/ipset/ip_set_hash_netiface.c +0 -1
@@ -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)
net/netfilter/ipset/ip_set_hash_netportnet.c +0 -1
@@ -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 */
Signature · 1 line
2.54.0
Florian Westphal
maintainerQuoted 25 lines · Florian Westphal
net/netfilter/ipset/ip_set_hash_gen.h +8
-1+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);
[..]
Review
Quoted 3 lines
unlock:
(quoted diff) +2
-0+ 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.
Hi Florian,
Quoted 34 lines · Florian Westphal
Quoted 25 lines · Florian Westphal
net/netfilter/ipset/ip_set_hash_gen.h +8
-1+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);[..]
Review
Quoted 3 lines
unlock:
(quoted diff) +2
-0+ 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.
Quoted 5 lines
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.]
Quoted 8 lines
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.
Quoted 1 line
But I think its a bit "too much" for this problem.
Best regards,
Jozsef
Signature · 3 lines
E-mail : [email protected], [email protected], [email protected] Address: Wigner Research Centre for Physics H-1525 Budapest 114, POB. 49, Hungary