@@ -154,6 +154,9 @@ static const union nf_inet_addr zeromask = {};
#undef mtype_kadt
#undef mtype_uadt
+#undef mtype_remove_random
+#undef mtype_remove_key
+#undef mtype_remove_cmpfn
#undef mtype_add
#undef mtype_do_set_exts
#undef mtype_del
@@ -205,6 +208,9 @@ static const union nf_inet_addr zeromask = {};
#define mtype_kadt IPSET_TOKEN(MTYPE, _kadt)
#define mtype_uadt IPSET_TOKEN(MTYPE, _uadt)
+#define mtype_remove_random IPSET_TOKEN(MTYPE, _remove_random)
+#define mtype_remove_key IPSET_TOKEN(MTYPE, _remove_key)
+#define mtype_remove_cmpfn IPSET_TOKEN(MTYPE, _remove_cmpfn)
#define mtype_add IPSET_TOKEN(MTYPE, _add)
#define mtype_del IPSET_TOKEN(MTYPE, _del)
#define mtype_test_cidrs IPSET_TOKEN(MTYPE, _test_cidrs)
@@ -664,6 +670,66 @@ mtype_rht_size(struct ip_set *set, u32 *elements, size_t *ext_size)
(offsetof(struct mtype_rht_elem, elem) + set->dsize);
}
+static u32 mtype_remove_key(const void *data, u32 len, u32 seed)
+{
+ return get_random_u32();
+}
+
+static int mtype_remove_cmpfn(struct rhashtable_compare_arg *arg, const void *obj)
+{
+ return 0; /* always match */
+}
+
+/**
+ * mtype_remove_random() - Remove a random element from the set (forceadd)
+ * @set: Pointer to the ip_set
+ * @h: Pointer to the htype
+ *
+ * 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, struct htype *h)
+{
+ 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_remove_key,
+ .obj_hashfn = mtype_rht_obj_hashfn,
+ .obj_cmpfn = mtype_remove_cmpfn,
+ .key_len = sizeof(u32),
+ };
+ struct mtype_rht_elem *e = NULL;
+ bool removed = false;
+ static const u32 k;
+
+#ifdef IP_SET_HASH_WITH_MULTI
+ {
+ struct rhlist_head *list = rhltable_lookup(&h->rhlt, &k,
+ ip_set_hash_rnd_params);
+ if (!list)
+ return false;
+
+ e = container_of(list, typeof(*e), node);
+ }
+#else
+ e = rhashtable_lookup(&h->ht, &k, ip_set_hash_rnd_params);
+#endif
+ if (e && !ipset_hash_remove(h, e))
+ removed = true;
+
+ if (removed) {
+ mtype_del_cidr_all(set, h, &e->elem);
+ ip_set_ext_destroy(set, &e->elem);
+ kfree_rcu(e, rcu);
+ }
+
+ return removed;
+}
+
/* Add an element to a hash and update the internal counters when succeeded,
* otherwise report the proper error code.
*/
@@ -733,11 +799,13 @@ mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext,
}
if (!old && ipset_hash_nelems(h) >= h->maxelem) {
- if (net_ratelimit())
- pr_warn("Set %s is full, maxelem %u reached\n",
- set->name, h->maxelem);
- ret = -IPSET_ERR_HASH_FULL;
- goto out_rcu_unlock;
+ if (!SET_WITH_FORCEADD(set) || !mtype_remove_random(set, h)) {
+ if (net_ratelimit())
+ pr_warn("Set %s is full, maxelem %u reached\n",
+ set->name, h->maxelem);
+ ret = -IPSET_ERR_HASH_FULL;
+ goto out_rcu_unlock;
+ }
}
e = kzalloc(offsetof(struct mtype_rht_elem, elem) + set->dsize,
The rhashtable conversion removed the SET_WITH_FORCEADD eviction logic. Add mtype_remove_random() helper to lookup a random key slot. If there is an element, try to evict it and allow add of the new element just like before the rhashtable conversion. Assisted-by: Claude:claude-opus-4-6 Signed-off-by: Florian Westphal <fw@strlen.de> --- v3: reword kdoc to say that can only be best-effort and cannot guarantee insertion. Quote ipset man page verbatim. LLM review consistently harps on mtype_remove_random being bad. Its not, its actually more likely to remove an entry than the old region code used pre-rhashtable. And even if we would actually do a linear scan, we can't guarantee insertion given other CPU might be doing and insert as well: forceadd never 'guarantees' insertion will work, even ipset man page says so. net/netfilter/ipset/ip_set_hash_gen.h | 78 +++++++++++++++++++++++++-- 1 file changed, 73 insertions(+), 5 deletions(-)