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, unsigned 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_PUT(skb, pid, seq, event, sizeof(*tcm));
 771         nlh->nlmsg_flags = flags;
 772         tcm = NLMSG_DATA(nlh);
 773         tcm->tcm_family = AF_UNSPEC;
 774         tcm->tcm_ifindex = q->dev->ifindex;
 775         tcm->tcm_parent = clid;
 776         tcm->tcm_handle = q->handle;
 777         tcm->tcm_info = atomic_read(&q->refcnt);
 778         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
 779         if (q->ops->dump && q->ops->dump(q, skb) < 0)
 780                 goto rtattr_failure;
 781         q->qstats.qlen = q->q.qlen;
 782
 783         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
 784                         TCA_XSTATS, q->stats_lock, &d) < 0)
 785                 goto rtattr_failure;
 786
 787         if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0)
 788                 goto rtattr_failure;
 789
 790         if (gnet_stats_copy_basic(&d, &q->bstats) < 0 ||
 791 #ifdef CONFIG_NET_ESTIMATOR
 792             gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 ||
 793 #endif
 794             gnet_stats_copy_queue(&d, &q->qstats) < 0)
 795                 goto rtattr_failure;
 796
 797         if (gnet_stats_finish_copy(&d) < 0)
 798                 goto rtattr_failure;
 799
 800         nlh->nlmsg_len = skb->tail - b;
 801         return skb->len;
 802
 803 nlmsg_failure:
 804 rtattr_failure:
 805         skb_trim(skb, b - skb->data);
 806         return -1;
 807 }
 808
 809 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n,
 810                         u32 clid, struct Qdisc *old, struct Qdisc *new)
 811 {
 812         struct sk_buff *skb;
 813         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
 814
 815         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
 816         if (!skb)
 817                 return -ENOBUFS;
 818
 819         if (old && old->handle) {
 820                 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0)
 821                         goto err_out;
 822         }
 823         if (new) {
 824                 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
 825                         goto err_out;
 826         }
 827
 828         if (skb->len)
 829                 return rtnetlink_send(skb, pid, RTMGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
 830
 831 err_out:
 832         kfree_skb(skb);
 833         return -EINVAL;
 834 }
 835
 836 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
 837 {
 838         int idx, q_idx;
 839         int s_idx, s_q_idx;
 840         struct net_device *dev;
 841         struct Qdisc *q;
 842
 843         s_idx = cb->args[0];
 844         s_q_idx = q_idx = cb->args[1];
 845         read_lock(&dev_base_lock);
 846         for (dev=dev_base, idx=0; dev; dev = dev->next, idx++) {
 847                 if (idx < s_idx)
 848                         continue;
 849                 if (idx > s_idx)
 850                         s_q_idx = 0;
 851                 read_lock_bh(&qdisc_tree_lock);
 852                 q_idx = 0;
 853                 list_for_each_entry(q, &dev->qdisc_list, list) {
 854                         if (q_idx < s_q_idx) {
 855                                 q_idx++;
 856                                 continue;
 857                         }
 858                         if (tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
 859                                           cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0) {
 860                                 read_unlock_bh(&qdisc_tree_lock);
 861                                 goto done;
 862                         }
 863                         q_idx++;
 864                 }
 865                 read_unlock_bh(&qdisc_tree_lock);
 866         }
 867
 868 done:
 869         read_unlock(&dev_base_lock);
 870
 871         cb->args[0] = idx;
 872         cb->args[1] = q_idx;
 873
 874         return skb->len;
 875 }
 876
 877
 878
 879 /************************************************
 880  *      Traffic classes manipulation.           *
 881  ************************************************/
 882
 883
 884
 885 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 886 {
 887         struct tcmsg *tcm = NLMSG_DATA(n);
 888         struct rtattr **tca = arg;
 889         struct net_device *dev;
 890         struct Qdisc *q = NULL;
 891         struct Qdisc_class_ops *cops;
 892         unsigned long cl = 0;
 893         unsigned long new_cl;
 894         u32 pid = tcm->tcm_parent;
 895         u32 clid = tcm->tcm_handle;
 896         u32 qid = TC_H_MAJ(clid);
 897         int err;
 898
 899         if ((dev = __dev_get_by_index(tcm->tcm_ifindex)) == NULL)
 900                 return -ENODEV;
 901
 902         /*
 903            parent == TC_H_UNSPEC - unspecified parent.
 904            parent == TC_H_ROOT   - class is root, which has no parent.
 905            parent == X:0         - parent is root class.
 906            parent == X:Y         - parent is a node in hierarchy.
 907            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
 908
 909            handle == 0:0         - generate handle from kernel pool.
 910            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
 911            handle == X:Y         - clear.
 912            handle == X:0         - root class.
 913          */
 914
 915         /* Step 1. Determine qdisc handle X:0 */
 916
 917         if (pid != TC_H_ROOT) {
 918                 u32 qid1 = TC_H_MAJ(pid);
 919
 920                 if (qid && qid1) {
 921                         /* If both majors are known, they must be identical. */
 922                         if (qid != qid1)
 923                                 return -EINVAL;
 924                 } else if (qid1) {
 925                         qid = qid1;
 926                 } else if (qid == 0)
 927                         qid = dev->qdisc_sleeping->handle;
 928
 929                 /* Now qid is genuine qdisc handle consistent
 930                    both with parent and child.
 931
 932                    TC_H_MAJ(pid) still may be unspecified, complete it now.
 933                  */
 934                 if (pid)
 935                         pid = TC_H_MAKE(qid, pid);
 936         } else {
 937                 if (qid == 0)
 938                         qid = dev->qdisc_sleeping->handle;
 939         }
 940
 941         /* OK. Locate qdisc */
 942         if ((q = qdisc_lookup(dev, qid)) == NULL)
 943                 return -ENOENT;
 944
 945         /* An check that it supports classes */
 946         cops = q->ops->cl_ops;
 947         if (cops == NULL)
 948                 return -EINVAL;
 949
 950         /* Now try to get class */
 951         if (clid == 0) {
 952                 if (pid == TC_H_ROOT)
 953                         clid = qid;
 954         } else
 955                 clid = TC_H_MAKE(qid, clid);
 956
 957         if (clid)
 958                 cl = cops->get(q, clid);
 959
 960         if (cl == 0) {
 961                 err = -ENOENT;
 962                 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE))
 963                         goto out;
 964         } else {
 965                 switch (n->nlmsg_type) {
 966                 case RTM_NEWTCLASS:
 967                         err = -EEXIST;
 968                         if (n->nlmsg_flags&NLM_F_EXCL)
 969                                 goto out;
 970                         break;
 971                 case RTM_DELTCLASS:
 972                         err = cops->delete(q, cl);
 973                         if (err == 0)
 974                                 tclass_notify(skb, n, q, cl, RTM_DELTCLASS);
 975                         goto out;
 976                 case RTM_GETTCLASS:
 977                         err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS);
 978                         goto out;
 979                 default:
 980                         err = -EINVAL;
 981                         goto out;
 982                 }
 983         }
 984
 985         new_cl = cl;
 986         err = cops->change(q, clid, pid, tca, &new_cl);
 987         if (err == 0)
 988                 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
 989
 990 out:
 991         if (cl)
 992                 cops->put(q, cl);
 993
 994         return err;
 995 }
 996
 997
 998 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
 999                           unsigned long cl,
1000                           u32 pid, u32 seq, unsigned flags, int event)
1001 {
1002         struct tcmsg *tcm;
1003         struct nlmsghdr  *nlh;
1004         unsigned char    *b = skb->tail;
1005         struct gnet_dump d;
1006         struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1007
1008         nlh = NLMSG_PUT(skb, pid, seq, event, sizeof(*tcm));
1009         nlh->nlmsg_flags = flags;
1010         tcm = NLMSG_DATA(nlh);
1011         tcm->tcm_family = AF_UNSPEC;
1012         tcm->tcm_ifindex = q->dev->ifindex;
1013         tcm->tcm_parent = q->handle;
1014         tcm->tcm_handle = q->handle;
1015         tcm->tcm_info = 0;
1016         RTA_PUT(skb, TCA_KIND, IFNAMSIZ, q->ops->id);
1017         if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1018                 goto rtattr_failure;
1019
1020         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1021                         TCA_XSTATS, q->stats_lock, &d) < 0)
1022                 goto rtattr_failure;
1023
1024         if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1025                 goto rtattr_failure;
1026
1027         if (gnet_stats_finish_copy(&d) < 0)
1028                 goto rtattr_failure;
1029
1030         nlh->nlmsg_len = skb->tail - b;
1031         return skb->len;
1032
1033 nlmsg_failure:
1034 rtattr_failure:
1035         skb_trim(skb, b - skb->data);
1036         return -1;
1037 }
1038
1039 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1040                           struct Qdisc *q, unsigned long cl, int event)
1041 {
1042         struct sk_buff *skb;
1043         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1044
1045         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1046         if (!skb)
1047                 return -ENOBUFS;
1048
1049         if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) {
1050                 kfree_skb(skb);
1051                 return -EINVAL;
1052         }
1053
1054         return rtnetlink_send(skb, pid, RTMGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1055 }
1056
1057 struct qdisc_dump_args
1058 {
1059         struct qdisc_walker w;
1060         struct sk_buff *skb;
1061         struct netlink_callback *cb;
1062 };
1063
1064 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg)
1065 {
1066         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
1067
1068         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid,
1069                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS);
1070 }
1071
1072 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
1073 {
1074         int t;
1075         int s_t;
1076         struct net_device *dev;
1077         struct Qdisc *q;
1078         struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh);
1079         struct qdisc_dump_args arg;
1080
1081         if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm)))
1082                 return 0;
1083         if ((dev = dev_get_by_index(tcm->tcm_ifindex)) == NULL)
1084                 return 0;
1085
1086         s_t = cb->args[0];
1087         t = 0;
1088
1089         read_lock_bh(&qdisc_tree_lock);
1090         list_for_each_entry(q, &dev->qdisc_list, list) {
1091                 if (t < s_t || !q->ops->cl_ops ||
1092                     (tcm->tcm_parent &&
1093                      TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
1094                         t++;
1095                         continue;
1096                 }
1097                 if (t > s_t)
1098                         memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
1099                 arg.w.fn = qdisc_class_dump;
1100                 arg.skb = skb;
1101                 arg.cb = cb;
1102                 arg.w.stop  = 0;
1103                 arg.w.skip = cb->args[1];
1104                 arg.w.count = 0;
1105                 q->ops->cl_ops->walk(q, &arg.w);
1106                 cb->args[1] = arg.w.count;
1107                 if (arg.w.stop)
1108                         break;
1109                 t++;
1110         }
1111         read_unlock_bh(&qdisc_tree_lock);
1112
1113         cb->args[0] = t;
1114
1115         dev_put(dev);
1116         return skb->len;
1117 }
1118
1119 /* Main classifier routine: scans classifier chain attached
1120    to this qdisc, (optionally) tests for protocol and asks
1121    specific classifiers.
1122  */
1123 int tc_classify(struct sk_buff *skb, struct tcf_proto *tp,
1124         struct tcf_result *res)
1125 {
1126         int err = 0;
1127         u32 protocol = skb->protocol;
1128 #ifdef CONFIG_NET_CLS_ACT
1129         struct tcf_proto *otp = tp;
1130 reclassify:
1131 #endif
1132         protocol = skb->protocol;
1133
1134         for ( ; tp; tp = tp->next) {
1135                 if ((tp->protocol == protocol ||
1136                         tp->protocol == __constant_htons(ETH_P_ALL)) &&
1137                         (err = tp->classify(skb, tp, res)) >= 0) {
1138 #ifdef CONFIG_NET_CLS_ACT
1139                         if ( TC_ACT_RECLASSIFY == err) {
1140                                 __u32 verd = (__u32) G_TC_VERD(skb->tc_verd);
1141                                 tp = otp;
1142
1143                                 if (MAX_REC_LOOP < verd++) {
1144                                         printk("rule prio %d protocol %02x reclassify is buggy packet dropped\n",
1145                                                 tp->prio&0xffff, ntohs(tp->protocol));
1146                                         return TC_ACT_SHOT;
1147                                 }
1148                                 skb->tc_verd = SET_TC_VERD(skb->tc_verd,verd);
1149                                 goto reclassify;
1150                         } else {
1151                                 if (skb->tc_verd)
1152                                         skb->tc_verd = SET_TC_VERD(skb->tc_verd,0);
1153                                 return err;
1154                         }
1155 #else
1156
1157                         return err;
1158 #endif
1159                 }
1160
1161         }
1162         return -1;
1163 }
1164
1165 static int psched_us_per_tick = 1;
1166 static int psched_tick_per_us = 1;
1167
1168 #ifdef CONFIG_PROC_FS
1169 static int psched_show(struct seq_file *seq, void *v)
1170 {
1171         seq_printf(seq, "%08x %08x %08x %08x\n",
1172                       psched_tick_per_us, psched_us_per_tick,
1173                       1000000, HZ);
1174
1175         return 0;
1176 }
1177
1178 static int psched_open(struct inode *inode, struct file *file)
1179 {
1180         return single_open(file, psched_show, PDE(inode)->data);
1181 }
1182
1183 static struct file_operations psched_fops = {
1184         .owner = THIS_MODULE,
1185         .open = psched_open,
1186         .read  = seq_read,
1187         .llseek = seq_lseek,
1188         .release = single_release,
1189 };
1190 #endif
1191
1192 #ifdef CONFIG_NET_SCH_CLK_CPU
1193 psched_tdiff_t psched_clock_per_hz;
1194 int psched_clock_scale;
1195 EXPORT_SYMBOL(psched_clock_per_hz);
1196 EXPORT_SYMBOL(psched_clock_scale);
1197
1198 psched_time_t psched_time_base;
1199 cycles_t psched_time_mark;
1200 EXPORT_SYMBOL(psched_time_mark);
1201 EXPORT_SYMBOL(psched_time_base);
1202
1203 /*
1204  * Periodically adjust psched_time_base to avoid overflow
1205  * with 32-bit get_cycles(). Safe up to 4GHz CPU.
1206  */
1207 static void psched_tick(unsigned long);
1208 static struct timer_list psched_timer = TIMER_INITIALIZER(psched_tick, 0, 0);
1209
1210 static void psched_tick(unsigned long dummy)
1211 {
1212         if (sizeof(cycles_t) == sizeof(u32)) {
1213                 psched_time_t dummy_stamp;
1214                 PSCHED_GET_TIME(dummy_stamp);
1215                 psched_timer.expires = jiffies + 1*HZ;
1216                 add_timer(&psched_timer);
1217         }
1218 }
1219
1220 int __init psched_calibrate_clock(void)
1221 {
1222         psched_time_t stamp, stamp1;
1223         struct timeval tv, tv1;
1224         psched_tdiff_t delay;
1225         long rdelay;
1226         unsigned long stop;
1227
1228         psched_tick(0);
1229         stop = jiffies + HZ/10;
1230         PSCHED_GET_TIME(stamp);
1231         do_gettimeofday(&tv);
1232         while (time_before(jiffies, stop)) {
1233                 barrier();
1234                 cpu_relax();
1235         }
1236         PSCHED_GET_TIME(stamp1);
1237         do_gettimeofday(&tv1);
1238
1239         delay = PSCHED_TDIFF(stamp1, stamp);
1240         rdelay = tv1.tv_usec - tv.tv_usec;
1241         rdelay += (tv1.tv_sec - tv.tv_sec)*1000000;
1242         if (rdelay > delay)
1243                 return -1;
1244         delay /= rdelay;
1245         psched_tick_per_us = delay;
1246         while ((delay>>=1) != 0)
1247                 psched_clock_scale++;
1248         psched_us_per_tick = 1<<psched_clock_scale;
1249         psched_clock_per_hz = (psched_tick_per_us*(1000000/HZ))>>psched_clock_scale;
1250         return 0;
1251 }
1252 #endif
1253
1254 static int __init pktsched_init(void)
1255 {
1256         struct rtnetlink_link *link_p;
1257
1258 #ifdef CONFIG_NET_SCH_CLK_CPU
1259         if (psched_calibrate_clock() < 0)
1260                 return -1;
1261 #elif defined(CONFIG_NET_SCH_CLK_JIFFIES)
1262         psched_tick_per_us = HZ<<PSCHED_JSCALE;
1263         psched_us_per_tick = 1000000;
1264 #endif
1265
1266         link_p = rtnetlink_links[PF_UNSPEC];
1267
1268         /* Setup rtnetlink links. It is made here to avoid
1269            exporting large number of public symbols.
1270          */
1271
1272         if (link_p) {
1273                 link_p[RTM_NEWQDISC-RTM_BASE].doit = tc_modify_qdisc;
1274                 link_p[RTM_DELQDISC-RTM_BASE].doit = tc_get_qdisc;
1275                 link_p[RTM_GETQDISC-RTM_BASE].doit = tc_get_qdisc;
1276                 link_p[RTM_GETQDISC-RTM_BASE].dumpit = tc_dump_qdisc;
1277                 link_p[RTM_NEWTCLASS-RTM_BASE].doit = tc_ctl_tclass;
1278                 link_p[RTM_DELTCLASS-RTM_BASE].doit = tc_ctl_tclass;
1279                 link_p[RTM_GETTCLASS-RTM_BASE].doit = tc_ctl_tclass;
1280                 link_p[RTM_GETTCLASS-RTM_BASE].dumpit = tc_dump_tclass;
1281         }
1282
1283         register_qdisc(&pfifo_qdisc_ops);
1284         register_qdisc(&bfifo_qdisc_ops);
1285         proc_net_fops_create("psched", 0, &psched_fops);
1286
1287         return 0;
1288 }
1289
1290 subsys_initcall(pktsched_init);
1291
1292 EXPORT_SYMBOL(qdisc_get_rtab);
1293 EXPORT_SYMBOL(qdisc_put_rtab);
1294 EXPORT_SYMBOL(register_qdisc);
1295 EXPORT_SYMBOL(unregister_qdisc);
1296 EXPORT_SYMBOL(tc_classify);