xref: /linux/net/netfilter/nft_set_hash.c (revision d642ef71) 
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 
24 struct nft_rhash {
25 	struct rhashtable		ht;
26 	struct delayed_work		gc_work;
27 };
28 
29 struct nft_rhash_elem {
30 	struct nft_elem_priv		priv;
31 	struct rhash_head		node;
32 	struct nft_set_ext		ext;
33 };
34 
35 struct nft_rhash_cmp_arg {
36 	const struct nft_set		*set;
37 	const u32			*key;
38 	u8				genmask;
39 };
40 
41 static inline u32 nft_rhash_key(const void *data, u32 len, u32 seed)
42 {
43 	const struct nft_rhash_cmp_arg *arg = data;
44 
45 	return jhash(arg->key, len, seed);
46 }
47 
48 static inline u32 nft_rhash_obj(const void *data, u32 len, u32 seed)
49 {
50 	const struct nft_rhash_elem *he = data;
51 
52 	return jhash(nft_set_ext_key(&he->ext), len, seed);
53 }
54 
55 static inline int nft_rhash_cmp(struct rhashtable_compare_arg *arg,
56 				const void *ptr)
57 {
58 	const struct nft_rhash_cmp_arg *x = arg->key;
59 	const struct nft_rhash_elem *he = ptr;
60 
61 	if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
62 		return 1;
63 	if (nft_set_elem_is_dead(&he->ext))
64 		return 1;
65 	if (nft_set_elem_expired(&he->ext))
66 		return 1;
67 	if (!nft_set_elem_active(&he->ext, x->genmask))
68 		return 1;
69 	return 0;
70 }
71 
72 static const struct rhashtable_params nft_rhash_params = {
73 	.head_offset		= offsetof(struct nft_rhash_elem, node),
74 	.hashfn			= nft_rhash_key,
75 	.obj_hashfn		= nft_rhash_obj,
76 	.obj_cmpfn		= nft_rhash_cmp,
77 	.automatic_shrinking	= true,
78 };
79 
80 INDIRECT_CALLABLE_SCOPE
81 bool nft_rhash_lookup(const struct net *net, const struct nft_set *set,
82 		      const u32 *key, const struct nft_set_ext **ext)
83 {
84 	struct nft_rhash *priv = nft_set_priv(set);
85 	const struct nft_rhash_elem *he;
86 	struct nft_rhash_cmp_arg arg = {
87 		.genmask = nft_genmask_cur(net),
88 		.set	 = set,
89 		.key	 = key,
90 	};
91 
92 	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
93 	if (he != NULL)
94 		*ext = &he->ext;
95 
96 	return !!he;
97 }
98 
99 static struct nft_elem_priv *
100 nft_rhash_get(const struct net *net, const struct nft_set *set,
101 	      const struct nft_set_elem *elem, unsigned int flags)
102 {
103 	struct nft_rhash *priv = nft_set_priv(set);
104 	struct nft_rhash_elem *he;
105 	struct nft_rhash_cmp_arg arg = {
106 		.genmask = nft_genmask_cur(net),
107 		.set	 = set,
108 		.key	 = elem->key.val.data,
109 	};
110 
111 	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
112 	if (he != NULL)
113 		return &he->priv;
114 
115 	return ERR_PTR(-ENOENT);
116 }
117 
118 static bool nft_rhash_update(struct nft_set *set, const u32 *key,
119 			     struct nft_elem_priv *
120 				   (*new)(struct nft_set *,
121 					  const struct nft_expr *,
122 					  struct nft_regs *regs),
123 			     const struct nft_expr *expr,
124 			     struct nft_regs *regs,
125 			     const struct nft_set_ext **ext)
126 {
127 	struct nft_rhash *priv = nft_set_priv(set);
128 	struct nft_rhash_elem *he, *prev;
129 	struct nft_elem_priv *elem_priv;
130 	struct nft_rhash_cmp_arg arg = {
131 		.genmask = NFT_GENMASK_ANY,
132 		.set	 = set,
133 		.key	 = key,
134 	};
135 
136 	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
137 	if (he != NULL)
138 		goto out;
139 
140 	elem_priv = new(set, expr, regs);
141 	if (!elem_priv)
142 		goto err1;
143 
144 	he = nft_elem_priv_cast(elem_priv);
145 	prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
146 						nft_rhash_params);
147 	if (IS_ERR(prev))
148 		goto err2;
149 
150 	/* Another cpu may race to insert the element with the same key */
151 	if (prev) {
152 		nft_set_elem_destroy(set, &he->priv, true);
153 		atomic_dec(&set->nelems);
154 		he = prev;
155 	}
156 
157 out:
158 	*ext = &he->ext;
159 	return true;
160 
161 err2:
162 	nft_set_elem_destroy(set, &he->priv, true);
163 	atomic_dec(&set->nelems);
164 err1:
165 	return false;
166 }
167 
168 static int nft_rhash_insert(const struct net *net, const struct nft_set *set,
169 			    const struct nft_set_elem *elem,
170 			    struct nft_elem_priv **elem_priv)
171 {
172 	struct nft_rhash_elem *he = nft_elem_priv_cast(elem->priv);
173 	struct nft_rhash *priv = nft_set_priv(set);
174 	struct nft_rhash_cmp_arg arg = {
175 		.genmask = nft_genmask_next(net),
176 		.set	 = set,
177 		.key	 = elem->key.val.data,
178 	};
179 	struct nft_rhash_elem *prev;
180 
181 	prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
182 						nft_rhash_params);
183 	if (IS_ERR(prev))
184 		return PTR_ERR(prev);
185 	if (prev) {
186 		*elem_priv = &prev->priv;
187 		return -EEXIST;
188 	}
189 	return 0;
190 }
191 
192 static void nft_rhash_activate(const struct net *net, const struct nft_set *set,
193 			       struct nft_elem_priv *elem_priv)
194 {
195 	struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
196 
197 	nft_set_elem_change_active(net, set, &he->ext);
198 }
199 
200 static void nft_rhash_flush(const struct net *net,
201 			    const struct nft_set *set,
202 			    struct nft_elem_priv *elem_priv)
203 {
204 	struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
205 
206 	nft_set_elem_change_active(net, set, &he->ext);
207 }
208 
209 static struct nft_elem_priv *
210 nft_rhash_deactivate(const struct net *net, const struct nft_set *set,
211 		     const struct nft_set_elem *elem)
212 {
213 	struct nft_rhash *priv = nft_set_priv(set);
214 	struct nft_rhash_elem *he;
215 	struct nft_rhash_cmp_arg arg = {
216 		.genmask = nft_genmask_next(net),
217 		.set	 = set,
218 		.key	 = elem->key.val.data,
219 	};
220 
221 	rcu_read_lock();
222 	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
223 	if (he)
224 		nft_set_elem_change_active(net, set, &he->ext);
225 
226 	rcu_read_unlock();
227 
228 	return &he->priv;
229 }
230 
231 static void nft_rhash_remove(const struct net *net,
232 			     const struct nft_set *set,
233 			     struct nft_elem_priv *elem_priv)
234 {
235 	struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
236 	struct nft_rhash *priv = nft_set_priv(set);
237 
238 	rhashtable_remove_fast(&priv->ht, &he->node, nft_rhash_params);
239 }
240 
241 static bool nft_rhash_delete(const struct nft_set *set,
242 			     const u32 *key)
243 {
244 	struct nft_rhash *priv = nft_set_priv(set);
245 	struct nft_rhash_cmp_arg arg = {
246 		.genmask = NFT_GENMASK_ANY,
247 		.set = set,
248 		.key = key,
249 	};
250 	struct nft_rhash_elem *he;
251 
252 	he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
253 	if (he == NULL)
254 		return false;
255 
256 	nft_set_elem_dead(&he->ext);
257 
258 	return true;
259 }
260 
261 static void nft_rhash_walk(const struct nft_ctx *ctx, struct nft_set *set,
262 			   struct nft_set_iter *iter)
263 {
264 	struct nft_rhash *priv = nft_set_priv(set);
265 	struct nft_rhash_elem *he;
266 	struct rhashtable_iter hti;
267 
268 	rhashtable_walk_enter(&priv->ht, &hti);
269 	rhashtable_walk_start(&hti);
270 
271 	while ((he = rhashtable_walk_next(&hti))) {
272 		if (IS_ERR(he)) {
273 			if (PTR_ERR(he) != -EAGAIN) {
274 				iter->err = PTR_ERR(he);
275 				break;
276 			}
277 
278 			continue;
279 		}
280 
281 		if (iter->count < iter->skip)
282 			goto cont;
283 		if (!nft_set_elem_active(&he->ext, iter->genmask))
284 			goto cont;
285 
286 		iter->err = iter->fn(ctx, set, iter, &he->priv);
287 		if (iter->err < 0)
288 			break;
289 
290 cont:
291 		iter->count++;
292 	}
293 	rhashtable_walk_stop(&hti);
294 	rhashtable_walk_exit(&hti);
295 }
296 
297 static bool nft_rhash_expr_needs_gc_run(const struct nft_set *set,
298 					struct nft_set_ext *ext)
299 {
300 	struct nft_set_elem_expr *elem_expr = nft_set_ext_expr(ext);
301 	struct nft_expr *expr;
302 	u32 size;
303 
304 	nft_setelem_expr_foreach(expr, elem_expr, size) {
305 		if (expr->ops->gc &&
306 		    expr->ops->gc(read_pnet(&set->net), expr))
307 			return true;
308 	}
309 
310 	return false;
311 }
312 
313 static void nft_rhash_gc(struct work_struct *work)
314 {
315 	struct nftables_pernet *nft_net;
316 	struct nft_set *set;
317 	struct nft_rhash_elem *he;
318 	struct nft_rhash *priv;
319 	struct rhashtable_iter hti;
320 	struct nft_trans_gc *gc;
321 	struct net *net;
322 	u32 gc_seq;
323 
324 	priv = container_of(work, struct nft_rhash, gc_work.work);
325 	set  = nft_set_container_of(priv);
326 	net  = read_pnet(&set->net);
327 	nft_net = nft_pernet(net);
328 	gc_seq = READ_ONCE(nft_net->gc_seq);
329 
330 	if (nft_set_gc_is_pending(set))
331 		goto done;
332 
333 	gc = nft_trans_gc_alloc(set, gc_seq, GFP_KERNEL);
334 	if (!gc)
335 		goto done;
336 
337 	rhashtable_walk_enter(&priv->ht, &hti);
338 	rhashtable_walk_start(&hti);
339 
340 	while ((he = rhashtable_walk_next(&hti))) {
341 		if (IS_ERR(he)) {
342 			nft_trans_gc_destroy(gc);
343 			gc = NULL;
344 			goto try_later;
345 		}
346 
347 		/* Ruleset has been updated, try later. */
348 		if (READ_ONCE(nft_net->gc_seq) != gc_seq) {
349 			nft_trans_gc_destroy(gc);
350 			gc = NULL;
351 			goto try_later;
352 		}
353 
354 		if (nft_set_elem_is_dead(&he->ext))
355 			goto dead_elem;
356 
357 		if (nft_set_ext_exists(&he->ext, NFT_SET_EXT_EXPRESSIONS) &&
358 		    nft_rhash_expr_needs_gc_run(set, &he->ext))
359 			goto needs_gc_run;
360 
361 		if (!nft_set_elem_expired(&he->ext))
362 			continue;
363 needs_gc_run:
364 		nft_set_elem_dead(&he->ext);
365 dead_elem:
366 		gc = nft_trans_gc_queue_async(gc, gc_seq, GFP_ATOMIC);
367 		if (!gc)
368 			goto try_later;
369 
370 		nft_trans_gc_elem_add(gc, he);
371 	}
372 
373 	gc = nft_trans_gc_catchall_async(gc, gc_seq);
374 
375 try_later:
376 	/* catchall list iteration requires rcu read side lock. */
377 	rhashtable_walk_stop(&hti);
378 	rhashtable_walk_exit(&hti);
379 
380 	if (gc)
381 		nft_trans_gc_queue_async_done(gc);
382 
383 done:
384 	queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
385 			   nft_set_gc_interval(set));
386 }
387 
388 static u64 nft_rhash_privsize(const struct nlattr * const nla[],
389 			      const struct nft_set_desc *desc)
390 {
391 	return sizeof(struct nft_rhash);
392 }
393 
394 static void nft_rhash_gc_init(const struct nft_set *set)
395 {
396 	struct nft_rhash *priv = nft_set_priv(set);
397 
398 	queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
399 			   nft_set_gc_interval(set));
400 }
401 
402 static int nft_rhash_init(const struct nft_set *set,
403 			  const struct nft_set_desc *desc,
404 			  const struct nlattr * const tb[])
405 {
406 	struct nft_rhash *priv = nft_set_priv(set);
407 	struct rhashtable_params params = nft_rhash_params;
408 	int err;
409 
410 	BUILD_BUG_ON(offsetof(struct nft_rhash_elem, priv) != 0);
411 
412 	params.nelem_hint = desc->size ?: NFT_RHASH_ELEMENT_HINT;
413 	params.key_len	  = set->klen;
414 
415 	err = rhashtable_init(&priv->ht, &params);
416 	if (err < 0)
417 		return err;
418 
419 	INIT_DEFERRABLE_WORK(&priv->gc_work, nft_rhash_gc);
420 	if (set->flags & (NFT_SET_TIMEOUT | NFT_SET_EVAL))
421 		nft_rhash_gc_init(set);
422 
423 	return 0;
424 }
425 
426 struct nft_rhash_ctx {
427 	const struct nft_ctx	ctx;
428 	const struct nft_set	*set;
429 };
430 
431 static void nft_rhash_elem_destroy(void *ptr, void *arg)
432 {
433 	struct nft_rhash_ctx *rhash_ctx = arg;
434 	struct nft_rhash_elem *he = ptr;
435 
436 	nf_tables_set_elem_destroy(&rhash_ctx->ctx, rhash_ctx->set, &he->priv);
437 }
438 
439 static void nft_rhash_destroy(const struct nft_ctx *ctx,
440 			      const struct nft_set *set)
441 {
442 	struct nft_rhash *priv = nft_set_priv(set);
443 	struct nft_rhash_ctx rhash_ctx = {
444 		.ctx	= *ctx,
445 		.set	= set,
446 	};
447 
448 	cancel_delayed_work_sync(&priv->gc_work);
449 	rhashtable_free_and_destroy(&priv->ht, nft_rhash_elem_destroy,
450 				    (void *)&rhash_ctx);
451 }
452 
453 /* Number of buckets is stored in u32, so cap our result to 1U<<31 */
454 #define NFT_MAX_BUCKETS (1U << 31)
455 
456 static u32 nft_hash_buckets(u32 size)
457 {
458 	u64 val = div_u64((u64)size * 4, 3);
459 
460 	if (val >= NFT_MAX_BUCKETS)
461 		return NFT_MAX_BUCKETS;
462 
463 	return roundup_pow_of_two(val);
464 }
465 
466 static bool nft_rhash_estimate(const struct nft_set_desc *desc, u32 features,
467 			       struct nft_set_estimate *est)
468 {
469 	est->size   = ~0;
470 	est->lookup = NFT_SET_CLASS_O_1;
471 	est->space  = NFT_SET_CLASS_O_N;
472 
473 	return true;
474 }
475 
476 struct nft_hash {
477 	u32				seed;
478 	u32				buckets;
479 	struct hlist_head		table[];
480 };
481 
482 struct nft_hash_elem {
483 	struct nft_elem_priv		priv;
484 	struct hlist_node		node;
485 	struct nft_set_ext		ext;
486 };
487 
488 INDIRECT_CALLABLE_SCOPE
489 bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
490 		     const u32 *key, const struct nft_set_ext **ext)
491 {
492 	struct nft_hash *priv = nft_set_priv(set);
493 	u8 genmask = nft_genmask_cur(net);
494 	const struct nft_hash_elem *he;
495 	u32 hash;
496 
497 	hash = jhash(key, set->klen, priv->seed);
498 	hash = reciprocal_scale(hash, priv->buckets);
499 	hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
500 		if (!memcmp(nft_set_ext_key(&he->ext), key, set->klen) &&
501 		    nft_set_elem_active(&he->ext, genmask)) {
502 			*ext = &he->ext;
503 			return true;
504 		}
505 	}
506 	return false;
507 }
508 
509 static struct nft_elem_priv *
510 nft_hash_get(const struct net *net, const struct nft_set *set,
511 	     const struct nft_set_elem *elem, unsigned int flags)
512 {
513 	struct nft_hash *priv = nft_set_priv(set);
514 	u8 genmask = nft_genmask_cur(net);
515 	struct nft_hash_elem *he;
516 	u32 hash;
517 
518 	hash = jhash(elem->key.val.data, set->klen, priv->seed);
519 	hash = reciprocal_scale(hash, priv->buckets);
520 	hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
521 		if (!memcmp(nft_set_ext_key(&he->ext), elem->key.val.data, set->klen) &&
522 		    nft_set_elem_active(&he->ext, genmask))
523 			return &he->priv;
524 	}
525 	return ERR_PTR(-ENOENT);
526 }
527 
528 INDIRECT_CALLABLE_SCOPE
529 bool nft_hash_lookup_fast(const struct net *net,
530 			  const struct nft_set *set,
531 			  const u32 *key, const struct nft_set_ext **ext)
532 {
533 	struct nft_hash *priv = nft_set_priv(set);
534 	u8 genmask = nft_genmask_cur(net);
535 	const struct nft_hash_elem *he;
536 	u32 hash, k1, k2;
537 
538 	k1 = *key;
539 	hash = jhash_1word(k1, priv->seed);
540 	hash = reciprocal_scale(hash, priv->buckets);
541 	hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
542 		k2 = *(u32 *)nft_set_ext_key(&he->ext)->data;
543 		if (k1 == k2 &&
544 		    nft_set_elem_active(&he->ext, genmask)) {
545 			*ext = &he->ext;
546 			return true;
547 		}
548 	}
549 	return false;
550 }
551 
552 static u32 nft_jhash(const struct nft_set *set, const struct nft_hash *priv,
553 		     const struct nft_set_ext *ext)
554 {
555 	const struct nft_data *key = nft_set_ext_key(ext);
556 	u32 hash, k1;
557 
558 	if (set->klen == 4) {
559 		k1 = *(u32 *)key;
560 		hash = jhash_1word(k1, priv->seed);
561 	} else {
562 		hash = jhash(key, set->klen, priv->seed);
563 	}
564 	hash = reciprocal_scale(hash, priv->buckets);
565 
566 	return hash;
567 }
568 
569 static int nft_hash_insert(const struct net *net, const struct nft_set *set,
570 			   const struct nft_set_elem *elem,
571 			   struct nft_elem_priv **elem_priv)
572 {
573 	struct nft_hash_elem *this = nft_elem_priv_cast(elem->priv), *he;
574 	struct nft_hash *priv = nft_set_priv(set);
575 	u8 genmask = nft_genmask_next(net);
576 	u32 hash;
577 
578 	hash = nft_jhash(set, priv, &this->ext);
579 	hlist_for_each_entry(he, &priv->table[hash], node) {
580 		if (!memcmp(nft_set_ext_key(&this->ext),
581 			    nft_set_ext_key(&he->ext), set->klen) &&
582 		    nft_set_elem_active(&he->ext, genmask)) {
583 			*elem_priv = &he->priv;
584 			return -EEXIST;
585 		}
586 	}
587 	hlist_add_head_rcu(&this->node, &priv->table[hash]);
588 	return 0;
589 }
590 
591 static void nft_hash_activate(const struct net *net, const struct nft_set *set,
592 			      struct nft_elem_priv *elem_priv)
593 {
594 	struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
595 
596 	nft_set_elem_change_active(net, set, &he->ext);
597 }
598 
599 static void nft_hash_flush(const struct net *net,
600 			   const struct nft_set *set,
601 			   struct nft_elem_priv *elem_priv)
602 {
603 	struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
604 
605 	nft_set_elem_change_active(net, set, &he->ext);
606 }
607 
608 static struct nft_elem_priv *
609 nft_hash_deactivate(const struct net *net, const struct nft_set *set,
610 		    const struct nft_set_elem *elem)
611 {
612 	struct nft_hash_elem *this = nft_elem_priv_cast(elem->priv), *he;
613 	struct nft_hash *priv = nft_set_priv(set);
614 	u8 genmask = nft_genmask_next(net);
615 	u32 hash;
616 
617 	hash = nft_jhash(set, priv, &this->ext);
618 	hlist_for_each_entry(he, &priv->table[hash], node) {
619 		if (!memcmp(nft_set_ext_key(&he->ext), &elem->key.val,
620 			    set->klen) &&
621 		    nft_set_elem_active(&he->ext, genmask)) {
622 			nft_set_elem_change_active(net, set, &he->ext);
623 			return &he->priv;
624 		}
625 	}
626 	return NULL;
627 }
628 
629 static void nft_hash_remove(const struct net *net,
630 			    const struct nft_set *set,
631 			    struct nft_elem_priv *elem_priv)
632 {
633 	struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
634 
635 	hlist_del_rcu(&he->node);
636 }
637 
638 static void nft_hash_walk(const struct nft_ctx *ctx, struct nft_set *set,
639 			  struct nft_set_iter *iter)
640 {
641 	struct nft_hash *priv = nft_set_priv(set);
642 	struct nft_hash_elem *he;
643 	int i;
644 
645 	for (i = 0; i < priv->buckets; i++) {
646 		hlist_for_each_entry_rcu(he, &priv->table[i], node) {
647 			if (iter->count < iter->skip)
648 				goto cont;
649 			if (!nft_set_elem_active(&he->ext, iter->genmask))
650 				goto cont;
651 
652 			iter->err = iter->fn(ctx, set, iter, &he->priv);
653 			if (iter->err < 0)
654 				return;
655 cont:
656 			iter->count++;
657 		}
658 	}
659 }
660 
661 static u64 nft_hash_privsize(const struct nlattr * const nla[],
662 			     const struct nft_set_desc *desc)
663 {
664 	return sizeof(struct nft_hash) +
665 	       (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head);
666 }
667 
668 static int nft_hash_init(const struct nft_set *set,
669 			 const struct nft_set_desc *desc,
670 			 const struct nlattr * const tb[])
671 {
672 	struct nft_hash *priv = nft_set_priv(set);
673 
674 	priv->buckets = nft_hash_buckets(desc->size);
675 	get_random_bytes(&priv->seed, sizeof(priv->seed));
676 
677 	return 0;
678 }
679 
680 static void nft_hash_destroy(const struct nft_ctx *ctx,
681 			     const struct nft_set *set)
682 {
683 	struct nft_hash *priv = nft_set_priv(set);
684 	struct nft_hash_elem *he;
685 	struct hlist_node *next;
686 	int i;
687 
688 	for (i = 0; i < priv->buckets; i++) {
689 		hlist_for_each_entry_safe(he, next, &priv->table[i], node) {
690 			hlist_del_rcu(&he->node);
691 			nf_tables_set_elem_destroy(ctx, set, &he->priv);
692 		}
693 	}
694 }
695 
696 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
697 			      struct nft_set_estimate *est)
698 {
699 	if (!desc->size)
700 		return false;
701 
702 	if (desc->klen == 4)
703 		return false;
704 
705 	est->size   = sizeof(struct nft_hash) +
706 		      (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head) +
707 		      (u64)desc->size * sizeof(struct nft_hash_elem);
708 	est->lookup = NFT_SET_CLASS_O_1;
709 	est->space  = NFT_SET_CLASS_O_N;
710 
711 	return true;
712 }
713 
714 static bool nft_hash_fast_estimate(const struct nft_set_desc *desc, u32 features,
715 				   struct nft_set_estimate *est)
716 {
717 	if (!desc->size)
718 		return false;
719 
720 	if (desc->klen != 4)
721 		return false;
722 
723 	est->size   = sizeof(struct nft_hash) +
724 		      (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head) +
725 		      (u64)desc->size * sizeof(struct nft_hash_elem);
726 	est->lookup = NFT_SET_CLASS_O_1;
727 	est->space  = NFT_SET_CLASS_O_N;
728 
729 	return true;
730 }
731 
732 const struct nft_set_type nft_set_rhash_type = {
733 	.features	= NFT_SET_MAP | NFT_SET_OBJECT |
734 			  NFT_SET_TIMEOUT | NFT_SET_EVAL,
735 	.ops		= {
736 		.privsize       = nft_rhash_privsize,
737 		.elemsize	= offsetof(struct nft_rhash_elem, ext),
738 		.estimate	= nft_rhash_estimate,
739 		.init		= nft_rhash_init,
740 		.gc_init	= nft_rhash_gc_init,
741 		.destroy	= nft_rhash_destroy,
742 		.insert		= nft_rhash_insert,
743 		.activate	= nft_rhash_activate,
744 		.deactivate	= nft_rhash_deactivate,
745 		.flush		= nft_rhash_flush,
746 		.remove		= nft_rhash_remove,
747 		.lookup		= nft_rhash_lookup,
748 		.update		= nft_rhash_update,
749 		.delete		= nft_rhash_delete,
750 		.walk		= nft_rhash_walk,
751 		.get		= nft_rhash_get,
752 	},
753 };
754 
755 const struct nft_set_type nft_set_hash_type = {
756 	.features	= NFT_SET_MAP | NFT_SET_OBJECT,
757 	.ops		= {
758 		.privsize       = nft_hash_privsize,
759 		.elemsize	= offsetof(struct nft_hash_elem, ext),
760 		.estimate	= nft_hash_estimate,
761 		.init		= nft_hash_init,
762 		.destroy	= nft_hash_destroy,
763 		.insert		= nft_hash_insert,
764 		.activate	= nft_hash_activate,
765 		.deactivate	= nft_hash_deactivate,
766 		.flush		= nft_hash_flush,
767 		.remove		= nft_hash_remove,
768 		.lookup		= nft_hash_lookup,
769 		.walk		= nft_hash_walk,
770 		.get		= nft_hash_get,
771 	},
772 };
773 
774 const struct nft_set_type nft_set_hash_fast_type = {
775 	.features	= NFT_SET_MAP | NFT_SET_OBJECT,
776 	.ops		= {
777 		.privsize       = nft_hash_privsize,
778 		.elemsize	= offsetof(struct nft_hash_elem, ext),
779 		.estimate	= nft_hash_fast_estimate,
780 		.init		= nft_hash_init,
781 		.destroy	= nft_hash_destroy,
782 		.insert		= nft_hash_insert,
783 		.activate	= nft_hash_activate,
784 		.deactivate	= nft_hash_deactivate,
785 		.flush		= nft_hash_flush,
786 		.remove		= nft_hash_remove,
787 		.lookup		= nft_hash_lookup_fast,
788 		.walk		= nft_hash_walk,
789 		.get		= nft_hash_get,
790 	},
791 };
792