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