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