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