1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * net/sched/sch_generic.c Generic packet scheduler routines.
5 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
6 * Jamal Hadi Salim, <hadi@cyberus.ca> 990601
10 #include <linux/bitops.h>
11 #include <linux/module.h>
12 #include <linux/types.h>
13 #include <linux/kernel.h>
14 #include <linux/sched.h>
15 #include <linux/string.h>
16 #include <linux/errno.h>
17 #include <linux/netdevice.h>
18 #include <linux/skbuff.h>
19 #include <linux/rtnetlink.h>
20 #include <linux/init.h>
21 #include <linux/rcupdate.h>
22 #include <linux/list.h>
23 #include <linux/slab.h>
24 #include <linux/if_vlan.h>
25 #include <linux/skb_array.h>
26 #include <linux/if_macvlan.h>
27 #include <net/sch_generic.h>
28 #include <net/pkt_sched.h>
30 #include <trace/events/qdisc.h>
31 #include <trace/events/net.h>
34 /* Qdisc to use by default */
35 const struct Qdisc_ops
*default_qdisc_ops
= &pfifo_fast_ops
;
36 EXPORT_SYMBOL(default_qdisc_ops
);
38 static void qdisc_maybe_clear_missed(struct Qdisc
*q
,
39 const struct netdev_queue
*txq
)
41 clear_bit(__QDISC_STATE_MISSED
, &q
->state
);
43 /* Make sure the below netif_xmit_frozen_or_stopped()
44 * checking happens after clearing STATE_MISSED.
46 smp_mb__after_atomic();
48 /* Checking netif_xmit_frozen_or_stopped() again to
49 * make sure STATE_MISSED is set if the STATE_MISSED
50 * set by netif_tx_wake_queue()'s rescheduling of
51 * net_tx_action() is cleared by the above clear_bit().
53 if (!netif_xmit_frozen_or_stopped(txq
))
54 set_bit(__QDISC_STATE_MISSED
, &q
->state
);
56 set_bit(__QDISC_STATE_DRAINING
, &q
->state
);
59 /* Main transmission queue. */
61 /* Modifications to data participating in scheduling must be protected with
62 * qdisc_lock(qdisc) spinlock.
64 * The idea is the following:
65 * - enqueue, dequeue are serialized via qdisc root lock
66 * - ingress filtering is also serialized via qdisc root lock
67 * - updates to tree and tree walking are only done under the rtnl mutex.
70 #define SKB_XOFF_MAGIC ((struct sk_buff *)1UL)
72 static inline struct sk_buff
*__skb_dequeue_bad_txq(struct Qdisc
*q
)
74 const struct netdev_queue
*txq
= q
->dev_queue
;
75 spinlock_t
*lock
= NULL
;
78 if (q
->flags
& TCQ_F_NOLOCK
) {
83 skb
= skb_peek(&q
->skb_bad_txq
);
85 /* check the reason of requeuing without tx lock first */
86 txq
= skb_get_tx_queue(txq
->dev
, skb
);
87 if (!netif_xmit_frozen_or_stopped(txq
)) {
88 skb
= __skb_dequeue(&q
->skb_bad_txq
);
89 if (qdisc_is_percpu_stats(q
)) {
90 qdisc_qstats_cpu_backlog_dec(q
, skb
);
91 qdisc_qstats_cpu_qlen_dec(q
);
93 qdisc_qstats_backlog_dec(q
, skb
);
98 qdisc_maybe_clear_missed(q
, txq
);
108 static inline struct sk_buff
*qdisc_dequeue_skb_bad_txq(struct Qdisc
*q
)
110 struct sk_buff
*skb
= skb_peek(&q
->skb_bad_txq
);
113 skb
= __skb_dequeue_bad_txq(q
);
118 static inline void qdisc_enqueue_skb_bad_txq(struct Qdisc
*q
,
121 spinlock_t
*lock
= NULL
;
123 if (q
->flags
& TCQ_F_NOLOCK
) {
124 lock
= qdisc_lock(q
);
128 __skb_queue_tail(&q
->skb_bad_txq
, skb
);
130 if (qdisc_is_percpu_stats(q
)) {
131 qdisc_qstats_cpu_backlog_inc(q
, skb
);
132 qdisc_qstats_cpu_qlen_inc(q
);
134 qdisc_qstats_backlog_inc(q
, skb
);
142 static inline void dev_requeue_skb(struct sk_buff
*skb
, struct Qdisc
*q
)
144 spinlock_t
*lock
= NULL
;
146 if (q
->flags
& TCQ_F_NOLOCK
) {
147 lock
= qdisc_lock(q
);
152 struct sk_buff
*next
= skb
->next
;
154 __skb_queue_tail(&q
->gso_skb
, skb
);
156 /* it's still part of the queue */
157 if (qdisc_is_percpu_stats(q
)) {
158 qdisc_qstats_cpu_requeues_inc(q
);
159 qdisc_qstats_cpu_backlog_inc(q
, skb
);
160 qdisc_qstats_cpu_qlen_inc(q
);
162 q
->qstats
.requeues
++;
163 qdisc_qstats_backlog_inc(q
, skb
);
172 set_bit(__QDISC_STATE_MISSED
, &q
->state
);
178 static void try_bulk_dequeue_skb(struct Qdisc
*q
,
180 const struct netdev_queue
*txq
,
183 int bytelimit
= qdisc_avail_bulklimit(txq
) - skb
->len
;
185 while (bytelimit
> 0) {
186 struct sk_buff
*nskb
= q
->dequeue(q
);
191 bytelimit
-= nskb
->len
; /* covers GSO len */
194 (*packets
)++; /* GSO counts as one pkt */
196 skb_mark_not_on_list(skb
);
199 /* This variant of try_bulk_dequeue_skb() makes sure
200 * all skbs in the chain are for the same txq
202 static void try_bulk_dequeue_skb_slow(struct Qdisc
*q
,
206 int mapping
= skb_get_queue_mapping(skb
);
207 struct sk_buff
*nskb
;
211 nskb
= q
->dequeue(q
);
214 if (unlikely(skb_get_queue_mapping(nskb
) != mapping
)) {
215 qdisc_enqueue_skb_bad_txq(q
, nskb
);
222 skb_mark_not_on_list(skb
);
225 /* Note that dequeue_skb can possibly return a SKB list (via skb->next).
226 * A requeued skb (via q->gso_skb) can also be a SKB list.
228 static struct sk_buff
*dequeue_skb(struct Qdisc
*q
, bool *validate
,
231 const struct netdev_queue
*txq
= q
->dev_queue
;
232 struct sk_buff
*skb
= NULL
;
235 if (unlikely(!skb_queue_empty(&q
->gso_skb
))) {
236 spinlock_t
*lock
= NULL
;
238 if (q
->flags
& TCQ_F_NOLOCK
) {
239 lock
= qdisc_lock(q
);
243 skb
= skb_peek(&q
->gso_skb
);
245 /* skb may be null if another cpu pulls gso_skb off in between
246 * empty check and lock.
254 /* skb in gso_skb were already validated */
256 if (xfrm_offload(skb
))
258 /* check the reason of requeuing without tx lock first */
259 txq
= skb_get_tx_queue(txq
->dev
, skb
);
260 if (!netif_xmit_frozen_or_stopped(txq
)) {
261 skb
= __skb_dequeue(&q
->gso_skb
);
262 if (qdisc_is_percpu_stats(q
)) {
263 qdisc_qstats_cpu_backlog_dec(q
, skb
);
264 qdisc_qstats_cpu_qlen_dec(q
);
266 qdisc_qstats_backlog_dec(q
, skb
);
271 qdisc_maybe_clear_missed(q
, txq
);
280 if ((q
->flags
& TCQ_F_ONETXQUEUE
) &&
281 netif_xmit_frozen_or_stopped(txq
)) {
282 qdisc_maybe_clear_missed(q
, txq
);
286 skb
= qdisc_dequeue_skb_bad_txq(q
);
288 if (skb
== SKB_XOFF_MAGIC
)
295 if (qdisc_may_bulk(q
))
296 try_bulk_dequeue_skb(q
, skb
, txq
, packets
);
298 try_bulk_dequeue_skb_slow(q
, skb
, packets
);
301 trace_qdisc_dequeue(q
, txq
, *packets
, skb
);
306 * Transmit possibly several skbs, and handle the return status as
307 * required. Owning running seqcount bit guarantees that
308 * only one CPU can execute this function.
310 * Returns to the caller:
311 * false - hardware queue frozen backoff
312 * true - feel free to send more pkts
314 bool sch_direct_xmit(struct sk_buff
*skb
, struct Qdisc
*q
,
315 struct net_device
*dev
, struct netdev_queue
*txq
,
316 spinlock_t
*root_lock
, bool validate
)
318 int ret
= NETDEV_TX_BUSY
;
321 /* And release qdisc */
323 spin_unlock(root_lock
);
325 /* Note that we validate skb (GSO, checksum, ...) outside of locks */
327 skb
= validate_xmit_skb_list(skb
, dev
, &again
);
329 #ifdef CONFIG_XFRM_OFFLOAD
330 if (unlikely(again
)) {
332 spin_lock(root_lock
);
334 dev_requeue_skb(skb
, q
);
340 HARD_TX_LOCK(dev
, txq
, smp_processor_id());
341 if (!netif_xmit_frozen_or_stopped(txq
))
342 skb
= dev_hard_start_xmit(skb
, dev
, txq
, &ret
);
344 qdisc_maybe_clear_missed(q
, txq
);
346 HARD_TX_UNLOCK(dev
, txq
);
349 spin_lock(root_lock
);
354 spin_lock(root_lock
);
356 if (!dev_xmit_complete(ret
)) {
357 /* Driver returned NETDEV_TX_BUSY - requeue skb */
358 if (unlikely(ret
!= NETDEV_TX_BUSY
))
359 net_warn_ratelimited("BUG %s code %d qlen %d\n",
360 dev
->name
, ret
, q
->q
.qlen
);
362 dev_requeue_skb(skb
, q
);
370 * NOTE: Called under qdisc_lock(q) with locally disabled BH.
372 * running seqcount guarantees only one CPU can process
373 * this qdisc at a time. qdisc_lock(q) serializes queue accesses for
376 * netif_tx_lock serializes accesses to device driver.
378 * qdisc_lock(q) and netif_tx_lock are mutually exclusive,
379 * if one is grabbed, another must be free.
381 * Note, that this procedure can be called by a watchdog timer
383 * Returns to the caller:
384 * 0 - queue is empty or throttled.
385 * >0 - queue is not empty.
388 static inline bool qdisc_restart(struct Qdisc
*q
, int *packets
)
390 spinlock_t
*root_lock
= NULL
;
391 struct netdev_queue
*txq
;
392 struct net_device
*dev
;
397 skb
= dequeue_skb(q
, &validate
, packets
);
401 if (!(q
->flags
& TCQ_F_NOLOCK
))
402 root_lock
= qdisc_lock(q
);
405 txq
= skb_get_tx_queue(dev
, skb
);
407 return sch_direct_xmit(skb
, q
, dev
, txq
, root_lock
, validate
);
410 void __qdisc_run(struct Qdisc
*q
)
412 int quota
= dev_tx_weight
;
415 while (qdisc_restart(q
, &packets
)) {
418 if (q
->flags
& TCQ_F_NOLOCK
)
419 set_bit(__QDISC_STATE_MISSED
, &q
->state
);
428 unsigned long dev_trans_start(struct net_device
*dev
)
430 unsigned long val
, res
;
433 if (is_vlan_dev(dev
))
434 dev
= vlan_dev_real_dev(dev
);
435 else if (netif_is_macvlan(dev
))
436 dev
= macvlan_dev_real_dev(dev
);
437 res
= netdev_get_tx_queue(dev
, 0)->trans_start
;
438 for (i
= 1; i
< dev
->num_tx_queues
; i
++) {
439 val
= netdev_get_tx_queue(dev
, i
)->trans_start
;
440 if (val
&& time_after(val
, res
))
446 EXPORT_SYMBOL(dev_trans_start
);
448 static void dev_watchdog(struct timer_list
*t
)
450 struct net_device
*dev
= from_timer(dev
, t
, watchdog_timer
);
453 if (!qdisc_tx_is_noop(dev
)) {
454 if (netif_device_present(dev
) &&
455 netif_running(dev
) &&
456 netif_carrier_ok(dev
)) {
457 int some_queue_timedout
= 0;
459 unsigned long trans_start
;
461 for (i
= 0; i
< dev
->num_tx_queues
; i
++) {
462 struct netdev_queue
*txq
;
464 txq
= netdev_get_tx_queue(dev
, i
);
465 trans_start
= txq
->trans_start
;
466 if (netif_xmit_stopped(txq
) &&
467 time_after(jiffies
, (trans_start
+
468 dev
->watchdog_timeo
))) {
469 some_queue_timedout
= 1;
470 txq
->trans_timeout
++;
475 if (some_queue_timedout
) {
476 trace_net_dev_xmit_timeout(dev
, i
);
477 WARN_ONCE(1, KERN_INFO
"NETDEV WATCHDOG: %s (%s): transmit queue %u timed out\n",
478 dev
->name
, netdev_drivername(dev
), i
);
479 dev
->netdev_ops
->ndo_tx_timeout(dev
, i
);
481 if (!mod_timer(&dev
->watchdog_timer
,
482 round_jiffies(jiffies
+
483 dev
->watchdog_timeo
)))
487 netif_tx_unlock(dev
);
492 void __netdev_watchdog_up(struct net_device
*dev
)
494 if (dev
->netdev_ops
->ndo_tx_timeout
) {
495 if (dev
->watchdog_timeo
<= 0)
496 dev
->watchdog_timeo
= 5*HZ
;
497 if (!mod_timer(&dev
->watchdog_timer
,
498 round_jiffies(jiffies
+ dev
->watchdog_timeo
)))
502 EXPORT_SYMBOL_GPL(__netdev_watchdog_up
);
504 static void dev_watchdog_up(struct net_device
*dev
)
506 __netdev_watchdog_up(dev
);
509 static void dev_watchdog_down(struct net_device
*dev
)
511 netif_tx_lock_bh(dev
);
512 if (del_timer(&dev
->watchdog_timer
))
514 netif_tx_unlock_bh(dev
);
518 * netif_carrier_on - set carrier
519 * @dev: network device
521 * Device has detected acquisition of carrier.
523 void netif_carrier_on(struct net_device
*dev
)
525 if (test_and_clear_bit(__LINK_STATE_NOCARRIER
, &dev
->state
)) {
526 if (dev
->reg_state
== NETREG_UNINITIALIZED
)
528 atomic_inc(&dev
->carrier_up_count
);
529 linkwatch_fire_event(dev
);
530 if (netif_running(dev
))
531 __netdev_watchdog_up(dev
);
534 EXPORT_SYMBOL(netif_carrier_on
);
537 * netif_carrier_off - clear carrier
538 * @dev: network device
540 * Device has detected loss of carrier.
542 void netif_carrier_off(struct net_device
*dev
)
544 if (!test_and_set_bit(__LINK_STATE_NOCARRIER
, &dev
->state
)) {
545 if (dev
->reg_state
== NETREG_UNINITIALIZED
)
547 atomic_inc(&dev
->carrier_down_count
);
548 linkwatch_fire_event(dev
);
551 EXPORT_SYMBOL(netif_carrier_off
);
554 * netif_carrier_event - report carrier state event
555 * @dev: network device
557 * Device has detected a carrier event but the carrier state wasn't changed.
558 * Use in drivers when querying carrier state asynchronously, to avoid missing
559 * events (link flaps) if link recovers before it's queried.
561 void netif_carrier_event(struct net_device
*dev
)
563 if (dev
->reg_state
== NETREG_UNINITIALIZED
)
565 atomic_inc(&dev
->carrier_up_count
);
566 atomic_inc(&dev
->carrier_down_count
);
567 linkwatch_fire_event(dev
);
569 EXPORT_SYMBOL_GPL(netif_carrier_event
);
571 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces
572 under all circumstances. It is difficult to invent anything faster or
576 static int noop_enqueue(struct sk_buff
*skb
, struct Qdisc
*qdisc
,
577 struct sk_buff
**to_free
)
579 __qdisc_drop(skb
, to_free
);
583 static struct sk_buff
*noop_dequeue(struct Qdisc
*qdisc
)
588 struct Qdisc_ops noop_qdisc_ops __read_mostly
= {
591 .enqueue
= noop_enqueue
,
592 .dequeue
= noop_dequeue
,
593 .peek
= noop_dequeue
,
594 .owner
= THIS_MODULE
,
597 static struct netdev_queue noop_netdev_queue
= {
598 RCU_POINTER_INITIALIZER(qdisc
, &noop_qdisc
),
599 .qdisc_sleeping
= &noop_qdisc
,
602 struct Qdisc noop_qdisc
= {
603 .enqueue
= noop_enqueue
,
604 .dequeue
= noop_dequeue
,
605 .flags
= TCQ_F_BUILTIN
,
606 .ops
= &noop_qdisc_ops
,
607 .q
.lock
= __SPIN_LOCK_UNLOCKED(noop_qdisc
.q
.lock
),
608 .dev_queue
= &noop_netdev_queue
,
609 .running
= SEQCNT_ZERO(noop_qdisc
.running
),
610 .busylock
= __SPIN_LOCK_UNLOCKED(noop_qdisc
.busylock
),
612 .next
= (struct sk_buff
*)&noop_qdisc
.gso_skb
,
613 .prev
= (struct sk_buff
*)&noop_qdisc
.gso_skb
,
615 .lock
= __SPIN_LOCK_UNLOCKED(noop_qdisc
.gso_skb
.lock
),
618 .next
= (struct sk_buff
*)&noop_qdisc
.skb_bad_txq
,
619 .prev
= (struct sk_buff
*)&noop_qdisc
.skb_bad_txq
,
621 .lock
= __SPIN_LOCK_UNLOCKED(noop_qdisc
.skb_bad_txq
.lock
),
624 EXPORT_SYMBOL(noop_qdisc
);
626 static int noqueue_init(struct Qdisc
*qdisc
, struct nlattr
*opt
,
627 struct netlink_ext_ack
*extack
)
629 /* register_qdisc() assigns a default of noop_enqueue if unset,
630 * but __dev_queue_xmit() treats noqueue only as such
631 * if this is NULL - so clear it here. */
632 qdisc
->enqueue
= NULL
;
636 struct Qdisc_ops noqueue_qdisc_ops __read_mostly
= {
639 .init
= noqueue_init
,
640 .enqueue
= noop_enqueue
,
641 .dequeue
= noop_dequeue
,
642 .peek
= noop_dequeue
,
643 .owner
= THIS_MODULE
,
646 static const u8 prio2band
[TC_PRIO_MAX
+ 1] = {
647 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
650 /* 3-band FIFO queue: old style, but should be a bit faster than
651 generic prio+fifo combination.
654 #define PFIFO_FAST_BANDS 3
657 * Private data for a pfifo_fast scheduler containing:
658 * - rings for priority bands
660 struct pfifo_fast_priv
{
661 struct skb_array q
[PFIFO_FAST_BANDS
];
664 static inline struct skb_array
*band2list(struct pfifo_fast_priv
*priv
,
667 return &priv
->q
[band
];
670 static int pfifo_fast_enqueue(struct sk_buff
*skb
, struct Qdisc
*qdisc
,
671 struct sk_buff
**to_free
)
673 int band
= prio2band
[skb
->priority
& TC_PRIO_MAX
];
674 struct pfifo_fast_priv
*priv
= qdisc_priv(qdisc
);
675 struct skb_array
*q
= band2list(priv
, band
);
676 unsigned int pkt_len
= qdisc_pkt_len(skb
);
679 err
= skb_array_produce(q
, skb
);
682 if (qdisc_is_percpu_stats(qdisc
))
683 return qdisc_drop_cpu(skb
, qdisc
, to_free
);
685 return qdisc_drop(skb
, qdisc
, to_free
);
688 qdisc_update_stats_at_enqueue(qdisc
, pkt_len
);
689 return NET_XMIT_SUCCESS
;
692 static struct sk_buff
*pfifo_fast_dequeue(struct Qdisc
*qdisc
)
694 struct pfifo_fast_priv
*priv
= qdisc_priv(qdisc
);
695 struct sk_buff
*skb
= NULL
;
696 bool need_retry
= true;
700 for (band
= 0; band
< PFIFO_FAST_BANDS
&& !skb
; band
++) {
701 struct skb_array
*q
= band2list(priv
, band
);
703 if (__skb_array_empty(q
))
706 skb
= __skb_array_consume(q
);
709 qdisc_update_stats_at_dequeue(qdisc
, skb
);
710 } else if (need_retry
&&
711 READ_ONCE(qdisc
->state
) & QDISC_STATE_NON_EMPTY
) {
712 /* Delay clearing the STATE_MISSED here to reduce
713 * the overhead of the second spin_trylock() in
714 * qdisc_run_begin() and __netif_schedule() calling
715 * in qdisc_run_end().
717 clear_bit(__QDISC_STATE_MISSED
, &qdisc
->state
);
718 clear_bit(__QDISC_STATE_DRAINING
, &qdisc
->state
);
720 /* Make sure dequeuing happens after clearing
723 smp_mb__after_atomic();
733 static struct sk_buff
*pfifo_fast_peek(struct Qdisc
*qdisc
)
735 struct pfifo_fast_priv
*priv
= qdisc_priv(qdisc
);
736 struct sk_buff
*skb
= NULL
;
739 for (band
= 0; band
< PFIFO_FAST_BANDS
&& !skb
; band
++) {
740 struct skb_array
*q
= band2list(priv
, band
);
742 skb
= __skb_array_peek(q
);
748 static void pfifo_fast_reset(struct Qdisc
*qdisc
)
751 struct pfifo_fast_priv
*priv
= qdisc_priv(qdisc
);
753 for (band
= 0; band
< PFIFO_FAST_BANDS
; band
++) {
754 struct skb_array
*q
= band2list(priv
, band
);
757 /* NULL ring is possible if destroy path is due to a failed
758 * skb_array_init() in pfifo_fast_init() case.
763 while ((skb
= __skb_array_consume(q
)) != NULL
)
767 if (qdisc_is_percpu_stats(qdisc
)) {
768 for_each_possible_cpu(i
) {
769 struct gnet_stats_queue
*q
;
771 q
= per_cpu_ptr(qdisc
->cpu_qstats
, i
);
778 static int pfifo_fast_dump(struct Qdisc
*qdisc
, struct sk_buff
*skb
)
780 struct tc_prio_qopt opt
= { .bands
= PFIFO_FAST_BANDS
};
782 memcpy(&opt
.priomap
, prio2band
, TC_PRIO_MAX
+ 1);
783 if (nla_put(skb
, TCA_OPTIONS
, sizeof(opt
), &opt
))
784 goto nla_put_failure
;
791 static int pfifo_fast_init(struct Qdisc
*qdisc
, struct nlattr
*opt
,
792 struct netlink_ext_ack
*extack
)
794 unsigned int qlen
= qdisc_dev(qdisc
)->tx_queue_len
;
795 struct pfifo_fast_priv
*priv
= qdisc_priv(qdisc
);
798 /* guard against zero length rings */
802 for (prio
= 0; prio
< PFIFO_FAST_BANDS
; prio
++) {
803 struct skb_array
*q
= band2list(priv
, prio
);
806 err
= skb_array_init(q
, qlen
, GFP_KERNEL
);
811 /* Can by-pass the queue discipline */
812 qdisc
->flags
|= TCQ_F_CAN_BYPASS
;
816 static void pfifo_fast_destroy(struct Qdisc
*sch
)
818 struct pfifo_fast_priv
*priv
= qdisc_priv(sch
);
821 for (prio
= 0; prio
< PFIFO_FAST_BANDS
; prio
++) {
822 struct skb_array
*q
= band2list(priv
, prio
);
824 /* NULL ring is possible if destroy path is due to a failed
825 * skb_array_init() in pfifo_fast_init() case.
829 /* Destroy ring but no need to kfree_skb because a call to
830 * pfifo_fast_reset() has already done that work.
832 ptr_ring_cleanup(&q
->ring
, NULL
);
836 static int pfifo_fast_change_tx_queue_len(struct Qdisc
*sch
,
837 unsigned int new_len
)
839 struct pfifo_fast_priv
*priv
= qdisc_priv(sch
);
840 struct skb_array
*bands
[PFIFO_FAST_BANDS
];
843 for (prio
= 0; prio
< PFIFO_FAST_BANDS
; prio
++) {
844 struct skb_array
*q
= band2list(priv
, prio
);
849 return skb_array_resize_multiple(bands
, PFIFO_FAST_BANDS
, new_len
,
853 struct Qdisc_ops pfifo_fast_ops __read_mostly
= {
855 .priv_size
= sizeof(struct pfifo_fast_priv
),
856 .enqueue
= pfifo_fast_enqueue
,
857 .dequeue
= pfifo_fast_dequeue
,
858 .peek
= pfifo_fast_peek
,
859 .init
= pfifo_fast_init
,
860 .destroy
= pfifo_fast_destroy
,
861 .reset
= pfifo_fast_reset
,
862 .dump
= pfifo_fast_dump
,
863 .change_tx_queue_len
= pfifo_fast_change_tx_queue_len
,
864 .owner
= THIS_MODULE
,
865 .static_flags
= TCQ_F_NOLOCK
| TCQ_F_CPUSTATS
,
867 EXPORT_SYMBOL(pfifo_fast_ops
);
869 static struct lock_class_key qdisc_tx_busylock
;
870 static struct lock_class_key qdisc_running_key
;
872 struct Qdisc
*qdisc_alloc(struct netdev_queue
*dev_queue
,
873 const struct Qdisc_ops
*ops
,
874 struct netlink_ext_ack
*extack
)
877 unsigned int size
= sizeof(*sch
) + ops
->priv_size
;
879 struct net_device
*dev
;
882 NL_SET_ERR_MSG(extack
, "No device queue given");
887 dev
= dev_queue
->dev
;
888 sch
= kzalloc_node(size
, GFP_KERNEL
, netdev_queue_numa_node_read(dev_queue
));
892 __skb_queue_head_init(&sch
->gso_skb
);
893 __skb_queue_head_init(&sch
->skb_bad_txq
);
894 qdisc_skb_head_init(&sch
->q
);
895 spin_lock_init(&sch
->q
.lock
);
897 if (ops
->static_flags
& TCQ_F_CPUSTATS
) {
899 netdev_alloc_pcpu_stats(struct gnet_stats_basic_cpu
);
900 if (!sch
->cpu_bstats
)
903 sch
->cpu_qstats
= alloc_percpu(struct gnet_stats_queue
);
904 if (!sch
->cpu_qstats
) {
905 free_percpu(sch
->cpu_bstats
);
910 spin_lock_init(&sch
->busylock
);
911 lockdep_set_class(&sch
->busylock
,
912 dev
->qdisc_tx_busylock
?: &qdisc_tx_busylock
);
914 /* seqlock has the same scope of busylock, for NOLOCK qdisc */
915 spin_lock_init(&sch
->seqlock
);
916 lockdep_set_class(&sch
->seqlock
,
917 dev
->qdisc_tx_busylock
?: &qdisc_tx_busylock
);
919 seqcount_init(&sch
->running
);
920 lockdep_set_class(&sch
->running
,
921 dev
->qdisc_running_key
?: &qdisc_running_key
);
924 sch
->flags
= ops
->static_flags
;
925 sch
->enqueue
= ops
->enqueue
;
926 sch
->dequeue
= ops
->dequeue
;
927 sch
->dev_queue
= dev_queue
;
929 refcount_set(&sch
->refcnt
, 1);
938 struct Qdisc
*qdisc_create_dflt(struct netdev_queue
*dev_queue
,
939 const struct Qdisc_ops
*ops
,
940 unsigned int parentid
,
941 struct netlink_ext_ack
*extack
)
945 if (!try_module_get(ops
->owner
)) {
946 NL_SET_ERR_MSG(extack
, "Failed to increase module reference counter");
950 sch
= qdisc_alloc(dev_queue
, ops
, extack
);
952 module_put(ops
->owner
);
955 sch
->parent
= parentid
;
957 if (!ops
->init
|| ops
->init(sch
, NULL
, extack
) == 0) {
958 trace_qdisc_create(ops
, dev_queue
->dev
, parentid
);
965 EXPORT_SYMBOL(qdisc_create_dflt
);
967 /* Under qdisc_lock(qdisc) and BH! */
969 void qdisc_reset(struct Qdisc
*qdisc
)
971 const struct Qdisc_ops
*ops
= qdisc
->ops
;
972 struct sk_buff
*skb
, *tmp
;
974 trace_qdisc_reset(qdisc
);
979 skb_queue_walk_safe(&qdisc
->gso_skb
, skb
, tmp
) {
980 __skb_unlink(skb
, &qdisc
->gso_skb
);
984 skb_queue_walk_safe(&qdisc
->skb_bad_txq
, skb
, tmp
) {
985 __skb_unlink(skb
, &qdisc
->skb_bad_txq
);
990 qdisc
->qstats
.backlog
= 0;
992 EXPORT_SYMBOL(qdisc_reset
);
994 void qdisc_free(struct Qdisc
*qdisc
)
996 if (qdisc_is_percpu_stats(qdisc
)) {
997 free_percpu(qdisc
->cpu_bstats
);
998 free_percpu(qdisc
->cpu_qstats
);
1004 static void qdisc_free_cb(struct rcu_head
*head
)
1006 struct Qdisc
*q
= container_of(head
, struct Qdisc
, rcu
);
1011 static void qdisc_destroy(struct Qdisc
*qdisc
)
1013 const struct Qdisc_ops
*ops
= qdisc
->ops
;
1015 #ifdef CONFIG_NET_SCHED
1016 qdisc_hash_del(qdisc
);
1018 qdisc_put_stab(rtnl_dereference(qdisc
->stab
));
1020 gen_kill_estimator(&qdisc
->rate_est
);
1025 ops
->destroy(qdisc
);
1027 module_put(ops
->owner
);
1028 dev_put(qdisc_dev(qdisc
));
1030 trace_qdisc_destroy(qdisc
);
1032 call_rcu(&qdisc
->rcu
, qdisc_free_cb
);
1035 void qdisc_put(struct Qdisc
*qdisc
)
1040 if (qdisc
->flags
& TCQ_F_BUILTIN
||
1041 !refcount_dec_and_test(&qdisc
->refcnt
))
1044 qdisc_destroy(qdisc
);
1046 EXPORT_SYMBOL(qdisc_put
);
1048 /* Version of qdisc_put() that is called with rtnl mutex unlocked.
1049 * Intended to be used as optimization, this function only takes rtnl lock if
1050 * qdisc reference counter reached zero.
1053 void qdisc_put_unlocked(struct Qdisc
*qdisc
)
1055 if (qdisc
->flags
& TCQ_F_BUILTIN
||
1056 !refcount_dec_and_rtnl_lock(&qdisc
->refcnt
))
1059 qdisc_destroy(qdisc
);
1062 EXPORT_SYMBOL(qdisc_put_unlocked
);
1064 /* Attach toplevel qdisc to device queue. */
1065 struct Qdisc
*dev_graft_qdisc(struct netdev_queue
*dev_queue
,
1066 struct Qdisc
*qdisc
)
1068 struct Qdisc
*oqdisc
= dev_queue
->qdisc_sleeping
;
1069 spinlock_t
*root_lock
;
1071 root_lock
= qdisc_lock(oqdisc
);
1072 spin_lock_bh(root_lock
);
1074 /* ... and graft new one */
1076 qdisc
= &noop_qdisc
;
1077 dev_queue
->qdisc_sleeping
= qdisc
;
1078 rcu_assign_pointer(dev_queue
->qdisc
, &noop_qdisc
);
1080 spin_unlock_bh(root_lock
);
1084 EXPORT_SYMBOL(dev_graft_qdisc
);
1086 static void attach_one_default_qdisc(struct net_device
*dev
,
1087 struct netdev_queue
*dev_queue
,
1090 struct Qdisc
*qdisc
;
1091 const struct Qdisc_ops
*ops
= default_qdisc_ops
;
1093 if (dev
->priv_flags
& IFF_NO_QUEUE
)
1094 ops
= &noqueue_qdisc_ops
;
1095 else if(dev
->type
== ARPHRD_CAN
)
1096 ops
= &pfifo_fast_ops
;
1098 qdisc
= qdisc_create_dflt(dev_queue
, ops
, TC_H_ROOT
, NULL
);
1102 if (!netif_is_multiqueue(dev
))
1103 qdisc
->flags
|= TCQ_F_ONETXQUEUE
| TCQ_F_NOPARENT
;
1104 dev_queue
->qdisc_sleeping
= qdisc
;
1107 static void attach_default_qdiscs(struct net_device
*dev
)
1109 struct netdev_queue
*txq
;
1110 struct Qdisc
*qdisc
;
1112 txq
= netdev_get_tx_queue(dev
, 0);
1114 if (!netif_is_multiqueue(dev
) ||
1115 dev
->priv_flags
& IFF_NO_QUEUE
) {
1116 netdev_for_each_tx_queue(dev
, attach_one_default_qdisc
, NULL
);
1117 qdisc
= txq
->qdisc_sleeping
;
1118 rcu_assign_pointer(dev
->qdisc
, qdisc
);
1119 qdisc_refcount_inc(qdisc
);
1121 qdisc
= qdisc_create_dflt(txq
, &mq_qdisc_ops
, TC_H_ROOT
, NULL
);
1123 rcu_assign_pointer(dev
->qdisc
, qdisc
);
1124 qdisc
->ops
->attach(qdisc
);
1127 qdisc
= rtnl_dereference(dev
->qdisc
);
1129 /* Detect default qdisc setup/init failed and fallback to "noqueue" */
1130 if (qdisc
== &noop_qdisc
) {
1131 netdev_warn(dev
, "default qdisc (%s) fail, fallback to %s\n",
1132 default_qdisc_ops
->id
, noqueue_qdisc_ops
.id
);
1133 dev
->priv_flags
|= IFF_NO_QUEUE
;
1134 netdev_for_each_tx_queue(dev
, attach_one_default_qdisc
, NULL
);
1135 qdisc
= txq
->qdisc_sleeping
;
1136 rcu_assign_pointer(dev
->qdisc
, qdisc
);
1137 qdisc_refcount_inc(qdisc
);
1138 dev
->priv_flags
^= IFF_NO_QUEUE
;
1141 #ifdef CONFIG_NET_SCHED
1142 if (qdisc
!= &noop_qdisc
)
1143 qdisc_hash_add(qdisc
, false);
1147 static void transition_one_qdisc(struct net_device
*dev
,
1148 struct netdev_queue
*dev_queue
,
1149 void *_need_watchdog
)
1151 struct Qdisc
*new_qdisc
= dev_queue
->qdisc_sleeping
;
1152 int *need_watchdog_p
= _need_watchdog
;
1154 if (!(new_qdisc
->flags
& TCQ_F_BUILTIN
))
1155 clear_bit(__QDISC_STATE_DEACTIVATED
, &new_qdisc
->state
);
1157 rcu_assign_pointer(dev_queue
->qdisc
, new_qdisc
);
1158 if (need_watchdog_p
) {
1159 dev_queue
->trans_start
= 0;
1160 *need_watchdog_p
= 1;
1164 void dev_activate(struct net_device
*dev
)
1168 /* No queueing discipline is attached to device;
1169 * create default one for devices, which need queueing
1170 * and noqueue_qdisc for virtual interfaces
1173 if (rtnl_dereference(dev
->qdisc
) == &noop_qdisc
)
1174 attach_default_qdiscs(dev
);
1176 if (!netif_carrier_ok(dev
))
1177 /* Delay activation until next carrier-on event */
1181 netdev_for_each_tx_queue(dev
, transition_one_qdisc
, &need_watchdog
);
1182 if (dev_ingress_queue(dev
))
1183 transition_one_qdisc(dev
, dev_ingress_queue(dev
), NULL
);
1185 if (need_watchdog
) {
1186 netif_trans_update(dev
);
1187 dev_watchdog_up(dev
);
1190 EXPORT_SYMBOL(dev_activate
);
1192 static void qdisc_deactivate(struct Qdisc
*qdisc
)
1194 if (qdisc
->flags
& TCQ_F_BUILTIN
)
1197 set_bit(__QDISC_STATE_DEACTIVATED
, &qdisc
->state
);
1200 static void dev_deactivate_queue(struct net_device
*dev
,
1201 struct netdev_queue
*dev_queue
,
1202 void *_qdisc_default
)
1204 struct Qdisc
*qdisc_default
= _qdisc_default
;
1205 struct Qdisc
*qdisc
;
1207 qdisc
= rtnl_dereference(dev_queue
->qdisc
);
1209 qdisc_deactivate(qdisc
);
1210 rcu_assign_pointer(dev_queue
->qdisc
, qdisc_default
);
1214 static void dev_reset_queue(struct net_device
*dev
,
1215 struct netdev_queue
*dev_queue
,
1218 struct Qdisc
*qdisc
;
1221 qdisc
= dev_queue
->qdisc_sleeping
;
1225 nolock
= qdisc
->flags
& TCQ_F_NOLOCK
;
1228 spin_lock_bh(&qdisc
->seqlock
);
1229 spin_lock_bh(qdisc_lock(qdisc
));
1233 spin_unlock_bh(qdisc_lock(qdisc
));
1235 clear_bit(__QDISC_STATE_MISSED
, &qdisc
->state
);
1236 clear_bit(__QDISC_STATE_DRAINING
, &qdisc
->state
);
1237 spin_unlock_bh(&qdisc
->seqlock
);
1241 static bool some_qdisc_is_busy(struct net_device
*dev
)
1245 for (i
= 0; i
< dev
->num_tx_queues
; i
++) {
1246 struct netdev_queue
*dev_queue
;
1247 spinlock_t
*root_lock
;
1251 dev_queue
= netdev_get_tx_queue(dev
, i
);
1252 q
= dev_queue
->qdisc_sleeping
;
1254 root_lock
= qdisc_lock(q
);
1255 spin_lock_bh(root_lock
);
1257 val
= (qdisc_is_running(q
) ||
1258 test_bit(__QDISC_STATE_SCHED
, &q
->state
));
1260 spin_unlock_bh(root_lock
);
1269 * dev_deactivate_many - deactivate transmissions on several devices
1270 * @head: list of devices to deactivate
1272 * This function returns only when all outstanding transmissions
1273 * have completed, unless all devices are in dismantle phase.
1275 void dev_deactivate_many(struct list_head
*head
)
1277 struct net_device
*dev
;
1279 list_for_each_entry(dev
, head
, close_list
) {
1280 netdev_for_each_tx_queue(dev
, dev_deactivate_queue
,
1282 if (dev_ingress_queue(dev
))
1283 dev_deactivate_queue(dev
, dev_ingress_queue(dev
),
1286 dev_watchdog_down(dev
);
1289 /* Wait for outstanding qdisc-less dev_queue_xmit calls or
1290 * outstanding qdisc enqueuing calls.
1291 * This is avoided if all devices are in dismantle phase :
1292 * Caller will call synchronize_net() for us
1296 list_for_each_entry(dev
, head
, close_list
) {
1297 netdev_for_each_tx_queue(dev
, dev_reset_queue
, NULL
);
1299 if (dev_ingress_queue(dev
))
1300 dev_reset_queue(dev
, dev_ingress_queue(dev
), NULL
);
1303 /* Wait for outstanding qdisc_run calls. */
1304 list_for_each_entry(dev
, head
, close_list
) {
1305 while (some_qdisc_is_busy(dev
)) {
1306 /* wait_event() would avoid this sleep-loop but would
1307 * require expensive checks in the fast paths of packet
1308 * processing which isn't worth it.
1310 schedule_timeout_uninterruptible(1);
1315 void dev_deactivate(struct net_device
*dev
)
1319 list_add(&dev
->close_list
, &single
);
1320 dev_deactivate_many(&single
);
1323 EXPORT_SYMBOL(dev_deactivate
);
1325 static int qdisc_change_tx_queue_len(struct net_device
*dev
,
1326 struct netdev_queue
*dev_queue
)
1328 struct Qdisc
*qdisc
= dev_queue
->qdisc_sleeping
;
1329 const struct Qdisc_ops
*ops
= qdisc
->ops
;
1331 if (ops
->change_tx_queue_len
)
1332 return ops
->change_tx_queue_len(qdisc
, dev
->tx_queue_len
);
1336 void dev_qdisc_change_real_num_tx(struct net_device
*dev
,
1337 unsigned int new_real_tx
)
1339 struct Qdisc
*qdisc
= rtnl_dereference(dev
->qdisc
);
1341 if (qdisc
->ops
->change_real_num_tx
)
1342 qdisc
->ops
->change_real_num_tx(qdisc
, new_real_tx
);
1345 int dev_qdisc_change_tx_queue_len(struct net_device
*dev
)
1347 bool up
= dev
->flags
& IFF_UP
;
1352 dev_deactivate(dev
);
1354 for (i
= 0; i
< dev
->num_tx_queues
; i
++) {
1355 ret
= qdisc_change_tx_queue_len(dev
, &dev
->_tx
[i
]);
1357 /* TODO: revert changes on a partial failure */
1367 static void dev_init_scheduler_queue(struct net_device
*dev
,
1368 struct netdev_queue
*dev_queue
,
1371 struct Qdisc
*qdisc
= _qdisc
;
1373 rcu_assign_pointer(dev_queue
->qdisc
, qdisc
);
1374 dev_queue
->qdisc_sleeping
= qdisc
;
1377 void dev_init_scheduler(struct net_device
*dev
)
1379 rcu_assign_pointer(dev
->qdisc
, &noop_qdisc
);
1380 netdev_for_each_tx_queue(dev
, dev_init_scheduler_queue
, &noop_qdisc
);
1381 if (dev_ingress_queue(dev
))
1382 dev_init_scheduler_queue(dev
, dev_ingress_queue(dev
), &noop_qdisc
);
1384 timer_setup(&dev
->watchdog_timer
, dev_watchdog
, 0);
1387 static void shutdown_scheduler_queue(struct net_device
*dev
,
1388 struct netdev_queue
*dev_queue
,
1389 void *_qdisc_default
)
1391 struct Qdisc
*qdisc
= dev_queue
->qdisc_sleeping
;
1392 struct Qdisc
*qdisc_default
= _qdisc_default
;
1395 rcu_assign_pointer(dev_queue
->qdisc
, qdisc_default
);
1396 dev_queue
->qdisc_sleeping
= qdisc_default
;
1402 void dev_shutdown(struct net_device
*dev
)
1404 netdev_for_each_tx_queue(dev
, shutdown_scheduler_queue
, &noop_qdisc
);
1405 if (dev_ingress_queue(dev
))
1406 shutdown_scheduler_queue(dev
, dev_ingress_queue(dev
), &noop_qdisc
);
1407 qdisc_put(rtnl_dereference(dev
->qdisc
));
1408 rcu_assign_pointer(dev
->qdisc
, &noop_qdisc
);
1410 WARN_ON(timer_pending(&dev
->watchdog_timer
));
1414 * psched_ratecfg_precompute__() - Pre-compute values for reciprocal division
1415 * @rate: Rate to compute reciprocal division values of
1416 * @mult: Multiplier for reciprocal division
1417 * @shift: Shift for reciprocal division
1419 * The multiplier and shift for reciprocal division by rate are stored
1420 * in mult and shift.
1422 * The deal here is to replace a divide by a reciprocal one
1423 * in fast path (a reciprocal divide is a multiply and a shift)
1425 * Normal formula would be :
1426 * time_in_ns = (NSEC_PER_SEC * len) / rate_bps
1428 * We compute mult/shift to use instead :
1429 * time_in_ns = (len * mult) >> shift;
1431 * We try to get the highest possible mult value for accuracy,
1432 * but have to make sure no overflows will ever happen.
1434 * reciprocal_value() is not used here it doesn't handle 64-bit values.
1436 static void psched_ratecfg_precompute__(u64 rate
, u32
*mult
, u8
*shift
)
1438 u64 factor
= NSEC_PER_SEC
;
1447 *mult
= div64_u64(factor
, rate
);
1448 if (*mult
& (1U << 31) || factor
& (1ULL << 63))
1455 void psched_ratecfg_precompute(struct psched_ratecfg
*r
,
1456 const struct tc_ratespec
*conf
,
1459 memset(r
, 0, sizeof(*r
));
1460 r
->overhead
= conf
->overhead
;
1462 r
->rate_bytes_ps
= max_t(u64
, conf
->rate
, rate64
);
1463 r
->linklayer
= (conf
->linklayer
& TC_LINKLAYER_MASK
);
1464 psched_ratecfg_precompute__(r
->rate_bytes_ps
, &r
->mult
, &r
->shift
);
1466 EXPORT_SYMBOL(psched_ratecfg_precompute
);
1468 void psched_ppscfg_precompute(struct psched_pktrate
*r
, u64 pktrate64
)
1470 r
->rate_pkts_ps
= pktrate64
;
1471 psched_ratecfg_precompute__(r
->rate_pkts_ps
, &r
->mult
, &r
->shift
);
1473 EXPORT_SYMBOL(psched_ppscfg_precompute
);
1475 static void mini_qdisc_rcu_func(struct rcu_head
*head
)
1479 void mini_qdisc_pair_swap(struct mini_Qdisc_pair
*miniqp
,
1480 struct tcf_proto
*tp_head
)
1482 /* Protected with chain0->filter_chain_lock.
1483 * Can't access chain directly because tp_head can be NULL.
1485 struct mini_Qdisc
*miniq_old
=
1486 rcu_dereference_protected(*miniqp
->p_miniq
, 1);
1487 struct mini_Qdisc
*miniq
;
1490 RCU_INIT_POINTER(*miniqp
->p_miniq
, NULL
);
1491 /* Wait for flying RCU callback before it is freed. */
1496 miniq
= !miniq_old
|| miniq_old
== &miniqp
->miniq2
?
1497 &miniqp
->miniq1
: &miniqp
->miniq2
;
1499 /* We need to make sure that readers won't see the miniq
1500 * we are about to modify. So wait until previous call_rcu callback
1504 miniq
->filter_list
= tp_head
;
1505 rcu_assign_pointer(*miniqp
->p_miniq
, miniq
);
1508 /* This is counterpart of the rcu barriers above. We need to
1509 * block potential new user of miniq_old until all readers
1510 * are not seeing it.
1512 call_rcu(&miniq_old
->rcu
, mini_qdisc_rcu_func
);
1514 EXPORT_SYMBOL(mini_qdisc_pair_swap
);
1516 void mini_qdisc_pair_block_init(struct mini_Qdisc_pair
*miniqp
,
1517 struct tcf_block
*block
)
1519 miniqp
->miniq1
.block
= block
;
1520 miniqp
->miniq2
.block
= block
;
1522 EXPORT_SYMBOL(mini_qdisc_pair_block_init
);
1524 void mini_qdisc_pair_init(struct mini_Qdisc_pair
*miniqp
, struct Qdisc
*qdisc
,
1525 struct mini_Qdisc __rcu
**p_miniq
)
1527 miniqp
->miniq1
.cpu_bstats
= qdisc
->cpu_bstats
;
1528 miniqp
->miniq1
.cpu_qstats
= qdisc
->cpu_qstats
;
1529 miniqp
->miniq2
.cpu_bstats
= qdisc
->cpu_bstats
;
1530 miniqp
->miniq2
.cpu_qstats
= qdisc
->cpu_qstats
;
1531 miniqp
->p_miniq
= p_miniq
;
1533 EXPORT_SYMBOL(mini_qdisc_pair_init
);