2 * net/sched/ematch.c Extended Match API
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
9 * Authors: Thomas Graf <tgraf@suug.ch>
11 * ==========================================================================
13 * An extended match (ematch) is a small classification tool not worth
14 * writing a full classifier for. Ematches can be interconnected to form
15 * a logic expression and get attached to classifiers to extend their
18 * The userspace part transforms the logic expressions into an array
19 * consisting of multiple sequences of interconnected ematches separated
20 * by markers. Precedence is implemented by a special ematch kind
21 * referencing a sequence beyond the marker of the current sequence
22 * causing the current position in the sequence to be pushed onto a stack
23 * to allow the current position to be overwritten by the position referenced
24 * in the special ematch. Matching continues in the new sequence until a
25 * marker is reached causing the position to be restored from the stack.
28 * A AND (B1 OR B2) AND C AND D
30 * ------->-PUSH-------
31 * -->-- / -->-- \ -->--
33 * +-------+-------+-------+-------+-------+--------+
34 * | A AND | B AND | C AND | D END | B1 OR | B2 END |
35 * +-------+-------+-------+-------+-------+--------+
37 * --------<-POP---------
39 * where B is a virtual ematch referencing to sequence starting with B1.
41 * ==========================================================================
43 * How to write an ematch in 60 seconds
44 * ------------------------------------
46 * 1) Provide a matcher function:
47 * static int my_match(struct sk_buff *skb, struct tcf_ematch *m,
48 * struct tcf_pkt_info *info)
50 * struct mydata *d = (struct mydata *) m->data;
52 * if (...matching goes here...)
58 * 2) Fill out a struct tcf_ematch_ops:
59 * static struct tcf_ematch_ops my_ops = {
61 * .datalen = sizeof(struct mydata),
63 * .owner = THIS_MODULE,
66 * 3) Register/Unregister your ematch:
67 * static int __init init_my_ematch(void)
69 * return tcf_em_register(&my_ops);
72 * static void __exit exit_my_ematch(void)
74 * tcf_em_unregister(&my_ops);
77 * module_init(init_my_ematch);
78 * module_exit(exit_my_ematch);
80 * 4) By now you should have two more seconds left, barely enough to
81 * open up a beer to watch the compilation going.
84 #include <linux/module.h>
85 #include <linux/types.h>
86 #include <linux/kernel.h>
87 #include <linux/errno.h>
88 #include <linux/rtnetlink.h>
89 #include <linux/skbuff.h>
90 #include <net/pkt_cls.h>
92 static LIST_HEAD(ematch_ops
);
93 static DEFINE_RWLOCK(ematch_mod_lock
);
95 static inline struct tcf_ematch_ops
* tcf_em_lookup(u16 kind
)
97 struct tcf_ematch_ops
*e
= NULL
;
99 read_lock(&ematch_mod_lock
);
100 list_for_each_entry(e
, &ematch_ops
, link
) {
101 if (kind
== e
->kind
) {
102 if (!try_module_get(e
->owner
))
104 read_unlock(&ematch_mod_lock
);
108 read_unlock(&ematch_mod_lock
);
114 * tcf_em_register - register an extended match
116 * @ops: ematch operations lookup table
118 * This function must be called by ematches to announce their presence.
119 * The given @ops must have kind set to a unique identifier and the
120 * callback match() must be implemented. All other callbacks are optional
121 * and a fallback implementation is used instead.
123 * Returns -EEXISTS if an ematch of the same kind has already registered.
125 int tcf_em_register(struct tcf_ematch_ops
*ops
)
128 struct tcf_ematch_ops
*e
;
130 if (ops
->match
== NULL
)
133 write_lock(&ematch_mod_lock
);
134 list_for_each_entry(e
, &ematch_ops
, link
)
135 if (ops
->kind
== e
->kind
)
138 list_add_tail(&ops
->link
, &ematch_ops
);
141 write_unlock(&ematch_mod_lock
);
144 EXPORT_SYMBOL(tcf_em_register
);
147 * tcf_em_unregister - unregster and extended match
149 * @ops: ematch operations lookup table
151 * This function must be called by ematches to announce their disappearance
152 * for examples when the module gets unloaded. The @ops parameter must be
153 * the same as the one used for registration.
155 * Returns -ENOENT if no matching ematch was found.
157 void tcf_em_unregister(struct tcf_ematch_ops
*ops
)
159 write_lock(&ematch_mod_lock
);
160 list_del(&ops
->link
);
161 write_unlock(&ematch_mod_lock
);
163 EXPORT_SYMBOL(tcf_em_unregister
);
165 static inline struct tcf_ematch
* tcf_em_get_match(struct tcf_ematch_tree
*tree
,
168 return &tree
->matches
[index
];
172 static int tcf_em_validate(struct tcf_proto
*tp
,
173 struct tcf_ematch_tree_hdr
*tree_hdr
,
174 struct tcf_ematch
*em
, struct nlattr
*nla
, int idx
)
177 struct tcf_ematch_hdr
*em_hdr
= nla_data(nla
);
178 int data_len
= nla_len(nla
) - sizeof(*em_hdr
);
179 void *data
= (void *) em_hdr
+ sizeof(*em_hdr
);
181 if (!TCF_EM_REL_VALID(em_hdr
->flags
))
184 if (em_hdr
->kind
== TCF_EM_CONTAINER
) {
185 /* Special ematch called "container", carries an index
186 * referencing an external ematch sequence. */
189 if (data_len
< sizeof(ref
))
193 if (ref
>= tree_hdr
->nmatches
)
196 /* We do not allow backward jumps to avoid loops and jumps
197 * to our own position are of course illegal. */
204 /* Note: This lookup will increase the module refcnt
205 * of the ematch module referenced. In case of a failure,
206 * a destroy function is called by the underlying layer
207 * which automatically releases the reference again, therefore
208 * the module MUST not be given back under any circumstances
209 * here. Be aware, the destroy function assumes that the
210 * module is held if the ops field is non zero. */
211 em
->ops
= tcf_em_lookup(em_hdr
->kind
);
213 if (em
->ops
== NULL
) {
215 #ifdef CONFIG_MODULES
217 request_module("ematch-kind-%u", em_hdr
->kind
);
219 em
->ops
= tcf_em_lookup(em_hdr
->kind
);
221 /* We dropped the RTNL mutex in order to
222 * perform the module load. Tell the caller
223 * to replay the request. */
224 module_put(em
->ops
->owner
);
231 /* ematch module provides expected length of data, so we
232 * can do a basic sanity check. */
233 if (em
->ops
->datalen
&& data_len
< em
->ops
->datalen
)
236 if (em
->ops
->change
) {
237 err
= em
->ops
->change(tp
, data
, data_len
, em
);
240 } else if (data_len
> 0) {
241 /* ematch module doesn't provide an own change
242 * procedure and expects us to allocate and copy
245 * TCF_EM_SIMPLE may be specified stating that the
246 * data only consists of a u32 integer and the module
247 * does not expected a memory reference but rather
248 * the value carried. */
249 if (em_hdr
->flags
& TCF_EM_SIMPLE
) {
250 if (data_len
< sizeof(u32
))
252 em
->data
= *(u32
*) data
;
254 void *v
= kmemdup(data
, data_len
, GFP_KERNEL
);
259 em
->data
= (unsigned long) v
;
264 em
->matchid
= em_hdr
->matchid
;
265 em
->flags
= em_hdr
->flags
;
266 em
->datalen
= data_len
;
273 static const struct nla_policy em_policy
[TCA_EMATCH_TREE_MAX
+ 1] = {
274 [TCA_EMATCH_TREE_HDR
] = { .len
= sizeof(struct tcf_ematch_tree_hdr
) },
275 [TCA_EMATCH_TREE_LIST
] = { .type
= NLA_NESTED
},
279 * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
281 * @tp: classifier kind handle
282 * @nla: ematch tree configuration TLV
283 * @tree: destination ematch tree variable to store the resulting
286 * This function validates the given configuration TLV @nla and builds an
287 * ematch tree in @tree. The resulting tree must later be copied into
288 * the private classifier data using tcf_em_tree_change(). You MUST NOT
289 * provide the ematch tree variable of the private classifier data directly,
290 * the changes would not be locked properly.
292 * Returns a negative error code if the configuration TLV contains errors.
294 int tcf_em_tree_validate(struct tcf_proto
*tp
, struct nlattr
*nla
,
295 struct tcf_ematch_tree
*tree
)
297 int idx
, list_len
, matches_len
, err
;
298 struct nlattr
*tb
[TCA_EMATCH_TREE_MAX
+ 1];
299 struct nlattr
*rt_match
, *rt_hdr
, *rt_list
;
300 struct tcf_ematch_tree_hdr
*tree_hdr
;
301 struct tcf_ematch
*em
;
303 memset(tree
, 0, sizeof(*tree
));
307 err
= nla_parse_nested(tb
, TCA_EMATCH_TREE_MAX
, nla
, em_policy
);
312 rt_hdr
= tb
[TCA_EMATCH_TREE_HDR
];
313 rt_list
= tb
[TCA_EMATCH_TREE_LIST
];
315 if (rt_hdr
== NULL
|| rt_list
== NULL
)
318 tree_hdr
= nla_data(rt_hdr
);
319 memcpy(&tree
->hdr
, tree_hdr
, sizeof(*tree_hdr
));
321 rt_match
= nla_data(rt_list
);
322 list_len
= nla_len(rt_list
);
323 matches_len
= tree_hdr
->nmatches
* sizeof(*em
);
325 tree
->matches
= kzalloc(matches_len
, GFP_KERNEL
);
326 if (tree
->matches
== NULL
)
329 /* We do not use nla_parse_nested here because the maximum
330 * number of attributes is unknown. This saves us the allocation
331 * for a tb buffer which would serve no purpose at all.
333 * The array of rt attributes is parsed in the order as they are
334 * provided, their type must be incremental from 1 to n. Even
335 * if it does not serve any real purpose, a failure of sticking
336 * to this policy will result in parsing failure. */
337 for (idx
= 0; nla_ok(rt_match
, list_len
); idx
++) {
340 if (rt_match
->nla_type
!= (idx
+ 1))
343 if (idx
>= tree_hdr
->nmatches
)
346 if (nla_len(rt_match
) < sizeof(struct tcf_ematch_hdr
))
349 em
= tcf_em_get_match(tree
, idx
);
351 err
= tcf_em_validate(tp
, tree_hdr
, em
, rt_match
, idx
);
355 rt_match
= nla_next(rt_match
, &list_len
);
358 /* Check if the number of matches provided by userspace actually
359 * complies with the array of matches. The number was used for
360 * the validation of references and a mismatch could lead to
361 * undefined references during the matching process. */
362 if (idx
!= tree_hdr
->nmatches
) {
372 tcf_em_tree_destroy(tp
, tree
);
375 EXPORT_SYMBOL(tcf_em_tree_validate
);
378 * tcf_em_tree_destroy - destroy an ematch tree
380 * @tp: classifier kind handle
381 * @tree: ematch tree to be deleted
383 * This functions destroys an ematch tree previously created by
384 * tcf_em_tree_validate()/tcf_em_tree_change(). You must ensure that
385 * the ematch tree is not in use before calling this function.
387 void tcf_em_tree_destroy(struct tcf_proto
*tp
, struct tcf_ematch_tree
*tree
)
391 if (tree
->matches
== NULL
)
394 for (i
= 0; i
< tree
->hdr
.nmatches
; i
++) {
395 struct tcf_ematch
*em
= tcf_em_get_match(tree
, i
);
398 if (em
->ops
->destroy
)
399 em
->ops
->destroy(tp
, em
);
400 else if (!tcf_em_is_simple(em
))
401 kfree((void *) em
->data
);
402 module_put(em
->ops
->owner
);
406 tree
->hdr
.nmatches
= 0;
407 kfree(tree
->matches
);
408 tree
->matches
= NULL
;
410 EXPORT_SYMBOL(tcf_em_tree_destroy
);
413 * tcf_em_tree_dump - dump ematch tree into a rtnl message
415 * @skb: skb holding the rtnl message
416 * @t: ematch tree to be dumped
417 * @tlv: TLV type to be used to encapsulate the tree
419 * This function dumps a ematch tree into a rtnl message. It is valid to
420 * call this function while the ematch tree is in use.
422 * Returns -1 if the skb tailroom is insufficient.
424 int tcf_em_tree_dump(struct sk_buff
*skb
, struct tcf_ematch_tree
*tree
, int tlv
)
428 struct nlattr
*top_start
;
429 struct nlattr
*list_start
;
431 top_start
= nla_nest_start(skb
, tlv
);
432 if (top_start
== NULL
)
433 goto nla_put_failure
;
435 NLA_PUT(skb
, TCA_EMATCH_TREE_HDR
, sizeof(tree
->hdr
), &tree
->hdr
);
437 list_start
= nla_nest_start(skb
, TCA_EMATCH_TREE_LIST
);
438 if (list_start
== NULL
)
439 goto nla_put_failure
;
441 tail
= skb_tail_pointer(skb
);
442 for (i
= 0; i
< tree
->hdr
.nmatches
; i
++) {
443 struct nlattr
*match_start
= (struct nlattr
*)tail
;
444 struct tcf_ematch
*em
= tcf_em_get_match(tree
, i
);
445 struct tcf_ematch_hdr em_hdr
= {
446 .kind
= em
->ops
? em
->ops
->kind
: TCF_EM_CONTAINER
,
447 .matchid
= em
->matchid
,
451 NLA_PUT(skb
, i
+1, sizeof(em_hdr
), &em_hdr
);
453 if (em
->ops
&& em
->ops
->dump
) {
454 if (em
->ops
->dump(skb
, em
) < 0)
455 goto nla_put_failure
;
456 } else if (tcf_em_is_container(em
) || tcf_em_is_simple(em
)) {
458 nla_put_nohdr(skb
, sizeof(u
), &u
);
459 } else if (em
->datalen
> 0)
460 nla_put_nohdr(skb
, em
->datalen
, (void *) em
->data
);
462 tail
= skb_tail_pointer(skb
);
463 match_start
->nla_len
= tail
- (u8
*)match_start
;
466 nla_nest_end(skb
, list_start
);
467 nla_nest_end(skb
, top_start
);
474 EXPORT_SYMBOL(tcf_em_tree_dump
);
476 static inline int tcf_em_match(struct sk_buff
*skb
, struct tcf_ematch
*em
,
477 struct tcf_pkt_info
*info
)
479 int r
= em
->ops
->match(skb
, em
, info
);
480 return tcf_em_is_inverted(em
) ? !r
: r
;
483 /* Do not use this function directly, use tcf_em_tree_match instead */
484 int __tcf_em_tree_match(struct sk_buff
*skb
, struct tcf_ematch_tree
*tree
,
485 struct tcf_pkt_info
*info
)
487 int stackp
= 0, match_idx
= 0, res
= 0;
488 struct tcf_ematch
*cur_match
;
489 int stack
[CONFIG_NET_EMATCH_STACK
];
492 while (match_idx
< tree
->hdr
.nmatches
) {
493 cur_match
= tcf_em_get_match(tree
, match_idx
);
495 if (tcf_em_is_container(cur_match
)) {
496 if (unlikely(stackp
>= CONFIG_NET_EMATCH_STACK
))
499 stack
[stackp
++] = match_idx
;
500 match_idx
= cur_match
->data
;
504 res
= tcf_em_match(skb
, cur_match
, info
);
506 if (tcf_em_early_end(cur_match
, res
))
514 match_idx
= stack
[--stackp
];
515 cur_match
= tcf_em_get_match(tree
, match_idx
);
517 if (tcf_em_early_end(cur_match
, res
))
529 printk("Local stack overflow, increase NET_EMATCH_STACK\n");
532 EXPORT_SYMBOL(__tcf_em_tree_match
);
This page took 0.04084 seconds and 5 git commands to generate.