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