2 * Copyright (c) 2008-2009 Patrick McHardy <kaber@trash.net>
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.
8 * Development of this code funded by Astaro AG (http://www.astaro.com/)
11 #include <linux/kernel.h>
12 #include <linux/init.h>
13 #include <linux/module.h>
14 #include <linux/list.h>
15 #include <linux/rbtree.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>
21 static DEFINE_SPINLOCK(nft_rbtree_lock
);
27 struct nft_rbtree_elem
{
29 struct nft_set_ext ext
;
32 static bool nft_rbtree_interval_end(const struct nft_rbtree_elem
*rbe
)
34 return nft_set_ext_exists(&rbe
->ext
, NFT_SET_EXT_FLAGS
) &&
35 (*nft_set_ext_flags(&rbe
->ext
) & NFT_SET_ELEM_INTERVAL_END
);
38 static bool nft_rbtree_lookup(const struct nft_set
*set
, const u32
*key
,
39 const struct nft_set_ext
**ext
)
41 const struct nft_rbtree
*priv
= nft_set_priv(set
);
42 const struct nft_rbtree_elem
*rbe
, *interval
= NULL
;
43 const struct rb_node
*parent
;
44 u8 genmask
= nft_genmask_cur(read_pnet(&set
->pnet
));
47 spin_lock_bh(&nft_rbtree_lock
);
48 parent
= priv
->root
.rb_node
;
49 while (parent
!= NULL
) {
50 rbe
= rb_entry(parent
, struct nft_rbtree_elem
, node
);
52 d
= memcmp(nft_set_ext_key(&rbe
->ext
), key
, set
->klen
);
54 parent
= parent
->rb_left
;
57 parent
= parent
->rb_right
;
60 if (!nft_set_elem_active(&rbe
->ext
, genmask
)) {
61 parent
= parent
->rb_left
;
64 if (nft_rbtree_interval_end(rbe
))
66 spin_unlock_bh(&nft_rbtree_lock
);
73 if (set
->flags
& NFT_SET_INTERVAL
&& interval
!= NULL
) {
78 spin_unlock_bh(&nft_rbtree_lock
);
82 static int __nft_rbtree_insert(const struct nft_set
*set
,
83 struct nft_rbtree_elem
*new)
85 struct nft_rbtree
*priv
= nft_set_priv(set
);
86 struct nft_rbtree_elem
*rbe
;
87 struct rb_node
*parent
, **p
;
88 u8 genmask
= nft_genmask_next(read_pnet(&set
->pnet
));
92 p
= &priv
->root
.rb_node
;
95 rbe
= rb_entry(parent
, struct nft_rbtree_elem
, node
);
96 d
= memcmp(nft_set_ext_key(&rbe
->ext
),
97 nft_set_ext_key(&new->ext
),
100 p
= &parent
->rb_left
;
102 p
= &parent
->rb_right
;
104 if (nft_set_elem_active(&rbe
->ext
, genmask
))
106 p
= &parent
->rb_left
;
109 rb_link_node(&new->node
, parent
, p
);
110 rb_insert_color(&new->node
, &priv
->root
);
114 static int nft_rbtree_insert(const struct nft_set
*set
,
115 const struct nft_set_elem
*elem
)
117 struct nft_rbtree_elem
*rbe
= elem
->priv
;
120 spin_lock_bh(&nft_rbtree_lock
);
121 err
= __nft_rbtree_insert(set
, rbe
);
122 spin_unlock_bh(&nft_rbtree_lock
);
127 static void nft_rbtree_remove(const struct nft_set
*set
,
128 const struct nft_set_elem
*elem
)
130 struct nft_rbtree
*priv
= nft_set_priv(set
);
131 struct nft_rbtree_elem
*rbe
= elem
->priv
;
133 spin_lock_bh(&nft_rbtree_lock
);
134 rb_erase(&rbe
->node
, &priv
->root
);
135 spin_unlock_bh(&nft_rbtree_lock
);
138 static void nft_rbtree_activate(const struct nft_set
*set
,
139 const struct nft_set_elem
*elem
)
141 struct nft_rbtree_elem
*rbe
= elem
->priv
;
143 nft_set_elem_change_active(set
, &rbe
->ext
);
146 static void *nft_rbtree_deactivate(const struct nft_set
*set
,
147 const struct nft_set_elem
*elem
)
149 const struct nft_rbtree
*priv
= nft_set_priv(set
);
150 const struct rb_node
*parent
= priv
->root
.rb_node
;
151 struct nft_rbtree_elem
*rbe
;
152 u8 genmask
= nft_genmask_cur(read_pnet(&set
->pnet
));
155 while (parent
!= NULL
) {
156 rbe
= rb_entry(parent
, struct nft_rbtree_elem
, node
);
158 d
= memcmp(nft_set_ext_key(&rbe
->ext
), &elem
->key
.val
,
161 parent
= parent
->rb_left
;
163 parent
= parent
->rb_right
;
165 if (!nft_set_elem_active(&rbe
->ext
, genmask
)) {
166 parent
= parent
->rb_left
;
169 nft_set_elem_change_active(set
, &rbe
->ext
);
176 static void nft_rbtree_walk(const struct nft_ctx
*ctx
,
177 const struct nft_set
*set
,
178 struct nft_set_iter
*iter
)
180 const struct nft_rbtree
*priv
= nft_set_priv(set
);
181 struct nft_rbtree_elem
*rbe
;
182 struct nft_set_elem elem
;
183 struct rb_node
*node
;
184 u8 genmask
= nft_genmask_cur(read_pnet(&set
->pnet
));
186 spin_lock_bh(&nft_rbtree_lock
);
187 for (node
= rb_first(&priv
->root
); node
!= NULL
; node
= rb_next(node
)) {
188 rbe
= rb_entry(node
, struct nft_rbtree_elem
, node
);
190 if (iter
->count
< iter
->skip
)
192 if (!nft_set_elem_active(&rbe
->ext
, genmask
))
197 iter
->err
= iter
->fn(ctx
, set
, iter
, &elem
);
199 spin_unlock_bh(&nft_rbtree_lock
);
205 spin_unlock_bh(&nft_rbtree_lock
);
208 static unsigned int nft_rbtree_privsize(const struct nlattr
* const nla
[])
210 return sizeof(struct nft_rbtree
);
213 static int nft_rbtree_init(const struct nft_set
*set
,
214 const struct nft_set_desc
*desc
,
215 const struct nlattr
* const nla
[])
217 struct nft_rbtree
*priv
= nft_set_priv(set
);
219 priv
->root
= RB_ROOT
;
223 static void nft_rbtree_destroy(const struct nft_set
*set
)
225 struct nft_rbtree
*priv
= nft_set_priv(set
);
226 struct nft_rbtree_elem
*rbe
;
227 struct rb_node
*node
;
229 while ((node
= priv
->root
.rb_node
) != NULL
) {
230 rb_erase(node
, &priv
->root
);
231 rbe
= rb_entry(node
, struct nft_rbtree_elem
, node
);
232 nft_set_elem_destroy(set
, rbe
);
236 static bool nft_rbtree_estimate(const struct nft_set_desc
*desc
, u32 features
,
237 struct nft_set_estimate
*est
)
241 nsize
= sizeof(struct nft_rbtree_elem
);
243 est
->size
= sizeof(struct nft_rbtree
) + desc
->size
* nsize
;
247 est
->class = NFT_SET_CLASS_O_LOG_N
;
252 static struct nft_set_ops nft_rbtree_ops __read_mostly
= {
253 .privsize
= nft_rbtree_privsize
,
254 .elemsize
= offsetof(struct nft_rbtree_elem
, ext
),
255 .estimate
= nft_rbtree_estimate
,
256 .init
= nft_rbtree_init
,
257 .destroy
= nft_rbtree_destroy
,
258 .insert
= nft_rbtree_insert
,
259 .remove
= nft_rbtree_remove
,
260 .deactivate
= nft_rbtree_deactivate
,
261 .activate
= nft_rbtree_activate
,
262 .lookup
= nft_rbtree_lookup
,
263 .walk
= nft_rbtree_walk
,
264 .features
= NFT_SET_INTERVAL
| NFT_SET_MAP
,
265 .owner
= THIS_MODULE
,
268 static int __init
nft_rbtree_module_init(void)
270 return nft_register_set(&nft_rbtree_ops
);
273 static void __exit
nft_rbtree_module_exit(void)
275 nft_unregister_set(&nft_rbtree_ops
);
278 module_init(nft_rbtree_module_init
);
279 module_exit(nft_rbtree_module_exit
);
281 MODULE_LICENSE("GPL");
282 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
283 MODULE_ALIAS_NFT_SET();