1
2
3
4
5
6
7
8
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/log2.h>
16#include <linux/jhash.h>
17#include <linux/netlink.h>
18#include <linux/workqueue.h>
19#include <linux/rhashtable.h>
20#include <linux/netfilter.h>
21#include <linux/netfilter/nf_tables.h>
22#include <net/netfilter/nf_tables.h>
23
24
25#define NFT_HASH_ELEMENT_HINT 3
26
27struct nft_hash {
28 struct rhashtable ht;
29 struct delayed_work gc_work;
30};
31
32struct nft_hash_elem {
33 struct rhash_head node;
34 struct nft_set_ext ext;
35};
36
37struct nft_hash_cmp_arg {
38 const struct nft_set *set;
39 const u32 *key;
40 u8 genmask;
41};
42
43static const struct rhashtable_params nft_hash_params;
44
45static inline u32 nft_hash_key(const void *data, u32 len, u32 seed)
46{
47 const struct nft_hash_cmp_arg *arg = data;
48
49 return jhash(arg->key, len, seed);
50}
51
52static inline u32 nft_hash_obj(const void *data, u32 len, u32 seed)
53{
54 const struct nft_hash_elem *he = data;
55
56 return jhash(nft_set_ext_key(&he->ext), len, seed);
57}
58
59static inline int nft_hash_cmp(struct rhashtable_compare_arg *arg,
60 const void *ptr)
61{
62 const struct nft_hash_cmp_arg *x = arg->key;
63 const struct nft_hash_elem *he = ptr;
64
65 if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
66 return 1;
67 if (nft_set_elem_expired(&he->ext))
68 return 1;
69 if (!nft_set_elem_active(&he->ext, x->genmask))
70 return 1;
71 return 0;
72}
73
74static bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
75 const u32 *key, const struct nft_set_ext **ext)
76{
77 struct nft_hash *priv = nft_set_priv(set);
78 const struct nft_hash_elem *he;
79 struct nft_hash_cmp_arg arg = {
80 .genmask = nft_genmask_cur(net),
81 .set = set,
82 .key = key,
83 };
84
85 he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
86 if (he != NULL)
87 *ext = &he->ext;
88
89 return !!he;
90}
91
92static bool nft_hash_update(struct nft_set *set, const u32 *key,
93 void *(*new)(struct nft_set *,
94 const struct nft_expr *,
95 struct nft_regs *regs),
96 const struct nft_expr *expr,
97 struct nft_regs *regs,
98 const struct nft_set_ext **ext)
99{
100 struct nft_hash *priv = nft_set_priv(set);
101 struct nft_hash_elem *he, *prev;
102 struct nft_hash_cmp_arg arg = {
103 .genmask = NFT_GENMASK_ANY,
104 .set = set,
105 .key = key,
106 };
107
108 he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
109 if (he != NULL)
110 goto out;
111
112 he = new(set, expr, regs);
113 if (he == NULL)
114 goto err1;
115
116 prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
117 nft_hash_params);
118 if (IS_ERR(prev))
119 goto err2;
120
121
122 if (prev) {
123 nft_set_elem_destroy(set, he, true);
124 he = prev;
125 }
126
127out:
128 *ext = &he->ext;
129 return true;
130
131err2:
132 nft_set_elem_destroy(set, he, true);
133err1:
134 return false;
135}
136
137static int nft_hash_insert(const struct net *net, const struct nft_set *set,
138 const struct nft_set_elem *elem,
139 struct nft_set_ext **ext)
140{
141 struct nft_hash *priv = nft_set_priv(set);
142 struct nft_hash_elem *he = elem->priv;
143 struct nft_hash_cmp_arg arg = {
144 .genmask = nft_genmask_next(net),
145 .set = set,
146 .key = elem->key.val.data,
147 };
148 struct nft_hash_elem *prev;
149
150 prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
151 nft_hash_params);
152 if (IS_ERR(prev))
153 return PTR_ERR(prev);
154 if (prev) {
155 *ext = &prev->ext;
156 return -EEXIST;
157 }
158 return 0;
159}
160
161static void nft_hash_activate(const struct net *net, const struct nft_set *set,
162 const struct nft_set_elem *elem)
163{
164 struct nft_hash_elem *he = elem->priv;
165
166 nft_set_elem_change_active(net, set, &he->ext);
167 nft_set_elem_clear_busy(&he->ext);
168}
169
170static void *nft_hash_deactivate(const struct net *net,
171 const struct nft_set *set,
172 const struct nft_set_elem *elem)
173{
174 struct nft_hash *priv = nft_set_priv(set);
175 struct nft_hash_elem *he;
176 struct nft_hash_cmp_arg arg = {
177 .genmask = nft_genmask_next(net),
178 .set = set,
179 .key = elem->key.val.data,
180 };
181
182 rcu_read_lock();
183 he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
184 if (he != NULL) {
185 if (!nft_set_elem_mark_busy(&he->ext) ||
186 !nft_is_active(net, &he->ext))
187 nft_set_elem_change_active(net, set, &he->ext);
188 else
189 he = NULL;
190 }
191 rcu_read_unlock();
192
193 return he;
194}
195
196static void nft_hash_remove(const struct nft_set *set,
197 const struct nft_set_elem *elem)
198{
199 struct nft_hash *priv = nft_set_priv(set);
200 struct nft_hash_elem *he = elem->priv;
201
202 rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params);
203}
204
205static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set,
206 struct nft_set_iter *iter)
207{
208 struct nft_hash *priv = nft_set_priv(set);
209 struct nft_hash_elem *he;
210 struct rhashtable_iter hti;
211 struct nft_set_elem elem;
212 int err;
213
214 err = rhashtable_walk_init(&priv->ht, &hti, GFP_KERNEL);
215 iter->err = err;
216 if (err)
217 return;
218
219 err = rhashtable_walk_start(&hti);
220 if (err && err != -EAGAIN) {
221 iter->err = err;
222 goto out;
223 }
224
225 while ((he = rhashtable_walk_next(&hti))) {
226 if (IS_ERR(he)) {
227 err = PTR_ERR(he);
228 if (err != -EAGAIN) {
229 iter->err = err;
230 goto out;
231 }
232
233 continue;
234 }
235
236 if (iter->count < iter->skip)
237 goto cont;
238 if (nft_set_elem_expired(&he->ext))
239 goto cont;
240 if (!nft_set_elem_active(&he->ext, iter->genmask))
241 goto cont;
242
243 elem.priv = he;
244
245 iter->err = iter->fn(ctx, set, iter, &elem);
246 if (iter->err < 0)
247 goto out;
248
249cont:
250 iter->count++;
251 }
252
253out:
254 rhashtable_walk_stop(&hti);
255 rhashtable_walk_exit(&hti);
256}
257
258static void nft_hash_gc(struct work_struct *work)
259{
260 struct nft_set *set;
261 struct nft_hash_elem *he;
262 struct nft_hash *priv;
263 struct nft_set_gc_batch *gcb = NULL;
264 struct rhashtable_iter hti;
265 int err;
266
267 priv = container_of(work, struct nft_hash, gc_work.work);
268 set = nft_set_container_of(priv);
269
270 err = rhashtable_walk_init(&priv->ht, &hti, GFP_KERNEL);
271 if (err)
272 goto schedule;
273
274 err = rhashtable_walk_start(&hti);
275 if (err && err != -EAGAIN)
276 goto out;
277
278 while ((he = rhashtable_walk_next(&hti))) {
279 if (IS_ERR(he)) {
280 if (PTR_ERR(he) != -EAGAIN)
281 goto out;
282 continue;
283 }
284
285 if (!nft_set_elem_expired(&he->ext))
286 continue;
287 if (nft_set_elem_mark_busy(&he->ext))
288 continue;
289
290 gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC);
291 if (gcb == NULL)
292 goto out;
293 rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params);
294 atomic_dec(&set->nelems);
295 nft_set_gc_batch_add(gcb, he);
296 }
297out:
298 rhashtable_walk_stop(&hti);
299 rhashtable_walk_exit(&hti);
300
301 nft_set_gc_batch_complete(gcb);
302schedule:
303 queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
304 nft_set_gc_interval(set));
305}
306
307static unsigned int nft_hash_privsize(const struct nlattr * const nla[])
308{
309 return sizeof(struct nft_hash);
310}
311
312static const struct rhashtable_params nft_hash_params = {
313 .head_offset = offsetof(struct nft_hash_elem, node),
314 .hashfn = nft_hash_key,
315 .obj_hashfn = nft_hash_obj,
316 .obj_cmpfn = nft_hash_cmp,
317 .automatic_shrinking = true,
318};
319
320static int nft_hash_init(const struct nft_set *set,
321 const struct nft_set_desc *desc,
322 const struct nlattr * const tb[])
323{
324 struct nft_hash *priv = nft_set_priv(set);
325 struct rhashtable_params params = nft_hash_params;
326 int err;
327
328 params.nelem_hint = desc->size ?: NFT_HASH_ELEMENT_HINT;
329 params.key_len = set->klen;
330
331 err = rhashtable_init(&priv->ht, ¶ms);
332 if (err < 0)
333 return err;
334
335 INIT_DEFERRABLE_WORK(&priv->gc_work, nft_hash_gc);
336 if (set->flags & NFT_SET_TIMEOUT)
337 queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
338 nft_set_gc_interval(set));
339 return 0;
340}
341
342static void nft_hash_elem_destroy(void *ptr, void *arg)
343{
344 nft_set_elem_destroy((const struct nft_set *)arg, ptr, true);
345}
346
347static void nft_hash_destroy(const struct nft_set *set)
348{
349 struct nft_hash *priv = nft_set_priv(set);
350
351 cancel_delayed_work_sync(&priv->gc_work);
352 rhashtable_free_and_destroy(&priv->ht, nft_hash_elem_destroy,
353 (void *)set);
354}
355
356static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
357 struct nft_set_estimate *est)
358{
359 unsigned int esize;
360
361 esize = sizeof(struct nft_hash_elem);
362 if (desc->size) {
363 est->size = sizeof(struct nft_hash) +
364 roundup_pow_of_two(desc->size * 4 / 3) *
365 sizeof(struct nft_hash_elem *) +
366 desc->size * esize;
367 } else {
368
369
370
371
372
373 est->size = esize + 2 * sizeof(struct nft_hash_elem *);
374 }
375
376 est->class = NFT_SET_CLASS_O_1;
377
378 return true;
379}
380
381static struct nft_set_ops nft_hash_ops __read_mostly = {
382 .privsize = nft_hash_privsize,
383 .elemsize = offsetof(struct nft_hash_elem, ext),
384 .estimate = nft_hash_estimate,
385 .init = nft_hash_init,
386 .destroy = nft_hash_destroy,
387 .insert = nft_hash_insert,
388 .activate = nft_hash_activate,
389 .deactivate = nft_hash_deactivate,
390 .remove = nft_hash_remove,
391 .lookup = nft_hash_lookup,
392 .update = nft_hash_update,
393 .walk = nft_hash_walk,
394 .features = NFT_SET_MAP | NFT_SET_TIMEOUT,
395 .owner = THIS_MODULE,
396};
397
398static int __init nft_hash_module_init(void)
399{
400 return nft_register_set(&nft_hash_ops);
401}
402
403static void __exit nft_hash_module_exit(void)
404{
405 nft_unregister_set(&nft_hash_ops);
406}
407
408module_init(nft_hash_module_init);
409module_exit(nft_hash_module_exit);
410
411MODULE_LICENSE("GPL");
412MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
413MODULE_ALIAS_NFT_SET();
414
