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