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