2 * Copyright (c) 2008-2009 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/netfilter.h>
18 #include <linux/netfilter/nf_tables.h>
19 #include <net/netfilter/nf_tables.h>
22 struct hlist_head
*hash
;
26 struct nft_hash_elem
{
27 struct hlist_node hnode
;
29 struct nft_data data
[];
32 static u32 nft_hash_rnd __read_mostly
;
33 static bool nft_hash_rnd_initted __read_mostly
;
35 static unsigned int nft_hash_data(const struct nft_data
*data
,
36 unsigned int hsize
, unsigned int len
)
40 h
= jhash(data
->data
, len
, nft_hash_rnd
);
41 return ((u64
)h
* hsize
) >> 32;
44 static bool nft_hash_lookup(const struct nft_set
*set
,
45 const struct nft_data
*key
,
46 struct nft_data
*data
)
48 const struct nft_hash
*priv
= nft_set_priv(set
);
49 const struct nft_hash_elem
*he
;
52 h
= nft_hash_data(key
, priv
->hsize
, set
->klen
);
53 hlist_for_each_entry(he
, &priv
->hash
[h
], hnode
) {
54 if (nft_data_cmp(&he
->key
, key
, set
->klen
))
56 if (set
->flags
& NFT_SET_MAP
)
57 nft_data_copy(data
, he
->data
);
63 static void nft_hash_elem_destroy(const struct nft_set
*set
,
64 struct nft_hash_elem
*he
)
66 nft_data_uninit(&he
->key
, NFT_DATA_VALUE
);
67 if (set
->flags
& NFT_SET_MAP
)
68 nft_data_uninit(he
->data
, set
->dtype
);
72 static int nft_hash_insert(const struct nft_set
*set
,
73 const struct nft_set_elem
*elem
)
75 struct nft_hash
*priv
= nft_set_priv(set
);
76 struct nft_hash_elem
*he
;
83 if (set
->flags
& NFT_SET_MAP
)
84 size
+= sizeof(he
->data
[0]);
86 he
= kzalloc(size
, GFP_KERNEL
);
90 nft_data_copy(&he
->key
, &elem
->key
);
91 if (set
->flags
& NFT_SET_MAP
)
92 nft_data_copy(he
->data
, &elem
->data
);
94 h
= nft_hash_data(&he
->key
, priv
->hsize
, set
->klen
);
95 hlist_add_head_rcu(&he
->hnode
, &priv
->hash
[h
]);
99 static void nft_hash_remove(const struct nft_set
*set
,
100 const struct nft_set_elem
*elem
)
102 struct nft_hash_elem
*he
= elem
->cookie
;
104 hlist_del_rcu(&he
->hnode
);
108 static int nft_hash_get(const struct nft_set
*set
, struct nft_set_elem
*elem
)
110 const struct nft_hash
*priv
= nft_set_priv(set
);
111 struct nft_hash_elem
*he
;
114 h
= nft_hash_data(&elem
->key
, priv
->hsize
, set
->klen
);
115 hlist_for_each_entry(he
, &priv
->hash
[h
], hnode
) {
116 if (nft_data_cmp(&he
->key
, &elem
->key
, set
->klen
))
121 if (set
->flags
& NFT_SET_MAP
)
122 nft_data_copy(&elem
->data
, he
->data
);
128 static void nft_hash_walk(const struct nft_ctx
*ctx
, const struct nft_set
*set
,
129 struct nft_set_iter
*iter
)
131 const struct nft_hash
*priv
= nft_set_priv(set
);
132 const struct nft_hash_elem
*he
;
133 struct nft_set_elem elem
;
136 for (i
= 0; i
< priv
->hsize
; i
++) {
137 hlist_for_each_entry(he
, &priv
->hash
[i
], hnode
) {
138 if (iter
->count
< iter
->skip
)
141 memcpy(&elem
.key
, &he
->key
, sizeof(elem
.key
));
142 if (set
->flags
& NFT_SET_MAP
)
143 memcpy(&elem
.data
, he
->data
, sizeof(elem
.data
));
146 iter
->err
= iter
->fn(ctx
, set
, iter
, &elem
);
155 static unsigned int nft_hash_privsize(const struct nlattr
* const nla
[])
157 return sizeof(struct nft_hash
);
160 static int nft_hash_init(const struct nft_set
*set
,
161 const struct nlattr
* const tb
[])
163 struct nft_hash
*priv
= nft_set_priv(set
);
166 if (unlikely(!nft_hash_rnd_initted
)) {
167 nft_hash_rnd
= prandom_u32();
168 nft_hash_rnd_initted
= true;
171 /* Aim for a load factor of 0.75 */
172 // FIXME: temporarily broken until we have set descriptions
176 priv
->hash
= kcalloc(cnt
, sizeof(struct hlist_head
), GFP_KERNEL
);
177 if (priv
->hash
== NULL
)
181 for (i
= 0; i
< cnt
; i
++)
182 INIT_HLIST_HEAD(&priv
->hash
[i
]);
187 static void nft_hash_destroy(const struct nft_set
*set
)
189 const struct nft_hash
*priv
= nft_set_priv(set
);
190 const struct hlist_node
*next
;
191 struct nft_hash_elem
*elem
;
194 for (i
= 0; i
< priv
->hsize
; i
++) {
195 hlist_for_each_entry_safe(elem
, next
, &priv
->hash
[i
], hnode
) {
196 hlist_del(&elem
->hnode
);
197 nft_hash_elem_destroy(set
, elem
);
203 static struct nft_set_ops nft_hash_ops __read_mostly
= {
204 .privsize
= nft_hash_privsize
,
205 .init
= nft_hash_init
,
206 .destroy
= nft_hash_destroy
,
208 .insert
= nft_hash_insert
,
209 .remove
= nft_hash_remove
,
210 .lookup
= nft_hash_lookup
,
211 .walk
= nft_hash_walk
,
212 .features
= NFT_SET_MAP
,
213 .owner
= THIS_MODULE
,
216 static int __init
nft_hash_module_init(void)
218 return nft_register_set(&nft_hash_ops
);
221 static void __exit
nft_hash_module_exit(void)
223 nft_unregister_set(&nft_hash_ops
);
226 module_init(nft_hash_module_init
);
227 module_exit(nft_hash_module_exit
);
229 MODULE_LICENSE("GPL");
230 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
231 MODULE_ALIAS_NFT_SET();