Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-or-later
2 : : /*
3 : : * net/sched/ematch.c Extended Match API
4 : : *
5 : : * Authors: Thomas Graf <tgraf@suug.ch>
6 : : *
7 : : * ==========================================================================
8 : : *
9 : : * An extended match (ematch) is a small classification tool not worth
10 : : * writing a full classifier for. Ematches can be interconnected to form
11 : : * a logic expression and get attached to classifiers to extend their
12 : : * functionatlity.
13 : : *
14 : : * The userspace part transforms the logic expressions into an array
15 : : * consisting of multiple sequences of interconnected ematches separated
16 : : * by markers. Precedence is implemented by a special ematch kind
17 : : * referencing a sequence beyond the marker of the current sequence
18 : : * causing the current position in the sequence to be pushed onto a stack
19 : : * to allow the current position to be overwritten by the position referenced
20 : : * in the special ematch. Matching continues in the new sequence until a
21 : : * marker is reached causing the position to be restored from the stack.
22 : : *
23 : : * Example:
24 : : * A AND (B1 OR B2) AND C AND D
25 : : *
26 : : * ------->-PUSH-------
27 : : * -->-- / -->-- \ -->--
28 : : * / \ / / \ \ / \
29 : : * +-------+-------+-------+-------+-------+--------+
30 : : * | A AND | B AND | C AND | D END | B1 OR | B2 END |
31 : : * +-------+-------+-------+-------+-------+--------+
32 : : * \ /
33 : : * --------<-POP---------
34 : : *
35 : : * where B is a virtual ematch referencing to sequence starting with B1.
36 : : *
37 : : * ==========================================================================
38 : : *
39 : : * How to write an ematch in 60 seconds
40 : : * ------------------------------------
41 : : *
42 : : * 1) Provide a matcher function:
43 : : * static int my_match(struct sk_buff *skb, struct tcf_ematch *m,
44 : : * struct tcf_pkt_info *info)
45 : : * {
46 : : * struct mydata *d = (struct mydata *) m->data;
47 : : *
48 : : * if (...matching goes here...)
49 : : * return 1;
50 : : * else
51 : : * return 0;
52 : : * }
53 : : *
54 : : * 2) Fill out a struct tcf_ematch_ops:
55 : : * static struct tcf_ematch_ops my_ops = {
56 : : * .kind = unique id,
57 : : * .datalen = sizeof(struct mydata),
58 : : * .match = my_match,
59 : : * .owner = THIS_MODULE,
60 : : * };
61 : : *
62 : : * 3) Register/Unregister your ematch:
63 : : * static int __init init_my_ematch(void)
64 : : * {
65 : : * return tcf_em_register(&my_ops);
66 : : * }
67 : : *
68 : : * static void __exit exit_my_ematch(void)
69 : : * {
70 : : * tcf_em_unregister(&my_ops);
71 : : * }
72 : : *
73 : : * module_init(init_my_ematch);
74 : : * module_exit(exit_my_ematch);
75 : : *
76 : : * 4) By now you should have two more seconds left, barely enough to
77 : : * open up a beer to watch the compilation going.
78 : : */
79 : :
80 : : #include <linux/module.h>
81 : : #include <linux/slab.h>
82 : : #include <linux/types.h>
83 : : #include <linux/kernel.h>
84 : : #include <linux/errno.h>
85 : : #include <linux/rtnetlink.h>
86 : : #include <linux/skbuff.h>
87 : : #include <net/pkt_cls.h>
88 : :
89 : : static LIST_HEAD(ematch_ops);
90 : : static DEFINE_RWLOCK(ematch_mod_lock);
91 : :
92 : 0 : static struct tcf_ematch_ops *tcf_em_lookup(u16 kind)
93 : : {
94 : 0 : struct tcf_ematch_ops *e = NULL;
95 : :
96 : 0 : read_lock(&ematch_mod_lock);
97 [ # # ]: 0 : list_for_each_entry(e, &ematch_ops, link) {
98 [ # # ]: 0 : if (kind == e->kind) {
99 [ # # ]: 0 : if (!try_module_get(e->owner))
100 : 0 : e = NULL;
101 : 0 : read_unlock(&ematch_mod_lock);
102 : 0 : return e;
103 : : }
104 : : }
105 : 0 : read_unlock(&ematch_mod_lock);
106 : :
107 : 0 : return NULL;
108 : : }
109 : :
110 : : /**
111 : : * tcf_em_register - register an extended match
112 : : *
113 : : * @ops: ematch operations lookup table
114 : : *
115 : : * This function must be called by ematches to announce their presence.
116 : : * The given @ops must have kind set to a unique identifier and the
117 : : * callback match() must be implemented. All other callbacks are optional
118 : : * and a fallback implementation is used instead.
119 : : *
120 : : * Returns -EEXISTS if an ematch of the same kind has already registered.
121 : : */
122 : 0 : int tcf_em_register(struct tcf_ematch_ops *ops)
123 : : {
124 : 0 : int err = -EEXIST;
125 : 0 : struct tcf_ematch_ops *e;
126 : :
127 [ # # ]: 0 : if (ops->match == NULL)
128 : : return -EINVAL;
129 : :
130 : 0 : write_lock(&ematch_mod_lock);
131 [ # # ]: 0 : list_for_each_entry(e, &ematch_ops, link)
132 [ # # ]: 0 : if (ops->kind == e->kind)
133 : 0 : goto errout;
134 : :
135 : 0 : list_add_tail(&ops->link, &ematch_ops);
136 : 0 : err = 0;
137 : 0 : errout:
138 : 0 : write_unlock(&ematch_mod_lock);
139 : 0 : return err;
140 : : }
141 : : EXPORT_SYMBOL(tcf_em_register);
142 : :
143 : : /**
144 : : * tcf_em_unregister - unregster and extended match
145 : : *
146 : : * @ops: ematch operations lookup table
147 : : *
148 : : * This function must be called by ematches to announce their disappearance
149 : : * for examples when the module gets unloaded. The @ops parameter must be
150 : : * the same as the one used for registration.
151 : : *
152 : : * Returns -ENOENT if no matching ematch was found.
153 : : */
154 : 0 : void tcf_em_unregister(struct tcf_ematch_ops *ops)
155 : : {
156 : 0 : write_lock(&ematch_mod_lock);
157 : 0 : list_del(&ops->link);
158 : 0 : write_unlock(&ematch_mod_lock);
159 : 0 : }
160 : : EXPORT_SYMBOL(tcf_em_unregister);
161 : :
162 : 0 : static inline struct tcf_ematch *tcf_em_get_match(struct tcf_ematch_tree *tree,
163 : : int index)
164 : : {
165 : 0 : return &tree->matches[index];
166 : : }
167 : :
168 : :
169 : : static int tcf_em_validate(struct tcf_proto *tp,
170 : : struct tcf_ematch_tree_hdr *tree_hdr,
171 : : struct tcf_ematch *em, struct nlattr *nla, int idx)
172 : : {
173 : : int err = -EINVAL;
174 : : struct tcf_ematch_hdr *em_hdr = nla_data(nla);
175 : : int data_len = nla_len(nla) - sizeof(*em_hdr);
176 : : void *data = (void *) em_hdr + sizeof(*em_hdr);
177 : : struct net *net = tp->chain->block->net;
178 : :
179 : : if (!TCF_EM_REL_VALID(em_hdr->flags))
180 : : goto errout;
181 : :
182 : : if (em_hdr->kind == TCF_EM_CONTAINER) {
183 : : /* Special ematch called "container", carries an index
184 : : * referencing an external ematch sequence.
185 : : */
186 : : u32 ref;
187 : :
188 : : if (data_len < sizeof(ref))
189 : : goto errout;
190 : : ref = *(u32 *) data;
191 : :
192 : : if (ref >= tree_hdr->nmatches)
193 : : goto errout;
194 : :
195 : : /* We do not allow backward jumps to avoid loops and jumps
196 : : * to our own position are of course illegal.
197 : : */
198 : : if (ref <= idx)
199 : : goto errout;
200 : :
201 : :
202 : : em->data = ref;
203 : : } else {
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 : : */
212 : : em->ops = tcf_em_lookup(em_hdr->kind);
213 : :
214 : : if (em->ops == NULL) {
215 : : err = -ENOENT;
216 : : #ifdef CONFIG_MODULES
217 : : __rtnl_unlock();
218 : : request_module("ematch-kind-%u", em_hdr->kind);
219 : : rtnl_lock();
220 : : em->ops = tcf_em_lookup(em_hdr->kind);
221 : : if (em->ops) {
222 : : /* We dropped the RTNL mutex in order to
223 : : * perform the module load. Tell the caller
224 : : * to replay the request.
225 : : */
226 : : module_put(em->ops->owner);
227 : : em->ops = NULL;
228 : : err = -EAGAIN;
229 : : }
230 : : #endif
231 : : goto errout;
232 : : }
233 : :
234 : : /* ematch module provides expected length of data, so we
235 : : * can do a basic sanity check.
236 : : */
237 : : if (em->ops->datalen && data_len < em->ops->datalen)
238 : : goto errout;
239 : :
240 : : if (em->ops->change) {
241 : : err = -EINVAL;
242 : : if (em_hdr->flags & TCF_EM_SIMPLE)
243 : : goto errout;
244 : : err = em->ops->change(net, data, data_len, em);
245 : : if (err < 0)
246 : : goto errout;
247 : : } else if (data_len > 0) {
248 : : /* ematch module doesn't provide an own change
249 : : * procedure and expects us to allocate and copy
250 : : * the ematch data.
251 : : *
252 : : * TCF_EM_SIMPLE may be specified stating that the
253 : : * data only consists of a u32 integer and the module
254 : : * does not expected a memory reference but rather
255 : : * the value carried.
256 : : */
257 : : if (em_hdr->flags & TCF_EM_SIMPLE) {
258 : : if (data_len < sizeof(u32))
259 : : goto errout;
260 : : em->data = *(u32 *) data;
261 : : } else {
262 : : void *v = kmemdup(data, data_len, GFP_KERNEL);
263 : : if (v == NULL) {
264 : : err = -ENOBUFS;
265 : : goto errout;
266 : : }
267 : : em->data = (unsigned long) v;
268 : : }
269 : : em->datalen = data_len;
270 : : }
271 : : }
272 : :
273 : : em->matchid = em_hdr->matchid;
274 : : em->flags = em_hdr->flags;
275 : : em->net = net;
276 : :
277 : : err = 0;
278 : : errout:
279 : : return err;
280 : : }
281 : :
282 : : static const struct nla_policy em_policy[TCA_EMATCH_TREE_MAX + 1] = {
283 : : [TCA_EMATCH_TREE_HDR] = { .len = sizeof(struct tcf_ematch_tree_hdr) },
284 : : [TCA_EMATCH_TREE_LIST] = { .type = NLA_NESTED },
285 : : };
286 : :
287 : : /**
288 : : * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
289 : : *
290 : : * @tp: classifier kind handle
291 : : * @nla: ematch tree configuration TLV
292 : : * @tree: destination ematch tree variable to store the resulting
293 : : * ematch tree.
294 : : *
295 : : * This function validates the given configuration TLV @nla and builds an
296 : : * ematch tree in @tree. The resulting tree must later be copied into
297 : : * the private classifier data using tcf_em_tree_change(). You MUST NOT
298 : : * provide the ematch tree variable of the private classifier data directly,
299 : : * the changes would not be locked properly.
300 : : *
301 : : * Returns a negative error code if the configuration TLV contains errors.
302 : : */
303 : 0 : int tcf_em_tree_validate(struct tcf_proto *tp, struct nlattr *nla,
304 : : struct tcf_ematch_tree *tree)
305 : : {
306 : 0 : int idx, list_len, matches_len, err;
307 : 0 : struct nlattr *tb[TCA_EMATCH_TREE_MAX + 1];
308 : 0 : struct nlattr *rt_match, *rt_hdr, *rt_list;
309 : 0 : struct tcf_ematch_tree_hdr *tree_hdr;
310 : 0 : struct tcf_ematch *em;
311 : :
312 : 0 : memset(tree, 0, sizeof(*tree));
313 [ # # ]: 0 : if (!nla)
314 : : return 0;
315 : :
316 : 0 : err = nla_parse_nested_deprecated(tb, TCA_EMATCH_TREE_MAX, nla,
317 : : em_policy, NULL);
318 [ # # ]: 0 : if (err < 0)
319 : 0 : goto errout;
320 : :
321 : 0 : err = -EINVAL;
322 : 0 : rt_hdr = tb[TCA_EMATCH_TREE_HDR];
323 : 0 : rt_list = tb[TCA_EMATCH_TREE_LIST];
324 : :
325 [ # # ]: 0 : if (rt_hdr == NULL || rt_list == NULL)
326 : 0 : goto errout;
327 : :
328 : 0 : tree_hdr = nla_data(rt_hdr);
329 : 0 : memcpy(&tree->hdr, tree_hdr, sizeof(*tree_hdr));
330 : :
331 : 0 : rt_match = nla_data(rt_list);
332 : 0 : list_len = nla_len(rt_list);
333 : 0 : matches_len = tree_hdr->nmatches * sizeof(*em);
334 : :
335 : 0 : tree->matches = kzalloc(matches_len, GFP_KERNEL);
336 [ # # ]: 0 : if (tree->matches == NULL)
337 : 0 : goto errout;
338 : :
339 : : /* We do not use nla_parse_nested here because the maximum
340 : : * number of attributes is unknown. This saves us the allocation
341 : : * for a tb buffer which would serve no purpose at all.
342 : : *
343 : : * The array of rt attributes is parsed in the order as they are
344 : : * provided, their type must be incremental from 1 to n. Even
345 : : * if it does not serve any real purpose, a failure of sticking
346 : : * to this policy will result in parsing failure.
347 : : */
348 [ # # ]: 0 : for (idx = 0; nla_ok(rt_match, list_len); idx++) {
349 : 0 : err = -EINVAL;
350 : :
351 [ # # ]: 0 : if (rt_match->nla_type != (idx + 1))
352 : 0 : goto errout_abort;
353 : :
354 [ # # ]: 0 : if (idx >= tree_hdr->nmatches)
355 : 0 : goto errout_abort;
356 : :
357 [ # # ]: 0 : if (nla_len(rt_match) < sizeof(struct tcf_ematch_hdr))
358 : 0 : goto errout_abort;
359 : :
360 : 0 : em = tcf_em_get_match(tree, idx);
361 : :
362 : 0 : err = tcf_em_validate(tp, tree_hdr, em, rt_match, idx);
363 [ # # ]: 0 : if (err < 0)
364 : 0 : goto errout_abort;
365 : :
366 : 0 : rt_match = nla_next(rt_match, &list_len);
367 : : }
368 : :
369 : : /* Check if the number of matches provided by userspace actually
370 : : * complies with the array of matches. The number was used for
371 : : * the validation of references and a mismatch could lead to
372 : : * undefined references during the matching process.
373 : : */
374 [ # # ]: 0 : if (idx != tree_hdr->nmatches) {
375 : 0 : err = -EINVAL;
376 : 0 : goto errout_abort;
377 : : }
378 : :
379 : : err = 0;
380 : : errout:
381 : : return err;
382 : :
383 : 0 : errout_abort:
384 : 0 : tcf_em_tree_destroy(tree);
385 : 0 : return err;
386 : : }
387 : : EXPORT_SYMBOL(tcf_em_tree_validate);
388 : :
389 : : /**
390 : : * tcf_em_tree_destroy - destroy an ematch tree
391 : : *
392 : : * @tp: classifier kind handle
393 : : * @tree: ematch tree to be deleted
394 : : *
395 : : * This functions destroys an ematch tree previously created by
396 : : * tcf_em_tree_validate()/tcf_em_tree_change(). You must ensure that
397 : : * the ematch tree is not in use before calling this function.
398 : : */
399 : 0 : void tcf_em_tree_destroy(struct tcf_ematch_tree *tree)
400 : : {
401 : 0 : int i;
402 : :
403 [ # # ]: 0 : if (tree->matches == NULL)
404 : : return;
405 : :
406 [ # # ]: 0 : for (i = 0; i < tree->hdr.nmatches; i++) {
407 : 0 : struct tcf_ematch *em = tcf_em_get_match(tree, i);
408 : :
409 [ # # ]: 0 : if (em->ops) {
410 [ # # ]: 0 : if (em->ops->destroy)
411 : 0 : em->ops->destroy(em);
412 [ # # ]: 0 : else if (!tcf_em_is_simple(em))
413 : 0 : kfree((void *) em->data);
414 : 0 : module_put(em->ops->owner);
415 : : }
416 : : }
417 : :
418 : 0 : tree->hdr.nmatches = 0;
419 : 0 : kfree(tree->matches);
420 : 0 : tree->matches = NULL;
421 : : }
422 : : EXPORT_SYMBOL(tcf_em_tree_destroy);
423 : :
424 : : /**
425 : : * tcf_em_tree_dump - dump ematch tree into a rtnl message
426 : : *
427 : : * @skb: skb holding the rtnl message
428 : : * @t: ematch tree to be dumped
429 : : * @tlv: TLV type to be used to encapsulate the tree
430 : : *
431 : : * This function dumps a ematch tree into a rtnl message. It is valid to
432 : : * call this function while the ematch tree is in use.
433 : : *
434 : : * Returns -1 if the skb tailroom is insufficient.
435 : : */
436 : 0 : int tcf_em_tree_dump(struct sk_buff *skb, struct tcf_ematch_tree *tree, int tlv)
437 : : {
438 : 0 : int i;
439 : 0 : u8 *tail;
440 : 0 : struct nlattr *top_start;
441 : 0 : struct nlattr *list_start;
442 : :
443 : 0 : top_start = nla_nest_start_noflag(skb, tlv);
444 [ # # ]: 0 : if (top_start == NULL)
445 : 0 : goto nla_put_failure;
446 : :
447 [ # # ]: 0 : if (nla_put(skb, TCA_EMATCH_TREE_HDR, sizeof(tree->hdr), &tree->hdr))
448 : 0 : goto nla_put_failure;
449 : :
450 : 0 : list_start = nla_nest_start_noflag(skb, TCA_EMATCH_TREE_LIST);
451 [ # # ]: 0 : if (list_start == NULL)
452 : 0 : goto nla_put_failure;
453 : :
454 : 0 : tail = skb_tail_pointer(skb);
455 [ # # ]: 0 : for (i = 0; i < tree->hdr.nmatches; i++) {
456 : 0 : struct nlattr *match_start = (struct nlattr *)tail;
457 : 0 : struct tcf_ematch *em = tcf_em_get_match(tree, i);
458 : 0 : struct tcf_ematch_hdr em_hdr = {
459 : 0 : .kind = em->ops ? em->ops->kind : TCF_EM_CONTAINER,
460 [ # # ]: 0 : .matchid = em->matchid,
461 : 0 : .flags = em->flags
462 : : };
463 : :
464 [ # # ]: 0 : if (nla_put(skb, i + 1, sizeof(em_hdr), &em_hdr))
465 : 0 : goto nla_put_failure;
466 : :
467 [ # # # # ]: 0 : if (em->ops && em->ops->dump) {
468 [ # # ]: 0 : if (em->ops->dump(skb, em) < 0)
469 : 0 : goto nla_put_failure;
470 [ # # # # ]: 0 : } else if (tcf_em_is_container(em) || tcf_em_is_simple(em)) {
471 : 0 : u32 u = em->data;
472 : 0 : nla_put_nohdr(skb, sizeof(u), &u);
473 [ # # ]: 0 : } else if (em->datalen > 0)
474 : 0 : nla_put_nohdr(skb, em->datalen, (void *) em->data);
475 : :
476 : 0 : tail = skb_tail_pointer(skb);
477 : 0 : match_start->nla_len = tail - (u8 *)match_start;
478 : : }
479 : :
480 : 0 : nla_nest_end(skb, list_start);
481 : 0 : nla_nest_end(skb, top_start);
482 : :
483 : 0 : return 0;
484 : :
485 : : nla_put_failure:
486 : : return -1;
487 : : }
488 : : EXPORT_SYMBOL(tcf_em_tree_dump);
489 : :
490 : 0 : static inline int tcf_em_match(struct sk_buff *skb, struct tcf_ematch *em,
491 : : struct tcf_pkt_info *info)
492 : : {
493 : 0 : int r = em->ops->match(skb, em, info);
494 : :
495 [ # # ]: 0 : return tcf_em_is_inverted(em) ? !r : r;
496 : : }
497 : :
498 : : /* Do not use this function directly, use tcf_em_tree_match instead */
499 : 0 : int __tcf_em_tree_match(struct sk_buff *skb, struct tcf_ematch_tree *tree,
500 : : struct tcf_pkt_info *info)
501 : : {
502 : 0 : int stackp = 0, match_idx = 0, res = 0;
503 : : struct tcf_ematch *cur_match;
504 : : int stack[CONFIG_NET_EMATCH_STACK];
505 : :
506 : : proceed:
507 [ # # ]: 0 : while (match_idx < tree->hdr.nmatches) {
508 : 0 : cur_match = tcf_em_get_match(tree, match_idx);
509 : :
510 [ # # ]: 0 : if (tcf_em_is_container(cur_match)) {
511 [ # # ]: 0 : if (unlikely(stackp >= CONFIG_NET_EMATCH_STACK))
512 : 0 : goto stack_overflow;
513 : :
514 : 0 : stack[stackp++] = match_idx;
515 : 0 : match_idx = cur_match->data;
516 : 0 : goto proceed;
517 : : }
518 : :
519 : 0 : res = tcf_em_match(skb, cur_match, info);
520 : :
521 [ # # ]: 0 : if (tcf_em_early_end(cur_match, res))
522 : : break;
523 : :
524 : 0 : match_idx++;
525 : : }
526 : :
527 : 0 : pop_stack:
528 [ # # ]: 0 : if (stackp > 0) {
529 : 0 : match_idx = stack[--stackp];
530 : 0 : cur_match = tcf_em_get_match(tree, match_idx);
531 : :
532 [ # # ]: 0 : if (tcf_em_is_inverted(cur_match))
533 : 0 : res = !res;
534 : :
535 [ # # ]: 0 : if (tcf_em_early_end(cur_match, res)) {
536 : 0 : goto pop_stack;
537 : : } else {
538 : 0 : match_idx++;
539 : 0 : goto proceed;
540 : : }
541 : : }
542 : :
543 : : return res;
544 : :
545 : : stack_overflow:
546 [ # # ]: 0 : net_warn_ratelimited("tc ematch: local stack overflow, increase NET_EMATCH_STACK\n");
547 : : return -1;
548 : : }
549 : : EXPORT_SYMBOL(__tcf_em_tree_match);
|
