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