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