/* * net/sched/sch_generic.c Generic packet scheduler routines. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version * 2 of the License, or (at your option) any later version. * * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> * Jamal Hadi Salim, <hadi@nortelnetworks.com> 990601 * - Ingress support */ #include <asm/uaccess.h> #include <asm/system.h> #include <asm/bitops.h> #include <linux/config.h> #include <linux/types.h> #include <linux/kernel.h> #include <linux/sched.h> #include <linux/string.h> #include <linux/mm.h> #include <linux/socket.h> #include <linux/sockios.h> #include <linux/in.h> #include <linux/errno.h> #include <linux/interrupt.h> #include <linux/netdevice.h> #include <linux/skbuff.h> #include <linux/rtnetlink.h> #include <linux/init.h> #include <net/sock.h> #include <net/pkt_sched.h> /* Main transmission queue. */ /* Main qdisc structure lock. However, modifications to data, participating in scheduling must be additionally protected with dev->queue_lock spinlock. The idea is the following: - enqueue, dequeue are serialized via top level device spinlock dev->queue_lock. - tree walking is protected by read_lock(qdisc_tree_lock) and this lock is used only in process context. - updates to tree are made only under rtnl semaphore, hence this lock may be made without local bh disabling. qdisc_tree_lock must be grabbed BEFORE dev->queue_lock! */ rwlock_t qdisc_tree_lock = RW_LOCK_UNLOCKED; /* dev->queue_lock serializes queue accesses for this device AND dev->qdisc pointer itself. dev->xmit_lock serializes accesses to device driver. dev->queue_lock and dev->xmit_lock are mutually exclusive, if one is grabbed, another must be free. */ /* Kick device. Note, that this procedure can be called by a watchdog timer, so that we do not check dev->tbusy flag here. Returns: 0 - queue is empty. >0 - queue is not empty, but throttled. <0 - queue is not empty. Device is throttled, if dev->tbusy != 0. NOTE: Called under dev->queue_lock with locally disabled BH. */ 77 int qdisc_restart(struct net_device *dev) { struct Qdisc *q = dev->qdisc; struct sk_buff *skb; /* Dequeue packet */ 83 if ((skb = q->dequeue(q)) != NULL) { 84 if (spin_trylock(&dev->xmit_lock)) { /* Remember that the driver is grabbed by us. */ dev->xmit_lock_owner = smp_processor_id(); /* And release queue */ 89 spin_unlock(&dev->queue_lock); 91 if (!netif_queue_stopped(dev)) { 92 if (netdev_nit) dev_queue_xmit_nit(skb, dev); 95 if (dev->hard_start_xmit(skb, dev) == 0) { dev->xmit_lock_owner = -1; 97 spin_unlock(&dev->xmit_lock); spin_lock(&dev->queue_lock); 100 return -1; } } /* Release the driver */ dev->xmit_lock_owner = -1; 106 spin_unlock(&dev->xmit_lock); spin_lock(&dev->queue_lock); q = dev->qdisc; 109 } else { /* So, someone grabbed the driver. */ /* It may be transient configuration error, when hard_start_xmit() recurses. We detect it by checking xmit owner and drop the packet when deadloop is detected. */ 117 if (dev->xmit_lock_owner == smp_processor_id()) { kfree_skb(skb); 119 if (net_ratelimit()) printk(KERN_DEBUG "Dead loop on netdevice %s, fix it urgently!\n", dev->name); 121 return -1; } netdev_rx_stat[smp_processor_id()].cpu_collision++; } /* Device kicked us out :( This is possible in three cases: 0. driver is locked 1. fastroute is enabled 2. device cannot determine busy state before start of transmission (f.e. dialout) 3. device is buggy (ppp) */ q->ops->requeue(skb, q); netif_schedule(dev); 138 return 1; } 140 return q->q.qlen; } 143 static void dev_watchdog(unsigned long arg) { struct net_device *dev = (struct net_device *)arg; spin_lock(&dev->xmit_lock); 148 if (dev->qdisc != &noop_qdisc) { if (netif_device_present(dev) && netif_running(dev) && 151 netif_carrier_ok(dev)) { if (netif_queue_stopped(dev) && 153 (jiffies - dev->trans_start) > dev->watchdog_timeo) { printk(KERN_INFO "NETDEV WATCHDOG: %s: transmit timed out\n", dev->name); dev->tx_timeout(dev); } 157 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo)) dev_hold(dev); } } 161 spin_unlock(&dev->xmit_lock); dev_put(dev); } 166 static void dev_watchdog_init(struct net_device *dev) { init_timer(&dev->watchdog_timer); dev->watchdog_timer.data = (unsigned long)dev; dev->watchdog_timer.function = dev_watchdog; } 173 void __netdev_watchdog_up(struct net_device *dev) { 175 if (dev->tx_timeout) { 176 if (dev->watchdog_timeo <= 0) dev->watchdog_timeo = 5*HZ; 178 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo)) dev_hold(dev); } } 183 static void dev_watchdog_up(struct net_device *dev) { 185 spin_lock_bh(&dev->xmit_lock); __netdev_watchdog_up(dev); 187 spin_unlock_bh(&dev->xmit_lock); } 190 static void dev_watchdog_down(struct net_device *dev) { 192 spin_lock_bh(&dev->xmit_lock); 193 if (del_timer(&dev->watchdog_timer)) __dev_put(dev); 195 spin_unlock_bh(&dev->xmit_lock); } /* "NOOP" scheduler: the best scheduler, recommended for all interfaces under all circumstances. It is difficult to invent anything faster or cheaper. */ static int 204 noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc) { kfree_skb(skb); 207 return NET_XMIT_CN; } static struct sk_buff * 211 noop_dequeue(struct Qdisc * qdisc) { 213 return NULL; } static int 217 noop_requeue(struct sk_buff *skb, struct Qdisc* qdisc) { 219 if (net_ratelimit()) printk(KERN_DEBUG "%s deferred output. It is buggy.\n", skb->dev->name); kfree_skb(skb); 222 return NET_XMIT_CN; } struct Qdisc_ops noop_qdisc_ops = { NULL, NULL, "noop", 0, noop_enqueue, noop_dequeue, noop_requeue, }; struct Qdisc noop_qdisc = { noop_enqueue, noop_dequeue, TCQ_F_BUILTIN, &noop_qdisc_ops, }; struct Qdisc_ops noqueue_qdisc_ops = { NULL, NULL, "noqueue", 0, noop_enqueue, noop_dequeue, noop_requeue, }; struct Qdisc noqueue_qdisc = { NULL, noop_dequeue, TCQ_F_BUILTIN, &noqueue_qdisc_ops, }; static const u8 prio2band[TC_PRIO_MAX+1] = { 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 }; /* 3-band FIFO queue: old style, but should be a bit faster than generic prio+fifo combination. */ static int 276 pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc) { struct sk_buff_head *list; list = ((struct sk_buff_head*)qdisc->data) + prio2band[skb->priority&TC_PRIO_MAX]; 283 if (list->qlen <= skb->dev->tx_queue_len) { __skb_queue_tail(list, skb); qdisc->q.qlen++; 286 return 0; } qdisc->stats.drops++; kfree_skb(skb); 290 return NET_XMIT_DROP; } static struct sk_buff * 294 pfifo_fast_dequeue(struct Qdisc* qdisc) { int prio; struct sk_buff_head *list = ((struct sk_buff_head*)qdisc->data); struct sk_buff *skb; 300 for (prio = 0; prio < 3; prio++, list++) { skb = __skb_dequeue(list); 302 if (skb) { qdisc->q.qlen--; 304 return skb; } } 307 return NULL; } static int 311 pfifo_fast_requeue(struct sk_buff *skb, struct Qdisc* qdisc) { struct sk_buff_head *list; list = ((struct sk_buff_head*)qdisc->data) + prio2band[skb->priority&TC_PRIO_MAX]; __skb_queue_head(list, skb); qdisc->q.qlen++; 320 return 0; } static void 324 pfifo_fast_reset(struct Qdisc* qdisc) { int prio; struct sk_buff_head *list = ((struct sk_buff_head*)qdisc->data); 329 for (prio=0; prio < 3; prio++) skb_queue_purge(list+prio); qdisc->q.qlen = 0; } 334 static int pfifo_fast_init(struct Qdisc *qdisc, struct rtattr *opt) { int i; struct sk_buff_head *list; list = ((struct sk_buff_head*)qdisc->data); 341 for (i=0; i<3; i++) skb_queue_head_init(list+i); 344 return 0; } static struct Qdisc_ops pfifo_fast_ops = { NULL, NULL, "pfifo_fast", 3 * sizeof(struct sk_buff_head), pfifo_fast_enqueue, pfifo_fast_dequeue, pfifo_fast_requeue, NULL, pfifo_fast_init, pfifo_fast_reset, }; 363 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops) { struct Qdisc *sch; int size = sizeof(*sch) + ops->priv_size; sch = kmalloc(size, GFP_KERNEL); 369 if (!sch) 370 return NULL; memset(sch, 0, size); skb_queue_head_init(&sch->q); sch->ops = ops; sch->enqueue = ops->enqueue; sch->dequeue = ops->dequeue; sch->dev = dev; sch->stats.lock = &dev->queue_lock; atomic_set(&sch->refcnt, 1); 380 if (!ops->init || ops->init(sch, NULL) == 0) 381 return sch; kfree(sch); 384 return NULL; } /* Under dev->queue_lock and BH! */ 389 void qdisc_reset(struct Qdisc *qdisc) { struct Qdisc_ops *ops = qdisc->ops; 393 if (ops->reset) ops->reset(qdisc); } /* Under dev->queue_lock and BH! */ 399 void qdisc_destroy(struct Qdisc *qdisc) { struct Qdisc_ops *ops = qdisc->ops; struct net_device *dev; 404 if (!atomic_dec_and_test(&qdisc->refcnt)) 405 return; dev = qdisc->dev; #ifdef CONFIG_NET_SCHED if (dev) { struct Qdisc *q, **qp; for (qp = &qdisc->dev->qdisc_list; (q=*qp) != NULL; qp = &q->next) { if (q == qdisc) { *qp = q->next; break; } } } #ifdef CONFIG_NET_ESTIMATOR qdisc_kill_estimator(&qdisc->stats); #endif #endif 423 if (ops->reset) ops->reset(qdisc); 425 if (ops->destroy) ops->destroy(qdisc); 427 if (!(qdisc->flags&TCQ_F_BUILTIN)) kfree(qdisc); } 432 void dev_activate(struct net_device *dev) { /* No queueing discipline is attached to device; create default one i.e. pfifo_fast for devices, which need queueing and noqueue_qdisc for virtual interfaces */ 440 if (dev->qdisc_sleeping == &noop_qdisc) { struct Qdisc *qdisc; 442 if (dev->tx_queue_len) { qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops); 444 if (qdisc == NULL) { printk(KERN_INFO "%s: activation failed\n", dev->name); 446 return; } 448 } else { qdisc = &noqueue_qdisc; } write_lock(&qdisc_tree_lock); dev->qdisc_sleeping = qdisc; 453 write_unlock(&qdisc_tree_lock); } 456 spin_lock_bh(&dev->queue_lock); 457 if ((dev->qdisc = dev->qdisc_sleeping) != &noqueue_qdisc) { dev->trans_start = jiffies; dev_watchdog_up(dev); } 461 spin_unlock_bh(&dev->queue_lock); } 464 void dev_deactivate(struct net_device *dev) { struct Qdisc *qdisc; 468 spin_lock_bh(&dev->queue_lock); qdisc = dev->qdisc; dev->qdisc = &noop_qdisc; qdisc_reset(qdisc); 474 spin_unlock_bh(&dev->queue_lock); dev_watchdog_down(dev); 478 while (test_bit(__LINK_STATE_SCHED, &dev->state)) { current->policy |= SCHED_YIELD; schedule(); } 483 spin_unlock_wait(&dev->xmit_lock); } 486 void dev_init_scheduler(struct net_device *dev) { write_lock(&qdisc_tree_lock); 489 spin_lock_bh(&dev->queue_lock); dev->qdisc = &noop_qdisc; 491 spin_unlock_bh(&dev->queue_lock); dev->qdisc_sleeping = &noop_qdisc; dev->qdisc_list = NULL; 494 write_unlock(&qdisc_tree_lock); dev_watchdog_init(dev); } 499 void dev_shutdown(struct net_device *dev) { struct Qdisc *qdisc; write_lock(&qdisc_tree_lock); 504 spin_lock_bh(&dev->queue_lock); qdisc = dev->qdisc_sleeping; dev->qdisc = &noop_qdisc; dev->qdisc_sleeping = &noop_qdisc; qdisc_destroy(qdisc); #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE) if ((qdisc = dev->qdisc_ingress) != NULL) { dev->qdisc_ingress = NULL; qdisc_destroy(qdisc); } #endif 515 BUG_TRAP(dev->qdisc_list == NULL); 516 BUG_TRAP(!timer_pending(&dev->watchdog_timer)); dev->qdisc_list = NULL; 518 spin_unlock_bh(&dev->queue_lock); 519 write_unlock(&qdisc_tree_lock); }