Root/
1 | /* |
2 | * Copyright (c) 2008-2009 Patrick McHardy <kaber@trash.net> |
3 | * |
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. |
7 | * |
8 | * Development of this code funded by Astaro AG (http://www.astaro.com/) |
9 | */ |
10 | |
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> |
20 | |
21 | struct nft_hash { |
22 | struct hlist_head *hash; |
23 | unsigned int hsize; |
24 | }; |
25 | |
26 | struct nft_hash_elem { |
27 | struct hlist_node hnode; |
28 | struct nft_data key; |
29 | struct nft_data data[]; |
30 | }; |
31 | |
32 | static u32 nft_hash_rnd __read_mostly; |
33 | static bool nft_hash_rnd_initted __read_mostly; |
34 | |
35 | static unsigned int nft_hash_data(const struct nft_data *data, |
36 | unsigned int hsize, unsigned int len) |
37 | { |
38 | unsigned int h; |
39 | |
40 | h = jhash(data->data, len, nft_hash_rnd); |
41 | return ((u64)h * hsize) >> 32; |
42 | } |
43 | |
44 | static bool nft_hash_lookup(const struct nft_set *set, |
45 | const struct nft_data *key, |
46 | struct nft_data *data) |
47 | { |
48 | const struct nft_hash *priv = nft_set_priv(set); |
49 | const struct nft_hash_elem *he; |
50 | unsigned int h; |
51 | |
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)) |
55 | continue; |
56 | if (set->flags & NFT_SET_MAP) |
57 | nft_data_copy(data, he->data); |
58 | return true; |
59 | } |
60 | return false; |
61 | } |
62 | |
63 | static void nft_hash_elem_destroy(const struct nft_set *set, |
64 | struct nft_hash_elem *he) |
65 | { |
66 | nft_data_uninit(&he->key, NFT_DATA_VALUE); |
67 | if (set->flags & NFT_SET_MAP) |
68 | nft_data_uninit(he->data, set->dtype); |
69 | kfree(he); |
70 | } |
71 | |
72 | static int nft_hash_insert(const struct nft_set *set, |
73 | const struct nft_set_elem *elem) |
74 | { |
75 | struct nft_hash *priv = nft_set_priv(set); |
76 | struct nft_hash_elem *he; |
77 | unsigned int size, h; |
78 | |
79 | if (elem->flags != 0) |
80 | return -EINVAL; |
81 | |
82 | size = sizeof(*he); |
83 | if (set->flags & NFT_SET_MAP) |
84 | size += sizeof(he->data[0]); |
85 | |
86 | he = kzalloc(size, GFP_KERNEL); |
87 | if (he == NULL) |
88 | return -ENOMEM; |
89 | |
90 | nft_data_copy(&he->key, &elem->key); |
91 | if (set->flags & NFT_SET_MAP) |
92 | nft_data_copy(he->data, &elem->data); |
93 | |
94 | h = nft_hash_data(&he->key, priv->hsize, set->klen); |
95 | hlist_add_head_rcu(&he->hnode, &priv->hash[h]); |
96 | return 0; |
97 | } |
98 | |
99 | static void nft_hash_remove(const struct nft_set *set, |
100 | const struct nft_set_elem *elem) |
101 | { |
102 | struct nft_hash_elem *he = elem->cookie; |
103 | |
104 | hlist_del_rcu(&he->hnode); |
105 | kfree(he); |
106 | } |
107 | |
108 | static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem) |
109 | { |
110 | const struct nft_hash *priv = nft_set_priv(set); |
111 | struct nft_hash_elem *he; |
112 | unsigned int h; |
113 | |
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)) |
117 | continue; |
118 | |
119 | elem->cookie = he; |
120 | elem->flags = 0; |
121 | if (set->flags & NFT_SET_MAP) |
122 | nft_data_copy(&elem->data, he->data); |
123 | return 0; |
124 | } |
125 | return -ENOENT; |
126 | } |
127 | |
128 | static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set, |
129 | struct nft_set_iter *iter) |
130 | { |
131 | const struct nft_hash *priv = nft_set_priv(set); |
132 | const struct nft_hash_elem *he; |
133 | struct nft_set_elem elem; |
134 | unsigned int i; |
135 | |
136 | for (i = 0; i < priv->hsize; i++) { |
137 | hlist_for_each_entry(he, &priv->hash[i], hnode) { |
138 | if (iter->count < iter->skip) |
139 | goto cont; |
140 | |
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)); |
144 | elem.flags = 0; |
145 | |
146 | iter->err = iter->fn(ctx, set, iter, &elem); |
147 | if (iter->err < 0) |
148 | return; |
149 | cont: |
150 | iter->count++; |
151 | } |
152 | } |
153 | } |
154 | |
155 | static unsigned int nft_hash_privsize(const struct nlattr * const nla[]) |
156 | { |
157 | return sizeof(struct nft_hash); |
158 | } |
159 | |
160 | static int nft_hash_init(const struct nft_set *set, |
161 | const struct nlattr * const tb[]) |
162 | { |
163 | struct nft_hash *priv = nft_set_priv(set); |
164 | unsigned int cnt, i; |
165 | |
166 | if (unlikely(!nft_hash_rnd_initted)) { |
167 | get_random_bytes(&nft_hash_rnd, 4); |
168 | nft_hash_rnd_initted = true; |
169 | } |
170 | |
171 | /* Aim for a load factor of 0.75 */ |
172 | // FIXME: temporarily broken until we have set descriptions |
173 | cnt = 100; |
174 | cnt = cnt * 4 / 3; |
175 | |
176 | priv->hash = kcalloc(cnt, sizeof(struct hlist_head), GFP_KERNEL); |
177 | if (priv->hash == NULL) |
178 | return -ENOMEM; |
179 | priv->hsize = cnt; |
180 | |
181 | for (i = 0; i < cnt; i++) |
182 | INIT_HLIST_HEAD(&priv->hash[i]); |
183 | |
184 | return 0; |
185 | } |
186 | |
187 | static void nft_hash_destroy(const struct nft_set *set) |
188 | { |
189 | const struct nft_hash *priv = nft_set_priv(set); |
190 | const struct hlist_node *next; |
191 | struct nft_hash_elem *elem; |
192 | unsigned int i; |
193 | |
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); |
198 | } |
199 | } |
200 | kfree(priv->hash); |
201 | } |
202 | |
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, |
207 | .get = nft_hash_get, |
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, |
214 | }; |
215 | |
216 | static int __init nft_hash_module_init(void) |
217 | { |
218 | return nft_register_set(&nft_hash_ops); |
219 | } |
220 | |
221 | static void __exit nft_hash_module_exit(void) |
222 | { |
223 | nft_unregister_set(&nft_hash_ops); |
224 | } |
225 | |
226 | module_init(nft_hash_module_init); |
227 | module_exit(nft_hash_module_exit); |
228 | |
229 | MODULE_LICENSE("GPL"); |
230 | MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>"); |
231 | MODULE_ALIAS_NFT_SET(); |
232 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9