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 <asm/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 rwlock_t qdisc_tree_lock = RW_LOCK_UNLOCKED;
  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         return q->q.qlen;
 183 }
 184
 185 static void dev_watchdog(unsigned long arg)
 186 {
 187         struct net_device *dev = (struct net_device *)arg;
 188
 189         spin_lock(&dev->xmit_lock);
 190         if (dev->qdisc != &noop_qdisc) {
 191                 if (netif_device_present(dev) &&
 192                     netif_running(dev) &&
 193                     netif_carrier_ok(dev)) {
 194                         if (netif_queue_stopped(dev) &&
 195                             (jiffies - dev->trans_start) > dev->watchdog_timeo) {
 196                                 printk(KERN_INFO "NETDEV WATCHDOG: %s: transmit timed out\n", dev->name);
 197                                 dev->tx_timeout(dev);
 198                         }
 199                         if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
 200                                 dev_hold(dev);
 201                 }
 202         }
 203         spin_unlock(&dev->xmit_lock);
 204
 205         dev_put(dev);
 206 }
 207
 208 static void dev_watchdog_init(struct net_device *dev)
 209 {
 210         init_timer(&dev->watchdog_timer);
 211         dev->watchdog_timer.data = (unsigned long)dev;
 212         dev->watchdog_timer.function = dev_watchdog;
 213 }
 214
 215 void __netdev_watchdog_up(struct net_device *dev)
 216 {
 217         if (dev->tx_timeout) {
 218                 if (dev->watchdog_timeo <= 0)
 219                         dev->watchdog_timeo = 5*HZ;
 220                 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
 221                         dev_hold(dev);
 222         }
 223 }
 224
 225 static void dev_watchdog_up(struct net_device *dev)
 226 {
 227         spin_lock_bh(&dev->xmit_lock);
 228         __netdev_watchdog_up(dev);
 229         spin_unlock_bh(&dev->xmit_lock);
 230 }
 231
 232 static void dev_watchdog_down(struct net_device *dev)
 233 {
 234         spin_lock_bh(&dev->xmit_lock);
 235         if (del_timer(&dev->watchdog_timer))
 236                 __dev_put(dev);
 237         spin_unlock_bh(&dev->xmit_lock);
 238 }
 239
 240 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces
 241    under all circumstances. It is difficult to invent anything faster or
 242    cheaper.
 243  */
 244
 245 static int
 246 noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc)
 247 {
 248         kfree_skb(skb);
 249         return NET_XMIT_CN;
 250 }
 251
 252 static struct sk_buff *
 253 noop_dequeue(struct Qdisc * qdisc)
 254 {
 255         return NULL;
 256 }
 257
 258 static int
 259 noop_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
 260 {
 261         if (net_ratelimit())
 262                 printk(KERN_DEBUG "%s deferred output. It is buggy.\n", skb->dev->name);
 263         kfree_skb(skb);
 264         return NET_XMIT_CN;
 265 }
 266
 267 struct Qdisc_ops noop_qdisc_ops = {
 268         .next           =       NULL,
 269         .cl_ops         =       NULL,
 270         .id             =       "noop",
 271         .priv_size      =       0,
 272         .enqueue        =       noop_enqueue,
 273         .dequeue        =       noop_dequeue,
 274         .requeue        =       noop_requeue,
 275         .owner          =       THIS_MODULE,
 276 };
 277
 278 struct Qdisc noop_qdisc = {
 279         .enqueue        =       noop_enqueue,
 280         .dequeue        =       noop_dequeue,
 281         .flags          =       TCQ_F_BUILTIN,
 282         .ops            =       &noop_qdisc_ops,
 283 };
 284
 285 struct Qdisc_ops noqueue_qdisc_ops = {
 286         .next           =       NULL,
 287         .cl_ops         =       NULL,
 288         .id             =       "noqueue",
 289         .priv_size      =       0,
 290         .enqueue        =       noop_enqueue,
 291         .dequeue        =       noop_dequeue,
 292         .requeue        =       noop_requeue,
 293         .owner          =       THIS_MODULE,
 294 };
 295
 296 struct Qdisc noqueue_qdisc = {
 297         .enqueue        =       NULL,
 298         .dequeue        =       noop_dequeue,
 299         .flags          =       TCQ_F_BUILTIN,
 300         .ops            =       &noqueue_qdisc_ops,
 301 };
 302
 303
 304 static const u8 prio2band[TC_PRIO_MAX+1] =
 305         { 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 };
 306
 307 /* 3-band FIFO queue: old style, but should be a bit faster than
 308    generic prio+fifo combination.
 309  */
 310
 311 static int
 312 pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc)
 313 {
 314         struct sk_buff_head *list = qdisc_priv(qdisc);
 315
 316         list += prio2band[skb->priority&TC_PRIO_MAX];
 317
 318         if (list->qlen < qdisc->dev->tx_queue_len) {
 319                 __skb_queue_tail(list, skb);
 320                 qdisc->q.qlen++;
 321                 qdisc->stats.bytes += skb->len;
 322                 qdisc->stats.packets++;
 323                 return 0;
 324         }
 325         qdisc->stats.drops++;
 326         kfree_skb(skb);
 327         return NET_XMIT_DROP;
 328 }
 329
 330 static struct sk_buff *
 331 pfifo_fast_dequeue(struct Qdisc* qdisc)
 332 {
 333         int prio;
 334         struct sk_buff_head *list = qdisc_priv(qdisc);
 335         struct sk_buff *skb;
 336
 337         for (prio = 0; prio < 3; prio++, list++) {
 338                 skb = __skb_dequeue(list);
 339                 if (skb) {
 340                         qdisc->q.qlen--;
 341                         return skb;
 342                 }
 343         }
 344         return NULL;
 345 }
 346
 347 static int
 348 pfifo_fast_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
 349 {
 350         struct sk_buff_head *list = qdisc_priv(qdisc);
 351
 352         list += prio2band[skb->priority&TC_PRIO_MAX];
 353
 354         __skb_queue_head(list, skb);
 355         qdisc->q.qlen++;
 356         return 0;
 357 }
 358
 359 static void
 360 pfifo_fast_reset(struct Qdisc* qdisc)
 361 {
 362         int prio;
 363         struct sk_buff_head *list = qdisc_priv(qdisc);
 364
 365         for (prio=0; prio < 3; prio++)
 366                 skb_queue_purge(list+prio);
 367         qdisc->q.qlen = 0;
 368 }
 369
 370 static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
 371 {
 372         unsigned char    *b = skb->tail;
 373         struct tc_prio_qopt opt;
 374
 375         opt.bands = 3;
 376         memcpy(&opt.priomap, prio2band, TC_PRIO_MAX+1);
 377         RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 378         return skb->len;
 379
 380 rtattr_failure:
 381         skb_trim(skb, b - skb->data);
 382         return -1;
 383 }
 384
 385 static int pfifo_fast_init(struct Qdisc *qdisc, struct rtattr *opt)
 386 {
 387         int i;
 388         struct sk_buff_head *list = qdisc_priv(qdisc);
 389
 390         for (i=0; i<3; i++)
 391                 skb_queue_head_init(list+i);
 392
 393         return 0;
 394 }
 395
 396 static struct Qdisc_ops pfifo_fast_ops = {
 397         .next           =       NULL,
 398         .cl_ops         =       NULL,
 399         .id             =       "pfifo_fast",
 400         .priv_size      =       3 * sizeof(struct sk_buff_head),
 401         .enqueue        =       pfifo_fast_enqueue,
 402         .dequeue        =       pfifo_fast_dequeue,
 403         .requeue        =       pfifo_fast_requeue,
 404         .init           =       pfifo_fast_init,
 405         .reset          =       pfifo_fast_reset,
 406         .dump           =       pfifo_fast_dump,
 407         .owner          =       THIS_MODULE,
 408 };
 409
 410 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops)
 411 {
 412         void *p;
 413         struct Qdisc *sch;
 414         int size;
 415
 416         /* ensure that the Qdisc and the private data are 32-byte aligned */
 417         size = ((sizeof(*sch) + QDISC_ALIGN_CONST) & ~QDISC_ALIGN_CONST);
 418         size += ops->priv_size + QDISC_ALIGN_CONST;
 419
 420         p = kmalloc(size, GFP_KERNEL);
 421         if (!p)
 422                 return NULL;
 423         memset(p, 0, size);
 424
 425         sch = (struct Qdisc *)(((unsigned long)p + QDISC_ALIGN_CONST)
 426                                & ~QDISC_ALIGN_CONST);
 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         /* enqueue is accessed locklessly - make sure it's visible
 439          * before we set a netdevice's qdisc pointer to sch */
 440         smp_wmb();
 441         if (!ops->init || ops->init(sch, NULL) == 0)
 442                 return sch;
 443
 444         dev_put(dev);
 445         kfree(p);
 446         return NULL;
 447 }
 448
 449 /* Under dev->queue_lock and BH! */
 450
 451 void qdisc_reset(struct Qdisc *qdisc)
 452 {
 453         struct Qdisc_ops *ops = qdisc->ops;
 454
 455         if (ops->reset)
 456                 ops->reset(qdisc);
 457 }
 458
 459 /* this is the rcu callback function to clean up a qdisc when there
 460  * are no further references to it */
 461
 462 static void __qdisc_destroy(struct rcu_head *head)
 463 {
 464         struct Qdisc *qdisc = container_of(head, struct Qdisc, q_rcu);
 465         struct Qdisc_ops  *ops = qdisc->ops;
 466
 467 #ifdef CONFIG_NET_ESTIMATOR
 468         qdisc_kill_estimator(&qdisc->stats);
 469 #endif
 470         write_lock(&qdisc_tree_lock);
 471         if (ops->reset)
 472                 ops->reset(qdisc);
 473         if (ops->destroy)
 474                 ops->destroy(qdisc);
 475         write_unlock(&qdisc_tree_lock);
 476         module_put(ops->owner);
 477
 478         dev_put(qdisc->dev);
 479         if (!(qdisc->flags&TCQ_F_BUILTIN))
 480                 kfree((char *) qdisc - qdisc->padded);
 481 }
 482
 483 /* Under dev->queue_lock and BH! */
 484
 485 void qdisc_destroy(struct Qdisc *qdisc)
 486 {
 487         if (!atomic_dec_and_test(&qdisc->refcnt))
 488                 return;
 489         list_del(&qdisc->list);
 490         call_rcu(&qdisc->q_rcu, __qdisc_destroy);
 491 }
 492
 493 void dev_activate(struct net_device *dev)
 494 {
 495         /* No queueing discipline is attached to device;
 496            create default one i.e. pfifo_fast for devices,
 497            which need queueing and noqueue_qdisc for
 498            virtual interfaces
 499          */
 500
 501         if (dev->qdisc_sleeping == &noop_qdisc) {
 502                 struct Qdisc *qdisc;
 503                 if (dev->tx_queue_len) {
 504                         qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops);
 505                         if (qdisc == NULL) {
 506                                 printk(KERN_INFO "%s: activation failed\n", dev->name);
 507                                 return;
 508                         }
 509                         write_lock_bh(&qdisc_tree_lock);
 510                         list_add_tail(&qdisc->list, &dev->qdisc_list);
 511                         write_unlock_bh(&qdisc_tree_lock);
 512                 } else {
 513                         qdisc =  &noqueue_qdisc;
 514                 }
 515                 write_lock_bh(&qdisc_tree_lock);
 516                 dev->qdisc_sleeping = qdisc;
 517                 write_unlock_bh(&qdisc_tree_lock);
 518         }
 519
 520         spin_lock_bh(&dev->queue_lock);
 521         if ((dev->qdisc = dev->qdisc_sleeping) != &noqueue_qdisc) {
 522                 dev->trans_start = jiffies;
 523                 dev_watchdog_up(dev);
 524         }
 525         spin_unlock_bh(&dev->queue_lock);
 526 }
 527
 528 void dev_deactivate(struct net_device *dev)
 529 {
 530         struct Qdisc *qdisc;
 531
 532         spin_lock_bh(&dev->queue_lock);
 533         qdisc = dev->qdisc;
 534         dev->qdisc = &noop_qdisc;
 535
 536         qdisc_reset(qdisc);
 537
 538         spin_unlock_bh(&dev->queue_lock);
 539
 540         dev_watchdog_down(dev);
 541
 542         while (test_bit(__LINK_STATE_SCHED, &dev->state))
 543                 yield();
 544
 545         spin_unlock_wait(&dev->xmit_lock);
 546 }
 547
 548 void dev_init_scheduler(struct net_device *dev)
 549 {
 550         qdisc_lock_tree(dev);
 551         dev->qdisc = &noop_qdisc;
 552         dev->qdisc_sleeping = &noop_qdisc;
 553         INIT_LIST_HEAD(&dev->qdisc_list);
 554         qdisc_unlock_tree(dev);
 555
 556         dev_watchdog_init(dev);
 557 }
 558
 559 void dev_shutdown(struct net_device *dev)
 560 {
 561         struct Qdisc *qdisc;
 562
 563         qdisc_lock_tree(dev);
 564         qdisc = dev->qdisc_sleeping;
 565         dev->qdisc = &noop_qdisc;
 566         dev->qdisc_sleeping = &noop_qdisc;
 567         qdisc_destroy(qdisc);
 568 #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE)
 569         if ((qdisc = dev->qdisc_ingress) != NULL) {
 570                 dev->qdisc_ingress = NULL;
 571                 qdisc_destroy(qdisc);
 572         }
 573 #endif
 574         BUG_TRAP(!timer_pending(&dev->watchdog_timer));
 575         qdisc_unlock_tree(dev);
 576 }
 577
 578 EXPORT_SYMBOL(__netdev_watchdog_up);
 579 EXPORT_SYMBOL(noop_qdisc);
 580 EXPORT_SYMBOL(noop_qdisc_ops);
 581 EXPORT_SYMBOL(qdisc_create_dflt);
 582 EXPORT_SYMBOL(qdisc_destroy);
 583 EXPORT_SYMBOL(qdisc_reset);
 584 EXPORT_SYMBOL(qdisc_restart);
 585 EXPORT_SYMBOL(qdisc_lock_tree);
 586 EXPORT_SYMBOL(qdisc_unlock_tree);