Blame view
net/netfilter/nft_set_rbtree.c
17.1 KB
d2912cb15 treewide: Replace... |
1 |
// SPDX-License-Identifier: GPL-2.0-only |
20a69341f netfilter: nf_tab... |
2 3 4 |
/* * Copyright (c) 2008-2009 Patrick McHardy <kaber@trash.net> * |
20a69341f netfilter: nf_tab... |
5 6 7 8 9 10 11 12 13 14 15 |
* 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> #include <linux/rbtree.h> #include <linux/netlink.h> #include <linux/netfilter.h> #include <linux/netfilter/nf_tables.h> |
5785cf15f netfilter: nf_tab... |
16 |
#include <net/netfilter/nf_tables_core.h> |
20a69341f netfilter: nf_tab... |
17 18 19 |
struct nft_rbtree { struct rb_root root; |
9b7e26aee netfilter: nft_se... |
20 |
rwlock_t lock; |
b901892b5 netfilter: nft_se... |
21 |
seqcount_rwlock_t count; |
8d8540c4f netfilter: nft_se... |
22 |
struct delayed_work gc_work; |
20a69341f netfilter: nf_tab... |
23 24 25 26 |
}; struct nft_rbtree_elem { struct rb_node node; |
fe2811ebe netfilter: nf_tab... |
27 |
struct nft_set_ext ext; |
20a69341f netfilter: nf_tab... |
28 |
}; |
ef1d20e0f netfilter: nft_rb... |
29 30 31 32 33 |
static bool nft_rbtree_interval_end(const struct nft_rbtree_elem *rbe) { return nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) && (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END); } |
cc02e457b netfilter: nf_tab... |
34 |
|
6f7c9caf0 netfilter: nft_se... |
35 36 37 38 |
static bool nft_rbtree_interval_start(const struct nft_rbtree_elem *rbe) { return !nft_rbtree_interval_end(rbe); } |
e701001e7 netfilter: nft_rb... |
39 40 41 42 43 |
static bool nft_rbtree_equal(const struct nft_set *set, const void *this, const struct nft_rbtree_elem *interval) { return memcmp(this, nft_set_ext_key(&interval->ext), set->klen) == 0; } |
9b7e26aee netfilter: nft_se... |
44 45 46 |
static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *set, const u32 *key, const struct nft_set_ext **ext, unsigned int seq) |
20a69341f netfilter: nf_tab... |
47 |
{ |
03e5fd0e9 netfilter: nft_se... |
48 |
struct nft_rbtree *priv = nft_set_priv(set); |
20a69341f netfilter: nf_tab... |
49 |
const struct nft_rbtree_elem *rbe, *interval = NULL; |
42a557691 netfilter: nf_tab... |
50 |
u8 genmask = nft_genmask_cur(net); |
16c45eda9 netfilter: nft_rb... |
51 |
const struct rb_node *parent; |
e701001e7 netfilter: nft_rb... |
52 |
const void *this; |
20a69341f netfilter: nf_tab... |
53 |
int d; |
9b7e26aee netfilter: nft_se... |
54 |
parent = rcu_dereference_raw(priv->root.rb_node); |
20a69341f netfilter: nf_tab... |
55 |
while (parent != NULL) { |
9b7e26aee netfilter: nft_se... |
56 57 |
if (read_seqcount_retry(&priv->count, seq)) return false; |
20a69341f netfilter: nf_tab... |
58 |
rbe = rb_entry(parent, struct nft_rbtree_elem, node); |
e701001e7 netfilter: nft_rb... |
59 60 |
this = nft_set_ext_key(&rbe->ext); d = memcmp(this, key, set->klen); |
20a69341f netfilter: nf_tab... |
61 |
if (d < 0) { |
9b7e26aee netfilter: nft_se... |
62 |
parent = rcu_dereference_raw(parent->rb_left); |
f9121355e netfilter: nft_se... |
63 64 |
if (interval && nft_rbtree_equal(set, this, interval) && |
82e20b444 netfilter: nft_se... |
65 |
nft_rbtree_interval_end(rbe) && |
6f7c9caf0 netfilter: nft_se... |
66 |
nft_rbtree_interval_start(interval)) |
e701001e7 netfilter: nft_rb... |
67 |
continue; |
20a69341f netfilter: nf_tab... |
68 69 |
interval = rbe; } else if (d > 0) |
9b7e26aee netfilter: nft_se... |
70 |
parent = rcu_dereference_raw(parent->rb_right); |
20a69341f netfilter: nf_tab... |
71 |
else { |
cc02e457b netfilter: nf_tab... |
72 |
if (!nft_set_elem_active(&rbe->ext, genmask)) { |
9b7e26aee netfilter: nft_se... |
73 |
parent = rcu_dereference_raw(parent->rb_left); |
cc02e457b netfilter: nf_tab... |
74 75 |
continue; } |
340eaff65 netfilter: nft_se... |
76 77 78 |
if (nft_set_elem_expired(&rbe->ext)) return false; |
db3b665dd netfilter: nft_se... |
79 80 81 82 83 84 85 |
if (nft_rbtree_interval_end(rbe)) { if (nft_set_is_anonymous(set)) return false; parent = rcu_dereference_raw(parent->rb_left); interval = NULL; continue; } |
b2832dd66 netfilter: nf_tab... |
86 87 |
*ext = &rbe->ext; |
20a69341f netfilter: nf_tab... |
88 89 90 |
return true; } } |
c1eda3c63 netfilter: nft_rb... |
91 92 |
if (set->flags & NFT_SET_INTERVAL && interval != NULL && nft_set_elem_active(&interval->ext, genmask) && |
340eaff65 netfilter: nft_se... |
93 |
!nft_set_elem_expired(&interval->ext) && |
6f7c9caf0 netfilter: nft_se... |
94 |
nft_rbtree_interval_start(interval)) { |
c1eda3c63 netfilter: nft_rb... |
95 96 |
*ext = &interval->ext; return true; |
20a69341f netfilter: nf_tab... |
97 |
} |
db3b665dd netfilter: nft_se... |
98 |
|
20a69341f netfilter: nf_tab... |
99 100 |
return false; } |
9b7e26aee netfilter: nft_se... |
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
static bool nft_rbtree_lookup(const struct net *net, const struct nft_set *set, const u32 *key, const struct nft_set_ext **ext) { struct nft_rbtree *priv = nft_set_priv(set); unsigned int seq = read_seqcount_begin(&priv->count); bool ret; ret = __nft_rbtree_lookup(net, set, key, ext, seq); if (ret || !read_seqcount_retry(&priv->count, seq)) return ret; read_lock_bh(&priv->lock); seq = read_seqcount_begin(&priv->count); ret = __nft_rbtree_lookup(net, set, key, ext, seq); read_unlock_bh(&priv->lock); return ret; } |
ba0e4d991 netfilter: nf_tab... |
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
static bool __nft_rbtree_get(const struct net *net, const struct nft_set *set, const u32 *key, struct nft_rbtree_elem **elem, unsigned int seq, unsigned int flags, u8 genmask) { struct nft_rbtree_elem *rbe, *interval = NULL; struct nft_rbtree *priv = nft_set_priv(set); const struct rb_node *parent; const void *this; int d; parent = rcu_dereference_raw(priv->root.rb_node); while (parent != NULL) { if (read_seqcount_retry(&priv->count, seq)) return false; rbe = rb_entry(parent, struct nft_rbtree_elem, node); this = nft_set_ext_key(&rbe->ext); d = memcmp(this, key, set->klen); if (d < 0) { parent = rcu_dereference_raw(parent->rb_left); |
3b18d5eba netfilter: nft_se... |
140 141 |
if (!(flags & NFT_SET_ELEM_INTERVAL_END)) interval = rbe; |
ba0e4d991 netfilter: nf_tab... |
142 143 |
} else if (d > 0) { parent = rcu_dereference_raw(parent->rb_right); |
3b18d5eba netfilter: nft_se... |
144 145 |
if (flags & NFT_SET_ELEM_INTERVAL_END) interval = rbe; |
ba0e4d991 netfilter: nf_tab... |
146 |
} else { |
db3b665dd netfilter: nft_se... |
147 |
if (!nft_set_elem_active(&rbe->ext, genmask)) { |
ba0e4d991 netfilter: nf_tab... |
148 |
parent = rcu_dereference_raw(parent->rb_left); |
db3b665dd netfilter: nft_se... |
149 150 |
continue; } |
ba0e4d991 netfilter: nf_tab... |
151 |
|
340eaff65 netfilter: nft_se... |
152 153 |
if (nft_set_elem_expired(&rbe->ext)) return false; |
ba0e4d991 netfilter: nf_tab... |
154 155 156 157 158 159 |
if (!nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) || (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END) == (flags & NFT_SET_ELEM_INTERVAL_END)) { *elem = rbe; return true; } |
db3b665dd netfilter: nft_se... |
160 161 162 163 164 |
if (nft_rbtree_interval_end(rbe)) interval = NULL; parent = rcu_dereference_raw(parent->rb_left); |
ba0e4d991 netfilter: nf_tab... |
165 166 167 168 169 |
} } if (set->flags & NFT_SET_INTERVAL && interval != NULL && nft_set_elem_active(&interval->ext, genmask) && |
340eaff65 netfilter: nft_se... |
170 |
!nft_set_elem_expired(&interval->ext) && |
3b18d5eba netfilter: nft_se... |
171 172 173 174 |
((!nft_rbtree_interval_end(interval) && !(flags & NFT_SET_ELEM_INTERVAL_END)) || (nft_rbtree_interval_end(interval) && (flags & NFT_SET_ELEM_INTERVAL_END)))) { |
ba0e4d991 netfilter: nf_tab... |
175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 |
*elem = interval; return true; } return false; } static void *nft_rbtree_get(const struct net *net, const struct nft_set *set, const struct nft_set_elem *elem, unsigned int flags) { struct nft_rbtree *priv = nft_set_priv(set); unsigned int seq = read_seqcount_begin(&priv->count); struct nft_rbtree_elem *rbe = ERR_PTR(-ENOENT); const u32 *key = (const u32 *)&elem->key.val; u8 genmask = nft_genmask_cur(net); bool ret; ret = __nft_rbtree_get(net, set, key, &rbe, seq, flags, genmask); if (ret || !read_seqcount_retry(&priv->count, seq)) return rbe; read_lock_bh(&priv->lock); seq = read_seqcount_begin(&priv->count); ret = __nft_rbtree_get(net, set, key, &rbe, seq, flags, genmask); if (!ret) rbe = ERR_PTR(-ENOENT); read_unlock_bh(&priv->lock); return rbe; } |
42a557691 netfilter: nf_tab... |
205 |
static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, |
c016c7e45 netfilter: nf_tab... |
206 207 |
struct nft_rbtree_elem *new, struct nft_set_ext **ext) |
20a69341f netfilter: nf_tab... |
208 |
{ |
072676304 netfilter: nft_se... |
209 |
bool overlap = false, dup_end_left = false, dup_end_right = false; |
20a69341f netfilter: nf_tab... |
210 |
struct nft_rbtree *priv = nft_set_priv(set); |
42a557691 netfilter: nf_tab... |
211 |
u8 genmask = nft_genmask_next(net); |
20a69341f netfilter: nf_tab... |
212 213 214 |
struct nft_rbtree_elem *rbe; struct rb_node *parent, **p; int d; |
7c84d4141 netfilter: nft_se... |
215 216 |
/* Detect overlaps as we descend the tree. Set the flag in these cases: * |
72239f279 netfilter: nft_se... |
217 218 219 |
* a1. _ _ __>| ?_ _ __| (insert end before existing end) * a2. _ _ ___| ?_ _ _>| (insert end after existing end) * a3. _ _ ___? >|_ _ __| (insert start before existing end) |
7c84d4141 netfilter: nft_se... |
220 221 222 223 224 225 |
* * and clear it later on, as we eventually reach the points indicated by * '?' above, in the cases described below. We'll always meet these * later, locally, due to tree ordering, and overlaps for the intervals * that are the closest together are always evaluated last. * |
72239f279 netfilter: nft_se... |
226 227 |
* b1. _ _ __>| !_ _ __| (insert end before existing start) * b2. _ _ ___| !_ _ _>| (insert end after existing start) |
226a88de4 netfilter: nft_se... |
228 229 230 |
* b3. _ _ ___! >|_ _ __| (insert start after existing end, as a leaf) * '--' no nodes falling in this range * b4. >|_ _ ! (insert start before existing start) |
7c84d4141 netfilter: nft_se... |
231 |
* |
72239f279 netfilter: nft_se... |
232 |
* Case a3. resolves to b3.: |
7c84d4141 netfilter: nft_se... |
233 234 |
* - if the inserted start element is the leftmost, because the '0' * element in the tree serves as end element |
226a88de4 netfilter: nft_se... |
235 236 237 238 239 240 |
* - otherwise, if an existing end is found immediately to the left. If * there are existing nodes in between, we need to further descend the * tree before we can conclude the new start isn't causing an overlap * * or to b4., which, preceded by a3., means we already traversed one or * more existing intervals entirely, from the right. |
7c84d4141 netfilter: nft_se... |
241 |
* |
72239f279 netfilter: nft_se... |
242 |
* For a new, rightmost pair of elements, we'll hit cases b3. and b2., |
7c84d4141 netfilter: nft_se... |
243 244 245 246 |
* in that order. * * The flag is also cleared in two special cases: * |
226a88de4 netfilter: nft_se... |
247 248 |
* b5. |__ _ _!|<_ _ _ (insert start right before existing end) * b6. |__ _ >|!__ _ _ (insert end right after existing start) |
7c84d4141 netfilter: nft_se... |
249 250 251 |
* * which always happen as last step and imply that no further * overlapping is possible. |
072676304 netfilter: nft_se... |
252 253 254 255 256 257 258 259 260 261 262 263 264 265 |
* * Another special case comes from the fact that start elements matching * an already existing start element are allowed: insertion is not * performed but we return -EEXIST in that case, and the error will be * cleared by the caller if NLM_F_EXCL is not present in the request. * This way, request for insertion of an exact overlap isn't reported as * error to userspace if not desired. * * However, if the existing start matches a pre-existing start, but the * end element doesn't match the corresponding pre-existing end element, * we need to report a partial overlap. This is a local condition that * can be noticed without need for a tracking flag, by checking for a * local duplicated end for a corresponding start, from left and right, * separately. |
7c84d4141 netfilter: nft_se... |
266 |
*/ |
20a69341f netfilter: nf_tab... |
267 268 269 270 271 |
parent = NULL; p = &priv->root.rb_node; while (*p != NULL) { parent = *p; rbe = rb_entry(parent, struct nft_rbtree_elem, node); |
e562d860d netfilter: nf_tab... |
272 273 274 |
d = memcmp(nft_set_ext_key(&rbe->ext), nft_set_ext_key(&new->ext), set->klen); |
7c84d4141 netfilter: nft_se... |
275 |
if (d < 0) { |
20a69341f netfilter: nf_tab... |
276 |
p = &parent->rb_left; |
7c84d4141 netfilter: nft_se... |
277 278 |
if (nft_rbtree_interval_start(new)) { |
72239f279 netfilter: nft_se... |
279 |
if (nft_rbtree_interval_end(rbe) && |
33d077996 netfilter: nft_se... |
280 |
nft_set_elem_active(&rbe->ext, genmask) && |
226a88de4 netfilter: nft_se... |
281 |
!nft_set_elem_expired(&rbe->ext) && !*p) |
72239f279 netfilter: nft_se... |
282 |
overlap = false; |
7c84d4141 netfilter: nft_se... |
283 |
} else { |
072676304 netfilter: nft_se... |
284 285 |
if (dup_end_left && !*p) return -ENOTEMPTY; |
7c84d4141 netfilter: nft_se... |
286 287 |
overlap = nft_rbtree_interval_end(rbe) && nft_set_elem_active(&rbe->ext, |
33d077996 netfilter: nft_se... |
288 289 |
genmask) && !nft_set_elem_expired(&rbe->ext); |
072676304 netfilter: nft_se... |
290 291 292 293 294 |
if (overlap) { dup_end_right = true; continue; } |
7c84d4141 netfilter: nft_se... |
295 296 |
} } else if (d > 0) { |
20a69341f netfilter: nf_tab... |
297 |
p = &parent->rb_right; |
7c84d4141 netfilter: nft_se... |
298 299 |
if (nft_rbtree_interval_end(new)) { |
072676304 netfilter: nft_se... |
300 301 |
if (dup_end_right && !*p) return -ENOTEMPTY; |
7c84d4141 netfilter: nft_se... |
302 303 |
overlap = nft_rbtree_interval_end(rbe) && nft_set_elem_active(&rbe->ext, |
33d077996 netfilter: nft_se... |
304 305 |
genmask) && !nft_set_elem_expired(&rbe->ext); |
072676304 netfilter: nft_se... |
306 307 308 309 310 |
if (overlap) { dup_end_left = true; continue; } |
226a88de4 netfilter: nft_se... |
311 |
} else if (nft_set_elem_active(&rbe->ext, genmask) && |
33d077996 netfilter: nft_se... |
312 |
!nft_set_elem_expired(&rbe->ext)) { |
226a88de4 netfilter: nft_se... |
313 |
overlap = nft_rbtree_interval_end(rbe); |
7c84d4141 netfilter: nft_se... |
314 315 |
} } else { |
d2df92e98 netfilter: nft_se... |
316 |
if (nft_rbtree_interval_end(rbe) && |
6f7c9caf0 netfilter: nft_se... |
317 |
nft_rbtree_interval_start(new)) { |
d2df92e98 netfilter: nft_se... |
318 |
p = &parent->rb_left; |
7c84d4141 netfilter: nft_se... |
319 |
|
33d077996 netfilter: nft_se... |
320 321 |
if (nft_set_elem_active(&rbe->ext, genmask) && !nft_set_elem_expired(&rbe->ext)) |
7c84d4141 netfilter: nft_se... |
322 |
overlap = false; |
6f7c9caf0 netfilter: nft_se... |
323 |
} else if (nft_rbtree_interval_start(rbe) && |
d2df92e98 netfilter: nft_se... |
324 325 |
nft_rbtree_interval_end(new)) { p = &parent->rb_right; |
7c84d4141 netfilter: nft_se... |
326 |
|
33d077996 netfilter: nft_se... |
327 328 |
if (nft_set_elem_active(&rbe->ext, genmask) && !nft_set_elem_expired(&rbe->ext)) |
7c84d4141 netfilter: nft_se... |
329 |
overlap = false; |
33d077996 netfilter: nft_se... |
330 331 |
} else if (nft_set_elem_active(&rbe->ext, genmask) && !nft_set_elem_expired(&rbe->ext)) { |
d2df92e98 netfilter: nft_se... |
332 333 334 335 |
*ext = &rbe->ext; return -EEXIST; } else { p = &parent->rb_left; |
e701001e7 netfilter: nft_rb... |
336 |
} |
cc02e457b netfilter: nf_tab... |
337 |
} |
072676304 netfilter: nft_se... |
338 339 |
dup_end_left = dup_end_right = false; |
20a69341f netfilter: nf_tab... |
340 |
} |
7c84d4141 netfilter: nft_se... |
341 342 343 |
if (overlap) return -ENOTEMPTY; |
9b7e26aee netfilter: nft_se... |
344 |
rb_link_node_rcu(&new->node, parent, p); |
20a69341f netfilter: nf_tab... |
345 346 347 |
rb_insert_color(&new->node, &priv->root); return 0; } |
42a557691 netfilter: nf_tab... |
348 |
static int nft_rbtree_insert(const struct net *net, const struct nft_set *set, |
c016c7e45 netfilter: nf_tab... |
349 350 |
const struct nft_set_elem *elem, struct nft_set_ext **ext) |
20a69341f netfilter: nf_tab... |
351 |
{ |
03e5fd0e9 netfilter: nft_se... |
352 |
struct nft_rbtree *priv = nft_set_priv(set); |
fe2811ebe netfilter: nf_tab... |
353 |
struct nft_rbtree_elem *rbe = elem->priv; |
20a69341f netfilter: nf_tab... |
354 |
int err; |
03e5fd0e9 netfilter: nft_se... |
355 |
write_lock_bh(&priv->lock); |
9b7e26aee netfilter: nft_se... |
356 |
write_seqcount_begin(&priv->count); |
c016c7e45 netfilter: nf_tab... |
357 |
err = __nft_rbtree_insert(net, set, rbe, ext); |
9b7e26aee netfilter: nft_se... |
358 |
write_seqcount_end(&priv->count); |
03e5fd0e9 netfilter: nft_se... |
359 |
write_unlock_bh(&priv->lock); |
fe2811ebe netfilter: nf_tab... |
360 |
|
20a69341f netfilter: nf_tab... |
361 362 |
return err; } |
5cb82a38c netfilter: nf_tab... |
363 364 |
static void nft_rbtree_remove(const struct net *net, const struct nft_set *set, |
20a69341f netfilter: nf_tab... |
365 366 367 |
const struct nft_set_elem *elem) { struct nft_rbtree *priv = nft_set_priv(set); |
cc02e457b netfilter: nf_tab... |
368 |
struct nft_rbtree_elem *rbe = elem->priv; |
20a69341f netfilter: nf_tab... |
369 |
|
03e5fd0e9 netfilter: nft_se... |
370 |
write_lock_bh(&priv->lock); |
9b7e26aee netfilter: nft_se... |
371 |
write_seqcount_begin(&priv->count); |
20a69341f netfilter: nf_tab... |
372 |
rb_erase(&rbe->node, &priv->root); |
9b7e26aee netfilter: nft_se... |
373 |
write_seqcount_end(&priv->count); |
03e5fd0e9 netfilter: nft_se... |
374 |
write_unlock_bh(&priv->lock); |
20a69341f netfilter: nf_tab... |
375 |
} |
42a557691 netfilter: nf_tab... |
376 377 |
static void nft_rbtree_activate(const struct net *net, const struct nft_set *set, |
cc02e457b netfilter: nf_tab... |
378 379 380 |
const struct nft_set_elem *elem) { struct nft_rbtree_elem *rbe = elem->priv; |
42a557691 netfilter: nf_tab... |
381 |
nft_set_elem_change_active(net, set, &rbe->ext); |
8d8540c4f netfilter: nft_se... |
382 |
nft_set_elem_clear_busy(&rbe->ext); |
cc02e457b netfilter: nf_tab... |
383 |
} |
1ba1c4140 netfilter: nf_tab... |
384 385 |
static bool nft_rbtree_flush(const struct net *net, const struct nft_set *set, void *priv) |
37df5301a netfilter: nft_se... |
386 387 |
{ struct nft_rbtree_elem *rbe = priv; |
8d8540c4f netfilter: nft_se... |
388 389 390 391 392 393 |
if (!nft_set_elem_mark_busy(&rbe->ext) || !nft_is_active(net, &rbe->ext)) { nft_set_elem_change_active(net, set, &rbe->ext); return true; } return false; |
37df5301a netfilter: nft_se... |
394 |
} |
42a557691 netfilter: nf_tab... |
395 396 |
static void *nft_rbtree_deactivate(const struct net *net, const struct nft_set *set, |
cc02e457b netfilter: nf_tab... |
397 |
const struct nft_set_elem *elem) |
20a69341f netfilter: nf_tab... |
398 399 400 |
{ const struct nft_rbtree *priv = nft_set_priv(set); const struct rb_node *parent = priv->root.rb_node; |
e701001e7 netfilter: nft_rb... |
401 |
struct nft_rbtree_elem *rbe, *this = elem->priv; |
42a557691 netfilter: nf_tab... |
402 |
u8 genmask = nft_genmask_next(net); |
20a69341f netfilter: nf_tab... |
403 404 405 406 |
int d; while (parent != NULL) { rbe = rb_entry(parent, struct nft_rbtree_elem, node); |
7d7402642 netfilter: nf_tab... |
407 408 |
d = memcmp(nft_set_ext_key(&rbe->ext), &elem->key.val, set->klen); |
20a69341f netfilter: nf_tab... |
409 410 411 412 413 |
if (d < 0) parent = parent->rb_left; else if (d > 0) parent = parent->rb_right; else { |
e701001e7 netfilter: nft_rb... |
414 |
if (nft_rbtree_interval_end(rbe) && |
6f7c9caf0 netfilter: nft_se... |
415 |
nft_rbtree_interval_start(this)) { |
e701001e7 netfilter: nft_rb... |
416 417 |
parent = parent->rb_left; continue; |
6f7c9caf0 netfilter: nft_se... |
418 |
} else if (nft_rbtree_interval_start(rbe) && |
e701001e7 netfilter: nft_rb... |
419 420 421 |
nft_rbtree_interval_end(this)) { parent = parent->rb_right; continue; |
05b7639da netfilter: nft_se... |
422 423 424 |
} else if (!nft_set_elem_active(&rbe->ext, genmask)) { parent = parent->rb_left; continue; |
e701001e7 netfilter: nft_rb... |
425 |
} |
1ba1c4140 netfilter: nf_tab... |
426 |
nft_rbtree_flush(net, set, rbe); |
cc02e457b netfilter: nf_tab... |
427 |
return rbe; |
20a69341f netfilter: nf_tab... |
428 429 |
} } |
cc02e457b netfilter: nf_tab... |
430 |
return NULL; |
20a69341f netfilter: nf_tab... |
431 432 433 |
} static void nft_rbtree_walk(const struct nft_ctx *ctx, |
de70185de netfilter: nf_tab... |
434 |
struct nft_set *set, |
20a69341f netfilter: nf_tab... |
435 436 |
struct nft_set_iter *iter) { |
03e5fd0e9 netfilter: nft_se... |
437 |
struct nft_rbtree *priv = nft_set_priv(set); |
fe2811ebe netfilter: nf_tab... |
438 |
struct nft_rbtree_elem *rbe; |
20a69341f netfilter: nf_tab... |
439 440 |
struct nft_set_elem elem; struct rb_node *node; |
03e5fd0e9 netfilter: nft_se... |
441 |
read_lock_bh(&priv->lock); |
20a69341f netfilter: nf_tab... |
442 |
for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) { |
cc02e457b netfilter: nf_tab... |
443 |
rbe = rb_entry(node, struct nft_rbtree_elem, node); |
20a69341f netfilter: nf_tab... |
444 445 |
if (iter->count < iter->skip) goto cont; |
340eaff65 netfilter: nft_se... |
446 447 |
if (nft_set_elem_expired(&rbe->ext)) goto cont; |
8588ac097 netfilter: nf_tab... |
448 |
if (!nft_set_elem_active(&rbe->ext, iter->genmask)) |
cc02e457b netfilter: nf_tab... |
449 |
goto cont; |
20a69341f netfilter: nf_tab... |
450 |
|
fe2811ebe netfilter: nf_tab... |
451 |
elem.priv = rbe; |
20a69341f netfilter: nf_tab... |
452 453 |
iter->err = iter->fn(ctx, set, iter, &elem); |
7632667d2 netfilter: nft_rb... |
454 |
if (iter->err < 0) { |
03e5fd0e9 netfilter: nft_se... |
455 |
read_unlock_bh(&priv->lock); |
20a69341f netfilter: nf_tab... |
456 |
return; |
7632667d2 netfilter: nft_rb... |
457 |
} |
20a69341f netfilter: nf_tab... |
458 459 460 |
cont: iter->count++; } |
03e5fd0e9 netfilter: nft_se... |
461 |
read_unlock_bh(&priv->lock); |
20a69341f netfilter: nf_tab... |
462 |
} |
8d8540c4f netfilter: nft_se... |
463 464 |
static void nft_rbtree_gc(struct work_struct *work) { |
a13f814a6 netfilter: nft_se... |
465 |
struct nft_rbtree_elem *rbe, *rbe_end = NULL, *rbe_prev = NULL; |
8d8540c4f netfilter: nft_se... |
466 |
struct nft_set_gc_batch *gcb = NULL; |
8d8540c4f netfilter: nft_se... |
467 |
struct nft_rbtree *priv; |
a13f814a6 netfilter: nft_se... |
468 |
struct rb_node *node; |
8d8540c4f netfilter: nft_se... |
469 |
struct nft_set *set; |
8d8540c4f netfilter: nft_se... |
470 471 472 473 474 475 476 477 478 479 |
priv = container_of(work, struct nft_rbtree, gc_work.work); set = nft_set_container_of(priv); write_lock_bh(&priv->lock); write_seqcount_begin(&priv->count); for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) { rbe = rb_entry(node, struct nft_rbtree_elem, node); if (nft_rbtree_interval_end(rbe)) { |
a13f814a6 netfilter: nft_se... |
480 |
rbe_end = rbe; |
8d8540c4f netfilter: nft_se... |
481 482 483 484 485 486 |
continue; } if (!nft_set_elem_expired(&rbe->ext)) continue; if (nft_set_elem_mark_busy(&rbe->ext)) continue; |
a13f814a6 netfilter: nft_se... |
487 488 489 490 |
if (rbe_prev) { rb_erase(&rbe_prev->node, &priv->root); rbe_prev = NULL; } |
8d8540c4f netfilter: nft_se... |
491 492 |
gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC); if (!gcb) |
c293ac959 netfilter: nft_se... |
493 |
break; |
8d8540c4f netfilter: nft_se... |
494 495 496 |
atomic_dec(&set->nelems); nft_set_gc_batch_add(gcb, rbe); |
a13f814a6 netfilter: nft_se... |
497 |
rbe_prev = rbe; |
8d8540c4f netfilter: nft_se... |
498 |
|
a13f814a6 netfilter: nft_se... |
499 |
if (rbe_end) { |
8d8540c4f netfilter: nft_se... |
500 |
atomic_dec(&set->nelems); |
a13f814a6 netfilter: nft_se... |
501 502 503 |
nft_set_gc_batch_add(gcb, rbe_end); rb_erase(&rbe_end->node, &priv->root); rbe_end = NULL; |
8d8540c4f netfilter: nft_se... |
504 505 |
} node = rb_next(node); |
c293ac959 netfilter: nft_se... |
506 507 |
if (!node) break; |
8d8540c4f netfilter: nft_se... |
508 |
} |
a13f814a6 netfilter: nft_se... |
509 510 |
if (rbe_prev) rb_erase(&rbe_prev->node, &priv->root); |
8d8540c4f netfilter: nft_se... |
511 512 513 514 515 516 517 518 |
write_seqcount_end(&priv->count); write_unlock_bh(&priv->lock); nft_set_gc_batch_complete(gcb); queue_delayed_work(system_power_efficient_wq, &priv->gc_work, nft_set_gc_interval(set)); } |
4ef360dd6 netfilter: nft_se... |
519 520 |
static u64 nft_rbtree_privsize(const struct nlattr * const nla[], const struct nft_set_desc *desc) |
20a69341f netfilter: nf_tab... |
521 522 523 524 525 |
{ return sizeof(struct nft_rbtree); } static int nft_rbtree_init(const struct nft_set *set, |
c50b960cc netfilter: nf_tab... |
526 |
const struct nft_set_desc *desc, |
20a69341f netfilter: nf_tab... |
527 528 529 |
const struct nlattr * const nla[]) { struct nft_rbtree *priv = nft_set_priv(set); |
03e5fd0e9 netfilter: nft_se... |
530 |
rwlock_init(&priv->lock); |
b901892b5 netfilter: nft_se... |
531 |
seqcount_rwlock_init(&priv->count, &priv->lock); |
20a69341f netfilter: nf_tab... |
532 |
priv->root = RB_ROOT; |
8d8540c4f netfilter: nft_se... |
533 534 535 536 537 |
INIT_DEFERRABLE_WORK(&priv->gc_work, nft_rbtree_gc); if (set->flags & NFT_SET_TIMEOUT) queue_delayed_work(system_power_efficient_wq, &priv->gc_work, nft_set_gc_interval(set)); |
20a69341f netfilter: nf_tab... |
538 539 540 541 542 543 544 545 |
return 0; } static void nft_rbtree_destroy(const struct nft_set *set) { struct nft_rbtree *priv = nft_set_priv(set); struct nft_rbtree_elem *rbe; struct rb_node *node; |
8d8540c4f netfilter: nft_se... |
546 |
cancel_delayed_work_sync(&priv->gc_work); |
c293ac959 netfilter: nft_se... |
547 |
rcu_barrier(); |
20a69341f netfilter: nf_tab... |
548 549 550 |
while ((node = priv->root.rb_node) != NULL) { rb_erase(node, &priv->root); rbe = rb_entry(node, struct nft_rbtree_elem, node); |
61f9e2924 netfilter: nf_tab... |
551 |
nft_set_elem_destroy(set, rbe, true); |
20a69341f netfilter: nf_tab... |
552 553 |
} } |
c50b960cc netfilter: nf_tab... |
554 555 556 |
static bool nft_rbtree_estimate(const struct nft_set_desc *desc, u32 features, struct nft_set_estimate *est) { |
f3a2181e1 netfilter: nf_tab... |
557 558 |
if (desc->field_count > 1) return false; |
c50b960cc netfilter: nf_tab... |
559 |
if (desc->size) |
080ed636a netfilter: nf_tab... |
560 561 |
est->size = sizeof(struct nft_rbtree) + desc->size * sizeof(struct nft_rbtree_elem); |
c50b960cc netfilter: nf_tab... |
562 |
else |
080ed636a netfilter: nf_tab... |
563 |
est->size = ~0; |
c50b960cc netfilter: nf_tab... |
564 |
|
55af753cd netfilter: nf_tab... |
565 |
est->lookup = NFT_SET_CLASS_O_LOG_N; |
0b5a78749 netfilter: nf_tab... |
566 |
est->space = NFT_SET_CLASS_O_N; |
c50b960cc netfilter: nf_tab... |
567 568 569 |
return true; } |
24d19826f netfilter: nf_tab... |
570 |
const struct nft_set_type nft_set_rbtree_type = { |
8d8540c4f netfilter: nft_se... |
571 |
.features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT | NFT_SET_TIMEOUT, |
71cc0873e netfilter: nf_tab... |
572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 |
.ops = { .privsize = nft_rbtree_privsize, .elemsize = offsetof(struct nft_rbtree_elem, ext), .estimate = nft_rbtree_estimate, .init = nft_rbtree_init, .destroy = nft_rbtree_destroy, .insert = nft_rbtree_insert, .remove = nft_rbtree_remove, .deactivate = nft_rbtree_deactivate, .flush = nft_rbtree_flush, .activate = nft_rbtree_activate, .lookup = nft_rbtree_lookup, .walk = nft_rbtree_walk, .get = nft_rbtree_get, }, |
20a69341f netfilter: nf_tab... |
587 |
}; |