1 /* 2 * net/sched/sch_api.c Packet scheduler API. 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 * Fixes: 12 * 13 * Rani Assaf <rani@magic.metawire.com> :980802: JIFFIES and CPU clock sources are repaired. 14 * Eduardo J. Blanco <ejbs@netlabs.com.uy> :990222: kmod support 15 * Jamal Hadi Salim <hadi@nortelnetworks.com>: 990601: ingress support 16 */ 17 18 #include <linux/module.h> 19 #include <linux/types.h> 20 #include <linux/kernel.h> 21 #include <linux/sched.h> 22 #include <linux/string.h> 23 #include <linux/mm.h> 24 #include <linux/socket.h> 25 #include <linux/sockios.h> 26 #include <linux/in.h> 27 #include <linux/errno.h> 28 #include <linux/interrupt.h> 29 #include <linux/netdevice.h> 30 #include <linux/skbuff.h> 31 #include <linux/rtnetlink.h> 32 #include <linux/init.h> 33 #include <linux/proc_fs.h> 34 #include <linux/seq_file.h> 35 #include <linux/kmod.h> 36 #include <linux/list.h> 37 #include <linux/bitops.h> 38 39 #include <net/sock.h> 40 #include <net/pkt_sched.h> 41 42 #include <asm/processor.h> 43 #include <asm/uaccess.h> 44 #include <asm/system.h> 45 46 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n, u32 clid, 47 struct Qdisc *old, struct Qdisc *new); 48 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n, 49 struct Qdisc *q, unsigned long cl, int event); 50 51 /* 52 53 Short review. 54 ------------- 55 56 This file consists of two interrelated parts: 57 58 1. queueing disciplines manager frontend. 59 2. traffic classes manager frontend. 60 61 Generally, queueing discipline ("qdisc") is a black box, 62 which is able to enqueue packets and to dequeue them (when 63 device is ready to send something) in order and at times 64 determined by algorithm hidden in it. 65 66 qdisc's are divided to two categories: 67 - "queues", which have no internal structure visible from outside. 68 - "schedulers", which split all the packets to "traffic classes", 69 using "packet classifiers" (look at cls_api.c) 70 71 In turn, classes may have child qdiscs (as rule, queues) 72 attached to them etc. etc. etc. 73 74 The goal of the routines in this file is to translate 75 information supplied by user in the form of handles 76 to more intelligible for kernel form, to make some sanity 77 checks and part of work, which is common to all qdiscs 78 and to provide rtnetlink notifications. 79 80 All real intelligent work is done inside qdisc modules. 81 82 83 84 Every discipline has two major routines: enqueue and dequeue. 85 86 ---dequeue 87 88 dequeue usually returns a skb to send. It is allowed to return NULL, 89 but it does not mean that queue is empty, it just means that 90 discipline does not want to send anything this time. 91 Queue is really empty if q->q.qlen == 0. 92 For complicated disciplines with multiple queues q->q is not 93 real packet queue, but however q->q.qlen must be valid. 94 95 ---enqueue 96 97 enqueue returns 0, if packet was enqueued successfully. 98 If packet (this one or another one) was dropped, it returns 99 not zero error code. 100 NET_XMIT_DROP - this packet dropped 101 Expected action: do not backoff, but wait until queue will clear. 102 NET_XMIT_CN - probably this packet enqueued, but another one dropped. 103 Expected action: backoff or ignore 104 NET_XMIT_POLICED - dropped by police. 105 Expected action: backoff or error to real-time apps. 106 107 Auxiliary routines: 108 109 ---requeue 110 111 requeues once dequeued packet. It is used for non-standard or 112 just buggy devices, which can defer output even if dev->tbusy=0. 113 114 ---reset 115 116 returns qdisc to initial state: purge all buffers, clear all 117 timers, counters (except for statistics) etc. 118 119 ---init 120 121 initializes newly created qdisc. 122 123 ---destroy 124 125 destroys resources allocated by init and during lifetime of qdisc. 126 127 ---change 128 129 changes qdisc parameters. 130 */ 131 132 /* Protects list of registered TC modules. It is pure SMP lock. */ 133 static DEFINE_RWLOCK(qdisc_mod_lock); 134 135 136 /************************************************ 137 * Queueing disciplines manipulation. * 138 ************************************************/ 139 140 141 /* The list of all installed queueing disciplines. */ 142 143 static struct Qdisc_ops *qdisc_base; 144 145 /* Register/uregister queueing discipline */ 146 147 int register_qdisc(struct Qdisc_ops *qops) 148 { 149 struct Qdisc_ops *q, **qp; 150 int rc = -EEXIST; 151 152 write_lock(&qdisc_mod_lock); 153 for (qp = &qdisc_base; (q = *qp) != NULL; qp = &q->next) 154 if (!strcmp(qops->id, q->id)) 155 goto out; 156 157 if (qops->enqueue == NULL) 158 qops->enqueue = noop_qdisc_ops.enqueue; 159 if (qops->requeue == NULL) 160 qops->requeue = noop_qdisc_ops.requeue; 161 if (qops->dequeue == NULL) 162 qops->dequeue = noop_qdisc_ops.dequeue; 163 164 qops->next = NULL; 165 *qp = qops; 166 rc = 0; 167 out: 168 write_unlock(&qdisc_mod_lock); 169 return rc; 170 } 171 172 int unregister_qdisc(struct Qdisc_ops *qops) 173 { 174 struct Qdisc_ops *q, **qp; 175 int err = -ENOENT; 176 177 write_lock(&qdisc_mod_lock); 178 for (qp = &qdisc_base; (q=*qp)!=NULL; qp = &q->next) 179 if (q == qops) 180 break; 181 if (q) { 182 *qp = q->next; 183 q->next = NULL; 184 err = 0; 185 } 186 write_unlock(&qdisc_mod_lock); 187 return err; 188 } 189 190 /* We know handle. Find qdisc among all qdisc's attached to device 191 (root qdisc, all its children, children of children etc.) 192 */ 193 194 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle) 195 { 196 struct Qdisc *q; 197 198 read_lock_bh(&qdisc_tree_lock); 199 list_for_each_entry(q, &dev->qdisc_list, list) { 200 if (q->handle == handle) { 201 read_unlock_bh(&qdisc_tree_lock); 202 return q; 203 } 204 } 205 read_unlock_bh(&qdisc_tree_lock); 206 return NULL; 207 } 208 209 static struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid) 210 { 211 unsigned long cl; 212 struct Qdisc *leaf; 213 struct Qdisc_class_ops *cops = p->ops->cl_ops; 214 215 if (cops == NULL) 216 return NULL; 217 cl = cops->get(p, classid); 218 219 if (cl == 0) 220 return NULL; 221 leaf = cops->leaf(p, cl); 222 cops->put(p, cl); 223 return leaf; 224 } 225 226 /* Find queueing discipline by name */ 227 228 static struct Qdisc_ops *qdisc_lookup_ops(struct rtattr *kind) 229 { 230 struct Qdisc_ops *q = NULL; 231 232 if (kind) { 233 read_lock(&qdisc_mod_lock); 234 for (q = qdisc_base; q; q = q->next) { 235 if (rtattr_strcmp(kind, q->id) == 0) { 236 if (!try_module_get(q->owner)) 237 q = NULL; 238 break; 239 } 240 } 241 read_unlock(&qdisc_mod_lock); 242 } 243 return q; 244 } 245 246 static struct qdisc_rate_table *qdisc_rtab_list; 247 248 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r, struct rtattr *tab) 249 { 250 struct qdisc_rate_table *rtab; 251 252 for (rtab = qdisc_rtab_list; rtab; rtab = rtab->next) { 253 if (memcmp(&rtab->rate, r, sizeof(struct tc_ratespec)) == 0) { 254 rtab->refcnt++; 255 return rtab; 256 } 257 } 258 259 if (tab == NULL || r->rate == 0 || r->cell_log == 0 || RTA_PAYLOAD(tab) != 1024) 260 return NULL; 261 262 rtab = kmalloc(sizeof(*rtab), GFP_KERNEL); 263 if (rtab) { 264 rtab->rate = *r; 265 rtab->refcnt = 1; 266 memcpy(rtab->data, RTA_DATA(tab), 1024); 267 rtab->next = qdisc_rtab_list; 268 qdisc_rtab_list = rtab; 269 } 270 return rtab; 271 } 272 273 void qdisc_put_rtab(struct qdisc_rate_table *tab) 274 { 275 struct qdisc_rate_table *rtab, **rtabp; 276 277 if (!tab || --tab->refcnt) 278 return; 279 280 for (rtabp = &qdisc_rtab_list; (rtab=*rtabp) != NULL; rtabp = &rtab->next) { 281 if (rtab == tab) { 282 *rtabp = rtab->next; 283 kfree(rtab); 284 return; 285 } 286 } 287 } 288 289 290 /* Allocate an unique handle from space managed by kernel */ 291 292 static u32 qdisc_alloc_handle(struct net_device *dev) 293 { 294 int i = 0x10000; 295 static u32 autohandle = TC_H_MAKE(0x80000000U, 0); 296 297 do { 298 autohandle += TC_H_MAKE(0x10000U, 0); 299 if (autohandle == TC_H_MAKE(TC_H_ROOT, 0)) 300 autohandle = TC_H_MAKE(0x80000000U, 0); 301 } while (qdisc_lookup(dev, autohandle) && --i > 0); 302 303 return i>0 ? autohandle : 0; 304 } 305 306 /* Attach toplevel qdisc to device dev */ 307 308 static struct Qdisc * 309 dev_graft_qdisc(struct net_device *dev, struct Qdisc *qdisc) 310 { 311 struct Qdisc *oqdisc; 312 313 if (dev->flags & IFF_UP) 314 dev_deactivate(dev); 315 316 qdisc_lock_tree(dev); 317 if (qdisc && qdisc->flags&TCQ_F_INGRESS) { 318 oqdisc = dev->qdisc_ingress; 319 /* Prune old scheduler */ 320 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1) { 321 /* delete */ 322 qdisc_reset(oqdisc); 323 dev->qdisc_ingress = NULL; 324 } else { /* new */ 325 dev->qdisc_ingress = qdisc; 326 } 327 328 } else { 329 330 oqdisc = dev->qdisc_sleeping; 331 332 /* Prune old scheduler */ 333 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1) 334 qdisc_reset(oqdisc); 335 336 /* ... and graft new one */ 337 if (qdisc == NULL) 338 qdisc = &noop_qdisc; 339 dev->qdisc_sleeping = qdisc; 340 dev->qdisc = &noop_qdisc; 341 } 342 343 qdisc_unlock_tree(dev); 344 345 if (dev->flags & IFF_UP) 346 dev_activate(dev); 347 348 return oqdisc; 349 } 350 351 352 /* Graft qdisc "new" to class "classid" of qdisc "parent" or 353 to device "dev". 354 355 Old qdisc is not destroyed but returned in *old. 356 */ 357 358 static int qdisc_graft(struct net_device *dev, struct Qdisc *parent, 359 u32 classid, 360 struct Qdisc *new, struct Qdisc **old) 361 { 362 int err = 0; 363 struct Qdisc *q = *old; 364 365 366 if (parent == NULL) { 367 if (q && q->flags&TCQ_F_INGRESS) { 368 *old = dev_graft_qdisc(dev, q); 369 } else { 370 *old = dev_graft_qdisc(dev, new); 371 } 372 } else { 373 struct Qdisc_class_ops *cops = parent->ops->cl_ops; 374 375 err = -EINVAL; 376 377 if (cops) { 378 unsigned long cl = cops->get(parent, classid); 379 if (cl) { 380 err = cops->graft(parent, cl, new, old); 381 if (new) 382 new->parent = classid; 383 cops->put(parent, cl); 384 } 385 } 386 } 387 return err; 388 } 389 390 /* 391 Allocate and initialize new qdisc. 392 393 Parameters are passed via opt. 394 */ 395 396 static struct Qdisc * 397 qdisc_create(struct net_device *dev, u32 handle, struct rtattr **tca, int *errp) 398 { 399 int err; 400 struct rtattr *kind = tca[TCA_KIND-1]; 401 struct Qdisc *sch; 402 struct Qdisc_ops *ops; 403 404 ops = qdisc_lookup_ops(kind); 405 #ifdef CONFIG_KMOD 406 if (ops == NULL && kind != NULL) { 407 char name[IFNAMSIZ]; 408 if (rtattr_strlcpy(name, kind, IFNAMSIZ) < IFNAMSIZ) { 409 /* We dropped the RTNL semaphore in order to 410 * perform the module load. So, even if we 411 * succeeded in loading the module we have to 412 * tell the caller to replay the request. We 413 * indicate this using -EAGAIN. 414 * We replay the request because the device may 415 * go away in the mean time. 416 */ 417 rtnl_unlock(); 418 request_module("sch_%s", name); 419 rtnl_lock(); 420 ops = qdisc_lookup_ops(kind); 421 if (ops != NULL) { 422 /* We will try again qdisc_lookup_ops, 423 * so don't keep a reference. 424 */ 425 module_put(ops->owner); 426 err = -EAGAIN; 427 goto err_out; 428 } 429 } 430 } 431 #endif 432 433 err = -ENOENT; 434 if (ops == NULL) 435 goto err_out; 436 437 sch = qdisc_alloc(dev, ops); 438 if (IS_ERR(sch)) { 439 err = PTR_ERR(sch); 440 goto err_out2; 441 } 442 443 if (handle == TC_H_INGRESS) { 444 sch->flags |= TCQ_F_INGRESS; 445 handle = TC_H_MAKE(TC_H_INGRESS, 0); 446 } else if (handle == 0) { 447 handle = qdisc_alloc_handle(dev); 448 err = -ENOMEM; 449 if (handle == 0) 450 goto err_out3; 451 } 452 453 sch->handle = handle; 454 455 if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS-1])) == 0) { 456 #ifdef CONFIG_NET_ESTIMATOR 457 if (tca[TCA_RATE-1]) { 458 err = gen_new_estimator(&sch->bstats, &sch->rate_est, 459 sch->stats_lock, 460 tca[TCA_RATE-1]); 461 if (err) { 462 /* 463 * Any broken qdiscs that would require 464 * a ops->reset() here? The qdisc was never 465 * in action so it shouldn't be necessary. 466 */ 467 if (ops->destroy) 468 ops->destroy(sch); 469 goto err_out3; 470 } 471 } 472 #endif 473 qdisc_lock_tree(dev); 474 list_add_tail(&sch->list, &dev->qdisc_list); 475 qdisc_unlock_tree(dev); 476 477 return sch; 478 } 479 err_out3: 480 dev_put(dev); 481 kfree((char *) sch - sch->padded); 482 err_out2: 483 module_put(ops->owner); 484 err_out: 485 *errp = err; 486 return NULL; 487 } 488 489 static int qdisc_change(struct Qdisc *sch, struct rtattr **tca) 490 { 491 if (tca[TCA_OPTIONS-1]) { 492 int err; 493 494 if (sch->ops->change == NULL) 495 return -EINVAL; 496 err = sch->ops->change(sch, tca[TCA_OPTIONS-1]); 497 if (err) 498 return err; 499 } 500 #ifdef CONFIG_NET_ESTIMATOR 501 if (tca[TCA_RATE-1]) 502 gen_replace_estimator(&sch->bstats, &sch->rate_est, 503 sch->stats_lock, tca[TCA_RATE-1]); 504 #endif 505 return 0; 506 } 507 508 struct check_loop_arg 509 { 510 struct qdisc_walker w; 511 struct Qdisc *p; 512 int depth; 513 }; 514 515 static int check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w); 516 517 static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth) 518 { 519 struct check_loop_arg arg; 520 521 if (q->ops->cl_ops == NULL) 522 return 0; 523 524 arg.w.stop = arg.w.skip = arg.w.count = 0; 525 arg.w.fn = check_loop_fn; 526 arg.depth = depth; 527 arg.p = p; 528 q->ops->cl_ops->walk(q, &arg.w); 529 return arg.w.stop ? -ELOOP : 0; 530 } 531 532 static int 533 check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w) 534 { 535 struct Qdisc *leaf; 536 struct Qdisc_class_ops *cops = q->ops->cl_ops; 537 struct check_loop_arg *arg = (struct check_loop_arg *)w; 538 539 leaf = cops->leaf(q, cl); 540 if (leaf) { 541 if (leaf == arg->p || arg->depth > 7) 542 return -ELOOP; 543 return check_loop(leaf, arg->p, arg->depth + 1); 544 } 545 return 0; 546 } 547 548 /* 549 * Delete/get qdisc. 550 */ 551 552 static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg) 553 { 554 struct tcmsg *tcm = NLMSG_DATA(n); 555 struct rtattr **tca = arg; 556 struct net_device *dev; 557 u32 clid = tcm->tcm_parent; 558 struct Qdisc *q = NULL; 559 struct Qdisc *p = NULL; 560 int err; 561 562 if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL) 563 return -ENODEV; 564 565 if (clid) { 566 if (clid != TC_H_ROOT) { 567 if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) { 568 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL) 569 return -ENOENT; 570 q = qdisc_leaf(p, clid); 571 } else { /* ingress */ 572 q = dev->qdisc_ingress; 573 } 574 } else { 575 q = dev->qdisc_sleeping; 576 } 577 if (!q) 578 return -ENOENT; 579 580 if (tcm->tcm_handle && q->handle != tcm->tcm_handle) 581 return -EINVAL; 582 } else { 583 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL) 584 return -ENOENT; 585 } 586 587 if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id)) 588 return -EINVAL; 589 590 if (n->nlmsg_type == RTM_DELQDISC) { 591 if (!clid) 592 return -EINVAL; 593 if (q->handle == 0) 594 return -ENOENT; 595 if ((err = qdisc_graft(dev, p, clid, NULL, &q)) != 0) 596 return err; 597 if (q) { 598 qdisc_notify(skb, n, clid, q, NULL); 599 spin_lock_bh(&dev->queue_lock); 600 qdisc_destroy(q); 601 spin_unlock_bh(&dev->queue_lock); 602 } 603 } else { 604 qdisc_notify(skb, n, clid, NULL, q); 605 } 606 return 0; 607 } 608 609 /* 610 Create/change qdisc. 611 */ 612 613 static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg) 614 { 615 struct tcmsg *tcm; 616 struct rtattr **tca; 617 struct net_device *dev; 618 u32 clid; 619 struct Qdisc *q, *p; 620 int err; 621 622 replay: 623 /* Reinit, just in case something touches this. */ 624 tcm = NLMSG_DATA(n); 625 tca = arg; 626 clid = tcm->tcm_parent; 627 q = p = NULL; 628 629 if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL) 630 return -ENODEV; 631 632 if (clid) { 633 if (clid != TC_H_ROOT) { 634 if (clid != TC_H_INGRESS) { 635 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL) 636 return -ENOENT; 637 q = qdisc_leaf(p, clid); 638 } else { /*ingress */ 639 q = dev->qdisc_ingress; 640 } 641 } else { 642 q = dev->qdisc_sleeping; 643 } 644 645 /* It may be default qdisc, ignore it */ 646 if (q && q->handle == 0) 647 q = NULL; 648 649 if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) { 650 if (tcm->tcm_handle) { 651 if (q && !(n->nlmsg_flags&NLM_F_REPLACE)) 652 return -EEXIST; 653 if (TC_H_MIN(tcm->tcm_handle)) 654 return -EINVAL; 655 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL) 656 goto create_n_graft; 657 if (n->nlmsg_flags&NLM_F_EXCL) 658 return -EEXIST; 659 if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id)) 660 return -EINVAL; 661 if (q == p || 662 (p && check_loop(q, p, 0))) 663 return -ELOOP; 664 atomic_inc(&q->refcnt); 665 goto graft; 666 } else { 667 if (q == NULL) 668 goto create_n_graft; 669 670 /* This magic test requires explanation. 671 * 672 * We know, that some child q is already 673 * attached to this parent and have choice: 674 * either to change it or to create/graft new one. 675 * 676 * 1. We are allowed to create/graft only 677 * if CREATE and REPLACE flags are set. 678 * 679 * 2. If EXCL is set, requestor wanted to say, 680 * that qdisc tcm_handle is not expected 681 * to exist, so that we choose create/graft too. 682 * 683 * 3. The last case is when no flags are set. 684 * Alas, it is sort of hole in API, we 685 * cannot decide what to do unambiguously. 686 * For now we select create/graft, if 687 * user gave KIND, which does not match existing. 688 */ 689 if ((n->nlmsg_flags&NLM_F_CREATE) && 690 (n->nlmsg_flags&NLM_F_REPLACE) && 691 ((n->nlmsg_flags&NLM_F_EXCL) || 692 (tca[TCA_KIND-1] && 693 rtattr_strcmp(tca[TCA_KIND-1], q->ops->id)))) 694 goto create_n_graft; 695 } 696 } 697 } else { 698 if (!tcm->tcm_handle) 699 return -EINVAL; 700 q = qdisc_lookup(dev, tcm->tcm_handle); 701 } 702 703 /* Change qdisc parameters */ 704 if (q == NULL) 705 return -ENOENT; 706 if (n->nlmsg_flags&NLM_F_EXCL) 707 return -EEXIST; 708 if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id)) 709 return -EINVAL; 710 err = qdisc_change(q, tca); 711 if (err == 0) 712 qdisc_notify(skb, n, clid, NULL, q); 713 return err; 714 715 create_n_graft: 716 if (!(n->nlmsg_flags&NLM_F_CREATE)) 717 return -ENOENT; 718 if (clid == TC_H_INGRESS) 719 q = qdisc_create(dev, tcm->tcm_parent, tca, &err); 720 else 721 q = qdisc_create(dev, tcm->tcm_handle, tca, &err); 722 if (q == NULL) { 723 if (err == -EAGAIN) 724 goto replay; 725 return err; 726 } 727 728 graft: 729 if (1) { 730 struct Qdisc *old_q = NULL; 731 err = qdisc_graft(dev, p, clid, q, &old_q); 732 if (err) { 733 if (q) { 734 spin_lock_bh(&dev->queue_lock); 735 qdisc_destroy(q); 736 spin_unlock_bh(&dev->queue_lock); 737 } 738 return err; 739 } 740 qdisc_notify(skb, n, clid, old_q, q); 741 if (old_q) { 742 spin_lock_bh(&dev->queue_lock); 743 qdisc_destroy(old_q); 744 spin_unlock_bh(&dev->queue_lock); 745 } 746 } 747 return 0; 748 } 749 750 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid, 751 u32 pid, u32 seq, u16 flags, int event) 752 { 753 struct tcmsg *tcm; 754 struct nlmsghdr *nlh; 755 unsigned char *b = skb->tail; 756 struct gnet_dump d; 757 758 nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags); 759 tcm = NLMSG_DATA(nlh); 760 tcm->tcm_family = AF_UNSPEC; 761 tcm->tcm__pad1 = 0; 762 tcm->tcm__pad2 = 0; 763 tcm->tcm_ifindex = q->dev->ifindex; 764 tcm->tcm_parent = clid; 765 tcm->tcm_handle = q->handle; 766 tcm->tcm_info = atomic_read(&q->refcnt); 767 RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id); 768 if (q->ops->dump && q->ops->dump(q, skb) < 0) 769 goto rtattr_failure; 770 q->qstats.qlen = q->q.qlen; 771 772 if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS, 773 TCA_XSTATS, q->stats_lock, &d) < 0) 774 goto rtattr_failure; 775 776 if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0) 777 goto rtattr_failure; 778 779 if (gnet_stats_copy_basic(&d, &q->bstats) < 0 || 780 #ifdef CONFIG_NET_ESTIMATOR 781 gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 || 782 #endif 783 gnet_stats_copy_queue(&d, &q->qstats) < 0) 784 goto rtattr_failure; 785 786 if (gnet_stats_finish_copy(&d) < 0) 787 goto rtattr_failure; 788 789 nlh->nlmsg_len = skb->tail - b; 790 return skb->len; 791 792 nlmsg_failure: 793 rtattr_failure: 794 skb_trim(skb, b - skb->data); 795 return -1; 796 } 797 798 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n, 799 u32 clid, struct Qdisc *old, struct Qdisc *new) 800 { 801 struct sk_buff *skb; 802 u32 pid = oskb ? NETLINK_CB(oskb).pid : 0; 803 804 skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL); 805 if (!skb) 806 return -ENOBUFS; 807 808 if (old && old->handle) { 809 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0) 810 goto err_out; 811 } 812 if (new) { 813 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0) 814 goto err_out; 815 } 816 817 if (skb->len) 818 return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO); 819 820 err_out: 821 kfree_skb(skb); 822 return -EINVAL; 823 } 824 825 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb) 826 { 827 int idx, q_idx; 828 int s_idx, s_q_idx; 829 struct net_device *dev; 830 struct Qdisc *q; 831 832 s_idx = cb->args[0]; 833 s_q_idx = q_idx = cb->args[1]; 834 read_lock(&dev_base_lock); 835 for (dev=dev_base, idx=0; dev; dev = dev->next, idx++) { 836 if (idx < s_idx) 837 continue; 838 if (idx > s_idx) 839 s_q_idx = 0; 840 read_lock_bh(&qdisc_tree_lock); 841 q_idx = 0; 842 list_for_each_entry(q, &dev->qdisc_list, list) { 843 if (q_idx < s_q_idx) { 844 q_idx++; 845 continue; 846 } 847 if (tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid, 848 cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0) { 849 read_unlock_bh(&qdisc_tree_lock); 850 goto done; 851 } 852 q_idx++; 853 } 854 read_unlock_bh(&qdisc_tree_lock); 855 } 856 857 done: 858 read_unlock(&dev_base_lock); 859 860 cb->args[0] = idx; 861 cb->args[1] = q_idx; 862 863 return skb->len; 864 } 865 866 867 868 /************************************************ 869 * Traffic classes manipulation. * 870 ************************************************/ 871 872 873 874 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg) 875 { 876 struct tcmsg *tcm = NLMSG_DATA(n); 877 struct rtattr **tca = arg; 878 struct net_device *dev; 879 struct Qdisc *q = NULL; 880 struct Qdisc_class_ops *cops; 881 unsigned long cl = 0; 882 unsigned long new_cl; 883 u32 pid = tcm->tcm_parent; 884 u32 clid = tcm->tcm_handle; 885 u32 qid = TC_H_MAJ(clid); 886 int err; 887 888 if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL) 889 return -ENODEV; 890 891 /* 892 parent == TC_H_UNSPEC - unspecified parent. 893 parent == TC_H_ROOT - class is root, which has no parent. 894 parent == X:0 - parent is root class. 895 parent == X:Y - parent is a node in hierarchy. 896 parent == 0:Y - parent is X:Y, where X:0 is qdisc. 897 898 handle == 0:0 - generate handle from kernel pool. 899 handle == 0:Y - class is X:Y, where X:0 is qdisc. 900 handle == X:Y - clear. 901 handle == X:0 - root class. 902 */ 903 904 /* Step 1. Determine qdisc handle X:0 */ 905 906 if (pid != TC_H_ROOT) { 907 u32 qid1 = TC_H_MAJ(pid); 908 909 if (qid && qid1) { 910 /* If both majors are known, they must be identical. */ 911 if (qid != qid1) 912 return -EINVAL; 913 } else if (qid1) { 914 qid = qid1; 915 } else if (qid == 0) 916 qid = dev->qdisc_sleeping->handle; 917 918 /* Now qid is genuine qdisc handle consistent 919 both with parent and child. 920 921 TC_H_MAJ(pid) still may be unspecified, complete it now. 922 */ 923 if (pid) 924 pid = TC_H_MAKE(qid, pid); 925 } else { 926 if (qid == 0) 927 qid = dev->qdisc_sleeping->handle; 928 } 929 930 /* OK. Locate qdisc */ 931 if ((q = qdisc_lookup(dev, qid)) == NULL) 932 return -ENOENT; 933 934 /* An check that it supports classes */ 935 cops = q->ops->cl_ops; 936 if (cops == NULL) 937 return -EINVAL; 938 939 /* Now try to get class */ 940 if (clid == 0) { 941 if (pid == TC_H_ROOT) 942 clid = qid; 943 } else 944 clid = TC_H_MAKE(qid, clid); 945 946 if (clid) 947 cl = cops->get(q, clid); 948 949 if (cl == 0) { 950 err = -ENOENT; 951 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE)) 952 goto out; 953 } else { 954 switch (n->nlmsg_type) { 955 case RTM_NEWTCLASS: 956 err = -EEXIST; 957 if (n->nlmsg_flags&NLM_F_EXCL) 958 goto out; 959 break; 960 case RTM_DELTCLASS: 961 err = cops->delete(q, cl); 962 if (err == 0) 963 tclass_notify(skb, n, q, cl, RTM_DELTCLASS); 964 goto out; 965 case RTM_GETTCLASS: 966 err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS); 967 goto out; 968 default: 969 err = -EINVAL; 970 goto out; 971 } 972 } 973 974 new_cl = cl; 975 err = cops->change(q, clid, pid, tca, &new_cl); 976 if (err == 0) 977 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS); 978 979 out: 980 if (cl) 981 cops->put(q, cl); 982 983 return err; 984 } 985 986 987 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q, 988 unsigned long cl, 989 u32 pid, u32 seq, u16 flags, int event) 990 { 991 struct tcmsg *tcm; 992 struct nlmsghdr *nlh; 993 unsigned char *b = skb->tail; 994 struct gnet_dump d; 995 struct Qdisc_class_ops *cl_ops = q->ops->cl_ops; 996 997 nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags); 998 tcm = NLMSG_DATA(nlh); 999 tcm->tcm_family = AF_UNSPEC; 1000 tcm->tcm_ifindex = q->dev->ifindex; 1001 tcm->tcm_parent = q->handle; 1002 tcm->tcm_handle = q->handle; 1003 tcm->tcm_info = 0; 1004 RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id); 1005 if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0) 1006 goto rtattr_failure; 1007 1008 if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS, 1009 TCA_XSTATS, q->stats_lock, &d) < 0) 1010 goto rtattr_failure; 1011 1012 if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0) 1013 goto rtattr_failure; 1014 1015 if (gnet_stats_finish_copy(&d) < 0) 1016 goto rtattr_failure; 1017 1018 nlh->nlmsg_len = skb->tail - b; 1019 return skb->len; 1020 1021 nlmsg_failure: 1022 rtattr_failure: 1023 skb_trim(skb, b - skb->data); 1024 return -1; 1025 } 1026 1027 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n, 1028 struct Qdisc *q, unsigned long cl, int event) 1029 { 1030 struct sk_buff *skb; 1031 u32 pid = oskb ? NETLINK_CB(oskb).pid : 0; 1032 1033 skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL); 1034 if (!skb) 1035 return -ENOBUFS; 1036 1037 if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) { 1038 kfree_skb(skb); 1039 return -EINVAL; 1040 } 1041 1042 return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO); 1043 } 1044 1045 struct qdisc_dump_args 1046 { 1047 struct qdisc_walker w; 1048 struct sk_buff *skb; 1049 struct netlink_callback *cb; 1050 }; 1051 1052 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg) 1053 { 1054 struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg; 1055 1056 return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid, 1057 a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS); 1058 } 1059 1060 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb) 1061 { 1062 int t; 1063 int s_t; 1064 struct net_device *dev; 1065 struct Qdisc *q; 1066 struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh); 1067 struct qdisc_dump_args arg; 1068 1069 if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm))) 1070 return 0; 1071 if ((dev = dev_get_by_index(tcm->tcm_ifindex)) == NULL) 1072 return 0; 1073 1074 s_t = cb->args[0]; 1075 t = 0; 1076 1077 read_lock_bh(&qdisc_tree_lock); 1078 list_for_each_entry(q, &dev->qdisc_list, list) { 1079 if (t < s_t || !q->ops->cl_ops || 1080 (tcm->tcm_parent && 1081 TC_H_MAJ(tcm->tcm_parent) != q->handle)) { 1082 t++; 1083 continue; 1084 } 1085 if (t > s_t) 1086 memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0])); 1087 arg.w.fn = qdisc_class_dump; 1088 arg.skb = skb; 1089 arg.cb = cb; 1090 arg.w.stop = 0; 1091 arg.w.skip = cb->args[1]; 1092 arg.w.count = 0; 1093 q->ops->cl_ops->walk(q, &arg.w); 1094 cb->args[1] = arg.w.count; 1095 if (arg.w.stop) 1096 break; 1097 t++; 1098 } 1099 read_unlock_bh(&qdisc_tree_lock); 1100 1101 cb->args[0] = t; 1102 1103 dev_put(dev); 1104 return skb->len; 1105 } 1106 1107 /* Main classifier routine: scans classifier chain attached 1108 to this qdisc, (optionally) tests for protocol and asks 1109 specific classifiers. 1110 */ 1111 int tc_classify(struct sk_buff *skb, struct tcf_proto *tp, 1112 struct tcf_result *res) 1113 { 1114 int err = 0; 1115 u32 protocol = skb->protocol; 1116 #ifdef CONFIG_NET_CLS_ACT 1117 struct tcf_proto *otp = tp; 1118 reclassify: 1119 #endif 1120 protocol = skb->protocol; 1121 1122 for ( ; tp; tp = tp->next) { 1123 if ((tp->protocol == protocol || 1124 tp->protocol == __constant_htons(ETH_P_ALL)) && 1125 (err = tp->classify(skb, tp, res)) >= 0) { 1126 #ifdef CONFIG_NET_CLS_ACT 1127 if ( TC_ACT_RECLASSIFY == err) { 1128 __u32 verd = (__u32) G_TC_VERD(skb->tc_verd); 1129 tp = otp; 1130 1131 if (MAX_REC_LOOP < verd++) { 1132 printk("rule prio %d protocol %02x reclassify is buggy packet dropped\n", 1133 tp->prio&0xffff, ntohs(tp->protocol)); 1134 return TC_ACT_SHOT; 1135 } 1136 skb->tc_verd = SET_TC_VERD(skb->tc_verd,verd); 1137 goto reclassify; 1138 } else { 1139 if (skb->tc_verd) 1140 skb->tc_verd = SET_TC_VERD(skb->tc_verd,0); 1141 return err; 1142 } 1143 #else 1144 1145 return err; 1146 #endif 1147 } 1148 1149 } 1150 return -1; 1151 } 1152 1153 static int psched_us_per_tick = 1; 1154 static int psched_tick_per_us = 1; 1155 1156 #ifdef CONFIG_PROC_FS 1157 static int psched_show(struct seq_file *seq, void *v) 1158 { 1159 seq_printf(seq, "%08x %08x %08x %08x\n", 1160 psched_tick_per_us, psched_us_per_tick, 1161 1000000, HZ); 1162 1163 return 0; 1164 } 1165 1166 static int psched_open(struct inode *inode, struct file *file) 1167 { 1168 return single_open(file, psched_show, PDE(inode)->data); 1169 } 1170 1171 static struct file_operations psched_fops = { 1172 .owner = THIS_MODULE, 1173 .open = psched_open, 1174 .read = seq_read, 1175 .llseek = seq_lseek, 1176 .release = single_release, 1177 }; 1178 #endif 1179 1180 #ifdef CONFIG_NET_SCH_CLK_CPU 1181 psched_tdiff_t psched_clock_per_hz; 1182 int psched_clock_scale; 1183 EXPORT_SYMBOL(psched_clock_per_hz); 1184 EXPORT_SYMBOL(psched_clock_scale); 1185 1186 psched_time_t psched_time_base; 1187 cycles_t psched_time_mark; 1188 EXPORT_SYMBOL(psched_time_mark); 1189 EXPORT_SYMBOL(psched_time_base); 1190 1191 /* 1192 * Periodically adjust psched_time_base to avoid overflow 1193 * with 32-bit get_cycles(). Safe up to 4GHz CPU. 1194 */ 1195 static void psched_tick(unsigned long); 1196 static DEFINE_TIMER(psched_timer, psched_tick, 0, 0); 1197 1198 static void psched_tick(unsigned long dummy) 1199 { 1200 if (sizeof(cycles_t) == sizeof(u32)) { 1201 psched_time_t dummy_stamp; 1202 PSCHED_GET_TIME(dummy_stamp); 1203 psched_timer.expires = jiffies + 1*HZ; 1204 add_timer(&psched_timer); 1205 } 1206 } 1207 1208 int __init psched_calibrate_clock(void) 1209 { 1210 psched_time_t stamp, stamp1; 1211 struct timeval tv, tv1; 1212 psched_tdiff_t delay; 1213 long rdelay; 1214 unsigned long stop; 1215 1216 psched_tick(0); 1217 stop = jiffies + HZ/10; 1218 PSCHED_GET_TIME(stamp); 1219 do_gettimeofday(&tv); 1220 while (time_before(jiffies, stop)) { 1221 barrier(); 1222 cpu_relax(); 1223 } 1224 PSCHED_GET_TIME(stamp1); 1225 do_gettimeofday(&tv1); 1226 1227 delay = PSCHED_TDIFF(stamp1, stamp); 1228 rdelay = tv1.tv_usec - tv.tv_usec; 1229 rdelay += (tv1.tv_sec - tv.tv_sec)*1000000; 1230 if (rdelay > delay) 1231 return -1; 1232 delay /= rdelay; 1233 psched_tick_per_us = delay; 1234 while ((delay>>=1) != 0) 1235 psched_clock_scale++; 1236 psched_us_per_tick = 1<<psched_clock_scale; 1237 psched_clock_per_hz = (psched_tick_per_us*(1000000/HZ))>>psched_clock_scale; 1238 return 0; 1239 } 1240 #endif 1241 1242 static int __init pktsched_init(void) 1243 { 1244 struct rtnetlink_link *link_p; 1245 1246 #ifdef CONFIG_NET_SCH_CLK_CPU 1247 if (psched_calibrate_clock() < 0) 1248 return -1; 1249 #elif defined(CONFIG_NET_SCH_CLK_JIFFIES) 1250 psched_tick_per_us = HZ<<PSCHED_JSCALE; 1251 psched_us_per_tick = 1000000; 1252 #endif 1253 1254 link_p = rtnetlink_links[PF_UNSPEC]; 1255 1256 /* Setup rtnetlink links. It is made here to avoid 1257 exporting large number of public symbols. 1258 */ 1259 1260 if (link_p) { 1261 link_p[RTM_NEWQDISC-RTM_BASE].doit = tc_modify_qdisc; 1262 link_p[RTM_DELQDISC-RTM_BASE].doit = tc_get_qdisc; 1263 link_p[RTM_GETQDISC-RTM_BASE].doit = tc_get_qdisc; 1264 link_p[RTM_GETQDISC-RTM_BASE].dumpit = tc_dump_qdisc; 1265 link_p[RTM_NEWTCLASS-RTM_BASE].doit = tc_ctl_tclass; 1266 link_p[RTM_DELTCLASS-RTM_BASE].doit = tc_ctl_tclass; 1267 link_p[RTM_GETTCLASS-RTM_BASE].doit = tc_ctl_tclass; 1268 link_p[RTM_GETTCLASS-RTM_BASE].dumpit = tc_dump_tclass; 1269 } 1270 1271 register_qdisc(&pfifo_qdisc_ops); 1272 register_qdisc(&bfifo_qdisc_ops); 1273 proc_net_fops_create("psched", 0, &psched_fops); 1274 1275 return 0; 1276 } 1277 1278 subsys_initcall(pktsched_init); 1279 1280 EXPORT_SYMBOL(qdisc_lookup); 1281 EXPORT_SYMBOL(qdisc_get_rtab); 1282 EXPORT_SYMBOL(qdisc_put_rtab); 1283 EXPORT_SYMBOL(register_qdisc); 1284 EXPORT_SYMBOL(unregister_qdisc); 1285 EXPORT_SYMBOL(tc_classify); 1286