Branch data Line data Source code
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 <linux/bitops.h>
15 : : #include <linux/module.h>
16 : : #include <linux/types.h>
17 : : #include <linux/kernel.h>
18 : : #include <linux/sched.h>
19 : : #include <linux/string.h>
20 : : #include <linux/errno.h>
21 : : #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>
27 : : #include <linux/slab.h>
28 : : #include <linux/if_vlan.h>
29 : : #include <net/sch_generic.h>
30 : : #include <net/pkt_sched.h>
31 : : #include <net/dst.h>
32 : :
33 : : /* Qdisc to use by default */
34 : : const struct Qdisc_ops *default_qdisc_ops = &pfifo_fast_ops;
35 : : EXPORT_SYMBOL(default_qdisc_ops);
36 : :
37 : : /* Main transmission queue. */
38 : :
39 : : /* Modifications to data participating in scheduling must be protected with
40 : : * qdisc_lock(qdisc) spinlock.
41 : : *
42 : : * The idea is the following:
43 : : * - enqueue, dequeue are serialized via qdisc root lock
44 : : * - ingress filtering is also serialized via qdisc root lock
45 : : * - updates to tree and tree walking are only done under the rtnl mutex.
46 : : */
47 : :
48 : : static inline int dev_requeue_skb(struct sk_buff *skb, struct Qdisc *q)
49 : : {
50 : : skb_dst_force(skb);
51 : 0 : q->gso_skb = skb;
52 : 0 : q->qstats.requeues++;
53 : 0 : q->q.qlen++; /* it's still part of the queue */
54 : 0 : __netif_schedule(q);
55 : :
56 : : return 0;
57 : : }
58 : :
59 : : static inline struct sk_buff *dequeue_skb(struct Qdisc *q)
60 : : {
61 : 0 : struct sk_buff *skb = q->gso_skb;
62 : 0 : const struct netdev_queue *txq = q->dev_queue;
63 : :
64 [ # # ]: 0 : if (unlikely(skb)) {
65 : : /* check the reason of requeuing without tx lock first */
66 : 0 : txq = netdev_get_tx_queue(txq->dev, skb_get_queue_mapping(skb));
67 [ # # ]: 0 : if (!netif_xmit_frozen_or_stopped(txq)) {
68 : 0 : q->gso_skb = NULL;
69 : 0 : q->q.qlen--;
70 : : } else
71 : : skb = NULL;
72 : : } else {
73 [ # # ][ # # ]: 0 : if (!(q->flags & TCQ_F_ONETXQUEUE) || !netif_xmit_frozen_or_stopped(txq))
74 : 0 : skb = q->dequeue(q);
75 : : }
76 : :
77 : : return skb;
78 : : }
79 : :
80 : : static inline int handle_dev_cpu_collision(struct sk_buff *skb,
81 : : struct netdev_queue *dev_queue,
82 : 0 : struct Qdisc *q)
83 : : {
84 : : int ret;
85 : :
86 [ # # ]: 0 : if (unlikely(dev_queue->xmit_lock_owner == smp_processor_id())) {
87 : : /*
88 : : * Same CPU holding the lock. It may be a transient
89 : : * configuration error, when hard_start_xmit() recurses. We
90 : : * detect it by checking xmit owner and drop the packet when
91 : : * deadloop is detected. Return OK to try the next skb.
92 : : */
93 : 0 : kfree_skb(skb);
94 [ # # ]: 0 : net_warn_ratelimited("Dead loop on netdevice %s, fix it urgently!\n",
95 : : dev_queue->dev->name);
96 : : ret = qdisc_qlen(q);
97 : : } else {
98 : : /*
99 : : * Another cpu is holding lock, requeue & delay xmits for
100 : : * some time.
101 : : */
102 : 0 : __this_cpu_inc(softnet_data.cpu_collision);
103 : : ret = dev_requeue_skb(skb, q);
104 : : }
105 : :
106 : : return ret;
107 : : }
108 : :
109 : : /*
110 : : * Transmit one skb, and handle the return status as required. Holding the
111 : : * __QDISC_STATE_RUNNING bit guarantees that only one CPU can execute this
112 : : * function.
113 : : *
114 : : * Returns to the caller:
115 : : * 0 - queue is empty or throttled.
116 : : * >0 - queue is not empty.
117 : : */
118 : 0 : int sch_direct_xmit(struct sk_buff *skb, struct Qdisc *q,
119 : 23043 : struct net_device *dev, struct netdev_queue *txq,
120 : : spinlock_t *root_lock)
121 : : {
122 : : int ret = NETDEV_TX_BUSY;
123 : :
124 : : /* And release qdisc */
125 : : spin_unlock(root_lock);
126 : :
127 [ + - ]: 23043 : HARD_TX_LOCK(dev, txq, smp_processor_id());
128 [ + - ]: 23043 : if (!netif_xmit_frozen_or_stopped(txq))
129 : 23043 : ret = dev_hard_start_xmit(skb, dev, txq);
130 : :
131 [ + - ]: 23043 : HARD_TX_UNLOCK(dev, txq);
132 : :
133 : : spin_lock(root_lock);
134 : :
135 [ + - ]: 23043 : if (dev_xmit_complete(ret)) {
136 : : /* Driver sent out skb successfully or skb was consumed */
137 : : ret = qdisc_qlen(q);
138 [ # # ]: 0 : } else if (ret == NETDEV_TX_LOCKED) {
139 : : /* Driver try lock failed */
140 : : ret = handle_dev_cpu_collision(skb, txq, q);
141 : : } else {
142 : : /* Driver returned NETDEV_TX_BUSY - requeue skb */
143 [ # # ]: 0 : if (unlikely(ret != NETDEV_TX_BUSY))
144 [ # # ]: 0 : net_warn_ratelimited("BUG %s code %d qlen %d\n",
145 : : dev->name, ret, q->q.qlen);
146 : :
147 : : ret = dev_requeue_skb(skb, q);
148 : : }
149 : :
150 [ - + ][ # # ]: 23043 : if (ret && netif_xmit_frozen_or_stopped(txq))
151 : : ret = 0;
152 : :
153 : 23043 : return ret;
154 : : }
155 : :
156 : : /*
157 : : * NOTE: Called under qdisc_lock(q) with locally disabled BH.
158 : : *
159 : : * __QDISC_STATE_RUNNING guarantees only one CPU can process
160 : : * this qdisc at a time. qdisc_lock(q) serializes queue accesses for
161 : : * this queue.
162 : : *
163 : : * netif_tx_lock serializes accesses to device driver.
164 : : *
165 : : * qdisc_lock(q) and netif_tx_lock are mutually exclusive,
166 : : * if one is grabbed, another must be free.
167 : : *
168 : : * Note, that this procedure can be called by a watchdog timer
169 : : *
170 : : * Returns to the caller:
171 : : * 0 - queue is empty or throttled.
172 : : * >0 - queue is not empty.
173 : : *
174 : : */
175 : 0 : static inline int qdisc_restart(struct Qdisc *q)
176 : : {
177 : : struct netdev_queue *txq;
178 : 0 : struct net_device *dev;
179 : : spinlock_t *root_lock;
180 : 0 : struct sk_buff *skb;
181 : :
182 : : /* Dequeue packet */
183 : : skb = dequeue_skb(q);
184 [ # # ]: 0 : if (unlikely(!skb))
185 : : return 0;
186 [ # # ][ # # ]: 0 : WARN_ON_ONCE(skb_dst_is_noref(skb));
[ # # ]
187 : 0 : root_lock = qdisc_lock(q);
188 : : dev = qdisc_dev(q);
189 : 0 : txq = netdev_get_tx_queue(dev, skb_get_queue_mapping(skb));
190 : :
191 : 0 : return sch_direct_xmit(skb, q, dev, txq, root_lock);
192 : : }
193 : :
194 : 0 : void __qdisc_run(struct Qdisc *q)
195 : : {
196 : 0 : int quota = weight_p;
197 : :
198 [ # # ]: 0 : while (qdisc_restart(q)) {
199 : : /*
200 : : * Ordered by possible occurrence: Postpone processing if
201 : : * 1. we've exceeded packet quota
202 : : * 2. another process needs the CPU;
203 : : */
204 [ # # ][ # # ]: 0 : if (--quota <= 0 || need_resched()) {
205 : 0 : __netif_schedule(q);
206 : 0 : break;
207 : : }
208 : : }
209 : :
210 : : qdisc_run_end(q);
211 : 0 : }
212 : :
213 : 0 : unsigned long dev_trans_start(struct net_device *dev)
214 : : {
215 : : unsigned long val, res;
216 : : unsigned int i;
217 : :
218 [ # # ]: 0 : if (is_vlan_dev(dev))
219 : : dev = vlan_dev_real_dev(dev);
220 : 0 : res = dev->trans_start;
221 [ # # ]: 0 : for (i = 0; i < dev->num_tx_queues; i++) {
222 : 0 : val = netdev_get_tx_queue(dev, i)->trans_start;
223 [ # # ][ # # ]: 0 : if (val && time_after(val, res))
224 : : res = val;
225 : : }
226 : 0 : dev->trans_start = res;
227 : :
228 : 0 : return res;
229 : : }
230 : : EXPORT_SYMBOL(dev_trans_start);
231 : :
232 : 0 : static void dev_watchdog(unsigned long arg)
233 : : {
234 : 0 : struct net_device *dev = (struct net_device *)arg;
235 : :
236 : : netif_tx_lock(dev);
237 [ # # ]: 0 : if (!qdisc_tx_is_noop(dev)) {
238 [ # # ][ # # ]: 0 : if (netif_device_present(dev) &&
239 [ # # ]: 0 : netif_running(dev) &&
240 : : netif_carrier_ok(dev)) {
241 : : int some_queue_timedout = 0;
242 : : unsigned int i;
243 : : unsigned long trans_start;
244 : :
245 [ # # ]: 0 : for (i = 0; i < dev->num_tx_queues; i++) {
246 : 0 : struct netdev_queue *txq;
247 : :
248 : : txq = netdev_get_tx_queue(dev, i);
249 : : /*
250 : : * old device drivers set dev->trans_start
251 : : */
252 [ # # ]: 0 : trans_start = txq->trans_start ? : dev->trans_start;
253 [ # # ]: 0 : if (netif_xmit_stopped(txq) &&
254 [ # # ]: 0 : time_after(jiffies, (trans_start +
255 : : dev->watchdog_timeo))) {
256 : : some_queue_timedout = 1;
257 : 0 : txq->trans_timeout++;
258 : 0 : break;
259 : : }
260 : : }
261 : :
262 [ # # ]: 0 : if (some_queue_timedout) {
263 [ # # ][ # # ]: 0 : WARN_ONCE(1, KERN_INFO "NETDEV WATCHDOG: %s (%s): transmit queue %u timed out\n",
264 : : dev->name, netdev_drivername(dev), i);
265 : 0 : dev->netdev_ops->ndo_tx_timeout(dev);
266 : : }
267 [ # # ]: 0 : if (!mod_timer(&dev->watchdog_timer,
268 : : round_jiffies(jiffies +
269 : 0 : dev->watchdog_timeo)))
270 : : dev_hold(dev);
271 : : }
272 : : }
273 : : netif_tx_unlock(dev);
274 : :
275 : : dev_put(dev);
276 : 0 : }
277 : :
278 : 0 : void __netdev_watchdog_up(struct net_device *dev)
279 : : {
280 [ # # ]: 0 : if (dev->netdev_ops->ndo_tx_timeout) {
281 [ # # ]: 0 : if (dev->watchdog_timeo <= 0)
282 : 0 : dev->watchdog_timeo = 5*HZ;
283 [ # # ]: 0 : if (!mod_timer(&dev->watchdog_timer,
284 : 0 : round_jiffies(jiffies + dev->watchdog_timeo)))
285 : : dev_hold(dev);
286 : : }
287 : 0 : }
288 : :
289 : : static void dev_watchdog_up(struct net_device *dev)
290 : : {
291 : 0 : __netdev_watchdog_up(dev);
292 : : }
293 : :
294 : 0 : static void dev_watchdog_down(struct net_device *dev)
295 : : {
296 : : netif_tx_lock_bh(dev);
297 [ # # ]: 0 : if (del_timer(&dev->watchdog_timer))
298 : : dev_put(dev);
299 : : netif_tx_unlock_bh(dev);
300 : 0 : }
301 : :
302 : : /**
303 : : * netif_carrier_on - set carrier
304 : : * @dev: network device
305 : : *
306 : : * Device has detected that carrier.
307 : : */
308 : 0 : void netif_carrier_on(struct net_device *dev)
309 : : {
310 [ - + ]: 16467 : if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state)) {
311 [ # # ]: 0 : if (dev->reg_state == NETREG_UNINITIALIZED)
312 : 0 : return;
313 : 0 : linkwatch_fire_event(dev);
314 [ # # ]: 0 : if (netif_running(dev))
315 : 0 : __netdev_watchdog_up(dev);
316 : : }
317 : : }
318 : : EXPORT_SYMBOL(netif_carrier_on);
319 : :
320 : : /**
321 : : * netif_carrier_off - clear carrier
322 : : * @dev: network device
323 : : *
324 : : * Device has detected loss of carrier.
325 : : */
326 : 0 : void netif_carrier_off(struct net_device *dev)
327 : : {
328 [ # # ]: 0 : if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state)) {
329 [ # # ]: 0 : if (dev->reg_state == NETREG_UNINITIALIZED)
330 : 0 : return;
331 : 0 : linkwatch_fire_event(dev);
332 : : }
333 : : }
334 : : EXPORT_SYMBOL(netif_carrier_off);
335 : :
336 : : /* "NOOP" scheduler: the best scheduler, recommended for all interfaces
337 : : under all circumstances. It is difficult to invent anything faster or
338 : : cheaper.
339 : : */
340 : :
341 : 0 : static int noop_enqueue(struct sk_buff *skb, struct Qdisc *qdisc)
342 : : {
343 : 0 : kfree_skb(skb);
344 : 0 : return NET_XMIT_CN;
345 : : }
346 : :
347 : 0 : static struct sk_buff *noop_dequeue(struct Qdisc *qdisc)
348 : : {
349 : 0 : return NULL;
350 : : }
351 : :
352 : : struct Qdisc_ops noop_qdisc_ops __read_mostly = {
353 : : .id = "noop",
354 : : .priv_size = 0,
355 : : .enqueue = noop_enqueue,
356 : : .dequeue = noop_dequeue,
357 : : .peek = noop_dequeue,
358 : : .owner = THIS_MODULE,
359 : : };
360 : :
361 : : static struct netdev_queue noop_netdev_queue = {
362 : : .qdisc = &noop_qdisc,
363 : : .qdisc_sleeping = &noop_qdisc,
364 : : };
365 : :
366 : : struct Qdisc noop_qdisc = {
367 : : .enqueue = noop_enqueue,
368 : : .dequeue = noop_dequeue,
369 : : .flags = TCQ_F_BUILTIN,
370 : : .ops = &noop_qdisc_ops,
371 : : .list = LIST_HEAD_INIT(noop_qdisc.list),
372 : : .q.lock = __SPIN_LOCK_UNLOCKED(noop_qdisc.q.lock),
373 : : .dev_queue = &noop_netdev_queue,
374 : : .busylock = __SPIN_LOCK_UNLOCKED(noop_qdisc.busylock),
375 : : };
376 : : EXPORT_SYMBOL(noop_qdisc);
377 : :
378 : : static struct Qdisc_ops noqueue_qdisc_ops __read_mostly = {
379 : : .id = "noqueue",
380 : : .priv_size = 0,
381 : : .enqueue = noop_enqueue,
382 : : .dequeue = noop_dequeue,
383 : : .peek = noop_dequeue,
384 : : .owner = THIS_MODULE,
385 : : };
386 : :
387 : : static struct Qdisc noqueue_qdisc;
388 : : static struct netdev_queue noqueue_netdev_queue = {
389 : : .qdisc = &noqueue_qdisc,
390 : : .qdisc_sleeping = &noqueue_qdisc,
391 : : };
392 : :
393 : : static struct Qdisc noqueue_qdisc = {
394 : : .enqueue = NULL,
395 : : .dequeue = noop_dequeue,
396 : : .flags = TCQ_F_BUILTIN,
397 : : .ops = &noqueue_qdisc_ops,
398 : : .list = LIST_HEAD_INIT(noqueue_qdisc.list),
399 : : .q.lock = __SPIN_LOCK_UNLOCKED(noqueue_qdisc.q.lock),
400 : : .dev_queue = &noqueue_netdev_queue,
401 : : .busylock = __SPIN_LOCK_UNLOCKED(noqueue_qdisc.busylock),
402 : : };
403 : :
404 : :
405 : : static const u8 prio2band[TC_PRIO_MAX + 1] = {
406 : : 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
407 : : };
408 : :
409 : : /* 3-band FIFO queue: old style, but should be a bit faster than
410 : : generic prio+fifo combination.
411 : : */
412 : :
413 : : #define PFIFO_FAST_BANDS 3
414 : :
415 : : /*
416 : : * Private data for a pfifo_fast scheduler containing:
417 : : * - queues for the three band
418 : : * - bitmap indicating which of the bands contain skbs
419 : : */
420 : : struct pfifo_fast_priv {
421 : : u32 bitmap;
422 : : struct sk_buff_head q[PFIFO_FAST_BANDS];
423 : : };
424 : :
425 : : /*
426 : : * Convert a bitmap to the first band number where an skb is queued, where:
427 : : * bitmap=0 means there are no skbs on any band.
428 : : * bitmap=1 means there is an skb on band 0.
429 : : * bitmap=7 means there are skbs on all 3 bands, etc.
430 : : */
431 : : static const int bitmap2band[] = {-1, 0, 1, 0, 2, 0, 1, 0};
432 : :
433 : : static inline struct sk_buff_head *band2list(struct pfifo_fast_priv *priv,
434 : : int band)
435 : : {
436 : 0 : return priv->q + band;
437 : : }
438 : :
439 : 0 : static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc *qdisc)
440 : : {
441 [ # # ]: 0 : if (skb_queue_len(&qdisc->q) < qdisc_dev(qdisc)->tx_queue_len) {
442 : 0 : int band = prio2band[skb->priority & TC_PRIO_MAX];
443 : : struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
444 : 0 : struct sk_buff_head *list = band2list(priv, band);
445 : :
446 : 0 : priv->bitmap |= (1 << band);
447 : 0 : qdisc->q.qlen++;
448 : 0 : return __qdisc_enqueue_tail(skb, qdisc, list);
449 : : }
450 : :
451 : 0 : return qdisc_drop(skb, qdisc);
452 : : }
453 : :
454 : 0 : static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc)
455 : : {
456 : : struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
457 : 0 : int band = bitmap2band[priv->bitmap];
458 : :
459 [ # # ]: 0 : if (likely(band >= 0)) {
460 : 0 : struct sk_buff_head *list = band2list(priv, band);
461 : : struct sk_buff *skb = __qdisc_dequeue_head(qdisc, list);
462 : :
463 : 0 : qdisc->q.qlen--;
464 [ # # ]: 0 : if (skb_queue_empty(list))
465 : 0 : priv->bitmap &= ~(1 << band);
466 : :
467 : 0 : return skb;
468 : : }
469 : :
470 : : return NULL;
471 : : }
472 : :
473 : 0 : static struct sk_buff *pfifo_fast_peek(struct Qdisc *qdisc)
474 : : {
475 : : struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
476 : 0 : int band = bitmap2band[priv->bitmap];
477 : :
478 [ # # ]: 0 : if (band >= 0) {
479 : 0 : struct sk_buff_head *list = band2list(priv, band);
480 : :
481 : 0 : return skb_peek(list);
482 : : }
483 : :
484 : : return NULL;
485 : : }
486 : :
487 : 0 : static void pfifo_fast_reset(struct Qdisc *qdisc)
488 : : {
489 : : int prio;
490 : : struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
491 : :
492 [ # # ]: 0 : for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
493 : 0 : __qdisc_reset_queue(qdisc, band2list(priv, prio));
494 : :
495 : 0 : priv->bitmap = 0;
496 : 0 : qdisc->qstats.backlog = 0;
497 : 0 : qdisc->q.qlen = 0;
498 : 0 : }
499 : :
500 : 0 : static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
501 : : {
502 : 0 : struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS };
503 : :
504 : 0 : memcpy(&opt.priomap, prio2band, TC_PRIO_MAX + 1);
505 [ # # ]: 0 : if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
506 : : goto nla_put_failure;
507 : 0 : return skb->len;
508 : :
509 : : nla_put_failure:
510 : : return -1;
511 : : }
512 : :
513 : 0 : static int pfifo_fast_init(struct Qdisc *qdisc, struct nlattr *opt)
514 : : {
515 : : int prio;
516 : : struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
517 : :
518 [ # # ]: 0 : for (prio = 0; prio < PFIFO_FAST_BANDS; prio++)
519 : 0 : skb_queue_head_init(band2list(priv, prio));
520 : :
521 : : /* Can by-pass the queue discipline */
522 : 0 : qdisc->flags |= TCQ_F_CAN_BYPASS;
523 : 0 : return 0;
524 : : }
525 : :
526 : : struct Qdisc_ops pfifo_fast_ops __read_mostly = {
527 : : .id = "pfifo_fast",
528 : : .priv_size = sizeof(struct pfifo_fast_priv),
529 : : .enqueue = pfifo_fast_enqueue,
530 : : .dequeue = pfifo_fast_dequeue,
531 : : .peek = pfifo_fast_peek,
532 : : .init = pfifo_fast_init,
533 : : .reset = pfifo_fast_reset,
534 : : .dump = pfifo_fast_dump,
535 : : .owner = THIS_MODULE,
536 : : };
537 : :
538 : : static struct lock_class_key qdisc_tx_busylock;
539 : :
540 : 0 : struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
541 : : const struct Qdisc_ops *ops)
542 : : {
543 : : void *p;
544 : : struct Qdisc *sch;
545 : 0 : unsigned int size = QDISC_ALIGN(sizeof(*sch)) + ops->priv_size;
546 : : int err = -ENOBUFS;
547 : 0 : struct net_device *dev = dev_queue->dev;
548 : :
549 : : p = kzalloc_node(size, GFP_KERNEL,
550 : : netdev_queue_numa_node_read(dev_queue));
551 : :
552 [ # # ]: 0 : if (!p)
553 : : goto errout;
554 : 0 : sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
555 : : /* if we got non aligned memory, ask more and do alignment ourself */
556 [ # # ]: 0 : if (sch != p) {
557 : 0 : kfree(p);
558 : 0 : p = kzalloc_node(size + QDISC_ALIGNTO - 1, GFP_KERNEL,
559 : : netdev_queue_numa_node_read(dev_queue));
560 [ # # ]: 0 : if (!p)
561 : : goto errout;
562 : 0 : sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
563 : 0 : sch->padded = (char *) sch - (char *) p;
564 : : }
565 : 0 : INIT_LIST_HEAD(&sch->list);
566 : 0 : skb_queue_head_init(&sch->q);
567 : :
568 : 0 : spin_lock_init(&sch->busylock);
569 : : lockdep_set_class(&sch->busylock,
570 : : dev->qdisc_tx_busylock ?: &qdisc_tx_busylock);
571 : :
572 : 0 : sch->ops = ops;
573 : 0 : sch->enqueue = ops->enqueue;
574 : 0 : sch->dequeue = ops->dequeue;
575 : 0 : sch->dev_queue = dev_queue;
576 : : dev_hold(dev);
577 : 0 : atomic_set(&sch->refcnt, 1);
578 : :
579 : 0 : return sch;
580 : : errout:
581 : : return ERR_PTR(err);
582 : : }
583 : :
584 : 0 : struct Qdisc *qdisc_create_dflt(struct netdev_queue *dev_queue,
585 : : const struct Qdisc_ops *ops,
586 : : unsigned int parentid)
587 : : {
588 : : struct Qdisc *sch;
589 : :
590 [ # # ]: 0 : if (!try_module_get(ops->owner))
591 : : goto errout;
592 : :
593 : 0 : sch = qdisc_alloc(dev_queue, ops);
594 [ # # ]: 0 : if (IS_ERR(sch))
595 : : goto errout;
596 : 0 : sch->parent = parentid;
597 : :
598 [ # # ][ # # ]: 0 : if (!ops->init || ops->init(sch, NULL) == 0)
599 : 0 : return sch;
600 : :
601 : 0 : qdisc_destroy(sch);
602 : : errout:
603 : : return NULL;
604 : : }
605 : : EXPORT_SYMBOL(qdisc_create_dflt);
606 : :
607 : : /* Under qdisc_lock(qdisc) and BH! */
608 : :
609 : 0 : void qdisc_reset(struct Qdisc *qdisc)
610 : : {
611 : 0 : const struct Qdisc_ops *ops = qdisc->ops;
612 : :
613 [ # # ]: 0 : if (ops->reset)
614 : 0 : ops->reset(qdisc);
615 : :
616 [ # # ]: 0 : if (qdisc->gso_skb) {
617 : 0 : kfree_skb(qdisc->gso_skb);
618 : 0 : qdisc->gso_skb = NULL;
619 : 0 : qdisc->q.qlen = 0;
620 : : }
621 : 0 : }
622 : : EXPORT_SYMBOL(qdisc_reset);
623 : :
624 : 0 : static void qdisc_rcu_free(struct rcu_head *head)
625 : : {
626 : 0 : struct Qdisc *qdisc = container_of(head, struct Qdisc, rcu_head);
627 : :
628 : 0 : kfree((char *) qdisc - qdisc->padded);
629 : 0 : }
630 : :
631 : 0 : void qdisc_destroy(struct Qdisc *qdisc)
632 : : {
633 : 0 : const struct Qdisc_ops *ops = qdisc->ops;
634 : :
635 [ # # # # ]: 0 : if (qdisc->flags & TCQ_F_BUILTIN ||
636 : 0 : !atomic_dec_and_test(&qdisc->refcnt))
637 : 0 : return;
638 : :
639 : : #ifdef CONFIG_NET_SCHED
640 : : qdisc_list_del(qdisc);
641 : :
642 : : qdisc_put_stab(rtnl_dereference(qdisc->stab));
643 : : #endif
644 : 0 : gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est);
645 [ # # ]: 0 : if (ops->reset)
646 : 0 : ops->reset(qdisc);
647 [ # # ]: 0 : if (ops->destroy)
648 : 0 : ops->destroy(qdisc);
649 : :
650 : 0 : module_put(ops->owner);
651 : : dev_put(qdisc_dev(qdisc));
652 : :
653 : 0 : kfree_skb(qdisc->gso_skb);
654 : : /*
655 : : * gen_estimator est_timer() might access qdisc->q.lock,
656 : : * wait a RCU grace period before freeing qdisc.
657 : : */
658 : 0 : call_rcu(&qdisc->rcu_head, qdisc_rcu_free);
659 : : }
660 : : EXPORT_SYMBOL(qdisc_destroy);
661 : :
662 : : /* Attach toplevel qdisc to device queue. */
663 : 0 : struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
664 : : struct Qdisc *qdisc)
665 : : {
666 : 0 : struct Qdisc *oqdisc = dev_queue->qdisc_sleeping;
667 : : spinlock_t *root_lock;
668 : :
669 : : root_lock = qdisc_lock(oqdisc);
670 : : spin_lock_bh(root_lock);
671 : :
672 : : /* Prune old scheduler */
673 [ # # ][ # # ]: 0 : if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1)
674 : 0 : qdisc_reset(oqdisc);
675 : :
676 : : /* ... and graft new one */
677 [ # # ]: 0 : if (qdisc == NULL)
678 : : qdisc = &noop_qdisc;
679 : 0 : dev_queue->qdisc_sleeping = qdisc;
680 : 0 : rcu_assign_pointer(dev_queue->qdisc, &noop_qdisc);
681 : :
682 : : spin_unlock_bh(root_lock);
683 : :
684 : 0 : return oqdisc;
685 : : }
686 : : EXPORT_SYMBOL(dev_graft_qdisc);
687 : :
688 : 0 : static void attach_one_default_qdisc(struct net_device *dev,
689 : : struct netdev_queue *dev_queue,
690 : : void *_unused)
691 : : {
692 : : struct Qdisc *qdisc = &noqueue_qdisc;
693 : :
694 [ # # ]: 0 : if (dev->tx_queue_len) {
695 : 0 : qdisc = qdisc_create_dflt(dev_queue,
696 : : default_qdisc_ops, TC_H_ROOT);
697 [ # # ]: 0 : if (!qdisc) {
698 : 0 : netdev_info(dev, "activation failed\n");
699 : 0 : return;
700 : : }
701 [ # # ]: 0 : if (!netif_is_multiqueue(dev))
702 : 0 : qdisc->flags |= TCQ_F_ONETXQUEUE;
703 : : }
704 : 0 : dev_queue->qdisc_sleeping = qdisc;
705 : : }
706 : :
707 : 0 : static void attach_default_qdiscs(struct net_device *dev)
708 : : {
709 : : struct netdev_queue *txq;
710 : : struct Qdisc *qdisc;
711 : :
712 : : txq = netdev_get_tx_queue(dev, 0);
713 : :
714 [ # # ][ # # ]: 0 : if (!netif_is_multiqueue(dev) || dev->tx_queue_len == 0) {
715 : : netdev_for_each_tx_queue(dev, attach_one_default_qdisc, NULL);
716 : 0 : dev->qdisc = txq->qdisc_sleeping;
717 : 0 : atomic_inc(&dev->qdisc->refcnt);
718 : : } else {
719 : 0 : qdisc = qdisc_create_dflt(txq, &mq_qdisc_ops, TC_H_ROOT);
720 [ # # ]: 0 : if (qdisc) {
721 : 0 : dev->qdisc = qdisc;
722 : 0 : qdisc->ops->attach(qdisc);
723 : : }
724 : : }
725 : 0 : }
726 : :
727 : 0 : static void transition_one_qdisc(struct net_device *dev,
728 : : struct netdev_queue *dev_queue,
729 : : void *_need_watchdog)
730 : : {
731 : 0 : struct Qdisc *new_qdisc = dev_queue->qdisc_sleeping;
732 : : int *need_watchdog_p = _need_watchdog;
733 : :
734 [ # # ]: 0 : if (!(new_qdisc->flags & TCQ_F_BUILTIN))
735 : 0 : clear_bit(__QDISC_STATE_DEACTIVATED, &new_qdisc->state);
736 : :
737 : 0 : rcu_assign_pointer(dev_queue->qdisc, new_qdisc);
738 [ # # ][ # # ]: 0 : if (need_watchdog_p && new_qdisc != &noqueue_qdisc) {
739 : 0 : dev_queue->trans_start = 0;
740 : 0 : *need_watchdog_p = 1;
741 : : }
742 : 0 : }
743 : :
744 : 0 : void dev_activate(struct net_device *dev)
745 : : {
746 : : int need_watchdog;
747 : :
748 : : /* No queueing discipline is attached to device;
749 : : * create default one for devices, which need queueing
750 : : * and noqueue_qdisc for virtual interfaces
751 : : */
752 : :
753 [ # # ]: 0 : if (dev->qdisc == &noop_qdisc)
754 : 0 : attach_default_qdiscs(dev);
755 : :
756 [ # # ]: 0 : if (!netif_carrier_ok(dev))
757 : : /* Delay activation until next carrier-on event */
758 : 0 : return;
759 : :
760 : 0 : need_watchdog = 0;
761 : : netdev_for_each_tx_queue(dev, transition_one_qdisc, &need_watchdog);
762 [ # # ]: 0 : if (dev_ingress_queue(dev))
763 : 0 : transition_one_qdisc(dev, dev_ingress_queue(dev), NULL);
764 : :
765 [ # # ]: 0 : if (need_watchdog) {
766 : 0 : dev->trans_start = jiffies;
767 : : dev_watchdog_up(dev);
768 : : }
769 : : }
770 : : EXPORT_SYMBOL(dev_activate);
771 : :
772 : 0 : static void dev_deactivate_queue(struct net_device *dev,
773 : : struct netdev_queue *dev_queue,
774 : : void *_qdisc_default)
775 : : {
776 : : struct Qdisc *qdisc_default = _qdisc_default;
777 : : struct Qdisc *qdisc;
778 : :
779 : 0 : qdisc = dev_queue->qdisc;
780 [ # # ]: 0 : if (qdisc) {
781 : : spin_lock_bh(qdisc_lock(qdisc));
782 : :
783 [ # # ]: 0 : if (!(qdisc->flags & TCQ_F_BUILTIN))
784 : 0 : set_bit(__QDISC_STATE_DEACTIVATED, &qdisc->state);
785 : :
786 : 0 : rcu_assign_pointer(dev_queue->qdisc, qdisc_default);
787 : 0 : qdisc_reset(qdisc);
788 : :
789 : : spin_unlock_bh(qdisc_lock(qdisc));
790 : : }
791 : 0 : }
792 : :
793 : 0 : static bool some_qdisc_is_busy(struct net_device *dev)
794 : : {
795 : : unsigned int i;
796 : :
797 [ # # ]: 0 : for (i = 0; i < dev->num_tx_queues; i++) {
798 : : struct netdev_queue *dev_queue;
799 : : spinlock_t *root_lock;
800 : 0 : struct Qdisc *q;
801 : : int val;
802 : :
803 : : dev_queue = netdev_get_tx_queue(dev, i);
804 : 0 : q = dev_queue->qdisc_sleeping;
805 : : root_lock = qdisc_lock(q);
806 : :
807 : : spin_lock_bh(root_lock);
808 : :
809 [ # # ][ # # ]: 0 : val = (qdisc_is_running(q) ||
810 : : test_bit(__QDISC_STATE_SCHED, &q->state));
811 : :
812 : : spin_unlock_bh(root_lock);
813 : :
814 [ # # ]: 0 : if (val)
815 : : return true;
816 : : }
817 : : return false;
818 : : }
819 : :
820 : : /**
821 : : * dev_deactivate_many - deactivate transmissions on several devices
822 : : * @head: list of devices to deactivate
823 : : *
824 : : * This function returns only when all outstanding transmissions
825 : : * have completed, unless all devices are in dismantle phase.
826 : : */
827 : 0 : void dev_deactivate_many(struct list_head *head)
828 : : {
829 : 0 : struct net_device *dev;
830 : : bool sync_needed = false;
831 : :
832 [ # # ]: 0 : list_for_each_entry(dev, head, close_list) {
833 : : netdev_for_each_tx_queue(dev, dev_deactivate_queue,
834 : : &noop_qdisc);
835 [ # # ]: 0 : if (dev_ingress_queue(dev))
836 : 0 : dev_deactivate_queue(dev, dev_ingress_queue(dev),
837 : : &noop_qdisc);
838 : :
839 : 0 : dev_watchdog_down(dev);
840 : 0 : sync_needed |= !dev->dismantle;
841 : : }
842 : :
843 : : /* Wait for outstanding qdisc-less dev_queue_xmit calls.
844 : : * This is avoided if all devices are in dismantle phase :
845 : : * Caller will call synchronize_net() for us
846 : : */
847 [ # # ]: 0 : if (sync_needed)
848 : 0 : synchronize_net();
849 : :
850 : : /* Wait for outstanding qdisc_run calls. */
851 [ # # ]: 0 : list_for_each_entry(dev, head, close_list)
852 [ # # ]: 0 : while (some_qdisc_is_busy(dev))
853 : 0 : yield();
854 : 0 : }
855 : :
856 : 0 : void dev_deactivate(struct net_device *dev)
857 : : {
858 : 0 : LIST_HEAD(single);
859 : :
860 : 0 : list_add(&dev->close_list, &single);
861 : 0 : dev_deactivate_many(&single);
862 : : list_del(&single);
863 : 0 : }
864 : : EXPORT_SYMBOL(dev_deactivate);
865 : :
866 : 0 : static void dev_init_scheduler_queue(struct net_device *dev,
867 : : struct netdev_queue *dev_queue,
868 : : void *_qdisc)
869 : : {
870 : : struct Qdisc *qdisc = _qdisc;
871 : :
872 : 0 : dev_queue->qdisc = qdisc;
873 : 0 : dev_queue->qdisc_sleeping = qdisc;
874 : 0 : }
875 : :
876 : 0 : void dev_init_scheduler(struct net_device *dev)
877 : : {
878 : 0 : dev->qdisc = &noop_qdisc;
879 : : netdev_for_each_tx_queue(dev, dev_init_scheduler_queue, &noop_qdisc);
880 [ # # ]: 0 : if (dev_ingress_queue(dev))
881 : : dev_init_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc);
882 : :
883 : 0 : setup_timer(&dev->watchdog_timer, dev_watchdog, (unsigned long)dev);
884 : 0 : }
885 : :
886 : 0 : static void shutdown_scheduler_queue(struct net_device *dev,
887 : : struct netdev_queue *dev_queue,
888 : : void *_qdisc_default)
889 : : {
890 : 0 : struct Qdisc *qdisc = dev_queue->qdisc_sleeping;
891 : : struct Qdisc *qdisc_default = _qdisc_default;
892 : :
893 [ # # ][ # # ]: 0 : if (qdisc) {
894 : 0 : rcu_assign_pointer(dev_queue->qdisc, qdisc_default);
895 : 0 : dev_queue->qdisc_sleeping = qdisc_default;
896 : :
897 : 0 : qdisc_destroy(qdisc);
898 : : }
899 : 0 : }
900 : :
901 : 0 : void dev_shutdown(struct net_device *dev)
902 : : {
903 : : netdev_for_each_tx_queue(dev, shutdown_scheduler_queue, &noop_qdisc);
904 [ # # ]: 0 : if (dev_ingress_queue(dev))
905 : : shutdown_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc);
906 : 0 : qdisc_destroy(dev->qdisc);
907 : 0 : dev->qdisc = &noop_qdisc;
908 : :
909 [ # # ]: 0 : WARN_ON(timer_pending(&dev->watchdog_timer));
910 : 0 : }
911 : :
912 : 0 : void psched_ratecfg_precompute(struct psched_ratecfg *r,
913 : : const struct tc_ratespec *conf,
914 : : u64 rate64)
915 : : {
916 : 0 : memset(r, 0, sizeof(*r));
917 : 0 : r->overhead = conf->overhead;
918 : 0 : r->rate_bytes_ps = max_t(u64, conf->rate, rate64);
919 : 0 : r->linklayer = (conf->linklayer & TC_LINKLAYER_MASK);
920 : 0 : r->mult = 1;
921 : : /*
922 : : * The deal here is to replace a divide by a reciprocal one
923 : : * in fast path (a reciprocal divide is a multiply and a shift)
924 : : *
925 : : * Normal formula would be :
926 : : * time_in_ns = (NSEC_PER_SEC * len) / rate_bps
927 : : *
928 : : * We compute mult/shift to use instead :
929 : : * time_in_ns = (len * mult) >> shift;
930 : : *
931 : : * We try to get the highest possible mult value for accuracy,
932 : : * but have to make sure no overflows will ever happen.
933 : : */
934 [ # # ]: 0 : if (r->rate_bytes_ps > 0) {
935 : : u64 factor = NSEC_PER_SEC;
936 : :
937 : : for (;;) {
938 : 0 : r->mult = div64_u64(factor, r->rate_bytes_ps);
939 [ # # ][ # # ]: 0 : if (r->mult & (1U << 31) || factor & (1ULL << 63))
940 : : break;
941 : 0 : factor <<= 1;
942 : 0 : r->shift++;
943 : 0 : }
944 : : }
945 : 0 : }
946 : : EXPORT_SYMBOL(psched_ratecfg_precompute);
|
