blob: ffad48109a228c66ccbd33124525dee83f9158df [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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
Linus Torvalds1da177e2005-04-16 15:20:36 -070014#include <linux/bitops.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015#include <linux/module.h>
16#include <linux/types.h>
17#include <linux/kernel.h>
18#include <linux/sched.h>
19#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#include <linux/errno.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include <linux/netdevice.h>
22#include <linux/skbuff.h>
23#include <linux/rtnetlink.h>
24#include <linux/init.h>
25#include <linux/rcupdate.h>
26#include <linux/list.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090027#include <linux/slab.h>
Jiri Pirko292f1c72013-02-12 00:12:03 +000028#include <net/sch_generic.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070029#include <net/pkt_sched.h>
Eric Dumazet7fee2262010-05-11 23:19:48 +000030#include <net/dst.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070031
32/* Main transmission queue. */
33
Patrick McHardy0463d4a2007-04-16 17:02:10 -070034/* Modifications to data participating in scheduling must be protected with
David S. Miller5fb66222008-08-02 20:02:43 -070035 * qdisc_lock(qdisc) spinlock.
Patrick McHardy0463d4a2007-04-16 17:02:10 -070036 *
37 * The idea is the following:
David S. Millerc7e4f3b2008-07-16 03:22:39 -070038 * - enqueue, dequeue are serialized via qdisc root lock
39 * - ingress filtering is also serialized via qdisc root lock
Patrick McHardy0463d4a2007-04-16 17:02:10 -070040 * - updates to tree and tree walking are only done under the rtnl mutex.
Linus Torvalds1da177e2005-04-16 15:20:36 -070041 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070042
David S. Miller37437bb2008-07-16 02:15:04 -070043static inline int dev_requeue_skb(struct sk_buff *skb, struct Qdisc *q)
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070044{
Eric Dumazet7fee2262010-05-11 23:19:48 +000045 skb_dst_force(skb);
Jarek Poplawski62523522008-10-06 10:41:50 -070046 q->gso_skb = skb;
Jarek Poplawski53e91502008-10-08 11:36:22 -070047 q->qstats.requeues++;
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +000048 q->q.qlen++; /* it's still part of the queue */
David S. Miller37437bb2008-07-16 02:15:04 -070049 __netif_schedule(q);
Jarek Poplawski62523522008-10-06 10:41:50 -070050
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070051 return 0;
52}
53
David S. Millerd3b753d2008-07-15 20:14:35 -070054static inline struct sk_buff *dequeue_skb(struct Qdisc *q)
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070055{
Jarek Poplawski554794d2008-10-06 09:54:39 -070056 struct sk_buff *skb = q->gso_skb;
Eric Dumazet1abbe132012-12-11 15:54:33 +000057 const struct netdev_queue *txq = q->dev_queue;
Jarek Poplawski554794d2008-10-06 09:54:39 -070058
Jarek Poplawskiebf05982008-09-22 22:16:23 -070059 if (unlikely(skb)) {
Jarek Poplawskiebf05982008-09-22 22:16:23 -070060 /* check the reason of requeuing without tx lock first */
Eric Dumazet1abbe132012-12-11 15:54:33 +000061 txq = netdev_get_tx_queue(txq->dev, skb_get_queue_mapping(skb));
Tom Herbert734664982011-11-28 16:32:44 +000062 if (!netif_xmit_frozen_or_stopped(txq)) {
Jarek Poplawski62523522008-10-06 10:41:50 -070063 q->gso_skb = NULL;
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +000064 q->q.qlen--;
65 } else
Jarek Poplawskiebf05982008-09-22 22:16:23 -070066 skb = NULL;
67 } else {
Eric Dumazet1abbe132012-12-11 15:54:33 +000068 if (!(q->flags & TCQ_F_ONETXQUEUE) || !netif_xmit_frozen_or_stopped(txq))
69 skb = q->dequeue(q);
Jarek Poplawskiebf05982008-09-22 22:16:23 -070070 }
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070071
72 return skb;
73}
74
Krishna Kumar6c1361a2007-06-24 19:56:09 -070075static inline int handle_dev_cpu_collision(struct sk_buff *skb,
David S. Miller970565b2008-07-08 23:10:33 -070076 struct netdev_queue *dev_queue,
Krishna Kumar6c1361a2007-06-24 19:56:09 -070077 struct Qdisc *q)
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070078{
Krishna Kumar6c1361a2007-06-24 19:56:09 -070079 int ret;
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070080
David S. Millerc773e842008-07-08 23:13:53 -070081 if (unlikely(dev_queue->xmit_lock_owner == smp_processor_id())) {
Krishna Kumar6c1361a2007-06-24 19:56:09 -070082 /*
83 * Same CPU holding the lock. It may be a transient
84 * configuration error, when hard_start_xmit() recurses. We
85 * detect it by checking xmit owner and drop the packet when
86 * deadloop is detected. Return OK to try the next skb.
87 */
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070088 kfree_skb(skb);
Joe Perchese87cc472012-05-13 21:56:26 +000089 net_warn_ratelimited("Dead loop on netdevice %s, fix it urgently!\n",
90 dev_queue->dev->name);
Krishna Kumar6c1361a2007-06-24 19:56:09 -070091 ret = qdisc_qlen(q);
92 } else {
93 /*
94 * Another cpu is holding lock, requeue & delay xmits for
95 * some time.
96 */
Eric Dumazetd6d9ca02010-07-19 10:48:49 +000097 __this_cpu_inc(softnet_data.cpu_collision);
David S. Miller37437bb2008-07-16 02:15:04 -070098 ret = dev_requeue_skb(skb, q);
Jamal Hadi Salimc716a812007-06-10 17:31:24 -070099 }
100
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700101 return ret;
Jamal Hadi Salimc716a812007-06-10 17:31:24 -0700102}
103
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900104/*
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000105 * Transmit one skb, and handle the return status as required. Holding the
106 * __QDISC_STATE_RUNNING bit guarantees that only one CPU can execute this
107 * function.
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700108 *
109 * Returns to the caller:
110 * 0 - queue is empty or throttled.
111 * >0 - queue is not empty.
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700112 */
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000113int sch_direct_xmit(struct sk_buff *skb, struct Qdisc *q,
114 struct net_device *dev, struct netdev_queue *txq,
115 spinlock_t *root_lock)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700116{
Peter P Waskiewicz Jr5f1a4852007-11-13 20:40:55 -0800117 int ret = NETDEV_TX_BUSY;
David S. Miller7698b4f2008-07-16 01:42:40 -0700118
119 /* And release qdisc */
120 spin_unlock(root_lock);
Herbert Xud90df3a2007-05-10 04:55:14 -0700121
David S. Millerc773e842008-07-08 23:13:53 -0700122 HARD_TX_LOCK(dev, txq, smp_processor_id());
Tom Herbert734664982011-11-28 16:32:44 +0000123 if (!netif_xmit_frozen_or_stopped(txq))
David S. Millerfd2ea0a2008-07-17 01:56:23 -0700124 ret = dev_hard_start_xmit(skb, dev, txq);
Patrick McHardy572a9d72009-11-10 06:14:14 +0000125
David S. Millerc773e842008-07-08 23:13:53 -0700126 HARD_TX_UNLOCK(dev, txq);
Jamal Hadi Salimc716a812007-06-10 17:31:24 -0700127
David S. Miller7698b4f2008-07-16 01:42:40 -0700128 spin_lock(root_lock);
Jamal Hadi Salimc716a812007-06-10 17:31:24 -0700129
Jarek Poplawski9a1654b2009-11-15 07:20:12 +0000130 if (dev_xmit_complete(ret)) {
131 /* Driver sent out skb successfully or skb was consumed */
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700132 ret = qdisc_qlen(q);
Jarek Poplawski9a1654b2009-11-15 07:20:12 +0000133 } else if (ret == NETDEV_TX_LOCKED) {
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700134 /* Driver try lock failed */
David S. Millereb6aafe2008-07-08 23:12:38 -0700135 ret = handle_dev_cpu_collision(skb, txq, q);
Jarek Poplawski9a1654b2009-11-15 07:20:12 +0000136 } else {
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700137 /* Driver returned NETDEV_TX_BUSY - requeue skb */
Joe Perchese87cc472012-05-13 21:56:26 +0000138 if (unlikely(ret != NETDEV_TX_BUSY))
139 net_warn_ratelimited("BUG %s code %d qlen %d\n",
140 dev->name, ret, q->q.qlen);
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700141
David S. Miller37437bb2008-07-16 02:15:04 -0700142 ret = dev_requeue_skb(skb, q);
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700143 }
144
Tom Herbert734664982011-11-28 16:32:44 +0000145 if (ret && netif_xmit_frozen_or_stopped(txq))
David S. Miller37437bb2008-07-16 02:15:04 -0700146 ret = 0;
147
Krishna Kumar6c1361a2007-06-24 19:56:09 -0700148 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149}
150
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000151/*
152 * NOTE: Called under qdisc_lock(q) with locally disabled BH.
153 *
154 * __QDISC_STATE_RUNNING guarantees only one CPU can process
155 * this qdisc at a time. qdisc_lock(q) serializes queue accesses for
156 * this queue.
157 *
158 * netif_tx_lock serializes accesses to device driver.
159 *
160 * qdisc_lock(q) and netif_tx_lock are mutually exclusive,
161 * if one is grabbed, another must be free.
162 *
163 * Note, that this procedure can be called by a watchdog timer
164 *
165 * Returns to the caller:
166 * 0 - queue is empty or throttled.
167 * >0 - queue is not empty.
168 *
169 */
170static inline int qdisc_restart(struct Qdisc *q)
171{
172 struct netdev_queue *txq;
173 struct net_device *dev;
174 spinlock_t *root_lock;
175 struct sk_buff *skb;
176
177 /* Dequeue packet */
178 skb = dequeue_skb(q);
179 if (unlikely(!skb))
180 return 0;
Eric Dumazet7fee2262010-05-11 23:19:48 +0000181 WARN_ON_ONCE(skb_dst_is_noref(skb));
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000182 root_lock = qdisc_lock(q);
183 dev = qdisc_dev(q);
184 txq = netdev_get_tx_queue(dev, skb_get_queue_mapping(skb));
185
186 return sch_direct_xmit(skb, q, dev, txq, root_lock);
187}
188
David S. Miller37437bb2008-07-16 02:15:04 -0700189void __qdisc_run(struct Qdisc *q)
Herbert Xu48d83322006-06-19 23:57:59 -0700190{
jamald5b8aa12011-06-26 08:13:54 +0000191 int quota = weight_p;
Herbert Xu2ba25062008-03-28 16:25:26 -0700192
David S. Miller37437bb2008-07-16 02:15:04 -0700193 while (qdisc_restart(q)) {
Herbert Xu2ba25062008-03-28 16:25:26 -0700194 /*
jamald5b8aa12011-06-26 08:13:54 +0000195 * Ordered by possible occurrence: Postpone processing if
196 * 1. we've exceeded packet quota
197 * 2. another process needs the CPU;
Herbert Xu2ba25062008-03-28 16:25:26 -0700198 */
Krishna Kumarf0c50c72011-07-14 23:16:21 +0000199 if (--quota <= 0 || need_resched()) {
David S. Miller37437bb2008-07-16 02:15:04 -0700200 __netif_schedule(q);
Herbert Xu2ba25062008-03-28 16:25:26 -0700201 break;
202 }
203 }
Herbert Xu48d83322006-06-19 23:57:59 -0700204
Eric Dumazetbc135b22010-06-02 03:23:51 -0700205 qdisc_run_end(q);
Herbert Xu48d83322006-06-19 23:57:59 -0700206}
207
Eric Dumazet9d214932009-05-17 20:55:16 -0700208unsigned long dev_trans_start(struct net_device *dev)
209{
210 unsigned long val, res = dev->trans_start;
211 unsigned int i;
212
213 for (i = 0; i < dev->num_tx_queues; i++) {
214 val = netdev_get_tx_queue(dev, i)->trans_start;
215 if (val && time_after(val, res))
216 res = val;
217 }
218 dev->trans_start = res;
219 return res;
220}
221EXPORT_SYMBOL(dev_trans_start);
222
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223static void dev_watchdog(unsigned long arg)
224{
225 struct net_device *dev = (struct net_device *)arg;
226
Herbert Xu932ff272006-06-09 12:20:56 -0700227 netif_tx_lock(dev);
David S. Millere8a04642008-07-17 00:34:19 -0700228 if (!qdisc_tx_is_noop(dev)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 if (netif_device_present(dev) &&
230 netif_running(dev) &&
231 netif_carrier_ok(dev)) {
Eric Dumazet9d214932009-05-17 20:55:16 -0700232 int some_queue_timedout = 0;
David S. Millere8a04642008-07-17 00:34:19 -0700233 unsigned int i;
Eric Dumazet9d214932009-05-17 20:55:16 -0700234 unsigned long trans_start;
Stephen Hemminger338f7562006-05-16 15:02:12 -0700235
David S. Millere8a04642008-07-17 00:34:19 -0700236 for (i = 0; i < dev->num_tx_queues; i++) {
237 struct netdev_queue *txq;
238
239 txq = netdev_get_tx_queue(dev, i);
Eric Dumazet9d214932009-05-17 20:55:16 -0700240 /*
241 * old device drivers set dev->trans_start
242 */
243 trans_start = txq->trans_start ? : dev->trans_start;
Tom Herbert734664982011-11-28 16:32:44 +0000244 if (netif_xmit_stopped(txq) &&
Eric Dumazet9d214932009-05-17 20:55:16 -0700245 time_after(jiffies, (trans_start +
246 dev->watchdog_timeo))) {
247 some_queue_timedout = 1;
david decotignyccf5ff62011-11-16 12:15:10 +0000248 txq->trans_timeout++;
David S. Millere8a04642008-07-17 00:34:19 -0700249 break;
250 }
251 }
252
Eric Dumazet9d214932009-05-17 20:55:16 -0700253 if (some_queue_timedout) {
Eric Dumazet9d214932009-05-17 20:55:16 -0700254 WARN_ONCE(1, KERN_INFO "NETDEV WATCHDOG: %s (%s): transmit queue %u timed out\n",
David S. Miller3019de12011-06-06 16:41:33 -0700255 dev->name, netdev_drivername(dev), i);
Stephen Hemmingerd3147742008-11-19 21:32:24 -0800256 dev->netdev_ops->ndo_tx_timeout(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257 }
David S. Millere8a04642008-07-17 00:34:19 -0700258 if (!mod_timer(&dev->watchdog_timer,
259 round_jiffies(jiffies +
260 dev->watchdog_timeo)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261 dev_hold(dev);
262 }
263 }
Herbert Xu932ff272006-06-09 12:20:56 -0700264 netif_tx_unlock(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700265
266 dev_put(dev);
267}
268
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269void __netdev_watchdog_up(struct net_device *dev)
270{
Stephen Hemmingerd3147742008-11-19 21:32:24 -0800271 if (dev->netdev_ops->ndo_tx_timeout) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700272 if (dev->watchdog_timeo <= 0)
273 dev->watchdog_timeo = 5*HZ;
Venkatesh Pallipadi60468d52007-05-31 21:28:44 -0700274 if (!mod_timer(&dev->watchdog_timer,
275 round_jiffies(jiffies + dev->watchdog_timeo)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276 dev_hold(dev);
277 }
278}
279
280static void dev_watchdog_up(struct net_device *dev)
281{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282 __netdev_watchdog_up(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283}
284
285static void dev_watchdog_down(struct net_device *dev)
286{
Herbert Xu932ff272006-06-09 12:20:56 -0700287 netif_tx_lock_bh(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288 if (del_timer(&dev->watchdog_timer))
Stephen Hemminger15333062006-03-20 22:32:28 -0800289 dev_put(dev);
Herbert Xu932ff272006-06-09 12:20:56 -0700290 netif_tx_unlock_bh(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700291}
292
Stephen Hemmingerbea33482007-10-03 16:41:36 -0700293/**
294 * netif_carrier_on - set carrier
295 * @dev: network device
296 *
297 * Device has detected that carrier.
298 */
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700299void netif_carrier_on(struct net_device *dev)
300{
Jeff Garzikbfaae0f2007-10-17 23:26:43 -0700301 if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state)) {
David S. Millerb4730012008-11-19 15:33:54 -0800302 if (dev->reg_state == NETREG_UNINITIALIZED)
303 return;
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700304 linkwatch_fire_event(dev);
Jeff Garzikbfaae0f2007-10-17 23:26:43 -0700305 if (netif_running(dev))
306 __netdev_watchdog_up(dev);
307 }
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700308}
Patrick McHardy62e3ba12008-01-22 22:10:23 -0800309EXPORT_SYMBOL(netif_carrier_on);
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700310
Stephen Hemmingerbea33482007-10-03 16:41:36 -0700311/**
312 * netif_carrier_off - clear carrier
313 * @dev: network device
314 *
315 * Device has detected loss of carrier.
316 */
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700317void netif_carrier_off(struct net_device *dev)
318{
David S. Millerb4730012008-11-19 15:33:54 -0800319 if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state)) {
320 if (dev->reg_state == NETREG_UNINITIALIZED)
321 return;
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700322 linkwatch_fire_event(dev);
David S. Millerb4730012008-11-19 15:33:54 -0800323 }
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700324}
Patrick McHardy62e3ba12008-01-22 22:10:23 -0800325EXPORT_SYMBOL(netif_carrier_off);
Denis Vlasenko0a242ef2005-08-11 15:32:53 -0700326
Linus Torvalds1da177e2005-04-16 15:20:36 -0700327/* "NOOP" scheduler: the best scheduler, recommended for all interfaces
328 under all circumstances. It is difficult to invent anything faster or
329 cheaper.
330 */
331
Thomas Graf94df1092005-06-18 22:59:08 -0700332static int noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333{
334 kfree_skb(skb);
335 return NET_XMIT_CN;
336}
337
Thomas Graf94df1092005-06-18 22:59:08 -0700338static struct sk_buff *noop_dequeue(struct Qdisc * qdisc)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339{
340 return NULL;
341}
342
Eric Dumazet20fea082007-11-14 01:44:41 -0800343struct Qdisc_ops noop_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344 .id = "noop",
345 .priv_size = 0,
346 .enqueue = noop_enqueue,
347 .dequeue = noop_dequeue,
Jarek Poplawski99c0db22008-10-31 00:45:27 -0700348 .peek = noop_dequeue,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700349 .owner = THIS_MODULE,
350};
351
David S. Miller7698b4f2008-07-16 01:42:40 -0700352static struct netdev_queue noop_netdev_queue = {
David S. Miller7698b4f2008-07-16 01:42:40 -0700353 .qdisc = &noop_qdisc,
Jarek Poplawski9f3ffae2008-10-19 23:37:47 -0700354 .qdisc_sleeping = &noop_qdisc,
David S. Miller7698b4f2008-07-16 01:42:40 -0700355};
356
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357struct Qdisc noop_qdisc = {
358 .enqueue = noop_enqueue,
359 .dequeue = noop_dequeue,
360 .flags = TCQ_F_BUILTIN,
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900361 .ops = &noop_qdisc_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362 .list = LIST_HEAD_INIT(noop_qdisc.list),
David S. Miller83874002008-07-17 00:53:03 -0700363 .q.lock = __SPIN_LOCK_UNLOCKED(noop_qdisc.q.lock),
David S. Miller7698b4f2008-07-16 01:42:40 -0700364 .dev_queue = &noop_netdev_queue,
Eric Dumazet7b5edbc2010-10-15 19:22:34 +0000365 .busylock = __SPIN_LOCK_UNLOCKED(noop_qdisc.busylock),
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366};
Patrick McHardy62e3ba12008-01-22 22:10:23 -0800367EXPORT_SYMBOL(noop_qdisc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368
Eric Dumazet20fea082007-11-14 01:44:41 -0800369static struct Qdisc_ops noqueue_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370 .id = "noqueue",
371 .priv_size = 0,
372 .enqueue = noop_enqueue,
373 .dequeue = noop_dequeue,
Jarek Poplawski99c0db22008-10-31 00:45:27 -0700374 .peek = noop_dequeue,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700375 .owner = THIS_MODULE,
376};
377
David S. Miller30ee42b2008-07-18 23:00:11 -0700378static struct Qdisc noqueue_qdisc;
379static struct netdev_queue noqueue_netdev_queue = {
380 .qdisc = &noqueue_qdisc,
Jarek Poplawski9f3ffae2008-10-19 23:37:47 -0700381 .qdisc_sleeping = &noqueue_qdisc,
David S. Miller30ee42b2008-07-18 23:00:11 -0700382};
383
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384static struct Qdisc noqueue_qdisc = {
385 .enqueue = NULL,
386 .dequeue = noop_dequeue,
387 .flags = TCQ_F_BUILTIN,
388 .ops = &noqueue_qdisc_ops,
389 .list = LIST_HEAD_INIT(noqueue_qdisc.list),
David S. Miller30ee42b2008-07-18 23:00:11 -0700390 .q.lock = __SPIN_LOCK_UNLOCKED(noqueue_qdisc.q.lock),
391 .dev_queue = &noqueue_netdev_queue,
Eric Dumazet7b5edbc2010-10-15 19:22:34 +0000392 .busylock = __SPIN_LOCK_UNLOCKED(noqueue_qdisc.busylock),
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393};
394
395
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000396static const u8 prio2band[TC_PRIO_MAX + 1] = {
397 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
398};
Thomas Graf321090e2005-06-18 22:58:35 -0700399
David S. Millerd3678b42008-07-21 09:56:13 -0700400/* 3-band FIFO queue: old style, but should be a bit faster than
401 generic prio+fifo combination.
402 */
403
404#define PFIFO_FAST_BANDS 3
405
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000406/*
407 * Private data for a pfifo_fast scheduler containing:
408 * - queues for the three band
409 * - bitmap indicating which of the bands contain skbs
410 */
411struct pfifo_fast_priv {
412 u32 bitmap;
413 struct sk_buff_head q[PFIFO_FAST_BANDS];
414};
415
416/*
417 * Convert a bitmap to the first band number where an skb is queued, where:
418 * bitmap=0 means there are no skbs on any band.
419 * bitmap=1 means there is an skb on band 0.
420 * bitmap=7 means there are skbs on all 3 bands, etc.
421 */
422static const int bitmap2band[] = {-1, 0, 1, 0, 2, 0, 1, 0};
423
424static inline struct sk_buff_head *band2list(struct pfifo_fast_priv *priv,
425 int band)
David S. Millerd3678b42008-07-21 09:56:13 -0700426{
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000427 return priv->q + band;
David S. Millerd3678b42008-07-21 09:56:13 -0700428}
429
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000430static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc *qdisc)
David S. Millerd3678b42008-07-21 09:56:13 -0700431{
Krishna Kumara453e062009-08-30 22:20:28 -0700432 if (skb_queue_len(&qdisc->q) < qdisc_dev(qdisc)->tx_queue_len) {
433 int band = prio2band[skb->priority & TC_PRIO_MAX];
434 struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
435 struct sk_buff_head *list = band2list(priv, band);
David S. Millerd3678b42008-07-21 09:56:13 -0700436
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000437 priv->bitmap |= (1 << band);
David S. Millerd3678b42008-07-21 09:56:13 -0700438 qdisc->q.qlen++;
Thomas Graf821d24a2005-06-18 22:58:15 -0700439 return __qdisc_enqueue_tail(skb, qdisc, list);
David S. Millerd3678b42008-07-21 09:56:13 -0700440 }
Thomas Graf821d24a2005-06-18 22:58:15 -0700441
442 return qdisc_drop(skb, qdisc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443}
444
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000445static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446{
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000447 struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
448 int band = bitmap2band[priv->bitmap];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700449
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000450 if (likely(band >= 0)) {
451 struct sk_buff_head *list = band2list(priv, band);
452 struct sk_buff *skb = __qdisc_dequeue_head(qdisc, list);
453
454 qdisc->q.qlen--;
455 if (skb_queue_empty(list))
456 priv->bitmap &= ~(1 << band);
457
458 return skb;
David S. Millerd3678b42008-07-21 09:56:13 -0700459 }
Thomas Graff87a9c32005-06-18 22:58:53 -0700460
Linus Torvalds1da177e2005-04-16 15:20:36 -0700461 return NULL;
462}
463
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000464static struct sk_buff *pfifo_fast_peek(struct Qdisc *qdisc)
Jarek Poplawski99c0db22008-10-31 00:45:27 -0700465{
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000466 struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
467 int band = bitmap2band[priv->bitmap];
Jarek Poplawski99c0db22008-10-31 00:45:27 -0700468
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000469 if (band >= 0) {
470 struct sk_buff_head *list = band2list(priv, band);
471
472 return skb_peek(list);
Jarek Poplawski99c0db22008-10-31 00:45:27 -0700473 }
474
475 return NULL;
476}
477
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000478static void pfifo_fast_reset(struct Qdisc *qdisc)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479{
David S. Millerd3678b42008-07-21 09:56:13 -0700480 int prio;
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000481 struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
David S. Millerd3678b42008-07-21 09:56:13 -0700482
483 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000484 __qdisc_reset_queue(qdisc, band2list(priv, prio));
David S. Millerd3678b42008-07-21 09:56:13 -0700485
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000486 priv->bitmap = 0;
Thomas Graf821d24a2005-06-18 22:58:15 -0700487 qdisc->qstats.backlog = 0;
David S. Millerd3678b42008-07-21 09:56:13 -0700488 qdisc->q.qlen = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489}
490
David S. Millerd3678b42008-07-21 09:56:13 -0700491static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
492{
493 struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS };
494
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000495 memcpy(&opt.priomap, prio2band, TC_PRIO_MAX + 1);
David S. Miller1b34ec42012-03-29 05:11:39 -0400496 if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
497 goto nla_put_failure;
David S. Millerd3678b42008-07-21 09:56:13 -0700498 return skb->len;
499
500nla_put_failure:
501 return -1;
502}
503
504static int pfifo_fast_init(struct Qdisc *qdisc, struct nlattr *opt)
505{
506 int prio;
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000507 struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
David S. Millerd3678b42008-07-21 09:56:13 -0700508
509 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000510 skb_queue_head_init(band2list(priv, prio));
David S. Millerd3678b42008-07-21 09:56:13 -0700511
Eric Dumazet23624932011-01-21 16:26:09 -0800512 /* Can by-pass the queue discipline */
513 qdisc->flags |= TCQ_F_CAN_BYPASS;
David S. Millerd3678b42008-07-21 09:56:13 -0700514 return 0;
515}
516
David S. Miller6ec1c692009-09-06 01:58:51 -0700517struct Qdisc_ops pfifo_fast_ops __read_mostly = {
David S. Millerd3678b42008-07-21 09:56:13 -0700518 .id = "pfifo_fast",
Krishna Kumarfd3ae5e2009-08-18 21:55:59 +0000519 .priv_size = sizeof(struct pfifo_fast_priv),
David S. Millerd3678b42008-07-21 09:56:13 -0700520 .enqueue = pfifo_fast_enqueue,
521 .dequeue = pfifo_fast_dequeue,
Jarek Poplawski99c0db22008-10-31 00:45:27 -0700522 .peek = pfifo_fast_peek,
David S. Millerd3678b42008-07-21 09:56:13 -0700523 .init = pfifo_fast_init,
524 .reset = pfifo_fast_reset,
525 .dump = pfifo_fast_dump,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700526 .owner = THIS_MODULE,
527};
John Fastabendb8970f02011-01-17 08:06:09 +0000528EXPORT_SYMBOL(pfifo_fast_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700529
Eric Dumazet23d3b8b2012-09-05 01:02:56 +0000530static struct lock_class_key qdisc_tx_busylock;
531
David S. Miller5ce2d482008-07-08 17:06:30 -0700532struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
David S. Millerbb949fb2008-07-08 16:55:56 -0700533 struct Qdisc_ops *ops)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534{
535 void *p;
536 struct Qdisc *sch;
Eric Dumazetd2760552011-03-03 11:10:02 -0800537 unsigned int size = QDISC_ALIGN(sizeof(*sch)) + ops->priv_size;
Thomas Graf3d54b822005-07-05 14:15:09 -0700538 int err = -ENOBUFS;
Eric Dumazet23d3b8b2012-09-05 01:02:56 +0000539 struct net_device *dev = dev_queue->dev;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700540
Eric Dumazetf2cd2d32010-11-29 08:14:37 +0000541 p = kzalloc_node(size, GFP_KERNEL,
542 netdev_queue_numa_node_read(dev_queue));
543
Linus Torvalds1da177e2005-04-16 15:20:36 -0700544 if (!p)
Thomas Graf3d54b822005-07-05 14:15:09 -0700545 goto errout;
Thomas Graf3d54b822005-07-05 14:15:09 -0700546 sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
Eric Dumazetd2760552011-03-03 11:10:02 -0800547 /* if we got non aligned memory, ask more and do alignment ourself */
548 if (sch != p) {
549 kfree(p);
550 p = kzalloc_node(size + QDISC_ALIGNTO - 1, GFP_KERNEL,
551 netdev_queue_numa_node_read(dev_queue));
552 if (!p)
553 goto errout;
554 sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
555 sch->padded = (char *) sch - (char *) p;
556 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700557 INIT_LIST_HEAD(&sch->list);
558 skb_queue_head_init(&sch->q);
Eric Dumazet23d3b8b2012-09-05 01:02:56 +0000559
Eric Dumazet79640a42010-06-02 05:09:29 -0700560 spin_lock_init(&sch->busylock);
Eric Dumazet23d3b8b2012-09-05 01:02:56 +0000561 lockdep_set_class(&sch->busylock,
562 dev->qdisc_tx_busylock ?: &qdisc_tx_busylock);
563
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564 sch->ops = ops;
565 sch->enqueue = ops->enqueue;
566 sch->dequeue = ops->dequeue;
David S. Millerbb949fb2008-07-08 16:55:56 -0700567 sch->dev_queue = dev_queue;
Eric Dumazet23d3b8b2012-09-05 01:02:56 +0000568 dev_hold(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700569 atomic_set(&sch->refcnt, 1);
Thomas Graf3d54b822005-07-05 14:15:09 -0700570
571 return sch;
572errout:
WANG Cong01e123d2008-06-27 19:51:35 -0700573 return ERR_PTR(err);
Thomas Graf3d54b822005-07-05 14:15:09 -0700574}
575
Changli Gao3511c912010-10-16 13:04:08 +0000576struct Qdisc *qdisc_create_dflt(struct netdev_queue *dev_queue,
577 struct Qdisc_ops *ops, unsigned int parentid)
Thomas Graf3d54b822005-07-05 14:15:09 -0700578{
579 struct Qdisc *sch;
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900580
David S. Miller5ce2d482008-07-08 17:06:30 -0700581 sch = qdisc_alloc(dev_queue, ops);
Thomas Graf3d54b822005-07-05 14:15:09 -0700582 if (IS_ERR(sch))
583 goto errout;
Patrick McHardy9f9afec2006-11-29 17:35:18 -0800584 sch->parent = parentid;
Thomas Graf3d54b822005-07-05 14:15:09 -0700585
Linus Torvalds1da177e2005-04-16 15:20:36 -0700586 if (!ops->init || ops->init(sch, NULL) == 0)
587 return sch;
588
Thomas Graf0fbbeb12005-08-23 10:12:44 -0700589 qdisc_destroy(sch);
Thomas Graf3d54b822005-07-05 14:15:09 -0700590errout:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591 return NULL;
592}
Patrick McHardy62e3ba12008-01-22 22:10:23 -0800593EXPORT_SYMBOL(qdisc_create_dflt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700594
David S. Miller5fb66222008-08-02 20:02:43 -0700595/* Under qdisc_lock(qdisc) and BH! */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700596
597void qdisc_reset(struct Qdisc *qdisc)
598{
Eric Dumazet20fea082007-11-14 01:44:41 -0800599 const struct Qdisc_ops *ops = qdisc->ops;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700600
601 if (ops->reset)
602 ops->reset(qdisc);
Jarek Poplawski67305eb2008-11-03 02:52:50 -0800603
Krishna Kumarbbd8a0d2009-08-06 01:44:21 +0000604 if (qdisc->gso_skb) {
605 kfree_skb(qdisc->gso_skb);
606 qdisc->gso_skb = NULL;
607 qdisc->q.qlen = 0;
608 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700609}
Patrick McHardy62e3ba12008-01-22 22:10:23 -0800610EXPORT_SYMBOL(qdisc_reset);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700611
Eric Dumazet5d944c62010-03-31 07:06:04 +0000612static void qdisc_rcu_free(struct rcu_head *head)
613{
614 struct Qdisc *qdisc = container_of(head, struct Qdisc, rcu_head);
615
616 kfree((char *) qdisc - qdisc->padded);
617}
618
David S. Miller1e0d5a52008-08-17 22:31:26 -0700619void qdisc_destroy(struct Qdisc *qdisc)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700620{
Eric Dumazet20fea082007-11-14 01:44:41 -0800621 const struct Qdisc_ops *ops = qdisc->ops;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700622
David S. Miller1e0d5a52008-08-17 22:31:26 -0700623 if (qdisc->flags & TCQ_F_BUILTIN ||
624 !atomic_dec_and_test(&qdisc->refcnt))
625 return;
626
David S. Miller3a682fb2008-07-20 18:13:01 -0700627#ifdef CONFIG_NET_SCHED
Jarek Poplawskif6e0b232008-08-22 03:24:05 -0700628 qdisc_list_del(qdisc);
629
Eric Dumazeta2da5702011-01-20 03:48:19 +0000630 qdisc_put_stab(rtnl_dereference(qdisc->stab));
David S. Miller3a682fb2008-07-20 18:13:01 -0700631#endif
Patrick McHardy85670cc2006-09-27 16:45:45 -0700632 gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est);
Patrick McHardy85670cc2006-09-27 16:45:45 -0700633 if (ops->reset)
634 ops->reset(qdisc);
635 if (ops->destroy)
636 ops->destroy(qdisc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637
Patrick McHardy85670cc2006-09-27 16:45:45 -0700638 module_put(ops->owner);
David S. Miller5ce2d482008-07-08 17:06:30 -0700639 dev_put(qdisc_dev(qdisc));
David S. Miller8a34c5d2008-07-17 00:47:45 -0700640
Jarek Poplawski554794d2008-10-06 09:54:39 -0700641 kfree_skb(qdisc->gso_skb);
Eric Dumazet5d944c62010-03-31 07:06:04 +0000642 /*
643 * gen_estimator est_timer() might access qdisc->q.lock,
644 * wait a RCU grace period before freeing qdisc.
645 */
646 call_rcu(&qdisc->rcu_head, qdisc_rcu_free);
David S. Miller8a34c5d2008-07-17 00:47:45 -0700647}
Patrick McHardy62e3ba12008-01-22 22:10:23 -0800648EXPORT_SYMBOL(qdisc_destroy);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700649
Patrick McHardy589983c2009-09-04 06:41:20 +0000650/* Attach toplevel qdisc to device queue. */
651struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
652 struct Qdisc *qdisc)
653{
654 struct Qdisc *oqdisc = dev_queue->qdisc_sleeping;
655 spinlock_t *root_lock;
656
657 root_lock = qdisc_lock(oqdisc);
658 spin_lock_bh(root_lock);
659
660 /* Prune old scheduler */
661 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1)
662 qdisc_reset(oqdisc);
663
664 /* ... and graft new one */
665 if (qdisc == NULL)
666 qdisc = &noop_qdisc;
667 dev_queue->qdisc_sleeping = qdisc;
668 rcu_assign_pointer(dev_queue->qdisc, &noop_qdisc);
669
670 spin_unlock_bh(root_lock);
671
672 return oqdisc;
673}
John Fastabendb8970f02011-01-17 08:06:09 +0000674EXPORT_SYMBOL(dev_graft_qdisc);
Patrick McHardy589983c2009-09-04 06:41:20 +0000675
David S. Millere8a04642008-07-17 00:34:19 -0700676static void attach_one_default_qdisc(struct net_device *dev,
677 struct netdev_queue *dev_queue,
678 void *_unused)
679{
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000680 struct Qdisc *qdisc = &noqueue_qdisc;
David S. Millere8a04642008-07-17 00:34:19 -0700681
682 if (dev->tx_queue_len) {
Changli Gao3511c912010-10-16 13:04:08 +0000683 qdisc = qdisc_create_dflt(dev_queue,
David S. Millerd3678b42008-07-21 09:56:13 -0700684 &pfifo_fast_ops, TC_H_ROOT);
David S. Millere8a04642008-07-17 00:34:19 -0700685 if (!qdisc) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000686 netdev_info(dev, "activation failed\n");
David S. Millere8a04642008-07-17 00:34:19 -0700687 return;
688 }
Eric Dumazet1abbe132012-12-11 15:54:33 +0000689 if (!netif_is_multiqueue(dev))
690 qdisc->flags |= TCQ_F_ONETXQUEUE;
David S. Millere8a04642008-07-17 00:34:19 -0700691 }
692 dev_queue->qdisc_sleeping = qdisc;
693}
694
David S. Miller6ec1c692009-09-06 01:58:51 -0700695static void attach_default_qdiscs(struct net_device *dev)
696{
697 struct netdev_queue *txq;
698 struct Qdisc *qdisc;
699
700 txq = netdev_get_tx_queue(dev, 0);
701
702 if (!netif_is_multiqueue(dev) || dev->tx_queue_len == 0) {
703 netdev_for_each_tx_queue(dev, attach_one_default_qdisc, NULL);
704 dev->qdisc = txq->qdisc_sleeping;
705 atomic_inc(&dev->qdisc->refcnt);
706 } else {
Changli Gao3511c912010-10-16 13:04:08 +0000707 qdisc = qdisc_create_dflt(txq, &mq_qdisc_ops, TC_H_ROOT);
David S. Miller6ec1c692009-09-06 01:58:51 -0700708 if (qdisc) {
709 qdisc->ops->attach(qdisc);
710 dev->qdisc = qdisc;
711 }
712 }
713}
714
David S. Millere8a04642008-07-17 00:34:19 -0700715static void transition_one_qdisc(struct net_device *dev,
716 struct netdev_queue *dev_queue,
717 void *_need_watchdog)
718{
David S. Miller83874002008-07-17 00:53:03 -0700719 struct Qdisc *new_qdisc = dev_queue->qdisc_sleeping;
David S. Millere8a04642008-07-17 00:34:19 -0700720 int *need_watchdog_p = _need_watchdog;
721
David S. Millera9312ae2008-08-17 21:51:03 -0700722 if (!(new_qdisc->flags & TCQ_F_BUILTIN))
723 clear_bit(__QDISC_STATE_DEACTIVATED, &new_qdisc->state);
724
David S. Miller83874002008-07-17 00:53:03 -0700725 rcu_assign_pointer(dev_queue->qdisc, new_qdisc);
Eric Dumazet9d214932009-05-17 20:55:16 -0700726 if (need_watchdog_p && new_qdisc != &noqueue_qdisc) {
727 dev_queue->trans_start = 0;
David S. Millere8a04642008-07-17 00:34:19 -0700728 *need_watchdog_p = 1;
Eric Dumazet9d214932009-05-17 20:55:16 -0700729 }
David S. Millere8a04642008-07-17 00:34:19 -0700730}
731
Linus Torvalds1da177e2005-04-16 15:20:36 -0700732void dev_activate(struct net_device *dev)
733{
David S. Millere8a04642008-07-17 00:34:19 -0700734 int need_watchdog;
David S. Millerb0e1e642008-07-08 17:42:10 -0700735
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736 /* No queueing discipline is attached to device;
David S. Millerd3678b42008-07-21 09:56:13 -0700737 create default one i.e. pfifo_fast for devices,
738 which need queueing and noqueue_qdisc for
739 virtual interfaces
Linus Torvalds1da177e2005-04-16 15:20:36 -0700740 */
741
David S. Miller6ec1c692009-09-06 01:58:51 -0700742 if (dev->qdisc == &noop_qdisc)
743 attach_default_qdiscs(dev);
Patrick McHardyaf356af2009-09-04 06:41:18 +0000744
Tommy S. Christensencacaddf2005-05-03 16:18:52 -0700745 if (!netif_carrier_ok(dev))
746 /* Delay activation until next carrier-on event */
747 return;
748
David S. Millere8a04642008-07-17 00:34:19 -0700749 need_watchdog = 0;
750 netdev_for_each_tx_queue(dev, transition_one_qdisc, &need_watchdog);
Eric Dumazet24824a02010-10-02 06:11:55 +0000751 if (dev_ingress_queue(dev))
752 transition_one_qdisc(dev, dev_ingress_queue(dev), NULL);
David S. Millere8a04642008-07-17 00:34:19 -0700753
754 if (need_watchdog) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755 dev->trans_start = jiffies;
756 dev_watchdog_up(dev);
757 }
David S. Millerb0e1e642008-07-08 17:42:10 -0700758}
John Fastabendb8970f02011-01-17 08:06:09 +0000759EXPORT_SYMBOL(dev_activate);
David S. Millerb0e1e642008-07-08 17:42:10 -0700760
David S. Millere8a04642008-07-17 00:34:19 -0700761static void dev_deactivate_queue(struct net_device *dev,
762 struct netdev_queue *dev_queue,
763 void *_qdisc_default)
David S. Millerb0e1e642008-07-08 17:42:10 -0700764{
David S. Millere8a04642008-07-17 00:34:19 -0700765 struct Qdisc *qdisc_default = _qdisc_default;
David S. Miller970565b2008-07-08 23:10:33 -0700766 struct Qdisc *qdisc;
David S. Millerb0e1e642008-07-08 17:42:10 -0700767
David S. Miller970565b2008-07-08 23:10:33 -0700768 qdisc = dev_queue->qdisc;
David S. Millerb0e1e642008-07-08 17:42:10 -0700769 if (qdisc) {
David S. Miller83874002008-07-17 00:53:03 -0700770 spin_lock_bh(qdisc_lock(qdisc));
771
David S. Millera9312ae2008-08-17 21:51:03 -0700772 if (!(qdisc->flags & TCQ_F_BUILTIN))
773 set_bit(__QDISC_STATE_DEACTIVATED, &qdisc->state);
774
Jarek Poplawskif7a54c12008-08-27 02:22:07 -0700775 rcu_assign_pointer(dev_queue->qdisc, qdisc_default);
David S. Millerb0e1e642008-07-08 17:42:10 -0700776 qdisc_reset(qdisc);
David S. Millerd3b753d2008-07-15 20:14:35 -0700777
David S. Miller83874002008-07-17 00:53:03 -0700778 spin_unlock_bh(qdisc_lock(qdisc));
David S. Millerb0e1e642008-07-08 17:42:10 -0700779 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700780}
781
David S. Miller4335cd22008-08-17 21:58:07 -0700782static bool some_qdisc_is_busy(struct net_device *dev)
David S. Millere8a04642008-07-17 00:34:19 -0700783{
784 unsigned int i;
785
786 for (i = 0; i < dev->num_tx_queues; i++) {
787 struct netdev_queue *dev_queue;
David S. Miller7698b4f2008-07-16 01:42:40 -0700788 spinlock_t *root_lock;
David S. Millere2627c82008-07-16 00:56:32 -0700789 struct Qdisc *q;
David S. Millere8a04642008-07-17 00:34:19 -0700790 int val;
791
792 dev_queue = netdev_get_tx_queue(dev, i);
David S. Millerb9a3b112008-08-13 15:18:38 -0700793 q = dev_queue->qdisc_sleeping;
David S. Miller5fb66222008-08-02 20:02:43 -0700794 root_lock = qdisc_lock(q);
David S. Millere8a04642008-07-17 00:34:19 -0700795
David S. Miller4335cd22008-08-17 21:58:07 -0700796 spin_lock_bh(root_lock);
David S. Millere8a04642008-07-17 00:34:19 -0700797
Eric Dumazetbc135b22010-06-02 03:23:51 -0700798 val = (qdisc_is_running(q) ||
David S. Millerb9a3b112008-08-13 15:18:38 -0700799 test_bit(__QDISC_STATE_SCHED, &q->state));
David S. Millere8a04642008-07-17 00:34:19 -0700800
David S. Miller4335cd22008-08-17 21:58:07 -0700801 spin_unlock_bh(root_lock);
David S. Millere8a04642008-07-17 00:34:19 -0700802
803 if (val)
804 return true;
805 }
806 return false;
807}
808
Eric Dumazet31376632011-05-19 23:42:09 +0000809/**
810 * dev_deactivate_many - deactivate transmissions on several devices
811 * @head: list of devices to deactivate
812 *
813 * This function returns only when all outstanding transmissions
814 * have completed, unless all devices are in dismantle phase.
815 */
Octavian Purdila44345722010-12-13 12:44:07 +0000816void dev_deactivate_many(struct list_head *head)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700817{
Octavian Purdila44345722010-12-13 12:44:07 +0000818 struct net_device *dev;
Eric Dumazet31376632011-05-19 23:42:09 +0000819 bool sync_needed = false;
Herbert Xu41a23b02007-05-10 14:12:47 -0700820
Octavian Purdila44345722010-12-13 12:44:07 +0000821 list_for_each_entry(dev, head, unreg_list) {
822 netdev_for_each_tx_queue(dev, dev_deactivate_queue,
823 &noop_qdisc);
824 if (dev_ingress_queue(dev))
825 dev_deactivate_queue(dev, dev_ingress_queue(dev),
826 &noop_qdisc);
827
828 dev_watchdog_down(dev);
Eric Dumazet31376632011-05-19 23:42:09 +0000829 sync_needed |= !dev->dismantle;
Octavian Purdila44345722010-12-13 12:44:07 +0000830 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831
Eric Dumazet31376632011-05-19 23:42:09 +0000832 /* Wait for outstanding qdisc-less dev_queue_xmit calls.
833 * This is avoided if all devices are in dismantle phase :
834 * Caller will call synchronize_net() for us
835 */
836 if (sync_needed)
837 synchronize_net();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838
Herbert Xud4828d82006-06-22 02:28:18 -0700839 /* Wait for outstanding qdisc_run calls. */
Octavian Purdila44345722010-12-13 12:44:07 +0000840 list_for_each_entry(dev, head, unreg_list)
841 while (some_qdisc_is_busy(dev))
842 yield();
843}
844
845void dev_deactivate(struct net_device *dev)
846{
847 LIST_HEAD(single);
848
849 list_add(&dev->unreg_list, &single);
850 dev_deactivate_many(&single);
Eric W. Biederman5f04d502011-02-20 11:49:45 -0800851 list_del(&single);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852}
John Fastabendb8970f02011-01-17 08:06:09 +0000853EXPORT_SYMBOL(dev_deactivate);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700854
David S. Millerb0e1e642008-07-08 17:42:10 -0700855static void dev_init_scheduler_queue(struct net_device *dev,
856 struct netdev_queue *dev_queue,
David S. Millere8a04642008-07-17 00:34:19 -0700857 void *_qdisc)
David S. Millerb0e1e642008-07-08 17:42:10 -0700858{
David S. Millere8a04642008-07-17 00:34:19 -0700859 struct Qdisc *qdisc = _qdisc;
860
David S. Millerb0e1e642008-07-08 17:42:10 -0700861 dev_queue->qdisc = qdisc;
862 dev_queue->qdisc_sleeping = qdisc;
David S. Millerb0e1e642008-07-08 17:42:10 -0700863}
864
Linus Torvalds1da177e2005-04-16 15:20:36 -0700865void dev_init_scheduler(struct net_device *dev)
866{
Patrick McHardyaf356af2009-09-04 06:41:18 +0000867 dev->qdisc = &noop_qdisc;
David S. Millere8a04642008-07-17 00:34:19 -0700868 netdev_for_each_tx_queue(dev, dev_init_scheduler_queue, &noop_qdisc);
Eric Dumazet24824a02010-10-02 06:11:55 +0000869 if (dev_ingress_queue(dev))
870 dev_init_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871
Pavel Emelyanovb24b8a22008-01-23 21:20:07 -0800872 setup_timer(&dev->watchdog_timer, dev_watchdog, (unsigned long)dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700873}
874
David S. Millere8a04642008-07-17 00:34:19 -0700875static void shutdown_scheduler_queue(struct net_device *dev,
876 struct netdev_queue *dev_queue,
877 void *_qdisc_default)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700878{
David S. Millerb0e1e642008-07-08 17:42:10 -0700879 struct Qdisc *qdisc = dev_queue->qdisc_sleeping;
David S. Millere8a04642008-07-17 00:34:19 -0700880 struct Qdisc *qdisc_default = _qdisc_default;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881
David S. Millerb0e1e642008-07-08 17:42:10 -0700882 if (qdisc) {
Jarek Poplawskif7a54c12008-08-27 02:22:07 -0700883 rcu_assign_pointer(dev_queue->qdisc, qdisc_default);
David S. Millerb0e1e642008-07-08 17:42:10 -0700884 dev_queue->qdisc_sleeping = qdisc_default;
885
Linus Torvalds1da177e2005-04-16 15:20:36 -0700886 qdisc_destroy(qdisc);
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900887 }
David S. Millerb0e1e642008-07-08 17:42:10 -0700888}
889
890void dev_shutdown(struct net_device *dev)
891{
David S. Millere8a04642008-07-17 00:34:19 -0700892 netdev_for_each_tx_queue(dev, shutdown_scheduler_queue, &noop_qdisc);
Eric Dumazet24824a02010-10-02 06:11:55 +0000893 if (dev_ingress_queue(dev))
894 shutdown_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc);
Patrick McHardyaf356af2009-09-04 06:41:18 +0000895 qdisc_destroy(dev->qdisc);
896 dev->qdisc = &noop_qdisc;
897
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700898 WARN_ON(timer_pending(&dev->watchdog_timer));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899}
Jiri Pirko292f1c72013-02-12 00:12:03 +0000900
901void psched_ratecfg_precompute(struct psched_ratecfg *r, u32 rate)
902{
903 u64 factor;
904 u64 mult;
905 int shift;
906
907 r->rate_bps = rate << 3;
908 r->shift = 0;
909 r->mult = 1;
910 /*
911 * Calibrate mult, shift so that token counting is accurate
912 * for smallest packet size (64 bytes). Token (time in ns) is
913 * computed as (bytes * 8) * NSEC_PER_SEC / rate_bps. It will
914 * work as long as the smallest packet transfer time can be
915 * accurately represented in nanosec.
916 */
917 if (r->rate_bps > 0) {
918 /*
919 * Higher shift gives better accuracy. Find the largest
920 * shift such that mult fits in 32 bits.
921 */
922 for (shift = 0; shift < 16; shift++) {
923 r->shift = shift;
924 factor = 8LLU * NSEC_PER_SEC * (1 << r->shift);
925 mult = div64_u64(factor, r->rate_bps);
926 if (mult > UINT_MAX)
927 break;
928 }
929
930 r->shift = shift - 1;
931 factor = 8LLU * NSEC_PER_SEC * (1 << r->shift);
932 r->mult = div64_u64(factor, r->rate_bps);
933 }
934}
935EXPORT_SYMBOL(psched_ratecfg_precompute);