net/sched/sch_api.c

   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/string.h>
  22 #include <linux/mm.h>
  23 #include <linux/socket.h>
  24 #include <linux/sockios.h>
  25 #include <linux/in.h>
  26 #include <linux/errno.h>
  27 #include <linux/interrupt.h>
  28 #include <linux/netdevice.h>
  29 #include <linux/skbuff.h>
  30 #include <linux/init.h>
  31 #include <linux/proc_fs.h>
  32 #include <linux/seq_file.h>
  33 #include <linux/kmod.h>
  34 #include <linux/list.h>
  35 #include <linux/bitops.h>
  36 #include <linux/hrtimer.h>
  37
  38 #include <net/netlink.h>
  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 static struct Qdisc *__qdisc_lookup(struct net_device *dev, u32 handle)
 195 {
 196         struct Qdisc *q;
 197
 198         list_for_each_entry(q, &dev->qdisc_list, list) {
 199                 if (q->handle == handle)
 200                         return q;
 201         }
 202         return NULL;
 203 }
 204
 205 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
 206 {
 207         struct Qdisc *q;
 208
 209         read_lock(&qdisc_tree_lock);
 210         q = __qdisc_lookup(dev, handle);
 211         read_unlock(&qdisc_tree_lock);
 212         return q;
 213 }
 214
 215 static struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid)
 216 {
 217         unsigned long cl;
 218         struct Qdisc *leaf;
 219         struct Qdisc_class_ops *cops = p->ops->cl_ops;
 220
 221         if (cops == NULL)
 222                 return NULL;
 223         cl = cops->get(p, classid);
 224
 225         if (cl == 0)
 226                 return NULL;
 227         leaf = cops->leaf(p, cl);
 228         cops->put(p, cl);
 229         return leaf;
 230 }
 231
 232 /* Find queueing discipline by name */
 233
 234 static struct Qdisc_ops *qdisc_lookup_ops(struct rtattr *kind)
 235 {
 236         struct Qdisc_ops *q = NULL;
 237
 238         if (kind) {
 239                 read_lock(&qdisc_mod_lock);
 240                 for (q = qdisc_base; q; q = q->next) {
 241                         if (rtattr_strcmp(kind, q->id) == 0) {
 242                                 if (!try_module_get(q->owner))
 243                                         q = NULL;
 244                                 break;
 245                         }
 246                 }
 247                 read_unlock(&qdisc_mod_lock);
 248         }
 249         return q;
 250 }
 251
 252 static struct qdisc_rate_table *qdisc_rtab_list;
 253
 254 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r, struct rtattr *tab)
 255 {
 256         struct qdisc_rate_table *rtab;
 257
 258         for (rtab = qdisc_rtab_list; rtab; rtab = rtab->next) {
 259                 if (memcmp(&rtab->rate, r, sizeof(struct tc_ratespec)) == 0) {
 260                         rtab->refcnt++;
 261                         return rtab;
 262                 }
 263         }
 264
 265         if (tab == NULL || r->rate == 0 || r->cell_log == 0 || RTA_PAYLOAD(tab) != 1024)
 266                 return NULL;
 267
 268         rtab = kmalloc(sizeof(*rtab), GFP_KERNEL);
 269         if (rtab) {
 270                 rtab->rate = *r;
 271                 rtab->refcnt = 1;
 272                 memcpy(rtab->data, RTA_DATA(tab), 1024);
 273                 rtab->next = qdisc_rtab_list;
 274                 qdisc_rtab_list = rtab;
 275         }
 276         return rtab;
 277 }
 278
 279 void qdisc_put_rtab(struct qdisc_rate_table *tab)
 280 {
 281         struct qdisc_rate_table *rtab, **rtabp;
 282
 283         if (!tab || --tab->refcnt)
 284                 return;
 285
 286         for (rtabp = &qdisc_rtab_list; (rtab=*rtabp) != NULL; rtabp = &rtab->next) {
 287                 if (rtab == tab) {
 288                         *rtabp = rtab->next;
 289                         kfree(rtab);
 290                         return;
 291                 }
 292         }
 293 }
 294
 295 static enum hrtimer_restart qdisc_watchdog(struct hrtimer *timer)
 296 {
 297         struct qdisc_watchdog *wd = container_of(timer, struct qdisc_watchdog,
 298                                                  timer);
 299
 300         wd->qdisc->flags &= ~TCQ_F_THROTTLED;
 301         netif_schedule(wd->qdisc->dev);
 302         return HRTIMER_NORESTART;
 303 }
 304
 305 void qdisc_watchdog_init(struct qdisc_watchdog *wd, struct Qdisc *qdisc)
 306 {
 307         hrtimer_init(&wd->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
 308         wd->timer.function = qdisc_watchdog;
 309         wd->qdisc = qdisc;
 310 }
 311 EXPORT_SYMBOL(qdisc_watchdog_init);
 312
 313 void qdisc_watchdog_schedule(struct qdisc_watchdog *wd, psched_time_t expires)
 314 {
 315         ktime_t time;
 316
 317         wd->qdisc->flags |= TCQ_F_THROTTLED;
 318         time = ktime_set(0, 0);
 319         time = ktime_add_ns(time, PSCHED_US2NS(expires));
 320         hrtimer_start(&wd->timer, time, HRTIMER_MODE_ABS);
 321 }
 322 EXPORT_SYMBOL(qdisc_watchdog_schedule);
 323
 324 void qdisc_watchdog_cancel(struct qdisc_watchdog *wd)
 325 {
 326         hrtimer_cancel(&wd->timer);
 327         wd->qdisc->flags &= ~TCQ_F_THROTTLED;
 328 }
 329 EXPORT_SYMBOL(qdisc_watchdog_cancel);
 330
 331 /* Allocate an unique handle from space managed by kernel */
 332
 333 static u32 qdisc_alloc_handle(struct net_device *dev)
 334 {
 335         int i = 0x10000;
 336         static u32 autohandle = TC_H_MAKE(0x80000000U, 0);
 337
 338         do {
 339                 autohandle += TC_H_MAKE(0x10000U, 0);
 340                 if (autohandle == TC_H_MAKE(TC_H_ROOT, 0))
 341                         autohandle = TC_H_MAKE(0x80000000U, 0);
 342         } while (qdisc_lookup(dev, autohandle) && --i > 0);
 343
 344         return i>0 ? autohandle : 0;
 345 }
 346
 347 /* Attach toplevel qdisc to device dev */
 348
 349 static struct Qdisc *
 350 dev_graft_qdisc(struct net_device *dev, struct Qdisc *qdisc)
 351 {
 352         struct Qdisc *oqdisc;
 353
 354         if (dev->flags & IFF_UP)
 355                 dev_deactivate(dev);
 356
 357         qdisc_lock_tree(dev);
 358         if (qdisc && qdisc->flags&TCQ_F_INGRESS) {
 359                 oqdisc = dev->qdisc_ingress;
 360                 /* Prune old scheduler */
 361                 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1) {
 362                         /* delete */
 363                         qdisc_reset(oqdisc);
 364                         dev->qdisc_ingress = NULL;
 365                 } else {  /* new */
 366                         dev->qdisc_ingress = qdisc;
 367                 }
 368
 369         } else {
 370
 371                 oqdisc = dev->qdisc_sleeping;
 372
 373                 /* Prune old scheduler */
 374                 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1)
 375                         qdisc_reset(oqdisc);
 376
 377                 /* ... and graft new one */
 378                 if (qdisc == NULL)
 379                         qdisc = &noop_qdisc;
 380                 dev->qdisc_sleeping = qdisc;
 381                 dev->qdisc = &noop_qdisc;
 382         }
 383
 384         qdisc_unlock_tree(dev);
 385
 386         if (dev->flags & IFF_UP)
 387                 dev_activate(dev);
 388
 389         return oqdisc;
 390 }
 391
 392 void qdisc_tree_decrease_qlen(struct Qdisc *sch, unsigned int n)
 393 {
 394         struct Qdisc_class_ops *cops;
 395         unsigned long cl;
 396         u32 parentid;
 397
 398         if (n == 0)
 399                 return;
 400         while ((parentid = sch->parent)) {
 401                 sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
 402                 cops = sch->ops->cl_ops;
 403                 if (cops->qlen_notify) {
 404                         cl = cops->get(sch, parentid);
 405                         cops->qlen_notify(sch, cl);
 406                         cops->put(sch, cl);
 407                 }
 408                 sch->q.qlen -= n;
 409         }
 410 }
 411 EXPORT_SYMBOL(qdisc_tree_decrease_qlen);
 412
 413 /* Graft qdisc "new" to class "classid" of qdisc "parent" or
 414    to device "dev".
 415
 416    Old qdisc is not destroyed but returned in *old.
 417  */
 418
 419 static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 420                        u32 classid,
 421                        struct Qdisc *new, struct Qdisc **old)
 422 {
 423         int err = 0;
 424         struct Qdisc *q = *old;
 425
 426
 427         if (parent == NULL) {
 428                 if (q && q->flags&TCQ_F_INGRESS) {
 429                         *old = dev_graft_qdisc(dev, q);
 430                 } else {
 431                         *old = dev_graft_qdisc(dev, new);
 432                 }
 433         } else {
 434                 struct Qdisc_class_ops *cops = parent->ops->cl_ops;
 435
 436                 err = -EINVAL;
 437
 438                 if (cops) {
 439                         unsigned long cl = cops->get(parent, classid);
 440                         if (cl) {
 441                                 err = cops->graft(parent, cl, new, old);
 442                                 if (new)
 443                                         new->parent = classid;
 444                                 cops->put(parent, cl);
 445                         }
 446                 }
 447         }
 448         return err;
 449 }
 450
 451 /*
 452    Allocate and initialize new qdisc.
 453
 454    Parameters are passed via opt.
 455  */
 456
 457 static struct Qdisc *
 458 qdisc_create(struct net_device *dev, u32 handle, struct rtattr **tca, int *errp)
 459 {
 460         int err;
 461         struct rtattr *kind = tca[TCA_KIND-1];
 462         struct Qdisc *sch;
 463         struct Qdisc_ops *ops;
 464
 465         ops = qdisc_lookup_ops(kind);
 466 #ifdef CONFIG_KMOD
 467         if (ops == NULL && kind != NULL) {
 468                 char name[IFNAMSIZ];
 469                 if (rtattr_strlcpy(name, kind, IFNAMSIZ) < IFNAMSIZ) {
 470                         /* We dropped the RTNL semaphore in order to
 471                          * perform the module load.  So, even if we
 472                          * succeeded in loading the module we have to
 473                          * tell the caller to replay the request.  We
 474                          * indicate this using -EAGAIN.
 475                          * We replay the request because the device may
 476                          * go away in the mean time.
 477                          */
 478                         rtnl_unlock();
 479                         request_module("sch_%s", name);
 480                         rtnl_lock();
 481                         ops = qdisc_lookup_ops(kind);
 482                         if (ops != NULL) {
 483                                 /* We will try again qdisc_lookup_ops,
 484                                  * so don't keep a reference.
 485                                  */
 486                                 module_put(ops->owner);
 487                                 err = -EAGAIN;
 488                                 goto err_out;
 489                         }
 490                 }
 491         }
 492 #endif
 493
 494         err = -ENOENT;
 495         if (ops == NULL)
 496                 goto err_out;
 497
 498         sch = qdisc_alloc(dev, ops);
 499         if (IS_ERR(sch)) {
 500                 err = PTR_ERR(sch);
 501                 goto err_out2;
 502         }
 503
 504         if (handle == TC_H_INGRESS) {
 505                 sch->flags |= TCQ_F_INGRESS;
 506                 handle = TC_H_MAKE(TC_H_INGRESS, 0);
 507         } else if (handle == 0) {
 508                 handle = qdisc_alloc_handle(dev);
 509                 err = -ENOMEM;
 510                 if (handle == 0)
 511                         goto err_out3;
 512         }
 513
 514         sch->handle = handle;
 515
 516         if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS-1])) == 0) {
 517 #ifdef CONFIG_NET_ESTIMATOR
 518                 if (tca[TCA_RATE-1]) {
 519                         err = gen_new_estimator(&sch->bstats, &sch->rate_est,
 520                                                 sch->stats_lock,
 521                                                 tca[TCA_RATE-1]);
 522                         if (err) {
 523                                 /*
 524                                  * Any broken qdiscs that would require
 525                                  * a ops->reset() here? The qdisc was never
 526                                  * in action so it shouldn't be necessary.
 527                                  */
 528                                 if (ops->destroy)
 529                                         ops->destroy(sch);
 530                                 goto err_out3;
 531                         }
 532                 }
 533 #endif
 534                 qdisc_lock_tree(dev);
 535                 list_add_tail(&sch->list, &dev->qdisc_list);
 536                 qdisc_unlock_tree(dev);
 537
 538                 return sch;
 539         }
 540 err_out3:
 541         dev_put(dev);
 542         kfree((char *) sch - sch->padded);
 543 err_out2:
 544         module_put(ops->owner);
 545 err_out:
 546         *errp = err;
 547         return NULL;
 548 }
 549
 550 static int qdisc_change(struct Qdisc *sch, struct rtattr **tca)
 551 {
 552         if (tca[TCA_OPTIONS-1]) {
 553                 int err;
 554
 555                 if (sch->ops->change == NULL)
 556                         return -EINVAL;
 557                 err = sch->ops->change(sch, tca[TCA_OPTIONS-1]);
 558                 if (err)
 559                         return err;
 560         }
 561 #ifdef CONFIG_NET_ESTIMATOR
 562         if (tca[TCA_RATE-1])
 563                 gen_replace_estimator(&sch->bstats, &sch->rate_est,
 564                         sch->stats_lock, tca[TCA_RATE-1]);
 565 #endif
 566         return 0;
 567 }
 568
 569 struct check_loop_arg
 570 {
 571         struct qdisc_walker     w;
 572         struct Qdisc            *p;
 573         int                     depth;
 574 };
 575
 576 static int check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w);
 577
 578 static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth)
 579 {
 580         struct check_loop_arg   arg;
 581
 582         if (q->ops->cl_ops == NULL)
 583                 return 0;
 584
 585         arg.w.stop = arg.w.skip = arg.w.count = 0;
 586         arg.w.fn = check_loop_fn;
 587         arg.depth = depth;
 588         arg.p = p;
 589         q->ops->cl_ops->walk(q, &arg.w);
 590         return arg.w.stop ? -ELOOP : 0;
 591 }
 592
 593 static int
 594 check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w)
 595 {
 596         struct Qdisc *leaf;
 597         struct Qdisc_class_ops *cops = q->ops->cl_ops;
 598         struct check_loop_arg *arg = (struct check_loop_arg *)w;
 599
 600         leaf = cops->leaf(q, cl);
 601         if (leaf) {
 602                 if (leaf == arg->p || arg->depth > 7)
 603                         return -ELOOP;
 604                 return check_loop(leaf, arg->p, arg->depth + 1);
 605         }
 606         return 0;
 607 }
 608
 609 /*
 610  * Delete/get qdisc.
 611  */
 612
 613 static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 614 {
 615         struct tcmsg *tcm = NLMSG_DATA(n);
 616         struct rtattr **tca = arg;
 617         struct net_device *dev;
 618         u32 clid = tcm->tcm_parent;
 619         struct Qdisc *q = NULL;
 620         struct Qdisc *p = NULL;
 621         int err;
 622
 623         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 624                 return -ENODEV;
 625
 626         if (clid) {
 627                 if (clid != TC_H_ROOT) {
 628                         if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) {
 629                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
 630                                         return -ENOENT;
 631                                 q = qdisc_leaf(p, clid);
 632                         } else { /* ingress */
 633                                 q = dev->qdisc_ingress;
 634                         }
 635                 } else {
 636                         q = dev->qdisc_sleeping;
 637                 }
 638                 if (!q)
 639                         return -ENOENT;
 640
 641                 if (tcm->tcm_handle && q->handle != tcm->tcm_handle)
 642                         return -EINVAL;
 643         } else {
 644                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
 645                         return -ENOENT;
 646         }
 647
 648         if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
 649                 return -EINVAL;
 650
 651         if (n->nlmsg_type == RTM_DELQDISC) {
 652                 if (!clid)
 653                         return -EINVAL;
 654                 if (q->handle == 0)
 655                         return -ENOENT;
 656                 if ((err = qdisc_graft(dev, p, clid, NULL, &q)) != 0)
 657                         return err;
 658                 if (q) {
 659                         qdisc_notify(skb, n, clid, q, NULL);
 660                         spin_lock_bh(&dev->queue_lock);
 661                         qdisc_destroy(q);
 662                         spin_unlock_bh(&dev->queue_lock);
 663                 }
 664         } else {
 665                 qdisc_notify(skb, n, clid, NULL, q);
 666         }
 667         return 0;
 668 }
 669
 670 /*
 671    Create/change qdisc.
 672  */
 673
 674 static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 675 {
 676         struct tcmsg *tcm;
 677         struct rtattr **tca;
 678         struct net_device *dev;
 679         u32 clid;
 680         struct Qdisc *q, *p;
 681         int err;
 682
 683 replay:
 684         /* Reinit, just in case something touches this. */
 685         tcm = NLMSG_DATA(n);
 686         tca = arg;
 687         clid = tcm->tcm_parent;
 688         q = p = NULL;
 689
 690         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 691                 return -ENODEV;
 692
 693         if (clid) {
 694                 if (clid != TC_H_ROOT) {
 695                         if (clid != TC_H_INGRESS) {
 696                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
 697                                         return -ENOENT;
 698                                 q = qdisc_leaf(p, clid);
 699                         } else { /*ingress */
 700                                 q = dev->qdisc_ingress;
 701                         }
 702                 } else {
 703                         q = dev->qdisc_sleeping;
 704                 }
 705
 706                 /* It may be default qdisc, ignore it */
 707                 if (q && q->handle == 0)
 708                         q = NULL;
 709
 710                 if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) {
 711                         if (tcm->tcm_handle) {
 712                                 if (q && !(n->nlmsg_flags&NLM_F_REPLACE))
 713                                         return -EEXIST;
 714                                 if (TC_H_MIN(tcm->tcm_handle))
 715                                         return -EINVAL;
 716                                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
 717                                         goto create_n_graft;
 718                                 if (n->nlmsg_flags&NLM_F_EXCL)
 719                                         return -EEXIST;
 720                                 if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
 721                                         return -EINVAL;
 722                                 if (q == p ||
 723                                     (p && check_loop(q, p, 0)))
 724                                         return -ELOOP;
 725                                 atomic_inc(&q->refcnt);
 726                                 goto graft;
 727                         } else {
 728                                 if (q == NULL)
 729                                         goto create_n_graft;
 730
 731                                 /* This magic test requires explanation.
 732                                  *
 733                                  *   We know, that some child q is already
 734                                  *   attached to this parent and have choice:
 735                                  *   either to change it or to create/graft new one.
 736                                  *
 737                                  *   1. We are allowed to create/graft only
 738                                  *   if CREATE and REPLACE flags are set.
 739                                  *
 740                                  *   2. If EXCL is set, requestor wanted to say,
 741                                  *   that qdisc tcm_handle is not expected
 742                                  *   to exist, so that we choose create/graft too.
 743                                  *
 744                                  *   3. The last case is when no flags are set.
 745                                  *   Alas, it is sort of hole in API, we
 746                                  *   cannot decide what to do unambiguously.
 747                                  *   For now we select create/graft, if
 748                                  *   user gave KIND, which does not match existing.
 749                                  */
 750                                 if ((n->nlmsg_flags&NLM_F_CREATE) &&
 751                                     (n->nlmsg_flags&NLM_F_REPLACE) &&
 752                                     ((n->nlmsg_flags&NLM_F_EXCL) ||
 753                                      (tca[TCA_KIND-1] &&
 754                                       rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))))
 755                                         goto create_n_graft;
 756                         }
 757                 }
 758         } else {
 759                 if (!tcm->tcm_handle)
 760                         return -EINVAL;
 761                 q = qdisc_lookup(dev, tcm->tcm_handle);
 762         }
 763
 764         /* Change qdisc parameters */
 765         if (q == NULL)
 766                 return -ENOENT;
 767         if (n->nlmsg_flags&NLM_F_EXCL)
 768                 return -EEXIST;
 769         if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
 770                 return -EINVAL;
 771         err = qdisc_change(q, tca);
 772         if (err == 0)
 773                 qdisc_notify(skb, n, clid, NULL, q);
 774         return err;
 775
 776 create_n_graft:
 777         if (!(n->nlmsg_flags&NLM_F_CREATE))
 778                 return -ENOENT;
 779         if (clid == TC_H_INGRESS)
 780                 q = qdisc_create(dev, tcm->tcm_parent, tca, &err);
 781         else
 782                 q = qdisc_create(dev, tcm->tcm_handle, tca, &err);
 783         if (q == NULL) {
 784                 if (err == -EAGAIN)
 785                         goto replay;
 786                 return err;
 787         }
 788
 789 graft:
 790         if (1) {
 791                 struct Qdisc *old_q = NULL;
 792                 err = qdisc_graft(dev, p, clid, q, &old_q);
 793                 if (err) {
 794                         if (q) {
 795                                 spin_lock_bh(&dev->queue_lock);
 796                                 qdisc_destroy(q);
 797                                 spin_unlock_bh(&dev->queue_lock);
 798                         }
 799                         return err;
 800                 }
 801                 qdisc_notify(skb, n, clid, old_q, q);
 802                 if (old_q) {
 803                         spin_lock_bh(&dev->queue_lock);
 804                         qdisc_destroy(old_q);
 805                         spin_unlock_bh(&dev->queue_lock);
 806                 }
 807         }
 808         return 0;
 809 }
 810
 811 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
 812                          u32 pid, u32 seq, u16 flags, int event)
 813 {
 814         struct tcmsg *tcm;
 815         struct nlmsghdr  *nlh;
 816         unsigned char *b = skb_tail_pointer(skb);
 817         struct gnet_dump d;
 818
 819         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
 820         tcm = NLMSG_DATA(nlh);
 821         tcm->tcm_family = AF_UNSPEC;
 822         tcm->tcm__pad1 = 0;
 823         tcm->tcm__pad2 = 0;
 824         tcm->tcm_ifindex = q->dev->ifindex;
 825         tcm->tcm_parent = clid;
 826         tcm->tcm_handle = q->handle;
 827         tcm->tcm_info = atomic_read(&q->refcnt);
 828         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
 829         if (q->ops->dump && q->ops->dump(q, skb) < 0)
 830                 goto rtattr_failure;
 831         q->qstats.qlen = q->q.qlen;
 832
 833         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
 834                         TCA_XSTATS, q->stats_lock, &d) < 0)
 835                 goto rtattr_failure;
 836
 837         if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0)
 838                 goto rtattr_failure;
 839
 840         if (gnet_stats_copy_basic(&d, &q->bstats) < 0 ||
 841 #ifdef CONFIG_NET_ESTIMATOR
 842             gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 ||
 843 #endif
 844             gnet_stats_copy_queue(&d, &q->qstats) < 0)
 845                 goto rtattr_failure;
 846
 847         if (gnet_stats_finish_copy(&d) < 0)
 848                 goto rtattr_failure;
 849
 850         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
 851         return skb->len;
 852
 853 nlmsg_failure:
 854 rtattr_failure:
 855         nlmsg_trim(skb, b);
 856         return -1;
 857 }
 858
 859 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n,
 860                         u32 clid, struct Qdisc *old, struct Qdisc *new)
 861 {
 862         struct sk_buff *skb;
 863         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
 864
 865         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
 866         if (!skb)
 867                 return -ENOBUFS;
 868
 869         if (old && old->handle) {
 870                 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0)
 871                         goto err_out;
 872         }
 873         if (new) {
 874                 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
 875                         goto err_out;
 876         }
 877
 878         if (skb->len)
 879                 return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
 880
 881 err_out:
 882         kfree_skb(skb);
 883         return -EINVAL;
 884 }
 885
 886 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
 887 {
 888         int idx, q_idx;
 889         int s_idx, s_q_idx;
 890         struct net_device *dev;
 891         struct Qdisc *q;
 892
 893         s_idx = cb->args[0];
 894         s_q_idx = q_idx = cb->args[1];
 895         read_lock(&dev_base_lock);
 896         for (dev=dev_base, idx=0; dev; dev = dev->next, idx++) {
 897                 if (idx < s_idx)
 898                         continue;
 899                 if (idx > s_idx)
 900                         s_q_idx = 0;
 901                 read_lock(&qdisc_tree_lock);
 902                 q_idx = 0;
 903                 list_for_each_entry(q, &dev->qdisc_list, list) {
 904                         if (q_idx < s_q_idx) {
 905                                 q_idx++;
 906                                 continue;
 907                         }
 908                         if (tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
 909                                           cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0) {
 910                                 read_unlock(&qdisc_tree_lock);
 911                                 goto done;
 912                         }
 913                         q_idx++;
 914                 }
 915                 read_unlock(&qdisc_tree_lock);
 916         }
 917
 918 done:
 919         read_unlock(&dev_base_lock);
 920
 921         cb->args[0] = idx;
 922         cb->args[1] = q_idx;
 923
 924         return skb->len;
 925 }
 926
 927
 928
 929 /************************************************
 930  *      Traffic classes manipulation.           *
 931  ************************************************/
 932
 933
 934
 935 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 936 {
 937         struct tcmsg *tcm = NLMSG_DATA(n);
 938         struct rtattr **tca = arg;
 939         struct net_device *dev;
 940         struct Qdisc *q = NULL;
 941         struct Qdisc_class_ops *cops;
 942         unsigned long cl = 0;
 943         unsigned long new_cl;
 944         u32 pid = tcm->tcm_parent;
 945         u32 clid = tcm->tcm_handle;
 946         u32 qid = TC_H_MAJ(clid);
 947         int err;
 948
 949         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 950                 return -ENODEV;
 951
 952         /*
 953            parent == TC_H_UNSPEC - unspecified parent.
 954            parent == TC_H_ROOT   - class is root, which has no parent.
 955            parent == X:0         - parent is root class.
 956            parent == X:Y         - parent is a node in hierarchy.
 957            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
 958
 959            handle == 0:0         - generate handle from kernel pool.
 960            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
 961            handle == X:Y         - clear.
 962            handle == X:0         - root class.
 963          */
 964
 965         /* Step 1. Determine qdisc handle X:0 */
 966
 967         if (pid != TC_H_ROOT) {
 968                 u32 qid1 = TC_H_MAJ(pid);
 969
 970                 if (qid && qid1) {
 971                         /* If both majors are known, they must be identical. */
 972                         if (qid != qid1)
 973                                 return -EINVAL;
 974                 } else if (qid1) {
 975                         qid = qid1;
 976                 } else if (qid == 0)
 977                         qid = dev->qdisc_sleeping->handle;
 978
 979                 /* Now qid is genuine qdisc handle consistent
 980                    both with parent and child.
 981
 982                    TC_H_MAJ(pid) still may be unspecified, complete it now.
 983                  */
 984                 if (pid)
 985                         pid = TC_H_MAKE(qid, pid);
 986         } else {
 987                 if (qid == 0)
 988                         qid = dev->qdisc_sleeping->handle;
 989         }
 990
 991         /* OK. Locate qdisc */
 992         if ((q = qdisc_lookup(dev, qid)) == NULL)
 993                 return -ENOENT;
 994
 995         /* An check that it supports classes */
 996         cops = q->ops->cl_ops;
 997         if (cops == NULL)
 998                 return -EINVAL;
 999
1000         /* Now try to get class */
1001         if (clid == 0) {
1002                 if (pid == TC_H_ROOT)
1003                         clid = qid;
1004         } else
1005                 clid = TC_H_MAKE(qid, clid);
1006
1007         if (clid)
1008                 cl = cops->get(q, clid);
1009
1010         if (cl == 0) {
1011                 err = -ENOENT;
1012                 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE))
1013                         goto out;
1014         } else {
1015                 switch (n->nlmsg_type) {
1016                 case RTM_NEWTCLASS:
1017                         err = -EEXIST;
1018                         if (n->nlmsg_flags&NLM_F_EXCL)
1019                                 goto out;
1020                         break;
1021                 case RTM_DELTCLASS:
1022                         err = cops->delete(q, cl);
1023                         if (err == 0)
1024                                 tclass_notify(skb, n, q, cl, RTM_DELTCLASS);
1025                         goto out;
1026                 case RTM_GETTCLASS:
1027                         err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS);
1028                         goto out;
1029                 default:
1030                         err = -EINVAL;
1031                         goto out;
1032                 }
1033         }
1034
1035         new_cl = cl;
1036         err = cops->change(q, clid, pid, tca, &new_cl);
1037         if (err == 0)
1038                 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
1039
1040 out:
1041         if (cl)
1042                 cops->put(q, cl);
1043
1044         return err;
1045 }
1046
1047
1048 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
1049                           unsigned long cl,
1050                           u32 pid, u32 seq, u16 flags, int event)
1051 {
1052         struct tcmsg *tcm;
1053         struct nlmsghdr  *nlh;
1054         unsigned char *b = skb_tail_pointer(skb);
1055         struct gnet_dump d;
1056         struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1057
1058         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
1059         tcm = NLMSG_DATA(nlh);
1060         tcm->tcm_family = AF_UNSPEC;
1061         tcm->tcm_ifindex = q->dev->ifindex;
1062         tcm->tcm_parent = q->handle;
1063         tcm->tcm_handle = q->handle;
1064         tcm->tcm_info = 0;
1065         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
1066         if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1067                 goto rtattr_failure;
1068
1069         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1070                         TCA_XSTATS, q->stats_lock, &d) < 0)
1071                 goto rtattr_failure;
1072
1073         if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1074                 goto rtattr_failure;
1075
1076         if (gnet_stats_finish_copy(&d) < 0)
1077                 goto rtattr_failure;
1078
1079         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1080         return skb->len;
1081
1082 nlmsg_failure:
1083 rtattr_failure:
1084         nlmsg_trim(skb, b);
1085         return -1;
1086 }
1087
1088 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1089                           struct Qdisc *q, unsigned long cl, int event)
1090 {
1091         struct sk_buff *skb;
1092         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1093
1094         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1095         if (!skb)
1096                 return -ENOBUFS;
1097
1098         if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) {
1099                 kfree_skb(skb);
1100                 return -EINVAL;
1101         }
1102
1103         return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1104 }
1105
1106 struct qdisc_dump_args
1107 {
1108         struct qdisc_walker w;
1109         struct sk_buff *skb;
1110         struct netlink_callback *cb;
1111 };
1112
1113 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg)
1114 {
1115         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
1116
1117         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid,
1118                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS);
1119 }
1120
1121 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
1122 {
1123         int t;
1124         int s_t;
1125         struct net_device *dev;
1126         struct Qdisc *q;
1127         struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh);
1128         struct qdisc_dump_args arg;
1129
1130         if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm)))
1131                 return 0;
1132         if ((dev = dev_get_by_index(tcm->tcm_ifindex)) == NULL)
1133                 return 0;
1134
1135         s_t = cb->args[0];
1136         t = 0;
1137
1138         read_lock(&qdisc_tree_lock);
1139         list_for_each_entry(q, &dev->qdisc_list, list) {
1140                 if (t < s_t || !q->ops->cl_ops ||
1141                     (tcm->tcm_parent &&
1142                      TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
1143                         t++;
1144                         continue;
1145                 }
1146                 if (t > s_t)
1147                         memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
1148                 arg.w.fn = qdisc_class_dump;
1149                 arg.skb = skb;
1150                 arg.cb = cb;
1151                 arg.w.stop  = 0;
1152                 arg.w.skip = cb->args[1];
1153                 arg.w.count = 0;
1154                 q->ops->cl_ops->walk(q, &arg.w);
1155                 cb->args[1] = arg.w.count;
1156                 if (arg.w.stop)
1157                         break;
1158                 t++;
1159         }
1160         read_unlock(&qdisc_tree_lock);
1161
1162         cb->args[0] = t;
1163
1164         dev_put(dev);
1165         return skb->len;
1166 }
1167
1168 /* Main classifier routine: scans classifier chain attached
1169    to this qdisc, (optionally) tests for protocol and asks
1170    specific classifiers.
1171  */
1172 int tc_classify(struct sk_buff *skb, struct tcf_proto *tp,
1173         struct tcf_result *res)
1174 {
1175         int err = 0;
1176         __be16 protocol = skb->protocol;
1177 #ifdef CONFIG_NET_CLS_ACT
1178         struct tcf_proto *otp = tp;
1179 reclassify:
1180 #endif
1181         protocol = skb->protocol;
1182
1183         for ( ; tp; tp = tp->next) {
1184                 if ((tp->protocol == protocol ||
1185                         tp->protocol == htons(ETH_P_ALL)) &&
1186                         (err = tp->classify(skb, tp, res)) >= 0) {
1187 #ifdef CONFIG_NET_CLS_ACT
1188                         if ( TC_ACT_RECLASSIFY == err) {
1189                                 __u32 verd = (__u32) G_TC_VERD(skb->tc_verd);
1190                                 tp = otp;
1191
1192                                 if (MAX_REC_LOOP < verd++) {
1193                                         printk("rule prio %d protocol %02x reclassify is buggy packet dropped\n",
1194                                                 tp->prio&0xffff, ntohs(tp->protocol));
1195                                         return TC_ACT_SHOT;
1196                                 }
1197                                 skb->tc_verd = SET_TC_VERD(skb->tc_verd,verd);
1198                                 goto reclassify;
1199                         } else {
1200                                 if (skb->tc_verd)
1201                                         skb->tc_verd = SET_TC_VERD(skb->tc_verd,0);
1202                                 return err;
1203                         }
1204 #else
1205
1206                         return err;
1207 #endif
1208                 }
1209
1210         }
1211         return -1;
1212 }
1213
1214 #ifdef CONFIG_PROC_FS
1215 static int psched_show(struct seq_file *seq, void *v)
1216 {
1217         seq_printf(seq, "%08x %08x %08x %08x\n",
1218                    (u32)NSEC_PER_USEC, (u32)PSCHED_US2NS(1),
1219                    1000000,
1220                    (u32)NSEC_PER_SEC/(u32)ktime_to_ns(KTIME_MONOTONIC_RES));
1221
1222         return 0;
1223 }
1224
1225 static int psched_open(struct inode *inode, struct file *file)
1226 {
1227         return single_open(file, psched_show, PDE(inode)->data);
1228 }
1229
1230 static const struct file_operations psched_fops = {
1231         .owner = THIS_MODULE,
1232         .open = psched_open,
1233         .read  = seq_read,
1234         .llseek = seq_lseek,
1235         .release = single_release,
1236 };
1237 #endif
1238
1239 static int __init pktsched_init(void)
1240 {
1241         register_qdisc(&pfifo_qdisc_ops);
1242         register_qdisc(&bfifo_qdisc_ops);
1243         proc_net_fops_create("psched", 0, &psched_fops);
1244
1245         rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL);
1246         rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL);
1247         rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc);
1248         rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL);
1249         rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL);
1250         rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass);
1251
1252         return 0;
1253 }
1254
1255 subsys_initcall(pktsched_init);
1256
1257 EXPORT_SYMBOL(qdisc_get_rtab);
1258 EXPORT_SYMBOL(qdisc_put_rtab);
1259 EXPORT_SYMBOL(register_qdisc);
1260 EXPORT_SYMBOL(unregister_qdisc);
1261 EXPORT_SYMBOL(tc_classify);