Linux v2.6.17-rc2
[linux-2.6/next.git] / net / sched / sch_generic.c
blob31eb83717c267a799b013f073cfe3e99301709d9
1 /*
2 * net/sched/sch_generic.c Generic packet scheduler routines.
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.
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10 * Jamal Hadi Salim, <hadi@cyberus.ca> 990601
11 * - Ingress support
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>
38 /* Main transmission queue. */
40 /* Main qdisc structure lock.
42 However, modifications
43 to data, participating in scheduling must be additionally
44 protected with dev->queue_lock spinlock.
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.
55 qdisc_tree_lock must be grabbed BEFORE dev->queue_lock!
57 DEFINE_RWLOCK(qdisc_tree_lock);
59 void qdisc_lock_tree(struct net_device *dev)
61 write_lock_bh(&qdisc_tree_lock);
62 spin_lock_bh(&dev->queue_lock);
65 void qdisc_unlock_tree(struct net_device *dev)
67 spin_unlock_bh(&dev->queue_lock);
68 write_unlock_bh(&qdisc_tree_lock);
71 /*
72 dev->queue_lock serializes queue accesses for this device
73 AND dev->qdisc pointer itself.
75 dev->xmit_lock serializes accesses to device driver.
77 dev->queue_lock and dev->xmit_lock are mutually exclusive,
78 if one is grabbed, another must be free.
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.
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.
90 NOTE: Called under dev->queue_lock with locally disabled BH.
93 int qdisc_restart(struct net_device *dev)
95 struct Qdisc *q = dev->qdisc;
96 struct sk_buff *skb;
98 /* Dequeue packet */
99 if ((skb = q->dequeue(q)) != NULL) {
100 unsigned nolock = (dev->features & NETIF_F_LLTX);
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.
110 if (!nolock) {
111 if (!spin_trylock(&dev->xmit_lock)) {
112 collision:
113 /* So, someone grabbed the driver. */
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.
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;
126 __get_cpu_var(netdev_rx_stat).cpu_collision++;
127 goto requeue;
129 /* Remember that the driver is grabbed by us. */
130 dev->xmit_lock_owner = smp_processor_id();
134 /* And release queue */
135 spin_unlock(&dev->queue_lock);
137 if (!netif_queue_stopped(dev)) {
138 int ret;
139 if (netdev_nit)
140 dev_queue_xmit_nit(skb, dev);
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);
148 spin_lock(&dev->queue_lock);
149 return -1;
151 if (ret == NETDEV_TX_LOCKED && nolock) {
152 spin_lock(&dev->queue_lock);
153 goto collision;
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);
163 spin_lock(&dev->queue_lock);
164 q = dev->qdisc;
167 /* Device kicked us out :(
168 This is possible in three cases:
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)
177 requeue:
178 q->ops->requeue(skb, q);
179 netif_schedule(dev);
180 return 1;
182 BUG_ON((int) q->q.qlen < 0);
183 return q->q.qlen;
186 static void dev_watchdog(unsigned long arg)
188 struct net_device *dev = (struct net_device *)arg;
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);
200 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
201 dev_hold(dev);
204 spin_unlock(&dev->xmit_lock);
206 dev_put(dev);
209 static void dev_watchdog_init(struct net_device *dev)
211 init_timer(&dev->watchdog_timer);
212 dev->watchdog_timer.data = (unsigned long)dev;
213 dev->watchdog_timer.function = dev_watchdog;
216 void __netdev_watchdog_up(struct net_device *dev)
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);
226 static void dev_watchdog_up(struct net_device *dev)
228 spin_lock_bh(&dev->xmit_lock);
229 __netdev_watchdog_up(dev);
230 spin_unlock_bh(&dev->xmit_lock);
233 static void dev_watchdog_down(struct net_device *dev)
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);
241 void netif_carrier_on(struct net_device *dev)
243 if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state))
244 linkwatch_fire_event(dev);
245 if (netif_running(dev))
246 __netdev_watchdog_up(dev);
249 void netif_carrier_off(struct net_device *dev)
251 if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state))
252 linkwatch_fire_event(dev);
255 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces
256 under all circumstances. It is difficult to invent anything faster or
257 cheaper.
260 static int noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc)
262 kfree_skb(skb);
263 return NET_XMIT_CN;
266 static struct sk_buff *noop_dequeue(struct Qdisc * qdisc)
268 return NULL;
271 static int noop_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
273 if (net_ratelimit())
274 printk(KERN_DEBUG "%s deferred output. It is buggy.\n",
275 skb->dev->name);
276 kfree_skb(skb);
277 return NET_XMIT_CN;
280 struct Qdisc_ops noop_qdisc_ops = {
281 .id = "noop",
282 .priv_size = 0,
283 .enqueue = noop_enqueue,
284 .dequeue = noop_dequeue,
285 .requeue = noop_requeue,
286 .owner = THIS_MODULE,
289 struct Qdisc noop_qdisc = {
290 .enqueue = noop_enqueue,
291 .dequeue = noop_dequeue,
292 .flags = TCQ_F_BUILTIN,
293 .ops = &noop_qdisc_ops,
294 .list = LIST_HEAD_INIT(noop_qdisc.list),
297 static struct Qdisc_ops noqueue_qdisc_ops = {
298 .id = "noqueue",
299 .priv_size = 0,
300 .enqueue = noop_enqueue,
301 .dequeue = noop_dequeue,
302 .requeue = noop_requeue,
303 .owner = THIS_MODULE,
306 static struct Qdisc noqueue_qdisc = {
307 .enqueue = NULL,
308 .dequeue = noop_dequeue,
309 .flags = TCQ_F_BUILTIN,
310 .ops = &noqueue_qdisc_ops,
311 .list = LIST_HEAD_INIT(noqueue_qdisc.list),
315 static const u8 prio2band[TC_PRIO_MAX+1] =
316 { 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 };
318 /* 3-band FIFO queue: old style, but should be a bit faster than
319 generic prio+fifo combination.
322 #define PFIFO_FAST_BANDS 3
324 static inline struct sk_buff_head *prio2list(struct sk_buff *skb,
325 struct Qdisc *qdisc)
327 struct sk_buff_head *list = qdisc_priv(qdisc);
328 return list + prio2band[skb->priority & TC_PRIO_MAX];
331 static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc)
333 struct sk_buff_head *list = prio2list(skb, qdisc);
335 if (skb_queue_len(list) < qdisc->dev->tx_queue_len) {
336 qdisc->q.qlen++;
337 return __qdisc_enqueue_tail(skb, qdisc, list);
340 return qdisc_drop(skb, qdisc);
343 static struct sk_buff *pfifo_fast_dequeue(struct Qdisc* qdisc)
345 int prio;
346 struct sk_buff_head *list = qdisc_priv(qdisc);
348 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) {
349 if (!skb_queue_empty(list + prio)) {
350 qdisc->q.qlen--;
351 return __qdisc_dequeue_head(qdisc, list + prio);
355 return NULL;
358 static int pfifo_fast_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
360 qdisc->q.qlen++;
361 return __qdisc_requeue(skb, qdisc, prio2list(skb, qdisc));
364 static void pfifo_fast_reset(struct Qdisc* qdisc)
366 int prio;
367 struct sk_buff_head *list = qdisc_priv(qdisc);
369 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
370 __qdisc_reset_queue(qdisc, list + prio);
372 qdisc->qstats.backlog = 0;
373 qdisc->q.qlen = 0;
376 static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
378 struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS };
380 memcpy(&opt.priomap, prio2band, TC_PRIO_MAX+1);
381 RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
382 return skb->len;
384 rtattr_failure:
385 return -1;
388 static int pfifo_fast_init(struct Qdisc *qdisc, struct rtattr *opt)
390 int prio;
391 struct sk_buff_head *list = qdisc_priv(qdisc);
393 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
394 skb_queue_head_init(list + prio);
396 return 0;
399 static struct Qdisc_ops pfifo_fast_ops = {
400 .id = "pfifo_fast",
401 .priv_size = PFIFO_FAST_BANDS * sizeof(struct sk_buff_head),
402 .enqueue = pfifo_fast_enqueue,
403 .dequeue = pfifo_fast_dequeue,
404 .requeue = pfifo_fast_requeue,
405 .init = pfifo_fast_init,
406 .reset = pfifo_fast_reset,
407 .dump = pfifo_fast_dump,
408 .owner = THIS_MODULE,
411 struct Qdisc *qdisc_alloc(struct net_device *dev, struct Qdisc_ops *ops)
413 void *p;
414 struct Qdisc *sch;
415 unsigned int size;
416 int err = -ENOBUFS;
418 /* ensure that the Qdisc and the private data are 32-byte aligned */
419 size = QDISC_ALIGN(sizeof(*sch));
420 size += ops->priv_size + (QDISC_ALIGNTO - 1);
422 p = kmalloc(size, GFP_KERNEL);
423 if (!p)
424 goto errout;
425 memset(p, 0, size);
426 sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
427 sch->padded = (char *) sch - (char *) p;
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);
439 return sch;
440 errout:
441 return ERR_PTR(-err);
444 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops)
446 struct Qdisc *sch;
448 sch = qdisc_alloc(dev, ops);
449 if (IS_ERR(sch))
450 goto errout;
452 if (!ops->init || ops->init(sch, NULL) == 0)
453 return sch;
455 qdisc_destroy(sch);
456 errout:
457 return NULL;
460 /* Under dev->queue_lock and BH! */
462 void qdisc_reset(struct Qdisc *qdisc)
464 struct Qdisc_ops *ops = qdisc->ops;
466 if (ops->reset)
467 ops->reset(qdisc);
470 /* this is the rcu callback function to clean up a qdisc when there
471 * are no further references to it */
473 static void __qdisc_destroy(struct rcu_head *head)
475 struct Qdisc *qdisc = container_of(head, struct Qdisc, q_rcu);
476 struct Qdisc_ops *ops = qdisc->ops;
478 #ifdef CONFIG_NET_ESTIMATOR
479 gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est);
480 #endif
481 write_lock(&qdisc_tree_lock);
482 if (ops->reset)
483 ops->reset(qdisc);
484 if (ops->destroy)
485 ops->destroy(qdisc);
486 write_unlock(&qdisc_tree_lock);
487 module_put(ops->owner);
489 dev_put(qdisc->dev);
490 kfree((char *) qdisc - qdisc->padded);
493 /* Under dev->queue_lock and BH! */
495 void qdisc_destroy(struct Qdisc *qdisc)
497 struct list_head cql = LIST_HEAD_INIT(cql);
498 struct Qdisc *cq, *q, *n;
500 if (qdisc->flags & TCQ_F_BUILTIN ||
501 !atomic_dec_and_test(&qdisc->refcnt))
502 return;
504 if (!list_empty(&qdisc->list)) {
505 if (qdisc->ops->cl_ops == NULL)
506 list_del(&qdisc->list);
507 else
508 list_move(&qdisc->list, &cql);
511 /* unlink inner qdiscs from dev->qdisc_list immediately */
512 list_for_each_entry(cq, &cql, list)
513 list_for_each_entry_safe(q, n, &qdisc->dev->qdisc_list, list)
514 if (TC_H_MAJ(q->parent) == TC_H_MAJ(cq->handle)) {
515 if (q->ops->cl_ops == NULL)
516 list_del_init(&q->list);
517 else
518 list_move_tail(&q->list, &cql);
520 list_for_each_entry_safe(cq, n, &cql, list)
521 list_del_init(&cq->list);
523 call_rcu(&qdisc->q_rcu, __qdisc_destroy);
526 void dev_activate(struct net_device *dev)
528 /* No queueing discipline is attached to device;
529 create default one i.e. pfifo_fast for devices,
530 which need queueing and noqueue_qdisc for
531 virtual interfaces
534 if (dev->qdisc_sleeping == &noop_qdisc) {
535 struct Qdisc *qdisc;
536 if (dev->tx_queue_len) {
537 qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops);
538 if (qdisc == NULL) {
539 printk(KERN_INFO "%s: activation failed\n", dev->name);
540 return;
542 write_lock_bh(&qdisc_tree_lock);
543 list_add_tail(&qdisc->list, &dev->qdisc_list);
544 write_unlock_bh(&qdisc_tree_lock);
545 } else {
546 qdisc = &noqueue_qdisc;
548 write_lock_bh(&qdisc_tree_lock);
549 dev->qdisc_sleeping = qdisc;
550 write_unlock_bh(&qdisc_tree_lock);
553 if (!netif_carrier_ok(dev))
554 /* Delay activation until next carrier-on event */
555 return;
557 spin_lock_bh(&dev->queue_lock);
558 rcu_assign_pointer(dev->qdisc, dev->qdisc_sleeping);
559 if (dev->qdisc != &noqueue_qdisc) {
560 dev->trans_start = jiffies;
561 dev_watchdog_up(dev);
563 spin_unlock_bh(&dev->queue_lock);
566 void dev_deactivate(struct net_device *dev)
568 struct Qdisc *qdisc;
570 spin_lock_bh(&dev->queue_lock);
571 qdisc = dev->qdisc;
572 dev->qdisc = &noop_qdisc;
574 qdisc_reset(qdisc);
576 spin_unlock_bh(&dev->queue_lock);
578 dev_watchdog_down(dev);
580 while (test_bit(__LINK_STATE_SCHED, &dev->state))
581 yield();
583 spin_unlock_wait(&dev->xmit_lock);
586 void dev_init_scheduler(struct net_device *dev)
588 qdisc_lock_tree(dev);
589 dev->qdisc = &noop_qdisc;
590 dev->qdisc_sleeping = &noop_qdisc;
591 INIT_LIST_HEAD(&dev->qdisc_list);
592 qdisc_unlock_tree(dev);
594 dev_watchdog_init(dev);
597 void dev_shutdown(struct net_device *dev)
599 struct Qdisc *qdisc;
601 qdisc_lock_tree(dev);
602 qdisc = dev->qdisc_sleeping;
603 dev->qdisc = &noop_qdisc;
604 dev->qdisc_sleeping = &noop_qdisc;
605 qdisc_destroy(qdisc);
606 #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE)
607 if ((qdisc = dev->qdisc_ingress) != NULL) {
608 dev->qdisc_ingress = NULL;
609 qdisc_destroy(qdisc);
611 #endif
612 BUG_TRAP(!timer_pending(&dev->watchdog_timer));
613 qdisc_unlock_tree(dev);
616 EXPORT_SYMBOL(__netdev_watchdog_up);
617 EXPORT_SYMBOL(netif_carrier_on);
618 EXPORT_SYMBOL(netif_carrier_off);
619 EXPORT_SYMBOL(noop_qdisc);
620 EXPORT_SYMBOL(noop_qdisc_ops);
621 EXPORT_SYMBOL(qdisc_create_dflt);
622 EXPORT_SYMBOL(qdisc_alloc);
623 EXPORT_SYMBOL(qdisc_destroy);
624 EXPORT_SYMBOL(qdisc_reset);
625 EXPORT_SYMBOL(qdisc_restart);
626 EXPORT_SYMBOL(qdisc_lock_tree);
627 EXPORT_SYMBOL(qdisc_unlock_tree);