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 (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 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 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 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 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 695 static int __init init_route4(void) 696 { 697 return register_tcf_proto_ops(&cls_route4_ops); 698 } 699 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