net/sched/sch_generic.c

   1 /*
   2  * net/sched/sch_generic.c      Generic packet scheduler routines.
   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  *              Jamal Hadi Salim, <hadi@cyberus.ca> 990601
  11  *              - Ingress support
  12  */
  13
  14 #include <asm/uaccess.h>
  15 #include <asm/system.h>
  16 #include <linux/bitops.h>
  17 #include <linux/config.h>
  18 #include <linux/module.h>
  19 #include <linux/types.h>
  20 #include <linux/kernel.h>
  21 #include <linux/sched.h>
  22 #include <linux/string.h>
  23 #include <linux/mm.h>
  24 #include <linux/socket.h>
  25 #include <linux/sockios.h>
  26 #include <linux/in.h>
  27 #include <linux/errno.h>
  28 #include <linux/interrupt.h>
  29 #include <linux/netdevice.h>
  30 #include <linux/skbuff.h>
  31 #include <linux/rtnetlink.h>
  32 #include <linux/init.h>
  33 #include <linux/rcupdate.h>
  34 #include <linux/list.h>
  35 #include <net/sock.h>
  36 #include <net/pkt_sched.h>
  37
  38 /* Main transmission queue. */
  39
  40 /* Main qdisc structure lock.
  41
  42    However, modifications
  43    to data, participating in scheduling must be additionally
  44    protected with dev->queue_lock spinlock.
  45
  46    The idea is the following:
  47    - enqueue, dequeue are serialized via top level device
  48      spinlock dev->queue_lock.
  49    - tree walking is protected by read_lock_bh(qdisc_tree_lock)
  50      and this lock is used only in process context.
  51    - updates to tree are made under rtnl semaphore or
  52      from softirq context (__qdisc_destroy rcu-callback)
  53      hence this lock needs local bh disabling.
  54
  55    qdisc_tree_lock must be grabbed BEFORE dev->queue_lock!
  56  */
  57 DEFINE_RWLOCK(qdisc_tree_lock);
  58
  59 void qdisc_lock_tree(struct net_device *dev)
  60 {
  61         write_lock_bh(&qdisc_tree_lock);
  62         spin_lock_bh(&dev->queue_lock);
  63 }
  64
  65 void qdisc_unlock_tree(struct net_device *dev)
  66 {
  67         spin_unlock_bh(&dev->queue_lock);
  68         write_unlock_bh(&qdisc_tree_lock);
  69 }
  70
  71 /*
  72    dev->queue_lock serializes queue accesses for this device
  73    AND dev->qdisc pointer itself.
  74
  75    dev->xmit_lock serializes accesses to device driver.
  76
  77    dev->queue_lock and dev->xmit_lock are mutually exclusive,
  78    if one is grabbed, another must be free.
  79  */
  80
  81
  82 /* Kick device.
  83    Note, that this procedure can be called by a watchdog timer, so that
  84    we do not check dev->tbusy flag here.
  85
  86    Returns:  0  - queue is empty.
  87             >0  - queue is not empty, but throttled.
  88             <0  - queue is not empty. Device is throttled, if dev->tbusy != 0.
  89
  90    NOTE: Called under dev->queue_lock with locally disabled BH.
  91 */
  92
  93 int qdisc_restart(struct net_device *dev)
  94 {
  95         struct Qdisc *q = dev->qdisc;
  96         struct sk_buff *skb;
  97
  98         /* Dequeue packet */
  99         if ((skb = q->dequeue(q)) != NULL) {
 100                 unsigned nolock = (dev->features & NETIF_F_LLTX);
 101                 /*
 102                  * When the driver has LLTX set it does its own locking
 103                  * in start_xmit. No need to add additional overhead by
 104                  * locking again. These checks are worth it because
 105                  * even uncongested locks can be quite expensive.
 106                  * The driver can do trylock like here too, in case
 107                  * of lock congestion it should return -1 and the packet
 108                  * will be requeued.
 109                  */
 110                 if (!nolock) {
 111                         if (!spin_trylock(&dev->xmit_lock)) {
 112                         collision:
 113                                 /* So, someone grabbed the driver. */
 114
 115                                 /* It may be transient configuration error,
 116                                    when hard_start_xmit() recurses. We detect
 117                                    it by checking xmit owner and drop the
 118                                    packet when deadloop is detected.
 119                                 */
 120                                 if (dev->xmit_lock_owner == smp_processor_id()) {
 121                                         kfree_skb(skb);
 122                                         if (net_ratelimit())
 123                                                 printk(KERN_DEBUG "Dead loop on netdevice %s, fix it urgently!\n", dev->name);
 124                                         return -1;
 125                                 }
 126                                 __get_cpu_var(netdev_rx_stat).cpu_collision++;
 127                                 goto requeue;
 128                         }
 129                         /* Remember that the driver is grabbed by us. */
 130                         dev->xmit_lock_owner = smp_processor_id();
 131                 }
 132
 133                 {
 134                         /* And release queue */
 135                         spin_unlock(&dev->queue_lock);
 136
 137                         if (!netif_queue_stopped(dev)) {
 138                                 int ret;
 139                                 if (netdev_nit)
 140                                         dev_queue_xmit_nit(skb, dev);
 141
 142                                 ret = dev->hard_start_xmit(skb, dev);
 143                                 if (ret == NETDEV_TX_OK) {
 144                                         if (!nolock) {
 145                                                 dev->xmit_lock_owner = -1;
 146                                                 spin_unlock(&dev->xmit_lock);
 147                                         }
 148                                         spin_lock(&dev->queue_lock);
 149                                         return -1;
 150                                 }
 151                                 if (ret == NETDEV_TX_LOCKED && nolock) {
 152                                         spin_lock(&dev->queue_lock);
 153                                         goto collision;
 154                                 }
 155                         }
 156
 157                         /* NETDEV_TX_BUSY - we need to requeue */
 158                         /* Release the driver */
 159                         if (!nolock) {
 160                                 dev->xmit_lock_owner = -1;
 161                                 spin_unlock(&dev->xmit_lock);
 162                         }
 163                         spin_lock(&dev->queue_lock);
 164                         q = dev->qdisc;
 165                 }
 166
 167                 /* Device kicked us out :(
 168                    This is possible in three cases:
 169
 170                    0. driver is locked
 171                    1. fastroute is enabled
 172                    2. device cannot determine busy state
 173                       before start of transmission (f.e. dialout)
 174                    3. device is buggy (ppp)
 175                  */
 176
 177 requeue:
 178                 q->ops->requeue(skb, q);
 179                 netif_schedule(dev);
 180                 return 1;
 181         }
 182         BUG_ON((int) q->q.qlen < 0);
 183         return q->q.qlen;
 184 }
 185
 186 static void dev_watchdog(unsigned long arg)
 187 {
 188         struct net_device *dev = (struct net_device *)arg;
 189
 190         spin_lock(&dev->xmit_lock);
 191         if (dev->qdisc != &noop_qdisc) {
 192                 if (netif_device_present(dev) &&
 193                     netif_running(dev) &&
 194                     netif_carrier_ok(dev)) {
 195                         if (netif_queue_stopped(dev) &&
 196                             (jiffies - dev->trans_start) > dev->watchdog_timeo) {
 197                                 printk(KERN_INFO "NETDEV WATCHDOG: %s: transmit timed out\n", dev->name);
 198                                 dev->tx_timeout(dev);
 199                         }
 200                         if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
 201                                 dev_hold(dev);
 202                 }
 203         }
 204         spin_unlock(&dev->xmit_lock);
 205
 206         dev_put(dev);
 207 }
 208
 209 static void dev_watchdog_init(struct net_device *dev)
 210 {
 211         init_timer(&dev->watchdog_timer);
 212         dev->watchdog_timer.data = (unsigned long)dev;
 213         dev->watchdog_timer.function = dev_watchdog;
 214 }
 215
 216 void __netdev_watchdog_up(struct net_device *dev)
 217 {
 218         if (dev->tx_timeout) {
 219                 if (dev->watchdog_timeo <= 0)
 220                         dev->watchdog_timeo = 5*HZ;
 221                 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
 222                         dev_hold(dev);
 223         }
 224 }
 225
 226 static void dev_watchdog_up(struct net_device *dev)
 227 {
 228         spin_lock_bh(&dev->xmit_lock);
 229         __netdev_watchdog_up(dev);
 230         spin_unlock_bh(&dev->xmit_lock);
 231 }
 232
 233 static void dev_watchdog_down(struct net_device *dev)
 234 {
 235         spin_lock_bh(&dev->xmit_lock);
 236         if (del_timer(&dev->watchdog_timer))
 237                 __dev_put(dev);
 238         spin_unlock_bh(&dev->xmit_lock);
 239 }
 240
 241 void netif_carrier_on(struct net_device *dev)
 242 {
 243         if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state))
 244                 linkwatch_fire_event(dev);
 245         if (netif_running(dev))
 246                 __netdev_watchdog_up(dev);
 247 }
 248
 249 void netif_carrier_off(struct net_device *dev)
 250 {
 251         if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state))
 252                 linkwatch_fire_event(dev);
 253 }
 254
 255 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces
 256    under all circumstances. It is difficult to invent anything faster or
 257    cheaper.
 258  */
 259
 260 static int noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc)
 261 {
 262         kfree_skb(skb);
 263         return NET_XMIT_CN;
 264 }
 265
 266 static struct sk_buff *noop_dequeue(struct Qdisc * qdisc)
 267 {
 268         return NULL;
 269 }
 270
 271 static int noop_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
 272 {
 273         if (net_ratelimit())
 274                 printk(KERN_DEBUG "%s deferred output. It is buggy.\n",
 275                        skb->dev->name);
 276         kfree_skb(skb);
 277         return NET_XMIT_CN;
 278 }
 279
 280 struct Qdisc_ops noop_qdisc_ops = {
 281         .id             =       "noop",
 282         .priv_size      =       0,
 283         .enqueue        =       noop_enqueue,
 284         .dequeue        =       noop_dequeue,
 285         .requeue        =       noop_requeue,
 286         .owner          =       THIS_MODULE,
 287 };
 288
 289 struct Qdisc noop_qdisc = {
 290         .enqueue        =       noop_enqueue,
 291         .dequeue        =       noop_dequeue,
 292         .flags          =       TCQ_F_BUILTIN,
 293         .ops            =       &noop_qdisc_ops,
 294         .list           =       LIST_HEAD_INIT(noop_qdisc.list),
 295 };
 296
 297 static struct Qdisc_ops noqueue_qdisc_ops = {
 298         .id             =       "noqueue",
 299         .priv_size      =       0,
 300         .enqueue        =       noop_enqueue,
 301         .dequeue        =       noop_dequeue,
 302         .requeue        =       noop_requeue,
 303         .owner          =       THIS_MODULE,
 304 };
 305
 306 static struct Qdisc noqueue_qdisc = {
 307         .enqueue        =       NULL,
 308         .dequeue        =       noop_dequeue,
 309         .flags          =       TCQ_F_BUILTIN,
 310         .ops            =       &noqueue_qdisc_ops,
 311         .list           =       LIST_HEAD_INIT(noqueue_qdisc.list),
 312 };
 313
 314
 315 static const u8 prio2band[TC_PRIO_MAX+1] =
 316         { 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 };
 317
 318 /* 3-band FIFO queue: old style, but should be a bit faster than
 319    generic prio+fifo combination.
 320  */
 321
 322 #define PFIFO_FAST_BANDS 3
 323
 324 static inline struct sk_buff_head *prio2list(struct sk_buff *skb,
 325                                              struct Qdisc *qdisc)
 326 {
 327         struct sk_buff_head *list = qdisc_priv(qdisc);
 328         return list + prio2band[skb->priority & TC_PRIO_MAX];
 329 }
 330
 331 static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc)
 332 {
 333         struct sk_buff_head *list = prio2list(skb, qdisc);
 334
 335         if (skb_queue_len(list) < qdisc->dev->tx_queue_len) {
 336                 qdisc->q.qlen++;
 337                 return __qdisc_enqueue_tail(skb, qdisc, list);
 338         }
 339
 340         return qdisc_drop(skb, qdisc);
 341 }
 342
 343 static struct sk_buff *pfifo_fast_dequeue(struct Qdisc* qdisc)
 344 {
 345         int prio;
 346         struct sk_buff_head *list = qdisc_priv(qdisc);
 347
 348         for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) {
 349                 if (!skb_queue_empty(list + prio)) {
 350                         qdisc->q.qlen--;
 351                         return __qdisc_dequeue_head(qdisc, list + prio);
 352                 }
 353         }
 354
 355         return NULL;
 356 }
 357
 358 static int pfifo_fast_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
 359 {
 360         qdisc->q.qlen++;
 361         return __qdisc_requeue(skb, qdisc, prio2list(skb, qdisc));
 362 }
 363
 364 static void pfifo_fast_reset(struct Qdisc* qdisc)
 365 {
 366         int prio;
 367         struct sk_buff_head *list = qdisc_priv(qdisc);
 368
 369         for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
 370                 __qdisc_reset_queue(qdisc, list + prio);
 371
 372         qdisc->qstats.backlog = 0;
 373         qdisc->q.qlen = 0;
 374 }
 375
 376 static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
 377 {
 378         struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS };
 379
 380         memcpy(&opt.priomap, prio2band, TC_PRIO_MAX+1);
 381         RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 382         return skb->len;
 383
 384 rtattr_failure:
 385         return -1;
 386 }
 387
 388 static int pfifo_fast_init(struct Qdisc *qdisc, struct rtattr *opt)
 389 {
 390         int prio;
 391         struct sk_buff_head *list = qdisc_priv(qdisc);
 392
 393         for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
 394                 skb_queue_head_init(list + prio);
 395
 396         return 0;
 397 }
 398
 399 static struct Qdisc_ops pfifo_fast_ops = {
 400         .id             =       "pfifo_fast",
 401         .priv_size      =       PFIFO_FAST_BANDS * sizeof(struct sk_buff_head),
 402         .enqueue        =       pfifo_fast_enqueue,
 403         .dequeue        =       pfifo_fast_dequeue,
 404         .requeue        =       pfifo_fast_requeue,
 405         .init           =       pfifo_fast_init,
 406         .reset          =       pfifo_fast_reset,
 407         .dump           =       pfifo_fast_dump,
 408         .owner          =       THIS_MODULE,
 409 };
 410
 411 struct Qdisc *qdisc_alloc(struct net_device *dev, struct Qdisc_ops *ops)
 412 {
 413         void *p;
 414         struct Qdisc *sch;
 415         unsigned int size;
 416         int err = -ENOBUFS;
 417
 418         /* ensure that the Qdisc and the private data are 32-byte aligned */
 419         size = QDISC_ALIGN(sizeof(*sch));
 420         size += ops->priv_size + (QDISC_ALIGNTO - 1);
 421
 422         p = kmalloc(size, GFP_KERNEL);
 423         if (!p)
 424                 goto errout;
 425         memset(p, 0, size);
 426         sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
 427         sch->padded = (char *) sch - (char *) p;
 428
 429         INIT_LIST_HEAD(&sch->list);
 430         skb_queue_head_init(&sch->q);
 431         sch->ops = ops;
 432         sch->enqueue = ops->enqueue;
 433         sch->dequeue = ops->dequeue;
 434         sch->dev = dev;
 435         dev_hold(dev);
 436         sch->stats_lock = &dev->queue_lock;
 437         atomic_set(&sch->refcnt, 1);
 438
 439         return sch;
 440 errout:
 441         return ERR_PTR(-err);
 442 }
 443
 444 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops)
 445 {
 446         struct Qdisc *sch;
 447
 448         sch = qdisc_alloc(dev, ops);
 449         if (IS_ERR(sch))
 450                 goto errout;
 451
 452         if (!ops->init || ops->init(sch, NULL) == 0)
 453                 return sch;
 454
 455         qdisc_destroy(sch);
 456 errout:
 457         return NULL;
 458 }
 459
 460 /* Under dev->queue_lock and BH! */
 461
 462 void qdisc_reset(struct Qdisc *qdisc)
 463 {
 464         struct Qdisc_ops *ops = qdisc->ops;
 465
 466         if (ops->reset)
 467                 ops->reset(qdisc);
 468 }
 469
 470 /* this is the rcu callback function to clean up a qdisc when there
 471  * are no further references to it */
 472
 473 static void __qdisc_destroy(struct rcu_head *head)
 474 {
 475         struct Qdisc *qdisc = container_of(head, struct Qdisc, q_rcu);
 476         struct Qdisc_ops  *ops = qdisc->ops;
 477
 478 #ifdef CONFIG_NET_ESTIMATOR
 479         gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est);
 480 #endif
 481         write_lock(&qdisc_tree_lock);
 482         if (ops->reset)
 483                 ops->reset(qdisc);
 484         if (ops->destroy)
 485                 ops->destroy(qdisc);
 486         write_unlock(&qdisc_tree_lock);
 487         module_put(ops->owner);
 488
 489         dev_put(qdisc->dev);
 490         kfree((char *) qdisc - qdisc->padded);
 491 }
 492
 493 /* Under dev->queue_lock and BH! */
 494
 495 void qdisc_destroy(struct Qdisc *qdisc)
 496 {
 497         struct list_head cql = LIST_HEAD_INIT(cql);
 498         struct Qdisc *cq, *q, *n;
 499
 500         if (qdisc->flags & TCQ_F_BUILTIN ||
 501                 !atomic_dec_and_test(&qdisc->refcnt))
 502                 return;
 503
 504         if (!list_empty(&qdisc->list)) {
 505                 if (qdisc->ops->cl_ops == NULL)
 506                         list_del(&qdisc->list);
 507                 else
 508                         list_move(&qdisc->list, &cql);
 509         }
 510
 511         /* unlink inner qdiscs from dev->qdisc_list immediately */
 512         list_for_each_entry(cq, &cql, list)
 513                 list_for_each_entry_safe(q, n, &qdisc->dev->qdisc_list, list)
 514                         if (TC_H_MAJ(q->parent) == TC_H_MAJ(cq->handle)) {
 515                                 if (q->ops->cl_ops == NULL)
 516                                         list_del_init(&q->list);
 517                                 else
 518                                         list_move_tail(&q->list, &cql);
 519                         }
 520         list_for_each_entry_safe(cq, n, &cql, list)
 521                 list_del_init(&cq->list);
 522
 523         call_rcu(&qdisc->q_rcu, __qdisc_destroy);
 524 }
 525
 526 void dev_activate(struct net_device *dev)
 527 {
 528         /* No queueing discipline is attached to device;
 529            create default one i.e. pfifo_fast for devices,
 530            which need queueing and noqueue_qdisc for
 531            virtual interfaces
 532          */
 533
 534         if (dev->qdisc_sleeping == &noop_qdisc) {
 535                 struct Qdisc *qdisc;
 536                 if (dev->tx_queue_len) {
 537                         qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops);
 538                         if (qdisc == NULL) {
 539                                 printk(KERN_INFO "%s: activation failed\n", dev->name);
 540                                 return;
 541                         }
 542                         write_lock_bh(&qdisc_tree_lock);
 543                         list_add_tail(&qdisc->list, &dev->qdisc_list);
 544                         write_unlock_bh(&qdisc_tree_lock);
 545                 } else {
 546                         qdisc =  &noqueue_qdisc;
 547                 }
 548                 write_lock_bh(&qdisc_tree_lock);
 549                 dev->qdisc_sleeping = qdisc;
 550                 write_unlock_bh(&qdisc_tree_lock);
 551         }
 552
 553         if (!netif_carrier_ok(dev))
 554                 /* Delay activation until next carrier-on event */
 555                 return;
 556
 557         spin_lock_bh(&dev->queue_lock);
 558         rcu_assign_pointer(dev->qdisc, dev->qdisc_sleeping);
 559         if (dev->qdisc != &noqueue_qdisc) {
 560                 dev->trans_start = jiffies;
 561                 dev_watchdog_up(dev);
 562         }
 563         spin_unlock_bh(&dev->queue_lock);
 564 }
 565
 566 void dev_deactivate(struct net_device *dev)
 567 {
 568         struct Qdisc *qdisc;
 569
 570         spin_lock_bh(&dev->queue_lock);
 571         qdisc = dev->qdisc;
 572         dev->qdisc = &noop_qdisc;
 573
 574         qdisc_reset(qdisc);
 575
 576         spin_unlock_bh(&dev->queue_lock);
 577
 578         dev_watchdog_down(dev);
 579
 580         while (test_bit(__LINK_STATE_SCHED, &dev->state))
 581                 yield();
 582
 583         spin_unlock_wait(&dev->xmit_lock);
 584 }
 585
 586 void dev_init_scheduler(struct net_device *dev)
 587 {
 588         qdisc_lock_tree(dev);
 589         dev->qdisc = &noop_qdisc;
 590         dev->qdisc_sleeping = &noop_qdisc;
 591         INIT_LIST_HEAD(&dev->qdisc_list);
 592         qdisc_unlock_tree(dev);
 593
 594         dev_watchdog_init(dev);
 595 }
 596
 597 void dev_shutdown(struct net_device *dev)
 598 {
 599         struct Qdisc *qdisc;
 600
 601         qdisc_lock_tree(dev);
 602         qdisc = dev->qdisc_sleeping;
 603         dev->qdisc = &noop_qdisc;
 604         dev->qdisc_sleeping = &noop_qdisc;
 605         qdisc_destroy(qdisc);
 606 #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE)
 607         if ((qdisc = dev->qdisc_ingress) != NULL) {
 608                 dev->qdisc_ingress = NULL;
 609                 qdisc_destroy(qdisc);
 610         }
 611 #endif
 612         BUG_TRAP(!timer_pending(&dev->watchdog_timer));
 613         qdisc_unlock_tree(dev);
 614 }
 615
 616 EXPORT_SYMBOL(__netdev_watchdog_up);
 617 EXPORT_SYMBOL(netif_carrier_on);
 618 EXPORT_SYMBOL(netif_carrier_off);
 619 EXPORT_SYMBOL(noop_qdisc);
 620 EXPORT_SYMBOL(noop_qdisc_ops);
 621 EXPORT_SYMBOL(qdisc_create_dflt);
 622 EXPORT_SYMBOL(qdisc_alloc);
 623 EXPORT_SYMBOL(qdisc_destroy);
 624 EXPORT_SYMBOL(qdisc_reset);
 625 EXPORT_SYMBOL(qdisc_restart);
 626 EXPORT_SYMBOL(qdisc_lock_tree);
 627 EXPORT_SYMBOL(qdisc_unlock_tree);