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         /* enqueue is accessed locklessly - make sure it's visible
 454          * before we set a netdevice's qdisc pointer to sch */
 455         smp_wmb();
 456         if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS-1])) == 0) {
 457                 write_lock(&qdisc_tree_lock);
 458                 sch->next = dev->qdisc_list;
 459                 dev->qdisc_list = sch;
 460                 write_unlock(&qdisc_tree_lock);
 461 #ifdef CONFIG_NET_ESTIMATOR
 462                 if (tca[TCA_RATE-1])
 463                         qdisc_new_estimator(&sch->stats, sch->stats_lock,
 464                                             tca[TCA_RATE-1]);
 465 #endif
 466                 return sch;
 467         }
 468         module_put(ops->owner);
 469
 470 err_out:
 471         *errp = err;
 472         if (sch)
 473                 kfree(sch);
 474         return NULL;
 475 }
 476
 477 static int qdisc_change(struct Qdisc *sch, struct rtattr **tca)
 478 {
 479         if (tca[TCA_OPTIONS-1]) {
 480                 int err;
 481
 482                 if (sch->ops->change == NULL)
 483                         return -EINVAL;
 484                 err = sch->ops->change(sch, tca[TCA_OPTIONS-1]);
 485                 if (err)
 486                         return err;
 487         }
 488 #ifdef CONFIG_NET_ESTIMATOR
 489         if (tca[TCA_RATE-1]) {
 490                 qdisc_kill_estimator(&sch->stats);
 491                 qdisc_new_estimator(&sch->stats, sch->stats_lock,
 492                                     tca[TCA_RATE-1]);
 493         }
 494 #endif
 495         return 0;
 496 }
 497
 498 struct check_loop_arg
 499 {
 500         struct qdisc_walker     w;
 501         struct Qdisc            *p;
 502         int                     depth;
 503 };
 504
 505 static int check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w);
 506
 507 static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth)
 508 {
 509         struct check_loop_arg   arg;
 510
 511         if (q->ops->cl_ops == NULL)
 512                 return 0;
 513
 514         arg.w.stop = arg.w.skip = arg.w.count = 0;
 515         arg.w.fn = check_loop_fn;
 516         arg.depth = depth;
 517         arg.p = p;
 518         q->ops->cl_ops->walk(q, &arg.w);
 519         return arg.w.stop ? -ELOOP : 0;
 520 }
 521
 522 static int
 523 check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w)
 524 {
 525         struct Qdisc *leaf;
 526         struct Qdisc_class_ops *cops = q->ops->cl_ops;
 527         struct check_loop_arg *arg = (struct check_loop_arg *)w;
 528
 529         leaf = cops->leaf(q, cl);
 530         if (leaf) {
 531                 if (leaf == arg->p || arg->depth > 7)
 532                         return -ELOOP;
 533                 return check_loop(leaf, arg->p, arg->depth + 1);
 534         }
 535         return 0;
 536 }
 537
 538 /*
 539  * Delete/get qdisc.
 540  */
 541
 542 static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 543 {
 544         struct tcmsg *tcm = NLMSG_DATA(n);
 545         struct rtattr **tca = arg;
 546         struct net_device *dev;
 547         u32 clid = tcm->tcm_parent;
 548         struct Qdisc *q = NULL;
 549         struct Qdisc *p = NULL;
 550         int err;
 551
 552         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 553                 return -ENODEV;
 554
 555         if (clid) {
 556                 if (clid != TC_H_ROOT) {
 557                         if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) {
 558                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
 559                                         return -ENOENT;
 560                                 q = qdisc_leaf(p, clid);
 561                         } else { /* ingress */
 562                                 q = dev->qdisc_ingress;
 563                         }
 564                 } else {
 565                         q = dev->qdisc_sleeping;
 566                 }
 567                 if (!q)
 568                         return -ENOENT;
 569
 570                 if (tcm->tcm_handle && q->handle != tcm->tcm_handle)
 571                         return -EINVAL;
 572         } else {
 573                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
 574                         return -ENOENT;
 575         }
 576
 577         if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
 578                 return -EINVAL;
 579
 580         if (n->nlmsg_type == RTM_DELQDISC) {
 581                 if (!clid)
 582                         return -EINVAL;
 583                 if (q->handle == 0)
 584                         return -ENOENT;
 585                 if ((err = qdisc_graft(dev, p, clid, NULL, &q)) != 0)
 586                         return err;
 587                 if (q) {
 588                         qdisc_notify(skb, n, clid, q, NULL);
 589                         spin_lock_bh(&dev->queue_lock);
 590                         qdisc_destroy(q);
 591                         spin_unlock_bh(&dev->queue_lock);
 592                 }
 593         } else {
 594                 qdisc_notify(skb, n, clid, NULL, q);
 595         }
 596         return 0;
 597 }
 598
 599 /*
 600    Create/change qdisc.
 601  */
 602
 603 static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 604 {
 605         struct tcmsg *tcm = NLMSG_DATA(n);
 606         struct rtattr **tca = arg;
 607         struct net_device *dev;
 608         u32 clid = tcm->tcm_parent;
 609         struct Qdisc *q = NULL;
 610         struct Qdisc *p = NULL;
 611         int err;
 612
 613         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 614                 return -ENODEV;
 615
 616         if (clid) {
 617                 if (clid != TC_H_ROOT) {
 618                         if (clid != TC_H_INGRESS) {
 619                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
 620                                         return -ENOENT;
 621                                 q = qdisc_leaf(p, clid);
 622                         } else { /*ingress */
 623                                 q = dev->qdisc_ingress;
 624                         }
 625                 } else {
 626                         q = dev->qdisc_sleeping;
 627                 }
 628
 629                 /* It may be default qdisc, ignore it */
 630                 if (q && q->handle == 0)
 631                         q = NULL;
 632
 633                 if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) {
 634                         if (tcm->tcm_handle) {
 635                                 if (q && !(n->nlmsg_flags&NLM_F_REPLACE))
 636                                         return -EEXIST;
 637                                 if (TC_H_MIN(tcm->tcm_handle))
 638                                         return -EINVAL;
 639                                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
 640                                         goto create_n_graft;
 641                                 if (n->nlmsg_flags&NLM_F_EXCL)
 642                                         return -EEXIST;
 643                                 if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
 644                                         return -EINVAL;
 645                                 if (q == p ||
 646                                     (p && check_loop(q, p, 0)))
 647                                         return -ELOOP;
 648                                 atomic_inc(&q->refcnt);
 649                                 goto graft;
 650                         } else {
 651                                 if (q == NULL)
 652                                         goto create_n_graft;
 653
 654                                 /* This magic test requires explanation.
 655                                  *
 656                                  *   We know, that some child q is already
 657                                  *   attached to this parent and have choice:
 658                                  *   either to change it or to create/graft new one.
 659                                  *
 660                                  *   1. We are allowed to create/graft only
 661                                  *   if CREATE and REPLACE flags are set.
 662                                  *
 663                                  *   2. If EXCL is set, requestor wanted to say,
 664                                  *   that qdisc tcm_handle is not expected
 665                                  *   to exist, so that we choose create/graft too.
 666                                  *
 667                                  *   3. The last case is when no flags are set.
 668                                  *   Alas, it is sort of hole in API, we
 669                                  *   cannot decide what to do unambiguously.
 670                                  *   For now we select create/graft, if
 671                                  *   user gave KIND, which does not match existing.
 672                                  */
 673                                 if ((n->nlmsg_flags&NLM_F_CREATE) &&
 674                                     (n->nlmsg_flags&NLM_F_REPLACE) &&
 675                                     ((n->nlmsg_flags&NLM_F_EXCL) ||
 676                                      (tca[TCA_KIND-1] &&
 677                                       rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))))
 678                                         goto create_n_graft;
 679                         }
 680                 }
 681         } else {
 682                 if (!tcm->tcm_handle)
 683                         return -EINVAL;
 684                 q = qdisc_lookup(dev, tcm->tcm_handle);
 685         }
 686
 687         /* Change qdisc parameters */
 688         if (q == NULL)
 689                 return -ENOENT;
 690         if (n->nlmsg_flags&NLM_F_EXCL)
 691                 return -EEXIST;
 692         if (tca[TCA_KIND-1] && rtattr_strcmp(tca[TCA_KIND-1], q->ops->id))
 693                 return -EINVAL;
 694         err = qdisc_change(q, tca);
 695         if (err == 0)
 696                 qdisc_notify(skb, n, clid, NULL, q);
 697         return err;
 698
 699 create_n_graft:
 700         if (!(n->nlmsg_flags&NLM_F_CREATE))
 701                 return -ENOENT;
 702         if (clid == TC_H_INGRESS)
 703                 q = qdisc_create(dev, tcm->tcm_parent, tca, &err);
 704         else
 705                 q = qdisc_create(dev, tcm->tcm_handle, tca, &err);
 706         if (q == NULL)
 707                 return err;
 708
 709 graft:
 710         if (1) {
 711                 struct Qdisc *old_q = NULL;
 712                 err = qdisc_graft(dev, p, clid, q, &old_q);
 713                 if (err) {
 714                         if (q) {
 715                                 spin_lock_bh(&dev->queue_lock);
 716                                 qdisc_destroy(q);
 717                                 spin_unlock_bh(&dev->queue_lock);
 718                         }
 719                         return err;
 720                 }
 721                 qdisc_notify(skb, n, clid, old_q, q);
 722                 if (old_q) {
 723                         spin_lock_bh(&dev->queue_lock);
 724                         qdisc_destroy(old_q);
 725                         spin_unlock_bh(&dev->queue_lock);
 726                 }
 727         }
 728         return 0;
 729 }
 730
 731 int qdisc_copy_stats(struct sk_buff *skb, struct tc_stats *st, spinlock_t *lock)
 732 {
 733         spin_lock_bh(lock);
 734         RTA_PUT(skb, TCA_STATS, sizeof(struct tc_stats), st);
 735         spin_unlock_bh(lock);
 736         return 0;
 737
 738 rtattr_failure:
 739         spin_unlock_bh(lock);
 740         return -1;
 741 }
 742
 743
 744 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
 745                          u32 pid, u32 seq, unsigned flags, int event)
 746 {
 747         struct tcmsg *tcm;
 748         struct nlmsghdr  *nlh;
 749         unsigned char    *b = skb->tail;
 750
 751         nlh = NLMSG_PUT(skb, pid, seq, event, sizeof(*tcm));
 752         nlh->nlmsg_flags = flags;
 753         tcm = NLMSG_DATA(nlh);
 754         tcm->tcm_family = AF_UNSPEC;
 755         tcm->tcm_ifindex = q->dev ? q->dev->ifindex : 0;
 756         tcm->tcm_parent = clid;
 757         tcm->tcm_handle = q->handle;
 758         tcm->tcm_info = atomic_read(&q->refcnt);
 759         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
 760         if (q->ops->dump && q->ops->dump(q, skb) < 0)
 761                 goto rtattr_failure;
 762         q->stats.qlen = q->q.qlen;
 763         if (qdisc_copy_stats(skb, &q->stats, q->stats_lock))
 764                 goto rtattr_failure;
 765         nlh->nlmsg_len = skb->tail - b;
 766         return skb->len;
 767
 768 nlmsg_failure:
 769 rtattr_failure:
 770         skb_trim(skb, b - skb->data);
 771         return -1;
 772 }
 773
 774 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n,
 775                         u32 clid, struct Qdisc *old, struct Qdisc *new)
 776 {
 777         struct sk_buff *skb;
 778         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
 779
 780         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
 781         if (!skb)
 782                 return -ENOBUFS;
 783
 784         if (old && old->handle) {
 785                 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0)
 786                         goto err_out;
 787         }
 788         if (new) {
 789                 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
 790                         goto err_out;
 791         }
 792
 793         if (skb->len)
 794                 return rtnetlink_send(skb, pid, RTMGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
 795
 796 err_out:
 797         kfree_skb(skb);
 798         return -EINVAL;
 799 }
 800
 801 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
 802 {
 803         int idx, q_idx;
 804         int s_idx, s_q_idx;
 805         struct net_device *dev;
 806         struct Qdisc *q;
 807
 808         s_idx = cb->args[0];
 809         s_q_idx = q_idx = cb->args[1];
 810         read_lock(&dev_base_lock);
 811         for (dev=dev_base, idx=0; dev; dev = dev->next, idx++) {
 812                 if (idx < s_idx)
 813                         continue;
 814                 if (idx > s_idx)
 815                         s_q_idx = 0;
 816                 read_lock(&qdisc_tree_lock);
 817                 for (q = dev->qdisc_list, q_idx = 0; q;
 818                      q = q->next, q_idx++) {
 819                         if (q_idx < s_q_idx)
 820                                 continue;
 821                         if (tc_fill_qdisc(skb, q, 0, NETLINK_CB(cb->skb).pid,
 822                                           cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0) {
 823                                 read_unlock(&qdisc_tree_lock);
 824                                 goto done;
 825                         }
 826                 }
 827                 read_unlock(&qdisc_tree_lock);
 828         }
 829
 830 done:
 831         read_unlock(&dev_base_lock);
 832
 833         cb->args[0] = idx;
 834         cb->args[1] = q_idx;
 835
 836         return skb->len;
 837 }
 838
 839
 840
 841 /************************************************
 842  *      Traffic classes manipulation.           *
 843  ************************************************/
 844
 845
 846
 847 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 848 {
 849         struct tcmsg *tcm = NLMSG_DATA(n);
 850         struct rtattr **tca = arg;
 851         struct net_device *dev;
 852         struct Qdisc *q = NULL;
 853         struct Qdisc_class_ops *cops;
 854         unsigned long cl = 0;
 855         unsigned long new_cl;
 856         u32 pid = tcm->tcm_parent;
 857         u32 clid = tcm->tcm_handle;
 858         u32 qid = TC_H_MAJ(clid);
 859         int err;
 860
 861         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 862                 return -ENODEV;
 863
 864         /*
 865            parent == TC_H_UNSPEC - unspecified parent.
 866            parent == TC_H_ROOT   - class is root, which has no parent.
 867            parent == X:0         - parent is root class.
 868            parent == X:Y         - parent is a node in hierarchy.
 869            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
 870
 871            handle == 0:0         - generate handle from kernel pool.
 872            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
 873            handle == X:Y         - clear.
 874            handle == X:0         - root class.
 875          */
 876
 877         /* Step 1. Determine qdisc handle X:0 */
 878
 879         if (pid != TC_H_ROOT) {
 880                 u32 qid1 = TC_H_MAJ(pid);
 881
 882                 if (qid && qid1) {
 883                         /* If both majors are known, they must be identical. */
 884                         if (qid != qid1)
 885                                 return -EINVAL;
 886                 } else if (qid1) {
 887                         qid = qid1;
 888                 } else if (qid == 0)
 889                         qid = dev->qdisc_sleeping->handle;
 890
 891                 /* Now qid is genuine qdisc handle consistent
 892                    both with parent and child.
 893
 894                    TC_H_MAJ(pid) still may be unspecified, complete it now.
 895                  */
 896                 if (pid)
 897                         pid = TC_H_MAKE(qid, pid);
 898         } else {
 899                 if (qid == 0)
 900                         qid = dev->qdisc_sleeping->handle;
 901         }
 902
 903         /* OK. Locate qdisc */
 904         if ((q = qdisc_lookup(dev, qid)) == NULL)
 905                 return -ENOENT;
 906
 907         /* An check that it supports classes */
 908         cops = q->ops->cl_ops;
 909         if (cops == NULL)
 910                 return -EINVAL;
 911
 912         /* Now try to get class */
 913         if (clid == 0) {
 914                 if (pid == TC_H_ROOT)
 915                         clid = qid;
 916         } else
 917                 clid = TC_H_MAKE(qid, clid);
 918
 919         if (clid)
 920                 cl = cops->get(q, clid);
 921
 922         if (cl == 0) {
 923                 err = -ENOENT;
 924                 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE))
 925                         goto out;
 926         } else {
 927                 switch (n->nlmsg_type) {
 928                 case RTM_NEWTCLASS:
 929                         err = -EEXIST;
 930                         if (n->nlmsg_flags&NLM_F_EXCL)
 931                                 goto out;
 932                         break;
 933                 case RTM_DELTCLASS:
 934                         err = cops->delete(q, cl);
 935                         if (err == 0)
 936                                 tclass_notify(skb, n, q, cl, RTM_DELTCLASS);
 937                         goto out;
 938                 case RTM_GETTCLASS:
 939                         err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS);
 940                         goto out;
 941                 default:
 942                         err = -EINVAL;
 943                         goto out;
 944                 }
 945         }
 946
 947         new_cl = cl;
 948         err = cops->change(q, clid, pid, tca, &new_cl);
 949         if (err == 0)
 950                 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
 951
 952 out:
 953         if (cl)
 954                 cops->put(q, cl);
 955
 956         return err;
 957 }
 958
 959
 960 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
 961                           unsigned long cl,
 962                           u32 pid, u32 seq, unsigned flags, int event)
 963 {
 964         struct tcmsg *tcm;
 965         struct nlmsghdr  *nlh;
 966         unsigned char    *b = skb->tail;
 967
 968         nlh = NLMSG_PUT(skb, pid, seq, event, sizeof(*tcm));
 969         nlh->nlmsg_flags = flags;
 970         tcm = NLMSG_DATA(nlh);
 971         tcm->tcm_family = AF_UNSPEC;
 972         tcm->tcm_ifindex = q->dev ? q->dev->ifindex : 0;
 973         tcm->tcm_parent = q->handle;
 974         tcm->tcm_handle = q->handle;
 975         tcm->tcm_info = 0;
 976         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
 977         if (q->ops->cl_ops->dump && q->ops->cl_ops->dump(q, cl, skb, tcm) < 0)
 978                 goto rtattr_failure;
 979         nlh->nlmsg_len = skb->tail - b;
 980         return skb->len;
 981
 982 nlmsg_failure:
 983 rtattr_failure:
 984         skb_trim(skb, b - skb->data);
 985         return -1;
 986 }
 987
 988 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
 989                           struct Qdisc *q, unsigned long cl, int event)
 990 {
 991         struct sk_buff *skb;
 992         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
 993
 994         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
 995         if (!skb)
 996                 return -ENOBUFS;
 997
 998         if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) {
 999                 kfree_skb(skb);
1000                 return -EINVAL;
1001         }
1002
1003         return rtnetlink_send(skb, pid, RTMGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1004 }
1005
1006 struct qdisc_dump_args
1007 {
1008         struct qdisc_walker w;
1009         struct sk_buff *skb;
1010         struct netlink_callback *cb;
1011 };
1012
1013 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg)
1014 {
1015         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
1016
1017         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid,
1018                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS);
1019 }
1020
1021 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
1022 {
1023         int t;
1024         int s_t;
1025         struct net_device *dev;
1026         struct Qdisc *q;
1027         struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh);
1028         struct qdisc_dump_args arg;
1029
1030         if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm)))
1031                 return 0;
1032         if ((dev = dev_get_by_index(tcm->tcm_ifindex)) == NULL)
1033                 return 0;
1034
1035         s_t = cb->args[0];
1036
1037         read_lock(&qdisc_tree_lock);
1038         for (q=dev->qdisc_list, t=0; q; q = q->next, t++) {
1039                 if (t < s_t) continue;
1040                 if (!q->ops->cl_ops) continue;
1041                 if (tcm->tcm_parent && TC_H_MAJ(tcm->tcm_parent) != q->handle)
1042                         continue;
1043                 if (t > s_t)
1044                         memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
1045                 arg.w.fn = qdisc_class_dump;
1046                 arg.skb = skb;
1047                 arg.cb = cb;
1048                 arg.w.stop  = 0;
1049                 arg.w.skip = cb->args[1];
1050                 arg.w.count = 0;
1051                 q->ops->cl_ops->walk(q, &arg.w);
1052                 cb->args[1] = arg.w.count;
1053                 if (arg.w.stop)
1054                         break;
1055         }
1056         read_unlock(&qdisc_tree_lock);
1057
1058         cb->args[0] = t;
1059
1060         dev_put(dev);
1061         return skb->len;
1062 }
1063
1064 int psched_us_per_tick = 1;
1065 int psched_tick_per_us = 1;
1066
1067 #ifdef CONFIG_PROC_FS
1068 static int psched_show(struct seq_file *seq, void *v)
1069 {
1070         seq_printf(seq, "%08x %08x %08x %08x\n",
1071                       psched_tick_per_us, psched_us_per_tick,
1072                       1000000, HZ);
1073
1074         return 0;
1075 }
1076
1077 static int psched_open(struct inode *inode, struct file *file)
1078 {
1079         return single_open(file, psched_show, PDE(inode)->data);
1080 }
1081
1082 static struct file_operations psched_fops = {
1083         .owner = THIS_MODULE,
1084         .open = psched_open,
1085         .read  = seq_read,
1086         .llseek = seq_lseek,
1087         .release = single_release,
1088 };
1089 #endif
1090
1091 #if PSCHED_CLOCK_SOURCE == PSCHED_GETTIMEOFDAY
1092 int psched_tod_diff(int delta_sec, int bound)
1093 {
1094         int delta;
1095
1096         if (bound <= 1000000 || delta_sec > (0x7FFFFFFF/1000000)-1)
1097                 return bound;
1098         delta = delta_sec * 1000000;
1099         if (delta > bound)
1100                 delta = bound;
1101         return delta;
1102 }
1103 EXPORT_SYMBOL(psched_tod_diff);
1104 #endif
1105
1106 psched_time_t psched_time_base;
1107
1108 #if PSCHED_CLOCK_SOURCE == PSCHED_CPU
1109 psched_tdiff_t psched_clock_per_hz;
1110 int psched_clock_scale;
1111 EXPORT_SYMBOL(psched_clock_per_hz);
1112 EXPORT_SYMBOL(psched_clock_scale);
1113 #endif
1114
1115 #ifdef PSCHED_WATCHER
1116 PSCHED_WATCHER psched_time_mark;
1117 EXPORT_SYMBOL(psched_time_mark);
1118 EXPORT_SYMBOL(psched_time_base);
1119
1120 static void psched_tick(unsigned long);
1121
1122 static struct timer_list psched_timer = TIMER_INITIALIZER(psched_tick, 0, 0);
1123
1124 static void psched_tick(unsigned long dummy)
1125 {
1126 #if PSCHED_CLOCK_SOURCE == PSCHED_CPU
1127         psched_time_t dummy_stamp;
1128         PSCHED_GET_TIME(dummy_stamp);
1129         /* It is OK up to 4GHz cpu */
1130         psched_timer.expires = jiffies + 1*HZ;
1131 #else
1132         unsigned long now = jiffies;
1133         psched_time_base += ((u64)(now-psched_time_mark))<<PSCHED_JSCALE;
1134         psched_time_mark = now;
1135         psched_timer.expires = now + 60*60*HZ;
1136 #endif
1137         add_timer(&psched_timer);
1138 }
1139 #endif
1140
1141 #if PSCHED_CLOCK_SOURCE == PSCHED_CPU
1142 int __init psched_calibrate_clock(void)
1143 {
1144         psched_time_t stamp, stamp1;
1145         struct timeval tv, tv1;
1146         psched_tdiff_t delay;
1147         long rdelay;
1148         unsigned long stop;
1149
1150 #ifdef PSCHED_WATCHER
1151         psched_tick(0);
1152 #endif
1153         stop = jiffies + HZ/10;
1154         PSCHED_GET_TIME(stamp);
1155         do_gettimeofday(&tv);
1156         while (time_before(jiffies, stop)) {
1157                 barrier();
1158                 cpu_relax();
1159         }
1160         PSCHED_GET_TIME(stamp1);
1161         do_gettimeofday(&tv1);
1162
1163         delay = PSCHED_TDIFF(stamp1, stamp);
1164         rdelay = tv1.tv_usec - tv.tv_usec;
1165         rdelay += (tv1.tv_sec - tv.tv_sec)*1000000;
1166         if (rdelay > delay)
1167                 return -1;
1168         delay /= rdelay;
1169         psched_tick_per_us = delay;
1170         while ((delay>>=1) != 0)
1171                 psched_clock_scale++;
1172         psched_us_per_tick = 1<<psched_clock_scale;
1173         psched_clock_per_hz = (psched_tick_per_us*(1000000/HZ))>>psched_clock_scale;
1174         return 0;
1175 }
1176 #endif
1177
1178 static int __init pktsched_init(void)
1179 {
1180         struct rtnetlink_link *link_p;
1181
1182 #if PSCHED_CLOCK_SOURCE == PSCHED_CPU
1183         if (psched_calibrate_clock() < 0)
1184                 return -1;
1185 #elif PSCHED_CLOCK_SOURCE == PSCHED_JIFFIES
1186         psched_tick_per_us = HZ<<PSCHED_JSCALE;
1187         psched_us_per_tick = 1000000;
1188 #ifdef PSCHED_WATCHER
1189         psched_tick(0);
1190 #endif
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);