cls_route.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /*
  3. * net/sched/cls_route.c ROUTE4 classifier.
  4. *
  5. * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  6. */
  7. #include <linux/module.h>
  8. #include <linux/slab.h>
  9. #include <linux/types.h>
  10. #include <linux/kernel.h>
  11. #include <linux/string.h>
  12. #include <linux/errno.h>
  13. #include <linux/skbuff.h>
  14. #include <net/dst.h>
  15. #include <net/route.h>
  16. #include <net/netlink.h>
  17. #include <net/act_api.h>
  18. #include <net/pkt_cls.h>
  19. /*
  20. * 1. For now we assume that route tags < 256.
  21. * It allows to use direct table lookups, instead of hash tables.
  22. * 2. For now we assume that "from TAG" and "fromdev DEV" statements
  23. * are mutually exclusive.
  24. * 3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
  25. */
  26. struct route4_fastmap {
  27. struct route4_filter *filter;
  28. u32 id;
  29. int iif;
  30. };
  31. struct route4_head {
  32. struct route4_fastmap fastmap[16];
  33. struct route4_bucket __rcu *table[256 + 1];
  34. struct rcu_head rcu;
  35. };
  36. struct route4_bucket {
  37. /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
  38. struct route4_filter __rcu *ht[16 + 16 + 1];
  39. struct rcu_head rcu;
  40. };
  41. struct route4_filter {
  42. struct route4_filter __rcu *next;
  43. u32 id;
  44. int iif;
  45. struct tcf_result res;
  46. struct tcf_exts exts;
  47. u32 handle;
  48. struct route4_bucket *bkt;
  49. struct tcf_proto *tp;
  50. struct rcu_work rwork;
  51. };
  52. #define ROUTE4_FAILURE ((struct route4_filter *)(-1L))
  53. static inline int route4_fastmap_hash(u32 id, int iif)
  54. {
  55. return id & 0xF;
  56. }
  57. static DEFINE_SPINLOCK(fastmap_lock);
  58. static void
  59. route4_reset_fastmap(struct route4_head *head)
  60. {
  61. spin_lock_bh(&fastmap_lock);
  62. memset(head->fastmap, 0, sizeof(head->fastmap));
  63. spin_unlock_bh(&fastmap_lock);
  64. }
  65. static void
  66. route4_set_fastmap(struct route4_head *head, u32 id, int iif,
  67. struct route4_filter *f)
  68. {
  69. int h = route4_fastmap_hash(id, iif);
  70. /* fastmap updates must look atomic to aling id, iff, filter */
  71. spin_lock_bh(&fastmap_lock);
  72. head->fastmap[h].id = id;
  73. head->fastmap[h].iif = iif;
  74. head->fastmap[h].filter = f;
  75. spin_unlock_bh(&fastmap_lock);
  76. }
  77. static inline int route4_hash_to(u32 id)
  78. {
  79. return id & 0xFF;
  80. }
  81. static inline int route4_hash_from(u32 id)
  82. {
  83. return (id >> 16) & 0xF;
  84. }
  85. static inline int route4_hash_iif(int iif)
  86. {
  87. return 16 + ((iif >> 16) & 0xF);
  88. }
  89. static inline int route4_hash_wild(void)
  90. {
  91. return 32;
  92. }
  93. #define ROUTE4_APPLY_RESULT() \
  94. { \
  95. *res = f->res; \
  96. if (tcf_exts_has_actions(&f->exts)) { \
  97. int r = tcf_exts_exec(skb, &f->exts, res); \
  98. if (r < 0) { \
  99. dont_cache = 1; \
  100. continue; \
  101. } \
  102. return r; \
  103. } else if (!dont_cache) \
  104. route4_set_fastmap(head, id, iif, f); \
  105. return 0; \
  106. }
  107. static int route4_classify(struct sk_buff *skb, const struct tcf_proto *tp,
  108. struct tcf_result *res)
  109. {
  110. struct route4_head *head = rcu_dereference_bh(tp->root);
  111. struct dst_entry *dst;
  112. struct route4_bucket *b;
  113. struct route4_filter *f;
  114. u32 id, h;
  115. int iif, dont_cache = 0;
  116. dst = skb_dst(skb);
  117. if (!dst)
  118. goto failure;
  119. id = dst->tclassid;
  120. iif = inet_iif(skb);
  121. h = route4_fastmap_hash(id, iif);
  122. spin_lock(&fastmap_lock);
  123. if (id == head->fastmap[h].id &&
  124. iif == head->fastmap[h].iif &&
  125. (f = head->fastmap[h].filter) != NULL) {
  126. if (f == ROUTE4_FAILURE) {
  127. spin_unlock(&fastmap_lock);
  128. goto failure;
  129. }
  130. *res = f->res;
  131. spin_unlock(&fastmap_lock);
  132. return 0;
  133. }
  134. spin_unlock(&fastmap_lock);
  135. h = route4_hash_to(id);
  136. restart:
  137. b = rcu_dereference_bh(head->table[h]);
  138. if (b) {
  139. for (f = rcu_dereference_bh(b->ht[route4_hash_from(id)]);
  140. f;
  141. f = rcu_dereference_bh(f->next))
  142. if (f->id == id)
  143. ROUTE4_APPLY_RESULT();
  144. for (f = rcu_dereference_bh(b->ht[route4_hash_iif(iif)]);
  145. f;
  146. f = rcu_dereference_bh(f->next))
  147. if (f->iif == iif)
  148. ROUTE4_APPLY_RESULT();
  149. for (f = rcu_dereference_bh(b->ht[route4_hash_wild()]);
  150. f;
  151. f = rcu_dereference_bh(f->next))
  152. ROUTE4_APPLY_RESULT();
  153. }
  154. if (h < 256) {
  155. h = 256;
  156. id &= ~0xFFFF;
  157. goto restart;
  158. }
  159. if (!dont_cache)
  160. route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
  161. failure:
  162. return -1;
  163. }
  164. static inline u32 to_hash(u32 id)
  165. {
  166. u32 h = id & 0xFF;
  167. if (id & 0x8000)
  168. h += 256;
  169. return h;
  170. }
  171. static inline u32 from_hash(u32 id)
  172. {
  173. id &= 0xFFFF;
  174. if (id == 0xFFFF)
  175. return 32;
  176. if (!(id & 0x8000)) {
  177. if (id > 255)
  178. return 256;
  179. return id & 0xF;
  180. }
  181. return 16 + (id & 0xF);
  182. }
  183. static void *route4_get(struct tcf_proto *tp, u32 handle)
  184. {
  185. struct route4_head *head = rtnl_dereference(tp->root);
  186. struct route4_bucket *b;
  187. struct route4_filter *f;
  188. unsigned int h1, h2;
  189. h1 = to_hash(handle);
  190. if (h1 > 256)
  191. return NULL;
  192. h2 = from_hash(handle >> 16);
  193. if (h2 > 32)
  194. return NULL;
  195. b = rtnl_dereference(head->table[h1]);
  196. if (b) {
  197. for (f = rtnl_dereference(b->ht[h2]);
  198. f;
  199. f = rtnl_dereference(f->next))
  200. if (f->handle == handle)
  201. return f;
  202. }
  203. return NULL;
  204. }
  205. static int route4_init(struct tcf_proto *tp)
  206. {
  207. struct route4_head *head;
  208. head = kzalloc(sizeof(struct route4_head), GFP_KERNEL);
  209. if (head == NULL)
  210. return -ENOBUFS;
  211. rcu_assign_pointer(tp->root, head);
  212. return 0;
  213. }
  214. static void __route4_delete_filter(struct route4_filter *f)
  215. {
  216. tcf_exts_destroy(&f->exts);
  217. tcf_exts_put_net(&f->exts);
  218. kfree(f);
  219. }
  220. static void route4_delete_filter_work(struct work_struct *work)
  221. {
  222. struct route4_filter *f = container_of(to_rcu_work(work),
  223. struct route4_filter,
  224. rwork);
  225. rtnl_lock();
  226. __route4_delete_filter(f);
  227. rtnl_unlock();
  228. }
  229. static void route4_queue_work(struct route4_filter *f)
  230. {
  231. tcf_queue_work(&f->rwork, route4_delete_filter_work);
  232. }
  233. static void route4_destroy(struct tcf_proto *tp, bool rtnl_held,
  234. struct netlink_ext_ack *extack)
  235. {
  236. struct route4_head *head = rtnl_dereference(tp->root);
  237. int h1, h2;
  238. if (head == NULL)
  239. return;
  240. for (h1 = 0; h1 <= 256; h1++) {
  241. struct route4_bucket *b;
  242. b = rtnl_dereference(head->table[h1]);
  243. if (b) {
  244. for (h2 = 0; h2 <= 32; h2++) {
  245. struct route4_filter *f;
  246. while ((f = rtnl_dereference(b->ht[h2])) != NULL) {
  247. struct route4_filter *next;
  248. next = rtnl_dereference(f->next);
  249. RCU_INIT_POINTER(b->ht[h2], next);
  250. tcf_unbind_filter(tp, &f->res);
  251. if (tcf_exts_get_net(&f->exts))
  252. route4_queue_work(f);
  253. else
  254. __route4_delete_filter(f);
  255. }
  256. }
  257. RCU_INIT_POINTER(head->table[h1], NULL);
  258. kfree_rcu(b, rcu);
  259. }
  260. }
  261. kfree_rcu(head, rcu);
  262. }
  263. static int route4_delete(struct tcf_proto *tp, void *arg, bool *last,
  264. bool rtnl_held, struct netlink_ext_ack *extack)
  265. {
  266. struct route4_head *head = rtnl_dereference(tp->root);
  267. struct route4_filter *f = arg;
  268. struct route4_filter __rcu **fp;
  269. struct route4_filter *nf;
  270. struct route4_bucket *b;
  271. unsigned int h = 0;
  272. int i, h1;
  273. if (!head || !f)
  274. return -EINVAL;
  275. h = f->handle;
  276. b = f->bkt;
  277. fp = &b->ht[from_hash(h >> 16)];
  278. for (nf = rtnl_dereference(*fp); nf;
  279. fp = &nf->next, nf = rtnl_dereference(*fp)) {
  280. if (nf == f) {
  281. /* unlink it */
  282. RCU_INIT_POINTER(*fp, rtnl_dereference(f->next));
  283. /* Remove any fastmap lookups that might ref filter
  284. * notice we unlink'd the filter so we can't get it
  285. * back in the fastmap.
  286. */
  287. route4_reset_fastmap(head);
  288. /* Delete it */
  289. tcf_unbind_filter(tp, &f->res);
  290. tcf_exts_get_net(&f->exts);
  291. tcf_queue_work(&f->rwork, route4_delete_filter_work);
  292. /* Strip RTNL protected tree */
  293. for (i = 0; i <= 32; i++) {
  294. struct route4_filter *rt;
  295. rt = rtnl_dereference(b->ht[i]);
  296. if (rt)
  297. goto out;
  298. }
  299. /* OK, session has no flows */
  300. RCU_INIT_POINTER(head->table[to_hash(h)], NULL);
  301. kfree_rcu(b, rcu);
  302. break;
  303. }
  304. }
  305. out:
  306. *last = true;
  307. for (h1 = 0; h1 <= 256; h1++) {
  308. if (rcu_access_pointer(head->table[h1])) {
  309. *last = false;
  310. break;
  311. }
  312. }
  313. return 0;
  314. }
  315. static const struct nla_policy route4_policy[TCA_ROUTE4_MAX + 1] = {
  316. [TCA_ROUTE4_CLASSID] = { .type = NLA_U32 },
  317. [TCA_ROUTE4_TO] = { .type = NLA_U32 },
  318. [TCA_ROUTE4_FROM] = { .type = NLA_U32 },
  319. [TCA_ROUTE4_IIF] = { .type = NLA_U32 },
  320. };
  321. static int route4_set_parms(struct net *net, struct tcf_proto *tp,
  322. unsigned long base, struct route4_filter *f,
  323. u32 handle, struct route4_head *head,
  324. struct nlattr **tb, struct nlattr *est, int new,
  325. bool ovr, struct netlink_ext_ack *extack)
  326. {
  327. u32 id = 0, to = 0, nhandle = 0x8000;
  328. struct route4_filter *fp;
  329. unsigned int h1;
  330. struct route4_bucket *b;
  331. int err;
  332. err = tcf_exts_validate(net, tp, tb, est, &f->exts, ovr, true, extack);
  333. if (err < 0)
  334. return err;
  335. if (tb[TCA_ROUTE4_TO]) {
  336. if (new && handle & 0x8000)
  337. return -EINVAL;
  338. to = nla_get_u32(tb[TCA_ROUTE4_TO]);
  339. if (to > 0xFF)
  340. return -EINVAL;
  341. nhandle = to;
  342. }
  343. if (tb[TCA_ROUTE4_FROM]) {
  344. if (tb[TCA_ROUTE4_IIF])
  345. return -EINVAL;
  346. id = nla_get_u32(tb[TCA_ROUTE4_FROM]);
  347. if (id > 0xFF)
  348. return -EINVAL;
  349. nhandle |= id << 16;
  350. } else if (tb[TCA_ROUTE4_IIF]) {
  351. id = nla_get_u32(tb[TCA_ROUTE4_IIF]);
  352. if (id > 0x7FFF)
  353. return -EINVAL;
  354. nhandle |= (id | 0x8000) << 16;
  355. } else
  356. nhandle |= 0xFFFF << 16;
  357. if (handle && new) {
  358. nhandle |= handle & 0x7F00;
  359. if (nhandle != handle)
  360. return -EINVAL;
  361. }
  362. h1 = to_hash(nhandle);
  363. b = rtnl_dereference(head->table[h1]);
  364. if (!b) {
  365. b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
  366. if (b == NULL)
  367. return -ENOBUFS;
  368. rcu_assign_pointer(head->table[h1], b);
  369. } else {
  370. unsigned int h2 = from_hash(nhandle >> 16);
  371. for (fp = rtnl_dereference(b->ht[h2]);
  372. fp;
  373. fp = rtnl_dereference(fp->next))
  374. if (fp->handle == f->handle)
  375. return -EEXIST;
  376. }
  377. if (tb[TCA_ROUTE4_TO])
  378. f->id = to;
  379. if (tb[TCA_ROUTE4_FROM])
  380. f->id = to | id<<16;
  381. else if (tb[TCA_ROUTE4_IIF])
  382. f->iif = id;
  383. f->handle = nhandle;
  384. f->bkt = b;
  385. f->tp = tp;
  386. if (tb[TCA_ROUTE4_CLASSID]) {
  387. f->res.classid = nla_get_u32(tb[TCA_ROUTE4_CLASSID]);
  388. tcf_bind_filter(tp, &f->res, base);
  389. }
  390. return 0;
  391. }
  392. static int route4_change(struct net *net, struct sk_buff *in_skb,
  393. struct tcf_proto *tp, unsigned long base, u32 handle,
  394. struct nlattr **tca, void **arg, bool ovr,
  395. bool rtnl_held, struct netlink_ext_ack *extack)
  396. {
  397. struct route4_head *head = rtnl_dereference(tp->root);
  398. struct route4_filter __rcu **fp;
  399. struct route4_filter *fold, *f1, *pfp, *f = NULL;
  400. struct route4_bucket *b;
  401. struct nlattr *opt = tca[TCA_OPTIONS];
  402. struct nlattr *tb[TCA_ROUTE4_MAX + 1];
  403. unsigned int h, th;
  404. int err;
  405. bool new = true;
  406. if (opt == NULL)
  407. return handle ? -EINVAL : 0;
  408. err = nla_parse_nested_deprecated(tb, TCA_ROUTE4_MAX, opt,
  409. route4_policy, NULL);
  410. if (err < 0)
  411. return err;
  412. fold = *arg;
  413. if (fold && handle && fold->handle != handle)
  414. return -EINVAL;
  415. err = -ENOBUFS;
  416. f = kzalloc(sizeof(struct route4_filter), GFP_KERNEL);
  417. if (!f)
  418. goto errout;
  419. err = tcf_exts_init(&f->exts, net, TCA_ROUTE4_ACT, TCA_ROUTE4_POLICE);
  420. if (err < 0)
  421. goto errout;
  422. if (fold) {
  423. f->id = fold->id;
  424. f->iif = fold->iif;
  425. f->res = fold->res;
  426. f->handle = fold->handle;
  427. f->tp = fold->tp;
  428. f->bkt = fold->bkt;
  429. new = false;
  430. }
  431. err = route4_set_parms(net, tp, base, f, handle, head, tb,
  432. tca[TCA_RATE], new, ovr, extack);
  433. if (err < 0)
  434. goto errout;
  435. h = from_hash(f->handle >> 16);
  436. fp = &f->bkt->ht[h];
  437. for (pfp = rtnl_dereference(*fp);
  438. (f1 = rtnl_dereference(*fp)) != NULL;
  439. fp = &f1->next)
  440. if (f->handle < f1->handle)
  441. break;
  442. tcf_block_netif_keep_dst(tp->chain->block);
  443. rcu_assign_pointer(f->next, f1);
  444. rcu_assign_pointer(*fp, f);
  445. if (fold && fold->handle && f->handle != fold->handle) {
  446. th = to_hash(fold->handle);
  447. h = from_hash(fold->handle >> 16);
  448. b = rtnl_dereference(head->table[th]);
  449. if (b) {
  450. fp = &b->ht[h];
  451. for (pfp = rtnl_dereference(*fp); pfp;
  452. fp = &pfp->next, pfp = rtnl_dereference(*fp)) {
  453. if (pfp == fold) {
  454. rcu_assign_pointer(*fp, fold->next);
  455. break;
  456. }
  457. }
  458. }
  459. }
  460. route4_reset_fastmap(head);
  461. *arg = f;
  462. if (fold) {
  463. tcf_unbind_filter(tp, &fold->res);
  464. tcf_exts_get_net(&fold->exts);
  465. tcf_queue_work(&fold->rwork, route4_delete_filter_work);
  466. }
  467. return 0;
  468. errout:
  469. if (f)
  470. tcf_exts_destroy(&f->exts);
  471. kfree(f);
  472. return err;
  473. }
  474. static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg,
  475. bool rtnl_held)
  476. {
  477. struct route4_head *head = rtnl_dereference(tp->root);
  478. unsigned int h, h1;
  479. if (head == NULL || arg->stop)
  480. return;
  481. for (h = 0; h <= 256; h++) {
  482. struct route4_bucket *b = rtnl_dereference(head->table[h]);
  483. if (b) {
  484. for (h1 = 0; h1 <= 32; h1++) {
  485. struct route4_filter *f;
  486. for (f = rtnl_dereference(b->ht[h1]);
  487. f;
  488. f = rtnl_dereference(f->next)) {
  489. if (arg->count < arg->skip) {
  490. arg->count++;
  491. continue;
  492. }
  493. if (arg->fn(tp, f, arg) < 0) {
  494. arg->stop = 1;
  495. return;
  496. }
  497. arg->count++;
  498. }
  499. }
  500. }
  501. }
  502. }
  503. static int route4_dump(struct net *net, struct tcf_proto *tp, void *fh,
  504. struct sk_buff *skb, struct tcmsg *t, bool rtnl_held)
  505. {
  506. struct route4_filter *f = fh;
  507. struct nlattr *nest;
  508. u32 id;
  509. if (f == NULL)
  510. return skb->len;
  511. t->tcm_handle = f->handle;
  512. nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
  513. if (nest == NULL)
  514. goto nla_put_failure;
  515. if (!(f->handle & 0x8000)) {
  516. id = f->id & 0xFF;
  517. if (nla_put_u32(skb, TCA_ROUTE4_TO, id))
  518. goto nla_put_failure;
  519. }
  520. if (f->handle & 0x80000000) {
  521. if ((f->handle >> 16) != 0xFFFF &&
  522. nla_put_u32(skb, TCA_ROUTE4_IIF, f->iif))
  523. goto nla_put_failure;
  524. } else {
  525. id = f->id >> 16;
  526. if (nla_put_u32(skb, TCA_ROUTE4_FROM, id))
  527. goto nla_put_failure;
  528. }
  529. if (f->res.classid &&
  530. nla_put_u32(skb, TCA_ROUTE4_CLASSID, f->res.classid))
  531. goto nla_put_failure;
  532. if (tcf_exts_dump(skb, &f->exts) < 0)
  533. goto nla_put_failure;
  534. nla_nest_end(skb, nest);
  535. if (tcf_exts_dump_stats(skb, &f->exts) < 0)
  536. goto nla_put_failure;
  537. return skb->len;
  538. nla_put_failure:
  539. nla_nest_cancel(skb, nest);
  540. return -1;
  541. }
  542. static void route4_bind_class(void *fh, u32 classid, unsigned long cl, void *q,
  543. unsigned long base)
  544. {
  545. struct route4_filter *f = fh;
  546. if (f && f->res.classid == classid) {
  547. if (cl)
  548. __tcf_bind_filter(q, &f->res, base);
  549. else
  550. __tcf_unbind_filter(q, &f->res);
  551. }
  552. }
  553. static struct tcf_proto_ops cls_route4_ops __read_mostly = {
  554. .kind = "route",
  555. .classify = route4_classify,
  556. .init = route4_init,
  557. .destroy = route4_destroy,
  558. .get = route4_get,
  559. .change = route4_change,
  560. .delete = route4_delete,
  561. .walk = route4_walk,
  562. .dump = route4_dump,
  563. .bind_class = route4_bind_class,
  564. .owner = THIS_MODULE,
  565. };
  566. static int __init init_route4(void)
  567. {
  568. return register_tcf_proto_ops(&cls_route4_ops);
  569. }
  570. static void __exit exit_route4(void)
  571. {
  572. unregister_tcf_proto_ops(&cls_route4_ops);
  573. }
  574. module_init(init_route4)
  575. module_exit(exit_route4)
  576. MODULE_LICENSE("GPL");