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 #include <linux/lockdep.h>
  31
  32 #include <net/net_namespace.h>
  33 #include <net/sock.h>
  34 #include <net/netlink.h>
  35 #include <net/pkt_sched.h>
  36
  37 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n, u32 clid,
  38                         struct Qdisc *old, struct Qdisc *new);
  39 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
  40                          struct Qdisc *q, unsigned long cl, int event);
  41
  42 /*
  43
  44    Short review.
  45    -------------
  46
  47    This file consists of two interrelated parts:
  48
  49    1. queueing disciplines manager frontend.
  50    2. traffic classes manager frontend.
  51
  52    Generally, queueing discipline ("qdisc") is a black box,
  53    which is able to enqueue packets and to dequeue them (when
  54    device is ready to send something) in order and at times
  55    determined by algorithm hidden in it.
  56
  57    qdisc's are divided to two categories:
  58    - "queues", which have no internal structure visible from outside.
  59    - "schedulers", which split all the packets to "traffic classes",
  60      using "packet classifiers" (look at cls_api.c)
  61
  62    In turn, classes may have child qdiscs (as rule, queues)
  63    attached to them etc. etc. etc.
  64
  65    The goal of the routines in this file is to translate
  66    information supplied by user in the form of handles
  67    to more intelligible for kernel form, to make some sanity
  68    checks and part of work, which is common to all qdiscs
  69    and to provide rtnetlink notifications.
  70
  71    All real intelligent work is done inside qdisc modules.
  72
  73
  74
  75    Every discipline has two major routines: enqueue and dequeue.
  76
  77    ---dequeue
  78
  79    dequeue usually returns a skb to send. It is allowed to return NULL,
  80    but it does not mean that queue is empty, it just means that
  81    discipline does not want to send anything this time.
  82    Queue is really empty if q->q.qlen == 0.
  83    For complicated disciplines with multiple queues q->q is not
  84    real packet queue, but however q->q.qlen must be valid.
  85
  86    ---enqueue
  87
  88    enqueue returns 0, if packet was enqueued successfully.
  89    If packet (this one or another one) was dropped, it returns
  90    not zero error code.
  91    NET_XMIT_DROP        - this packet dropped
  92      Expected action: do not backoff, but wait until queue will clear.
  93    NET_XMIT_CN          - probably this packet enqueued, but another one dropped.
  94      Expected action: backoff or ignore
  95    NET_XMIT_POLICED     - dropped by police.
  96      Expected action: backoff or error to real-time apps.
  97
  98    Auxiliary routines:
  99
 100    ---requeue
 101
 102    requeues once dequeued packet. It is used for non-standard or
 103    just buggy devices, which can defer output even if netif_queue_stopped()=0.
 104
 105    ---reset
 106
 107    returns qdisc to initial state: purge all buffers, clear all
 108    timers, counters (except for statistics) etc.
 109
 110    ---init
 111
 112    initializes newly created qdisc.
 113
 114    ---destroy
 115
 116    destroys resources allocated by init and during lifetime of qdisc.
 117
 118    ---change
 119
 120    changes qdisc parameters.
 121  */
 122
 123 /* Protects list of registered TC modules. It is pure SMP lock. */
 124 static DEFINE_RWLOCK(qdisc_mod_lock);
 125
 126
 127 /************************************************
 128  *      Queueing disciplines manipulation.      *
 129  ************************************************/
 130
 131
 132 /* The list of all installed queueing disciplines. */
 133
 134 static struct Qdisc_ops *qdisc_base;
 135
 136 /* Register/uregister queueing discipline */
 137
 138 int register_qdisc(struct Qdisc_ops *qops)
 139 {
 140         struct Qdisc_ops *q, **qp;
 141         int rc = -EEXIST;
 142
 143         write_lock(&qdisc_mod_lock);
 144         for (qp = &qdisc_base; (q = *qp) != NULL; qp = &q->next)
 145                 if (!strcmp(qops->id, q->id))
 146                         goto out;
 147
 148         if (qops->enqueue == NULL)
 149                 qops->enqueue = noop_qdisc_ops.enqueue;
 150         if (qops->requeue == NULL)
 151                 qops->requeue = noop_qdisc_ops.requeue;
 152         if (qops->dequeue == NULL)
 153                 qops->dequeue = noop_qdisc_ops.dequeue;
 154
 155         qops->next = NULL;
 156         *qp = qops;
 157         rc = 0;
 158 out:
 159         write_unlock(&qdisc_mod_lock);
 160         return rc;
 161 }
 162 EXPORT_SYMBOL(register_qdisc);
 163
 164 int unregister_qdisc(struct Qdisc_ops *qops)
 165 {
 166         struct Qdisc_ops *q, **qp;
 167         int err = -ENOENT;
 168
 169         write_lock(&qdisc_mod_lock);
 170         for (qp = &qdisc_base; (q=*qp)!=NULL; qp = &q->next)
 171                 if (q == qops)
 172                         break;
 173         if (q) {
 174                 *qp = q->next;
 175                 q->next = NULL;
 176                 err = 0;
 177         }
 178         write_unlock(&qdisc_mod_lock);
 179         return err;
 180 }
 181 EXPORT_SYMBOL(unregister_qdisc);
 182
 183 /* We know handle. Find qdisc among all qdisc's attached to device
 184    (root qdisc, all its children, children of children etc.)
 185  */
 186
 187 struct Qdisc *qdisc_match_from_root(struct Qdisc *root, u32 handle)
 188 {
 189         struct Qdisc *q;
 190
 191         if (!(root->flags & TCQ_F_BUILTIN) &&
 192             root->handle == handle)
 193                 return root;
 194
 195         list_for_each_entry(q, &root->list, list) {
 196                 if (q->handle == handle)
 197                         return q;
 198         }
 199         return NULL;
 200 }
 201
 202 /*
 203  * This lock is needed until some qdiscs stop calling qdisc_tree_decrease_qlen()
 204  * without rtnl_lock(); currently hfsc_dequeue(), netem_dequeue(), tbf_dequeue()
 205  */
 206 static DEFINE_SPINLOCK(qdisc_list_lock);
 207
 208 static void qdisc_list_add(struct Qdisc *q)
 209 {
 210         if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
 211                 spin_lock_bh(&qdisc_list_lock);
 212                 list_add_tail(&q->list, &qdisc_root_sleeping(q)->list);
 213                 spin_unlock_bh(&qdisc_list_lock);
 214         }
 215 }
 216
 217 void qdisc_list_del(struct Qdisc *q)
 218 {
 219         if ((q->parent != TC_H_ROOT) && !(q->flags & TCQ_F_INGRESS)) {
 220                 spin_lock_bh(&qdisc_list_lock);
 221                 list_del(&q->list);
 222                 spin_unlock_bh(&qdisc_list_lock);
 223         }
 224 }
 225 EXPORT_SYMBOL(qdisc_list_del);
 226
 227 struct Qdisc *qdisc_lookup(struct net_device *dev, u32 handle)
 228 {
 229         unsigned int i;
 230         struct Qdisc *q;
 231
 232         spin_lock_bh(&qdisc_list_lock);
 233
 234         for (i = 0; i < dev->num_tx_queues; i++) {
 235                 struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
 236                 struct Qdisc *txq_root = txq->qdisc_sleeping;
 237
 238                 q = qdisc_match_from_root(txq_root, handle);
 239                 if (q)
 240                         goto unlock;
 241         }
 242
 243         q = qdisc_match_from_root(dev->rx_queue.qdisc_sleeping, handle);
 244
 245 unlock:
 246         spin_unlock_bh(&qdisc_list_lock);
 247
 248         return q;
 249 }
 250
 251 static struct Qdisc *qdisc_leaf(struct Qdisc *p, u32 classid)
 252 {
 253         unsigned long cl;
 254         struct Qdisc *leaf;
 255         const struct Qdisc_class_ops *cops = p->ops->cl_ops;
 256
 257         if (cops == NULL)
 258                 return NULL;
 259         cl = cops->get(p, classid);
 260
 261         if (cl == 0)
 262                 return NULL;
 263         leaf = cops->leaf(p, cl);
 264         cops->put(p, cl);
 265         return leaf;
 266 }
 267
 268 /* Find queueing discipline by name */
 269
 270 static struct Qdisc_ops *qdisc_lookup_ops(struct nlattr *kind)
 271 {
 272         struct Qdisc_ops *q = NULL;
 273
 274         if (kind) {
 275                 read_lock(&qdisc_mod_lock);
 276                 for (q = qdisc_base; q; q = q->next) {
 277                         if (nla_strcmp(kind, q->id) == 0) {
 278                                 if (!try_module_get(q->owner))
 279                                         q = NULL;
 280                                 break;
 281                         }
 282                 }
 283                 read_unlock(&qdisc_mod_lock);
 284         }
 285         return q;
 286 }
 287
 288 static struct qdisc_rate_table *qdisc_rtab_list;
 289
 290 struct qdisc_rate_table *qdisc_get_rtab(struct tc_ratespec *r, struct nlattr *tab)
 291 {
 292         struct qdisc_rate_table *rtab;
 293
 294         for (rtab = qdisc_rtab_list; rtab; rtab = rtab->next) {
 295                 if (memcmp(&rtab->rate, r, sizeof(struct tc_ratespec)) == 0) {
 296                         rtab->refcnt++;
 297                         return rtab;
 298                 }
 299         }
 300
 301         if (tab == NULL || r->rate == 0 || r->cell_log == 0 ||
 302             nla_len(tab) != TC_RTAB_SIZE)
 303                 return NULL;
 304
 305         rtab = kmalloc(sizeof(*rtab), GFP_KERNEL);
 306         if (rtab) {
 307                 rtab->rate = *r;
 308                 rtab->refcnt = 1;
 309                 memcpy(rtab->data, nla_data(tab), 1024);
 310                 rtab->next = qdisc_rtab_list;
 311                 qdisc_rtab_list = rtab;
 312         }
 313         return rtab;
 314 }
 315 EXPORT_SYMBOL(qdisc_get_rtab);
 316
 317 void qdisc_put_rtab(struct qdisc_rate_table *tab)
 318 {
 319         struct qdisc_rate_table *rtab, **rtabp;
 320
 321         if (!tab || --tab->refcnt)
 322                 return;
 323
 324         for (rtabp = &qdisc_rtab_list; (rtab=*rtabp) != NULL; rtabp = &rtab->next) {
 325                 if (rtab == tab) {
 326                         *rtabp = rtab->next;
 327                         kfree(rtab);
 328                         return;
 329                 }
 330         }
 331 }
 332 EXPORT_SYMBOL(qdisc_put_rtab);
 333
 334 static LIST_HEAD(qdisc_stab_list);
 335 static DEFINE_SPINLOCK(qdisc_stab_lock);
 336
 337 static const struct nla_policy stab_policy[TCA_STAB_MAX + 1] = {
 338         [TCA_STAB_BASE] = { .len = sizeof(struct tc_sizespec) },
 339         [TCA_STAB_DATA] = { .type = NLA_BINARY },
 340 };
 341
 342 static struct qdisc_size_table *qdisc_get_stab(struct nlattr *opt)
 343 {
 344         struct nlattr *tb[TCA_STAB_MAX + 1];
 345         struct qdisc_size_table *stab;
 346         struct tc_sizespec *s;
 347         unsigned int tsize = 0;
 348         u16 *tab = NULL;
 349         int err;
 350
 351         err = nla_parse_nested(tb, TCA_STAB_MAX, opt, stab_policy);
 352         if (err < 0)
 353                 return ERR_PTR(err);
 354         if (!tb[TCA_STAB_BASE])
 355                 return ERR_PTR(-EINVAL);
 356
 357         s = nla_data(tb[TCA_STAB_BASE]);
 358
 359         if (s->tsize > 0) {
 360                 if (!tb[TCA_STAB_DATA])
 361                         return ERR_PTR(-EINVAL);
 362                 tab = nla_data(tb[TCA_STAB_DATA]);
 363                 tsize = nla_len(tb[TCA_STAB_DATA]) / sizeof(u16);
 364         }
 365
 366         if (!s || tsize != s->tsize || (!tab && tsize > 0))
 367                 return ERR_PTR(-EINVAL);
 368
 369         spin_lock(&qdisc_stab_lock);
 370
 371         list_for_each_entry(stab, &qdisc_stab_list, list) {
 372                 if (memcmp(&stab->szopts, s, sizeof(*s)))
 373                         continue;
 374                 if (tsize > 0 && memcmp(stab->data, tab, tsize * sizeof(u16)))
 375                         continue;
 376                 stab->refcnt++;
 377                 spin_unlock(&qdisc_stab_lock);
 378                 return stab;
 379         }
 380
 381         spin_unlock(&qdisc_stab_lock);
 382
 383         stab = kmalloc(sizeof(*stab) + tsize * sizeof(u16), GFP_KERNEL);
 384         if (!stab)
 385                 return ERR_PTR(-ENOMEM);
 386
 387         stab->refcnt = 1;
 388         stab->szopts = *s;
 389         if (tsize > 0)
 390                 memcpy(stab->data, tab, tsize * sizeof(u16));
 391
 392         spin_lock(&qdisc_stab_lock);
 393         list_add_tail(&stab->list, &qdisc_stab_list);
 394         spin_unlock(&qdisc_stab_lock);
 395
 396         return stab;
 397 }
 398
 399 void qdisc_put_stab(struct qdisc_size_table *tab)
 400 {
 401         if (!tab)
 402                 return;
 403
 404         spin_lock(&qdisc_stab_lock);
 405
 406         if (--tab->refcnt == 0) {
 407                 list_del(&tab->list);
 408                 kfree(tab);
 409         }
 410
 411         spin_unlock(&qdisc_stab_lock);
 412 }
 413 EXPORT_SYMBOL(qdisc_put_stab);
 414
 415 static int qdisc_dump_stab(struct sk_buff *skb, struct qdisc_size_table *stab)
 416 {
 417         struct nlattr *nest;
 418
 419         nest = nla_nest_start(skb, TCA_STAB);
 420         NLA_PUT(skb, TCA_STAB_BASE, sizeof(stab->szopts), &stab->szopts);
 421         nla_nest_end(skb, nest);
 422
 423         return skb->len;
 424
 425 nla_put_failure:
 426         return -1;
 427 }
 428
 429 void qdisc_calculate_pkt_len(struct sk_buff *skb, struct qdisc_size_table *stab)
 430 {
 431         int pkt_len, slot;
 432
 433         pkt_len = skb->len + stab->szopts.overhead;
 434         if (unlikely(!stab->szopts.tsize))
 435                 goto out;
 436
 437         slot = pkt_len + stab->szopts.cell_align;
 438         if (unlikely(slot < 0))
 439                 slot = 0;
 440
 441         slot >>= stab->szopts.cell_log;
 442         if (likely(slot < stab->szopts.tsize))
 443                 pkt_len = stab->data[slot];
 444         else
 445                 pkt_len = stab->data[stab->szopts.tsize - 1] *
 446                                 (slot / stab->szopts.tsize) +
 447                                 stab->data[slot % stab->szopts.tsize];
 448
 449         pkt_len <<= stab->szopts.size_log;
 450 out:
 451         if (unlikely(pkt_len < 1))
 452                 pkt_len = 1;
 453         qdisc_skb_cb(skb)->pkt_len = pkt_len;
 454 }
 455 EXPORT_SYMBOL(qdisc_calculate_pkt_len);
 456
 457 static enum hrtimer_restart qdisc_watchdog(struct hrtimer *timer)
 458 {
 459         struct qdisc_watchdog *wd = container_of(timer, struct qdisc_watchdog,
 460                                                  timer);
 461
 462         wd->qdisc->flags &= ~TCQ_F_THROTTLED;
 463         smp_wmb();
 464         __netif_schedule(qdisc_root(wd->qdisc));
 465
 466         return HRTIMER_NORESTART;
 467 }
 468
 469 void qdisc_watchdog_init(struct qdisc_watchdog *wd, struct Qdisc *qdisc)
 470 {
 471         hrtimer_init(&wd->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
 472         wd->timer.function = qdisc_watchdog;
 473         wd->qdisc = qdisc;
 474 }
 475 EXPORT_SYMBOL(qdisc_watchdog_init);
 476
 477 void qdisc_watchdog_schedule(struct qdisc_watchdog *wd, psched_time_t expires)
 478 {
 479         ktime_t time;
 480
 481         if (test_bit(__QDISC_STATE_DEACTIVATED,
 482                      &qdisc_root_sleeping(wd->qdisc)->state))
 483                 return;
 484
 485         wd->qdisc->flags |= TCQ_F_THROTTLED;
 486         time = ktime_set(0, 0);
 487         time = ktime_add_ns(time, PSCHED_US2NS(expires));
 488         hrtimer_start(&wd->timer, time, HRTIMER_MODE_ABS);
 489 }
 490 EXPORT_SYMBOL(qdisc_watchdog_schedule);
 491
 492 void qdisc_watchdog_cancel(struct qdisc_watchdog *wd)
 493 {
 494         hrtimer_cancel(&wd->timer);
 495         wd->qdisc->flags &= ~TCQ_F_THROTTLED;
 496 }
 497 EXPORT_SYMBOL(qdisc_watchdog_cancel);
 498
 499 static struct hlist_head *qdisc_class_hash_alloc(unsigned int n)
 500 {
 501         unsigned int size = n * sizeof(struct hlist_head), i;
 502         struct hlist_head *h;
 503
 504         if (size <= PAGE_SIZE)
 505                 h = kmalloc(size, GFP_KERNEL);
 506         else
 507                 h = (struct hlist_head *)
 508                         __get_free_pages(GFP_KERNEL, get_order(size));
 509
 510         if (h != NULL) {
 511                 for (i = 0; i < n; i++)
 512                         INIT_HLIST_HEAD(&h[i]);
 513         }
 514         return h;
 515 }
 516
 517 static void qdisc_class_hash_free(struct hlist_head *h, unsigned int n)
 518 {
 519         unsigned int size = n * sizeof(struct hlist_head);
 520
 521         if (size <= PAGE_SIZE)
 522                 kfree(h);
 523         else
 524                 free_pages((unsigned long)h, get_order(size));
 525 }
 526
 527 void qdisc_class_hash_grow(struct Qdisc *sch, struct Qdisc_class_hash *clhash)
 528 {
 529         struct Qdisc_class_common *cl;
 530         struct hlist_node *n, *next;
 531         struct hlist_head *nhash, *ohash;
 532         unsigned int nsize, nmask, osize;
 533         unsigned int i, h;
 534
 535         /* Rehash when load factor exceeds 0.75 */
 536         if (clhash->hashelems * 4 <= clhash->hashsize * 3)
 537                 return;
 538         nsize = clhash->hashsize * 2;
 539         nmask = nsize - 1;
 540         nhash = qdisc_class_hash_alloc(nsize);
 541         if (nhash == NULL)
 542                 return;
 543
 544         ohash = clhash->hash;
 545         osize = clhash->hashsize;
 546
 547         sch_tree_lock(sch);
 548         for (i = 0; i < osize; i++) {
 549                 hlist_for_each_entry_safe(cl, n, next, &ohash[i], hnode) {
 550                         h = qdisc_class_hash(cl->classid, nmask);
 551                         hlist_add_head(&cl->hnode, &nhash[h]);
 552                 }
 553         }
 554         clhash->hash     = nhash;
 555         clhash->hashsize = nsize;
 556         clhash->hashmask = nmask;
 557         sch_tree_unlock(sch);
 558
 559         qdisc_class_hash_free(ohash, osize);
 560 }
 561 EXPORT_SYMBOL(qdisc_class_hash_grow);
 562
 563 int qdisc_class_hash_init(struct Qdisc_class_hash *clhash)
 564 {
 565         unsigned int size = 4;
 566
 567         clhash->hash = qdisc_class_hash_alloc(size);
 568         if (clhash->hash == NULL)
 569                 return -ENOMEM;
 570         clhash->hashsize  = size;
 571         clhash->hashmask  = size - 1;
 572         clhash->hashelems = 0;
 573         return 0;
 574 }
 575 EXPORT_SYMBOL(qdisc_class_hash_init);
 576
 577 void qdisc_class_hash_destroy(struct Qdisc_class_hash *clhash)
 578 {
 579         qdisc_class_hash_free(clhash->hash, clhash->hashsize);
 580 }
 581 EXPORT_SYMBOL(qdisc_class_hash_destroy);
 582
 583 void qdisc_class_hash_insert(struct Qdisc_class_hash *clhash,
 584                              struct Qdisc_class_common *cl)
 585 {
 586         unsigned int h;
 587
 588         INIT_HLIST_NODE(&cl->hnode);
 589         h = qdisc_class_hash(cl->classid, clhash->hashmask);
 590         hlist_add_head(&cl->hnode, &clhash->hash[h]);
 591         clhash->hashelems++;
 592 }
 593 EXPORT_SYMBOL(qdisc_class_hash_insert);
 594
 595 void qdisc_class_hash_remove(struct Qdisc_class_hash *clhash,
 596                              struct Qdisc_class_common *cl)
 597 {
 598         hlist_del(&cl->hnode);
 599         clhash->hashelems--;
 600 }
 601 EXPORT_SYMBOL(qdisc_class_hash_remove);
 602
 603 /* Allocate an unique handle from space managed by kernel */
 604
 605 static u32 qdisc_alloc_handle(struct net_device *dev)
 606 {
 607         int i = 0x10000;
 608         static u32 autohandle = TC_H_MAKE(0x80000000U, 0);
 609
 610         do {
 611                 autohandle += TC_H_MAKE(0x10000U, 0);
 612                 if (autohandle == TC_H_MAKE(TC_H_ROOT, 0))
 613                         autohandle = TC_H_MAKE(0x80000000U, 0);
 614         } while (qdisc_lookup(dev, autohandle) && --i > 0);
 615
 616         return i>0 ? autohandle : 0;
 617 }
 618
 619 /* Attach toplevel qdisc to device queue. */
 620
 621 static struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
 622                                      struct Qdisc *qdisc)
 623 {
 624         struct Qdisc *oqdisc = dev_queue->qdisc_sleeping;
 625         spinlock_t *root_lock;
 626
 627         root_lock = qdisc_root_lock(oqdisc);
 628         spin_lock_bh(root_lock);
 629
 630         /* Prune old scheduler */
 631         if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1)
 632                 qdisc_reset(oqdisc);
 633
 634         /* ... and graft new one */
 635         if (qdisc == NULL)
 636                 qdisc = &noop_qdisc;
 637         dev_queue->qdisc_sleeping = qdisc;
 638         dev_queue->qdisc = &noop_qdisc;
 639
 640         spin_unlock_bh(root_lock);
 641
 642         return oqdisc;
 643 }
 644
 645 void qdisc_tree_decrease_qlen(struct Qdisc *sch, unsigned int n)
 646 {
 647         const struct Qdisc_class_ops *cops;
 648         unsigned long cl;
 649         u32 parentid;
 650
 651         if (n == 0)
 652                 return;
 653         while ((parentid = sch->parent)) {
 654                 if (TC_H_MAJ(parentid) == TC_H_MAJ(TC_H_INGRESS))
 655                         return;
 656
 657                 sch = qdisc_lookup(qdisc_dev(sch), TC_H_MAJ(parentid));
 658                 if (sch == NULL) {
 659                         WARN_ON(parentid != TC_H_ROOT);
 660                         return;
 661                 }
 662                 cops = sch->ops->cl_ops;
 663                 if (cops->qlen_notify) {
 664                         cl = cops->get(sch, parentid);
 665                         cops->qlen_notify(sch, cl);
 666                         cops->put(sch, cl);
 667                 }
 668                 sch->q.qlen -= n;
 669         }
 670 }
 671 EXPORT_SYMBOL(qdisc_tree_decrease_qlen);
 672
 673 static void notify_and_destroy(struct sk_buff *skb, struct nlmsghdr *n, u32 clid,
 674                                struct Qdisc *old, struct Qdisc *new)
 675 {
 676         if (new || old)
 677                 qdisc_notify(skb, n, clid, old, new);
 678
 679         if (old)
 680                 qdisc_destroy(old);
 681 }
 682
 683 /* Graft qdisc "new" to class "classid" of qdisc "parent" or
 684  * to device "dev".
 685  *
 686  * When appropriate send a netlink notification using 'skb'
 687  * and "n".
 688  *
 689  * On success, destroy old qdisc.
 690  */
 691
 692 static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 693                        struct sk_buff *skb, struct nlmsghdr *n, u32 classid,
 694                        struct Qdisc *new, struct Qdisc *old)
 695 {
 696         struct Qdisc *q = old;
 697         int err = 0;
 698
 699         if (parent == NULL) {
 700                 unsigned int i, num_q, ingress;
 701
 702                 ingress = 0;
 703                 num_q = dev->num_tx_queues;
 704                 if ((q && q->flags & TCQ_F_INGRESS) ||
 705                     (new && new->flags & TCQ_F_INGRESS)) {
 706                         num_q = 1;
 707                         ingress = 1;
 708                 }
 709
 710                 if (dev->flags & IFF_UP)
 711                         dev_deactivate(dev);
 712
 713                 for (i = 0; i < num_q; i++) {
 714                         struct netdev_queue *dev_queue = &dev->rx_queue;
 715
 716                         if (!ingress)
 717                                 dev_queue = netdev_get_tx_queue(dev, i);
 718
 719                         old = dev_graft_qdisc(dev_queue, new);
 720                         if (new && i > 0)
 721                                 atomic_inc(&new->refcnt);
 722
 723                         notify_and_destroy(skb, n, classid, old, new);
 724                 }
 725
 726                 if (dev->flags & IFF_UP)
 727                         dev_activate(dev);
 728         } else {
 729                 const struct Qdisc_class_ops *cops = parent->ops->cl_ops;
 730
 731                 err = -EINVAL;
 732
 733                 if (cops) {
 734                         unsigned long cl = cops->get(parent, classid);
 735                         if (cl) {
 736                                 err = cops->graft(parent, cl, new, &old);
 737                                 cops->put(parent, cl);
 738                         }
 739                 }
 740                 if (!err)
 741                         notify_and_destroy(skb, n, classid, old, new);
 742         }
 743         return err;
 744 }
 745
 746 /* lockdep annotation is needed for ingress; egress gets it only for name */
 747 static struct lock_class_key qdisc_tx_lock;
 748 static struct lock_class_key qdisc_rx_lock;
 749
 750 /*
 751    Allocate and initialize new qdisc.
 752
 753    Parameters are passed via opt.
 754  */
 755
 756 static struct Qdisc *
 757 qdisc_create(struct net_device *dev, struct netdev_queue *dev_queue,
 758              u32 parent, u32 handle, struct nlattr **tca, int *errp)
 759 {
 760         int err;
 761         struct nlattr *kind = tca[TCA_KIND];
 762         struct Qdisc *sch;
 763         struct Qdisc_ops *ops;
 764         struct qdisc_size_table *stab;
 765
 766         ops = qdisc_lookup_ops(kind);
 767 #ifdef CONFIG_KMOD
 768         if (ops == NULL && kind != NULL) {
 769                 char name[IFNAMSIZ];
 770                 if (nla_strlcpy(name, kind, IFNAMSIZ) < IFNAMSIZ) {
 771                         /* We dropped the RTNL semaphore in order to
 772                          * perform the module load.  So, even if we
 773                          * succeeded in loading the module we have to
 774                          * tell the caller to replay the request.  We
 775                          * indicate this using -EAGAIN.
 776                          * We replay the request because the device may
 777                          * go away in the mean time.
 778                          */
 779                         rtnl_unlock();
 780                         request_module("sch_%s", name);
 781                         rtnl_lock();
 782                         ops = qdisc_lookup_ops(kind);
 783                         if (ops != NULL) {
 784                                 /* We will try again qdisc_lookup_ops,
 785                                  * so don't keep a reference.
 786                                  */
 787                                 module_put(ops->owner);
 788                                 err = -EAGAIN;
 789                                 goto err_out;
 790                         }
 791                 }
 792         }
 793 #endif
 794
 795         err = -ENOENT;
 796         if (ops == NULL)
 797                 goto err_out;
 798
 799         sch = qdisc_alloc(dev_queue, ops);
 800         if (IS_ERR(sch)) {
 801                 err = PTR_ERR(sch);
 802                 goto err_out2;
 803         }
 804
 805         sch->parent = parent;
 806
 807         if (handle == TC_H_INGRESS) {
 808                 sch->flags |= TCQ_F_INGRESS;
 809                 handle = TC_H_MAKE(TC_H_INGRESS, 0);
 810                 lockdep_set_class(qdisc_lock(sch), &qdisc_rx_lock);
 811         } else {
 812                 if (handle == 0) {
 813                         handle = qdisc_alloc_handle(dev);
 814                         err = -ENOMEM;
 815                         if (handle == 0)
 816                                 goto err_out3;
 817                 }
 818                 lockdep_set_class(qdisc_lock(sch), &qdisc_tx_lock);
 819         }
 820
 821         sch->handle = handle;
 822
 823         if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS])) == 0) {
 824                 if (tca[TCA_STAB]) {
 825                         stab = qdisc_get_stab(tca[TCA_STAB]);
 826                         if (IS_ERR(stab)) {
 827                                 err = PTR_ERR(stab);
 828                                 goto err_out3;
 829                         }
 830                         sch->stab = stab;
 831                 }
 832                 if (tca[TCA_RATE]) {
 833                         err = gen_new_estimator(&sch->bstats, &sch->rate_est,
 834                                                 qdisc_root_lock(sch),
 835                                                 tca[TCA_RATE]);
 836                         if (err) {
 837                                 /*
 838                                  * Any broken qdiscs that would require
 839                                  * a ops->reset() here? The qdisc was never
 840                                  * in action so it shouldn't be necessary.
 841                                  */
 842                                 if (ops->destroy)
 843                                         ops->destroy(sch);
 844                                 goto err_out3;
 845                         }
 846                 }
 847
 848                 qdisc_list_add(sch);
 849
 850                 return sch;
 851         }
 852 err_out3:
 853         qdisc_put_stab(sch->stab);
 854         dev_put(dev);
 855         kfree((char *) sch - sch->padded);
 856 err_out2:
 857         module_put(ops->owner);
 858 err_out:
 859         *errp = err;
 860         return NULL;
 861 }
 862
 863 static int qdisc_change(struct Qdisc *sch, struct nlattr **tca)
 864 {
 865         struct qdisc_size_table *stab = NULL;
 866         int err = 0;
 867
 868         if (tca[TCA_OPTIONS]) {
 869                 if (sch->ops->change == NULL)
 870                         return -EINVAL;
 871                 err = sch->ops->change(sch, tca[TCA_OPTIONS]);
 872                 if (err)
 873                         return err;
 874         }
 875
 876         if (tca[TCA_STAB]) {
 877                 stab = qdisc_get_stab(tca[TCA_STAB]);
 878                 if (IS_ERR(stab))
 879                         return PTR_ERR(stab);
 880         }
 881
 882         qdisc_put_stab(sch->stab);
 883         sch->stab = stab;
 884
 885         if (tca[TCA_RATE])
 886                 gen_replace_estimator(&sch->bstats, &sch->rate_est,
 887                                       qdisc_root_lock(sch), tca[TCA_RATE]);
 888         return 0;
 889 }
 890
 891 struct check_loop_arg
 892 {
 893         struct qdisc_walker     w;
 894         struct Qdisc            *p;
 895         int                     depth;
 896 };
 897
 898 static int check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w);
 899
 900 static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth)
 901 {
 902         struct check_loop_arg   arg;
 903
 904         if (q->ops->cl_ops == NULL)
 905                 return 0;
 906
 907         arg.w.stop = arg.w.skip = arg.w.count = 0;
 908         arg.w.fn = check_loop_fn;
 909         arg.depth = depth;
 910         arg.p = p;
 911         q->ops->cl_ops->walk(q, &arg.w);
 912         return arg.w.stop ? -ELOOP : 0;
 913 }
 914
 915 static int
 916 check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w)
 917 {
 918         struct Qdisc *leaf;
 919         const struct Qdisc_class_ops *cops = q->ops->cl_ops;
 920         struct check_loop_arg *arg = (struct check_loop_arg *)w;
 921
 922         leaf = cops->leaf(q, cl);
 923         if (leaf) {
 924                 if (leaf == arg->p || arg->depth > 7)
 925                         return -ELOOP;
 926                 return check_loop(leaf, arg->p, arg->depth + 1);
 927         }
 928         return 0;
 929 }
 930
 931 /*
 932  * Delete/get qdisc.
 933  */
 934
 935 static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 936 {
 937         struct net *net = sock_net(skb->sk);
 938         struct tcmsg *tcm = NLMSG_DATA(n);
 939         struct nlattr *tca[TCA_MAX + 1];
 940         struct net_device *dev;
 941         u32 clid = tcm->tcm_parent;
 942         struct Qdisc *q = NULL;
 943         struct Qdisc *p = NULL;
 944         int err;
 945
 946         if (net != &init_net)
 947                 return -EINVAL;
 948
 949         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
 950                 return -ENODEV;
 951
 952         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, NULL);
 953         if (err < 0)
 954                 return err;
 955
 956         if (clid) {
 957                 if (clid != TC_H_ROOT) {
 958                         if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) {
 959                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
 960                                         return -ENOENT;
 961                                 q = qdisc_leaf(p, clid);
 962                         } else { /* ingress */
 963                                 q = dev->rx_queue.qdisc_sleeping;
 964                         }
 965                 } else {
 966                         struct netdev_queue *dev_queue;
 967                         dev_queue = netdev_get_tx_queue(dev, 0);
 968                         q = dev_queue->qdisc_sleeping;
 969                 }
 970                 if (!q)
 971                         return -ENOENT;
 972
 973                 if (tcm->tcm_handle && q->handle != tcm->tcm_handle)
 974                         return -EINVAL;
 975         } else {
 976                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
 977                         return -ENOENT;
 978         }
 979
 980         if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id))
 981                 return -EINVAL;
 982
 983         if (n->nlmsg_type == RTM_DELQDISC) {
 984                 if (!clid)
 985                         return -EINVAL;
 986                 if (q->handle == 0)
 987                         return -ENOENT;
 988                 if ((err = qdisc_graft(dev, p, skb, n, clid, NULL, q)) != 0)
 989                         return err;
 990         } else {
 991                 qdisc_notify(skb, n, clid, NULL, q);
 992         }
 993         return 0;
 994 }
 995
 996 /*
 997    Create/change qdisc.
 998  */
 999
1000 static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
1001 {
1002         struct net *net = sock_net(skb->sk);
1003         struct tcmsg *tcm;
1004         struct nlattr *tca[TCA_MAX + 1];
1005         struct net_device *dev;
1006         u32 clid;
1007         struct Qdisc *q, *p;
1008         int err;
1009
1010         if (net != &init_net)
1011                 return -EINVAL;
1012
1013 replay:
1014         /* Reinit, just in case something touches this. */
1015         tcm = NLMSG_DATA(n);
1016         clid = tcm->tcm_parent;
1017         q = p = NULL;
1018
1019         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
1020                 return -ENODEV;
1021
1022         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, NULL);
1023         if (err < 0)
1024                 return err;
1025
1026         if (clid) {
1027                 if (clid != TC_H_ROOT) {
1028                         if (clid != TC_H_INGRESS) {
1029                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
1030                                         return -ENOENT;
1031                                 q = qdisc_leaf(p, clid);
1032                         } else { /*ingress */
1033                                 q = dev->rx_queue.qdisc_sleeping;
1034                         }
1035                 } else {
1036                         struct netdev_queue *dev_queue;
1037                         dev_queue = netdev_get_tx_queue(dev, 0);
1038                         q = dev_queue->qdisc_sleeping;
1039                 }
1040
1041                 /* It may be default qdisc, ignore it */
1042                 if (q && q->handle == 0)
1043                         q = NULL;
1044
1045                 if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) {
1046                         if (tcm->tcm_handle) {
1047                                 if (q && !(n->nlmsg_flags&NLM_F_REPLACE))
1048                                         return -EEXIST;
1049                                 if (TC_H_MIN(tcm->tcm_handle))
1050                                         return -EINVAL;
1051                                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
1052                                         goto create_n_graft;
1053                                 if (n->nlmsg_flags&NLM_F_EXCL)
1054                                         return -EEXIST;
1055                                 if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id))
1056                                         return -EINVAL;
1057                                 if (q == p ||
1058                                     (p && check_loop(q, p, 0)))
1059                                         return -ELOOP;
1060                                 atomic_inc(&q->refcnt);
1061                                 goto graft;
1062                         } else {
1063                                 if (q == NULL)
1064                                         goto create_n_graft;
1065
1066                                 /* This magic test requires explanation.
1067                                  *
1068                                  *   We know, that some child q is already
1069                                  *   attached to this parent and have choice:
1070                                  *   either to change it or to create/graft new one.
1071                                  *
1072                                  *   1. We are allowed to create/graft only
1073                                  *   if CREATE and REPLACE flags are set.
1074                                  *
1075                                  *   2. If EXCL is set, requestor wanted to say,
1076                                  *   that qdisc tcm_handle is not expected
1077                                  *   to exist, so that we choose create/graft too.
1078                                  *
1079                                  *   3. The last case is when no flags are set.
1080                                  *   Alas, it is sort of hole in API, we
1081                                  *   cannot decide what to do unambiguously.
1082                                  *   For now we select create/graft, if
1083                                  *   user gave KIND, which does not match existing.
1084                                  */
1085                                 if ((n->nlmsg_flags&NLM_F_CREATE) &&
1086                                     (n->nlmsg_flags&NLM_F_REPLACE) &&
1087                                     ((n->nlmsg_flags&NLM_F_EXCL) ||
1088                                      (tca[TCA_KIND] &&
1089                                       nla_strcmp(tca[TCA_KIND], q->ops->id))))
1090                                         goto create_n_graft;
1091                         }
1092                 }
1093         } else {
1094                 if (!tcm->tcm_handle)
1095                         return -EINVAL;
1096                 q = qdisc_lookup(dev, tcm->tcm_handle);
1097         }
1098
1099         /* Change qdisc parameters */
1100         if (q == NULL)
1101                 return -ENOENT;
1102         if (n->nlmsg_flags&NLM_F_EXCL)
1103                 return -EEXIST;
1104         if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id))
1105                 return -EINVAL;
1106         err = qdisc_change(q, tca);
1107         if (err == 0)
1108                 qdisc_notify(skb, n, clid, NULL, q);
1109         return err;
1110
1111 create_n_graft:
1112         if (!(n->nlmsg_flags&NLM_F_CREATE))
1113                 return -ENOENT;
1114         if (clid == TC_H_INGRESS)
1115                 q = qdisc_create(dev, &dev->rx_queue,
1116                                  tcm->tcm_parent, tcm->tcm_parent,
1117                                  tca, &err);
1118         else
1119                 q = qdisc_create(dev, netdev_get_tx_queue(dev, 0),
1120                                  tcm->tcm_parent, tcm->tcm_handle,
1121                                  tca, &err);
1122         if (q == NULL) {
1123                 if (err == -EAGAIN)
1124                         goto replay;
1125                 return err;
1126         }
1127
1128 graft:
1129         err = qdisc_graft(dev, p, skb, n, clid, q, NULL);
1130         if (err) {
1131                 if (q)
1132                         qdisc_destroy(q);
1133                 return err;
1134         }
1135
1136         return 0;
1137 }
1138
1139 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
1140                          u32 pid, u32 seq, u16 flags, int event)
1141 {
1142         struct tcmsg *tcm;
1143         struct nlmsghdr  *nlh;
1144         unsigned char *b = skb_tail_pointer(skb);
1145         struct gnet_dump d;
1146
1147         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
1148         tcm = NLMSG_DATA(nlh);
1149         tcm->tcm_family = AF_UNSPEC;
1150         tcm->tcm__pad1 = 0;
1151         tcm->tcm__pad2 = 0;
1152         tcm->tcm_ifindex = qdisc_dev(q)->ifindex;
1153         tcm->tcm_parent = clid;
1154         tcm->tcm_handle = q->handle;
1155         tcm->tcm_info = atomic_read(&q->refcnt);
1156         NLA_PUT_STRING(skb, TCA_KIND, q->ops->id);
1157         if (q->ops->dump && q->ops->dump(q, skb) < 0)
1158                 goto nla_put_failure;
1159         q->qstats.qlen = q->q.qlen;
1160
1161         if (q->stab && qdisc_dump_stab(skb, q->stab) < 0)
1162                 goto nla_put_failure;
1163
1164         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1165                                          TCA_XSTATS, qdisc_root_lock(q), &d) < 0)
1166                 goto nla_put_failure;
1167
1168         if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0)
1169                 goto nla_put_failure;
1170
1171         if (gnet_stats_copy_basic(&d, &q->bstats) < 0 ||
1172             gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 ||
1173             gnet_stats_copy_queue(&d, &q->qstats) < 0)
1174                 goto nla_put_failure;
1175
1176         if (gnet_stats_finish_copy(&d) < 0)
1177                 goto nla_put_failure;
1178
1179         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1180         return skb->len;
1181
1182 nlmsg_failure:
1183 nla_put_failure:
1184         nlmsg_trim(skb, b);
1185         return -1;
1186 }
1187
1188 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1189                         u32 clid, struct Qdisc *old, struct Qdisc *new)
1190 {
1191         struct sk_buff *skb;
1192         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1193
1194         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1195         if (!skb)
1196                 return -ENOBUFS;
1197
1198         if (old && old->handle) {
1199                 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0)
1200                         goto err_out;
1201         }
1202         if (new) {
1203                 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
1204                         goto err_out;
1205         }
1206
1207         if (skb->len)
1208                 return rtnetlink_send(skb, &init_net, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1209
1210 err_out:
1211         kfree_skb(skb);
1212         return -EINVAL;
1213 }
1214
1215 static bool tc_qdisc_dump_ignore(struct Qdisc *q)
1216 {
1217         return (q->flags & TCQ_F_BUILTIN) ? true : false;
1218 }
1219
1220 static int tc_dump_qdisc_root(struct Qdisc *root, struct sk_buff *skb,
1221                               struct netlink_callback *cb,
1222                               int *q_idx_p, int s_q_idx)
1223 {
1224         int ret = 0, q_idx = *q_idx_p;
1225         struct Qdisc *q;
1226
1227         if (!root)
1228                 return 0;
1229
1230         q = root;
1231         if (q_idx < s_q_idx) {
1232                 q_idx++;
1233         } else {
1234                 if (!tc_qdisc_dump_ignore(q) &&
1235                     tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
1236                                   cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0)
1237                         goto done;
1238                 q_idx++;
1239         }
1240         list_for_each_entry(q, &root->list, list) {
1241                 if (q_idx < s_q_idx) {
1242                         q_idx++;
1243                         continue;
1244                 }
1245                 if (!tc_qdisc_dump_ignore(q) &&
1246                     tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
1247                                   cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0)
1248                         goto done;
1249                 q_idx++;
1250         }
1251
1252 out:
1253         *q_idx_p = q_idx;
1254         return ret;
1255 done:
1256         ret = -1;
1257         goto out;
1258 }
1259
1260 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
1261 {
1262         struct net *net = sock_net(skb->sk);
1263         int idx, q_idx;
1264         int s_idx, s_q_idx;
1265         struct net_device *dev;
1266
1267         if (net != &init_net)
1268                 return 0;
1269
1270         s_idx = cb->args[0];
1271         s_q_idx = q_idx = cb->args[1];
1272         read_lock(&dev_base_lock);
1273         idx = 0;
1274         for_each_netdev(&init_net, dev) {
1275                 struct netdev_queue *dev_queue;
1276
1277                 if (idx < s_idx)
1278                         goto cont;
1279                 if (idx > s_idx)
1280                         s_q_idx = 0;
1281                 q_idx = 0;
1282
1283                 dev_queue = netdev_get_tx_queue(dev, 0);
1284                 if (tc_dump_qdisc_root(dev_queue->qdisc_sleeping, skb, cb, &q_idx, s_q_idx) < 0)
1285                         goto done;
1286
1287                 dev_queue = &dev->rx_queue;
1288                 if (tc_dump_qdisc_root(dev_queue->qdisc_sleeping, skb, cb, &q_idx, s_q_idx) < 0)
1289                         goto done;
1290
1291 cont:
1292                 idx++;
1293         }
1294
1295 done:
1296         read_unlock(&dev_base_lock);
1297
1298         cb->args[0] = idx;
1299         cb->args[1] = q_idx;
1300
1301         return skb->len;
1302 }
1303
1304
1305
1306 /************************************************
1307  *      Traffic classes manipulation.           *
1308  ************************************************/
1309
1310
1311
1312 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
1313 {
1314         struct net *net = sock_net(skb->sk);
1315         struct netdev_queue *dev_queue;
1316         struct tcmsg *tcm = NLMSG_DATA(n);
1317         struct nlattr *tca[TCA_MAX + 1];
1318         struct net_device *dev;
1319         struct Qdisc *q = NULL;
1320         const struct Qdisc_class_ops *cops;
1321         unsigned long cl = 0;
1322         unsigned long new_cl;
1323         u32 pid = tcm->tcm_parent;
1324         u32 clid = tcm->tcm_handle;
1325         u32 qid = TC_H_MAJ(clid);
1326         int err;
1327
1328         if (net != &init_net)
1329                 return -EINVAL;
1330
1331         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
1332                 return -ENODEV;
1333
1334         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, NULL);
1335         if (err < 0)
1336                 return err;
1337
1338         /*
1339            parent == TC_H_UNSPEC - unspecified parent.
1340            parent == TC_H_ROOT   - class is root, which has no parent.
1341            parent == X:0         - parent is root class.
1342            parent == X:Y         - parent is a node in hierarchy.
1343            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
1344
1345            handle == 0:0         - generate handle from kernel pool.
1346            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
1347            handle == X:Y         - clear.
1348            handle == X:0         - root class.
1349          */
1350
1351         /* Step 1. Determine qdisc handle X:0 */
1352
1353         dev_queue = netdev_get_tx_queue(dev, 0);
1354         if (pid != TC_H_ROOT) {
1355                 u32 qid1 = TC_H_MAJ(pid);
1356
1357                 if (qid && qid1) {
1358                         /* If both majors are known, they must be identical. */
1359                         if (qid != qid1)
1360                                 return -EINVAL;
1361                 } else if (qid1) {
1362                         qid = qid1;
1363                 } else if (qid == 0)
1364                         qid = dev_queue->qdisc_sleeping->handle;
1365
1366                 /* Now qid is genuine qdisc handle consistent
1367                    both with parent and child.
1368
1369                    TC_H_MAJ(pid) still may be unspecified, complete it now.
1370                  */
1371                 if (pid)
1372                         pid = TC_H_MAKE(qid, pid);
1373         } else {
1374                 if (qid == 0)
1375                         qid = dev_queue->qdisc_sleeping->handle;
1376         }
1377
1378         /* OK. Locate qdisc */
1379         if ((q = qdisc_lookup(dev, qid)) == NULL)
1380                 return -ENOENT;
1381
1382         /* An check that it supports classes */
1383         cops = q->ops->cl_ops;
1384         if (cops == NULL)
1385                 return -EINVAL;
1386
1387         /* Now try to get class */
1388         if (clid == 0) {
1389                 if (pid == TC_H_ROOT)
1390                         clid = qid;
1391         } else
1392                 clid = TC_H_MAKE(qid, clid);
1393
1394         if (clid)
1395                 cl = cops->get(q, clid);
1396
1397         if (cl == 0) {
1398                 err = -ENOENT;
1399                 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE))
1400                         goto out;
1401         } else {
1402                 switch (n->nlmsg_type) {
1403                 case RTM_NEWTCLASS:
1404                         err = -EEXIST;
1405                         if (n->nlmsg_flags&NLM_F_EXCL)
1406                                 goto out;
1407                         break;
1408                 case RTM_DELTCLASS:
1409                         err = cops->delete(q, cl);
1410                         if (err == 0)
1411                                 tclass_notify(skb, n, q, cl, RTM_DELTCLASS);
1412                         goto out;
1413                 case RTM_GETTCLASS:
1414                         err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS);
1415                         goto out;
1416                 default:
1417                         err = -EINVAL;
1418                         goto out;
1419                 }
1420         }
1421
1422         new_cl = cl;
1423         err = cops->change(q, clid, pid, tca, &new_cl);
1424         if (err == 0)
1425                 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
1426
1427 out:
1428         if (cl)
1429                 cops->put(q, cl);
1430
1431         return err;
1432 }
1433
1434
1435 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
1436                           unsigned long cl,
1437                           u32 pid, u32 seq, u16 flags, int event)
1438 {
1439         struct tcmsg *tcm;
1440         struct nlmsghdr  *nlh;
1441         unsigned char *b = skb_tail_pointer(skb);
1442         struct gnet_dump d;
1443         const struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1444
1445         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
1446         tcm = NLMSG_DATA(nlh);
1447         tcm->tcm_family = AF_UNSPEC;
1448         tcm->tcm_ifindex = qdisc_dev(q)->ifindex;
1449         tcm->tcm_parent = q->handle;
1450         tcm->tcm_handle = q->handle;
1451         tcm->tcm_info = 0;
1452         NLA_PUT_STRING(skb, TCA_KIND, q->ops->id);
1453         if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1454                 goto nla_put_failure;
1455
1456         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1457                                          TCA_XSTATS, qdisc_root_lock(q), &d) < 0)
1458                 goto nla_put_failure;
1459
1460         if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1461                 goto nla_put_failure;
1462
1463         if (gnet_stats_finish_copy(&d) < 0)
1464                 goto nla_put_failure;
1465
1466         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1467         return skb->len;
1468
1469 nlmsg_failure:
1470 nla_put_failure:
1471         nlmsg_trim(skb, b);
1472         return -1;
1473 }
1474
1475 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1476                           struct Qdisc *q, unsigned long cl, int event)
1477 {
1478         struct sk_buff *skb;
1479         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1480
1481         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1482         if (!skb)
1483                 return -ENOBUFS;
1484
1485         if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) {
1486                 kfree_skb(skb);
1487                 return -EINVAL;
1488         }
1489
1490         return rtnetlink_send(skb, &init_net, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1491 }
1492
1493 struct qdisc_dump_args
1494 {
1495         struct qdisc_walker w;
1496         struct sk_buff *skb;
1497         struct netlink_callback *cb;
1498 };
1499
1500 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg)
1501 {
1502         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
1503
1504         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid,
1505                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS);
1506 }
1507
1508 static int tc_dump_tclass_qdisc(struct Qdisc *q, struct sk_buff *skb,
1509                                 struct tcmsg *tcm, struct netlink_callback *cb,
1510                                 int *t_p, int s_t)
1511 {
1512         struct qdisc_dump_args arg;
1513
1514         if (tc_qdisc_dump_ignore(q) ||
1515             *t_p < s_t || !q->ops->cl_ops ||
1516             (tcm->tcm_parent &&
1517              TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
1518                 (*t_p)++;
1519                 return 0;
1520         }
1521         if (*t_p > s_t)
1522                 memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
1523         arg.w.fn = qdisc_class_dump;
1524         arg.skb = skb;
1525         arg.cb = cb;
1526         arg.w.stop  = 0;
1527         arg.w.skip = cb->args[1];
1528         arg.w.count = 0;
1529         q->ops->cl_ops->walk(q, &arg.w);
1530         cb->args[1] = arg.w.count;
1531         if (arg.w.stop)
1532                 return -1;
1533         (*t_p)++;
1534         return 0;
1535 }
1536
1537 static int tc_dump_tclass_root(struct Qdisc *root, struct sk_buff *skb,
1538                                struct tcmsg *tcm, struct netlink_callback *cb,
1539                                int *t_p, int s_t)
1540 {
1541         struct Qdisc *q;
1542
1543         if (!root)
1544                 return 0;
1545
1546         if (tc_dump_tclass_qdisc(root, skb, tcm, cb, t_p, s_t) < 0)
1547                 return -1;
1548
1549         list_for_each_entry(q, &root->list, list) {
1550                 if (tc_dump_tclass_qdisc(q, skb, tcm, cb, t_p, s_t) < 0)
1551                         return -1;
1552         }
1553
1554         return 0;
1555 }
1556
1557 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
1558 {
1559         struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh);
1560         struct net *net = sock_net(skb->sk);
1561         struct netdev_queue *dev_queue;
1562         struct net_device *dev;
1563         int t, s_t;
1564
1565         if (net != &init_net)
1566                 return 0;
1567
1568         if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm)))
1569                 return 0;
1570         if ((dev = dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
1571                 return 0;
1572
1573         s_t = cb->args[0];
1574         t = 0;
1575
1576         dev_queue = netdev_get_tx_queue(dev, 0);
1577         if (tc_dump_tclass_root(dev_queue->qdisc_sleeping, skb, tcm, cb, &t, s_t) < 0)
1578                 goto done;
1579
1580         dev_queue = &dev->rx_queue;
1581         if (tc_dump_tclass_root(dev_queue->qdisc_sleeping, skb, tcm, cb, &t, s_t) < 0)
1582                 goto done;
1583
1584 done:
1585         cb->args[0] = t;
1586
1587         dev_put(dev);
1588         return skb->len;
1589 }
1590
1591 /* Main classifier routine: scans classifier chain attached
1592    to this qdisc, (optionally) tests for protocol and asks
1593    specific classifiers.
1594  */
1595 int tc_classify_compat(struct sk_buff *skb, struct tcf_proto *tp,
1596                        struct tcf_result *res)
1597 {
1598         __be16 protocol = skb->protocol;
1599         int err = 0;
1600
1601         for (; tp; tp = tp->next) {
1602                 if ((tp->protocol == protocol ||
1603                      tp->protocol == htons(ETH_P_ALL)) &&
1604                     (err = tp->classify(skb, tp, res)) >= 0) {
1605 #ifdef CONFIG_NET_CLS_ACT
1606                         if (err != TC_ACT_RECLASSIFY && skb->tc_verd)
1607                                 skb->tc_verd = SET_TC_VERD(skb->tc_verd, 0);
1608 #endif
1609                         return err;
1610                 }
1611         }
1612         return -1;
1613 }
1614 EXPORT_SYMBOL(tc_classify_compat);
1615
1616 int tc_classify(struct sk_buff *skb, struct tcf_proto *tp,
1617                 struct tcf_result *res)
1618 {
1619         int err = 0;
1620         __be16 protocol;
1621 #ifdef CONFIG_NET_CLS_ACT
1622         struct tcf_proto *otp = tp;
1623 reclassify:
1624 #endif
1625         protocol = skb->protocol;
1626
1627         err = tc_classify_compat(skb, tp, res);
1628 #ifdef CONFIG_NET_CLS_ACT
1629         if (err == TC_ACT_RECLASSIFY) {
1630                 u32 verd = G_TC_VERD(skb->tc_verd);
1631                 tp = otp;
1632
1633                 if (verd++ >= MAX_REC_LOOP) {
1634                         printk("rule prio %u protocol %02x reclassify loop, "
1635                                "packet dropped\n",
1636                                tp->prio&0xffff, ntohs(tp->protocol));
1637                         return TC_ACT_SHOT;
1638                 }
1639                 skb->tc_verd = SET_TC_VERD(skb->tc_verd, verd);
1640                 goto reclassify;
1641         }
1642 #endif
1643         return err;
1644 }
1645 EXPORT_SYMBOL(tc_classify);
1646
1647 void tcf_destroy(struct tcf_proto *tp)
1648 {
1649         tp->ops->destroy(tp);
1650         module_put(tp->ops->owner);
1651         kfree(tp);
1652 }
1653
1654 void tcf_destroy_chain(struct tcf_proto **fl)
1655 {
1656         struct tcf_proto *tp;
1657
1658         while ((tp = *fl) != NULL) {
1659                 *fl = tp->next;
1660                 tcf_destroy(tp);
1661         }
1662 }
1663 EXPORT_SYMBOL(tcf_destroy_chain);
1664
1665 #ifdef CONFIG_PROC_FS
1666 static int psched_show(struct seq_file *seq, void *v)
1667 {
1668         struct timespec ts;
1669
1670         hrtimer_get_res(CLOCK_MONOTONIC, &ts);
1671         seq_printf(seq, "%08x %08x %08x %08x\n",
1672                    (u32)NSEC_PER_USEC, (u32)PSCHED_US2NS(1),
1673                    1000000,
1674                    (u32)NSEC_PER_SEC/(u32)ktime_to_ns(timespec_to_ktime(ts)));
1675
1676         return 0;
1677 }
1678
1679 static int psched_open(struct inode *inode, struct file *file)
1680 {
1681         return single_open(file, psched_show, PDE(inode)->data);
1682 }
1683
1684 static const struct file_operations psched_fops = {
1685         .owner = THIS_MODULE,
1686         .open = psched_open,
1687         .read  = seq_read,
1688         .llseek = seq_lseek,
1689         .release = single_release,
1690 };
1691 #endif
1692
1693 static int __init pktsched_init(void)
1694 {
1695         register_qdisc(&pfifo_qdisc_ops);
1696         register_qdisc(&bfifo_qdisc_ops);
1697         proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
1698
1699         rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL);
1700         rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL);
1701         rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc);
1702         rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL);
1703         rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL);
1704         rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass);
1705
1706         return 0;
1707 }
1708
1709 subsys_initcall(pktsched_init);