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