2 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation.
8 * Development of this code funded by Astaro AG (http://www.astaro.com/)
11 #include <linux/kernel.h>
12 #include <linux/init.h>
13 #include <linux/module.h>
14 #include <linux/list.h>
15 #include <linux/log2.h>
16 #include <linux/jhash.h>
17 #include <linux/netlink.h>
18 #include <linux/workqueue.h>
19 #include <linux/rhashtable.h>
20 #include <linux/netfilter.h>
21 #include <linux/netfilter/nf_tables.h>
22 #include <net/netfilter/nf_tables.h>
24 /* We target a hash table size of 4, element hint is 75% of final size */
25 #define NFT_HASH_ELEMENT_HINT 3
29 struct delayed_work gc_work
;
32 struct nft_hash_elem
{
33 struct rhash_head node
;
34 struct nft_set_ext ext
;
37 struct nft_hash_cmp_arg
{
38 const struct nft_set
*set
;
43 static const struct rhashtable_params nft_hash_params
;
45 static inline u32
nft_hash_key(const void *data
, u32 len
, u32 seed
)
47 const struct nft_hash_cmp_arg
*arg
= data
;
49 return jhash(arg
->key
, len
, seed
);
52 static inline u32
nft_hash_obj(const void *data
, u32 len
, u32 seed
)
54 const struct nft_hash_elem
*he
= data
;
56 return jhash(nft_set_ext_key(&he
->ext
), len
, seed
);
59 static inline int nft_hash_cmp(struct rhashtable_compare_arg
*arg
,
62 const struct nft_hash_cmp_arg
*x
= arg
->key
;
63 const struct nft_hash_elem
*he
= ptr
;
65 if (memcmp(nft_set_ext_key(&he
->ext
), x
->key
, x
->set
->klen
))
67 if (nft_set_elem_expired(&he
->ext
))
69 if (!nft_set_elem_active(&he
->ext
, x
->genmask
))
74 static bool nft_hash_lookup(const struct net
*net
, const struct nft_set
*set
,
75 const u32
*key
, const struct nft_set_ext
**ext
)
77 struct nft_hash
*priv
= nft_set_priv(set
);
78 const struct nft_hash_elem
*he
;
79 struct nft_hash_cmp_arg arg
= {
80 .genmask
= nft_genmask_cur(net
),
85 he
= rhashtable_lookup_fast(&priv
->ht
, &arg
, nft_hash_params
);
92 static bool nft_hash_update(struct nft_set
*set
, const u32
*key
,
93 void *(*new)(struct nft_set
*,
94 const struct nft_expr
*,
95 struct nft_regs
*regs
),
96 const struct nft_expr
*expr
,
97 struct nft_regs
*regs
,
98 const struct nft_set_ext
**ext
)
100 struct nft_hash
*priv
= nft_set_priv(set
);
101 struct nft_hash_elem
*he
, *prev
;
102 struct nft_hash_cmp_arg arg
= {
103 .genmask
= NFT_GENMASK_ANY
,
108 he
= rhashtable_lookup_fast(&priv
->ht
, &arg
, nft_hash_params
);
112 he
= new(set
, expr
, regs
);
116 prev
= rhashtable_lookup_get_insert_key(&priv
->ht
, &arg
, &he
->node
,
121 /* Another cpu may race to insert the element with the same key */
123 nft_set_elem_destroy(set
, he
, true);
132 nft_set_elem_destroy(set
, he
, true);
137 static int nft_hash_insert(const struct net
*net
, const struct nft_set
*set
,
138 const struct nft_set_elem
*elem
,
139 struct nft_set_ext
**ext
)
141 struct nft_hash
*priv
= nft_set_priv(set
);
142 struct nft_hash_elem
*he
= elem
->priv
;
143 struct nft_hash_cmp_arg arg
= {
144 .genmask
= nft_genmask_next(net
),
146 .key
= elem
->key
.val
.data
,
148 struct nft_hash_elem
*prev
;
150 prev
= rhashtable_lookup_get_insert_key(&priv
->ht
, &arg
, &he
->node
,
153 return PTR_ERR(prev
);
161 static void nft_hash_activate(const struct net
*net
, const struct nft_set
*set
,
162 const struct nft_set_elem
*elem
)
164 struct nft_hash_elem
*he
= elem
->priv
;
166 nft_set_elem_change_active(net
, set
, &he
->ext
);
167 nft_set_elem_clear_busy(&he
->ext
);
170 static bool nft_hash_deactivate_one(const struct net
*net
,
171 const struct nft_set
*set
, void *priv
)
173 struct nft_hash_elem
*he
= priv
;
175 if (!nft_set_elem_mark_busy(&he
->ext
) ||
176 !nft_is_active(net
, &he
->ext
)) {
177 nft_set_elem_change_active(net
, set
, &he
->ext
);
183 static void *nft_hash_deactivate(const struct net
*net
,
184 const struct nft_set
*set
,
185 const struct nft_set_elem
*elem
)
187 struct nft_hash
*priv
= nft_set_priv(set
);
188 struct nft_hash_elem
*he
;
189 struct nft_hash_cmp_arg arg
= {
190 .genmask
= nft_genmask_next(net
),
192 .key
= elem
->key
.val
.data
,
196 he
= rhashtable_lookup_fast(&priv
->ht
, &arg
, nft_hash_params
);
198 !nft_hash_deactivate_one(net
, set
, he
))
206 static void nft_hash_remove(const struct nft_set
*set
,
207 const struct nft_set_elem
*elem
)
209 struct nft_hash
*priv
= nft_set_priv(set
);
210 struct nft_hash_elem
*he
= elem
->priv
;
212 rhashtable_remove_fast(&priv
->ht
, &he
->node
, nft_hash_params
);
215 static void nft_hash_walk(const struct nft_ctx
*ctx
, struct nft_set
*set
,
216 struct nft_set_iter
*iter
)
218 struct nft_hash
*priv
= nft_set_priv(set
);
219 struct nft_hash_elem
*he
;
220 struct rhashtable_iter hti
;
221 struct nft_set_elem elem
;
224 err
= rhashtable_walk_init(&priv
->ht
, &hti
, GFP_KERNEL
);
229 err
= rhashtable_walk_start(&hti
);
230 if (err
&& err
!= -EAGAIN
) {
235 while ((he
= rhashtable_walk_next(&hti
))) {
238 if (err
!= -EAGAIN
) {
246 if (iter
->count
< iter
->skip
)
248 if (nft_set_elem_expired(&he
->ext
))
250 if (!nft_set_elem_active(&he
->ext
, iter
->genmask
))
255 iter
->err
= iter
->fn(ctx
, set
, iter
, &elem
);
264 rhashtable_walk_stop(&hti
);
265 rhashtable_walk_exit(&hti
);
268 static void nft_hash_gc(struct work_struct
*work
)
271 struct nft_hash_elem
*he
;
272 struct nft_hash
*priv
;
273 struct nft_set_gc_batch
*gcb
= NULL
;
274 struct rhashtable_iter hti
;
277 priv
= container_of(work
, struct nft_hash
, gc_work
.work
);
278 set
= nft_set_container_of(priv
);
280 err
= rhashtable_walk_init(&priv
->ht
, &hti
, GFP_KERNEL
);
284 err
= rhashtable_walk_start(&hti
);
285 if (err
&& err
!= -EAGAIN
)
288 while ((he
= rhashtable_walk_next(&hti
))) {
290 if (PTR_ERR(he
) != -EAGAIN
)
295 if (!nft_set_elem_expired(&he
->ext
))
297 if (nft_set_elem_mark_busy(&he
->ext
))
300 gcb
= nft_set_gc_batch_check(set
, gcb
, GFP_ATOMIC
);
303 rhashtable_remove_fast(&priv
->ht
, &he
->node
, nft_hash_params
);
304 atomic_dec(&set
->nelems
);
305 nft_set_gc_batch_add(gcb
, he
);
308 rhashtable_walk_stop(&hti
);
309 rhashtable_walk_exit(&hti
);
311 nft_set_gc_batch_complete(gcb
);
313 queue_delayed_work(system_power_efficient_wq
, &priv
->gc_work
,
314 nft_set_gc_interval(set
));
317 static unsigned int nft_hash_privsize(const struct nlattr
* const nla
[])
319 return sizeof(struct nft_hash
);
322 static const struct rhashtable_params nft_hash_params
= {
323 .head_offset
= offsetof(struct nft_hash_elem
, node
),
324 .hashfn
= nft_hash_key
,
325 .obj_hashfn
= nft_hash_obj
,
326 .obj_cmpfn
= nft_hash_cmp
,
327 .automatic_shrinking
= true,
330 static int nft_hash_init(const struct nft_set
*set
,
331 const struct nft_set_desc
*desc
,
332 const struct nlattr
* const tb
[])
334 struct nft_hash
*priv
= nft_set_priv(set
);
335 struct rhashtable_params params
= nft_hash_params
;
338 params
.nelem_hint
= desc
->size
?: NFT_HASH_ELEMENT_HINT
;
339 params
.key_len
= set
->klen
;
341 err
= rhashtable_init(&priv
->ht
, ¶ms
);
345 INIT_DEFERRABLE_WORK(&priv
->gc_work
, nft_hash_gc
);
346 if (set
->flags
& NFT_SET_TIMEOUT
)
347 queue_delayed_work(system_power_efficient_wq
, &priv
->gc_work
,
348 nft_set_gc_interval(set
));
352 static void nft_hash_elem_destroy(void *ptr
, void *arg
)
354 nft_set_elem_destroy((const struct nft_set
*)arg
, ptr
, true);
357 static void nft_hash_destroy(const struct nft_set
*set
)
359 struct nft_hash
*priv
= nft_set_priv(set
);
361 cancel_delayed_work_sync(&priv
->gc_work
);
362 rhashtable_free_and_destroy(&priv
->ht
, nft_hash_elem_destroy
,
366 static bool nft_hash_estimate(const struct nft_set_desc
*desc
, u32 features
,
367 struct nft_set_estimate
*est
)
371 esize
= sizeof(struct nft_hash_elem
);
373 est
->size
= sizeof(struct nft_hash
) +
374 roundup_pow_of_two(desc
->size
* 4 / 3) *
375 sizeof(struct nft_hash_elem
*) +
378 /* Resizing happens when the load drops below 30% or goes
379 * above 75%. The average of 52.5% load (approximated by 50%)
380 * is used for the size estimation of the hash buckets,
381 * meaning we calculate two buckets per element.
383 est
->size
= esize
+ 2 * sizeof(struct nft_hash_elem
*);
386 est
->class = NFT_SET_CLASS_O_1
;
391 static struct nft_set_ops nft_hash_ops __read_mostly
= {
392 .privsize
= nft_hash_privsize
,
393 .elemsize
= offsetof(struct nft_hash_elem
, ext
),
394 .estimate
= nft_hash_estimate
,
395 .init
= nft_hash_init
,
396 .destroy
= nft_hash_destroy
,
397 .insert
= nft_hash_insert
,
398 .activate
= nft_hash_activate
,
399 .deactivate
= nft_hash_deactivate
,
400 .deactivate_one
= nft_hash_deactivate_one
,
401 .remove
= nft_hash_remove
,
402 .lookup
= nft_hash_lookup
,
403 .update
= nft_hash_update
,
404 .walk
= nft_hash_walk
,
405 .features
= NFT_SET_MAP
| NFT_SET_TIMEOUT
,
406 .owner
= THIS_MODULE
,
409 static int __init
nft_hash_module_init(void)
411 return nft_register_set(&nft_hash_ops
);
414 static void __exit
nft_hash_module_exit(void)
416 nft_unregister_set(&nft_hash_ops
);
419 module_init(nft_hash_module_init
);
420 module_exit(nft_hash_module_exit
);
422 MODULE_LICENSE("GPL");
423 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
424 MODULE_ALIAS_NFT_SET();