nft_set_hash.c

  1// SPDX-License-Identifier: GPL-2.0-only
  2/*
  3 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
  4 *
  5 * Development of this code funded by Astaro AG (http://www.astaro.com/)
  6 */
  7
  8#include <linux/kernel.h>
  9#include <linux/init.h>
 10#include <linux/module.h>
 11#include <linux/list.h>
 12#include <linux/log2.h>
 13#include <linux/jhash.h>
 14#include <linux/netlink.h>
 15#include <linux/workqueue.h>
 16#include <linux/rhashtable.h>
 17#include <linux/netfilter.h>
 18#include <linux/netfilter/nf_tables.h>
 19#include <net/netfilter/nf_tables_core.h>
 20
 21/* We target a hash table size of 4, element hint is 75% of final size */
 22#define NFT_RHASH_ELEMENT_HINT 3
 23
 24struct nft_rhash {
 25	struct rhashtable		ht;
 26	struct delayed_work		gc_work;
 27	u32				wq_gc_seq;
 28};
 29
 30struct nft_rhash_elem {
 31	struct nft_elem_priv		priv;
 32	struct rhash_head		node;
 33	struct llist_node		walk_node;
 34	u32				wq_gc_seq;
 35	struct nft_set_ext		ext;
 36};
 37
 38struct nft_rhash_cmp_arg {
 39	const struct nft_set		*set;
 40	const u32			*key;
 41	u8				genmask;
 42	u64				tstamp;
 43};
 44
 45static inline u32 nft_rhash_key(const void *data, u32 len, u32 seed)
 46{
 47	const struct nft_rhash_cmp_arg *arg = data;
 48
 49	return jhash(arg->key, len, seed);
 50}
 51
 52static inline u32 nft_rhash_obj(const void *data, u32 len, u32 seed)
 53{
 54	const struct nft_rhash_elem *he = data;
 55
 56	return jhash(nft_set_ext_key(&he->ext), len, seed);
 57}
 58
 59static inline int nft_rhash_cmp(struct rhashtable_compare_arg *arg,
 60				const void *ptr)
 61{
 62	const struct nft_rhash_cmp_arg *x = arg->key;
 63	const struct nft_rhash_elem *he = ptr;
 64
 65	if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
 66		return 1;
 67	if (nft_set_elem_is_dead(&he->ext))
 68		return 1;
 69	if (__nft_set_elem_expired(&he->ext, x->tstamp))
 70		return 1;
 71	if (!nft_set_elem_active(&he->ext, x->genmask))
 72		return 1;
 73	return 0;
 74}
 75
 76static const struct rhashtable_params nft_rhash_params = {
 77	.head_offset		= offsetof(struct nft_rhash_elem, node),
 78	.hashfn			= nft_rhash_key,
 79	.obj_hashfn		= nft_rhash_obj,
 80	.obj_cmpfn		= nft_rhash_cmp,
 81	.automatic_shrinking	= true,
 82};
 83
 84INDIRECT_CALLABLE_SCOPE
 85const struct nft_set_ext *
 86nft_rhash_lookup(const struct net *net, const struct nft_set *set,
 87		 const u32 *key)
 88{
 89	struct nft_rhash *priv = nft_set_priv(set);
 90	const struct nft_rhash_elem *he;
 91	struct nft_rhash_cmp_arg arg = {
 92		.genmask = nft_genmask_cur(net),
 93		.set	 = set,
 94		.key	 = key,
 95		.tstamp  = get_jiffies_64(),
 96	};
 97
 98	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 99	if (he != NULL)
100		return &he->ext;
101
102	return NULL;
103}
104
105static struct nft_elem_priv *
106nft_rhash_get(const struct net *net, const struct nft_set *set,
107	      const struct nft_set_elem *elem, unsigned int flags)
108{
109	struct nft_rhash *priv = nft_set_priv(set);
110	struct nft_rhash_elem *he;
111	struct nft_rhash_cmp_arg arg = {
112		.genmask = nft_genmask_cur(net),
113		.set	 = set,
114		.key	 = elem->key.val.data,
115		.tstamp  = get_jiffies_64(),
116	};
117
118	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
119	if (he != NULL)
120		return &he->priv;
121
122	return ERR_PTR(-ENOENT);
123}
124
125static const struct nft_set_ext *
126nft_rhash_update(struct nft_set *set, const u32 *key,
127		 const struct nft_expr *expr, struct nft_regs *regs)
128{
129	struct nft_rhash *priv = nft_set_priv(set);
130	struct nft_rhash_elem *he, *prev;
131	struct nft_elem_priv *elem_priv;
132	struct nft_rhash_cmp_arg arg = {
133		.genmask = NFT_GENMASK_ANY,
134		.set	 = set,
135		.key	 = key,
136		.tstamp  = get_jiffies_64(),
137	};
138
139	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
140	if (he != NULL)
141		goto out;
142
143	elem_priv = nft_dynset_new(set, expr, regs);
144	if (!elem_priv)
145		goto err1;
146
147	he = nft_elem_priv_cast(elem_priv);
148	init_llist_node(&he->walk_node);
149	prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
150						nft_rhash_params);
151	if (IS_ERR(prev))
152		goto err2;
153
154	/* Another cpu may race to insert the element with the same key */
155	if (prev) {
156		nft_set_elem_destroy(set, &he->priv, true);
157		atomic_dec(&set->nelems);
158		he = prev;
159	}
160
161out:
162	return &he->ext;
163
164err2:
165	nft_set_elem_destroy(set, &he->priv, true);
166	atomic_dec(&set->nelems);
167err1:
168	return NULL;
169}
170
171static int nft_rhash_insert(const struct net *net, const struct nft_set *set,
172			    const struct nft_set_elem *elem,
173			    struct nft_elem_priv **elem_priv)
174{
175	struct nft_rhash_elem *he = nft_elem_priv_cast(elem->priv);
176	struct nft_rhash *priv = nft_set_priv(set);
177	struct nft_rhash_cmp_arg arg = {
178		.genmask = nft_genmask_next(net),
179		.set	 = set,
180		.key	 = elem->key.val.data,
181		.tstamp	 = nft_net_tstamp(net),
182	};
183	struct nft_rhash_elem *prev;
184
185	init_llist_node(&he->walk_node);
186	prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
187						nft_rhash_params);
188	if (IS_ERR(prev))
189		return PTR_ERR(prev);
190	if (prev) {
191		*elem_priv = &prev->priv;
192		return -EEXIST;
193	}
194	return 0;
195}
196
197static void nft_rhash_activate(const struct net *net, const struct nft_set *set,
198			       struct nft_elem_priv *elem_priv)
199{
200	struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
201
202	nft_clear(net, &he->ext);
203}
204
205static void nft_rhash_flush(const struct net *net,
206			    const struct nft_set *set,
207			    struct nft_elem_priv *elem_priv)
208{
209	struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
210
211	nft_set_elem_change_active(net, set, &he->ext);
212}
213
214static struct nft_elem_priv *
215nft_rhash_deactivate(const struct net *net, const struct nft_set *set,
216		     const struct nft_set_elem *elem)
217{
218	struct nft_rhash *priv = nft_set_priv(set);
219	struct nft_rhash_elem *he;
220	struct nft_rhash_cmp_arg arg = {
221		.genmask = nft_genmask_next(net),
222		.set	 = set,
223		.key	 = elem->key.val.data,
224		.tstamp	 = nft_net_tstamp(net),
225	};
226
227	rcu_read_lock();
228	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
229	if (he)
230		nft_set_elem_change_active(net, set, &he->ext);
231
232	rcu_read_unlock();
233
234	return &he->priv;
235}
236
237static void nft_rhash_remove(const struct net *net,
238			     const struct nft_set *set,
239			     struct nft_elem_priv *elem_priv)
240{
241	struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
242	struct nft_rhash *priv = nft_set_priv(set);
243
244	rhashtable_remove_fast(&priv->ht, &he->node, nft_rhash_params);
245}
246
247static bool nft_rhash_delete(const struct nft_set *set,
248			     const u32 *key)
249{
250	struct nft_rhash *priv = nft_set_priv(set);
251	struct nft_rhash_cmp_arg arg = {
252		.genmask = NFT_GENMASK_ANY,
253		.set = set,
254		.key = key,
255	};
256	struct nft_rhash_elem *he;
257
258	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
259	if (he == NULL)
260		return false;
261
262	nft_set_elem_dead(&he->ext);
263
264	return true;
265}
266
267static void nft_rhash_walk_ro(const struct nft_ctx *ctx, struct nft_set *set,
268			      struct nft_set_iter *iter)
269{
270	struct nft_rhash *priv = nft_set_priv(set);
271	struct rhashtable_iter hti;
272	struct nft_rhash_elem *he;
273
274	rhashtable_walk_enter(&priv->ht, &hti);
275	rhashtable_walk_start(&hti);
276
277	while ((he = rhashtable_walk_next(&hti))) {
278		if (IS_ERR(he)) {
279			if (PTR_ERR(he) != -EAGAIN) {
280				iter->err = PTR_ERR(he);
281				break;
282			}
283
284			continue;
285		}
286
287		if (iter->count < iter->skip)
288			goto cont;
289
290		iter->err = iter->fn(ctx, set, iter, &he->priv);
291		if (iter->err < 0)
292			break;
293
294cont:
295		iter->count++;
296	}
297	rhashtable_walk_stop(&hti);
298	rhashtable_walk_exit(&hti);
299}
300
301static void nft_rhash_walk_update(const struct nft_ctx *ctx,
302				  struct nft_set *set,
303				  struct nft_set_iter *iter)
304{
305	struct nft_rhash *priv = nft_set_priv(set);
306	struct nft_rhash_elem *he, *tmp;
307	struct llist_node *first_node;
308	struct rhashtable_iter hti;
309	LLIST_HEAD(walk_list);
310
311	lockdep_assert_held(&nft_pernet(ctx->net)->commit_mutex);
312
313	if (set->in_update_walk) {
314		/* This can happen with bogus rulesets during ruleset validation
315		 * when a verdict map causes a jump back to the same map.
316		 *
317		 * Without this extra check the walk_next loop below will see
318		 * elems on the callers walk_list and skip (not validate) them.
319		 */
320		iter->err = -EMLINK;
321		return;
322	}
323
324	/* walk happens under RCU.
325	 *
326	 * We create a snapshot list so ->iter callback can sleep.
327	 * commit_mutex is held, elements can ...
328	 * .. be added in parallel from dataplane (dynset)
329	 * .. be marked as dead in parallel from dataplane (dynset).
330	 * .. be queued for removal in parallel (gc timeout).
331	 * .. not be freed: transaction mutex is held.
332	 */
333	rhashtable_walk_enter(&priv->ht, &hti);
334	rhashtable_walk_start(&hti);
335
336	while ((he = rhashtable_walk_next(&hti))) {
337		if (IS_ERR(he)) {
338			if (PTR_ERR(he) != -EAGAIN) {
339				iter->err = PTR_ERR(he);
340				break;
341			}
342
343			continue;
344		}
345
346		/* rhashtable resized during walk, skip */
347		if (llist_on_list(&he->walk_node))
348			continue;
349
350		llist_add(&he->walk_node, &walk_list);
351	}
352	rhashtable_walk_stop(&hti);
353	rhashtable_walk_exit(&hti);
354
355	first_node = __llist_del_all(&walk_list);
356	set->in_update_walk = true;
357	llist_for_each_entry_safe(he, tmp, first_node, walk_node) {
358		if (iter->err == 0) {
359			iter->err = iter->fn(ctx, set, iter, &he->priv);
360			if (iter->err == 0)
361				iter->count++;
362		}
363
364		/* all entries must be cleared again, else next ->walk iteration
365		 * will skip entries.
366		 */
367		init_llist_node(&he->walk_node);
368	}
369	set->in_update_walk = false;
370}
371
372static void nft_rhash_walk(const struct nft_ctx *ctx, struct nft_set *set,
373			   struct nft_set_iter *iter)
374{
375	switch (iter->type) {
376	case NFT_ITER_UPDATE:
377	case NFT_ITER_UPDATE_CLONE:
378		/* only relevant for netlink dumps which use READ type */
379		WARN_ON_ONCE(iter->skip != 0);
380
381		nft_rhash_walk_update(ctx, set, iter);
382		break;
383	case NFT_ITER_READ:
384		nft_rhash_walk_ro(ctx, set, iter);
385		break;
386	default:
387		iter->err = -EINVAL;
388		WARN_ON_ONCE(1);
389		break;
390	}
391}
392
393static bool nft_rhash_expr_needs_gc_run(const struct nft_set *set,
394					struct nft_set_ext *ext)
395{
396	struct nft_set_elem_expr *elem_expr = nft_set_ext_expr(ext);
397	struct nft_expr *expr;
398	u32 size;
399
400	nft_setelem_expr_foreach(expr, elem_expr, size) {
401		if (expr->ops->gc &&
402		    expr->ops->gc(read_pnet(&set->net), expr) &&
403		    set->flags & NFT_SET_EVAL)
404			return true;
405	}
406
407	return false;
408}
409
410static void nft_rhash_gc(struct work_struct *work)
411{
412	struct nftables_pernet *nft_net;
413	struct nft_set *set;
414	struct nft_rhash_elem *he;
415	struct nft_rhash *priv;
416	struct rhashtable_iter hti;
417	struct nft_trans_gc *gc;
418	struct net *net;
419	u32 gc_seq;
420
421	priv = container_of(work, struct nft_rhash, gc_work.work);
422	set  = nft_set_container_of(priv);
423	net  = read_pnet(&set->net);
424	nft_net = nft_pernet(net);
425	gc_seq = READ_ONCE(nft_net->gc_seq);
426
427	if (nft_set_gc_is_pending(set))
428		goto done;
429
430	gc = nft_trans_gc_alloc(set, gc_seq, GFP_KERNEL);
431	if (!gc)
432		goto done;
433
434	/* Elements never collected use a zero gc worker sequence number. */
435	if (unlikely(++priv->wq_gc_seq == 0))
436		priv->wq_gc_seq++;
437
438	rhashtable_walk_enter(&priv->ht, &hti);
439	rhashtable_walk_start(&hti);
440
441	while ((he = rhashtable_walk_next(&hti))) {
442		if (IS_ERR(he)) {
443			nft_trans_gc_destroy(gc);
444			gc = NULL;
445			goto try_later;
446		}
447
448		/* Ruleset has been updated, try later. */
449		if (READ_ONCE(nft_net->gc_seq) != gc_seq) {
450			nft_trans_gc_destroy(gc);
451			gc = NULL;
452			goto try_later;
453		}
454
455		/* rhashtable walk is unstable, already seen in this gc run?
456		 * Then, skip this element. In case of (unlikely) sequence
457		 * wraparound and stale element wq_gc_seq, next gc run will
458		 * just find this expired element.
459		 */
460		if (he->wq_gc_seq == priv->wq_gc_seq)
461			continue;
462
463		if (nft_set_elem_is_dead(&he->ext))
464			goto dead_elem;
465
466		if (nft_set_ext_exists(&he->ext, NFT_SET_EXT_EXPRESSIONS) &&
467		    nft_rhash_expr_needs_gc_run(set, &he->ext))
468			goto needs_gc_run;
469
470		if (!nft_set_elem_expired(&he->ext))
471			continue;
472needs_gc_run:
473		nft_set_elem_dead(&he->ext);
474dead_elem:
475		gc = nft_trans_gc_queue_async(gc, gc_seq, GFP_ATOMIC);
476		if (!gc)
477			goto try_later;
478
479		/* annotate gc sequence for this attempt. */
480		he->wq_gc_seq = priv->wq_gc_seq;
481		nft_trans_gc_elem_add(gc, he);
482	}
483
484	gc = nft_trans_gc_catchall_async(gc, gc_seq);
485
486try_later:
487	/* catchall list iteration requires rcu read side lock. */
488	rhashtable_walk_stop(&hti);
489	rhashtable_walk_exit(&hti);
490
491	if (gc)
492		nft_trans_gc_queue_async_done(gc);
493
494done:
495	queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
496			   nft_set_gc_interval(set));
497}
498
499static u64 nft_rhash_privsize(const struct nlattr * const nla[],
500			      const struct nft_set_desc *desc)
501{
502	return sizeof(struct nft_rhash);
503}
504
505static void nft_rhash_gc_init(const struct nft_set *set)
506{
507	struct nft_rhash *priv = nft_set_priv(set);
508
509	queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
510			   nft_set_gc_interval(set));
511}
512
513static int nft_rhash_init(const struct nft_set *set,
514			  const struct nft_set_desc *desc,
515			  const struct nlattr * const tb[])
516{
517	struct nft_rhash *priv = nft_set_priv(set);
518	struct rhashtable_params params = nft_rhash_params;
519	int err;
520
521	BUILD_BUG_ON(offsetof(struct nft_rhash_elem, priv) != 0);
522
523	params.nelem_hint = desc->size ?: NFT_RHASH_ELEMENT_HINT;
524	params.key_len	  = set->klen;
525
526	err = rhashtable_init(&priv->ht, &params);
527	if (err < 0)
528		return err;
529
530	INIT_DEFERRABLE_WORK(&priv->gc_work, nft_rhash_gc);
531	if (set->flags & (NFT_SET_TIMEOUT | NFT_SET_EVAL))
532		nft_rhash_gc_init(set);
533
534	return 0;
535}
536
537struct nft_rhash_ctx {
538	const struct nft_ctx	ctx;
539	const struct nft_set	*set;
540};
541
542static void nft_rhash_elem_destroy(void *ptr, void *arg)
543{
544	struct nft_rhash_ctx *rhash_ctx = arg;
545	struct nft_rhash_elem *he = ptr;
546
547	nf_tables_set_elem_destroy(&rhash_ctx->ctx, rhash_ctx->set, &he->priv);
548}
549
550static void nft_rhash_destroy(const struct nft_ctx *ctx,
551			      const struct nft_set *set)
552{
553	struct nft_rhash *priv = nft_set_priv(set);
554	struct nft_rhash_ctx rhash_ctx = {
555		.ctx	= *ctx,
556		.set	= set,
557	};
558
559	cancel_delayed_work_sync(&priv->gc_work);
560	rhashtable_free_and_destroy(&priv->ht, nft_rhash_elem_destroy,
561				    (void *)&rhash_ctx);
562}
563
564/* Number of buckets is stored in u32, so cap our result to 1U<<31 */
565#define NFT_MAX_BUCKETS (1U << 31)
566
567static u32 nft_hash_buckets(u32 size)
568{
569	u64 val = div_u64((u64)size * 4, 3);
570
571	if (val >= NFT_MAX_BUCKETS)
572		return NFT_MAX_BUCKETS;
573
574	return roundup_pow_of_two(val);
575}
576
577static bool nft_rhash_estimate(const struct nft_set_desc *desc, u32 features,
578			       struct nft_set_estimate *est)
579{
580	est->size   = ~0;
581	est->lookup = NFT_SET_CLASS_O_1;
582	est->space  = NFT_SET_CLASS_O_N;
583
584	return true;
585}
586
587struct nft_hash {
588	u32				seed;
589	u32				buckets;
590	struct hlist_head		table[];
591};
592
593struct nft_hash_elem {
594	struct nft_elem_priv		priv;
595	struct hlist_node		node;
596	struct nft_set_ext		ext;
597};
598
599INDIRECT_CALLABLE_SCOPE
600const struct nft_set_ext *
601nft_hash_lookup(const struct net *net, const struct nft_set *set,
602		const u32 *key)
603{
604	struct nft_hash *priv = nft_set_priv(set);
605	u8 genmask = nft_genmask_cur(net);
606	const struct nft_hash_elem *he;
607	u32 hash;
608
609	hash = jhash(key, set->klen, priv->seed);
610	hash = reciprocal_scale(hash, priv->buckets);
611	hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
612		if (!memcmp(nft_set_ext_key(&he->ext), key, set->klen) &&
613		    nft_set_elem_active(&he->ext, genmask))
614			return &he->ext;
615	}
616	return NULL;
617}
618
619static struct nft_elem_priv *
620nft_hash_get(const struct net *net, const struct nft_set *set,
621	     const struct nft_set_elem *elem, unsigned int flags)
622{
623	const u32 *key = (const u32 *)&elem->key.val;
624	struct nft_hash *priv = nft_set_priv(set);
625	u8 genmask = nft_genmask_cur(net);
626	struct nft_hash_elem *he;
627	u32 hash;
628
629	if (set->klen == 4)
630		hash = jhash_1word(*key, priv->seed);
631	else
632		hash = jhash(key, set->klen, priv->seed);
633
634	hash = reciprocal_scale(hash, priv->buckets);
635	hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
636		if (!memcmp(nft_set_ext_key(&he->ext), key, set->klen) &&
637		    nft_set_elem_active(&he->ext, genmask))
638			return &he->priv;
639	}
640	return ERR_PTR(-ENOENT);
641}
642
643INDIRECT_CALLABLE_SCOPE
644const struct nft_set_ext *
645nft_hash_lookup_fast(const struct net *net, const struct nft_set *set,
646		     const u32 *key)
647{
648	struct nft_hash *priv = nft_set_priv(set);
649	u8 genmask = nft_genmask_cur(net);
650	const struct nft_hash_elem *he;
651	u32 hash, k1, k2;
652
653	k1 = *key;
654	hash = jhash_1word(k1, priv->seed);
655	hash = reciprocal_scale(hash, priv->buckets);
656	hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
657		k2 = *(u32 *)nft_set_ext_key(&he->ext)->data;
658		if (k1 == k2 &&
659		    nft_set_elem_active(&he->ext, genmask))
660			return &he->ext;
661	}
662	return NULL;
663}
664
665static u32 nft_jhash(const struct nft_set *set, const struct nft_hash *priv,
666		     const struct nft_set_ext *ext)
667{
668	const struct nft_data *key = nft_set_ext_key(ext);
669	u32 hash, k1;
670
671	if (set->klen == 4) {
672		k1 = *(u32 *)key;
673		hash = jhash_1word(k1, priv->seed);
674	} else {
675		hash = jhash(key, set->klen, priv->seed);
676	}
677	hash = reciprocal_scale(hash, priv->buckets);
678
679	return hash;
680}
681
682static int nft_hash_insert(const struct net *net, const struct nft_set *set,
683			   const struct nft_set_elem *elem,
684			   struct nft_elem_priv **elem_priv)
685{
686	struct nft_hash_elem *this = nft_elem_priv_cast(elem->priv), *he;
687	struct nft_hash *priv = nft_set_priv(set);
688	u8 genmask = nft_genmask_next(net);
689	u32 hash;
690
691	hash = nft_jhash(set, priv, &this->ext);
692	hlist_for_each_entry(he, &priv->table[hash], node) {
693		if (!memcmp(nft_set_ext_key(&this->ext),
694			    nft_set_ext_key(&he->ext), set->klen) &&
695		    nft_set_elem_active(&he->ext, genmask)) {
696			*elem_priv = &he->priv;
697			return -EEXIST;
698		}
699	}
700	hlist_add_head_rcu(&this->node, &priv->table[hash]);
701	return 0;
702}
703
704static void nft_hash_activate(const struct net *net, const struct nft_set *set,
705			      struct nft_elem_priv *elem_priv)
706{
707	struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
708
709	nft_clear(net, &he->ext);
710}
711
712static void nft_hash_flush(const struct net *net,
713			   const struct nft_set *set,
714			   struct nft_elem_priv *elem_priv)
715{
716	struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
717
718	nft_set_elem_change_active(net, set, &he->ext);
719}
720
721static struct nft_elem_priv *
722nft_hash_deactivate(const struct net *net, const struct nft_set *set,
723		    const struct nft_set_elem *elem)
724{
725	struct nft_hash_elem *this = nft_elem_priv_cast(elem->priv), *he;
726	struct nft_hash *priv = nft_set_priv(set);
727	u8 genmask = nft_genmask_next(net);
728	u32 hash;
729
730	hash = nft_jhash(set, priv, &this->ext);
731	hlist_for_each_entry(he, &priv->table[hash], node) {
732		if (!memcmp(nft_set_ext_key(&he->ext), &elem->key.val,
733			    set->klen) &&
734		    nft_set_elem_active(&he->ext, genmask)) {
735			nft_set_elem_change_active(net, set, &he->ext);
736			return &he->priv;
737		}
738	}
739	return NULL;
740}
741
742static void nft_hash_remove(const struct net *net,
743			    const struct nft_set *set,
744			    struct nft_elem_priv *elem_priv)
745{
746	struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
747
748	hlist_del_rcu(&he->node);
749}
750
751static void nft_hash_walk(const struct nft_ctx *ctx, struct nft_set *set,
752			  struct nft_set_iter *iter)
753{
754	struct nft_hash *priv = nft_set_priv(set);
755	struct nft_hash_elem *he;
756	int i;
757
758	for (i = 0; i < priv->buckets; i++) {
759		hlist_for_each_entry_rcu(he, &priv->table[i], node,
760					 lockdep_is_held(&nft_pernet(ctx->net)->commit_mutex)) {
761			if (iter->count < iter->skip)
762				goto cont;
763
764			iter->err = iter->fn(ctx, set, iter, &he->priv);
765			if (iter->err < 0)
766				return;
767cont:
768			iter->count++;
769		}
770	}
771}
772
773static u64 nft_hash_privsize(const struct nlattr * const nla[],
774			     const struct nft_set_desc *desc)
775{
776	return sizeof(struct nft_hash) +
777	       (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head);
778}
779
780static int nft_hash_init(const struct nft_set *set,
781			 const struct nft_set_desc *desc,
782			 const struct nlattr * const tb[])
783{
784	struct nft_hash *priv = nft_set_priv(set);
785
786	priv->buckets = nft_hash_buckets(desc->size);
787	get_random_bytes(&priv->seed, sizeof(priv->seed));
788
789	return 0;
790}
791
792static void nft_hash_destroy(const struct nft_ctx *ctx,
793			     const struct nft_set *set)
794{
795	struct nft_hash *priv = nft_set_priv(set);
796	struct nft_hash_elem *he;
797	struct hlist_node *next;
798	int i;
799
800	for (i = 0; i < priv->buckets; i++) {
801		hlist_for_each_entry_safe(he, next, &priv->table[i], node) {
802			hlist_del_rcu(&he->node);
803			nf_tables_set_elem_destroy(ctx, set, &he->priv);
804		}
805	}
806}
807
808static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
809			      struct nft_set_estimate *est)
810{
811	if (!desc->size)
812		return false;
813
814	if (desc->klen == 4)
815		return false;
816
817	est->size   = sizeof(struct nft_hash) +
818		      (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head) +
819		      (u64)desc->size * sizeof(struct nft_hash_elem);
820	est->lookup = NFT_SET_CLASS_O_1;
821	est->space  = NFT_SET_CLASS_O_N;
822
823	return true;
824}
825
826static bool nft_hash_fast_estimate(const struct nft_set_desc *desc, u32 features,
827				   struct nft_set_estimate *est)
828{
829	if (!desc->size)
830		return false;
831
832	if (desc->klen != 4)
833		return false;
834
835	est->size   = sizeof(struct nft_hash) +
836		      (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head) +
837		      (u64)desc->size * sizeof(struct nft_hash_elem);
838	est->lookup = NFT_SET_CLASS_O_1;
839	est->space  = NFT_SET_CLASS_O_N;
840
841	return true;
842}
843
844const struct nft_set_type nft_set_rhash_type = {
845	.features	= NFT_SET_MAP | NFT_SET_OBJECT |
846			  NFT_SET_TIMEOUT | NFT_SET_EVAL,
847	.ops		= {
848		.privsize       = nft_rhash_privsize,
849		.elemsize	= offsetof(struct nft_rhash_elem, ext),
850		.estimate	= nft_rhash_estimate,
851		.init		= nft_rhash_init,
852		.gc_init	= nft_rhash_gc_init,
853		.destroy	= nft_rhash_destroy,
854		.insert		= nft_rhash_insert,
855		.activate	= nft_rhash_activate,
856		.deactivate	= nft_rhash_deactivate,
857		.flush		= nft_rhash_flush,
858		.remove		= nft_rhash_remove,
859		.lookup		= nft_rhash_lookup,
860		.update		= nft_rhash_update,
861		.delete		= nft_rhash_delete,
862		.walk		= nft_rhash_walk,
863		.get		= nft_rhash_get,
864	},
865};
866
867const struct nft_set_type nft_set_hash_type = {
868	.features	= NFT_SET_MAP | NFT_SET_OBJECT,
869	.ops		= {
870		.privsize       = nft_hash_privsize,
871		.elemsize	= offsetof(struct nft_hash_elem, ext),
872		.estimate	= nft_hash_estimate,
873		.init		= nft_hash_init,
874		.destroy	= nft_hash_destroy,
875		.insert		= nft_hash_insert,
876		.activate	= nft_hash_activate,
877		.deactivate	= nft_hash_deactivate,
878		.flush		= nft_hash_flush,
879		.remove		= nft_hash_remove,
880		.lookup		= nft_hash_lookup,
881		.walk		= nft_hash_walk,
882		.get		= nft_hash_get,
883	},
884};
885
886const struct nft_set_type nft_set_hash_fast_type = {
887	.features	= NFT_SET_MAP | NFT_SET_OBJECT,
888	.ops		= {
889		.privsize       = nft_hash_privsize,
890		.elemsize	= offsetof(struct nft_hash_elem, ext),
891		.estimate	= nft_hash_fast_estimate,
892		.init		= nft_hash_init,
893		.destroy	= nft_hash_destroy,
894		.insert		= nft_hash_insert,
895		.activate	= nft_hash_activate,
896		.deactivate	= nft_hash_deactivate,
897		.flush		= nft_hash_flush,
898		.remove		= nft_hash_remove,
899		.lookup		= nft_hash_lookup_fast,
900		.walk		= nft_hash_walk,
901		.get		= nft_hash_get,
902	},
903};