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