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 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces
 242    under all circumstances. It is difficult to invent anything faster or
 243    cheaper.
 244  */
 245
 246 static int
 247 noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc)
 248 {
 249         kfree_skb(skb);
 250         return NET_XMIT_CN;
 251 }
 252
 253 static struct sk_buff *
 254 noop_dequeue(struct Qdisc * qdisc)
 255 {
 256         return NULL;
 257 }
 258
 259 static int
 260 noop_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
 261 {
 262         if (net_ratelimit())
 263                 printk(KERN_DEBUG "%s deferred output. It is buggy.\n", skb->dev->name);
 264         kfree_skb(skb);
 265         return NET_XMIT_CN;
 266 }
 267
 268 struct Qdisc_ops noop_qdisc_ops = {
 269         .next           =       NULL,
 270         .cl_ops         =       NULL,
 271         .id             =       "noop",
 272         .priv_size      =       0,
 273         .enqueue        =       noop_enqueue,
 274         .dequeue        =       noop_dequeue,
 275         .requeue        =       noop_requeue,
 276         .owner          =       THIS_MODULE,
 277 };
 278
 279 struct Qdisc noop_qdisc = {
 280         .enqueue        =       noop_enqueue,
 281         .dequeue        =       noop_dequeue,
 282         .flags          =       TCQ_F_BUILTIN,
 283         .ops            =       &noop_qdisc_ops,
 284         .list           =       LIST_HEAD_INIT(noop_qdisc.list),
 285 };
 286
 287 static struct Qdisc_ops noqueue_qdisc_ops = {
 288         .next           =       NULL,
 289         .cl_ops         =       NULL,
 290         .id             =       "noqueue",
 291         .priv_size      =       0,
 292         .enqueue        =       noop_enqueue,
 293         .dequeue        =       noop_dequeue,
 294         .requeue        =       noop_requeue,
 295         .owner          =       THIS_MODULE,
 296 };
 297
 298 static struct Qdisc noqueue_qdisc = {
 299         .enqueue        =       NULL,
 300         .dequeue        =       noop_dequeue,
 301         .flags          =       TCQ_F_BUILTIN,
 302         .ops            =       &noqueue_qdisc_ops,
 303         .list           =       LIST_HEAD_INIT(noqueue_qdisc.list),
 304 };
 305
 306
 307 static const u8 prio2band[TC_PRIO_MAX+1] =
 308         { 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 };
 309
 310 /* 3-band FIFO queue: old style, but should be a bit faster than
 311    generic prio+fifo combination.
 312  */
 313
 314 static int
 315 pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc)
 316 {
 317         struct sk_buff_head *list = qdisc_priv(qdisc);
 318
 319         list += prio2band[skb->priority&TC_PRIO_MAX];
 320
 321         if (list->qlen < qdisc->dev->tx_queue_len) {
 322                 __skb_queue_tail(list, skb);
 323                 qdisc->q.qlen++;
 324                 qdisc->bstats.bytes += skb->len;
 325                 qdisc->bstats.packets++;
 326                 return 0;
 327         }
 328         qdisc->qstats.drops++;
 329         kfree_skb(skb);
 330         return NET_XMIT_DROP;
 331 }
 332
 333 static struct sk_buff *
 334 pfifo_fast_dequeue(struct Qdisc* qdisc)
 335 {
 336         int prio;
 337         struct sk_buff_head *list = qdisc_priv(qdisc);
 338         struct sk_buff *skb;
 339
 340         for (prio = 0; prio < 3; prio++, list++) {
 341                 skb = __skb_dequeue(list);
 342                 if (skb) {
 343                         qdisc->q.qlen--;
 344                         return skb;
 345                 }
 346         }
 347         return NULL;
 348 }
 349
 350 static int
 351 pfifo_fast_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
 352 {
 353         struct sk_buff_head *list = qdisc_priv(qdisc);
 354
 355         list += prio2band[skb->priority&TC_PRIO_MAX];
 356
 357         __skb_queue_head(list, skb);
 358         qdisc->q.qlen++;
 359         qdisc->qstats.requeues++;
 360         return 0;
 361 }
 362
 363 static void
 364 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 < 3; prio++)
 370                 skb_queue_purge(list+prio);
 371         qdisc->q.qlen = 0;
 372 }
 373
 374 static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
 375 {
 376         unsigned char    *b = skb->tail;
 377         struct tc_prio_qopt opt;
 378
 379         opt.bands = 3;
 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         skb_trim(skb, b - skb->data);
 386         return -1;
 387 }
 388
 389 static int pfifo_fast_init(struct Qdisc *qdisc, struct rtattr *opt)
 390 {
 391         int i;
 392         struct sk_buff_head *list = qdisc_priv(qdisc);
 393
 394         for (i=0; i<3; i++)
 395                 skb_queue_head_init(list+i);
 396
 397         return 0;
 398 }
 399
 400 static struct Qdisc_ops pfifo_fast_ops = {
 401         .next           =       NULL,
 402         .cl_ops         =       NULL,
 403         .id             =       "pfifo_fast",
 404         .priv_size      =       3 * sizeof(struct sk_buff_head),
 405         .enqueue        =       pfifo_fast_enqueue,
 406         .dequeue        =       pfifo_fast_dequeue,
 407         .requeue        =       pfifo_fast_requeue,
 408         .init           =       pfifo_fast_init,
 409         .reset          =       pfifo_fast_reset,
 410         .dump           =       pfifo_fast_dump,
 411         .owner          =       THIS_MODULE,
 412 };
 413
 414 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops)
 415 {
 416         void *p;
 417         struct Qdisc *sch;
 418         int size;
 419
 420         /* ensure that the Qdisc and the private data are 32-byte aligned */
 421         size = ((sizeof(*sch) + QDISC_ALIGN_CONST) & ~QDISC_ALIGN_CONST);
 422         size += ops->priv_size + QDISC_ALIGN_CONST;
 423
 424         p = kmalloc(size, GFP_KERNEL);
 425         if (!p)
 426                 return NULL;
 427         memset(p, 0, size);
 428
 429         sch = (struct Qdisc *)(((unsigned long)p + QDISC_ALIGN_CONST)
 430                                & ~QDISC_ALIGN_CONST);
 431         sch->padded = (char *)sch - (char *)p;
 432
 433         INIT_LIST_HEAD(&sch->list);
 434         skb_queue_head_init(&sch->q);
 435         sch->ops = ops;
 436         sch->enqueue = ops->enqueue;
 437         sch->dequeue = ops->dequeue;
 438         sch->dev = dev;
 439         dev_hold(dev);
 440         sch->stats_lock = &dev->queue_lock;
 441         atomic_set(&sch->refcnt, 1);
 442         if (!ops->init || ops->init(sch, NULL) == 0)
 443                 return sch;
 444
 445         dev_put(dev);
 446         kfree(p);
 447         return NULL;
 448 }
 449
 450 /* Under dev->queue_lock and BH! */
 451
 452 void qdisc_reset(struct Qdisc *qdisc)
 453 {
 454         struct Qdisc_ops *ops = qdisc->ops;
 455
 456         if (ops->reset)
 457                 ops->reset(qdisc);
 458 }
 459
 460 /* this is the rcu callback function to clean up a qdisc when there
 461  * are no further references to it */
 462
 463 static void __qdisc_destroy(struct rcu_head *head)
 464 {
 465         struct Qdisc *qdisc = container_of(head, struct Qdisc, q_rcu);
 466         struct Qdisc_ops  *ops = qdisc->ops;
 467
 468 #ifdef CONFIG_NET_ESTIMATOR
 469         gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est);
 470 #endif
 471         write_lock(&qdisc_tree_lock);
 472         if (ops->reset)
 473                 ops->reset(qdisc);
 474         if (ops->destroy)
 475                 ops->destroy(qdisc);
 476         write_unlock(&qdisc_tree_lock);
 477         module_put(ops->owner);
 478
 479         dev_put(qdisc->dev);
 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         struct list_head cql = LIST_HEAD_INIT(cql);
 488         struct Qdisc *cq, *q, *n;
 489
 490         if (qdisc->flags & TCQ_F_BUILTIN ||
 491                 !atomic_dec_and_test(&qdisc->refcnt))
 492                 return;
 493
 494         if (!list_empty(&qdisc->list)) {
 495                 if (qdisc->ops->cl_ops == NULL)
 496                         list_del(&qdisc->list);
 497                 else
 498                         list_move(&qdisc->list, &cql);
 499         }
 500
 501         /* unlink inner qdiscs from dev->qdisc_list immediately */
 502         list_for_each_entry(cq, &cql, list)
 503                 list_for_each_entry_safe(q, n, &qdisc->dev->qdisc_list, list)
 504                         if (TC_H_MAJ(q->parent) == TC_H_MAJ(cq->handle)) {
 505                                 if (q->ops->cl_ops == NULL)
 506                                         list_del_init(&q->list);
 507                                 else
 508                                         list_move_tail(&q->list, &cql);
 509                         }
 510         list_for_each_entry_safe(cq, n, &cql, list)
 511                 list_del_init(&cq->list);
 512
 513         call_rcu(&qdisc->q_rcu, __qdisc_destroy);
 514 }
 515
 516 void dev_activate(struct net_device *dev)
 517 {
 518         /* No queueing discipline is attached to device;
 519            create default one i.e. pfifo_fast for devices,
 520            which need queueing and noqueue_qdisc for
 521            virtual interfaces
 522          */
 523
 524         if (dev->qdisc_sleeping == &noop_qdisc) {
 525                 struct Qdisc *qdisc;
 526                 if (dev->tx_queue_len) {
 527                         qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops);
 528                         if (qdisc == NULL) {
 529                                 printk(KERN_INFO "%s: activation failed\n", dev->name);
 530                                 return;
 531                         }
 532                         write_lock_bh(&qdisc_tree_lock);
 533                         list_add_tail(&qdisc->list, &dev->qdisc_list);
 534                         write_unlock_bh(&qdisc_tree_lock);
 535                 } else {
 536                         qdisc =  &noqueue_qdisc;
 537                 }
 538                 write_lock_bh(&qdisc_tree_lock);
 539                 dev->qdisc_sleeping = qdisc;
 540                 write_unlock_bh(&qdisc_tree_lock);
 541         }
 542
 543         if (!netif_carrier_ok(dev))
 544                 /* Delay activation until next carrier-on event */
 545                 return;
 546
 547         spin_lock_bh(&dev->queue_lock);
 548         rcu_assign_pointer(dev->qdisc, dev->qdisc_sleeping);
 549         if (dev->qdisc != &noqueue_qdisc) {
 550                 dev->trans_start = jiffies;
 551                 dev_watchdog_up(dev);
 552         }
 553         spin_unlock_bh(&dev->queue_lock);
 554 }
 555
 556 void dev_deactivate(struct net_device *dev)
 557 {
 558         struct Qdisc *qdisc;
 559
 560         spin_lock_bh(&dev->queue_lock);
 561         qdisc = dev->qdisc;
 562         dev->qdisc = &noop_qdisc;
 563
 564         qdisc_reset(qdisc);
 565
 566         spin_unlock_bh(&dev->queue_lock);
 567
 568         dev_watchdog_down(dev);
 569
 570         while (test_bit(__LINK_STATE_SCHED, &dev->state))
 571                 yield();
 572
 573         spin_unlock_wait(&dev->xmit_lock);
 574 }
 575
 576 void dev_init_scheduler(struct net_device *dev)
 577 {
 578         qdisc_lock_tree(dev);
 579         dev->qdisc = &noop_qdisc;
 580         dev->qdisc_sleeping = &noop_qdisc;
 581         INIT_LIST_HEAD(&dev->qdisc_list);
 582         qdisc_unlock_tree(dev);
 583
 584         dev_watchdog_init(dev);
 585 }
 586
 587 void dev_shutdown(struct net_device *dev)
 588 {
 589         struct Qdisc *qdisc;
 590
 591         qdisc_lock_tree(dev);
 592         qdisc = dev->qdisc_sleeping;
 593         dev->qdisc = &noop_qdisc;
 594         dev->qdisc_sleeping = &noop_qdisc;
 595         qdisc_destroy(qdisc);
 596 #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE)
 597         if ((qdisc = dev->qdisc_ingress) != NULL) {
 598                 dev->qdisc_ingress = NULL;
 599                 qdisc_destroy(qdisc);
 600         }
 601 #endif
 602         BUG_TRAP(!timer_pending(&dev->watchdog_timer));
 603         qdisc_unlock_tree(dev);
 604 }
 605
 606 EXPORT_SYMBOL(__netdev_watchdog_up);
 607 EXPORT_SYMBOL(noop_qdisc);
 608 EXPORT_SYMBOL(noop_qdisc_ops);
 609 EXPORT_SYMBOL(qdisc_create_dflt);
 610 EXPORT_SYMBOL(qdisc_destroy);
 611 EXPORT_SYMBOL(qdisc_reset);
 612 EXPORT_SYMBOL(qdisc_restart);
 613 EXPORT_SYMBOL(qdisc_lock_tree);
 614 EXPORT_SYMBOL(qdisc_unlock_tree);