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
8 #include <linux/module.h>
9 #include <linux/slab.h>
10 #include <linux/types.h>
11 #include <linux/kernel.h>
12 #include <linux/string.h>
13 #include <linux/errno.h>
14 #include <linux/refcount.h>
15 #include <linux/skbuff.h>
16 #include <net/dst.h>
17 #include <net/route.h>
18 #include <net/netlink.h>
19 #include <net/act_api.h>
20 #include <net/pkt_cls.h>
21 #include <net/tc_wrapper.h>
22
23 /*
24 * 1. For now we assume that route tags < 256.
25 * It allows to use direct table lookups, instead of hash tables.
26 * 2. For now we assume that "from TAG" and "fromdev DEV" statements
27 * are mutually exclusive.
28 * 3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
29 */
30 struct route4_fastmap {
31 struct route4_filter *filter;
32 u32 id;
33 int iif;
34 };
35
36 struct route4_head {
37 struct route4_fastmap fastmap[16];
38 struct route4_bucket __rcu *table[256 + 1];
39 struct rcu_head rcu;
40 };
41
42 struct route4_bucket {
43 /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
44 struct route4_filter __rcu *ht[16 + 16 + 1];
45 refcount_t filters_ref;
46 struct rcu_head rcu;
47 };
48
49 struct route4_filter {
50 struct route4_filter __rcu *next;
51 u32 id;
52 int iif;
53
54 struct tcf_result res;
55 struct tcf_exts exts;
56 u32 handle;
57 bool dying;
58 struct route4_bucket *bkt;
59 struct tcf_proto *tp;
60 struct rcu_work rwork;
61 };
62
63 #define ROUTE4_FAILURE ((struct route4_filter *)(-1L))
64
route4_fastmap_hash(u32 id,int iif)65 static inline int route4_fastmap_hash(u32 id, int iif)
66 {
67 return id & 0xF;
68 }
69
70 static DEFINE_SPINLOCK(fastmap_lock);
71 static void
route4_reset_fastmap(struct route4_head * head,struct route4_filter * f)72 route4_reset_fastmap(struct route4_head *head, struct route4_filter *f)
73 {
74 spin_lock_bh(&fastmap_lock);
75 if (f)
76 f->dying = true;
77 memset(head->fastmap, 0, sizeof(head->fastmap));
78 spin_unlock_bh(&fastmap_lock);
79 }
80
81 static void
route4_set_fastmap(struct route4_head * head,u32 id,int iif,struct route4_filter * f)82 route4_set_fastmap(struct route4_head *head, u32 id, int iif,
83 struct route4_filter *f)
84 {
85 int h = route4_fastmap_hash(id, iif);
86
87 /* fastmap updates must look atomic to aling id, iff, filter */
88 spin_lock_bh(&fastmap_lock);
89 if (f == ROUTE4_FAILURE || !f->dying) {
90 head->fastmap[h].id = id;
91 head->fastmap[h].iif = iif;
92 head->fastmap[h].filter = f;
93 }
94 spin_unlock_bh(&fastmap_lock);
95 }
96
route4_hash_to(u32 id)97 static inline int route4_hash_to(u32 id)
98 {
99 return id & 0xFF;
100 }
101
route4_hash_from(u32 id)102 static inline int route4_hash_from(u32 id)
103 {
104 return (id >> 16) & 0xF;
105 }
106
route4_hash_iif(int iif)107 static inline int route4_hash_iif(int iif)
108 {
109 return 16 + ((iif >> 16) & 0xF);
110 }
111
route4_hash_wild(void)112 static inline int route4_hash_wild(void)
113 {
114 return 32;
115 }
116
117 #define ROUTE4_APPLY_RESULT() \
118 { \
119 *res = f->res; \
120 if (tcf_exts_has_actions(&f->exts)) { \
121 int r = tcf_exts_exec(skb, &f->exts, res); \
122 if (r < 0) { \
123 dont_cache = 1; \
124 continue; \
125 } \
126 return r; \
127 } else if (!dont_cache) \
128 route4_set_fastmap(head, id, iif, f); \
129 return 0; \
130 }
131
route4_classify(struct sk_buff * skb,const struct tcf_proto * tp,struct tcf_result * res)132 TC_INDIRECT_SCOPE int route4_classify(struct sk_buff *skb,
133 const struct tcf_proto *tp,
134 struct tcf_result *res)
135 {
136 struct route4_head *head = rcu_dereference_bh(tp->root);
137 struct dst_entry *dst;
138 struct route4_bucket *b;
139 struct route4_filter *f;
140 u32 id, h;
141 int iif, dont_cache = 0;
142
143 dst = skb_dst(skb);
144 if (!dst)
145 goto failure;
146
147 id = dst->tclassid;
148
149 iif = inet_iif(skb);
150
151 h = route4_fastmap_hash(id, iif);
152
153 spin_lock(&fastmap_lock);
154 if (id == head->fastmap[h].id &&
155 iif == head->fastmap[h].iif &&
156 (f = head->fastmap[h].filter) != NULL) {
157 if (f == ROUTE4_FAILURE) {
158 spin_unlock(&fastmap_lock);
159 goto failure;
160 }
161
162 *res = f->res;
163 spin_unlock(&fastmap_lock);
164 return 0;
165 }
166 spin_unlock(&fastmap_lock);
167
168 h = route4_hash_to(id);
169
170 restart:
171 b = rcu_dereference_bh(head->table[h]);
172 if (b) {
173 for (f = rcu_dereference_bh(b->ht[route4_hash_from(id)]);
174 f;
175 f = rcu_dereference_bh(f->next))
176 if (f->id == id)
177 ROUTE4_APPLY_RESULT();
178
179 for (f = rcu_dereference_bh(b->ht[route4_hash_iif(iif)]);
180 f;
181 f = rcu_dereference_bh(f->next))
182 if (f->iif == iif)
183 ROUTE4_APPLY_RESULT();
184
185 for (f = rcu_dereference_bh(b->ht[route4_hash_wild()]);
186 f;
187 f = rcu_dereference_bh(f->next))
188 ROUTE4_APPLY_RESULT();
189 }
190 if (h < 256) {
191 h = 256;
192 id &= ~0xFFFF;
193 goto restart;
194 }
195
196 if (!dont_cache)
197 route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
198 failure:
199 return -1;
200 }
201
to_hash(u32 id)202 static inline u32 to_hash(u32 id)
203 {
204 u32 h = id & 0xFF;
205
206 if (id & 0x8000)
207 h += 256;
208 return h;
209 }
210
from_hash(u32 id)211 static inline u32 from_hash(u32 id)
212 {
213 id &= 0xFFFF;
214 if (id == 0xFFFF)
215 return 32;
216 if (!(id & 0x8000)) {
217 if (id > 255)
218 return 256;
219 return id & 0xF;
220 }
221 return 16 + (id & 0xF);
222 }
223
route4_get(struct tcf_proto * tp,u32 handle)224 static void *route4_get(struct tcf_proto *tp, u32 handle)
225 {
226 struct route4_head *head = rtnl_dereference(tp->root);
227 struct route4_bucket *b;
228 struct route4_filter *f;
229 unsigned int h1, h2;
230
231 h1 = to_hash(handle);
232 if (h1 > 256)
233 return NULL;
234
235 h2 = from_hash(handle >> 16);
236 if (h2 > 32)
237 return NULL;
238
239 b = rtnl_dereference(head->table[h1]);
240 if (b) {
241 for (f = rtnl_dereference(b->ht[h2]);
242 f;
243 f = rtnl_dereference(f->next))
244 if (f->handle == handle)
245 return f;
246 }
247 return NULL;
248 }
249
route4_init(struct tcf_proto * tp)250 static int route4_init(struct tcf_proto *tp)
251 {
252 struct route4_head *head;
253
254 head = kzalloc_obj(struct route4_head);
255 if (head == NULL)
256 return -ENOBUFS;
257
258 rcu_assign_pointer(tp->root, head);
259 return 0;
260 }
261
__route4_delete_filter(struct route4_filter * f)262 static void __route4_delete_filter(struct route4_filter *f)
263 {
264 tcf_exts_destroy(&f->exts);
265 tcf_exts_put_net(&f->exts);
266 kfree(f);
267 }
268
route4_delete_filter_work(struct work_struct * work)269 static void route4_delete_filter_work(struct work_struct *work)
270 {
271 struct route4_filter *f = container_of(to_rcu_work(work),
272 struct route4_filter,
273 rwork);
274 rtnl_lock();
275 __route4_delete_filter(f);
276 rtnl_unlock();
277 }
278
route4_queue_work(struct route4_filter * f)279 static void route4_queue_work(struct route4_filter *f)
280 {
281 tcf_queue_work(&f->rwork, route4_delete_filter_work);
282 }
283
route4_destroy(struct tcf_proto * tp,bool rtnl_held,struct netlink_ext_ack * extack)284 static void route4_destroy(struct tcf_proto *tp, bool rtnl_held,
285 struct netlink_ext_ack *extack)
286 {
287 struct route4_head *head = rtnl_dereference(tp->root);
288 int h1, h2;
289
290 if (head == NULL)
291 return;
292
293 for (h1 = 0; h1 <= 256; h1++) {
294 struct route4_bucket *b;
295
296 b = rtnl_dereference(head->table[h1]);
297 if (b) {
298 for (h2 = 0; h2 <= 32; h2++) {
299 struct route4_filter *f;
300
301 while ((f = rtnl_dereference(b->ht[h2])) != NULL) {
302 struct route4_filter *next;
303
304 next = rtnl_dereference(f->next);
305 RCU_INIT_POINTER(b->ht[h2], next);
306 tcf_unbind_filter(tp, &f->res);
307 /* Mark the filter dying under fastmap_lock so
308 * any in-flight reader that still holds it
309 * will skip the republish in route4_set_fastmap().
310 */
311 spin_lock_bh(&fastmap_lock);
312 f->dying = true;
313 spin_unlock_bh(&fastmap_lock);
314 if (tcf_exts_get_net(&f->exts))
315 route4_queue_work(f);
316 else
317 __route4_delete_filter(f);
318 }
319 }
320 RCU_INIT_POINTER(head->table[h1], NULL);
321 kfree_rcu(b, rcu);
322 }
323 }
324
325 /* All filters are unlinked and marked dying, so no in-flight
326 * reader can republish a stale entry after this reset.
327 */
328 route4_reset_fastmap(head, NULL);
329 kfree_rcu(head, rcu);
330 }
331
route4_delete(struct tcf_proto * tp,void * arg,bool * last,bool rtnl_held,struct netlink_ext_ack * extack)332 static int route4_delete(struct tcf_proto *tp, void *arg, bool *last,
333 bool rtnl_held, struct netlink_ext_ack *extack)
334 {
335 struct route4_head *head = rtnl_dereference(tp->root);
336 struct route4_filter *f = arg;
337 struct route4_filter __rcu **fp;
338 struct route4_filter *nf;
339 struct route4_bucket *b;
340 unsigned int h = 0;
341 int h1;
342
343 if (!head || !f)
344 return -EINVAL;
345
346 h = f->handle;
347 b = f->bkt;
348
349 fp = &b->ht[from_hash(h >> 16)];
350 for (nf = rtnl_dereference(*fp); nf;
351 fp = &nf->next, nf = rtnl_dereference(*fp)) {
352 if (nf == f) {
353 /* unlink it */
354 RCU_INIT_POINTER(*fp, rtnl_dereference(f->next));
355
356 /* Clear any fastmap entries that may ref this filter and
357 * mark it dying so in-flight readers can't republish it
358 * after the reset.
359 */
360 route4_reset_fastmap(head, f);
361
362 /* Delete it */
363 tcf_unbind_filter(tp, &f->res);
364 tcf_exts_get_net(&f->exts);
365 tcf_queue_work(&f->rwork, route4_delete_filter_work);
366
367 if (refcount_dec_and_test(&b->filters_ref)) {
368 RCU_INIT_POINTER(head->table[to_hash(h)], NULL);
369 kfree_rcu(b, rcu);
370 }
371 break;
372 }
373 }
374
375 *last = true;
376 for (h1 = 0; h1 <= 256; h1++) {
377 if (rcu_access_pointer(head->table[h1])) {
378 *last = false;
379 break;
380 }
381 }
382
383 return 0;
384 }
385
386 static const struct nla_policy route4_policy[TCA_ROUTE4_MAX + 1] = {
387 [TCA_ROUTE4_CLASSID] = { .type = NLA_U32 },
388 [TCA_ROUTE4_TO] = NLA_POLICY_MAX(NLA_U32, 0xFF),
389 [TCA_ROUTE4_FROM] = NLA_POLICY_MAX(NLA_U32, 0xFF),
390 [TCA_ROUTE4_IIF] = NLA_POLICY_MAX(NLA_U32, 0x7FFF),
391 };
392
route4_set_parms(struct net * net,struct tcf_proto * tp,unsigned long base,struct route4_filter * f,u32 handle,struct route4_head * head,struct nlattr ** tb,struct nlattr * est,struct route4_filter * fold,u32 flags,struct netlink_ext_ack * extack)393 static int route4_set_parms(struct net *net, struct tcf_proto *tp,
394 unsigned long base, struct route4_filter *f,
395 u32 handle, struct route4_head *head,
396 struct nlattr **tb, struct nlattr *est,
397 struct route4_filter *fold, u32 flags,
398 struct netlink_ext_ack *extack)
399 {
400 u32 id = 0, to = 0, nhandle = 0x8000;
401 struct route4_filter *fp;
402 unsigned int h1;
403 struct route4_bucket *b;
404 int err;
405
406 err = tcf_exts_validate(net, tp, tb, est, &f->exts, flags, extack);
407 if (err < 0)
408 return err;
409
410 if (tb[TCA_ROUTE4_TO]) {
411 if (!fold && handle & 0x8000) {
412 NL_SET_ERR_MSG(extack, "Invalid handle");
413 return -EINVAL;
414 }
415 to = nla_get_u32(tb[TCA_ROUTE4_TO]);
416 nhandle = to;
417 }
418
419 if (tb[TCA_ROUTE4_FROM] && tb[TCA_ROUTE4_IIF]) {
420 NL_SET_ERR_MSG_ATTR(extack, tb[TCA_ROUTE4_FROM],
421 "'from' and 'fromif' are mutually exclusive");
422 return -EINVAL;
423 }
424
425 if (tb[TCA_ROUTE4_FROM]) {
426 id = nla_get_u32(tb[TCA_ROUTE4_FROM]);
427 nhandle |= id << 16;
428 } else if (tb[TCA_ROUTE4_IIF]) {
429 id = nla_get_u32(tb[TCA_ROUTE4_IIF]);
430 nhandle |= (id | 0x8000) << 16;
431 } else
432 nhandle |= 0xFFFF << 16;
433
434 if (handle && (!fold || nhandle == (handle & ~0x7F00)))
435 nhandle |= handle & 0x7F00;
436
437 if (handle && !fold && nhandle != handle) {
438 NL_SET_ERR_MSG_FMT(extack,
439 "Handle mismatch constructed: %x (expected: %x)",
440 handle, nhandle);
441 return -EINVAL;
442 }
443
444 if (!nhandle) {
445 NL_SET_ERR_MSG(extack, "Replacing with handle of 0 is invalid");
446 return -EINVAL;
447 }
448
449 h1 = to_hash(nhandle);
450 b = rtnl_dereference(head->table[h1]);
451 if (!b) {
452 b = kzalloc_obj(struct route4_bucket, GFP_KERNEL_ACCOUNT);
453 if (b == NULL)
454 return -ENOBUFS;
455
456 refcount_set(&b->filters_ref, 1);
457 rcu_assign_pointer(head->table[h1], b);
458 } else {
459 unsigned int h2 = from_hash(nhandle >> 16);
460
461 for (fp = rtnl_dereference(b->ht[h2]);
462 fp;
463 fp = rtnl_dereference(fp->next))
464 if (fp != fold && fp->handle == nhandle) {
465 NL_SET_ERR_MSG_FMT(extack,
466 "Handle %x is already in use",
467 nhandle);
468 return -EEXIST;
469 }
470
471 refcount_inc(&b->filters_ref);
472 }
473
474 if (tb[TCA_ROUTE4_TO])
475 f->id = to;
476
477 if (tb[TCA_ROUTE4_FROM])
478 f->id = to | id<<16;
479 else if (tb[TCA_ROUTE4_IIF])
480 f->iif = id;
481
482 f->handle = nhandle;
483 f->bkt = b;
484 f->tp = tp;
485
486 if (tb[TCA_ROUTE4_CLASSID]) {
487 f->res.classid = nla_get_u32(tb[TCA_ROUTE4_CLASSID]);
488 tcf_bind_filter(tp, &f->res, base);
489 }
490
491 return 0;
492 }
493
route4_change(struct net * net,struct sk_buff * in_skb,struct tcf_proto * tp,unsigned long base,u32 handle,struct nlattr ** tca,void ** arg,u32 flags,struct netlink_ext_ack * extack)494 static int route4_change(struct net *net, struct sk_buff *in_skb,
495 struct tcf_proto *tp, unsigned long base, u32 handle,
496 struct nlattr **tca, void **arg, u32 flags,
497 struct netlink_ext_ack *extack)
498 {
499 struct route4_head *head = rtnl_dereference(tp->root);
500 struct route4_filter __rcu **fp;
501 struct route4_filter *fold, *f1, *pfp, *f = NULL;
502 struct route4_bucket *b;
503 struct nlattr *tb[TCA_ROUTE4_MAX + 1];
504 unsigned int h;
505 int err;
506
507 if (!handle) {
508 NL_SET_ERR_MSG(extack, "Creating with handle of 0 is invalid");
509 return -EINVAL;
510 }
511
512 if (NL_REQ_ATTR_CHECK(extack, NULL, tca, TCA_OPTIONS)) {
513 NL_SET_ERR_MSG_MOD(extack, "Missing options");
514 return -EINVAL;
515 }
516
517 err = nla_parse_nested_deprecated(tb, TCA_ROUTE4_MAX, tca[TCA_OPTIONS],
518 route4_policy, NULL);
519 if (err < 0)
520 return err;
521
522 fold = *arg;
523 if (fold && fold->handle != handle)
524 return -EINVAL;
525
526 err = -ENOBUFS;
527 f = kzalloc_obj(struct route4_filter, GFP_KERNEL_ACCOUNT);
528 if (!f)
529 goto errout;
530
531 err = tcf_exts_init(&f->exts, net, TCA_ROUTE4_ACT, TCA_ROUTE4_POLICE);
532 if (err < 0)
533 goto errout;
534
535 if (fold) {
536 f->id = fold->id;
537 f->iif = fold->iif;
538 f->handle = fold->handle;
539
540 f->tp = fold->tp;
541 f->bkt = fold->bkt;
542 }
543
544 err = route4_set_parms(net, tp, base, f, handle, head, tb,
545 tca[TCA_RATE], fold, flags, extack);
546 if (err < 0)
547 goto errout;
548
549 h = from_hash(f->handle >> 16);
550 fp = &f->bkt->ht[h];
551 for (pfp = rtnl_dereference(*fp);
552 (f1 = rtnl_dereference(*fp)) != NULL;
553 fp = &f1->next)
554 if (f->handle < f1->handle)
555 break;
556
557 tcf_block_netif_keep_dst(tp->chain->block);
558 rcu_assign_pointer(f->next, f1);
559 rcu_assign_pointer(*fp, f);
560
561 if (fold) {
562 b = fold->bkt;
563 h = from_hash(fold->handle >> 16);
564 fp = &b->ht[h];
565 for (pfp = rtnl_dereference(*fp); pfp;
566 fp = &pfp->next, pfp = rtnl_dereference(*fp)) {
567 if (pfp == fold) {
568 rcu_assign_pointer(*fp, fold->next);
569 if (refcount_dec_and_test(&b->filters_ref)) {
570 unsigned int th = to_hash(fold->handle);
571
572 RCU_INIT_POINTER(head->table[th], NULL);
573 kfree_rcu(b, rcu);
574 }
575 break;
576 }
577 }
578 }
579
580 route4_reset_fastmap(head, fold);
581 *arg = f;
582 if (fold) {
583 tcf_unbind_filter(tp, &fold->res);
584 tcf_exts_get_net(&fold->exts);
585 tcf_queue_work(&fold->rwork, route4_delete_filter_work);
586 }
587 return 0;
588
589 errout:
590 if (f)
591 tcf_exts_destroy(&f->exts);
592 kfree(f);
593 return err;
594 }
595
route4_walk(struct tcf_proto * tp,struct tcf_walker * arg,bool rtnl_held)596 static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg,
597 bool rtnl_held)
598 {
599 struct route4_head *head = rtnl_dereference(tp->root);
600 unsigned int h, h1;
601
602 if (head == NULL || arg->stop)
603 return;
604
605 for (h = 0; h <= 256; h++) {
606 struct route4_bucket *b = rtnl_dereference(head->table[h]);
607
608 if (b) {
609 for (h1 = 0; h1 <= 32; h1++) {
610 struct route4_filter *f;
611
612 for (f = rtnl_dereference(b->ht[h1]);
613 f;
614 f = rtnl_dereference(f->next)) {
615 if (!tc_cls_stats_dump(tp, arg, f))
616 return;
617 }
618 }
619 }
620 }
621 }
622
route4_dump(struct net * net,struct tcf_proto * tp,void * fh,struct sk_buff * skb,struct tcmsg * t,bool rtnl_held)623 static int route4_dump(struct net *net, struct tcf_proto *tp, void *fh,
624 struct sk_buff *skb, struct tcmsg *t, bool rtnl_held)
625 {
626 struct route4_filter *f = fh;
627 struct nlattr *nest;
628 u32 id;
629
630 if (f == NULL)
631 return skb->len;
632
633 t->tcm_handle = f->handle;
634
635 nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
636 if (nest == NULL)
637 goto nla_put_failure;
638
639 if (!(f->handle & 0x8000)) {
640 id = f->id & 0xFF;
641 if (nla_put_u32(skb, TCA_ROUTE4_TO, id))
642 goto nla_put_failure;
643 }
644 if (f->handle & 0x80000000) {
645 if ((f->handle >> 16) != 0xFFFF &&
646 nla_put_u32(skb, TCA_ROUTE4_IIF, f->iif))
647 goto nla_put_failure;
648 } else {
649 id = f->id >> 16;
650 if (nla_put_u32(skb, TCA_ROUTE4_FROM, id))
651 goto nla_put_failure;
652 }
653 if (f->res.classid &&
654 nla_put_u32(skb, TCA_ROUTE4_CLASSID, f->res.classid))
655 goto nla_put_failure;
656
657 if (tcf_exts_dump(skb, &f->exts) < 0)
658 goto nla_put_failure;
659
660 nla_nest_end(skb, nest);
661
662 if (tcf_exts_dump_stats(skb, &f->exts) < 0)
663 goto nla_put_failure;
664
665 return skb->len;
666
667 nla_put_failure:
668 nla_nest_cancel(skb, nest);
669 return -1;
670 }
671
route4_bind_class(void * fh,u32 classid,unsigned long cl,void * q,unsigned long base)672 static void route4_bind_class(void *fh, u32 classid, unsigned long cl, void *q,
673 unsigned long base)
674 {
675 struct route4_filter *f = fh;
676
677 tc_cls_bind_class(classid, cl, q, &f->res, base);
678 }
679
680 static struct tcf_proto_ops cls_route4_ops __read_mostly = {
681 .kind = "route",
682 .classify = route4_classify,
683 .init = route4_init,
684 .destroy = route4_destroy,
685 .get = route4_get,
686 .change = route4_change,
687 .delete = route4_delete,
688 .walk = route4_walk,
689 .dump = route4_dump,
690 .bind_class = route4_bind_class,
691 .owner = THIS_MODULE,
692 };
693 MODULE_ALIAS_NET_CLS("route");
694
init_route4(void)695 static int __init init_route4(void)
696 {
697 return register_tcf_proto_ops(&cls_route4_ops);
698 }
699
exit_route4(void)700 static void __exit exit_route4(void)
701 {
702 unregister_tcf_proto_ops(&cls_route4_ops);
703 }
704
705 module_init(init_route4)
706 module_exit(exit_route4)
707 MODULE_DESCRIPTION("Routing table realm based TC classifier");
708 MODULE_LICENSE("GPL");
709