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