* [PATCH nf-next v8 1/6] rhashtable: Add rhashtable_flush_and_free helper
2026-11-11 10:11 [PATCH nf-next v8 0/6] ipset: replace internal hash table with rhashtable Florian Westphal
@ 2026-11-11 10:11 ` Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 2/6] netfilter: ipset: add rhashtable boilerplate stubs Florian Westphal
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Florian Westphal @ 2026-11-11 10:11 UTC (permalink / raw)
To: netfilter-devel
From: Herbert Xu <herbert@gondor.apana.org.au>
This patch adds the helper rhashtable_flush_and_free and its
rhltable counter-part. The intended user is netfilter:
https://sashiko.dev/#/patchset/20260828152256.8759-1-fw%40strlen.de
The hash table briefly becomes NULL during the flush call in order
to quiesce insertions on the old table so that ht->nelems can be
reset to zero safely.
The rest of the code is updated to handle ht->tbl being NULL.
In order to ensure that rehashes are fully disabled during the
flush, the self-rearming in rht_deferred_worker is moved inside
the mutex.
Incidentally, this allows the removal of the special hack where
it had to bypass the IRQ work. However, as the existing
rhashtable_free_and_destroy helper does not set the hash table
to NULL, change it to use disable_work_sync instead.
If concurrent insertions and removals hit the old table during
the call, they act directly on the old table.
If they see a NULL ht->tbl, they fail immediately.
Concurrent insertions and removals that see the new table act
on it.
After setting ht->tbl to NULL, the new helper waits for concurrent
insertions and removals on the old ht->tbl to complete, and then
cancels existing rehashes.
Once rehashes are completely gone, ht->nelems is reset to zero,
and the new table is installed.
Walkers are detached from the old table, and the dying flag is
set on the old table so that other walkers cannot reattach themselves
to the dying table. Replace the rcu_head_after_call_rcu check
in rhashtable_walk_stop with the dying flag.
Finally, the entries in the old table are freed.
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
Signed-off-by: Florian Westphal <fw@strlen.de>
---
unchanged in v8.
include/linux/rhashtable.h | 40 +++++++-
lib/rhashtable.c | 186 ++++++++++++++++++++++++++-----------
2 files changed, 171 insertions(+), 55 deletions(-)
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 70dac9214617..b98876dc6ff7 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -67,6 +67,7 @@ struct rhash_lock_head {};
* @nest: Number of bits of first-level nested table.
* @rehash: Current bucket being rehashed
* @hash_rnd: Random seed to fold into hash
+ * @dying: True if table is about to be freed
* @walkers: List of active walkers
* @rcu: RCU structure for freeing the table
* @future_tbl: Table under construction during rehashing
@@ -77,6 +78,7 @@ struct bucket_table {
unsigned int size;
unsigned int nest;
u32 hash_rnd;
+ bool dying;
struct list_head walkers;
struct rcu_head rcu;
@@ -255,6 +257,10 @@ void rhashtable_free_and_destroy(struct rhashtable *ht,
void *arg);
void rhashtable_destroy(struct rhashtable *ht);
+void rhashtable_flush_and_free(struct rhashtable *ht,
+ void (*free_fn)(void *ptr, void *arg),
+ void *arg);
+
struct rhash_lock_head __rcu **rht_bucket_nested(
const struct bucket_table *tbl, unsigned int hash);
struct rhash_lock_head __rcu **__rht_bucket_nested(
@@ -630,6 +636,9 @@ static __always_inline struct rhash_head *__rhashtable_lookup(
BUILD_BUG_ON(!__builtin_constant_p(freq));
tbl = rht_dereference_rcu(ht->tbl, ht);
+ if (!tbl)
+ goto out;
+
restart:
hash = rht_key_hashfn(ht, tbl, key, params);
bkt = rht_bucket(tbl, hash);
@@ -653,6 +662,7 @@ static __always_inline struct rhash_head *__rhashtable_lookup(
if (unlikely(tbl))
goto restart;
+out:
return NULL;
}
@@ -768,16 +778,19 @@ static __always_inline void *__rhashtable_insert_fast(
};
struct rhash_lock_head __rcu **bkt;
struct rhash_head __rcu **pprev;
+ void *data = ERR_PTR(-ESTALE);
struct bucket_table *tbl;
struct rhash_head *head;
unsigned long flags;
unsigned int hash;
int elasticity;
- void *data;
rcu_read_lock();
tbl = rht_dereference_rcu(ht->tbl, ht);
+ if (!tbl)
+ goto out;
+
hash = rht_head_hashfn(ht, tbl, obj, params);
elasticity = RHT_ELASTICITY;
bkt = rht_bucket_insert(ht, tbl, hash);
@@ -1136,11 +1149,13 @@ static __always_inline int __rhashtable_remove_fast(
const struct rhashtable_params params, bool rhlist)
{
struct bucket_table *tbl;
- int err;
+ int err = -ENOENT;
rcu_read_lock();
tbl = rht_dereference_rcu(ht->tbl, ht);
+ if (!tbl)
+ goto out;
/* Because we have already taken (and released) the bucket
* lock in old_tbl, if we find that future_tbl is not yet
@@ -1152,6 +1167,7 @@ static __always_inline int __rhashtable_remove_fast(
(tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
;
+out:
rcu_read_unlock();
return err;
@@ -1271,11 +1287,13 @@ static __always_inline int rhashtable_replace_fast(
const struct rhashtable_params params)
{
struct bucket_table *tbl;
- int err;
+ int err = -ENOENT;
rcu_read_lock();
tbl = rht_dereference_rcu(ht->tbl, ht);
+ if (!tbl)
+ goto out;
/* Because we have already taken (and released) the bucket
* lock in old_tbl, if we find that future_tbl is not yet
@@ -1287,6 +1305,7 @@ static __always_inline int rhashtable_replace_fast(
(tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
;
+out:
rcu_read_unlock();
return err;
@@ -1340,4 +1359,19 @@ static inline void rhltable_destroy(struct rhltable *hlt)
rhltable_free_and_destroy(hlt, NULL, NULL);
}
+/**
+ * rhltable_flush_and_free - unlink and free all elements in the hash list table
+ * @hlt: the hash list table to destroy
+ * @free_fn: callback to release resources of element
+ * @arg: pointer passed to free_fn
+ *
+ * See documentation for rhashtable_flush_and_free.
+ */
+static inline void rhltable_flush_and_free(struct rhltable *hlt,
+ void (*free_fn)(void *ptr,
+ void *arg),
+ void *arg)
+{
+ rhashtable_flush_and_free(&hlt->ht, free_fn, arg);
+}
#endif /* _LINUX_RHASHTABLE_H */
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 500c45cd1304..7b33dd046f67 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -350,6 +350,8 @@ static int rhashtable_rehash_table(struct rhashtable *ht)
rcu_assign_pointer(ht->tbl, new_tbl);
spin_lock(&ht->lock);
+ old_tbl->dying = true;
+
list_for_each_entry(walker, &old_tbl->walkers, list)
walker->tbl = NULL;
@@ -357,8 +359,8 @@ static int rhashtable_rehash_table(struct rhashtable *ht)
* table, and thus no references to the old table will
* remain.
* We do this inside the locked region so that
- * rhashtable_walk_stop() can use rcu_head_after_call_rcu()
- * to check if it should not re-link the table.
+ * rhashtable_walk_stop() can check tbl->dying before it
+ * re-links the table.
*/
call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
spin_unlock(&ht->lock);
@@ -434,6 +436,9 @@ static void rht_deferred_worker(struct work_struct *work)
mutex_lock(&ht->mutex);
tbl = rht_dereference(ht->tbl, ht);
+ if (!tbl)
+ goto out;
+
tbl = rhashtable_last_table(ht, tbl);
if (rht_grow_above_75(ht, tbl))
@@ -450,18 +455,11 @@ static void rht_deferred_worker(struct work_struct *work)
err = err ?: nerr;
}
- mutex_unlock(&ht->mutex);
-
- /*
- * Re-arm via @run_work, not @run_irq_work.
- * rhashtable_free_and_destroy() drains async work as irq_work_sync()
- * followed by cancel_work_sync(). If this site queued irq_work while
- * cancel_work_sync() was waiting for us, irq_work_sync() would already
- * have returned and the stale irq_work could fire post-teardown.
- * cancel_work_sync() natively handles self-requeue on @run_work.
- */
if (err)
- schedule_work(&ht->run_work);
+ irq_work_queue(&ht->run_irq_work);
+
+out:
+ mutex_unlock(&ht->mutex);
}
/*
@@ -488,6 +486,8 @@ static int rhashtable_insert_rehash(struct rhashtable *ht,
int err;
old_tbl = rht_dereference_rcu(ht->tbl, ht);
+ if (!old_tbl)
+ return -EAGAIN;
size = tbl->size;
@@ -635,6 +635,8 @@ static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
void *data;
new_tbl = rcu_dereference(ht->tbl);
+ if (!new_tbl)
+ return ERR_PTR(-ESTALE);
do {
tbl = new_tbl;
@@ -779,6 +781,8 @@ void *rhashtable_next_key(struct rhashtable *ht, const void *prev_key)
return ERR_PTR(-EOPNOTSUPP);
tbl = rht_dereference_rcu(ht->tbl, ht);
+ if (!tbl)
+ return NULL;
do {
he = __rhashtable_next_in_table(ht, tbl, prev_key);
if (!IS_ERR_OR_NULL(he))
@@ -820,12 +824,13 @@ void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)
iter->p = NULL;
iter->slot = 0;
iter->skip = 0;
- iter->end_of_table = 0;
spin_lock(&ht->lock);
iter->walker.tbl =
rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));
- list_add(&iter->walker.list, &iter->walker.tbl->walkers);
+ if (iter->walker.tbl)
+ list_add(&iter->walker.list, &iter->walker.tbl->walkers);
+ iter->end_of_table = !iter->walker.tbl;
spin_unlock(&ht->lock);
}
EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
@@ -883,6 +888,10 @@ int rhashtable_walk_start_check(struct rhashtable_iter *iter)
iter->slot = 0;
iter->skip = 0;
iter->p = NULL;
+ if (!iter->walker.tbl) {
+ iter->end_of_table = true;
+ return 0;
+ }
return -EAGAIN;
}
@@ -1091,7 +1100,7 @@ void rhashtable_walk_stop(struct rhashtable_iter *iter)
ht = iter->ht;
spin_lock(&ht->lock);
- if (rcu_head_after_call_rcu(&tbl->rcu, bucket_table_free_rcu))
+ if (tbl->dying)
/* This bucket table is being freed, don't re-link it. */
iter->walker.tbl = NULL;
else
@@ -1223,45 +1232,12 @@ static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,
} while (list);
}
-/**
- * rhashtable_free_and_destroy - free elements and destroy hash table
- * @ht: the hash table to destroy
- * @free_fn: callback to release resources of element
- * @arg: pointer passed to free_fn
- *
- * Stops an eventual async resize. If defined, invokes free_fn for each
- * element to releasal resources. Please note that RCU protected
- * readers may still be accessing the elements. Releasing of resources
- * must occur in a compatible manner. Then frees the bucket array.
- *
- * This function will eventually sleep to wait for an async resize
- * to complete. The caller is responsible that no further write operations
- * occurs in parallel.
- *
- * After cancel_work_sync() has returned, the deferred rehash worker is
- * quiesced and, per the contract above, no other concurrent access to the
- * rhashtable is possible. The tables are therefore owned exclusively by
- * this function and can be walked without ht->mutex held.
- */
-void rhashtable_free_and_destroy(struct rhashtable *ht,
- void (*free_fn)(void *ptr, void *arg),
- void *arg)
+static void rhashtable_free(struct rhashtable *ht, struct bucket_table *tbl,
+ void (*free_fn)(void *ptr, void *arg), void *arg)
{
- struct bucket_table *tbl, *next_tbl;
+ struct bucket_table *next_tbl;
unsigned int i;
- irq_work_sync(&ht->run_irq_work);
- cancel_work_sync(&ht->run_work);
-
- /*
- * Do NOT take ht->mutex here. The rehash worker establishes
- * ht->mutex -> fs_reclaim via GFP_KERNEL bucket allocation under
- * the mutex; callers on the reclaim path (e.g. simple_xattr_ht_free()
- * from evict() under the dcache shrinker for shmem/kernfs/pidfs
- * inodes) would otherwise close a circular dependency
- * fs_reclaim -> ht->mutex.
- */
- tbl = rcu_dereference_raw(ht->tbl);
restart:
if (free_fn) {
for (i = 0; i < tbl->size; i++) {
@@ -1286,6 +1262,36 @@ void rhashtable_free_and_destroy(struct rhashtable *ht,
goto restart;
}
}
+
+/**
+ * rhashtable_free_and_destroy - free elements and destroy hash table
+ * @ht: the hash table to destroy
+ * @free_fn: callback to release resources of element
+ * @arg: pointer passed to free_fn
+ *
+ * Stops an eventual async resize. If defined, invokes free_fn for each
+ * element to releasal resources. Please note that RCU protected
+ * readers may still be accessing the elements. Releasing of resources
+ * must occur in a compatible manner. Then frees the bucket array.
+ *
+ * This function will eventually sleep to wait for an async resize
+ * to complete. The caller is responsible that no further write operations
+ * occurs in parallel.
+ *
+ * After disable_work_sync() has returned, the deferred rehash worker is
+ * quiesced and, per the contract above, no other concurrent access to the
+ * rhashtable is possible. The tables are therefore owned exclusively by
+ * this function and can be walked without ht->mutex held.
+ */
+void rhashtable_free_and_destroy(struct rhashtable *ht,
+ void (*free_fn)(void *ptr, void *arg),
+ void *arg)
+{
+ disable_work_sync(&ht->run_work);
+ irq_work_sync(&ht->run_irq_work);
+
+ rhashtable_free(ht, rcu_dereference_raw(ht->tbl), free_fn, arg);
+}
EXPORT_SYMBOL_GPL(rhashtable_free_and_destroy);
void rhashtable_destroy(struct rhashtable *ht)
@@ -1362,3 +1368,79 @@ struct rhash_lock_head __rcu **rht_bucket_nested_insert(
}
EXPORT_SYMBOL_GPL(rht_bucket_nested_insert);
+
+/**
+ * rhashtable_flush_and_free - detach and discard all current elements
+ * @ht: the hash table to flush
+ * @free_fn: callback to release resources of an element, may be %NULL
+ * @arg: pointer passed to free_fn
+ *
+ * Swaps the bucket table backing @ht for a new, empty table.
+ *
+ * The detached table is then walked and every element found is
+ * unlinked, and, if @free_fn is given, handed to it for release.
+ *
+ * Unlike rhashtable_destroy(), @ht is left fully initialized and may
+ * continue to be used for lookups, insertions, and removals.
+ *
+ * This function may sleep, it cannot be called from atomic context or
+ * RCU read-side critical sections.
+ *
+ * The caller must not make concurrent rhashtable_flush_and_free calls.
+ * That is, a subsequent call can only be made once the first call has
+ * returned.
+ */
+void rhashtable_flush_and_free(struct rhashtable *ht,
+ void (*free_fn)(void *ptr, void *arg),
+ void *arg)
+{
+ struct bucket_table *tbl, *old_tbl, *new_tbl;
+ struct rhashtable_walker *walker;
+
+ new_tbl = bucket_table_alloc(ht, rounded_hashtable_size(&ht->p),
+ GFP_KERNEL);
+ if (!new_tbl)
+ new_tbl = bucket_table_alloc(ht, ht->p.min_size,
+ GFP_KERNEL | __GFP_NOFAIL);
+
+ mutex_lock(&ht->mutex);
+ old_tbl = rht_dereference(ht->tbl, ht);
+ RCU_INIT_POINTER(ht->tbl, NULL);
+ mutex_unlock(&ht->mutex);
+
+ /* Wait for insertions/removals on the old ht->tbl to complete. */
+ synchronize_rcu();
+
+ /* Cancel resizes/rehashes. */
+ irq_work_sync(&ht->run_irq_work);
+ cancel_work_sync(&ht->run_work);
+
+ atomic_set(&ht->nelems, 0);
+
+ /* No need for mutex as rehashes have all stopped. */
+ rcu_assign_pointer(ht->tbl, new_tbl);
+
+ /* Detach walkers from the old hash table. */
+ tbl = old_tbl;
+ spin_lock(&ht->lock);
+ do {
+ tbl->dying = true;
+ list_for_each_entry(walker, &tbl->walkers, list) {
+ struct rhashtable_iter *iter = container_of(
+ walker, struct rhashtable_iter, walker);
+
+ walker->tbl = NULL;
+ iter->end_of_table = true;
+ iter->p = NULL;
+ }
+
+ tbl = rcu_dereference_raw(tbl->future_tbl);
+ } while (tbl);
+ spin_unlock(&ht->lock);
+
+ /* Wait for walkers on old table to complete. */
+ synchronize_rcu();
+
+ rhashtable_free(ht, old_tbl, free_fn, arg);
+}
+EXPORT_SYMBOL_GPL(rhashtable_flush_and_free);
--
2.56.0
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nf-next v8 2/6] netfilter: ipset: add rhashtable boilerplate stubs
2026-11-11 10:11 [PATCH nf-next v8 0/6] ipset: replace internal hash table with rhashtable Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 1/6] rhashtable: Add rhashtable_flush_and_free helper Florian Westphal
@ 2026-11-11 10:11 ` Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 3/6] netfilter: ipset: replace internal hash table with rhashtable Florian Westphal
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Florian Westphal @ 2026-11-11 10:11 UTC (permalink / raw)
To: netfilter-devel
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.
Signed-off-by: Florian Westphal <fw@strlen.de>
---
unchanged.
net/netfilter/ipset/ip_set_hash_gen.h | 114 ++++++++++++++++++++++++--
1 file changed, 109 insertions(+), 5 deletions(-)
diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
index 80ca523f304b..a3f6c0aa47f7 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,62 @@ 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 */
+
+ /* element data; must be last. extensions follow. */
+ struct mtype_elem elem __aligned(__alignof__(u64));
+};
+
+/* 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),
+ .key_offset = offsetof(struct mtype_rht_elem, elem),
+ .hashfn = mtype_rht_hashfn,
+ .obj_hashfn = mtype_rht_obj_hashfn,
+ .obj_cmpfn = mtype_rht_cmpfn,
+ .key_len = HKEY_DATALEN,
+};
+
#define HKEY(data, initval, htable_bits) \
({ \
const u32 *__k = (const u32 *)data; \
@@ -313,6 +385,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 +555,19 @@ 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 mtype_rht_elem *e = ptr;
+ struct ip_set *set = arg;
+
+ rcu_read_lock();
+ ip_set_ext_destroy(set, &e->elem);
+ kfree_rcu(e, rcu);
+ rcu_read_unlock();
+}
+
/* Calculate the actual memory size of the set data */
static size_t
mtype_ahash_memsize(const struct htype *h, const struct htable *t)
@@ -586,6 +672,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);
@@ -1652,6 +1740,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;
@@ -1668,6 +1757,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",
@@ -1749,15 +1839,27 @@ 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;
+ /* 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.
@@ -1765,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;
@@ -1855,6 +1957,8 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set,
#endif
free_t:
ip_set_free(t);
+free_rht:
+ rhashtable_destroy(&h->ht);
free_h:
kfree(h);
return -ENOMEM;
--
2.56.0
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nf-next v8 3/6] netfilter: ipset: replace internal hash table with rhashtable
2026-11-11 10:11 [PATCH nf-next v8 0/6] ipset: replace internal hash table with rhashtable Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 1/6] rhashtable: Add rhashtable_flush_and_free helper Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 2/6] netfilter: ipset: add rhashtable boilerplate stubs Florian Westphal
@ 2026-11-11 10:11 ` Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 4/6] netfilter: ipset: also report mem size for cidr storage to userspace Florian Westphal
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Florian Westphal @ 2026-11-11 10:11 UTC (permalink / raw)
To: netfilter-devel
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 later.
Forced GC when set is full is removed: It is too expensive to do from
packet path insertions. Users can either enable FORCEADD or decrease GC
frequency. In case there is a requirement we could later re-add forced
GC when add request comes from userspace or add a 'fast gc' similar to
FORCEADD, where we probe a few random slots for expired elements rather
than doing a long walk in softirq context.
FORCEADD and MULTI hash type (netiface type) support is removed here to
reduce diff size. Both are added back later in the same series.
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.
Followup patch should also mark such dumps as interrupted so userspace
can retry, but this problem is not limited to ipset.
Several left-overs from the old implementation remain:
- data_next stubs (remaining caller is dead code needed
to avoid many 'defined but not used' compiler errors from hash
types)
- region locking (which is more of a misnomer now: it just tells
the ipset core that it should not lock the set)
- resize callback and resize checks in ipset core (hash types were
the only users).
These will be addressed in a followup series to avoid making the diff
even larger.
Joint work with Jozsef Kadlecisk.
Signed-off-by: Florian Westphal <fw@strlen.de>
---
v8:
- add 'exist-can-return-0-when racing-with-packet-path-and-thats-ok' comment
- add container struct for the rht walk iterator, it will be extended
in patch 5 / multi support
- re-indent the dump function, it avoids re-indendation of the
code in patch 5, end result is the same.
net/netfilter/ipset/ip_set_hash_gen.h | 1382 +++++++------------------
1 file changed, 396 insertions(+), 986 deletions(-)
diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
index a3f6c0aa47f7..8ac1b0f04856 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,19 @@
#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))
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 +66,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])
@@ -206,6 +123,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
@@ -216,8 +134,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
@@ -228,23 +144,22 @@ 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_new_elem
+#undef mtype_add_replace_old
#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_list_iter
+#undef mtype_rht_size
#undef mtype_head
#undef mtype_list
#undef mtype_gc_do
@@ -255,7 +170,6 @@ static const union nf_inet_addr zeromask = {};
#undef mtype_data_match
#undef htype
-#undef HKEY
#define mtype_data_equal IPSET_TOKEN(MTYPE, _data_equal)
#ifdef IP_SET_HASH_WITH_NETS
@@ -271,9 +185,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)
@@ -284,23 +195,21 @@ 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_new_elem IPSET_TOKEN(MTYPE, _new_elem)
+#define mtype_add_replace_old IPSET_TOKEN(MTYPE, _add_replace_old)
#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_list_iter IPSET_TOKEN(MTYPE, _list_iter)
+#define mtype_rht_size IPSET_TOKEN(MTYPE, _rht_size)
#define mtype_head IPSET_TOKEN(MTYPE, _head)
#define mtype_list IPSET_TOKEN(MTYPE, _list)
#define mtype_gc_do IPSET_TOKEN(MTYPE, _gc_do)
@@ -372,28 +281,18 @@ static const struct rhashtable_params mtype_rht_params = {
.key_len = HKEY_DATALEN,
};
-#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 */
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 */
- 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 */
@@ -404,15 +303,15 @@ struct htype {
struct mtype_elem next; /* temporary storage for uadd */
};
-/* 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 */
-};
+#define ipset_hash_elem_destroy_free(set, e) do { \
+ typeof(set) __set = (set); \
+ typeof(e) __e = (e); \
+ mtype_del_cidr_all(__set, __set->data, &__e->elem); \
+ ip_set_ext_destroy(__set, &__e->elem); \
+ kfree_rcu(__e, rcu); \
+} while (0)
+
+#define ipset_hash_nelems(h) atomic_read(&(h)->ht.nelems)
#ifdef IP_SET_HASH_WITH_NETS
/**
@@ -563,105 +462,24 @@ mtype_flush_elem(void *ptr, void *arg)
struct ip_set *set = arg;
rcu_read_lock();
- ip_set_ext_destroy(set, &e->elem);
- kfree_rcu(e, rcu);
+ ipset_hash_elem_destroy_free(set, e);
rcu_read_unlock();
}
-/* 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 */
+/**
+ * mtype_flush() - Flush a hash set type by destroying all elements.
+ * @set: Pointer to the ip_set.
+ *
+ * Because other CPUs may concurrently insert new entries into the table
+ * while flush is in progress, there is no guarantee that the table will
+ * be empty upon return.
+ */
static void
mtype_flush(struct ip_set *set)
{
struct htype *h = set->data;
-#ifdef IP_SET_HASH_WITH_NETS
- struct net_prefixes *nets;
-#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++) {
- u8 j;
-
- spin_lock_bh(&set->lock);
- nets = ipset_dereference_nfnl(h->rnets[i]);
- write_seqcount_begin(&nets->seq);
- for (j = 0; j < nets->len; j++)
- WRITE_ONCE(nets->nets[j], (struct net_prefix){});
- write_seqcount_end(&nets->seq);
- spin_unlock_bh(&set->lock);
- }
-#endif
-}
-
-/* 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;
- 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);
- }
-
-#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_flush_and_free(&h->ht, mtype_flush_elem, set);
}
/* Destroy a hash type of set */
@@ -669,16 +487,16 @@ 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
rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set);
- 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;
@@ -690,7 +508,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)
@@ -702,70 +519,51 @@ mtype_same_set(const struct ip_set *a, const struct ip_set *b)
a->extensions == b->extensions;
}
+/* Periodically drop and reacquire the rhashtable walk @hti so a large
+ * table doesn't hog the CPU. @seen counts objects seen since the last
+ * reacquire. Evaluates to true if the walk was stopped, in which case
+ * the caller must 'goto restart' to resume it.
+ *
+ * No per-type renaming needed: this has no linkage, so it is safe to
+ * define once even though this header is included multiple times per
+ * translation unit.
+ */
+#define mtype_gc_resched(hti, seen) \
+ ((seen)++ > 128 && need_resched() && \
+ (rhashtable_walk_stop(hti), cond_resched(), true))
+
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)))
- 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++;
- }
- 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. */
+ struct htype *h = set->data;
+ struct rhashtable_iter hti;
+ struct mtype_rht_elem *e;
+ unsigned int seen;
+
+ rhashtable_walk_enter(&h->ht, &hti);
+restart:
+ seen = 0;
+ rhashtable_walk_start(&hti);
+
+ while ((e = rhashtable_walk_next(&hti))) {
+ if (IS_ERR(e)) {
+ if (PTR_ERR(e) == -EAGAIN)
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);
+ break;
}
+
+ if (ip_set_timeout_expired(ext_timeout(&e->elem, set)) &&
+ rhashtable_remove_fast(&h->ht, &e->node, mtype_rht_params) == 0)
+ ipset_hash_elem_destroy_free(set, e);
+
+ /* stop+start can miss entries (we might have unlinked the
+ * element). This is harmless.
+ */
+ if (mtype_gc_resched(&hti, seen))
+ goto restart;
}
- spin_unlock_bh(&t->hregion[r].lock);
+ rhashtable_walk_stop(&hti);
+ rhashtable_walk_exit(&hti);
}
static void
@@ -773,40 +571,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
@@ -825,248 +601,151 @@ 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);
+/* 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)
+{
+ const struct htype *h = set->data;
+
+ /* Do GC to collect expired elements now so that the reported
+ * element count doesn't include expired elements.
+ */
+ if (SET_WITH_TIMEOUT(set))
+ mtype_gc_do(set);
-/* 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.
+ *elements = ipset_hash_nelems(h);
+ *ext_size = *elements *
+ (offsetof(struct mtype_rht_elem, elem) + set->dsize);
+}
+
+/**
+ * mtype_new_elem() - allocate and initialize a replacement/new element
+ * @set: Pointer to the ip_set
+ * @h: Pointer to the htype
+ * @d: Element data to copy in
+ * @ext: Extensions to initialize from
+ * @flags: Add flags (IPSET_FLAG_*)
+ * @old: The element we're replacing (can be NULL)
+ * @flag_exist: Whether the request carried IPSET_FLAG_EXIST
+ *
+ * allocates the element and initializes its data, cidr bookkeeping and
+ * extensions.
+ *
+ * The caller still has to link the returned element into the hash.
+ *
+ * Return: the new element, or PTR_ERR on failure.
*/
-static int
-mtype_resize(struct ip_set *set, bool retried)
+static struct mtype_rht_elem *
+mtype_new_elem(struct ip_set *set, struct htype *h, const struct mtype_elem *d,
+ const struct ip_set_ext *ext, u32 flags,
+ const struct mtype_rht_elem *old, bool flag_exist)
{
- struct htype *h = set->data;
- struct htable *t, *orig;
- u8 pos, htable_bits;
- size_t hsize, dsize = set->dsize;
+ bool flag_replace = !!old;
+ struct mtype_rht_elem *e;
#ifdef IP_SET_HASH_WITH_NETS
- u8 flags;
- struct mtype_elem *tmp;
+ int i, ret;
#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
- }
+ if (flag_replace && !flag_exist)
+ return ERR_PTR(-EEXIST);
+
+ if (!flag_replace && ipset_hash_nelems(h) >= h->maxelem) {
+ /* The upperlimit is not a hard ceiling, parallel insert
+ * allows overshoot: either client observes the old
+ * 'under limit' value, both increment. Not worth the
+ * effort to 'atomic_inc_return+decrement on error'.
+ *
+ * We also don't call mtype_gc_do(). If called from kernel,
+ * that's too expensive/costly, when called from userspace,
+ * its pretty much pointless, userspace can just retry once
+ * gc has fired, resp. decrease the gc interval.
+ */
+ if (1) {
+ if (net_ratelimit())
+ pr_warn("Set %s is full, maxelem %u reached\n",
+ set->name, h->maxelem);
+ return ERR_PTR(-EMFILE);
}
- rcu_read_unlock_bh();
}
- /* There can't be any other writer. */
- rcu_assign_pointer(h->table, t);
+ e = kzalloc(offsetof(struct mtype_rht_elem, elem) + set->dsize,
+ GFP_ATOMIC);
+ if (!e)
+ return ERR_PTR(-ENOMEM);
- /* Give time to other readers of the set */
- synchronize_rcu();
+ memcpy(&e->elem, d, sizeof(struct mtype_elem));
- 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.
- */
- 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);
+#ifdef IP_SET_HASH_WITH_NETS
+ 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);
+ return ERR_PTR(ret);
}
- 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);
+ mtype_data_set_flags(&e->elem, flags);
#endif
- return ret;
+ if (SET_WITH_COUNTER(set))
+ ip_set_init_counter(ext_counter(&e->elem, set), ext);
+ if (SET_WITH_COMMENT(set)) {
+ if (!ext->target) {
+ ip_set_init_comment(set, ext_comment(&e->elem, set), ext);
+ } else if (old) {
+ /* Kernel packet path: @ext carries no comment of its
+ * own, so duplicate whatever @old currently has.
+ *
+ * We can only do this safely BEFORE e is linked into
+ * the table, or we risk adding an extension to an element
+ * already pending via kfree_rcu.
+ */
+ struct ip_set_comment_rcu *old_c =
+ rcu_dereference(ext_comment(&old->elem, set)->c);
-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;
+ if (old_c) {
+ struct ip_set_ext tmp = *ext;
- /* 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);
+ tmp.comment = old_c->str;
+ ip_set_init_comment(set, ext_comment(&e->elem, set), &tmp);
+ }
+ }
}
- spin_unlock_bh(&set->lock);
- goto out;
+ if (SET_WITH_SKBINFO(set))
+ ip_set_init_skbinfo(ext_skbinfo(&e->elem, set), ext);
+ if (SET_WITH_TIMEOUT(set))
+ ip_set_timeout_set(ext_timeout(&e->elem, set), ext->timeout);
-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;
+ return e;
}
-/* Get the current number of elements and ext_size in the set */
+/* Update the new element's counters with the replaced one, unless
+ * userspace gave specific start values. @old has already been unlinked
+ * from the table, but may still be visible to other CPUs, so this
+ * is best-effort only. Always frees @old and undoes its mtype_add_cidr().
+ */
static void
-mtype_ext_size(struct ip_set *set, u32 *elements, size_t *ext_size)
+mtype_add_replace_old(struct ip_set *set, struct htype *h,
+ const struct mtype_elem *d, const struct ip_set_ext *ext,
+ struct mtype_rht_elem *e, struct mtype_rht_elem *old)
{
- 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;
+ if (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);
+
+ if (ext->packets == ULLONG_MAX)
+ atomic64_add(atomic64_read(&old_c->packets), &new_c->packets);
+ if (ext->bytes == ULLONG_MAX)
+ atomic64_add(atomic64_read(&old_c->bytes), &new_c->bytes);
}
+
+ ip_set_ext_destroy(set, &old->elem);
+ kfree_rcu(old, rcu);
+ mtype_del_cidr_all(set, h, d);
}
/* Add an element to a hash and update the internal counters when succeeded,
@@ -1076,299 +755,96 @@ 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;
- 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;
+ const struct mtype_elem *d = value;
+ struct htype *h = set->data;
+ struct mtype_rht_elem *e, *old;
+ int ret = 0;
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 = rhashtable_lookup(&h->ht, d, mtype_rht_params);
+ if (old && SET_ELEM_EXPIRED(set, &old->elem)) {
+ /* simple case: element is expired, same as old == NULL. */
+ if (rhashtable_remove_fast(&h->ht, &old->node,
+ mtype_rht_params) == 0)
+ ipset_hash_elem_destroy_free(set, old);
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;
- }
- ret = -IPSET_ERR_EXIST;
- goto unlock;
- }
- /* Reuse first timed out entry */
- if (SET_ELEM_EXPIRED(set, data) && j == -1) {
- j = i;
- reuse = true;
- }
- }
- 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--;
- }
- goto copy_data;
}
- 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);
+
+ e = mtype_new_elem(set, h, d, ext, flags, old, flag_exist);
+ if (IS_ERR(e)) {
+ ret = PTR_ERR(e);
+ 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:
-#ifdef IP_SET_HASH_WITH_NETS
- mtype_data_set_flags(data, flags);
-#endif
- if (SET_WITH_COUNTER(set))
- ip_set_init_counter(ext_counter(data, set), ext);
- if (SET_WITH_COMMENT(set) && !ext->target)
- ip_set_init_comment(set, ext_comment(data, 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 */
- 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);
+ if (old)
+ ret = rhashtable_replace_fast(&h->ht, &old->node, &e->node, mtype_rht_params);
+ else
+ ret = rhashtable_lookup_insert_key(&h->ht, d, &e->node, mtype_rht_params);
+
+ if (ret == -ENOENT && old) {
+ /* replace failed: maybe GC or concurrent mtype_del()
+ * reaped old element right now.
+ *
+ * Try once more with plain insert: Just like the initial
+ * rhashtable_lookup_insert_key() above the retry can lose
+ * to a second concurrent mtype_add() for the same key: ret
+ * becomes -EEXIST and is reported as success below when
+ * flag_exist is set. That is fine -- the element the
+ * caller asked to add is present either way, we just could
+ * not apply our extensions/comment. Not worth serializing
+ * the lookup+replace pair to avoid.
+ */
+ old = NULL;
+ ret = rhashtable_lookup_insert_key(&h->ht, d, &e->node, mtype_rht_params);
}
- 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);
+ if (ret) {
+ ip_set_ext_destroy(set, &e->elem);
+ kfree_rcu(e, rcu);
+ /* error: Undo mtype_add_cidr(). */
+ mtype_del_cidr_all(set, h, d);
}
- goto out;
+ if (ret == 0 && old)
+ mtype_add_replace_old(set, h, d, ext, e, old);
+
+ if (0) /* to be removed */
+ mtype_data_next(&h->next, d);
+out_rcu_unlock:
+ /* IPSET_ERR values cannot be used with ERR_PTR: IS_ERR_VALUE
+ * returns false for them, so translate those here.
+ */
+ if (ret == -EEXIST)
+ ret = flag_exist ? 0 : -IPSET_ERR_EXIST;
+ else if (ret == -EMFILE || ret == -E2BIG)
+ ret = -IPSET_ERR_HASH_FULL;
-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);
- }
+ 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.
- */
+ struct mtype_rht_elem *e;
+ int ret = -IPSET_ERR_EXIST;
+
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);
+ 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;
+ mtype_del_cidr_all(set, h, d);
+ ip_set_ext_destroy(set, &e->elem);
+ kfree_rcu(e, rcu);
+out_unlock:
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;
-
- 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);
- }
- 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);
- }
- return ret;
+ return ret ? -IPSET_ERR_EXIST : 0;
}
static int
@@ -1391,30 +867,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++) {
@@ -1434,38 +906,25 @@ 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)
- 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))
- continue;
- ret = mtype_data_match(data, ext, mext, set, flags);
+ e = rhashtable_lookup(&h->ht, d, mtype_rht_params);
+ if (e) {
+ 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
+ goto check_retry;
+ multi = false;
}
#if IPSET_NET_COUNT == 2
}
#endif
}
ret = 0;
-unlock:
+check_retry:
if (read_seqcount_retry(&nets0->seq, seq0))
goto retry;
#if IPSET_NET_COUNT == 2
if (read_seqcount_retry(&nets1->seq, seq1))
goto retry;
#endif
- rcu_read_unlock_bh();
return ret;
}
#endif
@@ -1476,16 +935,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
@@ -1499,68 +956,34 @@ 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;
+ e = rhashtable_lookup(&h->ht, d, mtype_rht_params);
+ if (!e)
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)
- goto out;
- }
+
+ ret = mtype_data_match(&e->elem, ext, mext, set, flags);
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;
@@ -1586,7 +1009,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;
@@ -1604,25 +1027,31 @@ mtype_head(struct ip_set *set, struct sk_buff *skb)
return -EMSGSIZE;
}
-/* Make possible to run dumping parallel with resizing */
+/**
+ * struct mtype_list_iter - per-dump state, stored via IPSET_CB_PRIVATE
+ * @hti: rhashtable walk cursor over @htype.ht
+ */
+struct mtype_list_iter {
+ struct rhashtable_iter hti;
+};
+
+/* Manage the rhashtable_iter lifetime for dump operations */
static void
mtype_uref(struct ip_set *set, struct netlink_callback *cb, bool start)
{
+ struct mtype_list_iter *iter;
struct htype *h = set->data;
- struct htable *t;
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);
+ iter = kzalloc_obj(*iter, GFP_KERNEL_ACCOUNT);
+ if (iter)
+ rhashtable_walk_enter(&h->ht, &iter->hti);
+ cb->args[IPSET_CB_PRIVATE] = (unsigned long)iter;
+ } else {
+ iter = (struct mtype_list_iter *)cb->args[IPSET_CB_PRIVATE];
+ if (iter) {
+ rhashtable_walk_exit(&iter->hti);
+ kfree(iter);
}
cb->args[IPSET_CB_PRIVATE] = 0;
}
@@ -1633,77 +1062,82 @@ static int
mtype_list(const struct ip_set *set,
struct sk_buff *skb, struct netlink_callback *cb)
{
- const struct htable *t;
- 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;
+ struct mtype_list_iter *iter =
+ (struct mtype_list_iter *)cb->args[IPSET_CB_PRIVATE];
+ struct rhashtable_iter *hti = iter ? &iter->hti : NULL;
+ struct nlattr *atd;
+ u32 emitted = 0;
+ int ret = 0;
+
+ if (!hti)
+ return -ENOMEM;
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))
- continue;
- pr_debug("list hash %lu hbucket %p i %u, data %p\n",
- cb->args[IPSET_CB_ARG0], n, i, e);
+ rhashtable_walk_start(hti);
+ {
+ struct mtype_rht_elem *e, *peeked;
+ struct nlattr *nested;
+ void *incomplete;
+
+ while ((e = rhashtable_walk_peek(hti))) {
+ if (IS_ERR(e)) {
+ if (PTR_ERR(e) == -EAGAIN)
+ continue;
+ 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) {
- if (cb->args[IPSET_CB_ARG0] == first) {
- nla_nest_cancel(skb, atd);
- ret = -EMSGSIZE;
- goto out;
- }
- goto nla_put_failure;
+ 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;
}
- 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);
+ 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
@@ -1729,7 +1163,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,
@@ -1740,12 +1174,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;
@@ -1753,12 +1186,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");
@@ -1829,7 +1261,12 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set,
#endif
if (tb[IPSET_ATTR_HASHSIZE]) {
+ /* Not used anymore, just for backwards compat, old hash
+ * implementation used to -ENOMEM on too large hashsize.
+ */
hashsize = ip_set_get_h32(tb[IPSET_ATTR_HASHSIZE]);
+ if (hashsize > INT_MAX)
+ return -ENOMEM;
if (hashsize < IPSET_MIMINAL_HASHSIZE)
hashsize = IPSET_MIMINAL_HASHSIZE;
}
@@ -1860,36 +1297,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;
@@ -1898,10 +1318,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]);
@@ -1912,10 +1330,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
@@ -1945,23 +1360,18 @@ 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:
rhashtable_destroy(&h->ht);
+#endif
free_h:
kfree(h);
- return -ENOMEM;
+ return err ? err : -ENOMEM;
}
#endif /* IP_SET_EMIT_CREATE */
--
2.56.0
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nf-next v8 4/6] netfilter: ipset: also report mem size for cidr storage to userspace
2026-11-11 10:11 [PATCH nf-next v8 0/6] ipset: replace internal hash table with rhashtable Florian Westphal
` (2 preceding siblings ...)
2026-11-11 10:11 ` [PATCH nf-next v8 3/6] netfilter: ipset: replace internal hash table with rhashtable Florian Westphal
@ 2026-11-11 10:11 ` Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 5/6] netfilter: ipset: re-add IP_SET_HASH_WITH_MULTI support Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 6/6] netfilter: ipset: re-add forceadd support Florian Westphal
5 siblings, 0 replies; 7+ messages in thread
From: Florian Westphal @ 2026-11-11 10:11 UTC (permalink / raw)
To: netfilter-devel
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>
---
No changes.
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 8ac1b0f04856..e7f2e584a7a5 100644
--- a/net/netfilter/ipset/ip_set_hash_gen.h
+++ b/net/netfilter/ipset/ip_set_hash_gen.h
@@ -616,6 +616,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
}
/**
--
2.56.0
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nf-next v8 5/6] netfilter: ipset: re-add IP_SET_HASH_WITH_MULTI support
2026-11-11 10:11 [PATCH nf-next v8 0/6] ipset: replace internal hash table with rhashtable Florian Westphal
` (3 preceding siblings ...)
2026-11-11 10:11 ` [PATCH nf-next v8 4/6] netfilter: ipset: also report mem size for cidr storage to userspace Florian Westphal
@ 2026-11-11 10:11 ` Florian Westphal
2026-11-11 10:11 ` [PATCH nf-next v8 6/6] netfilter: ipset: re-add forceadd support Florian Westphal
5 siblings, 0 replies; 7+ messages in thread
From: Florian Westphal @ 2026-11-11 10:11 UTC (permalink / raw)
To: netfilter-devel
Reimplement hash:net,iface set type on top of rhashtable.
A net/cidr/physdev key maps to one struct mtype_group, which owns a small
RCU-protected list of the actual elements.
Each element holds one distinct interface/wildcard value that shares
the key with that of the group.
An earlier attempt uses rhltable, but hash:net,iface requires control
of the insertion order.
mtype_group_find() and mtype_group_test() give each normal elements
priority over a wildcard element explicitly via the mtype_data_isexact
hook, independent of list order:
- mtype_del() must not remove a wildcard element instead of
the specific element named in the request.
- mtype_test()/mtype_test_cidrs() must not shadow a more specific
(e.g. nomatch) element added earlier.
- mtype_add() with IPSET_FLAG_EXIST must not tear down an unrelated
wildcard element as a side effect of refreshing a specific
element sharing its key.
Element count is tracked explicitly via htype->nelems so account for
the elements and not thhe rhastable-inserted group heads.
The IPSET_GROUP_MAX_ENTRIES limit bounds the list length of group-attached
entries. This limit is not new. The original hash table implementation
had a AHASH_MAX_TUNED value of 64: this provided an implicit upper bound
of identical hash keys that could be inserted.
As chain list walk becomes expensive with increasing lengths, this
limit is kept as the new, explicit IPSET_GROUP_MAX_ENTRIES cap.
Signed-off-by: Florian Westphal <fw@strlen.de>
---
v7:
- check if group could be removed from rhashtable
to avoid interference from flush or gc.
- remove a few grp->dead checks, its required only
when adding an element to a group.
- fix a bug shared with old hashtable implementation:
there should be no difference between 'element is
expired' and 'element doesn't exist' when doing a
lookup.
- mtype_group_remove_elem no longer releases the
group spinlock
- reduce copypasted code
- dumper now stores key instead of a skip count.
Doesn't make much difference (group can be changed
while a dump is in progress), but it does avoid
skipping elements that were not dumped before.
net/netfilter/ipset/ip_set_hash_gen.h | 662 ++++++++++++++++++-
net/netfilter/ipset/ip_set_hash_ip.c | 6 +-
net/netfilter/ipset/ip_set_hash_ipmac.c | 6 +-
net/netfilter/ipset/ip_set_hash_ipmark.c | 6 +-
net/netfilter/ipset/ip_set_hash_ipport.c | 6 +-
net/netfilter/ipset/ip_set_hash_ipportip.c | 6 +-
net/netfilter/ipset/ip_set_hash_ipportnet.c | 6 +-
net/netfilter/ipset/ip_set_hash_mac.c | 3 +-
net/netfilter/ipset/ip_set_hash_net.c | 6 +-
net/netfilter/ipset/ip_set_hash_netiface.c | 74 ++-
net/netfilter/ipset/ip_set_hash_netnet.c | 6 +-
net/netfilter/ipset/ip_set_hash_netport.c | 6 +-
net/netfilter/ipset/ip_set_hash_netportnet.c | 6 +-
13 files changed, 725 insertions(+), 74 deletions(-)
diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
index e7f2e584a7a5..5c85f316a09a 100644
--- a/net/netfilter/ipset/ip_set_hash_gen.h
+++ b/net/netfilter/ipset/ip_set_hash_gen.h
@@ -134,12 +134,27 @@ static const union nf_inet_addr zeromask = {};
#undef mtype_data_next
#undef mtype_elem
+#undef mtype_data_isexact
+#undef mtype_data_isequal
+
#undef mtype_rht_elem
#undef mtype_rht_hashfn
#undef mtype_rht_obj_hashfn
#undef mtype_rht_cmpfn
#undef mtype_rht_params
+#undef mtype_group
+#undef mtype_group_rht_params
+#undef mtype_group_obj_hashfn
+#undef mtype_group_cmpfn
+#undef mtype_group_get_or_create
+#undef mtype_group_remove_elem
+#undef mtype_group_unlock
+#undef mtype_group_find
+#undef mtype_group_test
+#undef mtype_group_list
+#undef mtype_flush_group
+
#undef mtype_add_cidr
#undef mtype_del_cidr
#undef mtype_del_cidr_all
@@ -172,6 +187,11 @@ static const union nf_inet_addr zeromask = {};
#undef htype
#define mtype_data_equal IPSET_TOKEN(MTYPE, _data_equal)
+#ifdef IP_SET_HASH_WITH_MULTI
+#define mtype_key_equal IPSET_TOKEN(MTYPE, _key_equal)
+#define mtype_data_isexact IPSET_TOKEN(MTYPE, _data_isexact)
+#define mtype_data_isequal IPSET_TOKEN(MTYPE, _data_isequal)
+#endif
#ifdef IP_SET_HASH_WITH_NETS
#define mtype_do_data_match IPSET_TOKEN(MTYPE, _do_data_match)
#else
@@ -191,6 +211,20 @@ static const union nf_inet_addr zeromask = {};
#define mtype_rht_cmpfn IPSET_TOKEN(MTYPE, _rht_cmpfn)
#define mtype_rht_params IPSET_TOKEN(MTYPE, _rht_params)
+#ifdef IP_SET_HASH_WITH_MULTI
+#define mtype_group IPSET_TOKEN(MTYPE, _group)
+#define mtype_group_rht_params IPSET_TOKEN(MTYPE, _group_rht_params)
+#define mtype_group_obj_hashfn IPSET_TOKEN(MTYPE, _group_obj_hashfn)
+#define mtype_group_cmpfn IPSET_TOKEN(MTYPE, _group_cmpfn)
+#define mtype_group_get_or_create IPSET_TOKEN(MTYPE, _group_get_or_create)
+#define mtype_group_remove_elem IPSET_TOKEN(MTYPE, _group_remove_elem)
+#define mtype_group_unlock IPSET_TOKEN(MTYPE, _group_put)
+#define mtype_group_find IPSET_TOKEN(MTYPE, _group_find)
+#define mtype_group_test IPSET_TOKEN(MTYPE, _group_test)
+#define mtype_group_list IPSET_TOKEN(MTYPE, _group_list)
+#define mtype_flush_group IPSET_TOKEN(MTYPE, _flush_group)
+#endif
+
#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)
@@ -229,13 +263,48 @@ 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 hlist_node node; /* linked into the owning group's iface_list */
+#else
struct rhash_head node;
+#endif
struct rcu_head rcu; /* deferred free after removal */
/* element data; must be last. extensions follow. */
struct mtype_elem elem __aligned(__alignof__(u64));
};
+#ifdef IP_SET_HASH_WITH_MULTI
+/* Max number of interface-differentiated elements sharing one net/cidr/
+ * physdev key. Chain length is bounded so test/add/del stay cheap.
+ */
+#define IPSET_GROUP_MAX_ENTRIES 64
+
+/**
+ * struct mtype_group - all elements sharing one net/cidr/physdev key
+ * @node: linkage in @htype.ht, keyed by @key via mtype_key_equal()
+ * @key: representative net/cidr/physdev key, used for hashing/lookup only
+ * @lock: protects @iface_list and @dead
+ * @dead: true once unlinked from @htype.ht; group is being freed
+ * @iface_list: RCU-protected list of mtype_rht_elem sharing @key
+ * @rcu: RCU head for deferred free
+ *
+ * hash:net,iface stores several elements under the same net/cidr/physdev
+ * key, differentiated by interface name (and, optionally, an interface
+ * name prefix via the wildcard flag). A group owns that small, bounded
+ * set of elements so lookups can apply iface-matching precedence (exact
+ * beats wildcard) without depending on list insertion order.
+ */
+struct mtype_group {
+ struct rhash_head node;
+ struct mtype_elem key;
+ spinlock_t lock;
+ bool dead;
+ struct hlist_head iface_list;
+ struct rcu_head rcu;
+};
+#endif
+
/* jhash of the lookup key */
static u32 mtype_rht_hashfn(const void *data, u32 len, u32 seed)
{
@@ -243,6 +312,7 @@ static u32 mtype_rht_hashfn(const void *data, u32 len, u32 seed)
return jhash2((const u32 *)data, HKEY_DATALEN / sizeof(u32), seed);
}
+#ifndef IP_SET_HASH_WITH_MULTI
/* jhash of an existing element object */
static u32 mtype_rht_obj_hashfn(const void *obj, u32 len, u32 seed)
{
@@ -266,10 +336,9 @@ 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;
- u32 multi = 0;
return !mtype_data_equal(&e->elem,
- (const struct mtype_elem *)arg->key, &multi);
+ (const struct mtype_elem *)arg->key);
}
static const struct rhashtable_params mtype_rht_params = {
@@ -280,10 +349,50 @@ static const struct rhashtable_params mtype_rht_params = {
.obj_cmpfn = mtype_rht_cmpfn,
.key_len = HKEY_DATALEN,
};
+#else /* IP_SET_HASH_WITH_MULTI */
+/* jhash of an existing group's representative key */
+static u32 mtype_group_obj_hashfn(const void *obj, u32 len, u32 seed)
+{
+ const struct mtype_group *grp = obj;
+#ifdef IP_SET_HASH_WITH_NETS
+ struct mtype_elem tmp;
+ u8 flags = 0;
+
+ memcpy(&tmp, &grp->key, HKEY_DATALEN);
+ mtype_data_reset_flags(&tmp, &flags);
+ return jhash2((const u32 *)&tmp, HKEY_DATALEN / sizeof(u32), seed);
+#else
+ return jhash2((const u32 *)&grp->key, HKEY_DATALEN / sizeof(u32), seed);
+#endif
+}
+
+/* 0 = key matches group (equal), non-zero = not equal. Only the narrow
+ * net/cidr/physdev key is compared: iface/wildcard differentiate elements
+ * *within* a group, not which group an element belongs to.
+ */
+static int mtype_group_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
+{
+ const struct mtype_group *grp = obj;
+
+ return !mtype_key_equal(&grp->key, (const struct mtype_elem *)arg->key);
+}
+
+static const struct rhashtable_params mtype_group_rht_params = {
+ .head_offset = offsetof(struct mtype_group, node),
+ .key_offset = offsetof(struct mtype_group, key),
+ .hashfn = mtype_rht_hashfn,
+ .obj_hashfn = mtype_group_obj_hashfn,
+ .obj_cmpfn = mtype_group_cmpfn,
+ .key_len = HKEY_DATALEN,
+};
+#endif /* IP_SET_HASH_WITH_MULTI */
/* The hash set type */
struct htype {
- struct rhashtable ht; /* the hash table */
+ struct rhashtable ht; /* the hash table: elements, or groups for "multi" */
+#ifdef IP_SET_HASH_WITH_MULTI
+ atomic_t nelems; /* total elements across all groups */
+#endif
struct net_prefixes __rcu *rnets[IPSET_NET_COUNT]; /* cidr prefixes */
struct htable_gc gc; /* gc workqueue */
u32 maxelem; /* max elements in the hash */
@@ -311,7 +420,11 @@ struct htype {
kfree_rcu(__e, rcu); \
} while (0)
+#ifdef IP_SET_HASH_WITH_MULTI
+#define ipset_hash_nelems(h) atomic_read(&(h)->nelems)
+#else
#define ipset_hash_nelems(h) atomic_read(&(h)->ht.nelems)
+#endif
#ifdef IP_SET_HASH_WITH_NETS
/**
@@ -454,6 +567,166 @@ mtype_del_cidr_all(struct ip_set *set, struct htype *h, const struct mtype_elem
#endif
}
+#ifdef IP_SET_HASH_WITH_MULTI
+/**
+ * mtype_group_get_or_create() - find or create the group for @d's key
+ * @h: Pointer to the htype
+ * @d: Element whose net/cidr/physdev key identifies the group
+ * @errp: Set to a negative errno when NULL is returned
+ *
+ * Return: the group with @grp->lock held (caller must unlock), or NULL
+ * with *@errp set.
+ */
+static struct mtype_group *
+mtype_group_get_or_create(struct htype *h, const struct mtype_elem *d, int *errp)
+ __cond_acquires(nonnull, &grp->lock)
+{
+ struct mtype_group *grp;
+ int err;
+
+retry:
+ grp = rhashtable_lookup(&h->ht, d, mtype_group_rht_params);
+ if (grp) {
+ spin_lock_bh(&grp->lock);
+
+ if (!grp->dead)
+ return grp;
+ /* Don't allow insertion into unreachable group:
+ * We lost the race with mtype_group_unlock(): by the
+ * time it released @grp->lock, @grp was already unlinked
+ * from h->ht, so a fresh lookup cannot find it again.
+ */
+ spin_unlock_bh(&grp->lock);
+ goto retry;
+ }
+
+ grp = kzalloc(sizeof(*grp), GFP_ATOMIC);
+ if (!grp) {
+ *errp = -ENOMEM;
+ return NULL;
+ }
+ INIT_HLIST_HEAD(&grp->iface_list);
+ spin_lock_init(&grp->lock);
+ memcpy(&grp->key, d, sizeof(grp->key));
+
+ spin_lock_bh(&grp->lock);
+ err = rhashtable_lookup_insert_key(&h->ht, d, &grp->node, mtype_group_rht_params);
+ if (err) {
+ spin_unlock_bh(&grp->lock);
+ kfree(grp);
+ if (err == -EEXIST) /* someone else created the group first */
+ goto retry;
+ *errp = err;
+ return NULL;
+ }
+ return grp;
+}
+
+/**
+ * mtype_group_remove_elem() - unlink @e from @grp and free @e
+ * @set: Pointer to the ip_set
+ * @h: Pointer to the htype
+ * @grp: Group owning @e, with @grp->lock held
+ * @e: Element to remove; must currently be linked into @grp->iface_list
+ */
+static void
+mtype_group_remove_elem(struct ip_set *set, struct htype *h,
+ struct mtype_group *grp, struct mtype_rht_elem *e)
+{
+ lockdep_assert_held(&grp->lock);
+
+ hlist_del_rcu(&e->node);
+ atomic_dec(&h->nelems);
+ ipset_hash_elem_destroy_free(set, e);
+}
+
+/**
+ * mtype_group_unlock() - release @grp->lock, freeing @grp if it ended up empty
+ * @h: Pointer to the htype
+ * @grp: Group to release, with @grp->lock held
+ *
+ * Call this instead of a bare spin_unlock_bh(&grp->lock) whenever @grp might
+ * have become empty; also call it from mtype_add() on error unwind when no
+ * new element was linked into @grp.
+ */
+static void
+mtype_group_unlock(struct htype *h, struct mtype_group *grp)
+ __releases(&grp->lock)
+{
+ bool release = false;
+
+ if (hlist_empty(&grp->iface_list) &&
+ rhashtable_remove_fast(&h->ht, &grp->node,
+ mtype_group_rht_params) == 0) {
+ grp->dead = true;
+ release = true;
+ }
+ spin_unlock_bh(&grp->lock);
+ if (release)
+ kfree_rcu(grp, rcu);
+}
+
+/**
+ * mtype_group_find() - pick the element a non-wildcard request affects
+ * @set: Pointer to the ip_set.
+ * @grp: Group to search, with @grp->lock held
+ * @d: Lookup key (net/cidr/physdev and interface)
+ *
+ * An exact (non-wildcard) element always takes priority over a wildcard
+ * element, independent of @grp's list order. Must be called with
+ * @grp->lock held: the result is only valid as long as the lock prevents
+ * a concurrent mtype_add() from linking a higher-priority element into
+ * @grp after this scan but before the caller acts on its result.
+ *
+ * Intentionally does not use mtype_data_isequal() (strict identity,
+ * including @d's wildcard flag): "ipset del" must be able to remove a
+ * wildcard element even if @d->wildcard is false.
+ *
+ * Return: the matching element, or NULL.
+ */
+static struct mtype_rht_elem *
+mtype_group_find(struct ip_set *set, struct mtype_group *grp, const struct mtype_elem *d)
+{
+ struct mtype_rht_elem *e, *best = NULL;
+
+ lockdep_assert_held(&grp->lock);
+
+ hlist_for_each_entry_rcu(e, &grp->iface_list, node) {
+ if (!mtype_data_equal(&e->elem, d) ||
+ SET_ELEM_EXPIRED(set, &e->elem))
+ continue;
+ if (mtype_data_isexact(&e->elem))
+ return e;
+ if (!best)
+ best = e;
+ }
+ return best;
+}
+#endif /* IP_SET_HASH_WITH_MULTI */
+
+#ifdef IP_SET_HASH_WITH_MULTI
+/* Free one group and all its elements: called by rhashtable_free_and_destroy
+ * and rhashtable_flush_and_free.
+ */
+static void
+mtype_flush_group(void *ptr, void *arg)
+{
+ struct mtype_group *grp = ptr;
+ struct ip_set *set = arg;
+ struct htype *h = set->data;
+ struct hlist_node *n;
+ struct mtype_rht_elem *e;
+
+ rcu_read_lock();
+ spin_lock_bh(&grp->lock);
+ hlist_for_each_entry_safe(e, n, &grp->iface_list, node)
+ mtype_group_remove_elem(set, h, grp, e);
+
+ spin_unlock_bh(&grp->lock);
+ rcu_read_unlock();
+ kfree_rcu(grp, rcu);
+}
+#else
/* Free one element: called by rhashtable_free_and_destroy */
static void
mtype_flush_elem(void *ptr, void *arg)
@@ -465,6 +738,7 @@ mtype_flush_elem(void *ptr, void *arg)
ipset_hash_elem_destroy_free(set, e);
rcu_read_unlock();
}
+#endif
/**
* mtype_flush() - Flush a hash set type by destroying all elements.
@@ -479,7 +753,11 @@ mtype_flush(struct ip_set *set)
{
struct htype *h = set->data;
+#ifdef IP_SET_HASH_WITH_MULTI
+ rhashtable_flush_and_free(&h->ht, mtype_flush_group, set);
+#else
rhashtable_flush_and_free(&h->ht, mtype_flush_elem, set);
+#endif
}
/* Destroy a hash type of set */
@@ -491,7 +769,12 @@ mtype_destroy(struct ip_set *set)
u32 i;
#endif
+#ifdef IP_SET_HASH_WITH_MULTI
+ rhashtable_free_and_destroy(&h->ht, mtype_flush_group, set);
+ DEBUG_NET_WARN_ON_ONCE(ipset_hash_nelems(h));
+#else
rhashtable_free_and_destroy(&h->ht, mtype_flush_elem, set);
+#endif
#ifdef IP_SET_HASH_WITH_NETS
for (i = 0; i < IPSET_NET_COUNT; i++)
@@ -545,23 +828,51 @@ mtype_gc_do(struct ip_set *set)
seen = 0;
rhashtable_walk_start(&hti);
- while ((e = rhashtable_walk_next(&hti))) {
- if (IS_ERR(e)) {
- if (PTR_ERR(e) == -EAGAIN)
- continue;
- break;
+#ifdef IP_SET_HASH_WITH_MULTI
+ {
+ struct mtype_group *grp;
+
+ while ((grp = rhashtable_walk_next(&hti))) {
+ struct hlist_node *n;
+
+ if (IS_ERR(grp)) {
+ if (PTR_ERR(grp) == -EAGAIN)
+ continue;
+ break;
+ }
+
+ spin_lock_bh(&grp->lock);
+ hlist_for_each_entry_safe(e, n, &grp->iface_list, node) {
+ if (ip_set_timeout_expired(ext_timeout(&e->elem, set)))
+ mtype_group_remove_elem(set, h, grp, e);
+ }
+ mtype_group_unlock(h, grp);
+
+ if (mtype_gc_resched(&hti, seen))
+ goto restart;
}
+ }
+#else
+ {
+ while ((e = rhashtable_walk_next(&hti))) {
+ if (IS_ERR(e)) {
+ if (PTR_ERR(e) == -EAGAIN)
+ continue;
+ break;
+ }
- if (ip_set_timeout_expired(ext_timeout(&e->elem, set)) &&
- rhashtable_remove_fast(&h->ht, &e->node, mtype_rht_params) == 0)
- ipset_hash_elem_destroy_free(set, e);
+ if (ip_set_timeout_expired(ext_timeout(&e->elem, set)) &&
+ rhashtable_remove_fast(&h->ht, &e->node, mtype_rht_params) == 0)
+ ipset_hash_elem_destroy_free(set, e);
- /* stop+start can miss entries (we might have unlinked the
- * element). This is harmless.
- */
- if (mtype_gc_resched(&hti, seen))
- goto restart;
+ /* stop+start can miss entries (we might have unlinked the
+ * element). This is harmless.
+ */
+ if (mtype_gc_resched(&hti, seen))
+ goto restart;
+ }
}
+#endif
rhashtable_walk_stop(&hti);
rhashtable_walk_exit(&hti);
}
@@ -616,6 +927,12 @@ 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_MULTI
+ /* h->ht now holds one struct mtype_group per net/cidr/physdev key,
+ * not per element; account for that separately from *elements.
+ */
+ *ext_size += atomic_read(&h->ht.nelems) * sizeof(struct mtype_group);
+#endif
#ifdef IP_SET_HASH_WITH_NETS
{
@@ -645,8 +962,9 @@ mtype_rht_size(struct ip_set *set, u32 *elements, size_t *ext_size)
* @old: The element we're replacing (can be NULL)
* @flag_exist: Whether the request carried IPSET_FLAG_EXIST
*
- * allocates the element and initializes its data, cidr bookkeeping and
- * extensions.
+ * Common to both the plain rhashtable and the "multi" group element
+ * insertion paths: validates the maxelem condition, allocates
+ * the element and initializes its data, cidr bookkeeping and extensions.
*
* The caller still has to link the returned element into the hash.
*
@@ -779,6 +1097,61 @@ mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext,
int ret = 0;
rcu_read_lock_bh();
+#ifdef IP_SET_HASH_WITH_MULTI
+ {
+ struct mtype_group *grp;
+ unsigned int seen = 0;
+
+ grp = mtype_group_get_or_create(h, d, &ret);
+ if (!grp)
+ goto out_rcu_unlock;
+
+ old = NULL;
+ hlist_for_each_entry_rcu(e, &grp->iface_list, node) {
+ if (SET_ELEM_EXPIRED(set, &e->elem)) {
+ mtype_group_remove_elem(set, h, grp, e);
+ continue;
+ }
+ /* mtype_data_equal() implements test-time, pattern
+ * matching semantics (a wildcard element's prefix
+ * matching any interface it covers): it must not be
+ * used here to find the element @d refreshes, or
+ * adding/refreshing a specific interface could replace
+ * an unrelated wildcard element covering it (or vice
+ * versa). Use strict representation identity instead.
+ */
+ if (mtype_data_isequal(&e->elem, d)) {
+ old = e;
+ break;
+ }
+ ++seen;
+ }
+
+ if (!old && seen >= IPSET_GROUP_MAX_ENTRIES) {
+ spin_unlock_bh(&grp->lock);
+ ret = -IPSET_ERR_HASH_FULL;
+ goto out_rcu_unlock;
+ }
+
+ e = mtype_new_elem(set, h, d, ext, flags, old, flag_exist);
+ if (IS_ERR(e)) {
+ mtype_group_unlock(h, grp);
+ ret = PTR_ERR(e);
+ goto out_rcu_unlock;
+ }
+
+ if (old) {
+ hlist_replace_rcu(&old->node, &e->node);
+ } else {
+ /* new entries are added at the tail for compatibility
+ * with the old array-based implementation.
+ */
+ hlist_add_tail_rcu(&e->node, &grp->iface_list);
+ atomic_inc(&h->nelems);
+ }
+ spin_unlock_bh(&grp->lock);
+ }
+#else
old = rhashtable_lookup(&h->ht, d, mtype_rht_params);
if (old && SET_ELEM_EXPIRED(set, &old->elem)) {
/* simple case: element is expired, same as old == NULL. */
@@ -821,6 +1194,7 @@ mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext,
/* error: Undo mtype_add_cidr(). */
mtype_del_cidr_all(set, h, d);
}
+#endif
if (ret == 0 && old)
mtype_add_replace_old(set, h, d, ext, e, old);
@@ -850,6 +1224,29 @@ mtype_del(struct ip_set *set, void *value, const struct ip_set_ext *ext,
int ret = -IPSET_ERR_EXIST;
rcu_read_lock_bh();
+#ifdef IP_SET_HASH_WITH_MULTI
+ {
+ struct mtype_group *grp;
+
+ grp = rhashtable_lookup(&h->ht, d, mtype_group_rht_params);
+ if (!grp)
+ goto out_unlock;
+
+ spin_lock_bh(&grp->lock);
+
+ /* Decide which element this request affects while holding
+ * @grp->lock, so a concurrent mtype_add() cannot link a
+ * higher-priority (exact) element in between this decision
+ * and mtype_group_remove_elem() acting on it below.
+ */
+ e = mtype_group_find(set, grp, d);
+ if (e) {
+ mtype_group_remove_elem(set, h, grp, e);
+ ret = 0;
+ }
+ mtype_group_unlock(h, grp);
+ }
+#else
e = rhashtable_lookup(&h->ht, d, mtype_rht_params);
if (!e || SET_ELEM_EXPIRED(set, &e->elem))
goto out_unlock;
@@ -859,6 +1256,7 @@ mtype_del(struct ip_set *set, void *value, const struct ip_set_ext *ext,
mtype_del_cidr_all(set, h, d);
ip_set_ext_destroy(set, &e->elem);
kfree_rcu(e, rcu);
+#endif
out_unlock:
rcu_read_unlock_bh();
return ret ? -IPSET_ERR_EXIST : 0;
@@ -874,6 +1272,84 @@ mtype_data_match(struct mtype_elem *data, const struct ip_set_ext *ext,
return mtype_do_data_match(data);
}
+#ifdef IP_SET_HASH_WITH_MULTI
+/**
+ * mtype_group_test() - test @d against the elements sharing its key
+ * @h: Pointer to the htype
+ * @d: Lookup key
+ * @iface_matched_p: set status of interface matching
+ * @ext: Match extensions from the caller
+ * @mext: Match extensions to fill in
+ * @set: Pointer to the ip_set
+ * @flags: Match flags
+ *
+ * An exact element is tried before any wildcard element, independent of
+ * list order, mirroring mtype_group_find()'s precedence. Must be called
+ * under rcu_read_lock().
+ *
+ * @multi is set when a live (non-expired) element exists for @d's key but
+ * none of the group's live elements match @d's interface: some other
+ * interface's entry is registered at this netmask length, so the caller
+ * must not fall through to a broader (less specific) one. @multi is left
+ * untouched (the caller's initial false) when the group has no live
+ * elements left at all, when no candidate's interface matches @d (nothing
+ * live registered here), or when a candidate's interface matches but it
+ * is filtered out by its extensions (e.g. timed out): either way, this
+ * netmask length is unresolved and the caller may still fall through.
+ *
+ * Return: mtype_data_match()'s result for the first candidate it accepts
+ * (match or nomatch), or 0 if no candidate in this group is accepted.
+ */
+static int
+mtype_group_test(struct htype *h, const struct mtype_elem *d,
+ bool *iface_matched_p,
+ const struct ip_set_ext *ext, struct ip_set_ext *mext,
+ struct ip_set *set, u32 flags)
+{
+ bool iface_matched = false, any_live = false;
+ struct mtype_rht_elem *e, *exact = NULL;
+ struct mtype_group *grp;
+ int ret;
+
+ grp = rhashtable_lookup(&h->ht, d, mtype_group_rht_params);
+ if (!grp)
+ return 0;
+
+ hlist_for_each_entry_rcu(e, &grp->iface_list, node) {
+ if (SET_ELEM_EXPIRED(set, &e->elem))
+ continue;
+ any_live = true;
+ if (!mtype_data_equal(&e->elem, d))
+ continue;
+ if (mtype_data_isexact(&e->elem)) {
+ exact = e;
+ break;
+ }
+ }
+
+ if (exact) {
+ ret = mtype_data_match(&exact->elem, ext, mext, set, flags);
+ if (ret)
+ return ret;
+ iface_matched = true;
+ }
+
+ hlist_for_each_entry_rcu(e, &grp->iface_list, node) {
+ if (e == exact || SET_ELEM_EXPIRED(set, &e->elem) ||
+ !mtype_data_equal(&e->elem, d))
+ continue;
+ iface_matched = true;
+ ret = mtype_data_match(&e->elem, ext, mext, set, flags);
+ if (ret)
+ return ret;
+ }
+
+ if (any_live)
+ *iface_matched_p = !iface_matched;
+ return 0;
+}
+#endif /* IP_SET_HASH_WITH_MULTI */
+
#ifdef IP_SET_HASH_WITH_NETS
/* Special test function which takes into account the different network
* sizes added to the set
@@ -885,7 +1361,9 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
{
struct htype *h = set->data;
struct net_prefixes *nets0;
+#ifndef IP_SET_HASH_WITH_MULTI
struct mtype_rht_elem *e;
+#endif
#if IPSET_NET_COUNT == 2
struct net_prefixes *nets1;
struct mtype_elem orig = *d;
@@ -895,11 +1373,11 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
int ret, j;
#endif
unsigned int seq0;
- u32 multi;
+ bool multi;
pr_debug("test by nets\n");
retry:
- multi = 0;
+ multi = false;
nets0 = ipset_dereference_bh_nfnl(h->rnets[0]);
seq0 = read_seqcount_begin(&nets0->seq);
#if IPSET_NET_COUNT == 2
@@ -923,6 +1401,17 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
#else
mtype_data_netmask(d, p0.cidr);
#endif
+#ifdef IP_SET_HASH_WITH_MULTI
+ /* mtype_group_test() sets multi itself: the outer loop
+ * stops here when some other interface's entry is
+ * registered at this netmask, but still falls through if
+ * nothing here matches our interface at all, or if it did
+ * but got filtered by its extensions (e.g. timed out).
+ */
+ ret = mtype_group_test(h, d, &multi, ext, mext, set, flags);
+ if (ret)
+ goto check_retry;
+#else
e = rhashtable_lookup(&h->ht, d, mtype_rht_params);
if (e) {
ret = mtype_data_match(&e->elem, ext, mext, set, flags);
@@ -930,6 +1419,7 @@ mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
goto check_retry;
multi = false;
}
+#endif
#if IPSET_NET_COUNT == 2
}
#endif
@@ -953,7 +1443,9 @@ mtype_test(struct ip_set *set, void *value, const struct ip_set_ext *ext,
{
struct htype *h = set->data;
struct mtype_elem *d = value;
+#ifndef IP_SET_HASH_WITH_MULTI
struct mtype_rht_elem *e;
+#endif
int ret = 0;
#ifdef IP_SET_HASH_WITH_NETS
int i;
@@ -973,11 +1465,19 @@ mtype_test(struct ip_set *set, void *value, const struct ip_set_ext *ext,
}
#endif
+#ifdef IP_SET_HASH_WITH_MULTI
+ {
+ bool multi = false;
+
+ ret = mtype_group_test(h, d, &multi, ext, mext, set, flags);
+ }
+#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;
@@ -1047,9 +1547,15 @@ mtype_head(struct ip_set *set, struct sk_buff *skb)
/**
* struct mtype_list_iter - per-dump state, stored via IPSET_CB_PRIVATE
* @hti: rhashtable walk cursor over @htype.ht
+ * @last: copy of the last element mtype_group_list() emitted
+ * @have_last: whether @last holds a valid element
*/
struct mtype_list_iter {
struct rhashtable_iter hti;
+#ifdef IP_SET_HASH_WITH_MULTI
+ struct mtype_elem last;
+ bool have_last;
+#endif
};
/* Manage the rhashtable_iter lifetime for dump operations */
@@ -1074,6 +1580,84 @@ mtype_uref(struct ip_set *set, struct netlink_callback *cb, bool start)
}
}
+#ifdef IP_SET_HASH_WITH_MULTI
+/**
+ * mtype_group_list() - dump as much of a group's elements as fits
+ * @set: Pointer to the ip_set
+ * @grp: Group to dump
+ * @skb: Target skb
+ * @emitted: Incremented by the number of elements this call added
+ * @iter: Per-dump cursor; @iter->last/@iter->have_last identify the
+ * element @grp was dumped up to in an earlier, paused call
+ *
+ * Groups can hold up to IPSET_GROUP_MAX_ENTRIES elements with arbitrary
+ * extensions (comment, skbinfo, ...), so a group is not guaranteed to fit
+ * into a single dump skb. Elements are therefore emitted one at a time,
+ * same as for the non-"multi" types: on failure, only the element that
+ * didn't fit is rewound, @iter is left pointing at the last element that
+ * did fit, and the caller resumes this same group from there on the
+ * next, fresh skb.
+ *
+ * Resuming by element identity (mtype_data_isequal(), rather than a
+ * plain position count) keeps the resume point correct even if a
+ * concurrent mtype_del() removes an earlier, already dumped element
+ * from @grp's iface_list while the dump was paused: entries are only
+ * ever appended at the tail, so no concurrent insert can land before
+ * the resume point either. If the previously emitted element itself
+ * was removed in the meantime, there is no reliable resume point left,
+ * so this group is instead dumped again from the start, i.e. userspace
+ * will see duplicates rather than skipping entries.
+ *
+ * Return: 0 once @grp is fully dumped, -EMSGSIZE if an element didn't fit.
+ */
+static int
+mtype_group_list(const struct ip_set *set, struct mtype_group *grp,
+ struct sk_buff *skb, u32 *emitted, struct mtype_list_iter *iter)
+{
+ struct mtype_rht_elem *e;
+ struct nlattr *nested;
+ bool skipping = false;
+ void *incomplete;
+
+ if (iter->have_last) {
+ hlist_for_each_entry_rcu(e, &grp->iface_list, node) {
+ if (mtype_data_isequal(&e->elem, &iter->last)) {
+ skipping = true;
+ break;
+ }
+ }
+ }
+
+ hlist_for_each_entry_rcu(e, &grp->iface_list, node) {
+ if (skipping) {
+ if (mtype_data_isequal(&e->elem, &iter->last))
+ skipping = false;
+ continue;
+ }
+
+ if (SET_ELEM_EXPIRED(set, &e->elem))
+ continue;
+
+ incomplete = skb_tail_pointer(skb);
+ nested = nla_nest_start(skb, IPSET_ATTR_DATA);
+ if (!nested ||
+ mtype_data_list(skb, &e->elem) ||
+ ip_set_put_extensions(skb, set, &e->elem, true)) {
+ if (nested)
+ nla_nest_cancel(skb, nested);
+ nlmsg_trim(skb, incomplete);
+ return -EMSGSIZE;
+ }
+ nla_nest_end(skb, nested);
+ (*emitted)++;
+ iter->last = e->elem;
+ iter->have_last = true;
+ }
+ iter->have_last = false;
+ return 0;
+}
+#endif
+
/* Reply a LIST/SAVE request: dump the elements of the specified set */
static int
mtype_list(const struct ip_set *set,
@@ -1094,6 +1678,31 @@ mtype_list(const struct ip_set *set,
return -EMSGSIZE;
rhashtable_walk_start(hti);
+#ifdef IP_SET_HASH_WITH_MULTI
+ {
+ struct mtype_group *grp;
+
+ while ((grp = rhashtable_walk_peek(hti))) {
+ if (IS_ERR(grp)) {
+ if (PTR_ERR(grp) == -EAGAIN)
+ continue;
+ ret = PTR_ERR(grp);
+ break;
+ }
+ if (mtype_group_list(set, grp, skb, &emitted, iter))
+ goto paused;
+
+ /* Only advance once the whole group is dumped. */
+ grp = rhashtable_walk_next(hti);
+ if (IS_ERR(grp)) {
+ ret = PTR_ERR(grp);
+ if (ret != -EAGAIN)
+ break;
+ ret = 0;
+ }
+ }
+ }
+#else
{
struct mtype_rht_elem *e, *peeked;
struct nlattr *nested;
@@ -1139,6 +1748,7 @@ mtype_list(const struct ip_set *set,
}
}
}
+#endif
/* Walk exhausted: listing done */
nla_nest_end(skb, atd);
rhashtable_walk_stop(hti);
@@ -1293,14 +1903,26 @@ IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set,
#ifdef IP_SET_PROTO_UNDEF
hsize = sizeof(struct htype);
+#ifdef IP_SET_HASH_WITH_MULTI
+ params = mtype_group_rht_params;
+#else
params = mtype_rht_params;
+#endif
#else
if (set->family == NFPROTO_IPV6) {
hsize = sizeof(struct IPSET_TOKEN(HTYPE, 6));
+#ifdef IP_SET_HASH_WITH_MULTI
+ params = IPSET_TOKEN(HTYPE, 6_group_rht_params);
+#else
params = IPSET_TOKEN(HTYPE, 6_rht_params);
+#endif
} else {
hsize = sizeof(struct IPSET_TOKEN(HTYPE, 4));
+#ifdef IP_SET_HASH_WITH_MULTI
+ params = IPSET_TOKEN(HTYPE, 4_group_rht_params);
+#else
params = IPSET_TOKEN(HTYPE, 4_rht_params);
+#endif
}
#endif
h = kzalloc(hsize, GFP_KERNEL);
diff --git a/net/netfilter/ipset/ip_set_hash_ip.c b/net/netfilter/ipset/ip_set_hash_ip.c
index c9f4e3859663..226c9f9195aa 100644
--- a/net/netfilter/ipset/ip_set_hash_ip.c
+++ b/net/netfilter/ipset/ip_set_hash_ip.c
@@ -49,8 +49,7 @@ struct hash_ip4_elem {
static bool
hash_ip4_data_equal(const struct hash_ip4_elem *e1,
- const struct hash_ip4_elem *e2,
- u32 *multi)
+ const struct hash_ip4_elem *e2)
{
return e1->ip == e2->ip;
}
@@ -181,8 +180,7 @@ struct hash_ip6_elem {
static bool
hash_ip6_data_equal(const struct hash_ip6_elem *ip1,
- const struct hash_ip6_elem *ip2,
- u32 *multi)
+ const struct hash_ip6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6);
}
diff --git a/net/netfilter/ipset/ip_set_hash_ipmac.c b/net/netfilter/ipset/ip_set_hash_ipmac.c
index b9a2681e2488..6389dbb8b48b 100644
--- a/net/netfilter/ipset/ip_set_hash_ipmac.c
+++ b/net/netfilter/ipset/ip_set_hash_ipmac.c
@@ -50,8 +50,7 @@ struct hash_ipmac4_elem {
static bool
hash_ipmac4_data_equal(const struct hash_ipmac4_elem *e1,
- const struct hash_ipmac4_elem *e2,
- u32 *multi)
+ const struct hash_ipmac4_elem *e2)
{
return e1->ip == e2->ip && ether_addr_equal(e1->ether, e2->ether);
}
@@ -157,8 +156,7 @@ struct hash_ipmac6_elem {
static bool
hash_ipmac6_data_equal(const struct hash_ipmac6_elem *e1,
- const struct hash_ipmac6_elem *e2,
- u32 *multi)
+ const struct hash_ipmac6_elem *e2)
{
return ipv6_addr_equal(&e1->ip.in6, &e2->ip.in6) &&
ether_addr_equal(e1->ether, e2->ether);
diff --git a/net/netfilter/ipset/ip_set_hash_ipmark.c b/net/netfilter/ipset/ip_set_hash_ipmark.c
index e26ca2a370e3..c1eb78b0c7c4 100644
--- a/net/netfilter/ipset/ip_set_hash_ipmark.c
+++ b/net/netfilter/ipset/ip_set_hash_ipmark.c
@@ -45,8 +45,7 @@ struct hash_ipmark4_elem {
static bool
hash_ipmark4_data_equal(const struct hash_ipmark4_elem *ip1,
- const struct hash_ipmark4_elem *ip2,
- u32 *multi)
+ const struct hash_ipmark4_elem *ip2)
{
return ip1->ip == ip2->ip &&
ip1->mark == ip2->mark;
@@ -181,8 +180,7 @@ struct hash_ipmark6_elem {
static bool
hash_ipmark6_data_equal(const struct hash_ipmark6_elem *ip1,
- const struct hash_ipmark6_elem *ip2,
- u32 *multi)
+ const struct hash_ipmark6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) &&
ip1->mark == ip2->mark;
diff --git a/net/netfilter/ipset/ip_set_hash_ipport.c b/net/netfilter/ipset/ip_set_hash_ipport.c
index 41ca24a22a02..29f55d6bb659 100644
--- a/net/netfilter/ipset/ip_set_hash_ipport.c
+++ b/net/netfilter/ipset/ip_set_hash_ipport.c
@@ -53,8 +53,7 @@ struct hash_ipport4_elem {
static bool
hash_ipport4_data_equal(const struct hash_ipport4_elem *ip1,
- const struct hash_ipport4_elem *ip2,
- u32 *multi)
+ const struct hash_ipport4_elem *ip2)
{
return ip1->ip == ip2->ip &&
ip1->port == ip2->port &&
@@ -223,8 +222,7 @@ struct hash_ipport6_elem {
static bool
hash_ipport6_data_equal(const struct hash_ipport6_elem *ip1,
- const struct hash_ipport6_elem *ip2,
- u32 *multi)
+ const struct hash_ipport6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) &&
ip1->port == ip2->port &&
diff --git a/net/netfilter/ipset/ip_set_hash_ipportip.c b/net/netfilter/ipset/ip_set_hash_ipportip.c
index b9ac2efaa15c..4115d7c9afef 100644
--- a/net/netfilter/ipset/ip_set_hash_ipportip.c
+++ b/net/netfilter/ipset/ip_set_hash_ipportip.c
@@ -49,8 +49,7 @@ struct hash_ipportip4_elem {
static bool
hash_ipportip4_data_equal(const struct hash_ipportip4_elem *ip1,
- const struct hash_ipportip4_elem *ip2,
- u32 *multi)
+ const struct hash_ipportip4_elem *ip2)
{
return ip1->ip == ip2->ip &&
ip1->ip2 == ip2->ip2 &&
@@ -220,8 +219,7 @@ struct hash_ipportip6_elem {
static bool
hash_ipportip6_data_equal(const struct hash_ipportip6_elem *ip1,
- const struct hash_ipportip6_elem *ip2,
- u32 *multi)
+ const struct hash_ipportip6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) &&
ipv6_addr_equal(&ip1->ip2.in6, &ip2->ip2.in6) &&
diff --git a/net/netfilter/ipset/ip_set_hash_ipportnet.c b/net/netfilter/ipset/ip_set_hash_ipportnet.c
index 195853a25b06..0cc5c7e1805a 100644
--- a/net/netfilter/ipset/ip_set_hash_ipportnet.c
+++ b/net/netfilter/ipset/ip_set_hash_ipportnet.c
@@ -62,8 +62,7 @@ struct hash_ipportnet4_elem {
static bool
hash_ipportnet4_data_equal(const struct hash_ipportnet4_elem *ip1,
- const struct hash_ipportnet4_elem *ip2,
- u32 *multi)
+ const struct hash_ipportnet4_elem *ip2)
{
return ip1->ip == ip2->ip &&
ip1->ip2 == ip2->ip2 &&
@@ -320,8 +319,7 @@ struct hash_ipportnet6_elem {
static bool
hash_ipportnet6_data_equal(const struct hash_ipportnet6_elem *ip1,
- const struct hash_ipportnet6_elem *ip2,
- u32 *multi)
+ const struct hash_ipportnet6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) &&
ipv6_addr_equal(&ip1->ip2.in6, &ip2->ip2.in6) &&
diff --git a/net/netfilter/ipset/ip_set_hash_mac.c b/net/netfilter/ipset/ip_set_hash_mac.c
index 41a122591fe2..af96243d5796 100644
--- a/net/netfilter/ipset/ip_set_hash_mac.c
+++ b/net/netfilter/ipset/ip_set_hash_mac.c
@@ -40,8 +40,7 @@ struct hash_mac4_elem {
static bool
hash_mac4_data_equal(const struct hash_mac4_elem *e1,
- const struct hash_mac4_elem *e2,
- u32 *multi)
+ const struct hash_mac4_elem *e2)
{
return ether_addr_equal(e1->ether, e2->ether);
}
diff --git a/net/netfilter/ipset/ip_set_hash_net.c b/net/netfilter/ipset/ip_set_hash_net.c
index 092f3c9281b8..4324e68df0e5 100644
--- a/net/netfilter/ipset/ip_set_hash_net.c
+++ b/net/netfilter/ipset/ip_set_hash_net.c
@@ -50,8 +50,7 @@ struct hash_net4_elem {
static bool
hash_net4_data_equal(const struct hash_net4_elem *ip1,
- const struct hash_net4_elem *ip2,
- u32 *multi)
+ const struct hash_net4_elem *ip2)
{
return ip1->ip == ip2->ip &&
ip1->cidr == ip2->cidr;
@@ -221,8 +220,7 @@ struct hash_net6_elem {
static bool
hash_net6_data_equal(const struct hash_net6_elem *ip1,
- const struct hash_net6_elem *ip2,
- u32 *multi)
+ const struct hash_net6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) &&
ip1->cidr == ip2->cidr;
diff --git a/net/netfilter/ipset/ip_set_hash_netiface.c b/net/netfilter/ipset/ip_set_hash_netiface.c
index b602cc43565d..e4d48274e7bc 100644
--- a/net/netfilter/ipset/ip_set_hash_netiface.c
+++ b/net/netfilter/ipset/ip_set_hash_netiface.c
@@ -63,16 +63,20 @@ struct hash_netiface4_elem {
};
/* Common functions */
-
static bool
-hash_netiface4_data_equal(const struct hash_netiface4_elem *ip1,
- const struct hash_netiface4_elem *ip2,
- u32 *multi)
+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 &&
- (++*multi) &&
- ip1->physdev == ip2->physdev &&
+ ip1->physdev == ip2->physdev;
+}
+
+static bool
+hash_netiface4_data_equal(const struct hash_netiface4_elem *ip1,
+ const struct hash_netiface4_elem *ip2)
+{
+ return hash_netiface4_key_equal(ip1, ip2) &&
(ip1->wildcard ?
strncmp(ip1->iface, ip2->iface, strlen(ip1->iface)) == 0 :
strcmp(ip1->iface, ip2->iface) == 0);
@@ -84,6 +88,29 @@ hash_netiface4_do_data_match(const struct hash_netiface4_elem *elem)
return elem->nomatch ? -ENOTEMPTY : 1;
}
+/* An exact (non-wildcard) element always takes priority over a wildcard
+ * element for the same net/cidr/physdev key, regardless of which one a
+ * group's element list happens to return first.
+ */
+static bool
+hash_netiface4_data_isexact(const struct hash_netiface4_elem *elem)
+{
+ return !elem->wildcard;
+}
+
+/* Whether @ip1 and @ip2 are the very same stored representation, as opposed
+ * to whether @ip2's interface merely matches the pattern @ip1 represents.
+ * Used to find the element an add request refreshes.
+ */
+static bool
+hash_netiface4_data_isequal(const struct hash_netiface4_elem *ip1,
+ const struct hash_netiface4_elem *ip2)
+{
+ return hash_netiface4_key_equal(ip1, ip2) &&
+ ip1->wildcard == ip2->wildcard &&
+ strcmp(ip1->iface, ip2->iface) == 0;
+}
+
static void
hash_netiface4_data_set_flags(struct hash_netiface4_elem *elem, u32 flags)
{
@@ -297,16 +324,20 @@ struct hash_netiface6_elem {
};
/* Common functions */
-
static bool
-hash_netiface6_data_equal(const struct hash_netiface6_elem *ip1,
- const struct hash_netiface6_elem *ip2,
- u32 *multi)
+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 &&
- (++*multi) &&
- ip1->physdev == ip2->physdev &&
+ ip1->physdev == ip2->physdev;
+}
+
+static bool
+hash_netiface6_data_equal(const struct hash_netiface6_elem *ip1,
+ const struct hash_netiface6_elem *ip2)
+{
+ return hash_netiface6_key_equal(ip1, ip2) &&
(ip1->wildcard ?
strncmp(ip1->iface, ip2->iface, strlen(ip1->iface)) == 0 :
strcmp(ip1->iface, ip2->iface) == 0);
@@ -318,6 +349,25 @@ hash_netiface6_do_data_match(const struct hash_netiface6_elem *elem)
return elem->nomatch ? -ENOTEMPTY : 1;
}
+static bool
+hash_netiface6_data_isexact(const struct hash_netiface6_elem *elem)
+{
+ return !elem->wildcard;
+}
+
+/* Whether @ip1 and @ip2 are the very same stored representation, as opposed
+ * to whether @ip2's interface merely matches the pattern @ip1 represents.
+ * Used to find the element an add request refreshes.
+ */
+static bool
+hash_netiface6_data_isequal(const struct hash_netiface6_elem *ip1,
+ const struct hash_netiface6_elem *ip2)
+{
+ return hash_netiface6_key_equal(ip1, ip2) &&
+ ip1->wildcard == ip2->wildcard &&
+ strcmp(ip1->iface, ip2->iface) == 0;
+}
+
static void
hash_netiface6_data_set_flags(struct hash_netiface6_elem *elem, u32 flags)
{
diff --git a/net/netfilter/ipset/ip_set_hash_netnet.c b/net/netfilter/ipset/ip_set_hash_netnet.c
index f7c8a1cc30fc..fe2c9e32da86 100644
--- a/net/netfilter/ipset/ip_set_hash_netnet.c
+++ b/net/netfilter/ipset/ip_set_hash_netnet.c
@@ -58,8 +58,7 @@ struct hash_netnet4_elem {
static bool
hash_netnet4_data_equal(const struct hash_netnet4_elem *ip1,
- const struct hash_netnet4_elem *ip2,
- u32 *multi)
+ const struct hash_netnet4_elem *ip2)
{
return ip1->ipcmp == ip2->ipcmp &&
ip1->ccmp == ip2->ccmp;
@@ -295,8 +294,7 @@ struct hash_netnet6_elem {
static bool
hash_netnet6_data_equal(const struct hash_netnet6_elem *ip1,
- const struct hash_netnet6_elem *ip2,
- u32 *multi)
+ const struct hash_netnet6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip[0].in6, &ip2->ip[0].in6) &&
ipv6_addr_equal(&ip1->ip[1].in6, &ip2->ip[1].in6) &&
diff --git a/net/netfilter/ipset/ip_set_hash_netport.c b/net/netfilter/ipset/ip_set_hash_netport.c
index 5de4b511de76..eaa96c7dcd47 100644
--- a/net/netfilter/ipset/ip_set_hash_netport.c
+++ b/net/netfilter/ipset/ip_set_hash_netport.c
@@ -60,8 +60,7 @@ struct hash_netport4_elem {
static bool
hash_netport4_data_equal(const struct hash_netport4_elem *ip1,
- const struct hash_netport4_elem *ip2,
- u32 *multi)
+ const struct hash_netport4_elem *ip2)
{
return ip1->ip == ip2->ip &&
ip1->port == ip2->port &&
@@ -277,8 +276,7 @@ struct hash_netport6_elem {
static bool
hash_netport6_data_equal(const struct hash_netport6_elem *ip1,
- const struct hash_netport6_elem *ip2,
- u32 *multi)
+ const struct hash_netport6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip.in6, &ip2->ip.in6) &&
ip1->port == ip2->port &&
diff --git a/net/netfilter/ipset/ip_set_hash_netportnet.c b/net/netfilter/ipset/ip_set_hash_netportnet.c
index 61af1ce27127..e9d08c5de4fb 100644
--- a/net/netfilter/ipset/ip_set_hash_netportnet.c
+++ b/net/netfilter/ipset/ip_set_hash_netportnet.c
@@ -59,8 +59,7 @@ struct hash_netportnet4_elem {
static bool
hash_netportnet4_data_equal(const struct hash_netportnet4_elem *ip1,
- const struct hash_netportnet4_elem *ip2,
- u32 *multi)
+ const struct hash_netportnet4_elem *ip2)
{
return ip1->ipcmp == ip2->ipcmp &&
ip1->ccmp == ip2->ccmp &&
@@ -352,8 +351,7 @@ struct hash_netportnet6_elem {
static bool
hash_netportnet6_data_equal(const struct hash_netportnet6_elem *ip1,
- const struct hash_netportnet6_elem *ip2,
- u32 *multi)
+ const struct hash_netportnet6_elem *ip2)
{
return ipv6_addr_equal(&ip1->ip[0].in6, &ip2->ip[0].in6) &&
ipv6_addr_equal(&ip1->ip[1].in6, &ip2->ip[1].in6) &&
--
2.56.0
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nf-next v8 6/6] netfilter: ipset: re-add forceadd support
2026-11-11 10:11 [PATCH nf-next v8 0/6] ipset: replace internal hash table with rhashtable Florian Westphal
` (4 preceding siblings ...)
2026-11-11 10:11 ` [PATCH nf-next v8 5/6] netfilter: ipset: re-add IP_SET_HASH_WITH_MULTI support Florian Westphal
@ 2026-11-11 10:11 ` Florian Westphal
5 siblings, 0 replies; 7+ messages in thread
From: Florian Westphal @ 2026-11-11 10:11 UTC (permalink / raw)
To: netfilter-devel
The rhashtable conversion removed the SET_WITH_FORCEADD eviction logic.
Add mtype_remove_random() helper to look up a random key slot: a group
for IP_SET_HASH_WITH_MULTI sets, or a plain element otherwise. If there
is one, try to evict it and allow add of the new element just like
before the rhashtable conversion.
Signed-off-by: Florian Westphal <fw@strlen.de>
---
- adjust for changes in patch 5, must call
mtype_group_unlock() after mtype_group_remove_elem().
net/netfilter/ipset/ip_set_hash_gen.h | 93 ++++++++++++++++++++++++++-
1 file changed, 92 insertions(+), 1 deletion(-)
diff --git a/net/netfilter/ipset/ip_set_hash_gen.h b/net/netfilter/ipset/ip_set_hash_gen.h
index 5c85f316a09a..f6e73b5aaece 100644
--- a/net/netfilter/ipset/ip_set_hash_gen.h
+++ b/net/netfilter/ipset/ip_set_hash_gen.h
@@ -165,6 +165,8 @@ static const union nf_inet_addr zeromask = {};
#undef mtype_kadt
#undef mtype_uadt
+#undef mtype_remove_random
+#undef mtype_remove_cmpfn
#undef mtype_new_elem
#undef mtype_add_replace_old
#undef mtype_add
@@ -235,6 +237,8 @@ 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_cmpfn IPSET_TOKEN(MTYPE, _remove_cmpfn)
#define mtype_new_elem IPSET_TOKEN(MTYPE, _new_elem)
#define mtype_add_replace_old IPSET_TOKEN(MTYPE, _add_replace_old)
#define mtype_add IPSET_TOKEN(MTYPE, _add)
@@ -952,6 +956,93 @@ mtype_rht_size(struct ip_set *set, u32 *elements, size_t *ext_size)
#endif
}
+static int mtype_remove_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
+{
+ return 0; /* always match */
+}
+
+/**
+ * mtype_remove_random() - Remove a random element from the set (forceadd)
+ * @set: Pointer to the ip_set
+ *
+ * When sets created with forceadd option become full the next addition
+ * to the set may succeed and evict a random entry from the set.
+ * Best-effort: no linear scan; 'return false' is fine.
+ *
+ * Return: true if an element was evicted, false otherwise.
+ */
+static bool
+mtype_remove_random(struct ip_set *set)
+{
+ u32 k[HKEY_DATALEN / sizeof(u32)];
+ struct htype *h = set->data;
+
+ /* make sure k[] doesn't eat too much stack space */
+ BUILD_BUG_ON(sizeof(k) > 64);
+
+ /* The real hashfn is needed instead of a "get_random_u32" stub,
+ * because rhashtable_lookup() might fail to constant-fold the
+ * params below, in which case it would fall back to h->params
+ * hashfn.
+ */
+ get_random_bytes(k, sizeof(k));
+
+#ifdef IP_SET_HASH_WITH_MULTI
+ {
+ static const struct rhashtable_params ip_set_hash_grp_rnd_params = {
+ .head_offset = offsetof(struct mtype_group, node),
+ .key_offset = offsetof(struct mtype_group, key),
+ .hashfn = mtype_rht_hashfn,
+ .obj_hashfn = mtype_group_obj_hashfn,
+ .obj_cmpfn = mtype_remove_cmpfn,
+ .key_len = HKEY_DATALEN,
+ };
+ struct mtype_group *grp;
+ struct mtype_rht_elem *e;
+
+ grp = rhashtable_lookup(&h->ht, k, ip_set_hash_grp_rnd_params);
+ if (!grp)
+ return false;
+
+ /* mtype_add() can call us while already holding this exact
+ * group's lock (maxelem reached while inserting into it);
+ * trylock to avoid self-deadlock. Best-effort: no linear
+ * scan, 'return false' is fine either way.
+ */
+ if (!spin_trylock_bh(&grp->lock))
+ return false;
+ e = hlist_entry_safe(grp->iface_list.first,
+ struct mtype_rht_elem, node);
+ if (!e) {
+ spin_unlock_bh(&grp->lock);
+ return false;
+ }
+ mtype_group_remove_elem(set, h, grp, e);
+ mtype_group_unlock(h, grp);
+ return true;
+ }
+#else
+ {
+ static const struct rhashtable_params ip_set_hash_rnd_params = {
+ .head_offset = offsetof(struct mtype_rht_elem, node),
+ .key_offset = offsetof(struct mtype_rht_elem, elem),
+ .hashfn = mtype_rht_hashfn,
+ .obj_hashfn = mtype_rht_obj_hashfn,
+ .obj_cmpfn = mtype_remove_cmpfn,
+ .key_len = HKEY_DATALEN,
+ };
+ struct mtype_rht_elem *e;
+
+ e = rhashtable_lookup(&h->ht, &k, ip_set_hash_rnd_params);
+ if (!e || rhashtable_remove_fast(&h->ht, &e->node, mtype_rht_params))
+ return false;
+
+ ipset_hash_elem_destroy_free(set, e);
+ return true;
+ }
+#endif
+}
+
/**
* mtype_new_elem() - allocate and initialize a replacement/new element
* @set: Pointer to the ip_set
@@ -995,7 +1086,7 @@ mtype_new_elem(struct ip_set *set, struct htype *h, const struct mtype_elem *d,
* its pretty much pointless, userspace can just retry once
* gc has fired, resp. decrease the gc interval.
*/
- if (1) {
+ if (!SET_WITH_FORCEADD(set) || !mtype_remove_random(set)) {
if (net_ratelimit())
pr_warn("Set %s is full, maxelem %u reached\n",
set->name, h->maxelem);
--
2.56.0
^ permalink raw reply related [flat|nested] 7+ messages in thread