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
26 struct nft_hash_elem
{
27 struct rhash_head node
;
29 struct nft_data data
[];
32 static const struct rhashtable_params nft_hash_params
;
34 static bool nft_hash_lookup(const struct nft_set
*set
,
35 const struct nft_data
*key
,
36 struct nft_data
*data
)
38 struct rhashtable
*priv
= nft_set_priv(set
);
39 const struct nft_hash_elem
*he
;
41 he
= rhashtable_lookup_fast(priv
, key
, nft_hash_params
);
42 if (he
&& set
->flags
& NFT_SET_MAP
)
43 nft_data_copy(data
, he
->data
);
48 static int nft_hash_insert(const struct nft_set
*set
,
49 const struct nft_set_elem
*elem
)
51 struct rhashtable
*priv
= nft_set_priv(set
);
52 struct nft_hash_elem
*he
;
60 if (set
->flags
& NFT_SET_MAP
)
61 size
+= sizeof(he
->data
[0]);
63 he
= kzalloc(size
, GFP_KERNEL
);
67 nft_data_copy(&he
->key
, &elem
->key
);
68 if (set
->flags
& NFT_SET_MAP
)
69 nft_data_copy(he
->data
, &elem
->data
);
71 err
= rhashtable_insert_fast(priv
, &he
->node
, nft_hash_params
);
78 static void nft_hash_elem_destroy(const struct nft_set
*set
,
79 struct nft_hash_elem
*he
)
81 nft_data_uninit(&he
->key
, NFT_DATA_VALUE
);
82 if (set
->flags
& NFT_SET_MAP
)
83 nft_data_uninit(he
->data
, set
->dtype
);
87 static void nft_hash_remove(const struct nft_set
*set
,
88 const struct nft_set_elem
*elem
)
90 struct rhashtable
*priv
= nft_set_priv(set
);
92 rhashtable_remove_fast(priv
, elem
->cookie
, nft_hash_params
);
97 static int nft_hash_get(const struct nft_set
*set
, struct nft_set_elem
*elem
)
99 struct rhashtable
*priv
= nft_set_priv(set
);
100 struct nft_hash_elem
*he
;
102 he
= rhashtable_lookup_fast(priv
, &elem
->key
, nft_hash_params
);
108 if (set
->flags
& NFT_SET_MAP
)
109 nft_data_copy(&elem
->data
, he
->data
);
114 static void nft_hash_walk(const struct nft_ctx
*ctx
, const struct nft_set
*set
,
115 struct nft_set_iter
*iter
)
117 struct rhashtable
*priv
= nft_set_priv(set
);
118 const struct nft_hash_elem
*he
;
119 struct rhashtable_iter hti
;
120 struct nft_set_elem elem
;
123 err
= rhashtable_walk_init(priv
, &hti
);
128 err
= rhashtable_walk_start(&hti
);
129 if (err
&& err
!= -EAGAIN
) {
134 while ((he
= rhashtable_walk_next(&hti
))) {
137 if (err
!= -EAGAIN
) {
145 if (iter
->count
< iter
->skip
)
148 memcpy(&elem
.key
, &he
->key
, sizeof(elem
.key
));
149 if (set
->flags
& NFT_SET_MAP
)
150 memcpy(&elem
.data
, he
->data
, sizeof(elem
.data
));
153 iter
->err
= iter
->fn(ctx
, set
, iter
, &elem
);
162 rhashtable_walk_stop(&hti
);
163 rhashtable_walk_exit(&hti
);
166 static unsigned int nft_hash_privsize(const struct nlattr
* const nla
[])
168 return sizeof(struct rhashtable
);
171 static const struct rhashtable_params nft_hash_params
= {
172 .head_offset
= offsetof(struct nft_hash_elem
, node
),
173 .key_offset
= offsetof(struct nft_hash_elem
, key
),
175 .automatic_shrinking
= true,
178 static int nft_hash_init(const struct nft_set
*set
,
179 const struct nft_set_desc
*desc
,
180 const struct nlattr
* const tb
[])
182 struct rhashtable
*priv
= nft_set_priv(set
);
183 struct rhashtable_params params
= nft_hash_params
;
185 params
.nelem_hint
= desc
->size
?: NFT_HASH_ELEMENT_HINT
;
186 params
.key_len
= set
->klen
;
188 return rhashtable_init(priv
, ¶ms
);
191 static void nft_free_element(void *ptr
, void *arg
)
193 nft_hash_elem_destroy((const struct nft_set
*)arg
, ptr
);
196 static void nft_hash_destroy(const struct nft_set
*set
)
198 rhashtable_free_and_destroy(nft_set_priv(set
), nft_free_element
,
202 static bool nft_hash_estimate(const struct nft_set_desc
*desc
, u32 features
,
203 struct nft_set_estimate
*est
)
207 esize
= sizeof(struct nft_hash_elem
);
208 if (features
& NFT_SET_MAP
)
209 esize
+= FIELD_SIZEOF(struct nft_hash_elem
, data
[0]);
212 est
->size
= sizeof(struct rhashtable
) +
213 roundup_pow_of_two(desc
->size
* 4 / 3) *
214 sizeof(struct nft_hash_elem
*) +
217 /* Resizing happens when the load drops below 30% or goes
218 * above 75%. The average of 52.5% load (approximated by 50%)
219 * is used for the size estimation of the hash buckets,
220 * meaning we calculate two buckets per element.
222 est
->size
= esize
+ 2 * sizeof(struct nft_hash_elem
*);
225 est
->class = NFT_SET_CLASS_O_1
;
230 static struct nft_set_ops nft_hash_ops __read_mostly
= {
231 .privsize
= nft_hash_privsize
,
232 .estimate
= nft_hash_estimate
,
233 .init
= nft_hash_init
,
234 .destroy
= nft_hash_destroy
,
236 .insert
= nft_hash_insert
,
237 .remove
= nft_hash_remove
,
238 .lookup
= nft_hash_lookup
,
239 .walk
= nft_hash_walk
,
240 .features
= NFT_SET_MAP
,
241 .owner
= THIS_MODULE
,
244 static int __init
nft_hash_module_init(void)
246 return nft_register_set(&nft_hash_ops
);
249 static void __exit
nft_hash_module_exit(void)
251 nft_unregister_set(&nft_hash_ops
);
254 module_init(nft_hash_module_init
);
255 module_exit(nft_hash_module_exit
);
257 MODULE_LICENSE("GPL");
258 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
259 MODULE_ALIAS_NFT_SET();