Commit | Line | Data |
---|---|---|
96518518 | 1 | /* |
20a69341 | 2 | * Copyright (c) 2008-2009 Patrick McHardy <kaber@trash.net> |
96518518 PM |
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; | |
96518518 PM |
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 | ||
20a69341 | 40 | h = jhash(data->data, len, nft_hash_rnd); |
96518518 PM |
41 | return ((u64)h * hsize) >> 32; |
42 | } | |
43 | ||
20a69341 PM |
44 | static bool nft_hash_lookup(const struct nft_set *set, |
45 | const struct nft_data *key, | |
46 | struct nft_data *data) | |
96518518 | 47 | { |
20a69341 PM |
48 | const struct nft_hash *priv = nft_set_priv(set); |
49 | const struct nft_hash_elem *he; | |
96518518 PM |
50 | unsigned int h; |
51 | ||
20a69341 PM |
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)) | |
96518518 | 55 | continue; |
20a69341 PM |
56 | if (set->flags & NFT_SET_MAP) |
57 | nft_data_copy(data, he->data); | |
58 | return true; | |
96518518 | 59 | } |
20a69341 | 60 | return false; |
96518518 PM |
61 | } |
62 | ||
20a69341 PM |
63 | static void nft_hash_elem_destroy(const struct nft_set *set, |
64 | struct nft_hash_elem *he) | |
96518518 | 65 | { |
20a69341 PM |
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); | |
96518518 PM |
70 | } |
71 | ||
20a69341 PM |
72 | static int nft_hash_insert(const struct nft_set *set, |
73 | const struct nft_set_elem *elem) | |
96518518 | 74 | { |
20a69341 PM |
75 | struct nft_hash *priv = nft_set_priv(set); |
76 | struct nft_hash_elem *he; | |
77 | unsigned int size, h; | |
96518518 | 78 | |
20a69341 | 79 | if (elem->flags != 0) |
96518518 | 80 | return -EINVAL; |
96518518 | 81 | |
20a69341 PM |
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) | |
96518518 PM |
88 | return -ENOMEM; |
89 | ||
20a69341 PM |
90 | nft_data_copy(&he->key, &elem->key); |
91 | if (set->flags & NFT_SET_MAP) | |
92 | nft_data_copy(he->data, &elem->data); | |
96518518 | 93 | |
20a69341 PM |
94 | h = nft_hash_data(&he->key, priv->hsize, set->klen); |
95 | hlist_add_head_rcu(&he->hnode, &priv->hash[h]); | |
96518518 | 96 | return 0; |
96518518 PM |
97 | } |
98 | ||
20a69341 PM |
99 | static void nft_hash_remove(const struct nft_set *set, |
100 | const struct nft_set_elem *elem) | |
96518518 | 101 | { |
20a69341 | 102 | struct nft_hash_elem *he = elem->cookie; |
96518518 | 103 | |
20a69341 PM |
104 | hlist_del_rcu(&he->hnode); |
105 | kfree(he); | |
106 | } | |
96518518 | 107 | |
20a69341 PM |
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; | |
96518518 | 113 | |
20a69341 PM |
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; | |
96518518 | 118 | |
20a69341 PM |
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; | |
96518518 PM |
126 | } |
127 | ||
20a69341 PM |
128 | static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set, |
129 | struct nft_set_iter *iter) | |
96518518 | 130 | { |
20a69341 PM |
131 | const struct nft_hash *priv = nft_set_priv(set); |
132 | const struct nft_hash_elem *he; | |
133 | struct nft_set_elem elem; | |
96518518 PM |
134 | unsigned int i; |
135 | ||
136 | for (i = 0; i < priv->hsize; i++) { | |
20a69341 PM |
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++; | |
96518518 PM |
151 | } |
152 | } | |
96518518 PM |
153 | } |
154 | ||
20a69341 PM |
155 | static unsigned int nft_hash_privsize(const struct nlattr * const nla[]) |
156 | { | |
157 | return sizeof(struct nft_hash); | |
158 | } | |
96518518 | 159 | |
20a69341 | 160 | static int nft_hash_init(const struct nft_set *set, |
96518518 PM |
161 | const struct nlattr * const tb[]) |
162 | { | |
20a69341 | 163 | struct nft_hash *priv = nft_set_priv(set); |
96518518 | 164 | unsigned int cnt, i; |
96518518 PM |
165 | |
166 | if (unlikely(!nft_hash_rnd_initted)) { | |
167 | get_random_bytes(&nft_hash_rnd, 4); | |
168 | nft_hash_rnd_initted = true; | |
169 | } | |
170 | ||
96518518 | 171 | /* Aim for a load factor of 0.75 */ |
20a69341 PM |
172 | // FIXME: temporarily broken until we have set descriptions |
173 | cnt = 100; | |
96518518 PM |
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 | ||
96518518 | 184 | return 0; |
96518518 PM |
185 | } |
186 | ||
20a69341 | 187 | static void nft_hash_destroy(const struct nft_set *set) |
96518518 | 188 | { |
20a69341 PM |
189 | const struct nft_hash *priv = nft_set_priv(set); |
190 | const struct hlist_node *next; | |
191 | struct nft_hash_elem *elem; | |
96518518 PM |
192 | unsigned int i; |
193 | ||
96518518 | 194 | for (i = 0; i < priv->hsize; i++) { |
20a69341 PM |
195 | hlist_for_each_entry_safe(elem, next, &priv->hash[i], hnode) { |
196 | hlist_del(&elem->hnode); | |
197 | nft_hash_elem_destroy(set, elem); | |
96518518 PM |
198 | } |
199 | } | |
20a69341 | 200 | kfree(priv->hash); |
96518518 PM |
201 | } |
202 | ||
20a69341 PM |
203 | static struct nft_set_ops nft_hash_ops __read_mostly = { |
204 | .privsize = nft_hash_privsize, | |
96518518 PM |
205 | .init = nft_hash_init, |
206 | .destroy = nft_hash_destroy, | |
20a69341 PM |
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, | |
96518518 PM |
214 | }; |
215 | ||
216 | static int __init nft_hash_module_init(void) | |
217 | { | |
20a69341 | 218 | return nft_register_set(&nft_hash_ops); |
96518518 PM |
219 | } |
220 | ||
221 | static void __exit nft_hash_module_exit(void) | |
222 | { | |
20a69341 | 223 | nft_unregister_set(&nft_hash_ops); |
96518518 PM |
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>"); | |
20a69341 | 231 | MODULE_ALIAS_NFT_SET(); |