SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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                 handle = TC_H_MAKE(TC_H_INGRESS, 0);
 504         } else if (handle == 0) {
 505                 handle = qdisc_alloc_handle(dev);
 506                 err = -ENOMEM;
 507                 if (handle == 0)
 508                         goto err_out3;
 509         }
 510
 511         sch->handle = handle;
 512
 513         if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS-1])) == 0) {
 514 #ifdef CONFIG_NET_ESTIMATOR
 515                 if (tca[TCA_RATE-1]) {
 516                         err = gen_new_estimator(&sch->bstats, &sch->rate_est,
 517                                                 sch->stats_lock,
 518                                                 tca[TCA_RATE-1]);
 519                         if (err) {
 520                                 /*
 521                                  * Any broken qdiscs that would require
 522                                  * a ops->reset() here? The qdisc was never
 523                                  * in action so it shouldn't be necessary.
 524                                  */
 525                                 if (ops->destroy)
 526                                         ops->destroy(sch);
 527                                 goto err_out3;
 528                         }
 529                 }
 530 #endif
 531                 qdisc_lock_tree(dev);
 532                 list_add_tail(&sch->list, &dev->qdisc_list);
 533                 qdisc_unlock_tree(dev);
 534
 535                 return sch;
 536         }
 537 err_out3:
 538         dev_put(dev);
 539         kfree((char *) sch - sch->padded);
 540 err_out2:
 541         module_put(ops->owner);
 542 err_out:
 543         *errp = err;
 544         return NULL;
 545 }
 546
 547 static int qdisc_change(struct Qdisc *sch, struct rtattr **tca)
 548 {
 549         if (tca[TCA_OPTIONS-1]) {
 550                 int err;
 551
 552                 if (sch->ops->change == NULL)
 553                         return -EINVAL;
 554                 err = sch->ops->change(sch, tca[TCA_OPTIONS-1]);
 555                 if (err)
 556                         return err;
 557         }
 558 #ifdef CONFIG_NET_ESTIMATOR
 559         if (tca[TCA_RATE-1])
 560                 gen_replace_estimator(&sch->bstats, &sch->rate_est,
 561                         sch->stats_lock, tca[TCA_RATE-1]);
 562 #endif
 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                         spin_lock_bh(&dev->queue_lock);
 658                         qdisc_destroy(q);
 659                         spin_unlock_bh(&dev->queue_lock);
 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                                 spin_lock_bh(&dev->queue_lock);
 793                                 qdisc_destroy(q);
 794                                 spin_unlock_bh(&dev->queue_lock);
 795                         }
 796                         return err;
 797                 }
 798                 qdisc_notify(skb, n, clid, old_q, q);
 799                 if (old_q) {
 800                         spin_lock_bh(&dev->queue_lock);
 801                         qdisc_destroy(old_q);
 802                         spin_unlock_bh(&dev->queue_lock);
 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 #ifdef CONFIG_NET_ESTIMATOR
 839             gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 ||
 840 #endif
 841             gnet_stats_copy_queue(&d, &q->qstats) < 0)
 842                 goto rtattr_failure;
 843
 844         if (gnet_stats_finish_copy(&d) < 0)
 845                 goto rtattr_failure;
 846
 847         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
 848         return skb->len;
 849
 850 nlmsg_failure:
 851 rtattr_failure:
 852         nlmsg_trim(skb, b);
 853         return -1;
 854 }
 855
 856 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n,
 857                         u32 clid, struct Qdisc *old, struct Qdisc *new)
 858 {
 859         struct sk_buff *skb;
 860         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
 861
 862         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
 863         if (!skb)
 864                 return -ENOBUFS;
 865
 866         if (old && old->handle) {
 867                 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0)
 868                         goto err_out;
 869         }
 870         if (new) {
 871                 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
 872                         goto err_out;
 873         }
 874
 875         if (skb->len)
 876                 return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
 877
 878 err_out:
 879         kfree_skb(skb);
 880         return -EINVAL;
 881 }
 882
 883 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
 884 {
 885         int idx, q_idx;
 886         int s_idx, s_q_idx;
 887         struct net_device *dev;
 888         struct Qdisc *q;
 889
 890         s_idx = cb->args[0];
 891         s_q_idx = q_idx = cb->args[1];
 892         read_lock(&dev_base_lock);
 893         for (dev=dev_base, idx=0; dev; dev = dev->next, idx++) {
 894                 if (idx < s_idx)
 895                         continue;
 896                 if (idx > s_idx)
 897                         s_q_idx = 0;
 898                 q_idx = 0;
 899                 list_for_each_entry(q, &dev->qdisc_list, list) {
 900                         if (q_idx < s_q_idx) {
 901                                 q_idx++;
 902                                 continue;
 903                         }
 904                         if (tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
 905                                           cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0)
 906                                 goto done;
 907                         q_idx++;
 908                 }
 909         }
 910
 911 done:
 912         read_unlock(&dev_base_lock);
 913
 914         cb->args[0] = idx;
 915         cb->args[1] = q_idx;
 916
 917         return skb->len;
 918 }
 919
 920
 921
 922 /************************************************
 923  *      Traffic classes manipulation.           *
 924  ************************************************/
 925
 926
 927
 928 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 929 {
 930         struct tcmsg *tcm = NLMSG_DATA(n);
 931         struct rtattr **tca = arg;
 932         struct net_device *dev;
 933         struct Qdisc *q = NULL;
 934         struct Qdisc_class_ops *cops;
 935         unsigned long cl = 0;
 936         unsigned long new_cl;
 937         u32 pid = tcm->tcm_parent;
 938         u32 clid = tcm->tcm_handle;
 939         u32 qid = TC_H_MAJ(clid);
 940         int err;
 941
 942         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 943                 return -ENODEV;
 944
 945         /*
 946            parent == TC_H_UNSPEC - unspecified parent.
 947            parent == TC_H_ROOT   - class is root, which has no parent.
 948            parent == X:0         - parent is root class.
 949            parent == X:Y         - parent is a node in hierarchy.
 950            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
 951
 952            handle == 0:0         - generate handle from kernel pool.
 953            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
 954            handle == X:Y         - clear.
 955            handle == X:0         - root class.
 956          */
 957
 958         /* Step 1. Determine qdisc handle X:0 */
 959
 960         if (pid != TC_H_ROOT) {
 961                 u32 qid1 = TC_H_MAJ(pid);
 962
 963                 if (qid && qid1) {
 964                         /* If both majors are known, they must be identical. */
 965                         if (qid != qid1)
 966                                 return -EINVAL;
 967                 } else if (qid1) {
 968                         qid = qid1;
 969                 } else if (qid == 0)
 970                         qid = dev->qdisc_sleeping->handle;
 971
 972                 /* Now qid is genuine qdisc handle consistent
 973                    both with parent and child.
 974
 975                    TC_H_MAJ(pid) still may be unspecified, complete it now.
 976                  */
 977                 if (pid)
 978                         pid = TC_H_MAKE(qid, pid);
 979         } else {
 980                 if (qid == 0)
 981                         qid = dev->qdisc_sleeping->handle;
 982         }
 983
 984         /* OK. Locate qdisc */
 985         if ((q = qdisc_lookup(dev, qid)) == NULL)
 986                 return -ENOENT;
 987
 988         /* An check that it supports classes */
 989         cops = q->ops->cl_ops;
 990         if (cops == NULL)
 991                 return -EINVAL;
 992
 993         /* Now try to get class */
 994         if (clid == 0) {
 995                 if (pid == TC_H_ROOT)
 996                         clid = qid;
 997         } else
 998                 clid = TC_H_MAKE(qid, clid);
 999
1000         if (clid)
1001                 cl = cops->get(q, clid);
1002
1003         if (cl == 0) {
1004                 err = -ENOENT;
1005                 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE))
1006                         goto out;
1007         } else {
1008                 switch (n->nlmsg_type) {
1009                 case RTM_NEWTCLASS:
1010                         err = -EEXIST;
1011                         if (n->nlmsg_flags&NLM_F_EXCL)
1012                                 goto out;
1013                         break;
1014                 case RTM_DELTCLASS:
1015                         err = cops->delete(q, cl);
1016                         if (err == 0)
1017                                 tclass_notify(skb, n, q, cl, RTM_DELTCLASS);
1018                         goto out;
1019                 case RTM_GETTCLASS:
1020                         err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS);
1021                         goto out;
1022                 default:
1023                         err = -EINVAL;
1024                         goto out;
1025                 }
1026         }
1027
1028         new_cl = cl;
1029         err = cops->change(q, clid, pid, tca, &new_cl);
1030         if (err == 0)
1031                 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
1032
1033 out:
1034         if (cl)
1035                 cops->put(q, cl);
1036
1037         return err;
1038 }
1039
1040
1041 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
1042                           unsigned long cl,
1043                           u32 pid, u32 seq, u16 flags, int event)
1044 {
1045         struct tcmsg *tcm;
1046         struct nlmsghdr  *nlh;
1047         unsigned char *b = skb_tail_pointer(skb);
1048         struct gnet_dump d;
1049         struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1050
1051         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
1052         tcm = NLMSG_DATA(nlh);
1053         tcm->tcm_family = AF_UNSPEC;
1054         tcm->tcm_ifindex = q->dev->ifindex;
1055         tcm->tcm_parent = q->handle;
1056         tcm->tcm_handle = q->handle;
1057         tcm->tcm_info = 0;
1058         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
1059         if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1060                 goto rtattr_failure;
1061
1062         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1063                         TCA_XSTATS, q->stats_lock, &d) < 0)
1064                 goto rtattr_failure;
1065
1066         if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1067                 goto rtattr_failure;
1068
1069         if (gnet_stats_finish_copy(&d) < 0)
1070                 goto rtattr_failure;
1071
1072         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1073         return skb->len;
1074
1075 nlmsg_failure:
1076 rtattr_failure:
1077         nlmsg_trim(skb, b);
1078         return -1;
1079 }
1080
1081 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1082                           struct Qdisc *q, unsigned long cl, int event)
1083 {
1084         struct sk_buff *skb;
1085         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1086
1087         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1088         if (!skb)
1089                 return -ENOBUFS;
1090
1091         if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) {
1092                 kfree_skb(skb);
1093                 return -EINVAL;
1094         }
1095
1096         return rtnetlink_send(skb, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1097 }
1098
1099 struct qdisc_dump_args
1100 {
1101         struct qdisc_walker w;
1102         struct sk_buff *skb;
1103         struct netlink_callback *cb;
1104 };
1105
1106 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg)
1107 {
1108         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
1109
1110         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid,
1111                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS);
1112 }
1113
1114 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
1115 {
1116         int t;
1117         int s_t;
1118         struct net_device *dev;
1119         struct Qdisc *q;
1120         struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh);
1121         struct qdisc_dump_args arg;
1122
1123         if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm)))
1124                 return 0;
1125         if ((dev = dev_get_by_index(tcm->tcm_ifindex)) == NULL)
1126                 return 0;
1127
1128         s_t = cb->args[0];
1129         t = 0;
1130
1131         list_for_each_entry(q, &dev->qdisc_list, list) {
1132                 if (t < s_t || !q->ops->cl_ops ||
1133                     (tcm->tcm_parent &&
1134                      TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
1135                         t++;
1136                         continue;
1137                 }
1138                 if (t > s_t)
1139                         memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
1140                 arg.w.fn = qdisc_class_dump;
1141                 arg.skb = skb;
1142                 arg.cb = cb;
1143                 arg.w.stop  = 0;
1144                 arg.w.skip = cb->args[1];
1145                 arg.w.count = 0;
1146                 q->ops->cl_ops->walk(q, &arg.w);
1147                 cb->args[1] = arg.w.count;
1148                 if (arg.w.stop)
1149                         break;
1150                 t++;
1151         }
1152
1153         cb->args[0] = t;
1154
1155         dev_put(dev);
1156         return skb->len;
1157 }
1158
1159 /* Main classifier routine: scans classifier chain attached
1160    to this qdisc, (optionally) tests for protocol and asks
1161    specific classifiers.
1162  */
1163 int tc_classify(struct sk_buff *skb, struct tcf_proto *tp,
1164         struct tcf_result *res)
1165 {
1166         int err = 0;
1167         __be16 protocol = skb->protocol;
1168 #ifdef CONFIG_NET_CLS_ACT
1169         struct tcf_proto *otp = tp;
1170 reclassify:
1171 #endif
1172         protocol = skb->protocol;
1173
1174         for ( ; tp; tp = tp->next) {
1175                 if ((tp->protocol == protocol ||
1176                         tp->protocol == htons(ETH_P_ALL)) &&
1177                         (err = tp->classify(skb, tp, res)) >= 0) {
1178 #ifdef CONFIG_NET_CLS_ACT
1179                         if ( TC_ACT_RECLASSIFY == err) {
1180                                 __u32 verd = (__u32) G_TC_VERD(skb->tc_verd);
1181                                 tp = otp;
1182
1183                                 if (MAX_REC_LOOP < verd++) {
1184                                         printk("rule prio %d protocol %02x reclassify is buggy packet dropped\n",
1185                                                 tp->prio&0xffff, ntohs(tp->protocol));
1186                                         return TC_ACT_SHOT;
1187                                 }
1188                                 skb->tc_verd = SET_TC_VERD(skb->tc_verd,verd);
1189                                 goto reclassify;
1190                         } else {
1191                                 if (skb->tc_verd)
1192                                         skb->tc_verd = SET_TC_VERD(skb->tc_verd,0);
1193                                 return err;
1194                         }
1195 #else
1196
1197                         return err;
1198 #endif
1199                 }
1200
1201         }
1202         return -1;
1203 }
1204
1205 void tcf_destroy(struct tcf_proto *tp)
1206 {
1207         tp->ops->destroy(tp);
1208         module_put(tp->ops->owner);
1209         kfree(tp);
1210 }
1211
1212 void tcf_destroy_chain(struct tcf_proto *fl)
1213 {
1214         struct tcf_proto *tp;
1215
1216         while ((tp = fl) != NULL) {
1217                 fl = tp->next;
1218                 tcf_destroy(tp);
1219         }
1220 }
1221 EXPORT_SYMBOL(tcf_destroy_chain);
1222
1223 #ifdef CONFIG_PROC_FS
1224 static int psched_show(struct seq_file *seq, void *v)
1225 {
1226         seq_printf(seq, "%08x %08x %08x %08x\n",
1227                    (u32)NSEC_PER_USEC, (u32)PSCHED_US2NS(1),
1228                    1000000,
1229                    (u32)NSEC_PER_SEC/(u32)ktime_to_ns(KTIME_MONOTONIC_RES));
1230
1231         return 0;
1232 }
1233
1234 static int psched_open(struct inode *inode, struct file *file)
1235 {
1236         return single_open(file, psched_show, PDE(inode)->data);
1237 }
1238
1239 static const struct file_operations psched_fops = {
1240         .owner = THIS_MODULE,
1241         .open = psched_open,
1242         .read  = seq_read,
1243         .llseek = seq_lseek,
1244         .release = single_release,
1245 };
1246 #endif
1247
1248 static int __init pktsched_init(void)
1249 {
1250         register_qdisc(&pfifo_qdisc_ops);
1251         register_qdisc(&bfifo_qdisc_ops);
1252         proc_net_fops_create("psched", 0, &psched_fops);
1253
1254         rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL);
1255         rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL);
1256         rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc);
1257         rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL);
1258         rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL);
1259         rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass);
1260
1261         return 0;
1262 }
1263
1264 subsys_initcall(pktsched_init);
1265
1266 EXPORT_SYMBOL(qdisc_get_rtab);
1267 EXPORT_SYMBOL(qdisc_put_rtab);
1268 EXPORT_SYMBOL(register_qdisc);
1269 EXPORT_SYMBOL(unregister_qdisc);
1270 EXPORT_SYMBOL(tc_classify);