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 | static struct tcf_ematch_ops *tcf_em_lookup(u16 kind) |
93 | { |
94 | struct tcf_ematch_ops *e = NULL; |
95 | |
96 | read_lock(&ematch_mod_lock); |
97 | list_for_each_entry(e, &ematch_ops, link) { |
98 | if (kind == e->kind) { |
99 | if (!try_module_get(module: e->owner)) |
100 | e = NULL; |
101 | read_unlock(&ematch_mod_lock); |
102 | return e; |
103 | } |
104 | } |
105 | read_unlock(&ematch_mod_lock); |
106 | |
107 | 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 | int tcf_em_register(struct tcf_ematch_ops *ops) |
123 | { |
124 | int err = -EEXIST; |
125 | struct tcf_ematch_ops *e; |
126 | |
127 | if (ops->match == NULL) |
128 | return -EINVAL; |
129 | |
130 | write_lock(&ematch_mod_lock); |
131 | list_for_each_entry(e, &ematch_ops, link) |
132 | if (ops->kind == e->kind) |
133 | goto errout; |
134 | |
135 | list_add_tail(new: &ops->link, head: &ematch_ops); |
136 | err = 0; |
137 | errout: |
138 | write_unlock(&ematch_mod_lock); |
139 | return err; |
140 | } |
141 | EXPORT_SYMBOL(tcf_em_register); |
142 | |
143 | /** |
144 | * tcf_em_unregister - unregister 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 | void tcf_em_unregister(struct tcf_ematch_ops *ops) |
155 | { |
156 | write_lock(&ematch_mod_lock); |
157 | list_del(entry: &ops->link); |
158 | write_unlock(&ematch_mod_lock); |
159 | } |
160 | EXPORT_SYMBOL(tcf_em_unregister); |
161 | |
162 | static inline struct tcf_ematch *tcf_em_get_match(struct tcf_ematch_tree *tree, |
163 | int index) |
164 | { |
165 | 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(kind: 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(kind: 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(module: 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 (em->ops->datalen > 0) |
259 | goto errout; |
260 | if (data_len < sizeof(u32)) |
261 | goto errout; |
262 | em->data = *(u32 *) data; |
263 | } else { |
264 | void *v = kmemdup(p: data, size: data_len, GFP_KERNEL); |
265 | if (v == NULL) { |
266 | err = -ENOBUFS; |
267 | goto errout; |
268 | } |
269 | em->data = (unsigned long) v; |
270 | } |
271 | em->datalen = data_len; |
272 | } |
273 | } |
274 | |
275 | em->matchid = em_hdr->matchid; |
276 | em->flags = em_hdr->flags; |
277 | em->net = net; |
278 | |
279 | err = 0; |
280 | errout: |
281 | return err; |
282 | } |
283 | |
284 | static const struct nla_policy em_policy[TCA_EMATCH_TREE_MAX + 1] = { |
285 | [TCA_EMATCH_TREE_HDR] = { .len = sizeof(struct tcf_ematch_tree_hdr) }, |
286 | [TCA_EMATCH_TREE_LIST] = { .type = NLA_NESTED }, |
287 | }; |
288 | |
289 | /** |
290 | * tcf_em_tree_validate - validate ematch config TLV and build ematch tree |
291 | * |
292 | * @tp: classifier kind handle |
293 | * @nla: ematch tree configuration TLV |
294 | * @tree: destination ematch tree variable to store the resulting |
295 | * ematch tree. |
296 | * |
297 | * This function validates the given configuration TLV @nla and builds an |
298 | * ematch tree in @tree. The resulting tree must later be copied into |
299 | * the private classifier data using tcf_em_tree_change(). You MUST NOT |
300 | * provide the ematch tree variable of the private classifier data directly, |
301 | * the changes would not be locked properly. |
302 | * |
303 | * Returns a negative error code if the configuration TLV contains errors. |
304 | */ |
305 | int tcf_em_tree_validate(struct tcf_proto *tp, struct nlattr *nla, |
306 | struct tcf_ematch_tree *tree) |
307 | { |
308 | int idx, list_len, matches_len, err; |
309 | struct nlattr *tb[TCA_EMATCH_TREE_MAX + 1]; |
310 | struct nlattr *rt_match, *rt_hdr, *rt_list; |
311 | struct tcf_ematch_tree_hdr *tree_hdr; |
312 | struct tcf_ematch *em; |
313 | |
314 | memset(tree, 0, sizeof(*tree)); |
315 | if (!nla) |
316 | return 0; |
317 | |
318 | err = nla_parse_nested_deprecated(tb, TCA_EMATCH_TREE_MAX, nla, |
319 | policy: em_policy, NULL); |
320 | if (err < 0) |
321 | goto errout; |
322 | |
323 | err = -EINVAL; |
324 | rt_hdr = tb[TCA_EMATCH_TREE_HDR]; |
325 | rt_list = tb[TCA_EMATCH_TREE_LIST]; |
326 | |
327 | if (rt_hdr == NULL || rt_list == NULL) |
328 | goto errout; |
329 | |
330 | tree_hdr = nla_data(nla: rt_hdr); |
331 | memcpy(&tree->hdr, tree_hdr, sizeof(*tree_hdr)); |
332 | |
333 | rt_match = nla_data(nla: rt_list); |
334 | list_len = nla_len(nla: rt_list); |
335 | matches_len = tree_hdr->nmatches * sizeof(*em); |
336 | |
337 | tree->matches = kzalloc(size: matches_len, GFP_KERNEL); |
338 | if (tree->matches == NULL) |
339 | goto errout; |
340 | |
341 | /* We do not use nla_parse_nested here because the maximum |
342 | * number of attributes is unknown. This saves us the allocation |
343 | * for a tb buffer which would serve no purpose at all. |
344 | * |
345 | * The array of rt attributes is parsed in the order as they are |
346 | * provided, their type must be incremental from 1 to n. Even |
347 | * if it does not serve any real purpose, a failure of sticking |
348 | * to this policy will result in parsing failure. |
349 | */ |
350 | for (idx = 0; nla_ok(nla: rt_match, remaining: list_len); idx++) { |
351 | err = -EINVAL; |
352 | |
353 | if (rt_match->nla_type != (idx + 1)) |
354 | goto errout_abort; |
355 | |
356 | if (idx >= tree_hdr->nmatches) |
357 | goto errout_abort; |
358 | |
359 | if (nla_len(nla: rt_match) < sizeof(struct tcf_ematch_hdr)) |
360 | goto errout_abort; |
361 | |
362 | em = tcf_em_get_match(tree, index: idx); |
363 | |
364 | err = tcf_em_validate(tp, tree_hdr, em, nla: rt_match, idx); |
365 | if (err < 0) |
366 | goto errout_abort; |
367 | |
368 | rt_match = nla_next(nla: rt_match, remaining: &list_len); |
369 | } |
370 | |
371 | /* Check if the number of matches provided by userspace actually |
372 | * complies with the array of matches. The number was used for |
373 | * the validation of references and a mismatch could lead to |
374 | * undefined references during the matching process. |
375 | */ |
376 | if (idx != tree_hdr->nmatches) { |
377 | err = -EINVAL; |
378 | goto errout_abort; |
379 | } |
380 | |
381 | err = 0; |
382 | errout: |
383 | return err; |
384 | |
385 | errout_abort: |
386 | tcf_em_tree_destroy(tree); |
387 | return err; |
388 | } |
389 | EXPORT_SYMBOL(tcf_em_tree_validate); |
390 | |
391 | /** |
392 | * tcf_em_tree_destroy - destroy an ematch tree |
393 | * |
394 | * @tree: ematch tree to be deleted |
395 | * |
396 | * This functions destroys an ematch tree previously created by |
397 | * tcf_em_tree_validate()/tcf_em_tree_change(). You must ensure that |
398 | * the ematch tree is not in use before calling this function. |
399 | */ |
400 | void tcf_em_tree_destroy(struct tcf_ematch_tree *tree) |
401 | { |
402 | int i; |
403 | |
404 | if (tree->matches == NULL) |
405 | return; |
406 | |
407 | for (i = 0; i < tree->hdr.nmatches; i++) { |
408 | struct tcf_ematch *em = tcf_em_get_match(tree, index: i); |
409 | |
410 | if (em->ops) { |
411 | if (em->ops->destroy) |
412 | em->ops->destroy(em); |
413 | else if (!tcf_em_is_simple(em)) |
414 | kfree(objp: (void *) em->data); |
415 | module_put(module: em->ops->owner); |
416 | } |
417 | } |
418 | |
419 | tree->hdr.nmatches = 0; |
420 | kfree(objp: tree->matches); |
421 | tree->matches = NULL; |
422 | } |
423 | EXPORT_SYMBOL(tcf_em_tree_destroy); |
424 | |
425 | /** |
426 | * tcf_em_tree_dump - dump ematch tree into a rtnl message |
427 | * |
428 | * @skb: skb holding the rtnl message |
429 | * @tree: ematch tree to be dumped |
430 | * @tlv: TLV type to be used to encapsulate the tree |
431 | * |
432 | * This function dumps a ematch tree into a rtnl message. It is valid to |
433 | * call this function while the ematch tree is in use. |
434 | * |
435 | * Returns -1 if the skb tailroom is insufficient. |
436 | */ |
437 | int tcf_em_tree_dump(struct sk_buff *skb, struct tcf_ematch_tree *tree, int tlv) |
438 | { |
439 | int i; |
440 | u8 *tail; |
441 | struct nlattr *top_start; |
442 | struct nlattr *list_start; |
443 | |
444 | top_start = nla_nest_start_noflag(skb, attrtype: tlv); |
445 | if (top_start == NULL) |
446 | goto nla_put_failure; |
447 | |
448 | if (nla_put(skb, attrtype: TCA_EMATCH_TREE_HDR, attrlen: sizeof(tree->hdr), data: &tree->hdr)) |
449 | goto nla_put_failure; |
450 | |
451 | list_start = nla_nest_start_noflag(skb, attrtype: TCA_EMATCH_TREE_LIST); |
452 | if (list_start == NULL) |
453 | goto nla_put_failure; |
454 | |
455 | tail = skb_tail_pointer(skb); |
456 | for (i = 0; i < tree->hdr.nmatches; i++) { |
457 | struct nlattr *match_start = (struct nlattr *)tail; |
458 | struct tcf_ematch *em = tcf_em_get_match(tree, index: i); |
459 | struct tcf_ematch_hdr em_hdr = { |
460 | .kind = em->ops ? em->ops->kind : TCF_EM_CONTAINER, |
461 | .matchid = em->matchid, |
462 | .flags = em->flags |
463 | }; |
464 | |
465 | if (nla_put(skb, attrtype: i + 1, attrlen: sizeof(em_hdr), data: &em_hdr)) |
466 | goto nla_put_failure; |
467 | |
468 | if (em->ops && em->ops->dump) { |
469 | if (em->ops->dump(skb, em) < 0) |
470 | goto nla_put_failure; |
471 | } else if (tcf_em_is_container(em) || tcf_em_is_simple(em)) { |
472 | u32 u = em->data; |
473 | nla_put_nohdr(skb, attrlen: sizeof(u), data: &u); |
474 | } else if (em->datalen > 0) |
475 | nla_put_nohdr(skb, attrlen: em->datalen, data: (void *) em->data); |
476 | |
477 | tail = skb_tail_pointer(skb); |
478 | match_start->nla_len = tail - (u8 *)match_start; |
479 | } |
480 | |
481 | nla_nest_end(skb, start: list_start); |
482 | nla_nest_end(skb, start: top_start); |
483 | |
484 | return 0; |
485 | |
486 | nla_put_failure: |
487 | return -1; |
488 | } |
489 | EXPORT_SYMBOL(tcf_em_tree_dump); |
490 | |
491 | static inline int tcf_em_match(struct sk_buff *skb, struct tcf_ematch *em, |
492 | struct tcf_pkt_info *info) |
493 | { |
494 | int r = em->ops->match(skb, em, info); |
495 | |
496 | return tcf_em_is_inverted(em) ? !r : r; |
497 | } |
498 | |
499 | /* Do not use this function directly, use tcf_em_tree_match instead */ |
500 | int __tcf_em_tree_match(struct sk_buff *skb, struct tcf_ematch_tree *tree, |
501 | struct tcf_pkt_info *info) |
502 | { |
503 | int stackp = 0, match_idx = 0, res = 0; |
504 | struct tcf_ematch *cur_match; |
505 | int stack[CONFIG_NET_EMATCH_STACK]; |
506 | |
507 | proceed: |
508 | while (match_idx < tree->hdr.nmatches) { |
509 | cur_match = tcf_em_get_match(tree, index: match_idx); |
510 | |
511 | if (tcf_em_is_container(em: cur_match)) { |
512 | if (unlikely(stackp >= CONFIG_NET_EMATCH_STACK)) |
513 | goto stack_overflow; |
514 | |
515 | stack[stackp++] = match_idx; |
516 | match_idx = cur_match->data; |
517 | goto proceed; |
518 | } |
519 | |
520 | res = tcf_em_match(skb, em: cur_match, info); |
521 | |
522 | if (tcf_em_early_end(em: cur_match, result: res)) |
523 | break; |
524 | |
525 | match_idx++; |
526 | } |
527 | |
528 | pop_stack: |
529 | if (stackp > 0) { |
530 | match_idx = stack[--stackp]; |
531 | cur_match = tcf_em_get_match(tree, index: match_idx); |
532 | |
533 | if (tcf_em_is_inverted(em: cur_match)) |
534 | res = !res; |
535 | |
536 | if (tcf_em_early_end(em: cur_match, result: res)) { |
537 | goto pop_stack; |
538 | } else { |
539 | match_idx++; |
540 | goto proceed; |
541 | } |
542 | } |
543 | |
544 | return res; |
545 | |
546 | stack_overflow: |
547 | net_warn_ratelimited("tc ematch: local stack overflow, increase NET_EMATCH_STACK\n" ); |
548 | return -1; |
549 | } |
550 | EXPORT_SYMBOL(__tcf_em_tree_match); |
551 | |