SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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    netif_tx_lock serializes accesses to device driver.
  76
  77    dev->queue_lock and netif_tx_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 static inline 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 (!netif_tx_trylock(dev)) {
 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                 }
 130
 131                 {
 132                         /* And release queue */
 133                         spin_unlock(&dev->queue_lock);
 134
 135                         if (!netif_queue_stopped(dev)) {
 136                                 int ret;
 137                                 if (netdev_nit)
 138                                         dev_queue_xmit_nit(skb, dev);
 139
 140                                 ret = dev->hard_start_xmit(skb, dev);
 141                                 if (ret == NETDEV_TX_OK) {
 142                                         if (!nolock) {
 143                                                 netif_tx_unlock(dev);
 144                                         }
 145                                         spin_lock(&dev->queue_lock);
 146                                         return -1;
 147                                 }
 148                                 if (ret == NETDEV_TX_LOCKED && nolock) {
 149                                         spin_lock(&dev->queue_lock);
 150                                         goto collision;
 151                                 }
 152                         }
 153
 154                         /* NETDEV_TX_BUSY - we need to requeue */
 155                         /* Release the driver */
 156                         if (!nolock) {
 157                                 netif_tx_unlock(dev);
 158                         }
 159                         spin_lock(&dev->queue_lock);
 160                         q = dev->qdisc;
 161                 }
 162
 163                 /* Device kicked us out :(
 164                    This is possible in three cases:
 165
 166                    0. driver is locked
 167                    1. fastroute is enabled
 168                    2. device cannot determine busy state
 169                       before start of transmission (f.e. dialout)
 170                    3. device is buggy (ppp)
 171                  */
 172
 173 requeue:
 174                 q->ops->requeue(skb, q);
 175                 netif_schedule(dev);
 176                 return 1;
 177         }
 178         BUG_ON((int) q->q.qlen < 0);
 179         return q->q.qlen;
 180 }
 181
 182 void __qdisc_run(struct net_device *dev)
 183 {
 184         while (qdisc_restart(dev) < 0 && !netif_queue_stopped(dev))
 185                 /* NOTHING */;
 186
 187         clear_bit(__LINK_STATE_QDISC_RUNNING, &dev->state);
 188 }
 189
 190 static void dev_watchdog(unsigned long arg)
 191 {
 192         struct net_device *dev = (struct net_device *)arg;
 193
 194         netif_tx_lock(dev);
 195         if (dev->qdisc != &noop_qdisc) {
 196                 if (netif_device_present(dev) &&
 197                     netif_running(dev) &&
 198                     netif_carrier_ok(dev)) {
 199                         if (netif_queue_stopped(dev) &&
 200                             time_after(jiffies, dev->trans_start + dev->watchdog_timeo)) {
 201
 202                                 printk(KERN_INFO "NETDEV WATCHDOG: %s: transmit timed out\n",
 203                                        dev->name);
 204                                 dev->tx_timeout(dev);
 205                         }
 206                         if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
 207                                 dev_hold(dev);
 208                 }
 209         }
 210         netif_tx_unlock(dev);
 211
 212         dev_put(dev);
 213 }
 214
 215 static void dev_watchdog_init(struct net_device *dev)
 216 {
 217         init_timer(&dev->watchdog_timer);
 218         dev->watchdog_timer.data = (unsigned long)dev;
 219         dev->watchdog_timer.function = dev_watchdog;
 220 }
 221
 222 void __netdev_watchdog_up(struct net_device *dev)
 223 {
 224         if (dev->tx_timeout) {
 225                 if (dev->watchdog_timeo <= 0)
 226                         dev->watchdog_timeo = 5*HZ;
 227                 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
 228                         dev_hold(dev);
 229         }
 230 }
 231
 232 static void dev_watchdog_up(struct net_device *dev)
 233 {
 234         netif_tx_lock_bh(dev);
 235         __netdev_watchdog_up(dev);
 236         netif_tx_unlock_bh(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 = kmalloc(size, GFP_KERNEL);
 429         if (!p)
 430                 goto errout;
 431         memset(p, 0, size);
 432         sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
 433         sch->padded = (char *) sch - (char *) p;
 434
 435         INIT_LIST_HEAD(&sch->list);
 436         skb_queue_head_init(&sch->q);
 437         sch->ops = ops;
 438         sch->enqueue = ops->enqueue;
 439         sch->dequeue = ops->dequeue;
 440         sch->dev = dev;
 441         dev_hold(dev);
 442         sch->stats_lock = &dev->queue_lock;
 443         atomic_set(&sch->refcnt, 1);
 444
 445         return sch;
 446 errout:
 447         return ERR_PTR(-err);
 448 }
 449
 450 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops)
 451 {
 452         struct Qdisc *sch;
 453
 454         sch = qdisc_alloc(dev, ops);
 455         if (IS_ERR(sch))
 456                 goto errout;
 457
 458         if (!ops->init || ops->init(sch, NULL) == 0)
 459                 return sch;
 460
 461         qdisc_destroy(sch);
 462 errout:
 463         return NULL;
 464 }
 465
 466 /* Under dev->queue_lock and BH! */
 467
 468 void qdisc_reset(struct Qdisc *qdisc)
 469 {
 470         struct Qdisc_ops *ops = qdisc->ops;
 471
 472         if (ops->reset)
 473                 ops->reset(qdisc);
 474 }
 475
 476 /* this is the rcu callback function to clean up a qdisc when there
 477  * are no further references to it */
 478
 479 static void __qdisc_destroy(struct rcu_head *head)
 480 {
 481         struct Qdisc *qdisc = container_of(head, struct Qdisc, q_rcu);
 482         struct Qdisc_ops  *ops = qdisc->ops;
 483
 484 #ifdef CONFIG_NET_ESTIMATOR
 485         gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est);
 486 #endif
 487         write_lock(&qdisc_tree_lock);
 488         if (ops->reset)
 489                 ops->reset(qdisc);
 490         if (ops->destroy)
 491                 ops->destroy(qdisc);
 492         write_unlock(&qdisc_tree_lock);
 493         module_put(ops->owner);
 494
 495         dev_put(qdisc->dev);
 496         kfree((char *) qdisc - qdisc->padded);
 497 }
 498
 499 /* Under dev->queue_lock and BH! */
 500
 501 void qdisc_destroy(struct Qdisc *qdisc)
 502 {
 503         struct list_head cql = LIST_HEAD_INIT(cql);
 504         struct Qdisc *cq, *q, *n;
 505
 506         if (qdisc->flags & TCQ_F_BUILTIN ||
 507                 !atomic_dec_and_test(&qdisc->refcnt))
 508                 return;
 509
 510         if (!list_empty(&qdisc->list)) {
 511                 if (qdisc->ops->cl_ops == NULL)
 512                         list_del(&qdisc->list);
 513                 else
 514                         list_move(&qdisc->list, &cql);
 515         }
 516
 517         /* unlink inner qdiscs from dev->qdisc_list immediately */
 518         list_for_each_entry(cq, &cql, list)
 519                 list_for_each_entry_safe(q, n, &qdisc->dev->qdisc_list, list)
 520                         if (TC_H_MAJ(q->parent) == TC_H_MAJ(cq->handle)) {
 521                                 if (q->ops->cl_ops == NULL)
 522                                         list_del_init(&q->list);
 523                                 else
 524                                         list_move_tail(&q->list, &cql);
 525                         }
 526         list_for_each_entry_safe(cq, n, &cql, list)
 527                 list_del_init(&cq->list);
 528
 529         call_rcu(&qdisc->q_rcu, __qdisc_destroy);
 530 }
 531
 532 void dev_activate(struct net_device *dev)
 533 {
 534         /* No queueing discipline is attached to device;
 535            create default one i.e. pfifo_fast for devices,
 536            which need queueing and noqueue_qdisc for
 537            virtual interfaces
 538          */
 539
 540         if (dev->qdisc_sleeping == &noop_qdisc) {
 541                 struct Qdisc *qdisc;
 542                 if (dev->tx_queue_len) {
 543                         qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops);
 544                         if (qdisc == NULL) {
 545                                 printk(KERN_INFO "%s: activation failed\n", dev->name);
 546                                 return;
 547                         }
 548                         write_lock_bh(&qdisc_tree_lock);
 549                         list_add_tail(&qdisc->list, &dev->qdisc_list);
 550                         write_unlock_bh(&qdisc_tree_lock);
 551                 } else {
 552                         qdisc =  &noqueue_qdisc;
 553                 }
 554                 write_lock_bh(&qdisc_tree_lock);
 555                 dev->qdisc_sleeping = qdisc;
 556                 write_unlock_bh(&qdisc_tree_lock);
 557         }
 558
 559         if (!netif_carrier_ok(dev))
 560                 /* Delay activation until next carrier-on event */
 561                 return;
 562
 563         spin_lock_bh(&dev->queue_lock);
 564         rcu_assign_pointer(dev->qdisc, dev->qdisc_sleeping);
 565         if (dev->qdisc != &noqueue_qdisc) {
 566                 dev->trans_start = jiffies;
 567                 dev_watchdog_up(dev);
 568         }
 569         spin_unlock_bh(&dev->queue_lock);
 570 }
 571
 572 void dev_deactivate(struct net_device *dev)
 573 {
 574         struct Qdisc *qdisc;
 575
 576         spin_lock_bh(&dev->queue_lock);
 577         qdisc = dev->qdisc;
 578         dev->qdisc = &noop_qdisc;
 579
 580         qdisc_reset(qdisc);
 581
 582         spin_unlock_bh(&dev->queue_lock);
 583
 584         dev_watchdog_down(dev);
 585
 586         while (test_bit(__LINK_STATE_SCHED, &dev->state))
 587                 yield();
 588
 589         spin_unlock_wait(&dev->_xmit_lock);
 590 }
 591
 592 void dev_init_scheduler(struct net_device *dev)
 593 {
 594         qdisc_lock_tree(dev);
 595         dev->qdisc = &noop_qdisc;
 596         dev->qdisc_sleeping = &noop_qdisc;
 597         INIT_LIST_HEAD(&dev->qdisc_list);
 598         qdisc_unlock_tree(dev);
 599
 600         dev_watchdog_init(dev);
 601 }
 602
 603 void dev_shutdown(struct net_device *dev)
 604 {
 605         struct Qdisc *qdisc;
 606
 607         qdisc_lock_tree(dev);
 608         qdisc = dev->qdisc_sleeping;
 609         dev->qdisc = &noop_qdisc;
 610         dev->qdisc_sleeping = &noop_qdisc;
 611         qdisc_destroy(qdisc);
 612 #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE)
 613         if ((qdisc = dev->qdisc_ingress) != NULL) {
 614                 dev->qdisc_ingress = NULL;
 615                 qdisc_destroy(qdisc);
 616         }
 617 #endif
 618         BUG_TRAP(!timer_pending(&dev->watchdog_timer));
 619         qdisc_unlock_tree(dev);
 620 }
 621
 622 EXPORT_SYMBOL(__netdev_watchdog_up);
 623 EXPORT_SYMBOL(netif_carrier_on);
 624 EXPORT_SYMBOL(netif_carrier_off);
 625 EXPORT_SYMBOL(noop_qdisc);
 626 EXPORT_SYMBOL(noop_qdisc_ops);
 627 EXPORT_SYMBOL(qdisc_create_dflt);
 628 EXPORT_SYMBOL(qdisc_alloc);
 629 EXPORT_SYMBOL(qdisc_destroy);
 630 EXPORT_SYMBOL(qdisc_reset);
 631 EXPORT_SYMBOL(qdisc_lock_tree);
 632 EXPORT_SYMBOL(qdisc_unlock_tree);