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