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