ematch.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548
  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. #include <linux/module.h>
  80. #include <linux/slab.h>
  81. #include <linux/types.h>
  82. #include <linux/kernel.h>
  83. #include <linux/errno.h>
  84. #include <linux/rtnetlink.h>
  85. #include <linux/skbuff.h>
  86. #include <net/pkt_cls.h>
  87. static LIST_HEAD(ematch_ops);
  88. static DEFINE_RWLOCK(ematch_mod_lock);
  89. static struct tcf_ematch_ops *tcf_em_lookup(u16 kind)
  90. {
  91. struct tcf_ematch_ops *e = NULL;
  92. read_lock(&ematch_mod_lock);
  93. list_for_each_entry(e, &ematch_ops, link) {
  94. if (kind == e->kind) {
  95. if (!try_module_get(e->owner))
  96. e = NULL;
  97. read_unlock(&ematch_mod_lock);
  98. return e;
  99. }
  100. }
  101. read_unlock(&ematch_mod_lock);
  102. return NULL;
  103. }
  104. /**
  105. * tcf_em_register - register an extended match
  106. *
  107. * @ops: ematch operations lookup table
  108. *
  109. * This function must be called by ematches to announce their presence.
  110. * The given @ops must have kind set to a unique identifier and the
  111. * callback match() must be implemented. All other callbacks are optional
  112. * and a fallback implementation is used instead.
  113. *
  114. * Returns -EEXISTS if an ematch of the same kind has already registered.
  115. */
  116. int tcf_em_register(struct tcf_ematch_ops *ops)
  117. {
  118. int err = -EEXIST;
  119. struct tcf_ematch_ops *e;
  120. if (ops->match == NULL)
  121. return -EINVAL;
  122. write_lock(&ematch_mod_lock);
  123. list_for_each_entry(e, &ematch_ops, link)
  124. if (ops->kind == e->kind)
  125. goto errout;
  126. list_add_tail(&ops->link, &ematch_ops);
  127. err = 0;
  128. errout:
  129. write_unlock(&ematch_mod_lock);
  130. return err;
  131. }
  132. EXPORT_SYMBOL(tcf_em_register);
  133. /**
  134. * tcf_em_unregister - unregster and extended match
  135. *
  136. * @ops: ematch operations lookup table
  137. *
  138. * This function must be called by ematches to announce their disappearance
  139. * for examples when the module gets unloaded. The @ops parameter must be
  140. * the same as the one used for registration.
  141. *
  142. * Returns -ENOENT if no matching ematch was found.
  143. */
  144. void tcf_em_unregister(struct tcf_ematch_ops *ops)
  145. {
  146. write_lock(&ematch_mod_lock);
  147. list_del(&ops->link);
  148. write_unlock(&ematch_mod_lock);
  149. }
  150. EXPORT_SYMBOL(tcf_em_unregister);
  151. static inline struct tcf_ematch *tcf_em_get_match(struct tcf_ematch_tree *tree,
  152. int index)
  153. {
  154. return &tree->matches[index];
  155. }
  156. static int tcf_em_validate(struct tcf_proto *tp,
  157. struct tcf_ematch_tree_hdr *tree_hdr,
  158. struct tcf_ematch *em, struct nlattr *nla, int idx)
  159. {
  160. int err = -EINVAL;
  161. struct tcf_ematch_hdr *em_hdr = nla_data(nla);
  162. int data_len = nla_len(nla) - sizeof(*em_hdr);
  163. void *data = (void *) em_hdr + sizeof(*em_hdr);
  164. struct net *net = tp->chain->block->net;
  165. if (!TCF_EM_REL_VALID(em_hdr->flags))
  166. goto errout;
  167. if (em_hdr->kind == TCF_EM_CONTAINER) {
  168. /* Special ematch called "container", carries an index
  169. * referencing an external ematch sequence.
  170. */
  171. u32 ref;
  172. if (data_len < sizeof(ref))
  173. goto errout;
  174. ref = *(u32 *) data;
  175. if (ref >= tree_hdr->nmatches)
  176. goto errout;
  177. /* We do not allow backward jumps to avoid loops and jumps
  178. * to our own position are of course illegal.
  179. */
  180. if (ref <= idx)
  181. goto errout;
  182. em->data = ref;
  183. } else {
  184. /* Note: This lookup will increase the module refcnt
  185. * of the ematch module referenced. In case of a failure,
  186. * a destroy function is called by the underlying layer
  187. * which automatically releases the reference again, therefore
  188. * the module MUST not be given back under any circumstances
  189. * here. Be aware, the destroy function assumes that the
  190. * module is held if the ops field is non zero.
  191. */
  192. em->ops = tcf_em_lookup(em_hdr->kind);
  193. if (em->ops == NULL) {
  194. err = -ENOENT;
  195. #ifdef CONFIG_MODULES
  196. __rtnl_unlock();
  197. request_module("ematch-kind-%u", em_hdr->kind);
  198. rtnl_lock();
  199. em->ops = tcf_em_lookup(em_hdr->kind);
  200. if (em->ops) {
  201. /* We dropped the RTNL mutex in order to
  202. * perform the module load. Tell the caller
  203. * to replay the request.
  204. */
  205. module_put(em->ops->owner);
  206. em->ops = NULL;
  207. err = -EAGAIN;
  208. }
  209. #endif
  210. goto errout;
  211. }
  212. /* ematch module provides expected length of data, so we
  213. * can do a basic sanity check.
  214. */
  215. if (em->ops->datalen && data_len < em->ops->datalen)
  216. goto errout;
  217. if (em->ops->change) {
  218. err = -EINVAL;
  219. if (em_hdr->flags & TCF_EM_SIMPLE)
  220. goto errout;
  221. err = em->ops->change(net, data, data_len, em);
  222. if (err < 0)
  223. goto errout;
  224. } else if (data_len > 0) {
  225. /* ematch module doesn't provide an own change
  226. * procedure and expects us to allocate and copy
  227. * the ematch data.
  228. *
  229. * TCF_EM_SIMPLE may be specified stating that the
  230. * data only consists of a u32 integer and the module
  231. * does not expected a memory reference but rather
  232. * the value carried.
  233. */
  234. if (em_hdr->flags & TCF_EM_SIMPLE) {
  235. if (data_len < sizeof(u32))
  236. goto errout;
  237. em->data = *(u32 *) data;
  238. } else {
  239. void *v = kmemdup(data, data_len, GFP_KERNEL);
  240. if (v == NULL) {
  241. err = -ENOBUFS;
  242. goto errout;
  243. }
  244. em->data = (unsigned long) v;
  245. }
  246. em->datalen = data_len;
  247. }
  248. }
  249. em->matchid = em_hdr->matchid;
  250. em->flags = em_hdr->flags;
  251. em->net = net;
  252. err = 0;
  253. errout:
  254. return err;
  255. }
  256. static const struct nla_policy em_policy[TCA_EMATCH_TREE_MAX + 1] = {
  257. [TCA_EMATCH_TREE_HDR] = { .len = sizeof(struct tcf_ematch_tree_hdr) },
  258. [TCA_EMATCH_TREE_LIST] = { .type = NLA_NESTED },
  259. };
  260. /**
  261. * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
  262. *
  263. * @tp: classifier kind handle
  264. * @nla: ematch tree configuration TLV
  265. * @tree: destination ematch tree variable to store the resulting
  266. * ematch tree.
  267. *
  268. * This function validates the given configuration TLV @nla and builds an
  269. * ematch tree in @tree. The resulting tree must later be copied into
  270. * the private classifier data using tcf_em_tree_change(). You MUST NOT
  271. * provide the ematch tree variable of the private classifier data directly,
  272. * the changes would not be locked properly.
  273. *
  274. * Returns a negative error code if the configuration TLV contains errors.
  275. */
  276. int tcf_em_tree_validate(struct tcf_proto *tp, struct nlattr *nla,
  277. struct tcf_ematch_tree *tree)
  278. {
  279. int idx, list_len, matches_len, err;
  280. struct nlattr *tb[TCA_EMATCH_TREE_MAX + 1];
  281. struct nlattr *rt_match, *rt_hdr, *rt_list;
  282. struct tcf_ematch_tree_hdr *tree_hdr;
  283. struct tcf_ematch *em;
  284. memset(tree, 0, sizeof(*tree));
  285. if (!nla)
  286. return 0;
  287. err = nla_parse_nested_deprecated(tb, TCA_EMATCH_TREE_MAX, nla,
  288. em_policy, NULL);
  289. if (err < 0)
  290. goto errout;
  291. err = -EINVAL;
  292. rt_hdr = tb[TCA_EMATCH_TREE_HDR];
  293. rt_list = tb[TCA_EMATCH_TREE_LIST];
  294. if (rt_hdr == NULL || rt_list == NULL)
  295. goto errout;
  296. tree_hdr = nla_data(rt_hdr);
  297. memcpy(&tree->hdr, tree_hdr, sizeof(*tree_hdr));
  298. rt_match = nla_data(rt_list);
  299. list_len = nla_len(rt_list);
  300. matches_len = tree_hdr->nmatches * sizeof(*em);
  301. tree->matches = kzalloc(matches_len, GFP_KERNEL);
  302. if (tree->matches == NULL)
  303. goto errout;
  304. /* We do not use nla_parse_nested here because the maximum
  305. * number of attributes is unknown. This saves us the allocation
  306. * for a tb buffer which would serve no purpose at all.
  307. *
  308. * The array of rt attributes is parsed in the order as they are
  309. * provided, their type must be incremental from 1 to n. Even
  310. * if it does not serve any real purpose, a failure of sticking
  311. * to this policy will result in parsing failure.
  312. */
  313. for (idx = 0; nla_ok(rt_match, list_len); idx++) {
  314. err = -EINVAL;
  315. if (rt_match->nla_type != (idx + 1))
  316. goto errout_abort;
  317. if (idx >= tree_hdr->nmatches)
  318. goto errout_abort;
  319. if (nla_len(rt_match) < sizeof(struct tcf_ematch_hdr))
  320. goto errout_abort;
  321. em = tcf_em_get_match(tree, idx);
  322. err = tcf_em_validate(tp, tree_hdr, em, rt_match, idx);
  323. if (err < 0)
  324. goto errout_abort;
  325. rt_match = nla_next(rt_match, &list_len);
  326. }
  327. /* Check if the number of matches provided by userspace actually
  328. * complies with the array of matches. The number was used for
  329. * the validation of references and a mismatch could lead to
  330. * undefined references during the matching process.
  331. */
  332. if (idx != tree_hdr->nmatches) {
  333. err = -EINVAL;
  334. goto errout_abort;
  335. }
  336. err = 0;
  337. errout:
  338. return err;
  339. errout_abort:
  340. tcf_em_tree_destroy(tree);
  341. return err;
  342. }
  343. EXPORT_SYMBOL(tcf_em_tree_validate);
  344. /**
  345. * tcf_em_tree_destroy - destroy an ematch tree
  346. *
  347. * @tree: ematch tree to be deleted
  348. *
  349. * This functions destroys an ematch tree previously created by
  350. * tcf_em_tree_validate()/tcf_em_tree_change(). You must ensure that
  351. * the ematch tree is not in use before calling this function.
  352. */
  353. void tcf_em_tree_destroy(struct tcf_ematch_tree *tree)
  354. {
  355. int i;
  356. if (tree->matches == NULL)
  357. return;
  358. for (i = 0; i < tree->hdr.nmatches; i++) {
  359. struct tcf_ematch *em = tcf_em_get_match(tree, i);
  360. if (em->ops) {
  361. if (em->ops->destroy)
  362. em->ops->destroy(em);
  363. else if (!tcf_em_is_simple(em))
  364. kfree((void *) em->data);
  365. module_put(em->ops->owner);
  366. }
  367. }
  368. tree->hdr.nmatches = 0;
  369. kfree(tree->matches);
  370. tree->matches = NULL;
  371. }
  372. EXPORT_SYMBOL(tcf_em_tree_destroy);
  373. /**
  374. * tcf_em_tree_dump - dump ematch tree into a rtnl message
  375. *
  376. * @skb: skb holding the rtnl message
  377. * @tree: ematch tree to be dumped
  378. * @tlv: TLV type to be used to encapsulate the tree
  379. *
  380. * This function dumps a ematch tree into a rtnl message. It is valid to
  381. * call this function while the ematch tree is in use.
  382. *
  383. * Returns -1 if the skb tailroom is insufficient.
  384. */
  385. int tcf_em_tree_dump(struct sk_buff *skb, struct tcf_ematch_tree *tree, int tlv)
  386. {
  387. int i;
  388. u8 *tail;
  389. struct nlattr *top_start;
  390. struct nlattr *list_start;
  391. top_start = nla_nest_start_noflag(skb, tlv);
  392. if (top_start == NULL)
  393. goto nla_put_failure;
  394. if (nla_put(skb, TCA_EMATCH_TREE_HDR, sizeof(tree->hdr), &tree->hdr))
  395. goto nla_put_failure;
  396. list_start = nla_nest_start_noflag(skb, TCA_EMATCH_TREE_LIST);
  397. if (list_start == NULL)
  398. goto nla_put_failure;
  399. tail = skb_tail_pointer(skb);
  400. for (i = 0; i < tree->hdr.nmatches; i++) {
  401. struct nlattr *match_start = (struct nlattr *)tail;
  402. struct tcf_ematch *em = tcf_em_get_match(tree, i);
  403. struct tcf_ematch_hdr em_hdr = {
  404. .kind = em->ops ? em->ops->kind : TCF_EM_CONTAINER,
  405. .matchid = em->matchid,
  406. .flags = em->flags
  407. };
  408. if (nla_put(skb, i + 1, sizeof(em_hdr), &em_hdr))
  409. goto nla_put_failure;
  410. if (em->ops && em->ops->dump) {
  411. if (em->ops->dump(skb, em) < 0)
  412. goto nla_put_failure;
  413. } else if (tcf_em_is_container(em) || tcf_em_is_simple(em)) {
  414. u32 u = em->data;
  415. nla_put_nohdr(skb, sizeof(u), &u);
  416. } else if (em->datalen > 0)
  417. nla_put_nohdr(skb, em->datalen, (void *) em->data);
  418. tail = skb_tail_pointer(skb);
  419. match_start->nla_len = tail - (u8 *)match_start;
  420. }
  421. nla_nest_end(skb, list_start);
  422. nla_nest_end(skb, top_start);
  423. return 0;
  424. nla_put_failure:
  425. return -1;
  426. }
  427. EXPORT_SYMBOL(tcf_em_tree_dump);
  428. static inline int tcf_em_match(struct sk_buff *skb, struct tcf_ematch *em,
  429. struct tcf_pkt_info *info)
  430. {
  431. int r = em->ops->match(skb, em, info);
  432. return tcf_em_is_inverted(em) ? !r : r;
  433. }
  434. /* Do not use this function directly, use tcf_em_tree_match instead */
  435. int __tcf_em_tree_match(struct sk_buff *skb, struct tcf_ematch_tree *tree,
  436. struct tcf_pkt_info *info)
  437. {
  438. int stackp = 0, match_idx = 0, res = 0;
  439. struct tcf_ematch *cur_match;
  440. int stack[CONFIG_NET_EMATCH_STACK];
  441. proceed:
  442. while (match_idx < tree->hdr.nmatches) {
  443. cur_match = tcf_em_get_match(tree, match_idx);
  444. if (tcf_em_is_container(cur_match)) {
  445. if (unlikely(stackp >= CONFIG_NET_EMATCH_STACK))
  446. goto stack_overflow;
  447. stack[stackp++] = match_idx;
  448. match_idx = cur_match->data;
  449. goto proceed;
  450. }
  451. res = tcf_em_match(skb, cur_match, info);
  452. if (tcf_em_early_end(cur_match, res))
  453. break;
  454. match_idx++;
  455. }
  456. pop_stack:
  457. if (stackp > 0) {
  458. match_idx = stack[--stackp];
  459. cur_match = tcf_em_get_match(tree, match_idx);
  460. if (tcf_em_is_inverted(cur_match))
  461. res = !res;
  462. if (tcf_em_early_end(cur_match, res)) {
  463. goto pop_stack;
  464. } else {
  465. match_idx++;
  466. goto proceed;
  467. }
  468. }
  469. return res;
  470. stack_overflow:
  471. net_warn_ratelimited("tc ematch: local stack overflow, increase NET_EMATCH_STACK\n");
  472. return -1;
  473. }
  474. EXPORT_SYMBOL(__tcf_em_tree_match);