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