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