]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - net/sched/ematch.c
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/slab.h>
86 #include <linux/types.h>
87 #include <linux/kernel.h>
88 #include <linux/errno.h>
89 #include <linux/rtnetlink.h>
90 #include <linux/skbuff.h>
91 #include <net/pkt_cls.h>
93 static LIST_HEAD(ematch_ops
);
94 static DEFINE_RWLOCK(ematch_mod_lock
);
96 static inline struct tcf_ematch_ops
* tcf_em_lookup(u16 kind
)
98 struct tcf_ematch_ops
*e
= NULL
;
100 read_lock(&ematch_mod_lock
);
101 list_for_each_entry(e
, &ematch_ops
, link
) {
102 if (kind
== e
->kind
) {
103 if (!try_module_get(e
->owner
))
105 read_unlock(&ematch_mod_lock
);
109 read_unlock(&ematch_mod_lock
);
115 * tcf_em_register - register an extended match
117 * @ops: ematch operations lookup table
119 * This function must be called by ematches to announce their presence.
120 * The given @ops must have kind set to a unique identifier and the
121 * callback match() must be implemented. All other callbacks are optional
122 * and a fallback implementation is used instead.
124 * Returns -EEXISTS if an ematch of the same kind has already registered.
126 int tcf_em_register(struct tcf_ematch_ops
*ops
)
129 struct tcf_ematch_ops
*e
;
131 if (ops
->match
== NULL
)
134 write_lock(&ematch_mod_lock
);
135 list_for_each_entry(e
, &ematch_ops
, link
)
136 if (ops
->kind
== e
->kind
)
139 list_add_tail(&ops
->link
, &ematch_ops
);
142 write_unlock(&ematch_mod_lock
);
145 EXPORT_SYMBOL(tcf_em_register
);
148 * tcf_em_unregister - unregster and extended match
150 * @ops: ematch operations lookup table
152 * This function must be called by ematches to announce their disappearance
153 * for examples when the module gets unloaded. The @ops parameter must be
154 * the same as the one used for registration.
156 * Returns -ENOENT if no matching ematch was found.
158 void tcf_em_unregister(struct tcf_ematch_ops
*ops
)
160 write_lock(&ematch_mod_lock
);
161 list_del(&ops
->link
);
162 write_unlock(&ematch_mod_lock
);
164 EXPORT_SYMBOL(tcf_em_unregister
);
166 static inline struct tcf_ematch
* tcf_em_get_match(struct tcf_ematch_tree
*tree
,
169 return &tree
->matches
[index
];
173 static int tcf_em_validate(struct tcf_proto
*tp
,
174 struct tcf_ematch_tree_hdr
*tree_hdr
,
175 struct tcf_ematch
*em
, struct nlattr
*nla
, int idx
)
178 struct tcf_ematch_hdr
*em_hdr
= nla_data(nla
);
179 int data_len
= nla_len(nla
) - sizeof(*em_hdr
);
180 void *data
= (void *) em_hdr
+ sizeof(*em_hdr
);
182 if (!TCF_EM_REL_VALID(em_hdr
->flags
))
185 if (em_hdr
->kind
== TCF_EM_CONTAINER
) {
186 /* Special ematch called "container", carries an index
187 * referencing an external ematch sequence. */
190 if (data_len
< sizeof(ref
))
194 if (ref
>= tree_hdr
->nmatches
)
197 /* We do not allow backward jumps to avoid loops and jumps
198 * to our own position are of course illegal. */
205 /* Note: This lookup will increase the module refcnt
206 * of the ematch module referenced. In case of a failure,
207 * a destroy function is called by the underlying layer
208 * which automatically releases the reference again, therefore
209 * the module MUST not be given back under any circumstances
210 * here. Be aware, the destroy function assumes that the
211 * module is held if the ops field is non zero. */
212 em
->ops
= tcf_em_lookup(em_hdr
->kind
);
214 if (em
->ops
== NULL
) {
216 #ifdef CONFIG_MODULES
218 request_module("ematch-kind-%u", em_hdr
->kind
);
220 em
->ops
= tcf_em_lookup(em_hdr
->kind
);
222 /* We dropped the RTNL mutex in order to
223 * perform the module load. Tell the caller
224 * to replay the request. */
225 module_put(em
->ops
->owner
);
232 /* ematch module provides expected length of data, so we
233 * can do a basic sanity check. */
234 if (em
->ops
->datalen
&& data_len
< em
->ops
->datalen
)
237 if (em
->ops
->change
) {
238 err
= em
->ops
->change(tp
, data
, data_len
, em
);
241 } else if (data_len
> 0) {
242 /* ematch module doesn't provide an own change
243 * procedure and expects us to allocate and copy
246 * TCF_EM_SIMPLE may be specified stating that the
247 * data only consists of a u32 integer and the module
248 * does not expected a memory reference but rather
249 * the value carried. */
250 if (em_hdr
->flags
& TCF_EM_SIMPLE
) {
251 if (data_len
< sizeof(u32
))
253 em
->data
= *(u32
*) data
;
255 void *v
= kmemdup(data
, data_len
, GFP_KERNEL
);
260 em
->data
= (unsigned long) v
;
265 em
->matchid
= em_hdr
->matchid
;
266 em
->flags
= em_hdr
->flags
;
267 em
->datalen
= data_len
;
274 static const struct nla_policy em_policy
[TCA_EMATCH_TREE_MAX
+ 1] = {
275 [TCA_EMATCH_TREE_HDR
] = { .len
= sizeof(struct tcf_ematch_tree_hdr
) },
276 [TCA_EMATCH_TREE_LIST
] = { .type
= NLA_NESTED
},
280 * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
282 * @tp: classifier kind handle
283 * @nla: ematch tree configuration TLV
284 * @tree: destination ematch tree variable to store the resulting
287 * This function validates the given configuration TLV @nla and builds an
288 * ematch tree in @tree. The resulting tree must later be copied into
289 * the private classifier data using tcf_em_tree_change(). You MUST NOT
290 * provide the ematch tree variable of the private classifier data directly,
291 * the changes would not be locked properly.
293 * Returns a negative error code if the configuration TLV contains errors.
295 int tcf_em_tree_validate(struct tcf_proto
*tp
, struct nlattr
*nla
,
296 struct tcf_ematch_tree
*tree
)
298 int idx
, list_len
, matches_len
, err
;
299 struct nlattr
*tb
[TCA_EMATCH_TREE_MAX
+ 1];
300 struct nlattr
*rt_match
, *rt_hdr
, *rt_list
;
301 struct tcf_ematch_tree_hdr
*tree_hdr
;
302 struct tcf_ematch
*em
;
304 memset(tree
, 0, sizeof(*tree
));
308 err
= nla_parse_nested(tb
, TCA_EMATCH_TREE_MAX
, nla
, em_policy
);
313 rt_hdr
= tb
[TCA_EMATCH_TREE_HDR
];
314 rt_list
= tb
[TCA_EMATCH_TREE_LIST
];
316 if (rt_hdr
== NULL
|| rt_list
== NULL
)
319 tree_hdr
= nla_data(rt_hdr
);
320 memcpy(&tree
->hdr
, tree_hdr
, sizeof(*tree_hdr
));
322 rt_match
= nla_data(rt_list
);
323 list_len
= nla_len(rt_list
);
324 matches_len
= tree_hdr
->nmatches
* sizeof(*em
);
326 tree
->matches
= kzalloc(matches_len
, GFP_KERNEL
);
327 if (tree
->matches
== NULL
)
330 /* We do not use nla_parse_nested here because the maximum
331 * number of attributes is unknown. This saves us the allocation
332 * for a tb buffer which would serve no purpose at all.
334 * The array of rt attributes is parsed in the order as they are
335 * provided, their type must be incremental from 1 to n. Even
336 * if it does not serve any real purpose, a failure of sticking
337 * to this policy will result in parsing failure. */
338 for (idx
= 0; nla_ok(rt_match
, list_len
); idx
++) {
341 if (rt_match
->nla_type
!= (idx
+ 1))
344 if (idx
>= tree_hdr
->nmatches
)
347 if (nla_len(rt_match
) < sizeof(struct tcf_ematch_hdr
))
350 em
= tcf_em_get_match(tree
, idx
);
352 err
= tcf_em_validate(tp
, tree_hdr
, em
, rt_match
, idx
);
356 rt_match
= nla_next(rt_match
, &list_len
);
359 /* Check if the number of matches provided by userspace actually
360 * complies with the array of matches. The number was used for
361 * the validation of references and a mismatch could lead to
362 * undefined references during the matching process. */
363 if (idx
!= tree_hdr
->nmatches
) {
373 tcf_em_tree_destroy(tp
, tree
);
376 EXPORT_SYMBOL(tcf_em_tree_validate
);
379 * tcf_em_tree_destroy - destroy an ematch tree
381 * @tp: classifier kind handle
382 * @tree: ematch tree to be deleted
384 * This functions destroys an ematch tree previously created by
385 * tcf_em_tree_validate()/tcf_em_tree_change(). You must ensure that
386 * the ematch tree is not in use before calling this function.
388 void tcf_em_tree_destroy(struct tcf_proto
*tp
, struct tcf_ematch_tree
*tree
)
392 if (tree
->matches
== NULL
)
395 for (i
= 0; i
< tree
->hdr
.nmatches
; i
++) {
396 struct tcf_ematch
*em
= tcf_em_get_match(tree
, i
);
399 if (em
->ops
->destroy
)
400 em
->ops
->destroy(tp
, em
);
401 else if (!tcf_em_is_simple(em
))
402 kfree((void *) em
->data
);
403 module_put(em
->ops
->owner
);
407 tree
->hdr
.nmatches
= 0;
408 kfree(tree
->matches
);
409 tree
->matches
= NULL
;
411 EXPORT_SYMBOL(tcf_em_tree_destroy
);
414 * tcf_em_tree_dump - dump ematch tree into a rtnl message
416 * @skb: skb holding the rtnl message
417 * @t: ematch tree to be dumped
418 * @tlv: TLV type to be used to encapsulate the tree
420 * This function dumps a ematch tree into a rtnl message. It is valid to
421 * call this function while the ematch tree is in use.
423 * Returns -1 if the skb tailroom is insufficient.
425 int tcf_em_tree_dump(struct sk_buff
*skb
, struct tcf_ematch_tree
*tree
, int tlv
)
429 struct nlattr
*top_start
;
430 struct nlattr
*list_start
;
432 top_start
= nla_nest_start(skb
, tlv
);
433 if (top_start
== NULL
)
434 goto nla_put_failure
;
436 NLA_PUT(skb
, TCA_EMATCH_TREE_HDR
, sizeof(tree
->hdr
), &tree
->hdr
);
438 list_start
= nla_nest_start(skb
, TCA_EMATCH_TREE_LIST
);
439 if (list_start
== NULL
)
440 goto nla_put_failure
;
442 tail
= skb_tail_pointer(skb
);
443 for (i
= 0; i
< tree
->hdr
.nmatches
; i
++) {
444 struct nlattr
*match_start
= (struct nlattr
*)tail
;
445 struct tcf_ematch
*em
= tcf_em_get_match(tree
, i
);
446 struct tcf_ematch_hdr em_hdr
= {
447 .kind
= em
->ops
? em
->ops
->kind
: TCF_EM_CONTAINER
,
448 .matchid
= em
->matchid
,
452 NLA_PUT(skb
, i
+1, sizeof(em_hdr
), &em_hdr
);
454 if (em
->ops
&& em
->ops
->dump
) {
455 if (em
->ops
->dump(skb
, em
) < 0)
456 goto nla_put_failure
;
457 } else if (tcf_em_is_container(em
) || tcf_em_is_simple(em
)) {
459 nla_put_nohdr(skb
, sizeof(u
), &u
);
460 } else if (em
->datalen
> 0)
461 nla_put_nohdr(skb
, em
->datalen
, (void *) em
->data
);
463 tail
= skb_tail_pointer(skb
);
464 match_start
->nla_len
= tail
- (u8
*)match_start
;
467 nla_nest_end(skb
, list_start
);
468 nla_nest_end(skb
, top_start
);
475 EXPORT_SYMBOL(tcf_em_tree_dump
);
477 static inline int tcf_em_match(struct sk_buff
*skb
, struct tcf_ematch
*em
,
478 struct tcf_pkt_info
*info
)
480 int r
= em
->ops
->match(skb
, em
, info
);
481 return tcf_em_is_inverted(em
) ? !r
: r
;
484 /* Do not use this function directly, use tcf_em_tree_match instead */
485 int __tcf_em_tree_match(struct sk_buff
*skb
, struct tcf_ematch_tree
*tree
,
486 struct tcf_pkt_info
*info
)
488 int stackp
= 0, match_idx
= 0, res
= 0;
489 struct tcf_ematch
*cur_match
;
490 int stack
[CONFIG_NET_EMATCH_STACK
];
493 while (match_idx
< tree
->hdr
.nmatches
) {
494 cur_match
= tcf_em_get_match(tree
, match_idx
);
496 if (tcf_em_is_container(cur_match
)) {
497 if (unlikely(stackp
>= CONFIG_NET_EMATCH_STACK
))
500 stack
[stackp
++] = match_idx
;
501 match_idx
= cur_match
->data
;
505 res
= tcf_em_match(skb
, cur_match
, info
);
507 if (tcf_em_early_end(cur_match
, res
))
515 match_idx
= stack
[--stackp
];
516 cur_match
= tcf_em_get_match(tree
, match_idx
);
518 if (tcf_em_early_end(cur_match
, res
))
530 printk(KERN_WARNING
"tc ematch: local stack overflow,"
531 " increase NET_EMATCH_STACK\n");
534 EXPORT_SYMBOL(__tcf_em_tree_match
);