netfilter: ipset: remove need to allocate memory on delete operations
Subsystems (2)
Florian Westphal
maintainerPATCH 1/1 netfilter: ipset: remove need to allocate memory on delete operations
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.
---
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(-)
net/netfilter/ipset/ip_set_hash_gen.h +43 -28
@@ -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));
Signature · 1 line
2.54.0
Hi Florian,
Quoted 31 lines · Florian Westphal
Allocating mem via
GFP_ATOMICon 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.
_addpath is unchanged: like the del path it acquiresset->lock, i.e. we are only writer.Fixes 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping")Signed-off-by Florian Westphal <[email protected]>---
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(-)net/netfilter/ipset/ip_set_hash_gen.h +0
-0
net/netfilter/ipset/ip_set_hash_gen.h struct htable { · line 107
Quoted 9 lines
net/netfilter/ipset/ip_set_hash_gen.h +3
-2@@ -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.
Quoted 108 lines
net/netfilter/ipset/ip_set_hash_gen.h +37
-24struct 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]); +
net/netfilter/ipset/ip_set_hash_gen.h mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d, · line 1412
Quoted 10 lines
net/netfilter/ipset/ip_set_hash_gen.h +3
-2+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
Signature · 3 lines
E-mail : [email protected], [email protected], [email protected] Address: Wigner Research Centre for Physics H-1525 Budapest 114, POB. 49, Hungary
Florian Westphal
maintainerQuoted 11 lines · Jozsef Kadlecsik
net/netfilter/ipset/ip_set_hash_gen.h struct htable { · line 107
Quoted 8 lines
/* Book-keeping of the prefixes added to the set */ struct
net_prefix{net/netfilter/ipset/ip_set_hash_gen.h +3
-2-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
Quoted 7 lines
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.
Quoted 1 line
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.
Quoted 3 lines
net/netfilter/ipset/ip_set_hash_gen.h mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n) · line 504
Quoted 3 lines
net/netfilter/ipset/ip_set_hash_gen.h +2
-0+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.
Hi Florian,
Quoted 4 lines · Florian Westphal
Quoted 1 line
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