[NET_SCHED]: Eliminate qdisc_tree_lock
[linux-2.6.git] / 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  * - updates to tree and tree walking are only done under the rtnl mutex.
46  */
47
48 void qdisc_lock_tree(struct net_device *dev)
49 {
50         spin_lock_bh(&dev->queue_lock);
51 }
52
53 void qdisc_unlock_tree(struct net_device *dev)
54 {
55         spin_unlock_bh(&dev->queue_lock);
56 }
57
58 /*
59    dev->queue_lock serializes queue accesses for this device
60    AND dev->qdisc pointer itself.
61
62    netif_tx_lock serializes accesses to device driver.
63
64    dev->queue_lock and netif_tx_lock are mutually exclusive,
65    if one is grabbed, another must be free.
66  */
67
68
69 /* Kick device.
70    Note, that this procedure can be called by a watchdog timer, so that
71    we do not check dev->tbusy flag here.
72
73    Returns:  0  - queue is empty.
74             >0  - queue is not empty, but throttled.
75             <0  - queue is not empty. Device is throttled, if dev->tbusy != 0.
76
77    NOTE: Called under dev->queue_lock with locally disabled BH.
78 */
79
80 static inline int qdisc_restart(struct net_device *dev)
81 {
82         struct Qdisc *q = dev->qdisc;
83         struct sk_buff *skb;
84
85         /* Dequeue packet */
86         if (((skb = dev->gso_skb)) || ((skb = q->dequeue(q)))) {
87                 unsigned nolock = (dev->features & NETIF_F_LLTX);
88
89                 dev->gso_skb = NULL;
90
91                 /*
92                  * When the driver has LLTX set it does its own locking
93                  * in start_xmit. No need to add additional overhead by
94                  * locking again. These checks are worth it because
95                  * even uncongested locks can be quite expensive.
96                  * The driver can do trylock like here too, in case
97                  * of lock congestion it should return -1 and the packet
98                  * will be requeued.
99                  */
100                 if (!nolock) {
101                         if (!netif_tx_trylock(dev)) {
102                         collision:
103                                 /* So, someone grabbed the driver. */
104
105                                 /* It may be transient configuration error,
106                                    when hard_start_xmit() recurses. We detect
107                                    it by checking xmit owner and drop the
108                                    packet when deadloop is detected.
109                                 */
110                                 if (dev->xmit_lock_owner == smp_processor_id()) {
111                                         kfree_skb(skb);
112                                         if (net_ratelimit())
113                                                 printk(KERN_DEBUG "Dead loop on netdevice %s, fix it urgently!\n", dev->name);
114                                         return -1;
115                                 }
116                                 __get_cpu_var(netdev_rx_stat).cpu_collision++;
117                                 goto requeue;
118                         }
119                 }
120
121                 {
122                         /* And release queue */
123                         spin_unlock(&dev->queue_lock);
124
125                         if (!netif_queue_stopped(dev)) {
126                                 int ret;
127
128                                 ret = dev_hard_start_xmit(skb, dev);
129                                 if (ret == NETDEV_TX_OK) {
130                                         if (!nolock) {
131                                                 netif_tx_unlock(dev);
132                                         }
133                                         spin_lock(&dev->queue_lock);
134                                         return -1;
135                                 }
136                                 if (ret == NETDEV_TX_LOCKED && nolock) {
137                                         spin_lock(&dev->queue_lock);
138                                         goto collision;
139                                 }
140                         }
141
142                         /* NETDEV_TX_BUSY - we need to requeue */
143                         /* Release the driver */
144                         if (!nolock) {
145                                 netif_tx_unlock(dev);
146                         }
147                         spin_lock(&dev->queue_lock);
148                         q = dev->qdisc;
149                 }
150
151                 /* Device kicked us out :(
152                    This is possible in three cases:
153
154                    0. driver is locked
155                    1. fastroute is enabled
156                    2. device cannot determine busy state
157                       before start of transmission (f.e. dialout)
158                    3. device is buggy (ppp)
159                  */
160
161 requeue:
162                 if (skb->next)
163                         dev->gso_skb = skb;
164                 else
165                         q->ops->requeue(skb, q);
166                 netif_schedule(dev);
167                 return 1;
168         }
169         BUG_ON((int) q->q.qlen < 0);
170         return q->q.qlen;
171 }
172
173 void __qdisc_run(struct net_device *dev)
174 {
175         if (unlikely(dev->qdisc == &noop_qdisc))
176                 goto out;
177
178         while (qdisc_restart(dev) < 0 && !netif_queue_stopped(dev))
179                 /* NOTHING */;
180
181 out:
182         clear_bit(__LINK_STATE_QDISC_RUNNING, &dev->state);
183 }
184
185 static void dev_watchdog(unsigned long arg)
186 {
187         struct net_device *dev = (struct net_device *)arg;
188
189         netif_tx_lock(dev);
190         if (dev->qdisc != &noop_qdisc) {
191                 if (netif_device_present(dev) &&
192                     netif_running(dev) &&
193                     netif_carrier_ok(dev)) {
194                         if (netif_queue_stopped(dev) &&
195                             time_after(jiffies, dev->trans_start + dev->watchdog_timeo)) {
196
197                                 printk(KERN_INFO "NETDEV WATCHDOG: %s: transmit timed out\n",
198                                        dev->name);
199                                 dev->tx_timeout(dev);
200                         }
201                         if (!mod_timer(&dev->watchdog_timer, round_jiffies(jiffies + dev->watchdog_timeo)))
202                                 dev_hold(dev);
203                 }
204         }
205         netif_tx_unlock(dev);
206
207         dev_put(dev);
208 }
209
210 static void dev_watchdog_init(struct net_device *dev)
211 {
212         init_timer(&dev->watchdog_timer);
213         dev->watchdog_timer.data = (unsigned long)dev;
214         dev->watchdog_timer.function = dev_watchdog;
215 }
216
217 void __netdev_watchdog_up(struct net_device *dev)
218 {
219         if (dev->tx_timeout) {
220                 if (dev->watchdog_timeo <= 0)
221                         dev->watchdog_timeo = 5*HZ;
222                 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo))
223                         dev_hold(dev);
224         }
225 }
226
227 static void dev_watchdog_up(struct net_device *dev)
228 {
229         __netdev_watchdog_up(dev);
230 }
231
232 static void dev_watchdog_down(struct net_device *dev)
233 {
234         netif_tx_lock_bh(dev);
235         if (del_timer(&dev->watchdog_timer))
236                 dev_put(dev);
237         netif_tx_unlock_bh(dev);
238 }
239
240 void netif_carrier_on(struct net_device *dev)
241 {
242         if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state))
243                 linkwatch_fire_event(dev);
244         if (netif_running(dev))
245                 __netdev_watchdog_up(dev);
246 }
247
248 void netif_carrier_off(struct net_device *dev)
249 {
250         if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state))
251                 linkwatch_fire_event(dev);
252 }
253
254 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces
255    under all circumstances. It is difficult to invent anything faster or
256    cheaper.
257  */
258
259 static int noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc)
260 {
261         kfree_skb(skb);
262         return NET_XMIT_CN;
263 }
264
265 static struct sk_buff *noop_dequeue(struct Qdisc * qdisc)
266 {
267         return NULL;
268 }
269
270 static int noop_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
271 {
272         if (net_ratelimit())
273                 printk(KERN_DEBUG "%s deferred output. It is buggy.\n",
274                        skb->dev->name);
275         kfree_skb(skb);
276         return NET_XMIT_CN;
277 }
278
279 struct Qdisc_ops noop_qdisc_ops = {
280         .id             =       "noop",
281         .priv_size      =       0,
282         .enqueue        =       noop_enqueue,
283         .dequeue        =       noop_dequeue,
284         .requeue        =       noop_requeue,
285         .owner          =       THIS_MODULE,
286 };
287
288 struct Qdisc noop_qdisc = {
289         .enqueue        =       noop_enqueue,
290         .dequeue        =       noop_dequeue,
291         .flags          =       TCQ_F_BUILTIN,
292         .ops            =       &noop_qdisc_ops,
293         .list           =       LIST_HEAD_INIT(noop_qdisc.list),
294 };
295
296 static struct Qdisc_ops noqueue_qdisc_ops = {
297         .id             =       "noqueue",
298         .priv_size      =       0,
299         .enqueue        =       noop_enqueue,
300         .dequeue        =       noop_dequeue,
301         .requeue        =       noop_requeue,
302         .owner          =       THIS_MODULE,
303 };
304
305 static struct Qdisc noqueue_qdisc = {
306         .enqueue        =       NULL,
307         .dequeue        =       noop_dequeue,
308         .flags          =       TCQ_F_BUILTIN,
309         .ops            =       &noqueue_qdisc_ops,
310         .list           =       LIST_HEAD_INIT(noqueue_qdisc.list),
311 };
312
313
314 static const u8 prio2band[TC_PRIO_MAX+1] =
315         { 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 };
316
317 /* 3-band FIFO queue: old style, but should be a bit faster than
318    generic prio+fifo combination.
319  */
320
321 #define PFIFO_FAST_BANDS 3
322
323 static inline struct sk_buff_head *prio2list(struct sk_buff *skb,
324                                              struct Qdisc *qdisc)
325 {
326         struct sk_buff_head *list = qdisc_priv(qdisc);
327         return list + prio2band[skb->priority & TC_PRIO_MAX];
328 }
329
330 static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc)
331 {
332         struct sk_buff_head *list = prio2list(skb, qdisc);
333
334         if (skb_queue_len(list) < qdisc->dev->tx_queue_len) {
335                 qdisc->q.qlen++;
336                 return __qdisc_enqueue_tail(skb, qdisc, list);
337         }
338
339         return qdisc_drop(skb, qdisc);
340 }
341
342 static struct sk_buff *pfifo_fast_dequeue(struct Qdisc* qdisc)
343 {
344         int prio;
345         struct sk_buff_head *list = qdisc_priv(qdisc);
346
347         for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) {
348                 if (!skb_queue_empty(list + prio)) {
349                         qdisc->q.qlen--;
350                         return __qdisc_dequeue_head(qdisc, list + prio);
351                 }
352         }
353
354         return NULL;
355 }
356
357 static int pfifo_fast_requeue(struct sk_buff *skb, struct Qdisc* qdisc)
358 {
359         qdisc->q.qlen++;
360         return __qdisc_requeue(skb, qdisc, prio2list(skb, qdisc));
361 }
362
363 static void pfifo_fast_reset(struct Qdisc* qdisc)
364 {
365         int prio;
366         struct sk_buff_head *list = qdisc_priv(qdisc);
367
368         for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
369                 __qdisc_reset_queue(qdisc, list + prio);
370
371         qdisc->qstats.backlog = 0;
372         qdisc->q.qlen = 0;
373 }
374
375 static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
376 {
377         struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS };
378
379         memcpy(&opt.priomap, prio2band, TC_PRIO_MAX+1);
380         RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
381         return skb->len;
382
383 rtattr_failure:
384         return -1;
385 }
386
387 static int pfifo_fast_init(struct Qdisc *qdisc, struct rtattr *opt)
388 {
389         int prio;
390         struct sk_buff_head *list = qdisc_priv(qdisc);
391
392         for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
393                 skb_queue_head_init(list + prio);
394
395         return 0;
396 }
397
398 static struct Qdisc_ops pfifo_fast_ops = {
399         .id             =       "pfifo_fast",
400         .priv_size      =       PFIFO_FAST_BANDS * sizeof(struct sk_buff_head),
401         .enqueue        =       pfifo_fast_enqueue,
402         .dequeue        =       pfifo_fast_dequeue,
403         .requeue        =       pfifo_fast_requeue,
404         .init           =       pfifo_fast_init,
405         .reset          =       pfifo_fast_reset,
406         .dump           =       pfifo_fast_dump,
407         .owner          =       THIS_MODULE,
408 };
409
410 struct Qdisc *qdisc_alloc(struct net_device *dev, struct Qdisc_ops *ops)
411 {
412         void *p;
413         struct Qdisc *sch;
414         unsigned int size;
415         int err = -ENOBUFS;
416
417         /* ensure that the Qdisc and the private data are 32-byte aligned */
418         size = QDISC_ALIGN(sizeof(*sch));
419         size += ops->priv_size + (QDISC_ALIGNTO - 1);
420
421         p = kzalloc(size, GFP_KERNEL);
422         if (!p)
423                 goto errout;
424         sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
425         sch->padded = (char *) sch - (char *) p;
426
427         INIT_LIST_HEAD(&sch->list);
428         skb_queue_head_init(&sch->q);
429         sch->ops = ops;
430         sch->enqueue = ops->enqueue;
431         sch->dequeue = ops->dequeue;
432         sch->dev = dev;
433         dev_hold(dev);
434         sch->stats_lock = &dev->queue_lock;
435         atomic_set(&sch->refcnt, 1);
436
437         return sch;
438 errout:
439         return ERR_PTR(-err);
440 }
441
442 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops,
443                                  unsigned int parentid)
444 {
445         struct Qdisc *sch;
446
447         sch = qdisc_alloc(dev, ops);
448         if (IS_ERR(sch))
449                 goto errout;
450         sch->parent = parentid;
451
452         if (!ops->init || ops->init(sch, NULL) == 0)
453                 return sch;
454
455         qdisc_destroy(sch);
456 errout:
457         return NULL;
458 }
459
460 /* Under dev->queue_lock and BH! */
461
462 void qdisc_reset(struct Qdisc *qdisc)
463 {
464         struct Qdisc_ops *ops = qdisc->ops;
465
466         if (ops->reset)
467                 ops->reset(qdisc);
468 }
469
470 /* this is the rcu callback function to clean up a qdisc when there
471  * are no further references to it */
472
473 static void __qdisc_destroy(struct rcu_head *head)
474 {
475         struct Qdisc *qdisc = container_of(head, struct Qdisc, q_rcu);
476         kfree((char *) qdisc - qdisc->padded);
477 }
478
479 /* Under dev->queue_lock and BH! */
480
481 void qdisc_destroy(struct Qdisc *qdisc)
482 {
483         struct Qdisc_ops  *ops = qdisc->ops;
484
485         if (qdisc->flags & TCQ_F_BUILTIN ||
486             !atomic_dec_and_test(&qdisc->refcnt))
487                 return;
488
489         list_del(&qdisc->list);
490 #ifdef CONFIG_NET_ESTIMATOR
491         gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est);
492 #endif
493         if (ops->reset)
494                 ops->reset(qdisc);
495         if (ops->destroy)
496                 ops->destroy(qdisc);
497
498         module_put(ops->owner);
499         dev_put(qdisc->dev);
500         call_rcu(&qdisc->q_rcu, __qdisc_destroy);
501 }
502
503 void dev_activate(struct net_device *dev)
504 {
505         /* No queueing discipline is attached to device;
506            create default one i.e. pfifo_fast for devices,
507            which need queueing and noqueue_qdisc for
508            virtual interfaces
509          */
510
511         if (dev->qdisc_sleeping == &noop_qdisc) {
512                 struct Qdisc *qdisc;
513                 if (dev->tx_queue_len) {
514                         qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops,
515                                                   TC_H_ROOT);
516                         if (qdisc == NULL) {
517                                 printk(KERN_INFO "%s: activation failed\n", dev->name);
518                                 return;
519                         }
520                         list_add_tail(&qdisc->list, &dev->qdisc_list);
521                 } else {
522                         qdisc =  &noqueue_qdisc;
523                 }
524                 dev->qdisc_sleeping = qdisc;
525         }
526
527         if (!netif_carrier_ok(dev))
528                 /* Delay activation until next carrier-on event */
529                 return;
530
531         spin_lock_bh(&dev->queue_lock);
532         rcu_assign_pointer(dev->qdisc, dev->qdisc_sleeping);
533         if (dev->qdisc != &noqueue_qdisc) {
534                 dev->trans_start = jiffies;
535                 dev_watchdog_up(dev);
536         }
537         spin_unlock_bh(&dev->queue_lock);
538 }
539
540 void dev_deactivate(struct net_device *dev)
541 {
542         struct Qdisc *qdisc;
543
544         spin_lock_bh(&dev->queue_lock);
545         qdisc = dev->qdisc;
546         dev->qdisc = &noop_qdisc;
547
548         qdisc_reset(qdisc);
549
550         spin_unlock_bh(&dev->queue_lock);
551
552         dev_watchdog_down(dev);
553
554         /* Wait for outstanding dev_queue_xmit calls. */
555         synchronize_rcu();
556
557         /* Wait for outstanding qdisc_run calls. */
558         while (test_bit(__LINK_STATE_QDISC_RUNNING, &dev->state))
559                 yield();
560
561         if (dev->gso_skb) {
562                 kfree_skb(dev->gso_skb);
563                 dev->gso_skb = NULL;
564         }
565 }
566
567 void dev_init_scheduler(struct net_device *dev)
568 {
569         qdisc_lock_tree(dev);
570         dev->qdisc = &noop_qdisc;
571         dev->qdisc_sleeping = &noop_qdisc;
572         INIT_LIST_HEAD(&dev->qdisc_list);
573         qdisc_unlock_tree(dev);
574
575         dev_watchdog_init(dev);
576 }
577
578 void dev_shutdown(struct net_device *dev)
579 {
580         struct Qdisc *qdisc;
581
582         qdisc_lock_tree(dev);
583         qdisc = dev->qdisc_sleeping;
584         dev->qdisc = &noop_qdisc;
585         dev->qdisc_sleeping = &noop_qdisc;
586         qdisc_destroy(qdisc);
587 #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE)
588         if ((qdisc = dev->qdisc_ingress) != NULL) {
589                 dev->qdisc_ingress = NULL;
590                 qdisc_destroy(qdisc);
591         }
592 #endif
593         BUG_TRAP(!timer_pending(&dev->watchdog_timer));
594         qdisc_unlock_tree(dev);
595 }
596
597 EXPORT_SYMBOL(netif_carrier_on);
598 EXPORT_SYMBOL(netif_carrier_off);
599 EXPORT_SYMBOL(noop_qdisc);
600 EXPORT_SYMBOL(qdisc_create_dflt);
601 EXPORT_SYMBOL(qdisc_destroy);
602 EXPORT_SYMBOL(qdisc_reset);
603 EXPORT_SYMBOL(qdisc_lock_tree);
604 EXPORT_SYMBOL(qdisc_unlock_tree);