cls_u32.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837
  1. /*
  2. * net/sched/cls_u32.c Ugly (or Universal) 32bit key Packet Classifier.
  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: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  10. *
  11. * The filters are packed to hash tables of key nodes
  12. * with a set of 32bit key/mask pairs at every node.
  13. * Nodes reference next level hash tables etc.
  14. *
  15. * This scheme is the best universal classifier I managed to
  16. * invent; it is not super-fast, but it is not slow (provided you
  17. * program it correctly), and general enough. And its relative
  18. * speed grows as the number of rules becomes larger.
  19. *
  20. * It seems that it represents the best middle point between
  21. * speed and manageability both by human and by machine.
  22. *
  23. * It is especially useful for link sharing combined with QoS;
  24. * pure RSVP doesn't need such a general approach and can use
  25. * much simpler (and faster) schemes, sort of cls_rsvp.c.
  26. *
  27. * JHS: We should remove the CONFIG_NET_CLS_IND from here
  28. * eventually when the meta match extension is made available
  29. *
  30. * nfmark match added by Catalin(ux aka Dino) BOIE <catab at umbrella.ro>
  31. */
  32. #include <linux/module.h>
  33. #include <linux/slab.h>
  34. #include <linux/types.h>
  35. #include <linux/kernel.h>
  36. #include <linux/string.h>
  37. #include <linux/errno.h>
  38. #include <linux/rtnetlink.h>
  39. #include <linux/skbuff.h>
  40. #include <linux/bitmap.h>
  41. #include <net/netlink.h>
  42. #include <net/act_api.h>
  43. #include <net/pkt_cls.h>
  44. struct tc_u_knode {
  45. struct tc_u_knode *next;
  46. u32 handle;
  47. struct tc_u_hnode *ht_up;
  48. struct tcf_exts exts;
  49. #ifdef CONFIG_NET_CLS_IND
  50. int ifindex;
  51. #endif
  52. u8 fshift;
  53. struct tcf_result res;
  54. struct tc_u_hnode *ht_down;
  55. #ifdef CONFIG_CLS_U32_PERF
  56. struct tc_u32_pcnt *pf;
  57. #endif
  58. #ifdef CONFIG_CLS_U32_MARK
  59. struct tc_u32_mark mark;
  60. #endif
  61. struct tc_u32_sel sel;
  62. };
  63. struct tc_u_hnode {
  64. struct tc_u_hnode *next;
  65. u32 handle;
  66. u32 prio;
  67. struct tc_u_common *tp_c;
  68. int refcnt;
  69. unsigned int divisor;
  70. struct tc_u_knode *ht[1];
  71. };
  72. struct tc_u_common {
  73. struct tc_u_hnode *hlist;
  74. struct Qdisc *q;
  75. int refcnt;
  76. u32 hgenerator;
  77. };
  78. static inline unsigned int u32_hash_fold(__be32 key,
  79. const struct tc_u32_sel *sel,
  80. u8 fshift)
  81. {
  82. unsigned int h = ntohl(key & sel->hmask) >> fshift;
  83. return h;
  84. }
  85. static int u32_classify(struct sk_buff *skb, const struct tcf_proto *tp, struct tcf_result *res)
  86. {
  87. struct {
  88. struct tc_u_knode *knode;
  89. unsigned int off;
  90. } stack[TC_U32_MAXDEPTH];
  91. struct tc_u_hnode *ht = tp->root;
  92. unsigned int off = skb_network_offset(skb);
  93. struct tc_u_knode *n;
  94. int sdepth = 0;
  95. int off2 = 0;
  96. int sel = 0;
  97. #ifdef CONFIG_CLS_U32_PERF
  98. int j;
  99. #endif
  100. int i, r;
  101. next_ht:
  102. n = ht->ht[sel];
  103. next_knode:
  104. if (n) {
  105. struct tc_u32_key *key = n->sel.keys;
  106. #ifdef CONFIG_CLS_U32_PERF
  107. n->pf->rcnt += 1;
  108. j = 0;
  109. #endif
  110. #ifdef CONFIG_CLS_U32_MARK
  111. if ((skb->mark & n->mark.mask) != n->mark.val) {
  112. n = n->next;
  113. goto next_knode;
  114. } else {
  115. n->mark.success++;
  116. }
  117. #endif
  118. for (i = n->sel.nkeys; i > 0; i--, key++) {
  119. int toff = off + key->off + (off2 & key->offmask);
  120. __be32 *data, hdata;
  121. if (skb_headroom(skb) + toff > INT_MAX)
  122. goto out;
  123. data = skb_header_pointer(skb, toff, 4, &hdata);
  124. if (!data)
  125. goto out;
  126. if ((*data ^ key->val) & key->mask) {
  127. n = n->next;
  128. goto next_knode;
  129. }
  130. #ifdef CONFIG_CLS_U32_PERF
  131. n->pf->kcnts[j] += 1;
  132. j++;
  133. #endif
  134. }
  135. if (n->ht_down == NULL) {
  136. check_terminal:
  137. if (n->sel.flags & TC_U32_TERMINAL) {
  138. *res = n->res;
  139. #ifdef CONFIG_NET_CLS_IND
  140. if (!tcf_match_indev(skb, n->ifindex)) {
  141. n = n->next;
  142. goto next_knode;
  143. }
  144. #endif
  145. #ifdef CONFIG_CLS_U32_PERF
  146. n->pf->rhit += 1;
  147. #endif
  148. r = tcf_exts_exec(skb, &n->exts, res);
  149. if (r < 0) {
  150. n = n->next;
  151. goto next_knode;
  152. }
  153. return r;
  154. }
  155. n = n->next;
  156. goto next_knode;
  157. }
  158. /* PUSH */
  159. if (sdepth >= TC_U32_MAXDEPTH)
  160. goto deadloop;
  161. stack[sdepth].knode = n;
  162. stack[sdepth].off = off;
  163. sdepth++;
  164. ht = n->ht_down;
  165. sel = 0;
  166. if (ht->divisor) {
  167. __be32 *data, hdata;
  168. data = skb_header_pointer(skb, off + n->sel.hoff, 4,
  169. &hdata);
  170. if (!data)
  171. goto out;
  172. sel = ht->divisor & u32_hash_fold(*data, &n->sel,
  173. n->fshift);
  174. }
  175. if (!(n->sel.flags & (TC_U32_VAROFFSET | TC_U32_OFFSET | TC_U32_EAT)))
  176. goto next_ht;
  177. if (n->sel.flags & (TC_U32_OFFSET | TC_U32_VAROFFSET)) {
  178. off2 = n->sel.off + 3;
  179. if (n->sel.flags & TC_U32_VAROFFSET) {
  180. __be16 *data, hdata;
  181. data = skb_header_pointer(skb,
  182. off + n->sel.offoff,
  183. 2, &hdata);
  184. if (!data)
  185. goto out;
  186. off2 += ntohs(n->sel.offmask & *data) >>
  187. n->sel.offshift;
  188. }
  189. off2 &= ~3;
  190. }
  191. if (n->sel.flags & TC_U32_EAT) {
  192. off += off2;
  193. off2 = 0;
  194. }
  195. if (off < skb->len)
  196. goto next_ht;
  197. }
  198. /* POP */
  199. if (sdepth--) {
  200. n = stack[sdepth].knode;
  201. ht = n->ht_up;
  202. off = stack[sdepth].off;
  203. goto check_terminal;
  204. }
  205. out:
  206. return -1;
  207. deadloop:
  208. net_warn_ratelimited("cls_u32: dead loop\n");
  209. return -1;
  210. }
  211. static struct tc_u_hnode *
  212. u32_lookup_ht(struct tc_u_common *tp_c, u32 handle)
  213. {
  214. struct tc_u_hnode *ht;
  215. for (ht = tp_c->hlist; ht; ht = ht->next)
  216. if (ht->handle == handle)
  217. break;
  218. return ht;
  219. }
  220. static struct tc_u_knode *
  221. u32_lookup_key(struct tc_u_hnode *ht, u32 handle)
  222. {
  223. unsigned int sel;
  224. struct tc_u_knode *n = NULL;
  225. sel = TC_U32_HASH(handle);
  226. if (sel > ht->divisor)
  227. goto out;
  228. for (n = ht->ht[sel]; n; n = n->next)
  229. if (n->handle == handle)
  230. break;
  231. out:
  232. return n;
  233. }
  234. static unsigned long u32_get(struct tcf_proto *tp, u32 handle)
  235. {
  236. struct tc_u_hnode *ht;
  237. struct tc_u_common *tp_c = tp->data;
  238. if (TC_U32_HTID(handle) == TC_U32_ROOT)
  239. ht = tp->root;
  240. else
  241. ht = u32_lookup_ht(tp_c, TC_U32_HTID(handle));
  242. if (!ht)
  243. return 0;
  244. if (TC_U32_KEY(handle) == 0)
  245. return (unsigned long)ht;
  246. return (unsigned long)u32_lookup_key(ht, handle);
  247. }
  248. static void u32_put(struct tcf_proto *tp, unsigned long f)
  249. {
  250. }
  251. static u32 gen_new_htid(struct tc_u_common *tp_c)
  252. {
  253. int i = 0x800;
  254. do {
  255. if (++tp_c->hgenerator == 0x7FF)
  256. tp_c->hgenerator = 1;
  257. } while (--i > 0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));
  258. return i > 0 ? (tp_c->hgenerator|0x800)<<20 : 0;
  259. }
  260. static int u32_init(struct tcf_proto *tp)
  261. {
  262. struct tc_u_hnode *root_ht;
  263. struct tc_u_common *tp_c;
  264. tp_c = tp->q->u32_node;
  265. root_ht = kzalloc(sizeof(*root_ht), GFP_KERNEL);
  266. if (root_ht == NULL)
  267. return -ENOBUFS;
  268. root_ht->divisor = 0;
  269. root_ht->refcnt++;
  270. root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000;
  271. root_ht->prio = tp->prio;
  272. if (tp_c == NULL) {
  273. tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
  274. if (tp_c == NULL) {
  275. kfree(root_ht);
  276. return -ENOBUFS;
  277. }
  278. tp_c->q = tp->q;
  279. tp->q->u32_node = tp_c;
  280. }
  281. tp_c->refcnt++;
  282. root_ht->next = tp_c->hlist;
  283. tp_c->hlist = root_ht;
  284. root_ht->tp_c = tp_c;
  285. tp->root = root_ht;
  286. tp->data = tp_c;
  287. return 0;
  288. }
  289. static int u32_destroy_key(struct tcf_proto *tp, struct tc_u_knode *n)
  290. {
  291. tcf_unbind_filter(tp, &n->res);
  292. tcf_exts_destroy(tp, &n->exts);
  293. if (n->ht_down)
  294. n->ht_down->refcnt--;
  295. #ifdef CONFIG_CLS_U32_PERF
  296. kfree(n->pf);
  297. #endif
  298. kfree(n);
  299. return 0;
  300. }
  301. static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode *key)
  302. {
  303. struct tc_u_knode **kp;
  304. struct tc_u_hnode *ht = key->ht_up;
  305. if (ht) {
  306. for (kp = &ht->ht[TC_U32_HASH(key->handle)]; *kp; kp = &(*kp)->next) {
  307. if (*kp == key) {
  308. tcf_tree_lock(tp);
  309. *kp = key->next;
  310. tcf_tree_unlock(tp);
  311. u32_destroy_key(tp, key);
  312. return 0;
  313. }
  314. }
  315. }
  316. WARN_ON(1);
  317. return 0;
  318. }
  319. static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
  320. {
  321. struct tc_u_knode *n;
  322. unsigned int h;
  323. for (h = 0; h <= ht->divisor; h++) {
  324. while ((n = ht->ht[h]) != NULL) {
  325. ht->ht[h] = n->next;
  326. u32_destroy_key(tp, n);
  327. }
  328. }
  329. }
  330. static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
  331. {
  332. struct tc_u_common *tp_c = tp->data;
  333. struct tc_u_hnode **hn;
  334. WARN_ON(ht->refcnt);
  335. u32_clear_hnode(tp, ht);
  336. for (hn = &tp_c->hlist; *hn; hn = &(*hn)->next) {
  337. if (*hn == ht) {
  338. *hn = ht->next;
  339. kfree(ht);
  340. return 0;
  341. }
  342. }
  343. WARN_ON(1);
  344. return -ENOENT;
  345. }
  346. static void u32_destroy(struct tcf_proto *tp)
  347. {
  348. struct tc_u_common *tp_c = tp->data;
  349. struct tc_u_hnode *root_ht = tp->root;
  350. WARN_ON(root_ht == NULL);
  351. if (root_ht && --root_ht->refcnt == 0)
  352. u32_destroy_hnode(tp, root_ht);
  353. if (--tp_c->refcnt == 0) {
  354. struct tc_u_hnode *ht;
  355. tp->q->u32_node = NULL;
  356. for (ht = tp_c->hlist; ht; ht = ht->next) {
  357. ht->refcnt--;
  358. u32_clear_hnode(tp, ht);
  359. }
  360. while ((ht = tp_c->hlist) != NULL) {
  361. tp_c->hlist = ht->next;
  362. WARN_ON(ht->refcnt != 0);
  363. kfree(ht);
  364. }
  365. kfree(tp_c);
  366. }
  367. tp->data = NULL;
  368. }
  369. static int u32_delete(struct tcf_proto *tp, unsigned long arg)
  370. {
  371. struct tc_u_hnode *ht = (struct tc_u_hnode *)arg;
  372. if (ht == NULL)
  373. return 0;
  374. if (TC_U32_KEY(ht->handle))
  375. return u32_delete_key(tp, (struct tc_u_knode *)ht);
  376. if (tp->root == ht)
  377. return -EINVAL;
  378. if (ht->refcnt == 1) {
  379. ht->refcnt--;
  380. u32_destroy_hnode(tp, ht);
  381. } else {
  382. return -EBUSY;
  383. }
  384. return 0;
  385. }
  386. #define NR_U32_NODE (1<<12)
  387. static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
  388. {
  389. struct tc_u_knode *n;
  390. unsigned long i;
  391. unsigned long *bitmap = kzalloc(BITS_TO_LONGS(NR_U32_NODE) * sizeof(unsigned long),
  392. GFP_KERNEL);
  393. if (!bitmap)
  394. return handle | 0xFFF;
  395. for (n = ht->ht[TC_U32_HASH(handle)]; n; n = n->next)
  396. set_bit(TC_U32_NODE(n->handle), bitmap);
  397. i = find_next_zero_bit(bitmap, NR_U32_NODE, 0x800);
  398. if (i >= NR_U32_NODE)
  399. i = find_next_zero_bit(bitmap, NR_U32_NODE, 1);
  400. kfree(bitmap);
  401. return handle | (i >= NR_U32_NODE ? 0xFFF : i);
  402. }
  403. static const struct nla_policy u32_policy[TCA_U32_MAX + 1] = {
  404. [TCA_U32_CLASSID] = { .type = NLA_U32 },
  405. [TCA_U32_HASH] = { .type = NLA_U32 },
  406. [TCA_U32_LINK] = { .type = NLA_U32 },
  407. [TCA_U32_DIVISOR] = { .type = NLA_U32 },
  408. [TCA_U32_SEL] = { .len = sizeof(struct tc_u32_sel) },
  409. [TCA_U32_INDEV] = { .type = NLA_STRING, .len = IFNAMSIZ },
  410. [TCA_U32_MARK] = { .len = sizeof(struct tc_u32_mark) },
  411. };
  412. static int u32_set_parms(struct net *net, struct tcf_proto *tp,
  413. unsigned long base, struct tc_u_hnode *ht,
  414. struct tc_u_knode *n, struct nlattr **tb,
  415. struct nlattr *est, bool ovr)
  416. {
  417. int err;
  418. struct tcf_exts e;
  419. tcf_exts_init(&e, TCA_U32_ACT, TCA_U32_POLICE);
  420. err = tcf_exts_validate(net, tp, tb, est, &e, ovr);
  421. if (err < 0)
  422. return err;
  423. err = -EINVAL;
  424. if (tb[TCA_U32_LINK]) {
  425. u32 handle = nla_get_u32(tb[TCA_U32_LINK]);
  426. struct tc_u_hnode *ht_down = NULL, *ht_old;
  427. if (TC_U32_KEY(handle))
  428. goto errout;
  429. if (handle) {
  430. ht_down = u32_lookup_ht(ht->tp_c, handle);
  431. if (ht_down == NULL)
  432. goto errout;
  433. ht_down->refcnt++;
  434. }
  435. tcf_tree_lock(tp);
  436. ht_old = n->ht_down;
  437. n->ht_down = ht_down;
  438. tcf_tree_unlock(tp);
  439. if (ht_old)
  440. ht_old->refcnt--;
  441. }
  442. if (tb[TCA_U32_CLASSID]) {
  443. n->res.classid = nla_get_u32(tb[TCA_U32_CLASSID]);
  444. tcf_bind_filter(tp, &n->res, base);
  445. }
  446. #ifdef CONFIG_NET_CLS_IND
  447. if (tb[TCA_U32_INDEV]) {
  448. int ret;
  449. ret = tcf_change_indev(net, tb[TCA_U32_INDEV]);
  450. if (ret < 0)
  451. goto errout;
  452. n->ifindex = ret;
  453. }
  454. #endif
  455. tcf_exts_change(tp, &n->exts, &e);
  456. return 0;
  457. errout:
  458. tcf_exts_destroy(tp, &e);
  459. return err;
  460. }
  461. static int u32_change(struct net *net, struct sk_buff *in_skb,
  462. struct tcf_proto *tp, unsigned long base, u32 handle,
  463. struct nlattr **tca,
  464. unsigned long *arg, bool ovr)
  465. {
  466. struct tc_u_common *tp_c = tp->data;
  467. struct tc_u_hnode *ht;
  468. struct tc_u_knode *n;
  469. struct tc_u32_sel *s;
  470. struct nlattr *opt = tca[TCA_OPTIONS];
  471. struct nlattr *tb[TCA_U32_MAX + 1];
  472. u32 htid;
  473. int err;
  474. if (opt == NULL)
  475. return handle ? -EINVAL : 0;
  476. err = nla_parse_nested(tb, TCA_U32_MAX, opt, u32_policy);
  477. if (err < 0)
  478. return err;
  479. n = (struct tc_u_knode *)*arg;
  480. if (n) {
  481. if (TC_U32_KEY(n->handle) == 0)
  482. return -EINVAL;
  483. return u32_set_parms(net, tp, base, n->ht_up, n, tb,
  484. tca[TCA_RATE], ovr);
  485. }
  486. if (tb[TCA_U32_DIVISOR]) {
  487. unsigned int divisor = nla_get_u32(tb[TCA_U32_DIVISOR]);
  488. if (--divisor > 0x100)
  489. return -EINVAL;
  490. if (TC_U32_KEY(handle))
  491. return -EINVAL;
  492. if (handle == 0) {
  493. handle = gen_new_htid(tp->data);
  494. if (handle == 0)
  495. return -ENOMEM;
  496. }
  497. ht = kzalloc(sizeof(*ht) + divisor*sizeof(void *), GFP_KERNEL);
  498. if (ht == NULL)
  499. return -ENOBUFS;
  500. ht->tp_c = tp_c;
  501. ht->refcnt = 1;
  502. ht->divisor = divisor;
  503. ht->handle = handle;
  504. ht->prio = tp->prio;
  505. ht->next = tp_c->hlist;
  506. tp_c->hlist = ht;
  507. *arg = (unsigned long)ht;
  508. return 0;
  509. }
  510. if (tb[TCA_U32_HASH]) {
  511. htid = nla_get_u32(tb[TCA_U32_HASH]);
  512. if (TC_U32_HTID(htid) == TC_U32_ROOT) {
  513. ht = tp->root;
  514. htid = ht->handle;
  515. } else {
  516. ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid));
  517. if (ht == NULL)
  518. return -EINVAL;
  519. }
  520. } else {
  521. ht = tp->root;
  522. htid = ht->handle;
  523. }
  524. if (ht->divisor < TC_U32_HASH(htid))
  525. return -EINVAL;
  526. if (handle) {
  527. if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid))
  528. return -EINVAL;
  529. handle = htid | TC_U32_NODE(handle);
  530. } else
  531. handle = gen_new_kid(ht, htid);
  532. if (tb[TCA_U32_SEL] == NULL)
  533. return -EINVAL;
  534. s = nla_data(tb[TCA_U32_SEL]);
  535. n = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
  536. if (n == NULL)
  537. return -ENOBUFS;
  538. #ifdef CONFIG_CLS_U32_PERF
  539. n->pf = kzalloc(sizeof(struct tc_u32_pcnt) + s->nkeys*sizeof(u64), GFP_KERNEL);
  540. if (n->pf == NULL) {
  541. kfree(n);
  542. return -ENOBUFS;
  543. }
  544. #endif
  545. memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
  546. n->ht_up = ht;
  547. n->handle = handle;
  548. n->fshift = s->hmask ? ffs(ntohl(s->hmask)) - 1 : 0;
  549. tcf_exts_init(&n->exts, TCA_U32_ACT, TCA_U32_POLICE);
  550. #ifdef CONFIG_CLS_U32_MARK
  551. if (tb[TCA_U32_MARK]) {
  552. struct tc_u32_mark *mark;
  553. mark = nla_data(tb[TCA_U32_MARK]);
  554. memcpy(&n->mark, mark, sizeof(struct tc_u32_mark));
  555. n->mark.success = 0;
  556. }
  557. #endif
  558. err = u32_set_parms(net, tp, base, ht, n, tb, tca[TCA_RATE], ovr);
  559. if (err == 0) {
  560. struct tc_u_knode **ins;
  561. for (ins = &ht->ht[TC_U32_HASH(handle)]; *ins; ins = &(*ins)->next)
  562. if (TC_U32_NODE(handle) < TC_U32_NODE((*ins)->handle))
  563. break;
  564. n->next = *ins;
  565. tcf_tree_lock(tp);
  566. *ins = n;
  567. tcf_tree_unlock(tp);
  568. *arg = (unsigned long)n;
  569. return 0;
  570. }
  571. #ifdef CONFIG_CLS_U32_PERF
  572. kfree(n->pf);
  573. #endif
  574. kfree(n);
  575. return err;
  576. }
  577. static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg)
  578. {
  579. struct tc_u_common *tp_c = tp->data;
  580. struct tc_u_hnode *ht;
  581. struct tc_u_knode *n;
  582. unsigned int h;
  583. if (arg->stop)
  584. return;
  585. for (ht = tp_c->hlist; ht; ht = ht->next) {
  586. if (ht->prio != tp->prio)
  587. continue;
  588. if (arg->count >= arg->skip) {
  589. if (arg->fn(tp, (unsigned long)ht, arg) < 0) {
  590. arg->stop = 1;
  591. return;
  592. }
  593. }
  594. arg->count++;
  595. for (h = 0; h <= ht->divisor; h++) {
  596. for (n = ht->ht[h]; n; n = n->next) {
  597. if (arg->count < arg->skip) {
  598. arg->count++;
  599. continue;
  600. }
  601. if (arg->fn(tp, (unsigned long)n, arg) < 0) {
  602. arg->stop = 1;
  603. return;
  604. }
  605. arg->count++;
  606. }
  607. }
  608. }
  609. }
  610. static int u32_dump(struct net *net, struct tcf_proto *tp, unsigned long fh,
  611. struct sk_buff *skb, struct tcmsg *t)
  612. {
  613. struct tc_u_knode *n = (struct tc_u_knode *)fh;
  614. struct nlattr *nest;
  615. if (n == NULL)
  616. return skb->len;
  617. t->tcm_handle = n->handle;
  618. nest = nla_nest_start(skb, TCA_OPTIONS);
  619. if (nest == NULL)
  620. goto nla_put_failure;
  621. if (TC_U32_KEY(n->handle) == 0) {
  622. struct tc_u_hnode *ht = (struct tc_u_hnode *)fh;
  623. u32 divisor = ht->divisor + 1;
  624. if (nla_put_u32(skb, TCA_U32_DIVISOR, divisor))
  625. goto nla_put_failure;
  626. } else {
  627. if (nla_put(skb, TCA_U32_SEL,
  628. sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
  629. &n->sel))
  630. goto nla_put_failure;
  631. if (n->ht_up) {
  632. u32 htid = n->handle & 0xFFFFF000;
  633. if (nla_put_u32(skb, TCA_U32_HASH, htid))
  634. goto nla_put_failure;
  635. }
  636. if (n->res.classid &&
  637. nla_put_u32(skb, TCA_U32_CLASSID, n->res.classid))
  638. goto nla_put_failure;
  639. if (n->ht_down &&
  640. nla_put_u32(skb, TCA_U32_LINK, n->ht_down->handle))
  641. goto nla_put_failure;
  642. #ifdef CONFIG_CLS_U32_MARK
  643. if ((n->mark.val || n->mark.mask) &&
  644. nla_put(skb, TCA_U32_MARK, sizeof(n->mark), &n->mark))
  645. goto nla_put_failure;
  646. #endif
  647. if (tcf_exts_dump(skb, &n->exts) < 0)
  648. goto nla_put_failure;
  649. #ifdef CONFIG_NET_CLS_IND
  650. if (n->ifindex) {
  651. struct net_device *dev;
  652. dev = __dev_get_by_index(net, n->ifindex);
  653. if (dev && nla_put_string(skb, TCA_U32_INDEV, dev->name))
  654. goto nla_put_failure;
  655. }
  656. #endif
  657. #ifdef CONFIG_CLS_U32_PERF
  658. if (nla_put(skb, TCA_U32_PCNT,
  659. sizeof(struct tc_u32_pcnt) + n->sel.nkeys*sizeof(u64),
  660. n->pf))
  661. goto nla_put_failure;
  662. #endif
  663. }
  664. nla_nest_end(skb, nest);
  665. if (TC_U32_KEY(n->handle))
  666. if (tcf_exts_dump_stats(skb, &n->exts) < 0)
  667. goto nla_put_failure;
  668. return skb->len;
  669. nla_put_failure:
  670. nla_nest_cancel(skb, nest);
  671. return -1;
  672. }
  673. static struct tcf_proto_ops cls_u32_ops __read_mostly = {
  674. .kind = "u32",
  675. .classify = u32_classify,
  676. .init = u32_init,
  677. .destroy = u32_destroy,
  678. .get = u32_get,
  679. .put = u32_put,
  680. .change = u32_change,
  681. .delete = u32_delete,
  682. .walk = u32_walk,
  683. .dump = u32_dump,
  684. .owner = THIS_MODULE,
  685. };
  686. static int __init init_u32(void)
  687. {
  688. pr_info("u32 classifier\n");
  689. #ifdef CONFIG_CLS_U32_PERF
  690. pr_info(" Performance counters on\n");
  691. #endif
  692. #ifdef CONFIG_NET_CLS_IND
  693. pr_info(" input device check on\n");
  694. #endif
  695. #ifdef CONFIG_NET_CLS_ACT
  696. pr_info(" Actions configured\n");
  697. #endif
  698. return register_tcf_proto_ops(&cls_u32_ops);
  699. }
  700. static void __exit exit_u32(void)
  701. {
  702. unregister_tcf_proto_ops(&cls_u32_ops);
  703. }
  704. module_init(init_u32)
  705. module_exit(exit_u32)
  706. MODULE_LICENSE("GPL");