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