Root/
1 | /* |
2 | * Copyright (c) 2008-2014 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/vmalloc.h> |
18 | #include <linux/netfilter.h> |
19 | #include <linux/netfilter/nf_tables.h> |
20 | #include <net/netfilter/nf_tables.h> |
21 | |
22 | #define NFT_HASH_MIN_SIZE 4 |
23 | |
24 | struct nft_hash { |
25 | struct nft_hash_table __rcu *tbl; |
26 | }; |
27 | |
28 | struct nft_hash_table { |
29 | unsigned int size; |
30 | unsigned int elements; |
31 | struct nft_hash_elem __rcu *buckets[]; |
32 | }; |
33 | |
34 | struct nft_hash_elem { |
35 | struct nft_hash_elem __rcu *next; |
36 | struct nft_data key; |
37 | struct nft_data data[]; |
38 | }; |
39 | |
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)) |
44 | |
45 | static u32 nft_hash_rnd __read_mostly; |
46 | static bool nft_hash_rnd_initted __read_mostly; |
47 | |
48 | static unsigned int nft_hash_data(const struct nft_data *data, |
49 | unsigned int hsize, unsigned int len) |
50 | { |
51 | unsigned int h; |
52 | |
53 | h = jhash(data->data, len, nft_hash_rnd); |
54 | return h & (hsize - 1); |
55 | } |
56 | |
57 | static bool nft_hash_lookup(const struct nft_set *set, |
58 | const struct nft_data *key, |
59 | struct nft_data *data) |
60 | { |
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; |
64 | unsigned int h; |
65 | |
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)) |
69 | continue; |
70 | if (set->flags & NFT_SET_MAP) |
71 | nft_data_copy(data, he->data); |
72 | return true; |
73 | } |
74 | return false; |
75 | } |
76 | |
77 | static void nft_hash_tbl_free(const struct nft_hash_table *tbl) |
78 | { |
79 | if (is_vmalloc_addr(tbl)) |
80 | vfree(tbl); |
81 | else |
82 | kfree(tbl); |
83 | } |
84 | |
85 | static struct nft_hash_table *nft_hash_tbl_alloc(unsigned int nbuckets) |
86 | { |
87 | struct nft_hash_table *tbl; |
88 | size_t size; |
89 | |
90 | size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]); |
91 | tbl = kzalloc(size, GFP_KERNEL | __GFP_REPEAT | __GFP_NOWARN); |
92 | if (tbl == NULL) |
93 | tbl = vzalloc(size); |
94 | if (tbl == NULL) |
95 | return NULL; |
96 | tbl->size = nbuckets; |
97 | |
98 | return tbl; |
99 | } |
100 | |
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) |
104 | { |
105 | struct nft_hash_elem *he, *last, *next; |
106 | unsigned int h; |
107 | |
108 | he = nft_dereference(tbl->buckets[n]); |
109 | if (he == NULL) |
110 | return; |
111 | h = nft_hash_data(&he->key, ntbl->size, set->klen); |
112 | |
113 | /* Find last element of first chain hashing to bucket h */ |
114 | last = he; |
115 | nft_hash_for_each_entry(he, he->next) { |
116 | if (nft_hash_data(&he->key, ntbl->size, set->klen) != h) |
117 | break; |
118 | last = he; |
119 | } |
120 | |
121 | /* Unlink first chain from the old table */ |
122 | RCU_INIT_POINTER(tbl->buckets[n], last->next); |
123 | |
124 | /* If end of chain reached, done */ |
125 | if (he == NULL) |
126 | return; |
127 | |
128 | /* Find first element of second chain hashing to bucket h */ |
129 | next = NULL; |
130 | nft_hash_for_each_entry(he, he->next) { |
131 | if (nft_hash_data(&he->key, ntbl->size, set->klen) != h) |
132 | continue; |
133 | next = he; |
134 | break; |
135 | } |
136 | |
137 | /* Link the two chains */ |
138 | RCU_INIT_POINTER(last->next, next); |
139 | } |
140 | |
141 | static int nft_hash_tbl_expand(const struct nft_set *set, struct nft_hash *priv) |
142 | { |
143 | struct nft_hash_table *tbl = nft_dereference(priv->tbl), *ntbl; |
144 | struct nft_hash_elem *he; |
145 | unsigned int i, h; |
146 | bool complete; |
147 | |
148 | ntbl = nft_hash_tbl_alloc(tbl->size * 2); |
149 | if (ntbl == NULL) |
150 | return -ENOMEM; |
151 | |
152 | /* Link new table's buckets to first element in the old table |
153 | * hashing to the new bucket. |
154 | */ |
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) |
159 | continue; |
160 | RCU_INIT_POINTER(ntbl->buckets[i], he); |
161 | break; |
162 | } |
163 | } |
164 | ntbl->elements = tbl->elements; |
165 | |
166 | /* Publish new table */ |
167 | rcu_assign_pointer(priv->tbl, ntbl); |
168 | |
169 | /* Unzip interleaved hash chains */ |
170 | do { |
171 | /* Wait for readers to use new table/unzipped chains */ |
172 | synchronize_rcu(); |
173 | |
174 | complete = true; |
175 | for (i = 0; i < tbl->size; i++) { |
176 | nft_hash_chain_unzip(set, ntbl, tbl, i); |
177 | if (tbl->buckets[i] != NULL) |
178 | complete = false; |
179 | } |
180 | } while (!complete); |
181 | |
182 | nft_hash_tbl_free(tbl); |
183 | return 0; |
184 | } |
185 | |
186 | static int nft_hash_tbl_shrink(const struct nft_set *set, struct nft_hash *priv) |
187 | { |
188 | struct nft_hash_table *tbl = nft_dereference(priv->tbl), *ntbl; |
189 | struct nft_hash_elem __rcu **pprev; |
190 | unsigned int i; |
191 | |
192 | ntbl = nft_hash_tbl_alloc(tbl->size / 2); |
193 | if (ntbl == NULL) |
194 | return -ENOMEM; |
195 | |
196 | for (i = 0; i < ntbl->size; i++) { |
197 | ntbl->buckets[i] = tbl->buckets[i]; |
198 | |
199 | for (pprev = &ntbl->buckets[i]; *pprev != NULL; |
200 | pprev = &nft_dereference(*pprev)->next) |
201 | ; |
202 | RCU_INIT_POINTER(*pprev, tbl->buckets[i + ntbl->size]); |
203 | } |
204 | ntbl->elements = tbl->elements; |
205 | |
206 | /* Publish new table */ |
207 | rcu_assign_pointer(priv->tbl, ntbl); |
208 | synchronize_rcu(); |
209 | |
210 | nft_hash_tbl_free(tbl); |
211 | return 0; |
212 | } |
213 | |
214 | static int nft_hash_insert(const struct nft_set *set, |
215 | const struct nft_set_elem *elem) |
216 | { |
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; |
221 | |
222 | if (elem->flags != 0) |
223 | return -EINVAL; |
224 | |
225 | size = sizeof(*he); |
226 | if (set->flags & NFT_SET_MAP) |
227 | size += sizeof(he->data[0]); |
228 | |
229 | he = kzalloc(size, GFP_KERNEL); |
230 | if (he == NULL) |
231 | return -ENOMEM; |
232 | |
233 | nft_data_copy(&he->key, &elem->key); |
234 | if (set->flags & NFT_SET_MAP) |
235 | nft_data_copy(he->data, &elem->data); |
236 | |
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); |
240 | tbl->elements++; |
241 | |
242 | /* Expand table when exceeding 75% load */ |
243 | if (tbl->elements > tbl->size / 4 * 3) |
244 | nft_hash_tbl_expand(set, priv); |
245 | |
246 | return 0; |
247 | } |
248 | |
249 | static void nft_hash_elem_destroy(const struct nft_set *set, |
250 | struct nft_hash_elem *he) |
251 | { |
252 | nft_data_uninit(&he->key, NFT_DATA_VALUE); |
253 | if (set->flags & NFT_SET_MAP) |
254 | nft_data_uninit(he->data, set->dtype); |
255 | kfree(he); |
256 | } |
257 | |
258 | static void nft_hash_remove(const struct nft_set *set, |
259 | const struct nft_set_elem *elem) |
260 | { |
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; |
264 | |
265 | pprev = elem->cookie; |
266 | he = nft_dereference((*pprev)); |
267 | |
268 | RCU_INIT_POINTER(*pprev, he->next); |
269 | synchronize_rcu(); |
270 | kfree(he); |
271 | tbl->elements--; |
272 | |
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); |
277 | } |
278 | |
279 | static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem) |
280 | { |
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; |
285 | unsigned int h; |
286 | |
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)) { |
291 | pprev = &he->next; |
292 | continue; |
293 | } |
294 | |
295 | elem->cookie = (void *)pprev; |
296 | elem->flags = 0; |
297 | if (set->flags & NFT_SET_MAP) |
298 | nft_data_copy(&elem->data, he->data); |
299 | return 0; |
300 | } |
301 | return -ENOENT; |
302 | } |
303 | |
304 | static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set, |
305 | struct nft_set_iter *iter) |
306 | { |
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; |
311 | unsigned int i; |
312 | |
313 | for (i = 0; i < tbl->size; i++) { |
314 | nft_hash_for_each_entry(he, tbl->buckets[i]) { |
315 | if (iter->count < iter->skip) |
316 | goto cont; |
317 | |
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)); |
321 | elem.flags = 0; |
322 | |
323 | iter->err = iter->fn(ctx, set, iter, &elem); |
324 | if (iter->err < 0) |
325 | return; |
326 | cont: |
327 | iter->count++; |
328 | } |
329 | } |
330 | } |
331 | |
332 | static unsigned int nft_hash_privsize(const struct nlattr * const nla[]) |
333 | { |
334 | return sizeof(struct nft_hash); |
335 | } |
336 | |
337 | static int nft_hash_init(const struct nft_set *set, |
338 | const struct nlattr * const tb[]) |
339 | { |
340 | struct nft_hash *priv = nft_set_priv(set); |
341 | struct nft_hash_table *tbl; |
342 | |
343 | if (unlikely(!nft_hash_rnd_initted)) { |
344 | get_random_bytes(&nft_hash_rnd, 4); |
345 | nft_hash_rnd_initted = true; |
346 | } |
347 | |
348 | tbl = nft_hash_tbl_alloc(NFT_HASH_MIN_SIZE); |
349 | if (tbl == NULL) |
350 | return -ENOMEM; |
351 | RCU_INIT_POINTER(priv->tbl, tbl); |
352 | return 0; |
353 | } |
354 | |
355 | static void nft_hash_destroy(const struct nft_set *set) |
356 | { |
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; |
360 | unsigned int i; |
361 | |
362 | for (i = 0; i < tbl->size; i++) { |
363 | for (he = nft_dereference(tbl->buckets[i]); he != NULL; |
364 | he = next) { |
365 | next = nft_dereference(he->next); |
366 | nft_hash_elem_destroy(set, he); |
367 | } |
368 | } |
369 | kfree(tbl); |
370 | } |
371 | |
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, |
376 | .get = nft_hash_get, |
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, |
383 | }; |
384 | |
385 | static int __init nft_hash_module_init(void) |
386 | { |
387 | return nft_register_set(&nft_hash_ops); |
388 | } |
389 | |
390 | static void __exit nft_hash_module_exit(void) |
391 | { |
392 | nft_unregister_set(&nft_hash_ops); |
393 | } |
394 | |
395 | module_init(nft_hash_module_init); |
396 | module_exit(nft_hash_module_exit); |
397 | |
398 | MODULE_LICENSE("GPL"); |
399 | MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>"); |
400 | MODULE_ALIAS_NFT_SET(); |
401 |
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