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                 qdisc_destroy(old);
 643 }
 644
 645 /* Graft qdisc "new" to class "classid" of qdisc "parent" or
 646  * to device "dev".
 647  *
 648  * When appropriate send a netlink notification using 'skb'
 649  * and "n".
 650  *
 651  * On success, destroy old qdisc.
 652  */
 653
 654 static int qdisc_graft(struct net_device *dev, struct Qdisc *parent,
 655                        struct sk_buff *skb, struct nlmsghdr *n, u32 classid,
 656                        struct Qdisc *new, struct Qdisc *old)
 657 {
 658         struct Qdisc *q = old;
 659         int err = 0;
 660
 661         if (parent == NULL) {
 662                 unsigned int i, num_q, ingress;
 663
 664                 ingress = 0;
 665                 num_q = dev->num_tx_queues;
 666                 if ((q && q->flags & TCQ_F_INGRESS) ||
 667                     (new && new->flags & TCQ_F_INGRESS)) {
 668                         num_q = 1;
 669                         ingress = 1;
 670                 }
 671
 672                 if (dev->flags & IFF_UP)
 673                         dev_deactivate(dev);
 674
 675                 for (i = 0; i < num_q; i++) {
 676                         struct netdev_queue *dev_queue = &dev->rx_queue;
 677
 678                         if (!ingress)
 679                                 dev_queue = netdev_get_tx_queue(dev, i);
 680
 681                         old = dev_graft_qdisc(dev_queue, new);
 682                         if (new && i > 0)
 683                                 atomic_inc(&new->refcnt);
 684
 685                         notify_and_destroy(skb, n, classid, old, new);
 686                 }
 687
 688                 if (dev->flags & IFF_UP)
 689                         dev_activate(dev);
 690         } else {
 691                 const struct Qdisc_class_ops *cops = parent->ops->cl_ops;
 692
 693                 err = -EINVAL;
 694
 695                 if (cops) {
 696                         unsigned long cl = cops->get(parent, classid);
 697                         if (cl) {
 698                                 err = cops->graft(parent, cl, new, &old);
 699                                 cops->put(parent, cl);
 700                         }
 701                 }
 702                 if (!err)
 703                         notify_and_destroy(skb, n, classid, old, new);
 704         }
 705         return err;
 706 }
 707
 708 /* lockdep annotation is needed for ingress; egress gets it only for name */
 709 static struct lock_class_key qdisc_tx_lock;
 710 static struct lock_class_key qdisc_rx_lock;
 711
 712 /*
 713    Allocate and initialize new qdisc.
 714
 715    Parameters are passed via opt.
 716  */
 717
 718 static struct Qdisc *
 719 qdisc_create(struct net_device *dev, struct netdev_queue *dev_queue,
 720              u32 parent, u32 handle, struct nlattr **tca, int *errp)
 721 {
 722         int err;
 723         struct nlattr *kind = tca[TCA_KIND];
 724         struct Qdisc *sch;
 725         struct Qdisc_ops *ops;
 726         struct qdisc_size_table *stab;
 727
 728         ops = qdisc_lookup_ops(kind);
 729 #ifdef CONFIG_KMOD
 730         if (ops == NULL && kind != NULL) {
 731                 char name[IFNAMSIZ];
 732                 if (nla_strlcpy(name, kind, IFNAMSIZ) < IFNAMSIZ) {
 733                         /* We dropped the RTNL semaphore in order to
 734                          * perform the module load.  So, even if we
 735                          * succeeded in loading the module we have to
 736                          * tell the caller to replay the request.  We
 737                          * indicate this using -EAGAIN.
 738                          * We replay the request because the device may
 739                          * go away in the mean time.
 740                          */
 741                         rtnl_unlock();
 742                         request_module("sch_%s", name);
 743                         rtnl_lock();
 744                         ops = qdisc_lookup_ops(kind);
 745                         if (ops != NULL) {
 746                                 /* We will try again qdisc_lookup_ops,
 747                                  * so don't keep a reference.
 748                                  */
 749                                 module_put(ops->owner);
 750                                 err = -EAGAIN;
 751                                 goto err_out;
 752                         }
 753                 }
 754         }
 755 #endif
 756
 757         err = -ENOENT;
 758         if (ops == NULL)
 759                 goto err_out;
 760
 761         sch = qdisc_alloc(dev_queue, ops);
 762         if (IS_ERR(sch)) {
 763                 err = PTR_ERR(sch);
 764                 goto err_out2;
 765         }
 766
 767         sch->parent = parent;
 768
 769         if (handle == TC_H_INGRESS) {
 770                 sch->flags |= TCQ_F_INGRESS;
 771                 handle = TC_H_MAKE(TC_H_INGRESS, 0);
 772                 lockdep_set_class(qdisc_lock(sch), &qdisc_rx_lock);
 773         } else {
 774                 if (handle == 0) {
 775                         handle = qdisc_alloc_handle(dev);
 776                         err = -ENOMEM;
 777                         if (handle == 0)
 778                                 goto err_out3;
 779                 }
 780                 lockdep_set_class(qdisc_lock(sch), &qdisc_tx_lock);
 781         }
 782
 783         sch->handle = handle;
 784
 785         if (!ops->init || (err = ops->init(sch, tca[TCA_OPTIONS])) == 0) {
 786                 if (tca[TCA_STAB]) {
 787                         stab = qdisc_get_stab(tca[TCA_STAB]);
 788                         if (IS_ERR(stab)) {
 789                                 err = PTR_ERR(stab);
 790                                 goto err_out3;
 791                         }
 792                         sch->stab = stab;
 793                 }
 794                 if (tca[TCA_RATE]) {
 795                         err = gen_new_estimator(&sch->bstats, &sch->rate_est,
 796                                                 qdisc_root_lock(sch),
 797                                                 tca[TCA_RATE]);
 798                         if (err) {
 799                                 /*
 800                                  * Any broken qdiscs that would require
 801                                  * a ops->reset() here? The qdisc was never
 802                                  * in action so it shouldn't be necessary.
 803                                  */
 804                                 if (ops->destroy)
 805                                         ops->destroy(sch);
 806                                 goto err_out3;
 807                         }
 808                 }
 809                 if ((parent != TC_H_ROOT) && !(sch->flags & TCQ_F_INGRESS))
 810                         list_add_tail(&sch->list, &dev_queue->qdisc_sleeping->list);
 811
 812                 return sch;
 813         }
 814 err_out3:
 815         qdisc_put_stab(sch->stab);
 816         dev_put(dev);
 817         kfree((char *) sch - sch->padded);
 818 err_out2:
 819         module_put(ops->owner);
 820 err_out:
 821         *errp = err;
 822         return NULL;
 823 }
 824
 825 static int qdisc_change(struct Qdisc *sch, struct nlattr **tca)
 826 {
 827         struct qdisc_size_table *stab = NULL;
 828         int err = 0;
 829
 830         if (tca[TCA_OPTIONS]) {
 831                 if (sch->ops->change == NULL)
 832                         return -EINVAL;
 833                 err = sch->ops->change(sch, tca[TCA_OPTIONS]);
 834                 if (err)
 835                         return err;
 836         }
 837
 838         if (tca[TCA_STAB]) {
 839                 stab = qdisc_get_stab(tca[TCA_STAB]);
 840                 if (IS_ERR(stab))
 841                         return PTR_ERR(stab);
 842         }
 843
 844         qdisc_put_stab(sch->stab);
 845         sch->stab = stab;
 846
 847         if (tca[TCA_RATE])
 848                 gen_replace_estimator(&sch->bstats, &sch->rate_est,
 849                                       qdisc_root_lock(sch), tca[TCA_RATE]);
 850         return 0;
 851 }
 852
 853 struct check_loop_arg
 854 {
 855         struct qdisc_walker     w;
 856         struct Qdisc            *p;
 857         int                     depth;
 858 };
 859
 860 static int check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w);
 861
 862 static int check_loop(struct Qdisc *q, struct Qdisc *p, int depth)
 863 {
 864         struct check_loop_arg   arg;
 865
 866         if (q->ops->cl_ops == NULL)
 867                 return 0;
 868
 869         arg.w.stop = arg.w.skip = arg.w.count = 0;
 870         arg.w.fn = check_loop_fn;
 871         arg.depth = depth;
 872         arg.p = p;
 873         q->ops->cl_ops->walk(q, &arg.w);
 874         return arg.w.stop ? -ELOOP : 0;
 875 }
 876
 877 static int
 878 check_loop_fn(struct Qdisc *q, unsigned long cl, struct qdisc_walker *w)
 879 {
 880         struct Qdisc *leaf;
 881         const struct Qdisc_class_ops *cops = q->ops->cl_ops;
 882         struct check_loop_arg *arg = (struct check_loop_arg *)w;
 883
 884         leaf = cops->leaf(q, cl);
 885         if (leaf) {
 886                 if (leaf == arg->p || arg->depth > 7)
 887                         return -ELOOP;
 888                 return check_loop(leaf, arg->p, arg->depth + 1);
 889         }
 890         return 0;
 891 }
 892
 893 /*
 894  * Delete/get qdisc.
 895  */
 896
 897 static int tc_get_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 898 {
 899         struct net *net = sock_net(skb->sk);
 900         struct tcmsg *tcm = NLMSG_DATA(n);
 901         struct nlattr *tca[TCA_MAX + 1];
 902         struct net_device *dev;
 903         u32 clid = tcm->tcm_parent;
 904         struct Qdisc *q = NULL;
 905         struct Qdisc *p = NULL;
 906         int err;
 907
 908         if (net != &init_net)
 909                 return -EINVAL;
 910
 911         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
 912                 return -ENODEV;
 913
 914         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, NULL);
 915         if (err < 0)
 916                 return err;
 917
 918         if (clid) {
 919                 if (clid != TC_H_ROOT) {
 920                         if (TC_H_MAJ(clid) != TC_H_MAJ(TC_H_INGRESS)) {
 921                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
 922                                         return -ENOENT;
 923                                 q = qdisc_leaf(p, clid);
 924                         } else { /* ingress */
 925                                 q = dev->rx_queue.qdisc_sleeping;
 926                         }
 927                 } else {
 928                         struct netdev_queue *dev_queue;
 929                         dev_queue = netdev_get_tx_queue(dev, 0);
 930                         q = dev_queue->qdisc_sleeping;
 931                 }
 932                 if (!q)
 933                         return -ENOENT;
 934
 935                 if (tcm->tcm_handle && q->handle != tcm->tcm_handle)
 936                         return -EINVAL;
 937         } else {
 938                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
 939                         return -ENOENT;
 940         }
 941
 942         if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id))
 943                 return -EINVAL;
 944
 945         if (n->nlmsg_type == RTM_DELQDISC) {
 946                 if (!clid)
 947                         return -EINVAL;
 948                 if (q->handle == 0)
 949                         return -ENOENT;
 950                 if ((err = qdisc_graft(dev, p, skb, n, clid, NULL, q)) != 0)
 951                         return err;
 952         } else {
 953                 qdisc_notify(skb, n, clid, NULL, q);
 954         }
 955         return 0;
 956 }
 957
 958 /*
 959    Create/change qdisc.
 960  */
 961
 962 static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
 963 {
 964         struct net *net = sock_net(skb->sk);
 965         struct tcmsg *tcm;
 966         struct nlattr *tca[TCA_MAX + 1];
 967         struct net_device *dev;
 968         u32 clid;
 969         struct Qdisc *q, *p;
 970         int err;
 971
 972         if (net != &init_net)
 973                 return -EINVAL;
 974
 975 replay:
 976         /* Reinit, just in case something touches this. */
 977         tcm = NLMSG_DATA(n);
 978         clid = tcm->tcm_parent;
 979         q = p = NULL;
 980
 981         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
 982                 return -ENODEV;
 983
 984         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, NULL);
 985         if (err < 0)
 986                 return err;
 987
 988         if (clid) {
 989                 if (clid != TC_H_ROOT) {
 990                         if (clid != TC_H_INGRESS) {
 991                                 if ((p = qdisc_lookup(dev, TC_H_MAJ(clid))) == NULL)
 992                                         return -ENOENT;
 993                                 q = qdisc_leaf(p, clid);
 994                         } else { /*ingress */
 995                                 q = dev->rx_queue.qdisc_sleeping;
 996                         }
 997                 } else {
 998                         struct netdev_queue *dev_queue;
 999                         dev_queue = netdev_get_tx_queue(dev, 0);
1000                         q = dev_queue->qdisc_sleeping;
1001                 }
1002
1003                 /* It may be default qdisc, ignore it */
1004                 if (q && q->handle == 0)
1005                         q = NULL;
1006
1007                 if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) {
1008                         if (tcm->tcm_handle) {
1009                                 if (q && !(n->nlmsg_flags&NLM_F_REPLACE))
1010                                         return -EEXIST;
1011                                 if (TC_H_MIN(tcm->tcm_handle))
1012                                         return -EINVAL;
1013                                 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL)
1014                                         goto create_n_graft;
1015                                 if (n->nlmsg_flags&NLM_F_EXCL)
1016                                         return -EEXIST;
1017                                 if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id))
1018                                         return -EINVAL;
1019                                 if (q == p ||
1020                                     (p && check_loop(q, p, 0)))
1021                                         return -ELOOP;
1022                                 atomic_inc(&q->refcnt);
1023                                 goto graft;
1024                         } else {
1025                                 if (q == NULL)
1026                                         goto create_n_graft;
1027
1028                                 /* This magic test requires explanation.
1029                                  *
1030                                  *   We know, that some child q is already
1031                                  *   attached to this parent and have choice:
1032                                  *   either to change it or to create/graft new one.
1033                                  *
1034                                  *   1. We are allowed to create/graft only
1035                                  *   if CREATE and REPLACE flags are set.
1036                                  *
1037                                  *   2. If EXCL is set, requestor wanted to say,
1038                                  *   that qdisc tcm_handle is not expected
1039                                  *   to exist, so that we choose create/graft too.
1040                                  *
1041                                  *   3. The last case is when no flags are set.
1042                                  *   Alas, it is sort of hole in API, we
1043                                  *   cannot decide what to do unambiguously.
1044                                  *   For now we select create/graft, if
1045                                  *   user gave KIND, which does not match existing.
1046                                  */
1047                                 if ((n->nlmsg_flags&NLM_F_CREATE) &&
1048                                     (n->nlmsg_flags&NLM_F_REPLACE) &&
1049                                     ((n->nlmsg_flags&NLM_F_EXCL) ||
1050                                      (tca[TCA_KIND] &&
1051                                       nla_strcmp(tca[TCA_KIND], q->ops->id))))
1052                                         goto create_n_graft;
1053                         }
1054                 }
1055         } else {
1056                 if (!tcm->tcm_handle)
1057                         return -EINVAL;
1058                 q = qdisc_lookup(dev, tcm->tcm_handle);
1059         }
1060
1061         /* Change qdisc parameters */
1062         if (q == NULL)
1063                 return -ENOENT;
1064         if (n->nlmsg_flags&NLM_F_EXCL)
1065                 return -EEXIST;
1066         if (tca[TCA_KIND] && nla_strcmp(tca[TCA_KIND], q->ops->id))
1067                 return -EINVAL;
1068         err = qdisc_change(q, tca);
1069         if (err == 0)
1070                 qdisc_notify(skb, n, clid, NULL, q);
1071         return err;
1072
1073 create_n_graft:
1074         if (!(n->nlmsg_flags&NLM_F_CREATE))
1075                 return -ENOENT;
1076         if (clid == TC_H_INGRESS)
1077                 q = qdisc_create(dev, &dev->rx_queue,
1078                                  tcm->tcm_parent, tcm->tcm_parent,
1079                                  tca, &err);
1080         else
1081                 q = qdisc_create(dev, netdev_get_tx_queue(dev, 0),
1082                                  tcm->tcm_parent, tcm->tcm_handle,
1083                                  tca, &err);
1084         if (q == NULL) {
1085                 if (err == -EAGAIN)
1086                         goto replay;
1087                 return err;
1088         }
1089
1090 graft:
1091         if (1) {
1092                 err = qdisc_graft(dev, p, skb, n, clid, q, NULL);
1093                 if (err) {
1094                         if (q)
1095                                 qdisc_destroy(q);
1096                         return err;
1097                 }
1098         }
1099         return 0;
1100 }
1101
1102 static int tc_fill_qdisc(struct sk_buff *skb, struct Qdisc *q, u32 clid,
1103                          u32 pid, u32 seq, u16 flags, int event)
1104 {
1105         struct tcmsg *tcm;
1106         struct nlmsghdr  *nlh;
1107         unsigned char *b = skb_tail_pointer(skb);
1108         struct gnet_dump d;
1109
1110         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
1111         tcm = NLMSG_DATA(nlh);
1112         tcm->tcm_family = AF_UNSPEC;
1113         tcm->tcm__pad1 = 0;
1114         tcm->tcm__pad2 = 0;
1115         tcm->tcm_ifindex = qdisc_dev(q)->ifindex;
1116         tcm->tcm_parent = clid;
1117         tcm->tcm_handle = q->handle;
1118         tcm->tcm_info = atomic_read(&q->refcnt);
1119         NLA_PUT_STRING(skb, TCA_KIND, q->ops->id);
1120         if (q->ops->dump && q->ops->dump(q, skb) < 0)
1121                 goto nla_put_failure;
1122         q->qstats.qlen = q->q.qlen;
1123
1124         if (q->stab && qdisc_dump_stab(skb, q->stab) < 0)
1125                 goto nla_put_failure;
1126
1127         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1128                                          TCA_XSTATS, qdisc_root_lock(q), &d) < 0)
1129                 goto nla_put_failure;
1130
1131         if (q->ops->dump_stats && q->ops->dump_stats(q, &d) < 0)
1132                 goto nla_put_failure;
1133
1134         if (gnet_stats_copy_basic(&d, &q->bstats) < 0 ||
1135             gnet_stats_copy_rate_est(&d, &q->rate_est) < 0 ||
1136             gnet_stats_copy_queue(&d, &q->qstats) < 0)
1137                 goto nla_put_failure;
1138
1139         if (gnet_stats_finish_copy(&d) < 0)
1140                 goto nla_put_failure;
1141
1142         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1143         return skb->len;
1144
1145 nlmsg_failure:
1146 nla_put_failure:
1147         nlmsg_trim(skb, b);
1148         return -1;
1149 }
1150
1151 static int qdisc_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1152                         u32 clid, struct Qdisc *old, struct Qdisc *new)
1153 {
1154         struct sk_buff *skb;
1155         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1156
1157         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1158         if (!skb)
1159                 return -ENOBUFS;
1160
1161         if (old && old->handle) {
1162                 if (tc_fill_qdisc(skb, old, clid, pid, n->nlmsg_seq, 0, RTM_DELQDISC) < 0)
1163                         goto err_out;
1164         }
1165         if (new) {
1166                 if (tc_fill_qdisc(skb, new, clid, pid, n->nlmsg_seq, old ? NLM_F_REPLACE : 0, RTM_NEWQDISC) < 0)
1167                         goto err_out;
1168         }
1169
1170         if (skb->len)
1171                 return rtnetlink_send(skb, &init_net, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1172
1173 err_out:
1174         kfree_skb(skb);
1175         return -EINVAL;
1176 }
1177
1178 static bool tc_qdisc_dump_ignore(struct Qdisc *q)
1179 {
1180         return (q->flags & TCQ_F_BUILTIN) ? true : false;
1181 }
1182
1183 static int tc_dump_qdisc_root(struct Qdisc *root, struct sk_buff *skb,
1184                               struct netlink_callback *cb,
1185                               int *q_idx_p, int s_q_idx)
1186 {
1187         int ret = 0, q_idx = *q_idx_p;
1188         struct Qdisc *q;
1189
1190         if (!root)
1191                 return 0;
1192
1193         q = root;
1194         if (q_idx < s_q_idx) {
1195                 q_idx++;
1196         } else {
1197                 if (!tc_qdisc_dump_ignore(q) &&
1198                     tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
1199                                   cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0)
1200                         goto done;
1201                 q_idx++;
1202         }
1203         list_for_each_entry(q, &root->list, list) {
1204                 if (q_idx < s_q_idx) {
1205                         q_idx++;
1206                         continue;
1207                 }
1208                 if (!tc_qdisc_dump_ignore(q) &&
1209                     tc_fill_qdisc(skb, q, q->parent, NETLINK_CB(cb->skb).pid,
1210                                   cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWQDISC) <= 0)
1211                         goto done;
1212                 q_idx++;
1213         }
1214
1215 out:
1216         *q_idx_p = q_idx;
1217         return ret;
1218 done:
1219         ret = -1;
1220         goto out;
1221 }
1222
1223 static int tc_dump_qdisc(struct sk_buff *skb, struct netlink_callback *cb)
1224 {
1225         struct net *net = sock_net(skb->sk);
1226         int idx, q_idx;
1227         int s_idx, s_q_idx;
1228         struct net_device *dev;
1229
1230         if (net != &init_net)
1231                 return 0;
1232
1233         s_idx = cb->args[0];
1234         s_q_idx = q_idx = cb->args[1];
1235         read_lock(&dev_base_lock);
1236         idx = 0;
1237         for_each_netdev(&init_net, dev) {
1238                 struct netdev_queue *dev_queue;
1239
1240                 if (idx < s_idx)
1241                         goto cont;
1242                 if (idx > s_idx)
1243                         s_q_idx = 0;
1244                 q_idx = 0;
1245
1246                 dev_queue = netdev_get_tx_queue(dev, 0);
1247                 if (tc_dump_qdisc_root(dev_queue->qdisc_sleeping, skb, cb, &q_idx, s_q_idx) < 0)
1248                         goto done;
1249
1250                 dev_queue = &dev->rx_queue;
1251                 if (tc_dump_qdisc_root(dev_queue->qdisc_sleeping, skb, cb, &q_idx, s_q_idx) < 0)
1252                         goto done;
1253
1254 cont:
1255                 idx++;
1256         }
1257
1258 done:
1259         read_unlock(&dev_base_lock);
1260
1261         cb->args[0] = idx;
1262         cb->args[1] = q_idx;
1263
1264         return skb->len;
1265 }
1266
1267
1268
1269 /************************************************
1270  *      Traffic classes manipulation.           *
1271  ************************************************/
1272
1273
1274
1275 static int tc_ctl_tclass(struct sk_buff *skb, struct nlmsghdr *n, void *arg)
1276 {
1277         struct net *net = sock_net(skb->sk);
1278         struct netdev_queue *dev_queue;
1279         struct tcmsg *tcm = NLMSG_DATA(n);
1280         struct nlattr *tca[TCA_MAX + 1];
1281         struct net_device *dev;
1282         struct Qdisc *q = NULL;
1283         const struct Qdisc_class_ops *cops;
1284         unsigned long cl = 0;
1285         unsigned long new_cl;
1286         u32 pid = tcm->tcm_parent;
1287         u32 clid = tcm->tcm_handle;
1288         u32 qid = TC_H_MAJ(clid);
1289         int err;
1290
1291         if (net != &init_net)
1292                 return -EINVAL;
1293
1294         if ((dev = __dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
1295                 return -ENODEV;
1296
1297         err = nlmsg_parse(n, sizeof(*tcm), tca, TCA_MAX, NULL);
1298         if (err < 0)
1299                 return err;
1300
1301         /*
1302            parent == TC_H_UNSPEC - unspecified parent.
1303            parent == TC_H_ROOT   - class is root, which has no parent.
1304            parent == X:0         - parent is root class.
1305            parent == X:Y         - parent is a node in hierarchy.
1306            parent == 0:Y         - parent is X:Y, where X:0 is qdisc.
1307
1308            handle == 0:0         - generate handle from kernel pool.
1309            handle == 0:Y         - class is X:Y, where X:0 is qdisc.
1310            handle == X:Y         - clear.
1311            handle == X:0         - root class.
1312          */
1313
1314         /* Step 1. Determine qdisc handle X:0 */
1315
1316         dev_queue = netdev_get_tx_queue(dev, 0);
1317         if (pid != TC_H_ROOT) {
1318                 u32 qid1 = TC_H_MAJ(pid);
1319
1320                 if (qid && qid1) {
1321                         /* If both majors are known, they must be identical. */
1322                         if (qid != qid1)
1323                                 return -EINVAL;
1324                 } else if (qid1) {
1325                         qid = qid1;
1326                 } else if (qid == 0)
1327                         qid = dev_queue->qdisc_sleeping->handle;
1328
1329                 /* Now qid is genuine qdisc handle consistent
1330                    both with parent and child.
1331
1332                    TC_H_MAJ(pid) still may be unspecified, complete it now.
1333                  */
1334                 if (pid)
1335                         pid = TC_H_MAKE(qid, pid);
1336         } else {
1337                 if (qid == 0)
1338                         qid = dev_queue->qdisc_sleeping->handle;
1339         }
1340
1341         /* OK. Locate qdisc */
1342         if ((q = qdisc_lookup(dev, qid)) == NULL)
1343                 return -ENOENT;
1344
1345         /* An check that it supports classes */
1346         cops = q->ops->cl_ops;
1347         if (cops == NULL)
1348                 return -EINVAL;
1349
1350         /* Now try to get class */
1351         if (clid == 0) {
1352                 if (pid == TC_H_ROOT)
1353                         clid = qid;
1354         } else
1355                 clid = TC_H_MAKE(qid, clid);
1356
1357         if (clid)
1358                 cl = cops->get(q, clid);
1359
1360         if (cl == 0) {
1361                 err = -ENOENT;
1362                 if (n->nlmsg_type != RTM_NEWTCLASS || !(n->nlmsg_flags&NLM_F_CREATE))
1363                         goto out;
1364         } else {
1365                 switch (n->nlmsg_type) {
1366                 case RTM_NEWTCLASS:
1367                         err = -EEXIST;
1368                         if (n->nlmsg_flags&NLM_F_EXCL)
1369                                 goto out;
1370                         break;
1371                 case RTM_DELTCLASS:
1372                         err = cops->delete(q, cl);
1373                         if (err == 0)
1374                                 tclass_notify(skb, n, q, cl, RTM_DELTCLASS);
1375                         goto out;
1376                 case RTM_GETTCLASS:
1377                         err = tclass_notify(skb, n, q, cl, RTM_NEWTCLASS);
1378                         goto out;
1379                 default:
1380                         err = -EINVAL;
1381                         goto out;
1382                 }
1383         }
1384
1385         new_cl = cl;
1386         err = cops->change(q, clid, pid, tca, &new_cl);
1387         if (err == 0)
1388                 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
1389
1390 out:
1391         if (cl)
1392                 cops->put(q, cl);
1393
1394         return err;
1395 }
1396
1397
1398 static int tc_fill_tclass(struct sk_buff *skb, struct Qdisc *q,
1399                           unsigned long cl,
1400                           u32 pid, u32 seq, u16 flags, int event)
1401 {
1402         struct tcmsg *tcm;
1403         struct nlmsghdr  *nlh;
1404         unsigned char *b = skb_tail_pointer(skb);
1405         struct gnet_dump d;
1406         const struct Qdisc_class_ops *cl_ops = q->ops->cl_ops;
1407
1408         nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*tcm), flags);
1409         tcm = NLMSG_DATA(nlh);
1410         tcm->tcm_family = AF_UNSPEC;
1411         tcm->tcm_ifindex = qdisc_dev(q)->ifindex;
1412         tcm->tcm_parent = q->handle;
1413         tcm->tcm_handle = q->handle;
1414         tcm->tcm_info = 0;
1415         NLA_PUT_STRING(skb, TCA_KIND, q->ops->id);
1416         if (cl_ops->dump && cl_ops->dump(q, cl, skb, tcm) < 0)
1417                 goto nla_put_failure;
1418
1419         if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
1420                                          TCA_XSTATS, qdisc_root_lock(q), &d) < 0)
1421                 goto nla_put_failure;
1422
1423         if (cl_ops->dump_stats && cl_ops->dump_stats(q, cl, &d) < 0)
1424                 goto nla_put_failure;
1425
1426         if (gnet_stats_finish_copy(&d) < 0)
1427                 goto nla_put_failure;
1428
1429         nlh->nlmsg_len = skb_tail_pointer(skb) - b;
1430         return skb->len;
1431
1432 nlmsg_failure:
1433 nla_put_failure:
1434         nlmsg_trim(skb, b);
1435         return -1;
1436 }
1437
1438 static int tclass_notify(struct sk_buff *oskb, struct nlmsghdr *n,
1439                           struct Qdisc *q, unsigned long cl, int event)
1440 {
1441         struct sk_buff *skb;
1442         u32 pid = oskb ? NETLINK_CB(oskb).pid : 0;
1443
1444         skb = alloc_skb(NLMSG_GOODSIZE, GFP_KERNEL);
1445         if (!skb)
1446                 return -ENOBUFS;
1447
1448         if (tc_fill_tclass(skb, q, cl, pid, n->nlmsg_seq, 0, event) < 0) {
1449                 kfree_skb(skb);
1450                 return -EINVAL;
1451         }
1452
1453         return rtnetlink_send(skb, &init_net, pid, RTNLGRP_TC, n->nlmsg_flags&NLM_F_ECHO);
1454 }
1455
1456 struct qdisc_dump_args
1457 {
1458         struct qdisc_walker w;
1459         struct sk_buff *skb;
1460         struct netlink_callback *cb;
1461 };
1462
1463 static int qdisc_class_dump(struct Qdisc *q, unsigned long cl, struct qdisc_walker *arg)
1464 {
1465         struct qdisc_dump_args *a = (struct qdisc_dump_args *)arg;
1466
1467         return tc_fill_tclass(a->skb, q, cl, NETLINK_CB(a->cb->skb).pid,
1468                               a->cb->nlh->nlmsg_seq, NLM_F_MULTI, RTM_NEWTCLASS);
1469 }
1470
1471 static int tc_dump_tclass_qdisc(struct Qdisc *q, struct sk_buff *skb,
1472                                 struct tcmsg *tcm, struct netlink_callback *cb,
1473                                 int *t_p, int s_t)
1474 {
1475         struct qdisc_dump_args arg;
1476
1477         if (tc_qdisc_dump_ignore(q) ||
1478             *t_p < s_t || !q->ops->cl_ops ||
1479             (tcm->tcm_parent &&
1480              TC_H_MAJ(tcm->tcm_parent) != q->handle)) {
1481                 (*t_p)++;
1482                 return 0;
1483         }
1484         if (*t_p > s_t)
1485                 memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0]));
1486         arg.w.fn = qdisc_class_dump;
1487         arg.skb = skb;
1488         arg.cb = cb;
1489         arg.w.stop  = 0;
1490         arg.w.skip = cb->args[1];
1491         arg.w.count = 0;
1492         q->ops->cl_ops->walk(q, &arg.w);
1493         cb->args[1] = arg.w.count;
1494         if (arg.w.stop)
1495                 return -1;
1496         (*t_p)++;
1497         return 0;
1498 }
1499
1500 static int tc_dump_tclass_root(struct Qdisc *root, struct sk_buff *skb,
1501                                struct tcmsg *tcm, struct netlink_callback *cb,
1502                                int *t_p, int s_t)
1503 {
1504         struct Qdisc *q;
1505
1506         if (!root)
1507                 return 0;
1508
1509         if (tc_dump_tclass_qdisc(root, skb, tcm, cb, t_p, s_t) < 0)
1510                 return -1;
1511
1512         list_for_each_entry(q, &root->list, list) {
1513                 if (tc_dump_tclass_qdisc(q, skb, tcm, cb, t_p, s_t) < 0)
1514                         return -1;
1515         }
1516
1517         return 0;
1518 }
1519
1520 static int tc_dump_tclass(struct sk_buff *skb, struct netlink_callback *cb)
1521 {
1522         struct tcmsg *tcm = (struct tcmsg*)NLMSG_DATA(cb->nlh);
1523         struct net *net = sock_net(skb->sk);
1524         struct netdev_queue *dev_queue;
1525         struct net_device *dev;
1526         int t, s_t;
1527
1528         if (net != &init_net)
1529                 return 0;
1530
1531         if (cb->nlh->nlmsg_len < NLMSG_LENGTH(sizeof(*tcm)))
1532                 return 0;
1533         if ((dev = dev_get_by_index(&init_net, tcm->tcm_ifindex)) == NULL)
1534                 return 0;
1535
1536         s_t = cb->args[0];
1537         t = 0;
1538
1539         dev_queue = netdev_get_tx_queue(dev, 0);
1540         if (tc_dump_tclass_root(dev_queue->qdisc_sleeping, skb, tcm, cb, &t, s_t) < 0)
1541                 goto done;
1542
1543         dev_queue = &dev->rx_queue;
1544         if (tc_dump_tclass_root(dev_queue->qdisc_sleeping, skb, tcm, cb, &t, s_t) < 0)
1545                 goto done;
1546
1547 done:
1548         cb->args[0] = t;
1549
1550         dev_put(dev);
1551         return skb->len;
1552 }
1553
1554 /* Main classifier routine: scans classifier chain attached
1555    to this qdisc, (optionally) tests for protocol and asks
1556    specific classifiers.
1557  */
1558 int tc_classify_compat(struct sk_buff *skb, struct tcf_proto *tp,
1559                        struct tcf_result *res)
1560 {
1561         __be16 protocol = skb->protocol;
1562         int err = 0;
1563
1564         for (; tp; tp = tp->next) {
1565                 if ((tp->protocol == protocol ||
1566                      tp->protocol == htons(ETH_P_ALL)) &&
1567                     (err = tp->classify(skb, tp, res)) >= 0) {
1568 #ifdef CONFIG_NET_CLS_ACT
1569                         if (err != TC_ACT_RECLASSIFY && skb->tc_verd)
1570                                 skb->tc_verd = SET_TC_VERD(skb->tc_verd, 0);
1571 #endif
1572                         return err;
1573                 }
1574         }
1575         return -1;
1576 }
1577 EXPORT_SYMBOL(tc_classify_compat);
1578
1579 int tc_classify(struct sk_buff *skb, struct tcf_proto *tp,
1580                 struct tcf_result *res)
1581 {
1582         int err = 0;
1583         __be16 protocol;
1584 #ifdef CONFIG_NET_CLS_ACT
1585         struct tcf_proto *otp = tp;
1586 reclassify:
1587 #endif
1588         protocol = skb->protocol;
1589
1590         err = tc_classify_compat(skb, tp, res);
1591 #ifdef CONFIG_NET_CLS_ACT
1592         if (err == TC_ACT_RECLASSIFY) {
1593                 u32 verd = G_TC_VERD(skb->tc_verd);
1594                 tp = otp;
1595
1596                 if (verd++ >= MAX_REC_LOOP) {
1597                         printk("rule prio %u protocol %02x reclassify loop, "
1598                                "packet dropped\n",
1599                                tp->prio&0xffff, ntohs(tp->protocol));
1600                         return TC_ACT_SHOT;
1601                 }
1602                 skb->tc_verd = SET_TC_VERD(skb->tc_verd, verd);
1603                 goto reclassify;
1604         }
1605 #endif
1606         return err;
1607 }
1608 EXPORT_SYMBOL(tc_classify);
1609
1610 void tcf_destroy(struct tcf_proto *tp)
1611 {
1612         tp->ops->destroy(tp);
1613         module_put(tp->ops->owner);
1614         kfree(tp);
1615 }
1616
1617 void tcf_destroy_chain(struct tcf_proto **fl)
1618 {
1619         struct tcf_proto *tp;
1620
1621         while ((tp = *fl) != NULL) {
1622                 *fl = tp->next;
1623                 tcf_destroy(tp);
1624         }
1625 }
1626 EXPORT_SYMBOL(tcf_destroy_chain);
1627
1628 #ifdef CONFIG_PROC_FS
1629 static int psched_show(struct seq_file *seq, void *v)
1630 {
1631         struct timespec ts;
1632
1633         hrtimer_get_res(CLOCK_MONOTONIC, &ts);
1634         seq_printf(seq, "%08x %08x %08x %08x\n",
1635                    (u32)NSEC_PER_USEC, (u32)PSCHED_US2NS(1),
1636                    1000000,
1637                    (u32)NSEC_PER_SEC/(u32)ktime_to_ns(timespec_to_ktime(ts)));
1638
1639         return 0;
1640 }
1641
1642 static int psched_open(struct inode *inode, struct file *file)
1643 {
1644         return single_open(file, psched_show, PDE(inode)->data);
1645 }
1646
1647 static const struct file_operations psched_fops = {
1648         .owner = THIS_MODULE,
1649         .open = psched_open,
1650         .read  = seq_read,
1651         .llseek = seq_lseek,
1652         .release = single_release,
1653 };
1654 #endif
1655
1656 static int __init pktsched_init(void)
1657 {
1658         register_qdisc(&pfifo_qdisc_ops);
1659         register_qdisc(&bfifo_qdisc_ops);
1660         proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
1661
1662         rtnl_register(PF_UNSPEC, RTM_NEWQDISC, tc_modify_qdisc, NULL);
1663         rtnl_register(PF_UNSPEC, RTM_DELQDISC, tc_get_qdisc, NULL);
1664         rtnl_register(PF_UNSPEC, RTM_GETQDISC, tc_get_qdisc, tc_dump_qdisc);
1665         rtnl_register(PF_UNSPEC, RTM_NEWTCLASS, tc_ctl_tclass, NULL);
1666         rtnl_register(PF_UNSPEC, RTM_DELTCLASS, tc_ctl_tclass, NULL);
1667         rtnl_register(PF_UNSPEC, RTM_GETTCLASS, tc_ctl_tclass, tc_dump_tclass);
1668
1669         return 0;
1670 }
1671
1672 subsys_initcall(pktsched_init);