Blame view
net/netfilter/nft_hash.c
9.22 KB
96518518c
|
1 |
/* |
ce6eb0d7c
|
2 |
* Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net> |
96518518c
|
3 4 5 6 7 8 9 10 11 12 13 14 |
* * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License version 2 as * published by the Free Software Foundation. * * Development of this code funded by Astaro AG (http://www.astaro.com/) */ #include <linux/kernel.h> #include <linux/init.h> #include <linux/module.h> #include <linux/list.h> |
c50b960cc
|
15 |
#include <linux/log2.h> |
96518518c
|
16 17 |
#include <linux/jhash.h> #include <linux/netlink.h> |
9d0982927
|
18 |
#include <linux/workqueue.h> |
cfe4a9dda
|
19 |
#include <linux/rhashtable.h> |
96518518c
|
20 21 22 |
#include <linux/netfilter.h> #include <linux/netfilter/nf_tables.h> #include <net/netfilter/nf_tables.h> |
cfe4a9dda
|
23 24 |
/* We target a hash table size of 4, element hint is 75% of final size */ #define NFT_HASH_ELEMENT_HINT 3 |
96518518c
|
25 |
|
745f5450d
|
26 27 |
struct nft_hash { struct rhashtable ht; |
9d0982927
|
28 |
struct delayed_work gc_work; |
745f5450d
|
29 |
}; |
96518518c
|
30 |
struct nft_hash_elem { |
cfe4a9dda
|
31 |
struct rhash_head node; |
fe2811ebe
|
32 |
struct nft_set_ext ext; |
96518518c
|
33 |
}; |
bfd6e327e
|
34 35 |
struct nft_hash_cmp_arg { const struct nft_set *set; |
8cd8937ac
|
36 |
const u32 *key; |
cc02e457b
|
37 |
u8 genmask; |
bfd6e327e
|
38 |
}; |
fa3773211
|
39 |
static const struct rhashtable_params nft_hash_params; |
bfd6e327e
|
40 41 42 43 44 45 46 47 48 49 |
static inline u32 nft_hash_key(const void *data, u32 len, u32 seed) { const struct nft_hash_cmp_arg *arg = data; return jhash(arg->key, len, seed); } static inline u32 nft_hash_obj(const void *data, u32 len, u32 seed) { const struct nft_hash_elem *he = data; |
fe2811ebe
|
50 |
return jhash(nft_set_ext_key(&he->ext), len, seed); |
bfd6e327e
|
51 52 53 54 55 56 57 |
} static inline int nft_hash_cmp(struct rhashtable_compare_arg *arg, const void *ptr) { const struct nft_hash_cmp_arg *x = arg->key; const struct nft_hash_elem *he = ptr; |
e562d860d
|
58 |
if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen)) |
bfd6e327e
|
59 |
return 1; |
9d0982927
|
60 61 |
if (nft_set_elem_expired(&he->ext)) return 1; |
cc02e457b
|
62 63 |
if (!nft_set_elem_active(&he->ext, x->genmask)) return 1; |
bfd6e327e
|
64 65 |
return 0; } |
8cd8937ac
|
66 |
static bool nft_hash_lookup(const struct nft_set *set, const u32 *key, |
b2832dd66
|
67 |
const struct nft_set_ext **ext) |
96518518c
|
68 |
{ |
745f5450d
|
69 |
struct nft_hash *priv = nft_set_priv(set); |
20a69341f
|
70 |
const struct nft_hash_elem *he; |
bfd6e327e
|
71 |
struct nft_hash_cmp_arg arg = { |
cc02e457b
|
72 |
.genmask = nft_genmask_cur(read_pnet(&set->pnet)), |
bfd6e327e
|
73 74 75 |
.set = set, .key = key, }; |
ce6eb0d7c
|
76 |
|
bfd6e327e
|
77 |
he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params); |
b2832dd66
|
78 79 |
if (he != NULL) *ext = &he->ext; |
ce6eb0d7c
|
80 |
|
cfe4a9dda
|
81 |
return !!he; |
96518518c
|
82 |
} |
8cd8937ac
|
83 |
static bool nft_hash_update(struct nft_set *set, const u32 *key, |
22fe54d5f
|
84 85 |
void *(*new)(struct nft_set *, const struct nft_expr *, |
a55e22e92
|
86 |
struct nft_regs *regs), |
22fe54d5f
|
87 |
const struct nft_expr *expr, |
a55e22e92
|
88 |
struct nft_regs *regs, |
22fe54d5f
|
89 90 91 92 93 94 95 96 97 98 99 100 101 |
const struct nft_set_ext **ext) { struct nft_hash *priv = nft_set_priv(set); struct nft_hash_elem *he; struct nft_hash_cmp_arg arg = { .genmask = NFT_GENMASK_ANY, .set = set, .key = key, }; he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params); if (he != NULL) goto out; |
a55e22e92
|
102 |
he = new(set, expr, regs); |
22fe54d5f
|
103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
if (he == NULL) goto err1; if (rhashtable_lookup_insert_key(&priv->ht, &arg, &he->node, nft_hash_params)) goto err2; out: *ext = &he->ext; return true; err2: nft_set_elem_destroy(set, he); err1: return false; } |
20a69341f
|
117 118 |
static int nft_hash_insert(const struct nft_set *set, const struct nft_set_elem *elem) |
96518518c
|
119 |
{ |
745f5450d
|
120 |
struct nft_hash *priv = nft_set_priv(set); |
fe2811ebe
|
121 |
struct nft_hash_elem *he = elem->priv; |
bfd6e327e
|
122 |
struct nft_hash_cmp_arg arg = { |
cc02e457b
|
123 |
.genmask = nft_genmask_next(read_pnet(&set->pnet)), |
bfd6e327e
|
124 |
.set = set, |
7d7402642
|
125 |
.key = elem->key.val.data, |
bfd6e327e
|
126 |
}; |
ce6eb0d7c
|
127 |
|
fe2811ebe
|
128 129 |
return rhashtable_lookup_insert_key(&priv->ht, &arg, &he->node, nft_hash_params); |
96518518c
|
130 |
} |
cc02e457b
|
131 132 |
static void nft_hash_activate(const struct nft_set *set, const struct nft_set_elem *elem) |
96518518c
|
133 |
{ |
cc02e457b
|
134 |
struct nft_hash_elem *he = elem->priv; |
ce6eb0d7c
|
135 |
|
cc02e457b
|
136 |
nft_set_elem_change_active(set, &he->ext); |
9d0982927
|
137 |
nft_set_elem_clear_busy(&he->ext); |
20a69341f
|
138 |
} |
96518518c
|
139 |
|
cc02e457b
|
140 141 |
static void *nft_hash_deactivate(const struct nft_set *set, const struct nft_set_elem *elem) |
20a69341f
|
142 |
{ |
745f5450d
|
143 |
struct nft_hash *priv = nft_set_priv(set); |
fa3773211
|
144 |
struct nft_hash_elem *he; |
bfd6e327e
|
145 |
struct nft_hash_cmp_arg arg = { |
cc02e457b
|
146 |
.genmask = nft_genmask_next(read_pnet(&set->pnet)), |
bfd6e327e
|
147 |
.set = set, |
7d7402642
|
148 |
.key = elem->key.val.data, |
bfd6e327e
|
149 |
}; |
fa3773211
|
150 |
|
9d0982927
|
151 |
rcu_read_lock(); |
bfd6e327e
|
152 |
he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params); |
9d0982927
|
153 154 155 156 157 158 159 |
if (he != NULL) { if (!nft_set_elem_mark_busy(&he->ext)) nft_set_elem_change_active(set, &he->ext); else he = NULL; } rcu_read_unlock(); |
8d24c0b43
|
160 |
|
cc02e457b
|
161 162 |
return he; } |
8d24c0b43
|
163 |
|
cc02e457b
|
164 165 166 167 168 169 170 |
static void nft_hash_remove(const struct nft_set *set, const struct nft_set_elem *elem) { struct nft_hash *priv = nft_set_priv(set); struct nft_hash_elem *he = elem->priv; rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params); |
96518518c
|
171 |
} |
20a69341f
|
172 173 |
static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set, struct nft_set_iter *iter) |
96518518c
|
174 |
{ |
745f5450d
|
175 |
struct nft_hash *priv = nft_set_priv(set); |
fe2811ebe
|
176 |
struct nft_hash_elem *he; |
9a7766288
|
177 |
struct rhashtable_iter hti; |
20a69341f
|
178 |
struct nft_set_elem elem; |
cc02e457b
|
179 |
u8 genmask = nft_genmask_cur(read_pnet(&set->pnet)); |
9a7766288
|
180 |
int err; |
96518518c
|
181 |
|
745f5450d
|
182 |
err = rhashtable_walk_init(&priv->ht, &hti); |
9a7766288
|
183 184 185 |
iter->err = err; if (err) return; |
88d6ed15a
|
186 |
|
9a7766288
|
187 188 189 190 191 192 193 194 195 196 197 198 199 |
err = rhashtable_walk_start(&hti); if (err && err != -EAGAIN) { iter->err = err; goto out; } while ((he = rhashtable_walk_next(&hti))) { if (IS_ERR(he)) { err = PTR_ERR(he); if (err != -EAGAIN) { iter->err = err; goto out; } |
d8bdff59c
|
200 201 |
continue; |
9a7766288
|
202 203 204 205 |
} if (iter->count < iter->skip) goto cont; |
9d0982927
|
206 207 |
if (nft_set_elem_expired(&he->ext)) goto cont; |
cc02e457b
|
208 209 |
if (!nft_set_elem_active(&he->ext, genmask)) goto cont; |
20a69341f
|
210 |
|
fe2811ebe
|
211 |
elem.priv = he; |
9a7766288
|
212 213 214 215 |
iter->err = iter->fn(ctx, set, iter, &elem); if (iter->err < 0) goto out; |
20a69341f
|
216 |
|
20a69341f
|
217 |
cont: |
9a7766288
|
218 |
iter->count++; |
96518518c
|
219 |
} |
9a7766288
|
220 221 222 223 |
out: rhashtable_walk_stop(&hti); rhashtable_walk_exit(&hti); |
96518518c
|
224 |
} |
9d0982927
|
225 226 |
static void nft_hash_gc(struct work_struct *work) { |
3dd0673ac
|
227 |
struct nft_set *set; |
9d0982927
|
228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 |
struct nft_hash_elem *he; struct nft_hash *priv; struct nft_set_gc_batch *gcb = NULL; struct rhashtable_iter hti; int err; priv = container_of(work, struct nft_hash, gc_work.work); set = nft_set_container_of(priv); err = rhashtable_walk_init(&priv->ht, &hti); if (err) goto schedule; err = rhashtable_walk_start(&hti); if (err && err != -EAGAIN) goto out; while ((he = rhashtable_walk_next(&hti))) { if (IS_ERR(he)) { if (PTR_ERR(he) != -EAGAIN) goto out; continue; } if (!nft_set_elem_expired(&he->ext)) continue; if (nft_set_elem_mark_busy(&he->ext)) continue; gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC); if (gcb == NULL) goto out; rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params); |
3dd0673ac
|
261 |
atomic_dec(&set->nelems); |
9d0982927
|
262 263 264 265 266 267 268 269 270 271 272 |
nft_set_gc_batch_add(gcb, he); } out: rhashtable_walk_stop(&hti); rhashtable_walk_exit(&hti); nft_set_gc_batch_complete(gcb); schedule: queue_delayed_work(system_power_efficient_wq, &priv->gc_work, nft_set_gc_interval(set)); } |
20a69341f
|
273 274 |
static unsigned int nft_hash_privsize(const struct nlattr * const nla[]) { |
745f5450d
|
275 |
return sizeof(struct nft_hash); |
cfe4a9dda
|
276 |
} |
fa3773211
|
277 |
static const struct rhashtable_params nft_hash_params = { |
45d84751f
|
278 |
.head_offset = offsetof(struct nft_hash_elem, node), |
bfd6e327e
|
279 280 281 |
.hashfn = nft_hash_key, .obj_hashfn = nft_hash_obj, .obj_cmpfn = nft_hash_cmp, |
45d84751f
|
282 |
.automatic_shrinking = true, |
fa3773211
|
283 |
}; |
20a69341f
|
284 |
static int nft_hash_init(const struct nft_set *set, |
c50b960cc
|
285 |
const struct nft_set_desc *desc, |
96518518c
|
286 287 |
const struct nlattr * const tb[]) { |
745f5450d
|
288 |
struct nft_hash *priv = nft_set_priv(set); |
fa3773211
|
289 |
struct rhashtable_params params = nft_hash_params; |
9d0982927
|
290 |
int err; |
fa3773211
|
291 292 |
params.nelem_hint = desc->size ?: NFT_HASH_ELEMENT_HINT; |
45d84751f
|
293 |
params.key_len = set->klen; |
96518518c
|
294 |
|
9d0982927
|
295 296 297 298 299 300 301 302 303 |
err = rhashtable_init(&priv->ht, ¶ms); if (err < 0) return err; INIT_DEFERRABLE_WORK(&priv->gc_work, nft_hash_gc); if (set->flags & NFT_SET_TIMEOUT) queue_delayed_work(system_power_efficient_wq, &priv->gc_work, nft_set_gc_interval(set)); return 0; |
96518518c
|
304 |
} |
61edafbb4
|
305 |
static void nft_hash_elem_destroy(void *ptr, void *arg) |
96518518c
|
306 |
{ |
61edafbb4
|
307 |
nft_set_elem_destroy((const struct nft_set *)arg, ptr); |
6b6f302ce
|
308 |
} |
97defe1ec
|
309 |
|
6b6f302ce
|
310 311 |
static void nft_hash_destroy(const struct nft_set *set) { |
745f5450d
|
312 |
struct nft_hash *priv = nft_set_priv(set); |
9d0982927
|
313 |
cancel_delayed_work_sync(&priv->gc_work); |
61edafbb4
|
314 315 |
rhashtable_free_and_destroy(&priv->ht, nft_hash_elem_destroy, (void *)set); |
96518518c
|
316 |
} |
c50b960cc
|
317 318 319 320 321 322 |
static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features, struct nft_set_estimate *est) { unsigned int esize; esize = sizeof(struct nft_hash_elem); |
c50b960cc
|
323 |
if (desc->size) { |
745f5450d
|
324 |
est->size = sizeof(struct nft_hash) + |
cfe4a9dda
|
325 |
roundup_pow_of_two(desc->size * 4 / 3) * |
c50b960cc
|
326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 |
sizeof(struct nft_hash_elem *) + desc->size * esize; } else { /* Resizing happens when the load drops below 30% or goes * above 75%. The average of 52.5% load (approximated by 50%) * is used for the size estimation of the hash buckets, * meaning we calculate two buckets per element. */ est->size = esize + 2 * sizeof(struct nft_hash_elem *); } est->class = NFT_SET_CLASS_O_1; return true; } |
20a69341f
|
341 342 |
static struct nft_set_ops nft_hash_ops __read_mostly = { .privsize = nft_hash_privsize, |
fe2811ebe
|
343 |
.elemsize = offsetof(struct nft_hash_elem, ext), |
c50b960cc
|
344 |
.estimate = nft_hash_estimate, |
96518518c
|
345 346 |
.init = nft_hash_init, .destroy = nft_hash_destroy, |
20a69341f
|
347 |
.insert = nft_hash_insert, |
cc02e457b
|
348 349 |
.activate = nft_hash_activate, .deactivate = nft_hash_deactivate, |
20a69341f
|
350 351 |
.remove = nft_hash_remove, .lookup = nft_hash_lookup, |
22fe54d5f
|
352 |
.update = nft_hash_update, |
20a69341f
|
353 |
.walk = nft_hash_walk, |
9d0982927
|
354 |
.features = NFT_SET_MAP | NFT_SET_TIMEOUT, |
20a69341f
|
355 |
.owner = THIS_MODULE, |
96518518c
|
356 357 358 359 |
}; static int __init nft_hash_module_init(void) { |
20a69341f
|
360 |
return nft_register_set(&nft_hash_ops); |
96518518c
|
361 362 363 364 |
} static void __exit nft_hash_module_exit(void) { |
20a69341f
|
365 |
nft_unregister_set(&nft_hash_ops); |
96518518c
|
366 367 368 369 370 371 372 |
} module_init(nft_hash_module_init); module_exit(nft_hash_module_exit); MODULE_LICENSE("GPL"); MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>"); |
20a69341f
|
373 |
MODULE_ALIAS_NFT_SET(); |