* [PATCH nf 0/7] netfilter: switch ipset to rhashtable
@ 2026-08-06 10:19 Florian Westphal
2026-08-06 10:19 ` [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations Florian Westphal
` (7 more replies)
0 siblings, 8 replies; 11+ messages in thread
From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw)
To: netfilter-devel; +Cc: Jozsef Kadlecsik, Florian Westphal
1) Replace memory allocation in ipset delete operations with in-place
substitution. Move empty CIDR ranges to the end of the array.
This addresses LLM findings of a patch from the rhashtable preparation
series.
2) Fix list_type ext_size memory accounting on set flush. As-is,
flush sets the value to 0, but call_rcu() destructor can subtract again.
Addresses drive-by LLM report.
3) Add rhashtable boilerplate stubs to netfilter ipset. Implement rhashtable
initialization and destruction routines.
4) Add rhltable boilerplate stubs to netfilter ipset. Prepare transitioning
certain hash sets from rhashtable to rhltable. Was not part of RFC,
needed for the 'net,iface.t' set type.
5) Replace ipset hash tables with rhashtable.
This change will splat on debug kernels, fix is queued as
'rhashtable: fix false-positive lockdep splat on rhltable destruction'
in herbert/crypto-2.6.git.
6) Restore forceadd support to ipset rhashtable via random element
eviction.
7) Include dynamic CIDR storage memory size in userspace reports.
Another LLM finding during review of initial preparation patches.
Florian Westphal (7):
netfilter: ipset: remove need to allocate memory on delete operations
netfilter: ipset: let destroy callbacks adjust ext mem size
netfilter: ipset: add rhashtable boilerplate stubs
netfilter: ipset: add rhltable boilerplate stubs
netfilter: ipset: replace internal hash table with rhashtable
netfilter: ipset: re-add forceadd support for rhashtable
netfilter: ipset: also report mem size for cidr storage to userspace
net/netfilter/ipset/ip_set_bitmap_gen.h | 2 +-
net/netfilter/ipset/ip_set_hash_gen.h | 1716 ++++++++----------
net/netfilter/ipset/ip_set_hash_netiface.c | 25 +-
net/netfilter/ipset/ip_set_hash_netportnet.c | 1 -
net/netfilter/ipset/ip_set_list_set.c | 3 +-
5 files changed, 734 insertions(+), 1013 deletions(-)
--
2.54.0
^ permalink raw reply [flat|nested] 11+ messages in thread* [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal @ 2026-08-06 10:19 ` Florian Westphal 2026-08-09 12:56 ` Jozsef Kadlecsik 2026-08-06 10:19 ` [PATCH nf 2/7] netfilter: ipset: let destroy callbacks adjust ext mem size Florian Westphal ` (6 subsequent siblings) 7 siblings, 1 reply; 11+ messages in thread From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw) To: netfilter-devel; +Cc: Jozsef Kadlecsik, 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 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 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations 2026-08-06 10:19 ` [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations Florian Westphal @ 2026-08-09 12:56 ` Jozsef Kadlecsik 2026-08-09 14:14 ` Florian Westphal 0 siblings, 1 reply; 11+ messages in thread From: Jozsef Kadlecsik @ 2026-08-09 12:56 UTC (permalink / raw) To: Florian Westphal; +Cc: netfilter-devel 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 <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 > > -- 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations 2026-08-09 12:56 ` Jozsef Kadlecsik @ 2026-08-09 14:14 ` Florian Westphal 0 siblings, 0 replies; 11+ messages in thread From: Florian Westphal @ 2026-08-09 14:14 UTC (permalink / raw) To: Jozsef Kadlecsik; +Cc: netfilter-devel Jozsef Kadlecsik <kadlec@netfilter.org> wrote: > Sigh. It's getting more and more complicated to maintain a fairly simple > data structure. Yup. Would be very simple for SMP=n :-) > 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] Depends on how likely a constant pingpong between 1 / 0 count is. Given data (packet) path can't insert a new netmask, I would guess its very very unlikely, so the seqcount / retry loop is not used at all. ^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH nf 2/7] netfilter: ipset: let destroy callbacks adjust ext mem size 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal 2026-08-06 10:19 ` [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations Florian Westphal @ 2026-08-06 10:19 ` Florian Westphal 2026-08-06 10:19 ` [PATCH nf 3/7] netfilter: ipset: add rhashtable boilerplate stubs Florian Westphal ` (5 subsequent siblings) 7 siblings, 0 replies; 11+ messages in thread From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw) To: netfilter-devel; +Cc: Jozsef Kadlecsik, Florian Westphal For bitmap this change makes no difference, because destructors are called synchronously. List type however calls them via call_rcu() so accounting decrement can happen after list_set_flush() set ext_size to 0. 'set->elements = 0' can be removed for the same reason in the list type case, it calls 'set->elements--' for each element. Fixes: 9e41f26a505c ("netfilter: ipset: Count non-static extension memory for userspace") Suggested-by: Jozsef Kadlecsik <kadlec@netfilter.org> Signed-off-by: Florian Westphal <fw@strlen.de> --- Was not part of earlier RFC series. net/netfilter/ipset/ip_set_bitmap_gen.h | 2 +- net/netfilter/ipset/ip_set_list_set.c | 3 +-- 2 files changed, 2 insertions(+), 3 deletions(-) diff --git a/net/netfilter/ipset/ip_set_bitmap_gen.h b/net/netfilter/ipset/ip_set_bitmap_gen.h index 226fdf17b683..d6a7e6604542 100644 --- a/net/netfilter/ipset/ip_set_bitmap_gen.h +++ b/net/netfilter/ipset/ip_set_bitmap_gen.h @@ -77,7 +77,7 @@ mtype_flush(struct ip_set *set) mtype_ext_cleanup(set); bitmap_zero(map->members, map->elements); set->elements = 0; - atomic64_set(&set->ext_size, 0); + DEBUG_NET_WARN_ON_ONCE(atomic64_read(&set->ext_size) > 0); } /* Calculate the actual memory size of the set data */ diff --git a/net/netfilter/ipset/ip_set_list_set.c b/net/netfilter/ipset/ip_set_list_set.c index ca3ef9479e83..024de3bc9fc3 100644 --- a/net/netfilter/ipset/ip_set_list_set.c +++ b/net/netfilter/ipset/ip_set_list_set.c @@ -420,8 +420,7 @@ list_set_flush(struct ip_set *set) list_for_each_entry_safe(e, n, &map->members, list) list_set_del(set, e); - set->elements = 0; - atomic64_set(&set->ext_size, 0); + DEBUG_NET_WARN_ON_ONCE(set->elements > 0); } static void -- 2.54.0 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH nf 3/7] netfilter: ipset: add rhashtable boilerplate stubs 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal 2026-08-06 10:19 ` [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations Florian Westphal 2026-08-06 10:19 ` [PATCH nf 2/7] netfilter: ipset: let destroy callbacks adjust ext mem size Florian Westphal @ 2026-08-06 10:19 ` Florian Westphal 2026-08-06 10:19 ` [PATCH nf 4/7] netfilter: ipset: add rhltable " Florian Westphal ` (4 subsequent siblings) 7 siblings, 0 replies; 11+ messages in thread From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw) To: netfilter-devel; +Cc: Jozsef Kadlecsik, Florian Westphal Preparation patch. Adds an rhashtable to the set and initialises and destroys it. No elements are ever added to this hashtable. This change is supposed to be devoid of side effects and is separate to reduce size of the conversion patch. Assisted-by: Claude:claude-sonnet-4-6 Signed-off-by: Florian Westphal <fw@strlen.de> --- net/netfilter/ipset/ip_set_hash_gen.h | 111 ++++++++++++++++++++++++-- 1 file changed, 106 insertions(+), 5 deletions(-) diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h index 8c79938410a0..b116b98991cd 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/rhashtable.h> #include <linux/seqlock.h> #include <linux/netfilter/nfnetlink.h> #include <linux/netfilter/ipset/ip_set.h> @@ -217,9 +218,16 @@ static const union nf_inet_addr zeromask = {}; #undef mtype_ahash_destroy #undef mtype_ext_cleanup +#undef mtype_rht_elem +#undef mtype_rht_hashfn +#undef mtype_rht_obj_hashfn +#undef mtype_rht_cmpfn +#undef mtype_rht_params + #undef mtype_add_cidr #undef mtype_del_cidr #undef mtype_del_cidr_all +#undef mtype_flush_elem #undef mtype_ahash_memsize #undef mtype_flush #undef mtype_destroy @@ -265,9 +273,17 @@ static const union nf_inet_addr zeromask = {}; #define mtype_ahash_destroy IPSET_TOKEN(MTYPE, _ahash_destroy) #define mtype_ext_cleanup IPSET_TOKEN(MTYPE, _ext_cleanup) + +#define mtype_rht_elem IPSET_TOKEN(MTYPE, _rht_elem) +#define mtype_rht_hashfn IPSET_TOKEN(MTYPE, _rht_hashfn) +#define mtype_rht_obj_hashfn IPSET_TOKEN(MTYPE, _rht_obj_hashfn) +#define mtype_rht_cmpfn IPSET_TOKEN(MTYPE, _rht_cmpfn) +#define mtype_rht_params IPSET_TOKEN(MTYPE, _rht_params) + #define mtype_add_cidr IPSET_TOKEN(MTYPE, _add_cidr) #define mtype_del_cidr IPSET_TOKEN(MTYPE, _del_cidr) #define mtype_del_cidr_all IPSET_TOKEN(MTYPE, _del_cidr_all) +#define mtype_flush_elem IPSET_TOKEN(MTYPE, _flush_elem) #define mtype_ahash_memsize IPSET_TOKEN(MTYPE, _ahash_memsize) #define mtype_flush IPSET_TOKEN(MTYPE, _flush) #define mtype_destroy IPSET_TOKEN(MTYPE, _destroy) @@ -300,6 +316,60 @@ static const union nf_inet_addr zeromask = {}; #define htype MTYPE +/* Per-element rhashtable object. Extensions follow the elem field inline; + * allocate as offsetof(struct mtype_rht_elem, elem) + set->dsize bytes. + */ +struct mtype_rht_elem { + struct rhash_head node; + struct rcu_head rcu; /* deferred free after removal */ + struct mtype_elem elem; /* element data; extensions follow */ +}; + +/* jhash of the lookup key */ +static u32 mtype_rht_hashfn(const void *data, u32 len, u32 seed) +{ + BUILD_BUG_ON(HKEY_DATALEN % sizeof(u32) != 0); + return jhash2((const u32 *)data, HKEY_DATALEN / sizeof(u32), seed); +} + +/* jhash of an existing element object */ +static u32 mtype_rht_obj_hashfn(const void *obj, u32 len, u32 seed) +{ + const struct mtype_rht_elem *e = obj; +#ifdef IP_SET_HASH_WITH_NETS + /* Reset transient flags (e.g. nomatch) before hashing so that the + * object hash always equals the lookup-key hash computed by hashfn. + */ + struct mtype_elem tmp; + u8 flags = 0; + + memcpy(&tmp, &e->elem, HKEY_DATALEN); + mtype_data_reset_flags(&tmp, &flags); + return jhash2((const u32 *)&tmp, HKEY_DATALEN / sizeof(u32), seed); +#else + return jhash2((const u32 *)&e->elem, HKEY_DATALEN / sizeof(u32), seed); +#endif +} + +/* 0 = key matches object (equal), non-zero = not equal */ +static int mtype_rht_cmpfn(struct rhashtable_compare_arg *arg, const void *obj) +{ + const struct mtype_rht_elem *e = obj; + u32 multi = 0; + + return !mtype_data_equal(&e->elem, + (const struct mtype_elem *)arg->key, &multi); +} + +static const struct rhashtable_params mtype_rht_params = { + .head_offset = offsetof(struct mtype_rht_elem, node), + .hashfn = mtype_rht_hashfn, + .obj_hashfn = mtype_rht_obj_hashfn, + .obj_cmpfn = mtype_rht_cmpfn, + .key_len = HKEY_DATALEN, + .automatic_shrinking = true, +}; + #define HKEY(data, initval, htable_bits) \ ({ \ const u32 *__k = (const u32 *)data; \ @@ -313,6 +383,7 @@ static const union nf_inet_addr zeromask = {}; /* The generic hash structure */ struct htype { struct htable __rcu *table; /* the hash table */ + struct rhashtable ht; /* the hash table */ struct net_prefixes __rcu *rnets[IPSET_NET_COUNT]; /* cidr prefixes */ struct htable_gc gc; /* gc workqueue */ u32 maxelem; /* max elements in the hash */ @@ -482,6 +553,16 @@ mtype_del_cidr_all(struct ip_set *set, struct htype *h, const struct mtype_elem #endif } +/* Free one element: called by rhashtable_free_and_destroy */ +static void +mtype_flush_elem(void *ptr, void *arg) +{ + struct ip_set *set = arg; + struct mtype_rht_elem *e = ptr; + + ip_set_ext_destroy(set, &e->elem); + kfree_rcu(e, rcu); +} /* Calculate the actual memory size of the set data */ static size_t mtype_ahash_memsize(const struct htype *h, const struct htable *t) @@ -588,6 +669,8 @@ mtype_destroy(struct ip_set *set) struct htable *t = (__force struct htable *)h->table; struct list_head *l, *lt; + rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set); + list_for_each_safe(l, lt, &t->ad) { list_del(l); kfree(l); @@ -1655,6 +1738,7 @@ static int IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, struct nlattr *tb[], u32 flags) { + struct rhashtable_params params; u32 hashsize = IPSET_DEFAULT_HASHSIZE, maxelem = IPSET_DEFAULT_MAXELEM; #ifdef IP_SET_HASH_WITH_MARKMASK u32 markmask; @@ -1671,6 +1755,7 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, size_t hsize; struct htype *h; struct htable *t; + int err; u32 i; pr_debug("Create set %s with family %s\n", @@ -1752,15 +1837,29 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, #ifdef IP_SET_PROTO_UNDEF hsize = sizeof(struct htype); + params = mtype_rht_params; #else - hsize = set->family == NFPROTO_IPV6 ? - sizeof(struct IPSET_TOKEN(HTYPE, 6)) : - sizeof(struct IPSET_TOKEN(HTYPE, 4)); + if (set->family == NFPROTO_IPV6) { + hsize = sizeof(struct IPSET_TOKEN(HTYPE, 6)); + params = IPSET_TOKEN(HTYPE, 6_rht_params); + } else { + hsize = sizeof(struct IPSET_TOKEN(HTYPE, 4)); + params = IPSET_TOKEN(HTYPE, 4_rht_params); + } #endif h = kzalloc(hsize, GFP_KERNEL); if (!h) return -ENOMEM; + /* Initialize rhashtable with the user-requested size as hint */ + params.nelem_hint = hashsize; + /* maxsize: maximum bucket table size to expand to */ + params.max_size = maxelem; + + err = rhashtable_init(&h->ht, ¶ms); + if (err) + goto free_h; + /* Compute htable_bits from the user input parameter hashsize. * Assume that hashsize == 2^htable_bits, * otherwise round up to the first 2^n value. @@ -1768,10 +1867,10 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, hbits = fls(hashsize - 1); hsize = htable_size(hbits); if (hsize == 0) - goto free_h; + goto free_rht; t = ip_set_alloc(hsize); if (!t) - goto free_h; + goto free_rht; t->hregion = ip_set_alloc(ahash_sizeof_regions(hbits)); if (!t->hregion) goto free_t; @@ -1858,6 +1957,8 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, #endif free_t: ip_set_free(t); +free_rht: + rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set); free_h: kfree(h); return -ENOMEM; -- 2.54.0 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH nf 4/7] netfilter: ipset: add rhltable boilerplate stubs 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal ` (2 preceding siblings ...) 2026-08-06 10:19 ` [PATCH nf 3/7] netfilter: ipset: add rhashtable boilerplate stubs Florian Westphal @ 2026-08-06 10:19 ` Florian Westphal 2026-08-06 10:19 ` [PATCH nf 5/7] netfilter: ipset: replace internal hash table with rhashtable Florian Westphal ` (3 subsequent siblings) 7 siblings, 0 replies; 11+ messages in thread From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw) To: netfilter-devel; +Cc: Jozsef Kadlecsik, Florian Westphal Preparation patch. ip_set_hash_netiface.c (IP_SET_HASH_WITH_MULTI) may store distinct elements with the same hash key. rhashtable doesn't support this. For these sets, switch to rhltable which stores identical hlist heads. We can then walk the list after lookup to find best match. Signed-off-by: Florian Westphal <fw@strlen.de> --- Was not part of earlier RFC series. net/netfilter/ipset/ip_set_hash_gen.h | 41 +++++++++++++++++++++- net/netfilter/ipset/ip_set_hash_netiface.c | 24 +++++++++---- 2 files changed, 58 insertions(+), 7 deletions(-) diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h index b116b98991cd..c426ccfca520 100644 --- a/net/netfilter/ipset/ip_set_hash_gen.h +++ b/net/netfilter/ipset/ip_set_hash_gen.h @@ -206,6 +206,7 @@ static const union nf_inet_addr zeromask = {}; /* Family dependent templates */ #undef ahash_data +#undef mtype_key_equal #undef mtype_data_equal #undef mtype_do_data_match #undef mtype_data_set_flags @@ -257,6 +258,9 @@ static const union nf_inet_addr zeromask = {}; #undef htype #undef HKEY +#ifdef IP_SET_HASH_WITH_MULTI +#define mtype_key_equal IPSET_TOKEN(MTYPE, _key_equal) +#endif #define mtype_data_equal IPSET_TOKEN(MTYPE, _data_equal) #ifdef IP_SET_HASH_WITH_NETS #define mtype_do_data_match IPSET_TOKEN(MTYPE, _do_data_match) @@ -320,7 +324,11 @@ static const union nf_inet_addr zeromask = {}; * allocate as offsetof(struct mtype_rht_elem, elem) + set->dsize bytes. */ struct mtype_rht_elem { +#ifdef IP_SET_HASH_WITH_MULTI + struct rhlist_head node; +#else struct rhash_head node; +#endif struct rcu_head rcu; /* deferred free after removal */ struct mtype_elem elem; /* element data; extensions follow */ }; @@ -355,10 +363,15 @@ static u32 mtype_rht_obj_hashfn(const void *obj, u32 len, u32 seed) static int mtype_rht_cmpfn(struct rhashtable_compare_arg *arg, const void *obj) { const struct mtype_rht_elem *e = obj; +#ifdef IP_SET_HASH_WITH_MULTI + return !mtype_key_equal(&e->elem, + (const struct mtype_elem *)arg->key); +#else u32 multi = 0; return !mtype_data_equal(&e->elem, - (const struct mtype_elem *)arg->key, &multi); + (const struct mtype_elem *)arg->key, &multi); +#endif } static const struct rhashtable_params mtype_rht_params = { @@ -383,7 +396,11 @@ static const struct rhashtable_params mtype_rht_params = { /* The generic hash structure */ struct htype { struct htable __rcu *table; /* the hash table */ +#ifdef IP_SET_HASH_WITH_MULTI + struct rhltable rhlt; /* the hashlist table */ +#else struct rhashtable ht; /* the hash table */ +#endif struct net_prefixes __rcu *rnets[IPSET_NET_COUNT]; /* cidr prefixes */ struct htable_gc gc; /* gc workqueue */ u32 maxelem; /* max elements in the hash */ @@ -402,6 +419,16 @@ struct htype { struct mtype_elem next; /* temporary storage for uadd */ }; +#ifdef IP_SET_HASH_WITH_MULTI +#define ipset_hash_nelems(h) atomic_read(&(h)->rhlt.ht.nelems) +#define ipset_hash_walk_enter(h, iter) rhltable_walk_enter(&(h)->rhlt, (iter)) +#define ipset_hash_remove(h, e) rhltable_remove(&(h)->rhlt, &(e)->node, mtype_rht_params) +#else +#define ipset_hash_nelems(h) atomic_read(&(h)->ht.nelems) +#define ipset_hash_walk_enter(h, iter) rhashtable_walk_enter(&(h)->ht, (iter)) +#define ipset_hash_remove(h, e) rhashtable_remove_fast(&(h)->ht, &(e)->node, mtype_rht_params) +#endif + /* ADD|DEL entries saved during resize */ struct mtype_resize_ad { struct list_head list; @@ -669,7 +696,11 @@ mtype_destroy(struct ip_set *set) struct htable *t = (__force struct htable *)h->table; struct list_head *l, *lt; +#ifdef IP_SET_HASH_WITH_MULTI + rhltable_free_and_destroy(&h->rhlt, mtype_flush_elem, set); +#else rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set); +#endif list_for_each_safe(l, lt, &t->ad) { list_del(l); @@ -1856,7 +1887,11 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, /* maxsize: maximum bucket table size to expand to */ params.max_size = maxelem; +#ifdef IP_SET_HASH_WITH_MULTI + err = rhltable_init(&h->rhlt, ¶ms); +#else err = rhashtable_init(&h->ht, ¶ms); +#endif if (err) goto free_h; @@ -1958,7 +1993,11 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, free_t: ip_set_free(t); free_rht: +#ifdef IP_SET_HASH_WITH_MULTI + rhltable_free_and_destroy(&h->rhlt, mtype_flush_elem, set); +#else rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set); +#endif free_h: kfree(h); return -ENOMEM; diff --git a/net/netfilter/ipset/ip_set_hash_netiface.c b/net/netfilter/ipset/ip_set_hash_netiface.c index b602cc43565d..edadd6307675 100644 --- a/net/netfilter/ipset/ip_set_hash_netiface.c +++ b/net/netfilter/ipset/ip_set_hash_netiface.c @@ -63,16 +63,22 @@ struct hash_netiface4_elem { }; /* Common functions */ +static bool +hash_netiface4_key_equal(const struct hash_netiface4_elem *ip1, + const struct hash_netiface4_elem *ip2) +{ + return ip1->ip == ip2->ip && + ip1->cidr == ip2->cidr && + ip1->physdev == ip2->physdev; +} static bool hash_netiface4_data_equal(const struct hash_netiface4_elem *ip1, const struct hash_netiface4_elem *ip2, u32 *multi) { - return ip1->ip == ip2->ip && - ip1->cidr == ip2->cidr && + return hash_netiface4_key_equal(ip1, ip2) && (++*multi) && - ip1->physdev == ip2->physdev && (ip1->wildcard ? strncmp(ip1->iface, ip2->iface, strlen(ip1->iface)) == 0 : strcmp(ip1->iface, ip2->iface) == 0); @@ -297,16 +303,22 @@ struct hash_netiface6_elem { }; /* Common functions */ +static bool +hash_netiface6_key_equal(const struct hash_netiface6_elem *ip1, + const struct hash_netiface6_elem *ip2) +{ + return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) && + ip1->cidr == ip2->cidr && + ip1->physdev == ip2->physdev; +} static bool hash_netiface6_data_equal(const struct hash_netiface6_elem *ip1, const struct hash_netiface6_elem *ip2, u32 *multi) { - return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) && - ip1->cidr == ip2->cidr && + return hash_netiface6_key_equal(ip1, ip2) && (++*multi) && - ip1->physdev == ip2->physdev && (ip1->wildcard ? strncmp(ip1->iface, ip2->iface, strlen(ip1->iface)) == 0 : strcmp(ip1->iface, ip2->iface) == 0); -- 2.54.0 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH nf 5/7] netfilter: ipset: replace internal hash table with rhashtable 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal ` (3 preceding siblings ...) 2026-08-06 10:19 ` [PATCH nf 4/7] netfilter: ipset: add rhltable " Florian Westphal @ 2026-08-06 10:19 ` Florian Westphal 2026-08-06 10:19 ` [PATCH nf 6/7] netfilter: ipset: re-add forceadd support for rhashtable Florian Westphal ` (2 subsequent siblings) 7 siblings, 0 replies; 11+ messages in thread From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw) To: netfilter-devel; +Cc: Jozsef Kadlecsik, Florian Westphal Replace ipset hash tables with rhashtable. The IP_SET_HASH_WITH_MULTI hash type is converted to an rhltable: It stores *lists* of identical hash keys that contain different data. For this set type (netiface) the hash is the address/netmask and the data part also stores an interface name. Matching in such a set needs to first obtain a the best net/mask match, and then walk the rhlist to search for a matching interface name. This optionally allows wildcard matching / partial matching of the name prefix. The hash table replaced here supported this via the "multi" flag, which is now obsolete and will be removed. The replaced hash table also had a AHASH_MAX_TUNED value of 64: this provided an implicit upper bound of identical hash keys that could be inserted. An existing test in ipset.git fails if more than 64 entries can be added. As the chain list walk becomes expensive with increasing length, keep this limit but make it explicit via RHL_MAX_CHAINLEN. FORCEADD is removed to reduce diff size, it is added back later. Initval, bucket size and hashtable bits configuration options are kept for backwards compatibility; they are not used anymore. Rename mtype_ext_size() to mtype_rht_size() because the function returns the size of the rhashtable. automatic rhashtable shrinking remains disabled for now. Quoting Jozsef: "the hash types of ipset presently can only grow to the max size but can never shrink. [..] if automatic_shrinking is set to false, then both the current behaviour is kept and no resizing happens due to running a gc before listing head/dumping the whole set." Setting rhashtable .automatic_shrinking to true will not break the kernel, but it does cause test flakiness in a few ipset test cases: those check that timed out elements disappear after a few seconds. With automatic_shrinking enabled, that can cause the dump walker to hit -EAGAIN during resize which may results in duplicate or omitted elements. Keep auto-shrinking disabled for now. In case it is later needed, it would be possible to mark such dumps as interrupted and let userspace retry. There are several left-overs from the old implementation remaining, these will be removed in a followup series: - resize callback and resize checks - region locking - multi-flag - data_next stubs Joint work with Jozsef Kadlecisk. Assisted-by: Claude:claude-opus-4-6 Signed-off-by: Florian Westphal <fw@strlen.de> --- Several changes compared to RFC (conditional rhltable usage). Requires 'rhashtable: fix false-positive lockdep splat on rhltable destruction' net/netfilter/ipset/ip_set_hash_gen.h | 1401 ++++++++----------------- 1 file changed, 411 insertions(+), 990 deletions(-) diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h index c426ccfca520..277cefd4cd19 100644 --- a/net/netfilter/ipset/ip_set_hash_gen.h +++ b/net/netfilter/ipset/ip_set_hash_gen.h @@ -5,7 +5,6 @@ #define _IP_SET_HASH_GEN_H #include <linux/rcupdate.h> -#include <linux/rcupdate_wait.h> #include <linux/jhash.h> #include <linux/types.h> #include <linux/rhashtable.h> @@ -18,84 +17,23 @@ #define ipset_dereference_nfnl(p) \ rcu_dereference_protected(p, \ lockdep_nfnl_is_held(NFNL_SUBSYS_IPSET)) -#define ipset_dereference_set(p, set) \ - rcu_dereference_protected(p, \ - lockdep_nfnl_is_held(NFNL_SUBSYS_IPSET) || \ - lockdep_is_held(&(set)->lock)) #define ipset_dereference_bh_nfnl(p) \ rcu_dereference_bh_check(p, \ lockdep_nfnl_is_held(NFNL_SUBSYS_IPSET)) -/* Hashing which uses arrays to resolve clashing. The hash table is resized - * (doubled) when searching becomes too long. - * Internally jhash is used with the assumption that the size of the - * stored data is a multiple of sizeof(u32). - * - * Readers and resizing - * - * Resizing can be triggered by userspace command only, and those - * are serialized by the nfnl mutex. During resizing the set is - * read-locked, so the only possible concurrent operations are - * the kernel side readers. Those must be protected by proper RCU locking. - */ - -/* Number of elements to store in an initial array block */ +/* Kept for backward compatibility */ #define AHASH_INIT_SIZE 2 -/* Max number of elements to store in an array block */ #define AHASH_MAX_SIZE (6 * AHASH_INIT_SIZE) -/* Max muber of elements in the array block when tuned */ -#define AHASH_MAX_TUNED 64 -#define AHASH_MAX(h) ((h)->bucketsize) - -/* A hash bucket */ -struct hbucket { - struct rcu_head rcu; /* for call_rcu */ - /* Which positions are used in the array */ - DECLARE_BITMAP(used, AHASH_MAX_TUNED); - u8 size; /* size of the array */ - u8 pos; /* position of the first free entry */ - unsigned char value[] /* the array of the values */ - __aligned(__alignof__(u64)); -}; -/* Region size for locking == 2^HTABLE_REGION_BITS */ -#define HTABLE_REGION_BITS 10 -#define ahash_numof_locks(htable_bits) \ - ((htable_bits) < HTABLE_REGION_BITS ? 1 \ - : jhash_size((htable_bits) - HTABLE_REGION_BITS)) -#define ahash_sizeof_regions(htable_bits) \ - (ahash_numof_locks(htable_bits) * sizeof(struct ip_set_region)) -#define ahash_region(n) \ - ((n) / jhash_size(HTABLE_REGION_BITS)) -#define ahash_bucket_start(h, htable_bits) \ - ((htable_bits) < HTABLE_REGION_BITS ? 0 \ - : (h) * jhash_size(HTABLE_REGION_BITS)) -#define ahash_bucket_end(h, htable_bits) \ - ((htable_bits) < HTABLE_REGION_BITS ? jhash_size(htable_bits) \ - : ((h) + 1) * jhash_size(HTABLE_REGION_BITS)) +#ifdef IP_SET_HASH_WITH_MULTI +#define RHL_MAX_CHAINLEN 64 +#endif struct htable_gc { struct delayed_work dwork; struct ip_set *set; /* Set the gc belongs to */ - spinlock_t lock; /* Lock to exclude gc and resize */ - u32 region; /* Last gc run position */ }; -/* The hash table: the table size stored here in order to make resizing easy */ -struct htable { - bool resizing; /* Mark ongoing resize */ - atomic_t uref; /* References for dumping and gc */ - u8 htable_bits; /* size of hash table == 2^htable_bits */ - u32 maxelem; /* Maxelem per region */ - struct list_head ad; /* Resize add|del backlist */ - struct ip_set_region *hregion; /* Region locks and ext sizes */ - struct hbucket __rcu *bucket[]; /* hashtable buckets */ -}; - -#define hbucket(h, i) ((h)->bucket[i]) -#define ext_size(n, dsize) \ - (sizeof(struct hbucket) + (n) * (dsize)) - #ifndef IPSET_NET_COUNT #define IPSET_NET_COUNT 1 #endif @@ -132,23 +70,6 @@ struct net_prefixes { struct net_prefix nets[] __counted_by(len); }; -/* Compute the hash table size */ -static size_t -htable_size(u8 hbits) -{ - size_t hsize; - - /* We must fit both into u32 in jhash and INT_MAX in kvmalloc_node() */ - if (hbits > 31) - return 0; - hsize = jhash_size(hbits); - if ((INT_MAX - sizeof(struct htable)) / sizeof(struct hbucket *) - < hsize) - return 0; - - return hsize * sizeof(struct hbucket *) + sizeof(struct htable); -} - #ifdef IP_SET_HASH_WITH_NETS #if IPSET_NET_COUNT > 1 #define __CIDR(cidr, i) (cidr[i]) @@ -217,8 +138,6 @@ static const union nf_inet_addr zeromask = {}; #undef mtype_data_next #undef mtype_elem -#undef mtype_ahash_destroy -#undef mtype_ext_cleanup #undef mtype_rht_elem #undef mtype_rht_hashfn #undef mtype_rht_obj_hashfn @@ -229,23 +148,19 @@ static const union nf_inet_addr zeromask = {}; #undef mtype_del_cidr #undef mtype_del_cidr_all #undef mtype_flush_elem -#undef mtype_ahash_memsize #undef mtype_flush #undef mtype_destroy #undef mtype_same_set #undef mtype_kadt #undef mtype_uadt -#undef mtype_bucket_size -#undef mtype_hash_size #undef mtype_add +#undef mtype_do_set_exts #undef mtype_del #undef mtype_test_cidrs #undef mtype_test #undef mtype_uref -#undef mtype_resize -#undef mtype_ext_size -#undef mtype_resize_ad +#undef mtype_rht_size #undef mtype_head #undef mtype_list #undef mtype_gc_do @@ -256,7 +171,6 @@ static const union nf_inet_addr zeromask = {}; #undef mtype_data_match #undef htype -#undef HKEY #ifdef IP_SET_HASH_WITH_MULTI #define mtype_key_equal IPSET_TOKEN(MTYPE, _key_equal) @@ -275,9 +189,6 @@ static const union nf_inet_addr zeromask = {}; #define mtype_data_next IPSET_TOKEN(MTYPE, _data_next) #define mtype_elem IPSET_TOKEN(MTYPE, _elem) -#define mtype_ahash_destroy IPSET_TOKEN(MTYPE, _ahash_destroy) -#define mtype_ext_cleanup IPSET_TOKEN(MTYPE, _ext_cleanup) - #define mtype_rht_elem IPSET_TOKEN(MTYPE, _rht_elem) #define mtype_rht_hashfn IPSET_TOKEN(MTYPE, _rht_hashfn) #define mtype_rht_obj_hashfn IPSET_TOKEN(MTYPE, _rht_obj_hashfn) @@ -288,23 +199,18 @@ static const union nf_inet_addr zeromask = {}; #define mtype_del_cidr IPSET_TOKEN(MTYPE, _del_cidr) #define mtype_del_cidr_all IPSET_TOKEN(MTYPE, _del_cidr_all) #define mtype_flush_elem IPSET_TOKEN(MTYPE, _flush_elem) -#define mtype_ahash_memsize IPSET_TOKEN(MTYPE, _ahash_memsize) #define mtype_flush IPSET_TOKEN(MTYPE, _flush) #define mtype_destroy IPSET_TOKEN(MTYPE, _destroy) #define mtype_same_set IPSET_TOKEN(MTYPE, _same_set) #define mtype_kadt IPSET_TOKEN(MTYPE, _kadt) #define mtype_uadt IPSET_TOKEN(MTYPE, _uadt) -#define mtype_bucket_size IPSET_TOKEN(MTYPE, _bucket_size) -#define mtype_hash_size IPSET_TOKEN(MTYPE, _hash_size) #define mtype_add IPSET_TOKEN(MTYPE, _add) #define mtype_del IPSET_TOKEN(MTYPE, _del) #define mtype_test_cidrs IPSET_TOKEN(MTYPE, _test_cidrs) #define mtype_test IPSET_TOKEN(MTYPE, _test) #define mtype_uref IPSET_TOKEN(MTYPE, _uref) -#define mtype_resize IPSET_TOKEN(MTYPE, _resize) -#define mtype_ext_size IPSET_TOKEN(MTYPE, _ext_size) -#define mtype_resize_ad IPSET_TOKEN(MTYPE, _resize_ad) +#define mtype_rht_size IPSET_TOKEN(MTYPE, _ext_size) #define mtype_head IPSET_TOKEN(MTYPE, _head) #define mtype_list IPSET_TOKEN(MTYPE, _list) #define mtype_gc_do IPSET_TOKEN(MTYPE, _gc_do) @@ -380,22 +286,10 @@ static const struct rhashtable_params mtype_rht_params = { .obj_hashfn = mtype_rht_obj_hashfn, .obj_cmpfn = mtype_rht_cmpfn, .key_len = HKEY_DATALEN, - .automatic_shrinking = true, }; -#define HKEY(data, initval, htable_bits) \ -({ \ - const u32 *__k = (const u32 *)data; \ - u32 __l = HKEY_DATALEN / sizeof(u32); \ - \ - BUILD_BUG_ON(HKEY_DATALEN % sizeof(u32) != 0); \ - \ - jhash2(__k, __l, initval) & jhash_mask(htable_bits); \ -}) - -/* The generic hash structure */ +/* The hash set type */ struct htype { - struct htable __rcu *table; /* the hash table */ #ifdef IP_SET_HASH_WITH_MULTI struct rhltable rhlt; /* the hashlist table */ #else @@ -404,11 +298,12 @@ struct htype { struct net_prefixes __rcu *rnets[IPSET_NET_COUNT]; /* cidr prefixes */ struct htable_gc gc; /* gc workqueue */ u32 maxelem; /* max elements in the hash */ - u32 initval; /* random jhash init value */ + u32 initval; /* kept for backward compatibility */ #ifdef IP_SET_HASH_WITH_MARKMASK u32 markmask; /* markmask value for mark mask to store */ #endif - u8 bucketsize; /* max elements in an array block */ + u8 htable_bits; /* kept for backward compatibility */ + u8 bucketsize; /* kept for backward compatibility */ #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) u8 netmask; /* netmask value for subnets to store */ union nf_inet_addr bitmask; /* stores bitmask */ @@ -429,16 +324,6 @@ struct htype { #define ipset_hash_remove(h, e) rhashtable_remove_fast(&(h)->ht, &(e)->node, mtype_rht_params) #endif -/* ADD|DEL entries saved during resize */ -struct mtype_resize_ad { - struct list_head list; - enum ipset_adt ad; /* ADD|DEL element */ - struct mtype_elem d; /* Element value */ - struct ip_set_ext ext; /* Extensions for ADD */ - struct ip_set_ext mext; /* Target extensions for ADD */ - u32 flags; /* Flags for ADD */ -}; - #ifdef IP_SET_HASH_WITH_NETS /** * mtype_add_cidr - Add a CIDR entry to hash table bookkeeping @@ -590,102 +475,32 @@ mtype_flush_elem(void *ptr, void *arg) ip_set_ext_destroy(set, &e->elem); kfree_rcu(e, rcu); } -/* Calculate the actual memory size of the set data */ -static size_t -mtype_ahash_memsize(const struct htype *h, const struct htable *t) -{ - return sizeof(*h) + sizeof(*t) + ahash_sizeof_regions(t->htable_bits); -} - -/* Get the ith element from the array block n */ -#define ahash_data(n, i, dsize) \ - ((struct mtype_elem *)((n)->value + ((i) * (dsize)))) - -static void -mtype_ext_cleanup(struct ip_set *set, struct hbucket *n) -{ - int i; - u8 pos = smp_load_acquire(&n->pos); - - for (i = 0; i < pos; i++) - if (test_bit(i, n->used)) - ip_set_ext_destroy(set, ahash_data(n, i, set->dsize)); -} /* Flush a hash type of set: destroy all elements */ static void mtype_flush(struct ip_set *set) { struct htype *h = set->data; -#ifdef IP_SET_HASH_WITH_NETS - struct net_prefixes *nets, *tmp; -#endif - struct htable *t; - struct hbucket *n; - u32 r, i; - - t = ipset_dereference_nfnl(h->table); - for (r = 0; r < ahash_numof_locks(t->htable_bits); r++) { - spin_lock_bh(&t->hregion[r].lock); - for (i = ahash_bucket_start(r, t->htable_bits); - i < ahash_bucket_end(r, t->htable_bits); i++) { - n = __ipset_dereference(hbucket(t, i)); - if (!n) - continue; - if (set->extensions & IPSET_EXT_DESTROY) - mtype_ext_cleanup(set, n); - /* FIXME: use slab cache */ - rcu_assign_pointer(hbucket(t, i), NULL); - kfree_rcu(n, rcu); - } - t->hregion[r].ext_size = 0; - t->hregion[r].elements = 0; - spin_unlock_bh(&t->hregion[r].lock); - } -#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; - - for (j = 0; j < nets->len; j++) - nets->nets[j].count = 0; - } else { - rcu_assign_pointer(h->rnets[i], tmp); - kfree_rcu(nets, rcu); - } - } -#endif -} + struct rhashtable_iter hti; + struct mtype_rht_elem *e; -/* Destroy the hashtable part of the set */ -static void -mtype_ahash_destroy(struct ip_set *set, struct htable *t, bool ext_destroy) -{ -#ifdef IP_SET_HASH_WITH_NETS - struct htype *h = set->data; -#endif - struct hbucket *n; - u32 i; + ipset_hash_walk_enter(h, &hti); + rhashtable_walk_start(&hti); - for (i = 0; i < jhash_size(t->htable_bits); i++) { - n = (__force struct hbucket *)hbucket(t, i); - if (!n) - continue; - if (set->extensions & IPSET_EXT_DESTROY && ext_destroy) - mtype_ext_cleanup(set, n); - /* FIXME: use slab cache */ - kfree(n); + while ((e = rhashtable_walk_next(&hti))) { + if (IS_ERR(e)) { + if (PTR_ERR(e) == -EAGAIN) + continue; + break; + } + if (ipset_hash_remove(h, e)) + continue; /* Concurrent delete? skip */ + mtype_del_cidr_all(set, h, &e->elem); + ip_set_ext_destroy(set, &e->elem); + kfree_rcu(e, rcu); } - -#ifdef IP_SET_HASH_WITH_NETS - if (ext_destroy) - for (i = 0; i < IPSET_NET_COUNT; i++) - kfree(rcu_dereference_raw(h->rnets[i])); -#endif - ip_set_free(t->hregion); - ip_set_free(t); + rhashtable_walk_stop(&hti); + rhashtable_walk_exit(&hti); } /* Destroy a hash type of set */ @@ -693,8 +508,9 @@ static void mtype_destroy(struct ip_set *set) { struct htype *h = set->data; - struct htable *t = (__force struct htable *)h->table; - struct list_head *l, *lt; +#ifdef IP_SET_HASH_WITH_NETS + u32 i; +#endif #ifdef IP_SET_HASH_WITH_MULTI rhltable_free_and_destroy(&h->rhlt, mtype_flush_elem, set); @@ -702,11 +518,10 @@ mtype_destroy(struct ip_set *set) rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set); #endif - list_for_each_safe(l, lt, &t->ad) { - list_del(l); - kfree(l); - } - mtype_ahash_destroy(set, t, true); +#ifdef IP_SET_HASH_WITH_NETS + for (i = 0; i < IPSET_NET_COUNT; i++) + kfree(rcu_dereference_raw(h->rnets[i])); +#endif kfree(h); set->data = NULL; @@ -718,7 +533,6 @@ mtype_same_set(const struct ip_set *a, const struct ip_set *b) const struct htype *x = a->data; const struct htype *y = b->data; - /* Resizing changes htable_bits, so we ignore it */ return x->maxelem == y->maxelem && a->timeout == b->timeout && #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) @@ -731,69 +545,46 @@ mtype_same_set(const struct ip_set *a, const struct ip_set *b) } static void -mtype_gc_do(struct ip_set *set, struct htype *h, struct htable *t, u32 r) +mtype_gc_do(struct ip_set *set) { - struct hbucket *n, *tmp; - struct mtype_elem *data; - u32 i, j, d; - size_t dsize = set->dsize; - u8 pos, htable_bits = t->htable_bits; - - spin_lock_bh(&t->hregion[r].lock); - for (i = ahash_bucket_start(r, htable_bits); - i < ahash_bucket_end(r, htable_bits); i++) { - n = __ipset_dereference(hbucket(t, i)); - if (!n) - continue; - pos = smp_load_acquire(&n->pos); - for (j = 0, d = 0; j < pos; j++) { - if (!test_bit(j, n->used)) { - d++; - continue; - } - data = ahash_data(n, j, dsize); - if (!ip_set_timeout_expired(ext_timeout(data, set))) + struct htype *h = set->data; + struct rhashtable_iter hti; + struct mtype_rht_elem *e; + unsigned int seen = 0; + + ipset_hash_walk_enter(h, &hti); +restart: + rhashtable_walk_start(&hti); + + while ((e = rhashtable_walk_next(&hti))) { + bool drop_lock; + + if (IS_ERR(e)) { + if (PTR_ERR(e) == -EAGAIN) continue; - pr_debug("expired %u/%u\n", i, j); - clear_bit(j, n->used); - smp_mb__after_atomic(); - mtype_del_cidr_all(set, h, data); - t->hregion[r].elements--; - ip_set_ext_destroy(set, data); - d++; + break; } - if (d >= AHASH_INIT_SIZE) { - if (d >= n->size) { - t->hregion[r].ext_size -= - ext_size(n->size, dsize); - rcu_assign_pointer(hbucket(t, i), NULL); - kfree_rcu(n, rcu); - continue; - } - tmp = kzalloc(sizeof(*tmp) + - (n->size - AHASH_INIT_SIZE) * dsize, - GFP_ATOMIC); - if (!tmp) - /* Still try to delete expired elements. */ - continue; - tmp->size = n->size - AHASH_INIT_SIZE; - for (j = 0, d = 0; j < pos; j++) { - if (!test_bit(j, n->used)) - continue; - data = ahash_data(n, j, dsize); - memcpy(tmp->value + d * dsize, - data, dsize); - set_bit(d, tmp->used); - d++; - } - tmp->pos = d; - t->hregion[r].ext_size -= - ext_size(AHASH_INIT_SIZE, dsize); - rcu_assign_pointer(hbucket(t, i), tmp); - kfree_rcu(n, rcu); + + drop_lock = need_resched(); + if (seen++ > 64 && drop_lock) { + seen = 0; + rhashtable_walk_stop(&hti); + cond_resched(); + goto restart; } + + if (!ip_set_timeout_expired(ext_timeout(&e->elem, set))) + continue; + + if (ipset_hash_remove(h, e)) + continue; + + ip_set_ext_destroy(set, &e->elem); + mtype_del_cidr_all(set, h, &e->elem); + kfree_rcu(e, rcu); } - spin_unlock_bh(&t->hregion[r].lock); + rhashtable_walk_stop(&hti); + rhashtable_walk_exit(&hti); } static void @@ -801,40 +592,18 @@ mtype_gc(struct work_struct *work) { struct htable_gc *gc; struct ip_set *set; - struct htype *h; - struct htable *t; - u32 r, numof_locks; unsigned int next_run; gc = container_of(work, struct htable_gc, dwork.work); set = gc->set; - h = set->data; - rcu_read_lock_bh(); - t = rcu_dereference_bh(h->table); - atomic_inc(&t->uref); - rcu_read_unlock_bh(); - numof_locks = ahash_numof_locks(t->htable_bits); - r = gc->region++; - if (r >= numof_locks) { - r = gc->region = 0; - } - next_run = (IPSET_GC_PERIOD(set->timeout) * HZ) / numof_locks; - if (next_run < HZ/10) - next_run = HZ/10; - - spin_lock_bh(&gc->lock); - if (!t->resizing) - mtype_gc_do(set, h, t, r); - spin_unlock_bh(&gc->lock); - - if (atomic_dec_and_test(&t->uref) && t->resizing) { - pr_debug("Table destroy after resize by expire: %p\n", t); - mtype_ahash_destroy(set, t, false); - } + next_run = IPSET_GC_PERIOD(set->timeout) * HZ; + if (next_run < HZ) + next_run = HZ; - queue_delayed_work(system_power_efficient_wq, &gc->dwork, next_run); + mtype_gc_do(set); + queue_delayed_work(system_power_efficient_wq, &gc->dwork, next_run); } static void @@ -853,248 +622,21 @@ mtype_cancel_gc(struct ip_set *set) disable_delayed_work_sync(&h->gc.dwork); } -static int -mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext, - struct ip_set_ext *mext, u32 flags); -static int -mtype_del(struct ip_set *set, void *value, const struct ip_set_ext *ext, - struct ip_set_ext *mext, u32 flags); - -/* Resize a hash: create a new hash table with doubling the hashsize - * and inserting the elements to it. Repeat until we succeed or - * fail due to memory pressures. - */ -static int -mtype_resize(struct ip_set *set, bool retried) +/* Get the current number of elements and per-element memory in the set */ +static void +mtype_rht_size(struct ip_set *set, u32 *elements, size_t *ext_size) { - struct htype *h = set->data; - struct htable *t, *orig; - u8 pos, htable_bits; - size_t hsize, dsize = set->dsize; -#ifdef IP_SET_HASH_WITH_NETS - u8 flags; - struct mtype_elem *tmp; -#endif - struct mtype_elem *data; - struct mtype_elem *d; - struct hbucket *n, *m; - struct list_head *l, *lt; - struct mtype_resize_ad *x; - u32 i, j, r, nr, key; - int ret; - -#ifdef IP_SET_HASH_WITH_NETS - tmp = kmalloc(dsize, GFP_KERNEL); - if (!tmp) - return -ENOMEM; -#endif - orig = ipset_dereference_bh_nfnl(h->table); - htable_bits = orig->htable_bits; - -retry: - ret = 0; - htable_bits++; - if (!htable_bits) - goto hbwarn; - hsize = htable_size(htable_bits); - if (!hsize) - goto hbwarn; - t = ip_set_alloc(hsize); - if (!t) { - ret = -ENOMEM; - goto out; - } - t->hregion = ip_set_alloc(ahash_sizeof_regions(htable_bits)); - if (!t->hregion) { - ip_set_free(t); - ret = -ENOMEM; - goto out; - } - t->htable_bits = htable_bits; - t->maxelem = h->maxelem / ahash_numof_locks(htable_bits); - INIT_LIST_HEAD(&t->ad); - for (i = 0; i < ahash_numof_locks(htable_bits); i++) - spin_lock_init(&t->hregion[i].lock); - - /* There can't be another parallel resizing, - * but dumping and kernel side add/del are possible - */ - orig = ipset_dereference_bh_nfnl(h->table); - atomic_inc(&orig->uref); - spin_lock_bh(&h->gc.lock); - orig->resizing = true; - spin_unlock_bh(&h->gc.lock); - pr_debug("attempt to resize set %s from %u to %u, t %p\n", - set->name, orig->htable_bits, htable_bits, orig); - for (r = 0; r < ahash_numof_locks(orig->htable_bits); r++) { - /* Expire may replace a hbucket with another one */ - rcu_read_lock_bh(); - for (i = ahash_bucket_start(r, orig->htable_bits); - i < ahash_bucket_end(r, orig->htable_bits); i++) { - n = __ipset_dereference(hbucket(orig, i)); - if (!n) - continue; - pos = smp_load_acquire(&n->pos); - for (j = 0; j < pos; j++) { - if (!test_bit_acquire(j, n->used)) - continue; - data = ahash_data(n, j, dsize); - if (SET_ELEM_EXPIRED(set, data)) - continue; -#ifdef IP_SET_HASH_WITH_NETS - /* We have readers running parallel with us, - * so the live data cannot be modified. - */ - flags = 0; - memcpy(tmp, data, dsize); - data = tmp; - mtype_data_reset_flags(data, &flags); -#endif - key = HKEY(data, h->initval, htable_bits); - m = __ipset_dereference(hbucket(t, key)); - nr = ahash_region(key); - if (!m) { - m = kzalloc(sizeof(*m) + - AHASH_INIT_SIZE * dsize, - GFP_ATOMIC); - if (!m) { - ret = -ENOMEM; - goto cleanup; - } - m->size = AHASH_INIT_SIZE; - t->hregion[nr].ext_size += - ext_size(AHASH_INIT_SIZE, - dsize); - RCU_INIT_POINTER(hbucket(t, key), m); - } else if (m->pos >= m->size) { - struct hbucket *ht; - - if (m->size >= AHASH_MAX(h)) { - ret = -EAGAIN; - } else { - ht = kzalloc(sizeof(*ht) + - (m->size + AHASH_INIT_SIZE) - * dsize, - GFP_ATOMIC); - if (!ht) - ret = -ENOMEM; - } - if (ret < 0) - goto cleanup; - memcpy(ht, m, sizeof(struct hbucket) + - m->size * dsize); - ht->size = m->size + AHASH_INIT_SIZE; - t->hregion[nr].ext_size += - ext_size(AHASH_INIT_SIZE, - dsize); - kfree(m); - m = ht; - RCU_INIT_POINTER(hbucket(t, key), ht); - } - d = ahash_data(m, m->pos, dsize); - memcpy(d, data, dsize); - set_bit(m->pos++, m->used); - t->hregion[nr].elements++; -#ifdef IP_SET_HASH_WITH_NETS - mtype_data_reset_flags(d, &flags); -#endif - } - } - rcu_read_unlock_bh(); - } - - /* There can't be any other writer. */ - rcu_assign_pointer(h->table, t); + const struct htype *h = set->data; - /* Give time to other readers of the set */ - synchronize_rcu(); - - pr_debug("set %s resized from %u (%p) to %u (%p)\n", set->name, - orig->htable_bits, orig, t->htable_bits, t); - /* Add/delete elements processed by the SET target during resize. - * Kernel-side add cannot trigger a resize and userspace actions - * are serialized by the mutex. + /* Do GC to collect expired elements now so that the reported + * element count doesn't include expired elements. */ - list_for_each_safe(l, lt, &orig->ad) { - x = list_entry(l, struct mtype_resize_ad, list); - if (x->ad == IPSET_ADD) { - mtype_add(set, &x->d, &x->ext, &x->mext, x->flags); - } else { - mtype_del(set, &x->d, NULL, NULL, 0); - } - list_del(l); - kfree(l); - } - /* If there's nobody else using the table, destroy it */ - if (atomic_dec_and_test(&orig->uref)) { - pr_debug("Table destroy by resize %p\n", orig); - mtype_ahash_destroy(set, orig, false); - } - -out: -#ifdef IP_SET_HASH_WITH_NETS - kfree(tmp); -#endif - return ret; - -cleanup: - rcu_read_unlock_bh(); - spin_lock_bh(&h->gc.lock); - orig->resizing = false; - spin_unlock_bh(&h->gc.lock); - /* Make sure parallel readers see that orig->resizing is false - * before we decrement uref */ - synchronize_rcu(); - atomic_dec(&orig->uref); - mtype_ahash_destroy(set, t, false); - if (ret == -EAGAIN) - goto retry; - - /* Cleanup the backlog of ADD/DEL elements */ - spin_lock_bh(&set->lock); - list_for_each_safe(l, lt, &orig->ad) { - list_del(l); - kfree(l); - } - spin_unlock_bh(&set->lock); - goto out; - -hbwarn: - /* In case we have plenty of memory :-) */ - pr_warn("Cannot increase the hashsize of set %s further\n", set->name); - ret = -IPSET_ERR_HASH_FULL; - goto out; -} + if (SET_WITH_TIMEOUT(set)) + mtype_gc_do(set); -/* Get the current number of elements and ext_size in the set */ -static void -mtype_ext_size(struct ip_set *set, u32 *elements, size_t *ext_size) -{ - struct htype *h = set->data; - const struct htable *t; - struct hbucket *n; - struct mtype_elem *data; - u32 i, j, r; - u8 pos; - - t = rcu_dereference_bh(h->table); - for (r = 0; r < ahash_numof_locks(t->htable_bits); r++) { - for (i = ahash_bucket_start(r, t->htable_bits); - i < ahash_bucket_end(r, t->htable_bits); i++) { - n = rcu_dereference_bh(hbucket(t, i)); - if (!n) - continue; - pos = smp_load_acquire(&n->pos); - for (j = 0; j < pos; j++) { - if (!test_bit_acquire(j, n->used)) - continue; - data = ahash_data(n, j, set->dsize); - if (!SET_ELEM_EXPIRED(set, data)) - (*elements)++; - } - } - *ext_size += t->hregion[r].ext_size; - } + *elements = ipset_hash_nelems(h); + *ext_size = *elements * + (offsetof(struct mtype_rht_elem, elem) + set->dsize); } /* Add an element to a hash and update the internal counters when succeeded, @@ -1104,299 +646,224 @@ static int mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext, struct ip_set_ext *mext, u32 flags) { - struct htype *h = set->data; - struct htable *t; + struct mtype_rht_elem *e, *old = NULL; const struct mtype_elem *d = value; - struct mtype_elem *data; - struct hbucket *n, *old = ERR_PTR(-ENOENT); - int i, j = -1, ret; bool flag_exist = flags & IPSET_FLAG_EXIST; - bool deleted = false, forceadd = false, reuse = false; - u32 r, key, multi = 0, elements, maxelem; - u8 npos = 0; + struct htype *h = set->data; + int ret = 0; +#ifdef IP_SET_HASH_WITH_NETS + int i; +#endif rcu_read_lock_bh(); - t = rcu_dereference_bh(h->table); - key = HKEY(value, h->initval, t->htable_bits); - r = ahash_region(key); - atomic_inc(&t->uref); - rcu_read_unlock_bh(); - elements = t->hregion[r].elements; - maxelem = t->maxelem; - if (elements >= maxelem) { - u32 e; - if (SET_WITH_TIMEOUT(set)) - mtype_gc_do(set, h, t, r); - maxelem = h->maxelem; - elements = 0; - for (e = 0; e < ahash_numof_locks(t->htable_bits); e++) - elements += t->hregion[e].elements; - if (elements >= maxelem && SET_WITH_FORCEADD(set)) - forceadd = true; - } - - spin_lock_bh(&t->hregion[r].lock); - n = rcu_dereference_bh(hbucket(t, key)); - if (!n) { - if (forceadd || elements >= maxelem) - goto set_full; - old = NULL; - n = kzalloc(sizeof(*n) + AHASH_INIT_SIZE * set->dsize, - GFP_ATOMIC); - if (!n) { - ret = -ENOMEM; - goto unlock; - } - n->size = AHASH_INIT_SIZE; - t->hregion[r].ext_size += - ext_size(AHASH_INIT_SIZE, set->dsize); - goto copy_elem; - } - npos = smp_load_acquire(&n->pos); - for (i = 0; i < npos; i++) { - if (!test_bit(i, n->used)) { - /* Reuse first deleted entry */ - if (j == -1) { - deleted = reuse = true; - j = i; - } - continue; - } - data = ahash_data(n, i, set->dsize); - if (mtype_data_equal(data, d, &multi)) { - if (flag_exist || SET_ELEM_EXPIRED(set, data)) { - /* Just the extensions could be overwritten */ - j = i; - goto overwrite_extensions; +#ifdef IP_SET_HASH_WITH_MULTI + { + struct rhlist_head *tmp, *list; + unsigned int seen = 0; + u32 multi = 0; + + list = rhltable_lookup(&h->rhlt, d, mtype_rht_params); + if (!list) + goto insert; + + rhl_for_each_entry_rcu(old, tmp, list, node) { + if (SET_ELEM_EXPIRED(set, &old->elem)) { + if (rhltable_remove(&h->rhlt, &old->node, mtype_rht_params) == 0) { + mtype_del_cidr_all(set, h, &old->elem); + ip_set_ext_destroy(set, &old->elem); + kfree_rcu(old, rcu); + } + continue; } - ret = -IPSET_ERR_EXIST; - goto unlock; + + if (mtype_data_equal(&old->elem, d, &multi)) + goto insert; + ++seen; } - /* Reuse first timed out entry */ - if (SET_ELEM_EXPIRED(set, data) && j == -1) { - j = i; - reuse = true; + + if (seen >= RHL_MAX_CHAINLEN) { + ret = -IPSET_ERR_HASH_FULL; + goto out_rcu_unlock; } + old = NULL; } - if (reuse || forceadd) { - if (j == -1) - j = 0; - data = ahash_data(n, j, set->dsize); - if (!deleted) { - mtype_del_cidr_all(set, h, data); - ip_set_ext_destroy(set, data); - t->hregion[r].elements--; +#else + old = rhashtable_lookup(&h->ht, d, mtype_rht_params); + if (!old) + goto insert; + /* simple case 1: element is expired, same as old == NULL. */ + if (SET_ELEM_EXPIRED(set, &old->elem)) { + if (rhashtable_remove_fast(&h->ht, &old->node, + mtype_rht_params) == 0) { + mtype_del_cidr_all(set, h, &old->elem); + ip_set_ext_destroy(set, &old->elem); + kfree_rcu(old, rcu); } - goto copy_data; + old = NULL; } - if (elements >= maxelem) - goto set_full; - /* Create a new slot */ - if (npos >= n->size) { -#ifdef IP_SET_HASH_WITH_MULTI - if (h->bucketsize >= AHASH_MAX_TUNED) - goto set_full; - else if (h->bucketsize <= multi) - h->bucketsize += AHASH_INIT_SIZE; #endif - if (n->size >= AHASH_MAX(h)) { - /* Trigger rehashing */ - mtype_data_next(&h->next, d); - ret = -EAGAIN; - goto resize; - } - old = n; - n = kzalloc(sizeof(*n) + - (old->size + AHASH_INIT_SIZE) * set->dsize, - GFP_ATOMIC); - if (!n) { - ret = -ENOMEM; - goto unlock; - } - memcpy(n, old, sizeof(struct hbucket) + - old->size * set->dsize); - n->size = old->size + AHASH_INIT_SIZE; - t->hregion[r].ext_size += - ext_size(AHASH_INIT_SIZE, set->dsize); +insert: + /* simple case 2: exists and we are not replacing. + * Can't do in-place extension updates, this can race with GC + * and mtype_del(): could end up adding new comment to an + * element that had kfree_rcu() called on it. + */ + if (old && !flag_exist) { + ret = -IPSET_ERR_EXIST; + goto out_rcu_unlock; } -copy_elem: - j = npos++; - data = ahash_data(n, j, set->dsize); -copy_data: - t->hregion[r].elements++; -#ifdef IP_SET_HASH_WITH_NETS - for (i = 0; i < IPSET_NET_COUNT; i++) - mtype_add_cidr(set, h, DCIDR_GET(d->cidr, i), i); -#endif - memcpy(data, d, sizeof(struct mtype_elem)); -overwrite_extensions: + if (!old && ipset_hash_nelems(h) >= h->maxelem) { + if (net_ratelimit()) + pr_warn("Set %s is full, maxelem %u reached\n", + set->name, h->maxelem); + ret = -IPSET_ERR_HASH_FULL; + goto out_rcu_unlock; + } + + e = kzalloc(offsetof(struct mtype_rht_elem, elem) + set->dsize, + GFP_ATOMIC); + if (!e) { + ret = -ENOMEM; + goto out_rcu_unlock; + } + + memcpy(&e->elem, d, sizeof(struct mtype_elem)); + #ifdef IP_SET_HASH_WITH_NETS - mtype_data_set_flags(data, flags); + for (i = 0; i < IPSET_NET_COUNT; i++) { + ret = mtype_add_cidr(set, h, DCIDR_GET(d->cidr, i), i); + if (ret) { + while (i > 0) { + --i; + mtype_del_cidr(set, h, DCIDR_GET(d->cidr, i), i); + } + kfree(e); + goto out_rcu_unlock; + } + } + + mtype_data_set_flags(&e->elem, flags); #endif if (SET_WITH_COUNTER(set)) - ip_set_init_counter(ext_counter(data, set), ext); + ip_set_init_counter(ext_counter(&e->elem, set), ext); if (SET_WITH_COMMENT(set) && !ext->target) - ip_set_init_comment(set, ext_comment(data, set), ext); + ip_set_init_comment(set, ext_comment(&e->elem, set), ext); if (SET_WITH_SKBINFO(set)) - ip_set_init_skbinfo(ext_skbinfo(data, set), ext); - /* Must come last for the case when timed out entry is reused */ + ip_set_init_skbinfo(ext_skbinfo(&e->elem, set), ext); if (SET_WITH_TIMEOUT(set)) - ip_set_timeout_set(ext_timeout(data, set), ext->timeout); - smp_mb__before_atomic(); - /* Ensure all data writes are visible before updating position */ - smp_store_release(&n->pos, npos); - set_bit(j, n->used); - if (old != ERR_PTR(-ENOENT)) { - rcu_assign_pointer(hbucket(t, key), n); - if (old) - kfree_rcu(old, rcu); - } - ret = 0; -resize: - spin_unlock_bh(&t->hregion[r].lock); - if (t->resizing && ext && ext->target) { - /* Resize is in process and kernel side add, save values */ - struct mtype_resize_ad *x; - - x = kzalloc_obj(struct mtype_resize_ad, GFP_ATOMIC); - if (!x) - /* Don't bother */ - goto out; - x->ad = IPSET_ADD; - memcpy(&x->d, value, sizeof(struct mtype_elem)); - memcpy(&x->ext, ext, sizeof(struct ip_set_ext)); - memcpy(&x->mext, mext, sizeof(struct ip_set_ext)); - x->flags = flags; - spin_lock_bh(&set->lock); - list_add_tail(&x->list, &t->ad); - spin_unlock_bh(&set->lock); + ip_set_timeout_set(ext_timeout(&e->elem, set), ext->timeout); + +#ifdef IP_SET_HASH_WITH_MULTI + if (old) + ret = rhashtable_replace_fast(&h->rhlt.ht, &old->node.rhead, + &e->node.rhead, mtype_rht_params); + else + ret = rhltable_insert_key(&h->rhlt, &e->elem, &e->node, mtype_rht_params); +#else + if (old) + ret = rhashtable_replace_fast(&h->ht, &old->node, &e->node, mtype_rht_params); + else + ret = rhashtable_insert_fast(&h->ht, &e->node, mtype_rht_params); +#endif + if (ret == -ENOENT && old) { + /* replace failed: maybe GC or concurrent mtype_del() + * reaped old element right now. + * + * Try once more with plain insert. + */ + old = NULL; +#ifdef IP_SET_HASH_WITH_MULTI + ret = rhltable_insert_key(&h->rhlt, &e->elem, &e->node, mtype_rht_params); +#else + ret = rhashtable_insert_fast(&h->ht, &e->node, mtype_rht_params); +#endif } - goto out; -set_full: - if (net_ratelimit()) - pr_warn("Set %s is full, maxelem %u reached\n", - set->name, maxelem); - ret = -IPSET_ERR_HASH_FULL; -unlock: - spin_unlock_bh(&t->hregion[r].lock); -out: - if (atomic_dec_and_test(&t->uref) && t->resizing) { - pr_debug("Table destroy after resize by add: %p\n", t); - mtype_ahash_destroy(set, t, false); + if (ret) { + ip_set_ext_destroy(set, &e->elem); + kfree(e); + /* error: Undo mtype_add_cidr(). */ + mtype_del_cidr_all(set, h, d); + } else if (old) { + /* Update the new elements counters with the replaced + * one, unless userspace gave specific start values. + * + * old_c is still visible to other CPUs, so this is + * best-effort only. + */ + if (ext->packets == ULLONG_MAX && + SET_WITH_COUNTER(set) && + !SET_ELEM_EXPIRED(set, &old->elem)) { + const struct ip_set_counter *old_c = ext_counter(&old->elem, set); + struct ip_set_counter *new_c = ext_counter(&e->elem, set); + + atomic64_add(atomic64_read(&old_c->bytes), &new_c->bytes); + atomic64_add(atomic64_read(&old_c->packets), &new_c->packets); + } + ip_set_ext_destroy(set, &old->elem); + kfree_rcu(old, rcu); + /* successful replace: Undo mtype_add_cidr(). */ + mtype_del_cidr_all(set, h, d); } + + if (ret == -EEXIST) + ret = flag_exist ? 0 : -IPSET_ERR_EXIST; + + if (0) /* to be removed */ + mtype_data_next(&h->next, d); +out_rcu_unlock: + rcu_read_unlock_bh(); return ret; } -/* Delete an element from the hash and free up space if possible. - */ +/* Delete an element from the hash */ static int mtype_del(struct ip_set *set, void *value, const struct ip_set_ext *ext, struct ip_set_ext *mext, u32 flags) { struct htype *h = set->data; - struct htable *t; const struct mtype_elem *d = value; - struct mtype_elem *data; - struct hbucket *n; - struct mtype_resize_ad *x = NULL; - int i, j, k, r, ret = -IPSET_ERR_EXIST; - u32 key, multi = 0; - size_t dsize = set->dsize; - u8 pos; - - /* Userspace add and resize is excluded by the mutex. - * Kernespace add does not trigger resize. - */ - rcu_read_lock_bh(); - t = rcu_dereference_bh(h->table); - key = HKEY(value, h->initval, t->htable_bits); - r = ahash_region(key); - atomic_inc(&t->uref); - rcu_read_unlock_bh(); - - spin_lock_bh(&t->hregion[r].lock); - n = rcu_dereference_bh(hbucket(t, key)); - if (!n) - goto out; - pos = smp_load_acquire(&n->pos); - for (i = 0, k = 0; i < pos; i++) { - if (!test_bit(i, n->used)) { - k++; - continue; - } - data = ahash_data(n, i, dsize); - if (!mtype_data_equal(data, d, &multi)) - continue; - if (SET_ELEM_EXPIRED(set, data)) - goto out; + struct mtype_rht_elem *e; + int ret = -IPSET_ERR_EXIST; - ret = 0; - clear_bit(i, n->used); - smp_mb__after_atomic(); - if (i + 1 == pos) - smp_store_release(&n->pos, --pos); - t->hregion[r].elements--; - mtype_del_cidr_all(set, h, d); - ip_set_ext_destroy(set, data); - - if (t->resizing && ext && ext->target) { - /* Resize is in process and kernel side del, - * save values - */ - x = kzalloc_obj(struct mtype_resize_ad, GFP_ATOMIC); - if (x) { - x->ad = IPSET_DEL; - memcpy(&x->d, value, - sizeof(struct mtype_elem)); - x->flags = flags; - } - } - for (; i < pos; i++) { - if (!test_bit(i, n->used)) - k++; - } - if (k == pos) { - t->hregion[r].ext_size -= ext_size(n->size, dsize); - rcu_assign_pointer(hbucket(t, key), NULL); - kfree_rcu(n, rcu); - } else if (k >= AHASH_INIT_SIZE) { - struct hbucket *tmp = kzalloc(sizeof(*tmp) + - (n->size - AHASH_INIT_SIZE) * dsize, - GFP_ATOMIC); - if (!tmp) - goto out; - tmp->size = n->size - AHASH_INIT_SIZE; - for (j = 0, k = 0; j < pos; j++) { - if (!test_bit(j, n->used)) - continue; - data = ahash_data(n, j, dsize); - memcpy(tmp->value + k * dsize, data, dsize); - set_bit(k, tmp->used); - k++; - } - tmp->pos = k; - t->hregion[r].ext_size -= - ext_size(AHASH_INIT_SIZE, dsize); - rcu_assign_pointer(hbucket(t, key), tmp); - kfree_rcu(n, rcu); + rcu_read_lock_bh(); +#ifdef IP_SET_HASH_WITH_MULTI + { + struct rhlist_head *tmp, *list; + u32 multi = 0; + + list = rhltable_lookup(&h->rhlt, d, mtype_rht_params); + if (!list) + goto out_unlock; + rhl_for_each_entry_rcu(e, tmp, list, node) { + if (!mtype_data_equal(&e->elem, d, &multi)) + continue; + if (SET_ELEM_EXPIRED(set, &e->elem)) + goto out_unlock; + /* fails if GC evicts this entry right now. */ + ret = rhltable_remove(&h->rhlt, &e->node, mtype_rht_params); + break; } - goto out; - } -out: - spin_unlock_bh(&t->hregion[r].lock); - if (x) { - spin_lock_bh(&set->lock); - list_add(&x->list, &t->ad); - spin_unlock_bh(&set->lock); - } - if (atomic_dec_and_test(&t->uref) && t->resizing) { - pr_debug("Table destroy after resize by del: %p\n", t); - mtype_ahash_destroy(set, t, false); + /* either no entry found or race with GC */ + if (ret) + goto out_unlock; } - return ret; +#else + e = rhashtable_lookup(&h->ht, d, mtype_rht_params); + if (!e || SET_ELEM_EXPIRED(set, &e->elem)) + goto out_unlock; + ret = rhashtable_remove_fast(&h->ht, &e->node, mtype_rht_params); + if (ret) + goto out_unlock; +#endif + mtype_del_cidr_all(set, h, d); + ip_set_ext_destroy(set, &e->elem); + kfree_rcu(e, rcu); +out_unlock: + rcu_read_unlock_bh(); + return ret ? -IPSET_ERR_EXIST : 0; } static int @@ -1419,30 +886,26 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d, struct ip_set_ext *mext, u32 flags) { struct htype *h = set->data; - struct htable *t = rcu_dereference_bh(h->table); struct net_prefixes *nets0; - struct hbucket *n; - struct mtype_elem *data; + struct mtype_rht_elem *e; #if IPSET_NET_COUNT == 2 struct net_prefixes *nets1; struct mtype_elem orig = *d; unsigned int seq1; - int ret, i, j, k; + int ret, j, k; #else - int ret, i, j; + int ret, j; #endif unsigned int seq0; - u32 key, multi; - u8 pos; + u32 multi; pr_debug("test by nets\n"); - rcu_read_lock_bh(); retry: multi = 0; - nets0 = rcu_dereference_bh(h->rnets[0]); + nets0 = ipset_dereference_bh_nfnl(h->rnets[0]); seq0 = read_seqcount_begin(&nets0->seq); #if IPSET_NET_COUNT == 2 - nets1 = rcu_dereference_bh(h->rnets[1]); + nets1 = ipset_dereference_bh_nfnl(h->rnets[1]); seq1 = read_seqcount_begin(&nets1->seq); #endif for (j = 0; j < nets0->len && !multi; j++) { @@ -1462,25 +925,36 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d, #else mtype_data_netmask(d, p0.cidr); #endif - key = HKEY(d, h->initval, t->htable_bits); - n = rcu_dereference_bh(hbucket(t, key)); - if (!n) +#ifdef IP_SET_HASH_WITH_MULTI + { + struct rhlist_head *tmp, *list; + + list = rhltable_lookup(&h->rhlt, d, mtype_rht_params); + if (!list) continue; - pos = smp_load_acquire(&n->pos); - for (i = 0; i < pos; i++) { - if (!test_bit_acquire(i, n->used)) - continue; - data = ahash_data(n, i, set->dsize); - if (!mtype_data_equal(data, d, &multi)) + + rhl_for_each_entry_rcu(e, tmp, list, node) { + if (!SET_ELEM_EXPIRED(set, &e->elem)) + multi = true; + if (!mtype_data_equal(&e->elem, d, &multi)) continue; - ret = mtype_data_match(data, ext, mext, set, flags); + ret = mtype_data_match(&e->elem, ext, mext, set, flags); + if (ret) + return ret; + multi = false; + } + } +#else + e = rhashtable_lookup(&h->ht, d, mtype_rht_params); + if (e) { + if (!SET_ELEM_EXPIRED(set, &e->elem)) + multi = true; + ret = mtype_data_match(&e->elem, ext, mext, set, flags); if (ret != 0) - goto unlock; -#ifdef IP_SET_HASH_WITH_MULTI - /* No match, reset multiple match flag */ - multi = 0; -#endif + return ret; + multi = false; } +#endif #if IPSET_NET_COUNT == 2 } #endif @@ -1492,10 +966,7 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d, if (read_seqcount_retry(&nets1->seq, seq1)) goto retry; #endif - ret = 0; -unlock: - rcu_read_unlock_bh(); - return ret; + return 0; } #endif @@ -1505,16 +976,14 @@ mtype_test(struct ip_set *set, void *value, const struct ip_set_ext *ext, struct ip_set_ext *mext, u32 flags) { struct htype *h = set->data; - struct htable *t; struct mtype_elem *d = value; - struct hbucket *n; - struct mtype_elem *data; - int i, ret = 0; - u32 key, multi = 0; - u8 pos; + struct mtype_rht_elem *e; + int ret = 0; +#ifdef IP_SET_HASH_WITH_NETS + int i; +#endif rcu_read_lock_bh(); - t = rcu_dereference_bh(h->table); #ifdef IP_SET_HASH_WITH_NETS /* If we test an IP address and not a network address, * try all possible network sizes @@ -1528,68 +997,53 @@ mtype_test(struct ip_set *set, void *value, const struct ip_set_ext *ext, } #endif - key = HKEY(d, h->initval, t->htable_bits); - n = rcu_dereference_bh(hbucket(t, key)); - if (!n) { - ret = 0; - goto out; - } - pos = smp_load_acquire(&n->pos); - for (i = 0; i < pos; i++) { - if (!test_bit_acquire(i, n->used)) - continue; - data = ahash_data(n, i, set->dsize); - if (!mtype_data_equal(data, d, &multi)) - continue; - ret = mtype_data_match(data, ext, mext, set, flags); - if (ret != 0) +#ifdef IP_SET_HASH_WITH_MULTI + { + struct rhlist_head *tmp, *list; + u32 multi = 0; + + list = rhltable_lookup(&h->rhlt, d, mtype_rht_params); + if (!list) goto out; + + rhl_for_each_entry_rcu(e, tmp, list, node) { + if (!mtype_data_equal(&e->elem, d, &multi)) + continue; + ret = mtype_data_match(&e->elem, ext, mext, set, flags); + if (ret) + goto out; + } } +#else + e = rhashtable_lookup(&h->ht, d, mtype_rht_params); + if (!e) + goto out; + + ret = mtype_data_match(&e->elem, ext, mext, set, flags); +#endif out: rcu_read_unlock_bh(); return ret; } -static u32 mtype_hash_size(const struct htype *h) -{ - const struct htable *t; - u8 htable_bits; - - rcu_read_lock(); - t = rcu_dereference(h->table); - htable_bits = t->htable_bits; - rcu_read_unlock(); - - return jhash_size(htable_bits); -} - -static u32 mtype_bucket_size(const struct htype *h) -{ - return h->bucketsize; -} - /* Reply a HEADER request: fill out the header part of the set */ static int mtype_head(struct ip_set *set, struct sk_buff *skb) { struct htype *h = set->data; - const struct htable *t; struct nlattr *nested; size_t memsize; u32 elements = 0; size_t ext_size = 0; - rcu_read_lock_bh(); - t = rcu_dereference_bh(h->table); - mtype_ext_size(set, &elements, &ext_size); - memsize = mtype_ahash_memsize(h, t) + ext_size + atomic64_read(&set->ext_size); - rcu_read_unlock_bh(); + mtype_rht_size(set, &elements, &ext_size); + memsize = sizeof(*h) + ext_size + atomic64_read(&set->ext_size); nested = nla_nest_start(skb, IPSET_ATTR_DATA); if (!nested) goto nla_put_failure; - if (nla_put_net32(skb, IPSET_ATTR_HASHSIZE, htonl(mtype_hash_size(h)))) + if (nla_put_net32(skb, IPSET_ATTR_HASHSIZE, htonl(jhash_size(h->htable_bits)))) goto nla_put_failure; if (nla_put_net32(skb, IPSET_ATTR_MAXELEM, htonl(h->maxelem))) goto nla_put_failure; @@ -1615,7 +1069,7 @@ mtype_head(struct ip_set *set, struct sk_buff *skb) goto nla_put_failure; #endif if (set->flags & IPSET_CREATE_FLAG_BUCKETSIZE) { - if (nla_put_u8(skb, IPSET_ATTR_BUCKETSIZE, mtype_bucket_size(h))) + if (nla_put_u8(skb, IPSET_ATTR_BUCKETSIZE, h->bucketsize)) goto nla_put_failure; if (nla_put_net32(skb, IPSET_ATTR_INITVAL, htonl(h->initval))) goto nla_put_failure; @@ -1633,25 +1087,23 @@ mtype_head(struct ip_set *set, struct sk_buff *skb) return -EMSGSIZE; } -/* Make possible to run dumping parallel with resizing */ +/* Manage the rhashtable_iter lifetime for dump operations */ static void mtype_uref(struct ip_set *set, struct netlink_callback *cb, bool start) { struct htype *h = set->data; - struct htable *t; + struct rhashtable_iter *hti; if (start) { - rcu_read_lock_bh(); - t = ipset_dereference_bh_nfnl(h->table); - atomic_inc(&t->uref); - cb->args[IPSET_CB_PRIVATE] = (unsigned long)t; - rcu_read_unlock_bh(); - } else if (cb->args[IPSET_CB_PRIVATE]) { - t = (struct htable *)cb->args[IPSET_CB_PRIVATE]; - if (atomic_dec_and_test(&t->uref) && t->resizing) { - pr_debug("Table destroy after resize " - " by dump: %p\n", t); - mtype_ahash_destroy(set, t, false); + hti = kmalloc_obj(*hti, GFP_ATOMIC); + if (hti) + ipset_hash_walk_enter(h, hti); + cb->args[IPSET_CB_PRIVATE] = (unsigned long)hti; + } else { + hti = (struct rhashtable_iter *)cb->args[IPSET_CB_PRIVATE]; + if (hti) { + rhashtable_walk_exit(hti); + kfree(hti); } cb->args[IPSET_CB_PRIVATE] = 0; } @@ -1662,77 +1114,77 @@ static int mtype_list(const struct ip_set *set, struct sk_buff *skb, struct netlink_callback *cb) { - const struct htable *t; + struct rhashtable_iter *hti = + (struct rhashtable_iter *)cb->args[IPSET_CB_PRIVATE]; + struct mtype_rht_elem *e, *peeked; struct nlattr *atd, *nested; - const struct hbucket *n; - const struct mtype_elem *e; - u32 first = cb->args[IPSET_CB_ARG0]; - /* We assume that one hash bucket fills into one page */ void *incomplete; - int i, ret = 0; - u8 pos; + u32 emitted = 0; + int ret = 0; + + if (!hti) + return -EMSGSIZE; atd = nla_nest_start(skb, IPSET_ATTR_ADT); if (!atd) return -EMSGSIZE; - pr_debug("list hash set %s\n", set->name); - t = (const struct htable *)cb->args[IPSET_CB_PRIVATE]; - /* Expire may replace a hbucket with another one */ - rcu_read_lock(); - for (; cb->args[IPSET_CB_ARG0] < jhash_size(t->htable_bits); - cb->args[IPSET_CB_ARG0]++) { - cond_resched_rcu(); - incomplete = skb_tail_pointer(skb); - n = rcu_dereference(hbucket(t, cb->args[IPSET_CB_ARG0])); - pr_debug("cb->arg bucket: %lu, t %p n %p\n", - cb->args[IPSET_CB_ARG0], t, n); - if (!n) - continue; - pos = smp_load_acquire(&n->pos); - for (i = 0; i < pos; i++) { - if (!test_bit_acquire(i, n->used)) - continue; - e = ahash_data(n, i, set->dsize); - if (SET_ELEM_EXPIRED(set, e)) + rhashtable_walk_start(hti); + while ((e = rhashtable_walk_peek(hti))) { + if (IS_ERR(e)) { + if (PTR_ERR(e) == -EAGAIN) continue; - pr_debug("list hash %lu hbucket %p i %u, data %p\n", - cb->args[IPSET_CB_ARG0], n, i, e); - nested = nla_nest_start(skb, IPSET_ATTR_DATA); - if (!nested) { - if (cb->args[IPSET_CB_ARG0] == first) { - nla_nest_cancel(skb, atd); - ret = -EMSGSIZE; - goto out; - } - goto nla_put_failure; - } - if (mtype_data_list(skb, e)) - goto nla_put_failure; - if (ip_set_put_extensions(skb, set, e, true)) - goto nla_put_failure; - nla_nest_end(skb, nested); + ret = PTR_ERR(e); + break; + } + peeked = e; +next_dump: + if (SET_ELEM_EXPIRED(set, &e->elem)) + goto next_entry; + + incomplete = skb_tail_pointer(skb); + nested = nla_nest_start(skb, IPSET_ATTR_DATA); + if (!nested) { + nlmsg_trim(skb, incomplete); + goto paused; + } + if (mtype_data_list(skb, &e->elem) || + ip_set_put_extensions(skb, set, &e->elem, true)) { + nla_nest_cancel(skb, nested); + nlmsg_trim(skb, incomplete); + goto paused; + } + nla_nest_end(skb, nested); + emitted++; +next_entry: + e = rhashtable_walk_next(hti); + if (IS_ERR(e)) { + ret = PTR_ERR(e); + if (ret != -EAGAIN) + break; + ret = 0; + } else if (peeked && e != peeked) { + peeked = NULL; + if (e) + goto next_dump; } } + /* Walk exhausted: listing done */ nla_nest_end(skb, atd); - /* Set listing finished */ + rhashtable_walk_stop(hti); cb->args[IPSET_CB_ARG0] = 0; + return ret; - goto out; - -nla_put_failure: - nlmsg_trim(skb, incomplete); - if (unlikely(first == cb->args[IPSET_CB_ARG0])) { - pr_warn("Can't list set %s: one bucket does not fit into a message. Please report it!\n", - set->name); - cb->args[IPSET_CB_ARG0] = 0; - ret = -EMSGSIZE; - } else { - nla_nest_end(skb, atd); +paused: + if (emitted == 0) { + nla_nest_cancel(skb, atd); + rhashtable_walk_stop(hti); + return -EMSGSIZE; } -out: - rcu_read_unlock(); - return ret; + cb->args[IPSET_CB_ARG0] = 1; + nla_nest_end(skb, atd); + rhashtable_walk_stop(hti); + return 0; } static int @@ -1758,7 +1210,7 @@ static const struct ip_set_type_variant mtype_variant = { .head = mtype_head, .list = mtype_list, .uref = mtype_uref, - .resize = mtype_resize, + .resize = NULL, .same_set = mtype_same_set, .cancel_gc = mtype_cancel_gc, .region_lock = true, @@ -1769,12 +1221,11 @@ static int IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, struct nlattr *tb[], u32 flags) { - struct rhashtable_params params; u32 hashsize = IPSET_DEFAULT_HASHSIZE, maxelem = IPSET_DEFAULT_MAXELEM; + struct rhashtable_params params; #ifdef IP_SET_HASH_WITH_MARKMASK u32 markmask; #endif - u8 hbits; #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) int ret __attribute__((unused)) = 0; u8 netmask = set->family == NFPROTO_IPV4 ? 32 : 128; @@ -1782,12 +1233,11 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, #endif #ifdef IP_SET_HASH_WITH_NETS struct net_prefixes *nets; + int i; #endif size_t hsize; struct htype *h; - struct htable *t; int err; - u32 i; pr_debug("Create set %s with family %s\n", set->name, set->family == NFPROTO_IPV4 ? "inet" : "inet6"); @@ -1882,8 +1332,6 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, if (!h) return -ENOMEM; - /* Initialize rhashtable with the user-requested size as hint */ - params.nelem_hint = hashsize; /* maxsize: maximum bucket table size to expand to */ params.max_size = maxelem; @@ -1895,36 +1343,19 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, if (err) goto free_h; - /* Compute htable_bits from the user input parameter hashsize. - * Assume that hashsize == 2^htable_bits, - * otherwise round up to the first 2^n value. - */ - hbits = fls(hashsize - 1); - hsize = htable_size(hbits); - if (hsize == 0) - goto free_rht; - t = ip_set_alloc(hsize); - if (!t) - goto free_rht; - t->hregion = ip_set_alloc(ahash_sizeof_regions(hbits)); - if (!t->hregion) - goto free_t; #ifdef IP_SET_HASH_WITH_NETS for (i = 0; i < IPSET_NET_COUNT; i++) { nets = kzalloc_obj(*nets); if (!nets) { while (i > 0) kfree(rcu_dereference_raw(h->rnets[--i])); - goto free_hregion; + goto free_rht; } seqcount_spinlock_init(&nets->seq, &set->lock); RCU_INIT_POINTER(h->rnets[i], nets); } #endif h->gc.set = set; - spin_lock_init(&h->gc.lock); - for (i = 0; i < ahash_numof_locks(hbits); i++) - spin_lock_init(&t->hregion[i].lock); h->maxelem = maxelem; #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) h->bitmask = bitmask; @@ -1933,10 +1364,8 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, #ifdef IP_SET_HASH_WITH_MARKMASK h->markmask = markmask; #endif - if (tb[IPSET_ATTR_INITVAL]) + if (tb[IPSET_ATTR_INITVAL]) /* only stored for userspace dump compatibility */ h->initval = ntohl(nla_get_be32(tb[IPSET_ATTR_INITVAL])); - else - get_random_bytes(&h->initval, sizeof(h->initval)); h->bucketsize = AHASH_MAX_SIZE; if (tb[IPSET_ATTR_BUCKETSIZE]) { h->bucketsize = nla_get_u8(tb[IPSET_ATTR_BUCKETSIZE]); @@ -1947,10 +1376,7 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, else if (h->bucketsize % 2) h->bucketsize += 1; } - t->htable_bits = hbits; - t->maxelem = h->maxelem / ahash_numof_locks(hbits); - INIT_LIST_HEAD(&t->ad); - RCU_INIT_POINTER(h->table, t); + h->htable_bits = fls(hashsize - 1); set->data = h; #ifndef IP_SET_PROTO_UNDEF @@ -1980,27 +1406,22 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, IPSET_TOKEN(HTYPE, 6_gc_init)(&h->gc); #endif } - pr_debug("create %s hashsize %u (%u) maxelem %u: %p(%p)\n", - set->name, mtype_hash_size(h), - t->htable_bits, h->maxelem, set->data, t); + pr_debug("create %s hashsize %u maxelem %u\n", + set->name, jhash_size(h->htable_bits), h->maxelem); return 0; #ifdef IP_SET_HASH_WITH_NETS -free_hregion: - ip_set_free(t->hregion); -#endif -free_t: - ip_set_free(t); free_rht: #ifdef IP_SET_HASH_WITH_MULTI rhltable_free_and_destroy(&h->rhlt, mtype_flush_elem, set); #else rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set); #endif +#endif free_h: kfree(h); - return -ENOMEM; + return err ? err : -ENOMEM; } #endif /* IP_SET_EMIT_CREATE */ -- 2.54.0 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH nf 6/7] netfilter: ipset: re-add forceadd support for rhashtable 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal ` (4 preceding siblings ...) 2026-08-06 10:19 ` [PATCH nf 5/7] netfilter: ipset: replace internal hash table with rhashtable Florian Westphal @ 2026-08-06 10:19 ` Florian Westphal 2026-08-06 10:19 ` [PATCH nf 7/7] netfilter: ipset: also report mem size for cidr storage to userspace Florian Westphal 2026-08-06 15:22 ` [syzbot ci] Re: netfilter: switch ipset to rhashtable syzbot ci 7 siblings, 0 replies; 11+ messages in thread From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw) To: netfilter-devel; +Cc: Jozsef Kadlecsik, Florian Westphal The rhashtable conversion removed the SET_WITH_FORCEADD eviction logic. Add mtype_remove_random() helper to lookup a random key slot. If there is an element, try to evict it and allow add of the new element just like before the rhashtable conversion. Assisted-by: Claude:claude-opus-4-6 Signed-off-by: Florian Westphal <fw@strlen.de> --- Very different compared to RFC, now evicts a random element instead of first element found via walk. net/netfilter/ipset/ip_set_hash_gen.h | 67 +++++++++++++++++++++++++-- 1 file changed, 62 insertions(+), 5 deletions(-) diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h index 277cefd4cd19..2bb3ec147ae3 100644 --- a/net/netfilter/ipset/ip_set_hash_gen.h +++ b/net/netfilter/ipset/ip_set_hash_gen.h @@ -154,6 +154,9 @@ static const union nf_inet_addr zeromask = {}; #undef mtype_kadt #undef mtype_uadt +#undef mtype_remove_random +#undef mtype_remove_key +#undef mtype_remove_cmpfn #undef mtype_add #undef mtype_do_set_exts #undef mtype_del @@ -205,6 +208,9 @@ static const union nf_inet_addr zeromask = {}; #define mtype_kadt IPSET_TOKEN(MTYPE, _kadt) #define mtype_uadt IPSET_TOKEN(MTYPE, _uadt) +#define mtype_remove_random IPSET_TOKEN(MTYPE, _remove_random) +#define mtype_remove_key IPSET_TOKEN(MTYPE, _remove_key) +#define mtype_remove_cmpfn IPSET_TOKEN(MTYPE, _remove_cmpfn) #define mtype_add IPSET_TOKEN(MTYPE, _add) #define mtype_del IPSET_TOKEN(MTYPE, _del) #define mtype_test_cidrs IPSET_TOKEN(MTYPE, _test_cidrs) @@ -639,6 +645,55 @@ mtype_rht_size(struct ip_set *set, u32 *elements, size_t *ext_size) (offsetof(struct mtype_rht_elem, elem) + set->dsize); } +static u32 mtype_remove_key(const void *data, u32 len, u32 seed) +{ + return get_random_u32(); +} + +static int mtype_remove_cmpfn(struct rhashtable_compare_arg *arg, const void *obj) +{ + return 0; /* always match */ +} + +/* Evict one element from the set to make room for a new one (forceadd) */ +static bool +mtype_remove_random(struct ip_set *set, struct htype *h) +{ + static const struct rhashtable_params ip_set_hash_rnd_params = { + .head_offset = offsetof(struct mtype_rht_elem, node), + .hashfn = mtype_remove_key, + .obj_hashfn = mtype_rht_obj_hashfn, + .obj_cmpfn = mtype_remove_cmpfn, + .key_len = sizeof(u32), + }; + struct mtype_rht_elem *e = NULL; + bool removed = false; + static const u32 k; + +#ifdef IP_SET_HASH_WITH_MULTI + { + struct rhlist_head *list = rhltable_lookup(&h->rhlt, &k, + ip_set_hash_rnd_params); + if (!list) + return false; + + e = container_of(list, typeof(*e), node); + } +#else + e = rhashtable_lookup(&h->ht, &k, ip_set_hash_rnd_params); +#endif + if (e && !ipset_hash_remove(h, e)) + removed = true; + + if (removed) { + mtype_del_cidr_all(set, h, &e->elem); + ip_set_ext_destroy(set, &e->elem); + kfree_rcu(e, rcu); + } + + return removed; +} + /* Add an element to a hash and update the internal counters when succeeded, * otherwise report the proper error code. */ @@ -714,11 +769,13 @@ mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext, } if (!old && ipset_hash_nelems(h) >= h->maxelem) { - if (net_ratelimit()) - pr_warn("Set %s is full, maxelem %u reached\n", - set->name, h->maxelem); - ret = -IPSET_ERR_HASH_FULL; - goto out_rcu_unlock; + if (!SET_WITH_FORCEADD(set) || !mtype_remove_random(set, h)) { + if (net_ratelimit()) + pr_warn("Set %s is full, maxelem %u reached\n", + set->name, h->maxelem); + ret = -IPSET_ERR_HASH_FULL; + goto out_rcu_unlock; + } } e = kzalloc(offsetof(struct mtype_rht_elem, elem) + set->dsize, -- 2.54.0 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH nf 7/7] netfilter: ipset: also report mem size for cidr storage to userspace 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal ` (5 preceding siblings ...) 2026-08-06 10:19 ` [PATCH nf 6/7] netfilter: ipset: re-add forceadd support for rhashtable Florian Westphal @ 2026-08-06 10:19 ` Florian Westphal 2026-08-06 15:22 ` [syzbot ci] Re: netfilter: switch ipset to rhashtable syzbot ci 7 siblings, 0 replies; 11+ messages in thread From: Florian Westphal @ 2026-08-06 10:19 UTC (permalink / raw) To: netfilter-devel; +Cc: Jozsef Kadlecsik, Florian Westphal After the 'Fixes' commit, the storage is allocated dynamically. Include this when reporting the mem usage. Fixes: 8e5fd2a55e24 ("netfilter: ipset: rework cidr bookkeeping") Signed-off-by: Florian Westphal <fw@strlen.de> --- Not part of RFC. net/netfilter/ipset/ip_set_hash_gen.h | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h index 2bb3ec147ae3..506dae7cec82 100644 --- a/net/netfilter/ipset/ip_set_hash_gen.h +++ b/net/netfilter/ipset/ip_set_hash_gen.h @@ -643,6 +643,23 @@ mtype_rht_size(struct ip_set *set, u32 *elements, size_t *ext_size) *elements = ipset_hash_nelems(h); *ext_size = *elements * (offsetof(struct mtype_rht_elem, elem) + set->dsize); + +#ifdef IP_SET_HASH_WITH_NETS + { + const struct net_prefixes *nets; + int i; + + rcu_read_lock(); + + for (i = 0; i < IPSET_NET_COUNT; i++) { + nets = rcu_dereference(h->rnets[i]); + if (nets) + *ext_size += ksize(nets); + } + + rcu_read_unlock(); + } +#endif } static u32 mtype_remove_key(const void *data, u32 len, u32 seed) -- 2.54.0 ^ permalink raw reply related [flat|nested] 11+ messages in thread
* [syzbot ci] Re: netfilter: switch ipset to rhashtable 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal ` (6 preceding siblings ...) 2026-08-06 10:19 ` [PATCH nf 7/7] netfilter: ipset: also report mem size for cidr storage to userspace Florian Westphal @ 2026-08-06 15:22 ` syzbot ci 7 siblings, 0 replies; 11+ messages in thread From: syzbot ci @ 2026-08-06 15:22 UTC (permalink / raw) To: fw, kadlec, netfilter-devel; +Cc: syzbot, syzkaller-bugs syzbot ci has tested the following series [v1] netfilter: switch ipset to rhashtable https://lore.kernel.org/all/20260806101947.2802-1-fw@strlen.de * [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations * [PATCH nf 2/7] netfilter: ipset: let destroy callbacks adjust ext mem size * [PATCH nf 3/7] netfilter: ipset: add rhashtable boilerplate stubs * [PATCH nf 4/7] netfilter: ipset: add rhltable boilerplate stubs * [PATCH nf 5/7] netfilter: ipset: replace internal hash table with rhashtable * [PATCH nf 6/7] netfilter: ipset: re-add forceadd support for rhashtable * [PATCH nf 7/7] netfilter: ipset: also report mem size for cidr storage to userspace and found the following issues: * UBSAN: shift-out-of-bounds in hash_netiface6_head * UBSAN: shift-out-of-bounds in hash_netportnet6_head Full report is available here: https://ci.syzbot.org/series/e7969a90-d2b3-4da4-8795-4c3794dae0f0 *** UBSAN: shift-out-of-bounds in hash_netiface6_head tree: nf URL: https://kernel.googlesource.com/pub/scm/linux/kernel/git/netfilter/nf.git base: 44871eadd07a7f004aa00cb87399461eea08c630 arch: amd64 compiler: Debian clang version 22.1.8 (++20260613092233+e80beda6e255-1~exp1~20260613092250.77), Debian LLD 22.1.8 config: https://ci.syzbot.org/builds/81d26051-7806-406c-9355-fbf52dca8f68/config syz repro: https://ci.syzbot.org/findings/cb9f585e-5753-41c6-b732-20d1d77f5564/syz_repro ------------[ cut here ]------------ UBSAN: shift-out-of-bounds in net/netfilter/ipset/ip_set_hash_gen.h:1120:46 shift exponent 32 is too large for 32-bit type 'u32' (aka 'unsigned int') CPU: 1 UID: 0 PID: 5865 Comm: syz.2.19 Not tainted syzkaller #0 PREEMPT(full) Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 1.16.2-debian-1.16.2-1 04/01/2014 Call Trace: <TASK> dump_stack_lvl+0xe8/0x150 lib/dump_stack.c:120 ubsan_epilogue+0xa/0x30 lib/ubsan.c:233 __ubsan_handle_shift_out_of_bounds+0x36d/0x400 lib/ubsan.c:494 hash_netiface6_head+0x89e/0x970 net/netfilter/ipset/ip_set_hash_gen.h:1120 ip_set_dump_do+0x1476/0x1920 net/netfilter/ipset/ip_set_core.c:1664 netlink_dump+0x711/0xee0 net/netlink/af_netlink.c:2331 __netlink_dump_start+0x589/0x7b0 net/netlink/af_netlink.c:2446 netlink_dump_start include/linux/netlink.h:341 [inline] ip_set_dump+0x15b/0x1f0 net/netfilter/ipset/ip_set_core.c:1730 nfnetlink_rcv_msg+0xcc2/0x12b0 net/netfilter/nfnetlink.c:300 netlink_rcv_skb+0x226/0x4a0 net/netlink/af_netlink.c:2556 nfnetlink_rcv+0x2b9/0x28c0 net/netfilter/nfnetlink.c:667 netlink_unicast_kernel net/netlink/af_netlink.c:1319 [inline] netlink_unicast+0x7bb/0x940 net/netlink/af_netlink.c:1345 netlink_sendmsg+0x813/0xb40 net/netlink/af_netlink.c:1900 sock_sendmsg_nosec+0x13a/0x180 net/socket.c:775 __sock_sendmsg net/socket.c:790 [inline] ____sys_sendmsg+0x54e/0x850 net/socket.c:2684 ___sys_sendmsg+0x2a5/0x360 net/socket.c:2738 __sys_sendmsg net/socket.c:2770 [inline] __do_sys_sendmsg net/socket.c:2775 [inline] __se_sys_sendmsg net/socket.c:2773 [inline] __x64_sys_sendmsg+0x1b1/0x290 net/socket.c:2773 do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline] do_syscall_64+0x174/0x580 arch/x86/entry/syscall_64.c:94 entry_SYSCALL_64_after_hwframe+0x77/0x7f RIP: 0033:0x7f7b3159e019 Code: ff c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 c7 c1 e8 ff ff ff f7 d8 64 89 01 48 RSP: 002b:00007f7b323e2028 EFLAGS: 00000246 ORIG_RAX: 000000000000002e RAX: ffffffffffffffda RBX: 00007f7b31825fa0 RCX: 00007f7b3159e019 RDX: 0000000000008080 RSI: 0000200000000180 RDI: 0000000000000004 RBP: 00007f7b3163500c R08: 0000000000000000 R09: 0000000000000000 R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000000 R13: 00007f7b31826038 R14: 00007f7b31825fa0 R15: 00007ffdc35054d8 </TASK> ---[ end trace ]--- *** UBSAN: shift-out-of-bounds in hash_netportnet6_head tree: nf URL: https://kernel.googlesource.com/pub/scm/linux/kernel/git/netfilter/nf.git base: 44871eadd07a7f004aa00cb87399461eea08c630 arch: amd64 compiler: Debian clang version 22.1.8 (++20260613092233+e80beda6e255-1~exp1~20260613092250.77), Debian LLD 22.1.8 config: https://ci.syzbot.org/builds/81d26051-7806-406c-9355-fbf52dca8f68/config syz repro: https://ci.syzbot.org/findings/0f098de1-ac6a-4b30-8a0d-ea1586a67851/syz_repro ------------[ cut here ]------------ UBSAN: shift-out-of-bounds in net/netfilter/ipset/ip_set_hash_gen.h:1120:46 shift exponent 32 is too large for 32-bit type 'u32' (aka 'unsigned int') CPU: 1 UID: 0 PID: 5838 Comm: syz.0.17 Not tainted syzkaller #0 PREEMPT(full) Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 1.16.2-debian-1.16.2-1 04/01/2014 Call Trace: <TASK> dump_stack_lvl+0xe8/0x150 lib/dump_stack.c:120 ubsan_epilogue+0xa/0x30 lib/ubsan.c:233 __ubsan_handle_shift_out_of_bounds+0x36d/0x400 lib/ubsan.c:494 hash_netportnet6_head+0x97a/0xa40 net/netfilter/ipset/ip_set_hash_gen.h:1120 ip_set_dump_do+0x1476/0x1920 net/netfilter/ipset/ip_set_core.c:1664 netlink_dump+0x711/0xee0 net/netlink/af_netlink.c:2331 __netlink_dump_start+0x589/0x7b0 net/netlink/af_netlink.c:2446 netlink_dump_start include/linux/netlink.h:341 [inline] ip_set_dump+0x15b/0x1f0 net/netfilter/ipset/ip_set_core.c:1730 nfnetlink_rcv_msg+0xcc2/0x12b0 net/netfilter/nfnetlink.c:300 netlink_rcv_skb+0x226/0x4a0 net/netlink/af_netlink.c:2556 nfnetlink_rcv+0x2b9/0x28c0 net/netfilter/nfnetlink.c:667 netlink_unicast_kernel net/netlink/af_netlink.c:1319 [inline] netlink_unicast+0x7bb/0x940 net/netlink/af_netlink.c:1345 netlink_sendmsg+0x813/0xb40 net/netlink/af_netlink.c:1900 sock_sendmsg_nosec+0x13a/0x180 net/socket.c:775 __sock_sendmsg net/socket.c:790 [inline] ____sys_sendmsg+0x54e/0x850 net/socket.c:2684 ___sys_sendmsg+0x2a5/0x360 net/socket.c:2738 __sys_sendmsg net/socket.c:2770 [inline] __do_sys_sendmsg net/socket.c:2775 [inline] __se_sys_sendmsg net/socket.c:2773 [inline] __x64_sys_sendmsg+0x1b1/0x290 net/socket.c:2773 do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline] do_syscall_64+0x174/0x580 arch/x86/entry/syscall_64.c:94 entry_SYSCALL_64_after_hwframe+0x77/0x7f RIP: 0033:0x7f44dc59e019 Code: ff c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 c7 c1 e8 ff ff ff f7 d8 64 89 01 48 RSP: 002b:00007f44dd41d028 EFLAGS: 00000246 ORIG_RAX: 000000000000002e RAX: ffffffffffffffda RBX: 00007f44dc825fa0 RCX: 00007f44dc59e019 RDX: 0000000000000000 RSI: 0000200000000200 RDI: 0000000000000004 RBP: 00007f44dc63500c R08: 0000000000000000 R09: 0000000000000000 R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000000 R13: 00007f44dc826038 R14: 00007f44dc825fa0 R15: 00007ffdbc9c05c8 </TASK> ---[ end trace ]--- *** If these findings have caused you to resend the series or submit a separate fix, please add the following tag to your commit message: Tested-by: syzbot@syzkaller.appspotmail.com --- This report is generated by a bot. It may contain errors. syzbot ci engineers can be reached at syzkaller@googlegroups.com. To test a patch for this bug, please reply with `#syz test` (should be on a separate line). The patch should be attached to the email. Note: arguments like custom git repos and branches are not supported. ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2026-08-09 14:14 UTC | newest] Thread overview: 11+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2026-08-06 10:19 [PATCH nf 0/7] netfilter: switch ipset to rhashtable Florian Westphal 2026-08-06 10:19 ` [PATCH nf 1/7] netfilter: ipset: remove need to allocate memory on delete operations Florian Westphal 2026-08-09 12:56 ` Jozsef Kadlecsik 2026-08-09 14:14 ` Florian Westphal 2026-08-06 10:19 ` [PATCH nf 2/7] netfilter: ipset: let destroy callbacks adjust ext mem size Florian Westphal 2026-08-06 10:19 ` [PATCH nf 3/7] netfilter: ipset: add rhashtable boilerplate stubs Florian Westphal 2026-08-06 10:19 ` [PATCH nf 4/7] netfilter: ipset: add rhltable " Florian Westphal 2026-08-06 10:19 ` [PATCH nf 5/7] netfilter: ipset: replace internal hash table with rhashtable Florian Westphal 2026-08-06 10:19 ` [PATCH nf 6/7] netfilter: ipset: re-add forceadd support for rhashtable Florian Westphal 2026-08-06 10:19 ` [PATCH nf 7/7] netfilter: ipset: also report mem size for cidr storage to userspace Florian Westphal 2026-08-06 15:22 ` [syzbot ci] Re: netfilter: switch ipset to rhashtable syzbot ci
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox