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(key: arg->key, length: len, initval: 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(key: nft_set_ext_key(ext: &he->ext), length: len, initval: 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(p: nft_set_ext_key(ext: &he->ext), q: x->key, size: x->set->klen)) |
62 | return 1; |
63 | if (nft_set_elem_is_dead(ext: &he->ext)) |
64 | return 1; |
65 | if (nft_set_elem_expired(ext: &he->ext)) |
66 | return 1; |
67 | if (!nft_set_elem_active(ext: &he->ext, genmask: 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(ht: &priv->ht, key: &arg, params: 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(ht: &priv->ht, key: &arg, params: nft_rhash_params); |
112 | if (he != NULL) |
113 | return &he->priv; |
114 | |
115 | return ERR_PTR(error: -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(ht: &priv->ht, key: &arg, params: 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(priv: elem_priv); |
145 | prev = rhashtable_lookup_get_insert_key(ht: &priv->ht, key: &arg, obj: &he->node, |
146 | params: nft_rhash_params); |
147 | if (IS_ERR(ptr: 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, elem_priv: &he->priv, destroy_expr: true); |
153 | atomic_dec(v: &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, elem_priv: &he->priv, destroy_expr: true); |
163 | atomic_dec(v: &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(priv: 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(ht: &priv->ht, key: &arg, obj: &he->node, |
182 | params: nft_rhash_params); |
183 | if (IS_ERR(ptr: prev)) |
184 | return PTR_ERR(ptr: 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(priv: elem_priv); |
196 | |
197 | nft_set_elem_change_active(net, set, ext: &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(priv: elem_priv); |
205 | |
206 | nft_set_elem_change_active(net, set, ext: &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(ht: &priv->ht, key: &arg, params: nft_rhash_params); |
223 | if (he) |
224 | nft_set_elem_change_active(net, set, ext: &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(priv: elem_priv); |
236 | struct nft_rhash *priv = nft_set_priv(set); |
237 | |
238 | rhashtable_remove_fast(ht: &priv->ht, obj: &he->node, params: 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(ht: &priv->ht, key: &arg, params: nft_rhash_params); |
253 | if (he == NULL) |
254 | return false; |
255 | |
256 | nft_set_elem_dead(ext: &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(ht: &priv->ht, iter: &hti); |
269 | rhashtable_walk_start(iter: &hti); |
270 | |
271 | while ((he = rhashtable_walk_next(iter: &hti))) { |
272 | if (IS_ERR(ptr: he)) { |
273 | if (PTR_ERR(ptr: he) != -EAGAIN) { |
274 | iter->err = PTR_ERR(ptr: he); |
275 | break; |
276 | } |
277 | |
278 | continue; |
279 | } |
280 | |
281 | if (iter->count < iter->skip) |
282 | goto cont; |
283 | if (!nft_set_elem_active(ext: &he->ext, genmask: 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(iter: &hti); |
294 | rhashtable_walk_exit(iter: &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(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(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(s: 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(ht: &priv->ht, iter: &hti); |
338 | rhashtable_walk_start(iter: &hti); |
339 | |
340 | while ((he = rhashtable_walk_next(iter: &hti))) { |
341 | if (IS_ERR(ptr: he)) { |
342 | nft_trans_gc_destroy(trans: 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(trans: gc); |
350 | gc = NULL; |
351 | goto try_later; |
352 | } |
353 | |
354 | if (nft_set_elem_is_dead(ext: &he->ext)) |
355 | goto dead_elem; |
356 | |
357 | if (nft_set_ext_exists(ext: &he->ext, id: NFT_SET_EXT_EXPRESSIONS) && |
358 | nft_rhash_expr_needs_gc_run(set, ext: &he->ext)) |
359 | goto needs_gc_run; |
360 | |
361 | if (!nft_set_elem_expired(ext: &he->ext)) |
362 | continue; |
363 | needs_gc_run: |
364 | nft_set_elem_dead(ext: &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, priv: 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(iter: &hti); |
378 | rhashtable_walk_exit(iter: &hti); |
379 | |
380 | if (gc) |
381 | nft_trans_gc_queue_async_done(gc); |
382 | |
383 | done: |
384 | queue_delayed_work(wq: system_power_efficient_wq, dwork: &priv->gc_work, |
385 | delay: 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(wq: system_power_efficient_wq, dwork: &priv->gc_work, |
399 | delay: 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(ht: &priv->ht, params: ¶ms); |
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(ctx: &rhash_ctx->ctx, set: rhash_ctx->set, elem_priv: &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(dwork: &priv->gc_work); |
449 | rhashtable_free_and_destroy(ht: &priv->ht, free_fn: nft_rhash_elem_destroy, |
450 | arg: (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(dividend: (u64)size * 4, divisor: 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, length: set->klen, initval: priv->seed); |
498 | hash = reciprocal_scale(val: hash, ep_ro: priv->buckets); |
499 | hlist_for_each_entry_rcu(he, &priv->table[hash], node) { |
500 | if (!memcmp(p: nft_set_ext_key(ext: &he->ext), q: key, size: set->klen) && |
501 | nft_set_elem_active(ext: &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(key: elem->key.val.data, length: set->klen, initval: priv->seed); |
519 | hash = reciprocal_scale(val: hash, ep_ro: priv->buckets); |
520 | hlist_for_each_entry_rcu(he, &priv->table[hash], node) { |
521 | if (!memcmp(p: nft_set_ext_key(ext: &he->ext), q: elem->key.val.data, size: set->klen) && |
522 | nft_set_elem_active(ext: &he->ext, genmask)) |
523 | return &he->priv; |
524 | } |
525 | return ERR_PTR(error: -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(a: k1, initval: priv->seed); |
540 | hash = reciprocal_scale(val: hash, ep_ro: priv->buckets); |
541 | hlist_for_each_entry_rcu(he, &priv->table[hash], node) { |
542 | k2 = *(u32 *)nft_set_ext_key(ext: &he->ext)->data; |
543 | if (k1 == k2 && |
544 | nft_set_elem_active(ext: &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(a: k1, initval: priv->seed); |
561 | } else { |
562 | hash = jhash(key, length: set->klen, initval: priv->seed); |
563 | } |
564 | hash = reciprocal_scale(val: hash, ep_ro: 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(priv: 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, ext: &this->ext); |
579 | hlist_for_each_entry(he, &priv->table[hash], node) { |
580 | if (!memcmp(p: nft_set_ext_key(ext: &this->ext), |
581 | q: nft_set_ext_key(ext: &he->ext), size: set->klen) && |
582 | nft_set_elem_active(ext: &he->ext, genmask)) { |
583 | *elem_priv = &he->priv; |
584 | return -EEXIST; |
585 | } |
586 | } |
587 | hlist_add_head_rcu(n: &this->node, h: &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(priv: elem_priv); |
595 | |
596 | nft_set_elem_change_active(net, set, ext: &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(priv: elem_priv); |
604 | |
605 | nft_set_elem_change_active(net, set, ext: &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(priv: 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, ext: &this->ext); |
618 | hlist_for_each_entry(he, &priv->table[hash], node) { |
619 | if (!memcmp(p: nft_set_ext_key(ext: &he->ext), q: &elem->key.val, |
620 | size: set->klen) && |
621 | nft_set_elem_active(ext: &he->ext, genmask)) { |
622 | nft_set_elem_change_active(net, set, ext: &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(priv: elem_priv); |
634 | |
635 | hlist_del_rcu(n: &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(ext: &he->ext, genmask: 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(size: 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(size: desc->size); |
675 | get_random_bytes(buf: &priv->seed, len: 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(n: &he->node); |
691 | nf_tables_set_elem_destroy(ctx, set, elem_priv: &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(size: 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(size: 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 | |