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 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 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 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 97 static inline int route4_hash_to(u32 id) 98 { 99 return id & 0xFF; 100 } 101 102 static inline int route4_hash_from(u32 id) 103 { 104 return (id >> 16) & 0xF; 105 } 106 107 static inline int route4_hash_iif(int iif) 108 { 109 return 16 + ((iif >> 16) & 0xF); 110 } 111 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 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 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 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 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 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 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 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 279 static void route4_queue_work(struct route4_filter *f) 280 { 281 tcf_queue_work(&f->rwork, route4_delete_filter_work); 282 } 283 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 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 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 (fold && !tb[TCA_ROUTE4_TO] && !tb[TCA_ROUTE4_FROM] && 438 !tb[TCA_ROUTE4_IIF] && nhandle != fold->handle) { 439 NL_SET_ERR_MSG(extack, "Routing attributes required"); 440 return -EINVAL; 441 } 442 443 if (handle && !fold && nhandle != handle) { 444 NL_SET_ERR_MSG_FMT(extack, 445 "Handle mismatch constructed: %x (expected: %x)", 446 handle, nhandle); 447 return -EINVAL; 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 refcount_set(&b->filters_ref, 1); 463 rcu_assign_pointer(head->table[h1], b); 464 } else { 465 unsigned int h2 = from_hash(nhandle >> 16); 466 467 for (fp = rtnl_dereference(b->ht[h2]); 468 fp; 469 fp = rtnl_dereference(fp->next)) 470 if (fp != fold && fp->handle == nhandle) { 471 NL_SET_ERR_MSG_FMT(extack, 472 "Handle %x is already in use", 473 nhandle); 474 return -EEXIST; 475 } 476 477 refcount_inc(&b->filters_ref); 478 } 479 480 if (tb[TCA_ROUTE4_TO]) 481 f->id = to; 482 483 if (tb[TCA_ROUTE4_FROM]) 484 f->id = to | id<<16; 485 else if (tb[TCA_ROUTE4_IIF]) 486 f->iif = id; 487 488 f->handle = nhandle; 489 f->bkt = b; 490 f->tp = tp; 491 492 if (tb[TCA_ROUTE4_CLASSID]) { 493 f->res.classid = nla_get_u32(tb[TCA_ROUTE4_CLASSID]); 494 tcf_bind_filter(tp, &f->res, base); 495 } 496 497 return 0; 498 } 499 500 static int route4_change(struct net *net, struct sk_buff *in_skb, 501 struct tcf_proto *tp, unsigned long base, u32 handle, 502 struct nlattr **tca, void **arg, u32 flags, 503 struct netlink_ext_ack *extack) 504 { 505 struct route4_head *head = rtnl_dereference(tp->root); 506 struct route4_filter __rcu **fp; 507 struct route4_filter *fold, *f1, *pfp, *f = NULL; 508 struct route4_bucket *b; 509 struct nlattr *tb[TCA_ROUTE4_MAX + 1]; 510 unsigned int h; 511 int err; 512 513 if (!handle) { 514 NL_SET_ERR_MSG(extack, "Creating with handle of 0 is invalid"); 515 return -EINVAL; 516 } 517 518 if (NL_REQ_ATTR_CHECK(extack, NULL, tca, TCA_OPTIONS)) { 519 NL_SET_ERR_MSG_MOD(extack, "Missing options"); 520 return -EINVAL; 521 } 522 523 err = nla_parse_nested_deprecated(tb, TCA_ROUTE4_MAX, tca[TCA_OPTIONS], 524 route4_policy, NULL); 525 if (err < 0) 526 return err; 527 528 fold = *arg; 529 if (fold && fold->handle != handle) 530 return -EINVAL; 531 532 err = -ENOBUFS; 533 f = kzalloc_obj(struct route4_filter, GFP_KERNEL_ACCOUNT); 534 if (!f) 535 goto errout; 536 537 err = tcf_exts_init(&f->exts, net, TCA_ROUTE4_ACT, TCA_ROUTE4_POLICE); 538 if (err < 0) 539 goto errout; 540 541 if (fold) { 542 f->id = fold->id; 543 f->iif = fold->iif; 544 f->handle = fold->handle; 545 546 f->tp = fold->tp; 547 f->bkt = fold->bkt; 548 } 549 550 err = route4_set_parms(net, tp, base, f, handle, head, tb, 551 tca[TCA_RATE], fold, flags, extack); 552 if (err < 0) 553 goto errout; 554 555 h = from_hash(f->handle >> 16); 556 fp = &f->bkt->ht[h]; 557 for (pfp = rtnl_dereference(*fp); 558 (f1 = rtnl_dereference(*fp)) != NULL; 559 fp = &f1->next) 560 if (f->handle < f1->handle) 561 break; 562 563 tcf_block_netif_keep_dst(tp->chain->block); 564 rcu_assign_pointer(f->next, f1); 565 rcu_assign_pointer(*fp, f); 566 567 if (fold) { 568 b = fold->bkt; 569 h = from_hash(fold->handle >> 16); 570 fp = &b->ht[h]; 571 for (pfp = rtnl_dereference(*fp); pfp; 572 fp = &pfp->next, pfp = rtnl_dereference(*fp)) { 573 if (pfp == fold) { 574 rcu_assign_pointer(*fp, fold->next); 575 if (refcount_dec_and_test(&b->filters_ref)) { 576 unsigned int th = to_hash(fold->handle); 577 578 RCU_INIT_POINTER(head->table[th], NULL); 579 kfree_rcu(b, rcu); 580 } 581 break; 582 } 583 } 584 } 585 586 route4_reset_fastmap(head, fold); 587 *arg = f; 588 if (fold) { 589 tcf_unbind_filter(tp, &fold->res); 590 tcf_exts_get_net(&fold->exts); 591 tcf_queue_work(&fold->rwork, route4_delete_filter_work); 592 } 593 return 0; 594 595 errout: 596 if (f) 597 tcf_exts_destroy(&f->exts); 598 kfree(f); 599 return err; 600 } 601 602 static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg, 603 bool rtnl_held) 604 { 605 struct route4_head *head = rtnl_dereference(tp->root); 606 unsigned int h, h1; 607 608 if (head == NULL || arg->stop) 609 return; 610 611 for (h = 0; h <= 256; h++) { 612 struct route4_bucket *b = rtnl_dereference(head->table[h]); 613 614 if (b) { 615 for (h1 = 0; h1 <= 32; h1++) { 616 struct route4_filter *f; 617 618 for (f = rtnl_dereference(b->ht[h1]); 619 f; 620 f = rtnl_dereference(f->next)) { 621 if (!tc_cls_stats_dump(tp, arg, f)) 622 return; 623 } 624 } 625 } 626 } 627 } 628 629 static int route4_dump(struct net *net, struct tcf_proto *tp, void *fh, 630 struct sk_buff *skb, struct tcmsg *t, bool rtnl_held) 631 { 632 struct route4_filter *f = fh; 633 struct nlattr *nest; 634 u32 id; 635 636 if (f == NULL) 637 return skb->len; 638 639 t->tcm_handle = f->handle; 640 641 nest = nla_nest_start_noflag(skb, TCA_OPTIONS); 642 if (nest == NULL) 643 goto nla_put_failure; 644 645 if (!(f->handle & 0x8000)) { 646 id = f->id & 0xFF; 647 if (nla_put_u32(skb, TCA_ROUTE4_TO, id)) 648 goto nla_put_failure; 649 } 650 if (f->handle & 0x80000000) { 651 if ((f->handle >> 16) != 0xFFFF && 652 nla_put_u32(skb, TCA_ROUTE4_IIF, f->iif)) 653 goto nla_put_failure; 654 } else { 655 id = f->id >> 16; 656 if (nla_put_u32(skb, TCA_ROUTE4_FROM, id)) 657 goto nla_put_failure; 658 } 659 if (f->res.classid && 660 nla_put_u32(skb, TCA_ROUTE4_CLASSID, f->res.classid)) 661 goto nla_put_failure; 662 663 if (tcf_exts_dump(skb, &f->exts) < 0) 664 goto nla_put_failure; 665 666 nla_nest_end(skb, nest); 667 668 if (tcf_exts_dump_stats(skb, &f->exts) < 0) 669 goto nla_put_failure; 670 671 return skb->len; 672 673 nla_put_failure: 674 nla_nest_cancel(skb, nest); 675 return -1; 676 } 677 678 static void route4_bind_class(void *fh, u32 classid, unsigned long cl, void *q, 679 unsigned long base) 680 { 681 struct route4_filter *f = fh; 682 683 tc_cls_bind_class(classid, cl, q, &f->res, base); 684 } 685 686 static struct tcf_proto_ops cls_route4_ops __read_mostly = { 687 .kind = "route", 688 .classify = route4_classify, 689 .init = route4_init, 690 .destroy = route4_destroy, 691 .get = route4_get, 692 .change = route4_change, 693 .delete = route4_delete, 694 .walk = route4_walk, 695 .dump = route4_dump, 696 .bind_class = route4_bind_class, 697 .owner = THIS_MODULE, 698 }; 699 MODULE_ALIAS_NET_CLS("route"); 700 701 static int __init init_route4(void) 702 { 703 return register_tcf_proto_ops(&cls_route4_ops); 704 } 705 706 static void __exit exit_route4(void) 707 { 708 unregister_tcf_proto_ops(&cls_route4_ops); 709 } 710 711 module_init(init_route4) 712 module_exit(exit_route4) 713 MODULE_DESCRIPTION("Routing table realm based TC classifier"); 714 MODULE_LICENSE("GPL"); 715