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