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