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/jhash.h>
16 #include <linux/netlink.h>
17 #include <linux/vmalloc.h>
18 #include <linux/netfilter.h>
19 #include <linux/netfilter/nf_tables.h>
20 #include <net/netfilter/nf_tables.h>
22 #define NFT_HASH_MIN_SIZE 4
25 struct nft_hash_table __rcu
*tbl
;
28 struct nft_hash_table
{
30 unsigned int elements
;
31 struct nft_hash_elem __rcu
*buckets
[];
34 struct nft_hash_elem
{
35 struct nft_hash_elem __rcu
*next
;
37 struct nft_data data
[];
40 #define nft_hash_for_each_entry(i, head) \
41 for (i = nft_dereference(head); i != NULL; i = nft_dereference(i->next))
42 #define nft_hash_for_each_entry_rcu(i, head) \
43 for (i = rcu_dereference(head); i != NULL; i = rcu_dereference(i->next))
45 static u32 nft_hash_rnd __read_mostly
;
46 static bool nft_hash_rnd_initted __read_mostly
;
48 static unsigned int nft_hash_data(const struct nft_data
*data
,
49 unsigned int hsize
, unsigned int len
)
53 h
= jhash(data
->data
, len
, nft_hash_rnd
);
54 return h
& (hsize
- 1);
57 static bool nft_hash_lookup(const struct nft_set
*set
,
58 const struct nft_data
*key
,
59 struct nft_data
*data
)
61 const struct nft_hash
*priv
= nft_set_priv(set
);
62 const struct nft_hash_table
*tbl
= rcu_dereference(priv
->tbl
);
63 const struct nft_hash_elem
*he
;
66 h
= nft_hash_data(key
, tbl
->size
, set
->klen
);
67 nft_hash_for_each_entry_rcu(he
, tbl
->buckets
[h
]) {
68 if (nft_data_cmp(&he
->key
, key
, set
->klen
))
70 if (set
->flags
& NFT_SET_MAP
)
71 nft_data_copy(data
, he
->data
);
77 static void nft_hash_tbl_free(const struct nft_hash_table
*tbl
)
79 if (is_vmalloc_addr(tbl
))
85 static struct nft_hash_table
*nft_hash_tbl_alloc(unsigned int nbuckets
)
87 struct nft_hash_table
*tbl
;
90 size
= sizeof(*tbl
) + nbuckets
* sizeof(tbl
->buckets
[0]);
91 tbl
= kzalloc(size
, GFP_KERNEL
| __GFP_REPEAT
| __GFP_NOWARN
);
101 static void nft_hash_chain_unzip(const struct nft_set
*set
,
102 const struct nft_hash_table
*ntbl
,
103 struct nft_hash_table
*tbl
, unsigned int n
)
105 struct nft_hash_elem
*he
, *last
, *next
;
108 he
= nft_dereference(tbl
->buckets
[n
]);
111 h
= nft_hash_data(&he
->key
, ntbl
->size
, set
->klen
);
113 /* Find last element of first chain hashing to bucket h */
115 nft_hash_for_each_entry(he
, he
->next
) {
116 if (nft_hash_data(&he
->key
, ntbl
->size
, set
->klen
) != h
)
121 /* Unlink first chain from the old table */
122 RCU_INIT_POINTER(tbl
->buckets
[n
], last
->next
);
124 /* If end of chain reached, done */
128 /* Find first element of second chain hashing to bucket h */
130 nft_hash_for_each_entry(he
, he
->next
) {
131 if (nft_hash_data(&he
->key
, ntbl
->size
, set
->klen
) != h
)
137 /* Link the two chains */
138 RCU_INIT_POINTER(last
->next
, next
);
141 static int nft_hash_tbl_expand(const struct nft_set
*set
, struct nft_hash
*priv
)
143 struct nft_hash_table
*tbl
= nft_dereference(priv
->tbl
), *ntbl
;
144 struct nft_hash_elem
*he
;
148 ntbl
= nft_hash_tbl_alloc(tbl
->size
* 2);
152 /* Link new table's buckets to first element in the old table
153 * hashing to the new bucket.
155 for (i
= 0; i
< ntbl
->size
; i
++) {
156 h
= i
< tbl
->size
? i
: i
- tbl
->size
;
157 nft_hash_for_each_entry(he
, tbl
->buckets
[h
]) {
158 if (nft_hash_data(&he
->key
, ntbl
->size
, set
->klen
) != i
)
160 RCU_INIT_POINTER(ntbl
->buckets
[i
], he
);
164 ntbl
->elements
= tbl
->elements
;
166 /* Publish new table */
167 rcu_assign_pointer(priv
->tbl
, ntbl
);
169 /* Unzip interleaved hash chains */
171 /* Wait for readers to use new table/unzipped chains */
175 for (i
= 0; i
< tbl
->size
; i
++) {
176 nft_hash_chain_unzip(set
, ntbl
, tbl
, i
);
177 if (tbl
->buckets
[i
] != NULL
)
182 nft_hash_tbl_free(tbl
);
186 static int nft_hash_tbl_shrink(const struct nft_set
*set
, struct nft_hash
*priv
)
188 struct nft_hash_table
*tbl
= nft_dereference(priv
->tbl
), *ntbl
;
189 struct nft_hash_elem __rcu
**pprev
;
192 ntbl
= nft_hash_tbl_alloc(tbl
->size
/ 2);
196 for (i
= 0; i
< ntbl
->size
; i
++) {
197 ntbl
->buckets
[i
] = tbl
->buckets
[i
];
199 for (pprev
= &ntbl
->buckets
[i
]; *pprev
!= NULL
;
200 pprev
= &nft_dereference(*pprev
)->next
)
202 RCU_INIT_POINTER(*pprev
, tbl
->buckets
[i
+ ntbl
->size
]);
204 ntbl
->elements
= tbl
->elements
;
206 /* Publish new table */
207 rcu_assign_pointer(priv
->tbl
, ntbl
);
210 nft_hash_tbl_free(tbl
);
214 static int nft_hash_insert(const struct nft_set
*set
,
215 const struct nft_set_elem
*elem
)
217 struct nft_hash
*priv
= nft_set_priv(set
);
218 struct nft_hash_table
*tbl
= nft_dereference(priv
->tbl
);
219 struct nft_hash_elem
*he
;
220 unsigned int size
, h
;
222 if (elem
->flags
!= 0)
226 if (set
->flags
& NFT_SET_MAP
)
227 size
+= sizeof(he
->data
[0]);
229 he
= kzalloc(size
, GFP_KERNEL
);
233 nft_data_copy(&he
->key
, &elem
->key
);
234 if (set
->flags
& NFT_SET_MAP
)
235 nft_data_copy(he
->data
, &elem
->data
);
237 h
= nft_hash_data(&he
->key
, tbl
->size
, set
->klen
);
238 RCU_INIT_POINTER(he
->next
, tbl
->buckets
[h
]);
239 rcu_assign_pointer(tbl
->buckets
[h
], he
);
242 /* Expand table when exceeding 75% load */
243 if (tbl
->elements
> tbl
->size
/ 4 * 3)
244 nft_hash_tbl_expand(set
, priv
);
249 static void nft_hash_elem_destroy(const struct nft_set
*set
,
250 struct nft_hash_elem
*he
)
252 nft_data_uninit(&he
->key
, NFT_DATA_VALUE
);
253 if (set
->flags
& NFT_SET_MAP
)
254 nft_data_uninit(he
->data
, set
->dtype
);
258 static void nft_hash_remove(const struct nft_set
*set
,
259 const struct nft_set_elem
*elem
)
261 struct nft_hash
*priv
= nft_set_priv(set
);
262 struct nft_hash_table
*tbl
= nft_dereference(priv
->tbl
);
263 struct nft_hash_elem
*he
, __rcu
**pprev
;
265 pprev
= elem
->cookie
;
266 he
= nft_dereference((*pprev
));
268 RCU_INIT_POINTER(*pprev
, he
->next
);
273 /* Shrink table beneath 30% load */
274 if (tbl
->elements
< tbl
->size
* 3 / 10 &&
275 tbl
->size
> NFT_HASH_MIN_SIZE
)
276 nft_hash_tbl_shrink(set
, priv
);
279 static int nft_hash_get(const struct nft_set
*set
, struct nft_set_elem
*elem
)
281 const struct nft_hash
*priv
= nft_set_priv(set
);
282 const struct nft_hash_table
*tbl
= nft_dereference(priv
->tbl
);
283 struct nft_hash_elem __rcu
* const *pprev
;
284 struct nft_hash_elem
*he
;
287 h
= nft_hash_data(&elem
->key
, tbl
->size
, set
->klen
);
288 pprev
= &tbl
->buckets
[h
];
289 nft_hash_for_each_entry(he
, tbl
->buckets
[h
]) {
290 if (nft_data_cmp(&he
->key
, &elem
->key
, set
->klen
)) {
295 elem
->cookie
= (void *)pprev
;
297 if (set
->flags
& NFT_SET_MAP
)
298 nft_data_copy(&elem
->data
, he
->data
);
304 static void nft_hash_walk(const struct nft_ctx
*ctx
, const struct nft_set
*set
,
305 struct nft_set_iter
*iter
)
307 const struct nft_hash
*priv
= nft_set_priv(set
);
308 const struct nft_hash_table
*tbl
= nft_dereference(priv
->tbl
);
309 const struct nft_hash_elem
*he
;
310 struct nft_set_elem elem
;
313 for (i
= 0; i
< tbl
->size
; i
++) {
314 nft_hash_for_each_entry(he
, tbl
->buckets
[i
]) {
315 if (iter
->count
< iter
->skip
)
318 memcpy(&elem
.key
, &he
->key
, sizeof(elem
.key
));
319 if (set
->flags
& NFT_SET_MAP
)
320 memcpy(&elem
.data
, he
->data
, sizeof(elem
.data
));
323 iter
->err
= iter
->fn(ctx
, set
, iter
, &elem
);
332 static unsigned int nft_hash_privsize(const struct nlattr
* const nla
[])
334 return sizeof(struct nft_hash
);
337 static int nft_hash_init(const struct nft_set
*set
,
338 const struct nlattr
* const tb
[])
340 struct nft_hash
*priv
= nft_set_priv(set
);
341 struct nft_hash_table
*tbl
;
343 if (unlikely(!nft_hash_rnd_initted
)) {
344 get_random_bytes(&nft_hash_rnd
, 4);
345 nft_hash_rnd_initted
= true;
348 tbl
= nft_hash_tbl_alloc(NFT_HASH_MIN_SIZE
);
351 RCU_INIT_POINTER(priv
->tbl
, tbl
);
355 static void nft_hash_destroy(const struct nft_set
*set
)
357 const struct nft_hash
*priv
= nft_set_priv(set
);
358 const struct nft_hash_table
*tbl
= nft_dereference(priv
->tbl
);
359 struct nft_hash_elem
*he
, *next
;
362 for (i
= 0; i
< tbl
->size
; i
++) {
363 for (he
= nft_dereference(tbl
->buckets
[i
]); he
!= NULL
;
365 next
= nft_dereference(he
->next
);
366 nft_hash_elem_destroy(set
, he
);
372 static struct nft_set_ops nft_hash_ops __read_mostly
= {
373 .privsize
= nft_hash_privsize
,
374 .init
= nft_hash_init
,
375 .destroy
= nft_hash_destroy
,
377 .insert
= nft_hash_insert
,
378 .remove
= nft_hash_remove
,
379 .lookup
= nft_hash_lookup
,
380 .walk
= nft_hash_walk
,
381 .features
= NFT_SET_MAP
,
382 .owner
= THIS_MODULE
,
385 static int __init
nft_hash_module_init(void)
387 return nft_register_set(&nft_hash_ops
);
390 static void __exit
nft_hash_module_exit(void)
392 nft_unregister_set(&nft_hash_ops
);
395 module_init(nft_hash_module_init
);
396 module_exit(nft_hash_module_exit
);
398 MODULE_LICENSE("GPL");
399 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
400 MODULE_ALIAS_NFT_SET();