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/rhashtable.h>
19 #include <linux/netfilter.h>
20 #include <linux/netfilter/nf_tables.h>
21 #include <net/netfilter/nf_tables.h>
23 /* We target a hash table size of 4, element hint is 75% of final size */
24 #define NFT_HASH_ELEMENT_HINT 3
30 struct nft_hash_elem
{
31 struct rhash_head node
;
32 struct nft_set_ext ext
;
35 struct nft_hash_cmp_arg
{
36 const struct nft_set
*set
;
37 const struct nft_data
*key
;
41 static const struct rhashtable_params nft_hash_params
;
43 static inline u32
nft_hash_key(const void *data
, u32 len
, u32 seed
)
45 const struct nft_hash_cmp_arg
*arg
= data
;
47 return jhash(arg
->key
, len
, seed
);
50 static inline u32
nft_hash_obj(const void *data
, u32 len
, u32 seed
)
52 const struct nft_hash_elem
*he
= data
;
54 return jhash(nft_set_ext_key(&he
->ext
), len
, seed
);
57 static inline int nft_hash_cmp(struct rhashtable_compare_arg
*arg
,
60 const struct nft_hash_cmp_arg
*x
= arg
->key
;
61 const struct nft_hash_elem
*he
= ptr
;
63 if (nft_data_cmp(nft_set_ext_key(&he
->ext
), x
->key
, x
->set
->klen
))
65 if (!nft_set_elem_active(&he
->ext
, x
->genmask
))
70 static bool nft_hash_lookup(const struct nft_set
*set
,
71 const struct nft_data
*key
,
72 const struct nft_set_ext
**ext
)
74 struct nft_hash
*priv
= nft_set_priv(set
);
75 const struct nft_hash_elem
*he
;
76 struct nft_hash_cmp_arg arg
= {
77 .genmask
= nft_genmask_cur(read_pnet(&set
->pnet
)),
82 he
= rhashtable_lookup_fast(&priv
->ht
, &arg
, nft_hash_params
);
89 static int nft_hash_insert(const struct nft_set
*set
,
90 const struct nft_set_elem
*elem
)
92 struct nft_hash
*priv
= nft_set_priv(set
);
93 struct nft_hash_elem
*he
= elem
->priv
;
94 struct nft_hash_cmp_arg arg
= {
95 .genmask
= nft_genmask_next(read_pnet(&set
->pnet
)),
100 return rhashtable_lookup_insert_key(&priv
->ht
, &arg
, &he
->node
,
104 static void nft_hash_activate(const struct nft_set
*set
,
105 const struct nft_set_elem
*elem
)
107 struct nft_hash_elem
*he
= elem
->priv
;
109 nft_set_elem_change_active(set
, &he
->ext
);
112 static void *nft_hash_deactivate(const struct nft_set
*set
,
113 const struct nft_set_elem
*elem
)
115 struct nft_hash
*priv
= nft_set_priv(set
);
116 struct nft_hash_elem
*he
;
117 struct nft_hash_cmp_arg arg
= {
118 .genmask
= nft_genmask_next(read_pnet(&set
->pnet
)),
123 he
= rhashtable_lookup_fast(&priv
->ht
, &arg
, nft_hash_params
);
125 nft_set_elem_change_active(set
, &he
->ext
);
130 static void nft_hash_remove(const struct nft_set
*set
,
131 const struct nft_set_elem
*elem
)
133 struct nft_hash
*priv
= nft_set_priv(set
);
134 struct nft_hash_elem
*he
= elem
->priv
;
136 rhashtable_remove_fast(&priv
->ht
, &he
->node
, nft_hash_params
);
139 static void nft_hash_walk(const struct nft_ctx
*ctx
, const struct nft_set
*set
,
140 struct nft_set_iter
*iter
)
142 struct nft_hash
*priv
= nft_set_priv(set
);
143 struct nft_hash_elem
*he
;
144 struct rhashtable_iter hti
;
145 struct nft_set_elem elem
;
146 u8 genmask
= nft_genmask_cur(read_pnet(&set
->pnet
));
149 err
= rhashtable_walk_init(&priv
->ht
, &hti
);
154 err
= rhashtable_walk_start(&hti
);
155 if (err
&& err
!= -EAGAIN
) {
160 while ((he
= rhashtable_walk_next(&hti
))) {
163 if (err
!= -EAGAIN
) {
171 if (iter
->count
< iter
->skip
)
173 if (!nft_set_elem_active(&he
->ext
, genmask
))
178 iter
->err
= iter
->fn(ctx
, set
, iter
, &elem
);
187 rhashtable_walk_stop(&hti
);
188 rhashtable_walk_exit(&hti
);
191 static unsigned int nft_hash_privsize(const struct nlattr
* const nla
[])
193 return sizeof(struct nft_hash
);
196 static const struct rhashtable_params nft_hash_params
= {
197 .head_offset
= offsetof(struct nft_hash_elem
, node
),
198 .hashfn
= nft_hash_key
,
199 .obj_hashfn
= nft_hash_obj
,
200 .obj_cmpfn
= nft_hash_cmp
,
201 .automatic_shrinking
= true,
204 static int nft_hash_init(const struct nft_set
*set
,
205 const struct nft_set_desc
*desc
,
206 const struct nlattr
* const tb
[])
208 struct nft_hash
*priv
= nft_set_priv(set
);
209 struct rhashtable_params params
= nft_hash_params
;
211 params
.nelem_hint
= desc
->size
?: NFT_HASH_ELEMENT_HINT
;
212 params
.key_len
= set
->klen
;
214 return rhashtable_init(&priv
->ht
, ¶ms
);
217 static void nft_hash_elem_destroy(void *ptr
, void *arg
)
219 nft_set_elem_destroy((const struct nft_set
*)arg
, ptr
);
222 static void nft_hash_destroy(const struct nft_set
*set
)
224 struct nft_hash
*priv
= nft_set_priv(set
);
226 rhashtable_free_and_destroy(&priv
->ht
, nft_hash_elem_destroy
,
230 static bool nft_hash_estimate(const struct nft_set_desc
*desc
, u32 features
,
231 struct nft_set_estimate
*est
)
235 esize
= sizeof(struct nft_hash_elem
);
237 est
->size
= sizeof(struct nft_hash
) +
238 roundup_pow_of_two(desc
->size
* 4 / 3) *
239 sizeof(struct nft_hash_elem
*) +
242 /* Resizing happens when the load drops below 30% or goes
243 * above 75%. The average of 52.5% load (approximated by 50%)
244 * is used for the size estimation of the hash buckets,
245 * meaning we calculate two buckets per element.
247 est
->size
= esize
+ 2 * sizeof(struct nft_hash_elem
*);
250 est
->class = NFT_SET_CLASS_O_1
;
255 static struct nft_set_ops nft_hash_ops __read_mostly
= {
256 .privsize
= nft_hash_privsize
,
257 .elemsize
= offsetof(struct nft_hash_elem
, ext
),
258 .estimate
= nft_hash_estimate
,
259 .init
= nft_hash_init
,
260 .destroy
= nft_hash_destroy
,
261 .insert
= nft_hash_insert
,
262 .activate
= nft_hash_activate
,
263 .deactivate
= nft_hash_deactivate
,
264 .remove
= nft_hash_remove
,
265 .lookup
= nft_hash_lookup
,
266 .walk
= nft_hash_walk
,
267 .features
= NFT_SET_MAP
,
268 .owner
= THIS_MODULE
,
271 static int __init
nft_hash_module_init(void)
273 return nft_register_set(&nft_hash_ops
);
276 static void __exit
nft_hash_module_exit(void)
278 nft_unregister_set(&nft_hash_ops
);
281 module_init(nft_hash_module_init
);
282 module_exit(nft_hash_module_exit
);
284 MODULE_LICENSE("GPL");
285 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
286 MODULE_ALIAS_NFT_SET();