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