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