sch_generic.c

   1// SPDX-License-Identifier: GPL-2.0-or-later
   2/*
   3 * net/sched/sch_generic.c	Generic packet scheduler routines.
   4 *
   5 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
   6 *              Jamal Hadi Salim, <hadi@cyberus.ca> 990601
   7 *              - Ingress support
   8 */
   9
  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 <linux/bpf.h>
  28#include <net/sch_generic.h>
  29#include <net/pkt_sched.h>
  30#include <net/dst.h>
  31#include <net/hotdata.h>
  32#include <trace/events/qdisc.h>
  33#include <trace/events/net.h>
  34#include <net/xfrm.h>
  35
  36/* Qdisc to use by default */
  37const struct Qdisc_ops *default_qdisc_ops = &pfifo_fast_ops;
  38EXPORT_SYMBOL(default_qdisc_ops);
  39
  40static void qdisc_maybe_clear_missed(struct Qdisc *q,
  41				     const struct netdev_queue *txq)
  42{
  43	clear_bit(__QDISC_STATE_MISSED, &q->state);
  44
  45	/* Make sure the below netif_xmit_frozen_or_stopped()
  46	 * checking happens after clearing STATE_MISSED.
  47	 */
  48	smp_mb__after_atomic();
  49
  50	/* Checking netif_xmit_frozen_or_stopped() again to
  51	 * make sure STATE_MISSED is set if the STATE_MISSED
  52	 * set by netif_tx_wake_queue()'s rescheduling of
  53	 * net_tx_action() is cleared by the above clear_bit().
  54	 */
  55	if (!netif_xmit_frozen_or_stopped(txq))
  56		set_bit(__QDISC_STATE_MISSED, &q->state);
  57	else
  58		set_bit(__QDISC_STATE_DRAINING, &q->state);
  59}
  60
  61/* Main transmission queue. */
  62
  63/* Modifications to data participating in scheduling must be protected with
  64 * qdisc_lock(qdisc) spinlock.
  65 *
  66 * The idea is the following:
  67 * - enqueue, dequeue are serialized via qdisc root lock
  68 * - ingress filtering is also serialized via qdisc root lock
  69 * - updates to tree and tree walking are only done under the rtnl mutex.
  70 */
  71
  72#define SKB_XOFF_MAGIC ((struct sk_buff *)1UL)
  73
  74static inline struct sk_buff *__skb_dequeue_bad_txq(struct Qdisc *q)
  75{
  76	const struct netdev_queue *txq = q->dev_queue;
  77	spinlock_t *lock = NULL;
  78	struct sk_buff *skb;
  79
  80	if (q->flags & TCQ_F_NOLOCK) {
  81		lock = qdisc_lock(q);
  82		spin_lock(lock);
  83	}
  84
  85	skb = skb_peek(&q->skb_bad_txq);
  86	if (skb) {
  87		/* check the reason of requeuing without tx lock first */
  88		txq = skb_get_tx_queue(txq->dev, skb);
  89		if (!netif_xmit_frozen_or_stopped(txq)) {
  90			skb = __skb_dequeue(&q->skb_bad_txq);
  91			if (qdisc_is_percpu_stats(q)) {
  92				qdisc_qstats_cpu_backlog_dec(q, skb);
  93				qdisc_qstats_cpu_qlen_dec(q);
  94			} else {
  95				qdisc_qstats_backlog_dec(q, skb);
  96				q->q.qlen--;
  97			}
  98		} else {
  99			skb = SKB_XOFF_MAGIC;
 100			qdisc_maybe_clear_missed(q, txq);
 101		}
 102	}
 103
 104	if (lock)
 105		spin_unlock(lock);
 106
 107	return skb;
 108}
 109
 110static inline struct sk_buff *qdisc_dequeue_skb_bad_txq(struct Qdisc *q)
 111{
 112	struct sk_buff *skb = skb_peek(&q->skb_bad_txq);
 113
 114	if (unlikely(skb))
 115		skb = __skb_dequeue_bad_txq(q);
 116
 117	return skb;
 118}
 119
 120static inline void qdisc_enqueue_skb_bad_txq(struct Qdisc *q,
 121					     struct sk_buff *skb)
 122{
 123	spinlock_t *lock = NULL;
 124
 125	if (q->flags & TCQ_F_NOLOCK) {
 126		lock = qdisc_lock(q);
 127		spin_lock(lock);
 128	}
 129
 130	__skb_queue_tail(&q->skb_bad_txq, skb);
 131
 132	if (qdisc_is_percpu_stats(q)) {
 133		qdisc_qstats_cpu_backlog_inc(q, skb);
 134		qdisc_qstats_cpu_qlen_inc(q);
 135	} else {
 136		qdisc_qstats_backlog_inc(q, skb);
 137		q->q.qlen++;
 138	}
 139
 140	if (lock)
 141		spin_unlock(lock);
 142}
 143
 144static inline void dev_requeue_skb(struct sk_buff *skb, struct Qdisc *q)
 145{
 146	spinlock_t *lock = NULL;
 147
 148	if (q->flags & TCQ_F_NOLOCK) {
 149		lock = qdisc_lock(q);
 150		spin_lock(lock);
 151	}
 152
 153	while (skb) {
 154		struct sk_buff *next = skb->next;
 155
 156		__skb_queue_tail(&q->gso_skb, skb);
 157
 158		/* it's still part of the queue */
 159		if (qdisc_is_percpu_stats(q)) {
 160			qdisc_qstats_cpu_requeues_inc(q);
 161			qdisc_qstats_cpu_backlog_inc(q, skb);
 162			qdisc_qstats_cpu_qlen_inc(q);
 163		} else {
 164			q->qstats.requeues++;
 165			qdisc_qstats_backlog_inc(q, skb);
 166			q->q.qlen++;
 167		}
 168
 169		skb = next;
 170	}
 171
 172	if (lock) {
 173		spin_unlock(lock);
 174		set_bit(__QDISC_STATE_MISSED, &q->state);
 175	} else {
 176		__netif_schedule(q);
 177	}
 178}
 179
 180static void try_bulk_dequeue_skb(struct Qdisc *q,
 181				 struct sk_buff *skb,
 182				 const struct netdev_queue *txq,
 183				 int *packets, int budget)
 184{
 185	int bytelimit = qdisc_avail_bulklimit(txq) - skb->len;
 186	int cnt = 0;
 187
 188	while (bytelimit > 0) {
 189		struct sk_buff *nskb = q->dequeue(q);
 190
 191		if (!nskb)
 192			break;
 193
 194		bytelimit -= nskb->len; /* covers GSO len */
 195		skb->next = nskb;
 196		skb = nskb;
 197		if (++cnt >= budget)
 198			break;
 199	}
 200	(*packets) += cnt;
 201	skb_mark_not_on_list(skb);
 202}
 203
 204/* This variant of try_bulk_dequeue_skb() makes sure
 205 * all skbs in the chain are for the same txq
 206 */
 207static void try_bulk_dequeue_skb_slow(struct Qdisc *q,
 208				      struct sk_buff *skb,
 209				      int *packets)
 210{
 211	int mapping = skb_get_queue_mapping(skb);
 212	struct sk_buff *nskb;
 213	int cnt = 0;
 214
 215	do {
 216		nskb = q->dequeue(q);
 217		if (!nskb)
 218			break;
 219		if (unlikely(skb_get_queue_mapping(nskb) != mapping)) {
 220			qdisc_enqueue_skb_bad_txq(q, nskb);
 221			break;
 222		}
 223		skb->next = nskb;
 224		skb = nskb;
 225	} while (++cnt < 8);
 226	(*packets) += cnt;
 227	skb_mark_not_on_list(skb);
 228}
 229
 230/* Note that dequeue_skb can possibly return a SKB list (via skb->next).
 231 * A requeued skb (via q->gso_skb) can also be a SKB list.
 232 */
 233static struct sk_buff *dequeue_skb(struct Qdisc *q, bool *validate,
 234				   int *packets, int budget)
 235{
 236	const struct netdev_queue *txq = q->dev_queue;
 237	struct sk_buff *skb = NULL;
 238
 239	*packets = 1;
 240	if (unlikely(!skb_queue_empty(&q->gso_skb))) {
 241		spinlock_t *lock = NULL;
 242
 243		if (q->flags & TCQ_F_NOLOCK) {
 244			lock = qdisc_lock(q);
 245			spin_lock(lock);
 246		}
 247
 248		skb = skb_peek(&q->gso_skb);
 249
 250		/* skb may be null if another cpu pulls gso_skb off in between
 251		 * empty check and lock.
 252		 */
 253		if (!skb) {
 254			if (lock)
 255				spin_unlock(lock);
 256			goto validate;
 257		}
 258
 259		/* skb in gso_skb were already validated */
 260		*validate = false;
 261		if (xfrm_offload(skb))
 262			*validate = true;
 263		/* check the reason of requeuing without tx lock first */
 264		txq = skb_get_tx_queue(txq->dev, skb);
 265		if (!netif_xmit_frozen_or_stopped(txq)) {
 266			skb = __skb_dequeue(&q->gso_skb);
 267			if (qdisc_is_percpu_stats(q)) {
 268				qdisc_qstats_cpu_backlog_dec(q, skb);
 269				qdisc_qstats_cpu_qlen_dec(q);
 270			} else {
 271				qdisc_qstats_backlog_dec(q, skb);
 272				q->q.qlen--;
 273			}
 274		} else {
 275			skb = NULL;
 276			qdisc_maybe_clear_missed(q, txq);
 277		}
 278		if (lock)
 279			spin_unlock(lock);
 280		goto trace;
 281	}
 282validate:
 283	*validate = true;
 284
 285	if ((q->flags & TCQ_F_ONETXQUEUE) &&
 286	    netif_xmit_frozen_or_stopped(txq)) {
 287		qdisc_maybe_clear_missed(q, txq);
 288		return skb;
 289	}
 290
 291	skb = qdisc_dequeue_skb_bad_txq(q);
 292	if (unlikely(skb)) {
 293		if (skb == SKB_XOFF_MAGIC)
 294			return NULL;
 295		goto bulk;
 296	}
 297	skb = q->dequeue(q);
 298	if (skb) {
 299bulk:
 300		if (qdisc_may_bulk(q))
 301			try_bulk_dequeue_skb(q, skb, txq, packets, budget);
 302		else
 303			try_bulk_dequeue_skb_slow(q, skb, packets);
 304	}
 305trace:
 306	trace_qdisc_dequeue(q, txq, *packets, skb);
 307	return skb;
 308}
 309
 310/*
 311 * Transmit possibly several skbs, and handle the return status as
 312 * required. Owning qdisc running bit guarantees that only one CPU
 313 * can execute this function.
 314 *
 315 * Returns to the caller:
 316 *				false  - hardware queue frozen backoff
 317 *				true   - feel free to send more pkts
 318 */
 319bool sch_direct_xmit(struct sk_buff *skb, struct Qdisc *q,
 320		     struct net_device *dev, struct netdev_queue *txq,
 321		     spinlock_t *root_lock, bool validate)
 322{
 323	int ret = NETDEV_TX_BUSY;
 324	bool again = false;
 325
 326	/* And release qdisc */
 327	if (root_lock)
 328		spin_unlock(root_lock);
 329
 330	/* Note that we validate skb (GSO, checksum, ...) outside of locks */
 331	if (validate)
 332		skb = validate_xmit_skb_list(skb, dev, &again);
 333
 334#ifdef CONFIG_XFRM_OFFLOAD
 335	if (unlikely(again)) {
 336		if (root_lock)
 337			spin_lock(root_lock);
 338
 339		dev_requeue_skb(skb, q);
 340		return false;
 341	}
 342#endif
 343
 344	if (likely(skb)) {
 345		HARD_TX_LOCK(dev, txq, smp_processor_id());
 346		if (!netif_xmit_frozen_or_stopped(txq))
 347			skb = dev_hard_start_xmit(skb, dev, txq, &ret);
 348		else
 349			qdisc_maybe_clear_missed(q, txq);
 350
 351		HARD_TX_UNLOCK(dev, txq);
 352	} else {
 353		if (root_lock)
 354			spin_lock(root_lock);
 355		return true;
 356	}
 357
 358	if (root_lock)
 359		spin_lock(root_lock);
 360
 361	if (!dev_xmit_complete(ret)) {
 362		/* Driver returned NETDEV_TX_BUSY - requeue skb */
 363		if (unlikely(ret != NETDEV_TX_BUSY))
 364			net_warn_ratelimited("BUG %s code %d qlen %d\n",
 365					     dev->name, ret, q->q.qlen);
 366
 367		dev_requeue_skb(skb, q);
 368		return false;
 369	}
 370
 371	return true;
 372}
 373
 374/*
 375 * NOTE: Called under qdisc_lock(q) with locally disabled BH.
 376 *
 377 * running seqcount guarantees only one CPU can process
 378 * this qdisc at a time. qdisc_lock(q) serializes queue accesses for
 379 * this queue.
 380 *
 381 *  netif_tx_lock serializes accesses to device driver.
 382 *
 383 *  qdisc_lock(q) and netif_tx_lock are mutually exclusive,
 384 *  if one is grabbed, another must be free.
 385 *
 386 * Note, that this procedure can be called by a watchdog timer
 387 *
 388 * Returns to the caller:
 389 *				0  - queue is empty or throttled.
 390 *				>0 - queue is not empty.
 391 *
 392 */
 393static inline bool qdisc_restart(struct Qdisc *q, int *packets, int budget)
 394{
 395	spinlock_t *root_lock = NULL;
 396	struct netdev_queue *txq;
 397	struct net_device *dev;
 398	struct sk_buff *skb;
 399	bool validate;
 400
 401	/* Dequeue packet */
 402	skb = dequeue_skb(q, &validate, packets, budget);
 403	if (unlikely(!skb))
 404		return false;
 405
 406	if (!(q->flags & TCQ_F_NOLOCK))
 407		root_lock = qdisc_lock(q);
 408
 409	dev = qdisc_dev(q);
 410	txq = skb_get_tx_queue(dev, skb);
 411
 412	return sch_direct_xmit(skb, q, dev, txq, root_lock, validate);
 413}
 414
 415void __qdisc_run(struct Qdisc *q)
 416{
 417	int quota = READ_ONCE(net_hotdata.dev_tx_weight);
 418	int packets;
 419
 420	while (qdisc_restart(q, &packets, quota)) {
 421		quota -= packets;
 422		if (quota <= 0) {
 423			if (q->flags & TCQ_F_NOLOCK)
 424				set_bit(__QDISC_STATE_MISSED, &q->state);
 425			else
 426				__netif_schedule(q);
 427
 428			break;
 429		}
 430	}
 431}
 432
 433unsigned long dev_trans_start(struct net_device *dev)
 434{
 435	unsigned long res = READ_ONCE(netdev_get_tx_queue(dev, 0)->trans_start);
 436	unsigned long val;
 437	unsigned int i;
 438
 439	for (i = 1; i < dev->num_tx_queues; i++) {
 440		val = READ_ONCE(netdev_get_tx_queue(dev, i)->trans_start);
 441		if (val && time_after(val, res))
 442			res = val;
 443	}
 444
 445	return res;
 446}
 447EXPORT_SYMBOL(dev_trans_start);
 448
 449static void netif_freeze_queues(struct net_device *dev)
 450{
 451	unsigned int i;
 452	int cpu;
 453
 454	cpu = smp_processor_id();
 455	for (i = 0; i < dev->num_tx_queues; i++) {
 456		struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
 457
 458		/* We are the only thread of execution doing a
 459		 * freeze, but we have to grab the _xmit_lock in
 460		 * order to synchronize with threads which are in
 461		 * the ->hard_start_xmit() handler and already
 462		 * checked the frozen bit.
 463		 */
 464		__netif_tx_lock(txq, cpu);
 465		set_bit(__QUEUE_STATE_FROZEN, &txq->state);
 466		__netif_tx_unlock(txq);
 467	}
 468}
 469
 470void netif_tx_lock(struct net_device *dev)
 471{
 472	spin_lock(&dev->tx_global_lock);
 473	netif_freeze_queues(dev);
 474}
 475EXPORT_SYMBOL(netif_tx_lock);
 476
 477static void netif_unfreeze_queues(struct net_device *dev)
 478{
 479	unsigned int i;
 480
 481	for (i = 0; i < dev->num_tx_queues; i++) {
 482		struct netdev_queue *txq = netdev_get_tx_queue(dev, i);
 483
 484		/* No need to grab the _xmit_lock here.  If the
 485		 * queue is not stopped for another reason, we
 486		 * force a schedule.
 487		 */
 488		clear_bit(__QUEUE_STATE_FROZEN, &txq->state);
 489		netif_schedule_queue(txq);
 490	}
 491}
 492
 493void netif_tx_unlock(struct net_device *dev)
 494{
 495	netif_unfreeze_queues(dev);
 496	spin_unlock(&dev->tx_global_lock);
 497}
 498EXPORT_SYMBOL(netif_tx_unlock);
 499
 500static void dev_watchdog(struct timer_list *t)
 501{
 502	struct net_device *dev = timer_container_of(dev, t, watchdog_timer);
 503	bool release = true;
 504
 505	spin_lock(&dev->tx_global_lock);
 506	if (!qdisc_tx_is_noop(dev)) {
 507		if (netif_device_present(dev) &&
 508		    netif_running(dev) &&
 509		    netif_carrier_ok(dev)) {
 510			unsigned int timedout_ms = 0;
 511			unsigned int i;
 512			unsigned long trans_start;
 513			unsigned long oldest_start = jiffies;
 514
 515			for (i = 0; i < dev->num_tx_queues; i++) {
 516				struct netdev_queue *txq;
 517
 518				txq = netdev_get_tx_queue(dev, i);
 519				if (!netif_xmit_stopped(txq))
 520					continue;
 521
 522				/* Paired with WRITE_ONCE() + smp_mb...() in
 523				 * netdev_tx_sent_queue() and netif_tx_stop_queue().
 524				 */
 525				smp_mb();
 526				trans_start = READ_ONCE(txq->trans_start);
 527
 528				if (time_after(jiffies, trans_start + dev->watchdog_timeo)) {
 529					timedout_ms = jiffies_to_msecs(jiffies - trans_start);
 530					atomic_long_inc(&txq->trans_timeout);
 531					break;
 532				}
 533				if (time_after(oldest_start, trans_start))
 534					oldest_start = trans_start;
 535			}
 536
 537			if (unlikely(timedout_ms)) {
 538				trace_net_dev_xmit_timeout(dev, i);
 539				netdev_crit(dev, "NETDEV WATCHDOG: CPU: %d: transmit queue %u timed out %u ms\n",
 540					    raw_smp_processor_id(),
 541					    i, timedout_ms);
 542				netif_freeze_queues(dev);
 543				dev->netdev_ops->ndo_tx_timeout(dev, i);
 544				netif_unfreeze_queues(dev);
 545			}
 546			if (!mod_timer(&dev->watchdog_timer,
 547				       round_jiffies(oldest_start +
 548						     dev->watchdog_timeo)))
 549				release = false;
 550		}
 551	}
 552	spin_unlock(&dev->tx_global_lock);
 553
 554	if (release)
 555		netdev_put(dev, &dev->watchdog_dev_tracker);
 556}
 557
 558void netdev_watchdog_up(struct net_device *dev)
 559{
 560	if (!dev->netdev_ops->ndo_tx_timeout)
 561		return;
 562	if (dev->watchdog_timeo <= 0)
 563		dev->watchdog_timeo = 5*HZ;
 564	if (!mod_timer(&dev->watchdog_timer,
 565		       round_jiffies(jiffies + dev->watchdog_timeo)))
 566		netdev_hold(dev, &dev->watchdog_dev_tracker,
 567			    GFP_ATOMIC);
 568}
 569EXPORT_SYMBOL_GPL(netdev_watchdog_up);
 570
 571static void netdev_watchdog_down(struct net_device *dev)
 572{
 573	netif_tx_lock_bh(dev);
 574	if (timer_delete(&dev->watchdog_timer))
 575		netdev_put(dev, &dev->watchdog_dev_tracker);
 576	netif_tx_unlock_bh(dev);
 577}
 578
 579/**
 580 *	netif_carrier_on - set carrier
 581 *	@dev: network device
 582 *
 583 * Device has detected acquisition of carrier.
 584 */
 585void netif_carrier_on(struct net_device *dev)
 586{
 587	if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state)) {
 588		if (dev->reg_state == NETREG_UNINITIALIZED)
 589			return;
 590		atomic_inc(&dev->carrier_up_count);
 591		linkwatch_fire_event(dev);
 592		if (netif_running(dev))
 593			netdev_watchdog_up(dev);
 594	}
 595}
 596EXPORT_SYMBOL(netif_carrier_on);
 597
 598/**
 599 *	netif_carrier_off - clear carrier
 600 *	@dev: network device
 601 *
 602 * Device has detected loss of carrier.
 603 */
 604void netif_carrier_off(struct net_device *dev)
 605{
 606	if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state)) {
 607		if (dev->reg_state == NETREG_UNINITIALIZED)
 608			return;
 609		atomic_inc(&dev->carrier_down_count);
 610		linkwatch_fire_event(dev);
 611	}
 612}
 613EXPORT_SYMBOL(netif_carrier_off);
 614
 615/**
 616 *	netif_carrier_event - report carrier state event
 617 *	@dev: network device
 618 *
 619 * Device has detected a carrier event but the carrier state wasn't changed.
 620 * Use in drivers when querying carrier state asynchronously, to avoid missing
 621 * events (link flaps) if link recovers before it's queried.
 622 */
 623void netif_carrier_event(struct net_device *dev)
 624{
 625	if (dev->reg_state == NETREG_UNINITIALIZED)
 626		return;
 627	atomic_inc(&dev->carrier_up_count);
 628	atomic_inc(&dev->carrier_down_count);
 629	linkwatch_fire_event(dev);
 630}
 631EXPORT_SYMBOL_GPL(netif_carrier_event);
 632
 633/* "NOOP" scheduler: the best scheduler, recommended for all interfaces
 634   under all circumstances. It is difficult to invent anything faster or
 635   cheaper.
 636 */
 637
 638static int noop_enqueue(struct sk_buff *skb, struct Qdisc *qdisc,
 639			struct sk_buff **to_free)
 640{
 641	dev_core_stats_tx_dropped_inc(skb->dev);
 642	__qdisc_drop(skb, to_free);
 643	return NET_XMIT_CN;
 644}
 645
 646static struct sk_buff *noop_dequeue(struct Qdisc *qdisc)
 647{
 648	return NULL;
 649}
 650
 651struct Qdisc_ops noop_qdisc_ops __read_mostly = {
 652	.id		=	"noop",
 653	.priv_size	=	0,
 654	.enqueue	=	noop_enqueue,
 655	.dequeue	=	noop_dequeue,
 656	.peek		=	noop_dequeue,
 657	.owner		=	THIS_MODULE,
 658};
 659
 660static struct netdev_queue noop_netdev_queue = {
 661	RCU_POINTER_INITIALIZER(qdisc, &noop_qdisc),
 662	RCU_POINTER_INITIALIZER(qdisc_sleeping, &noop_qdisc),
 663};
 664
 665struct Qdisc noop_qdisc = {
 666	.enqueue	=	noop_enqueue,
 667	.dequeue	=	noop_dequeue,
 668	.flags		=	TCQ_F_BUILTIN,
 669	.ops		=	&noop_qdisc_ops,
 670	.q.lock		=	__SPIN_LOCK_UNLOCKED(noop_qdisc.q.lock),
 671	.dev_queue	=	&noop_netdev_queue,
 672	.gso_skb = {
 673		.next = (struct sk_buff *)&noop_qdisc.gso_skb,
 674		.prev = (struct sk_buff *)&noop_qdisc.gso_skb,
 675		.qlen = 0,
 676		.lock = __SPIN_LOCK_UNLOCKED(noop_qdisc.gso_skb.lock),
 677	},
 678	.skb_bad_txq = {
 679		.next = (struct sk_buff *)&noop_qdisc.skb_bad_txq,
 680		.prev = (struct sk_buff *)&noop_qdisc.skb_bad_txq,
 681		.qlen = 0,
 682		.lock = __SPIN_LOCK_UNLOCKED(noop_qdisc.skb_bad_txq.lock),
 683	},
 684};
 685EXPORT_SYMBOL(noop_qdisc);
 686
 687static int noqueue_init(struct Qdisc *qdisc, struct nlattr *opt,
 688			struct netlink_ext_ack *extack)
 689{
 690	/* register_qdisc() assigns a default of noop_enqueue if unset,
 691	 * but __dev_queue_xmit() treats noqueue only as such
 692	 * if this is NULL - so clear it here. */
 693	qdisc->enqueue = NULL;
 694	return 0;
 695}
 696
 697struct Qdisc_ops noqueue_qdisc_ops __read_mostly = {
 698	.id		=	"noqueue",
 699	.priv_size	=	0,
 700	.init		=	noqueue_init,
 701	.enqueue	=	noop_enqueue,
 702	.dequeue	=	noop_dequeue,
 703	.peek		=	noop_dequeue,
 704	.owner		=	THIS_MODULE,
 705};
 706
 707const u8 sch_default_prio2band[TC_PRIO_MAX + 1] = {
 708	1, 2, 2, 2, 1, 2, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1
 709};
 710EXPORT_SYMBOL(sch_default_prio2band);
 711
 712/* 3-band FIFO queue: old style, but should be a bit faster than
 713   generic prio+fifo combination.
 714 */
 715
 716#define PFIFO_FAST_BANDS 3
 717
 718/*
 719 * Private data for a pfifo_fast scheduler containing:
 720 *	- rings for priority bands
 721 */
 722struct pfifo_fast_priv {
 723	struct skb_array q[PFIFO_FAST_BANDS];
 724};
 725
 726static inline struct skb_array *band2list(struct pfifo_fast_priv *priv,
 727					  int band)
 728{
 729	return &priv->q[band];
 730}
 731
 732static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc *qdisc,
 733			      struct sk_buff **to_free)
 734{
 735	int band = sch_default_prio2band[skb->priority & TC_PRIO_MAX];
 736	struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
 737	struct skb_array *q = band2list(priv, band);
 738	unsigned int pkt_len = qdisc_pkt_len(skb);
 739	int err;
 740
 741	err = skb_array_produce(q, skb);
 742
 743	if (unlikely(err)) {
 744		tcf_set_drop_reason(skb, SKB_DROP_REASON_QDISC_OVERLIMIT);
 745
 746		if (qdisc_is_percpu_stats(qdisc))
 747			return qdisc_drop_cpu(skb, qdisc, to_free);
 748		else
 749			return qdisc_drop(skb, qdisc, to_free);
 750	}
 751
 752	qdisc_update_stats_at_enqueue(qdisc, pkt_len);
 753	return NET_XMIT_SUCCESS;
 754}
 755
 756static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc)
 757{
 758	struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
 759	struct sk_buff *skb = NULL;
 760	bool need_retry = true;
 761	int band;
 762
 763retry:
 764	for (band = 0; band < PFIFO_FAST_BANDS && !skb; band++) {
 765		struct skb_array *q = band2list(priv, band);
 766
 767		if (__skb_array_empty(q))
 768			continue;
 769
 770		skb = __skb_array_consume(q);
 771	}
 772	if (likely(skb)) {
 773		qdisc_update_stats_at_dequeue(qdisc, skb);
 774	} else if (need_retry &&
 775		   READ_ONCE(qdisc->state) & QDISC_STATE_NON_EMPTY) {
 776		/* Delay clearing the STATE_MISSED here to reduce
 777		 * the overhead of the second spin_trylock() in
 778		 * qdisc_run_begin() and __netif_schedule() calling
 779		 * in qdisc_run_end().
 780		 */
 781		clear_bit(__QDISC_STATE_MISSED, &qdisc->state);
 782		clear_bit(__QDISC_STATE_DRAINING, &qdisc->state);
 783
 784		/* Make sure dequeuing happens after clearing
 785		 * STATE_MISSED.
 786		 */
 787		smp_mb__after_atomic();
 788
 789		need_retry = false;
 790
 791		goto retry;
 792	}
 793
 794	return skb;
 795}
 796
 797static struct sk_buff *pfifo_fast_peek(struct Qdisc *qdisc)
 798{
 799	struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
 800	struct sk_buff *skb = NULL;
 801	int band;
 802
 803	for (band = 0; band < PFIFO_FAST_BANDS && !skb; band++) {
 804		struct skb_array *q = band2list(priv, band);
 805
 806		skb = __skb_array_peek(q);
 807	}
 808
 809	return skb;
 810}
 811
 812static void pfifo_fast_reset(struct Qdisc *qdisc)
 813{
 814	int i, band;
 815	struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
 816
 817	for (band = 0; band < PFIFO_FAST_BANDS; band++) {
 818		struct skb_array *q = band2list(priv, band);
 819		struct sk_buff *skb;
 820
 821		/* NULL ring is possible if destroy path is due to a failed
 822		 * skb_array_init() in pfifo_fast_init() case.
 823		 */
 824		if (!q->ring.queue)
 825			continue;
 826
 827		while ((skb = __skb_array_consume(q)) != NULL)
 828			kfree_skb(skb);
 829	}
 830
 831	if (qdisc_is_percpu_stats(qdisc)) {
 832		for_each_possible_cpu(i) {
 833			struct gnet_stats_queue *q;
 834
 835			q = per_cpu_ptr(qdisc->cpu_qstats, i);
 836			q->backlog = 0;
 837			q->qlen = 0;
 838		}
 839	}
 840}
 841
 842static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb)
 843{
 844	struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS };
 845
 846	memcpy(&opt.priomap, sch_default_prio2band, TC_PRIO_MAX + 1);
 847	if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
 848		goto nla_put_failure;
 849	return skb->len;
 850
 851nla_put_failure:
 852	return -1;
 853}
 854
 855static int pfifo_fast_init(struct Qdisc *qdisc, struct nlattr *opt,
 856			   struct netlink_ext_ack *extack)
 857{
 858	unsigned int qlen = qdisc_dev(qdisc)->tx_queue_len;
 859	struct pfifo_fast_priv *priv = qdisc_priv(qdisc);
 860	int prio;
 861
 862	/* guard against zero length rings */
 863	if (!qlen)
 864		return -EINVAL;
 865
 866	for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) {
 867		struct skb_array *q = band2list(priv, prio);
 868		int err;
 869
 870		err = skb_array_init(q, qlen, GFP_KERNEL);
 871		if (err)
 872			return -ENOMEM;
 873	}
 874
 875	/* Can by-pass the queue discipline */
 876	qdisc->flags |= TCQ_F_CAN_BYPASS;
 877	return 0;
 878}
 879
 880static void pfifo_fast_destroy(struct Qdisc *sch)
 881{
 882	struct pfifo_fast_priv *priv = qdisc_priv(sch);
 883	int prio;
 884
 885	for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) {
 886		struct skb_array *q = band2list(priv, prio);
 887
 888		/* NULL ring is possible if destroy path is due to a failed
 889		 * skb_array_init() in pfifo_fast_init() case.
 890		 */
 891		if (!q->ring.queue)
 892			continue;
 893		/* Destroy ring but no need to kfree_skb because a call to
 894		 * pfifo_fast_reset() has already done that work.
 895		 */
 896		ptr_ring_cleanup(&q->ring, NULL);
 897	}
 898}
 899
 900static int pfifo_fast_change_tx_queue_len(struct Qdisc *sch,
 901					  unsigned int new_len)
 902{
 903	struct pfifo_fast_priv *priv = qdisc_priv(sch);
 904	struct skb_array *bands[PFIFO_FAST_BANDS];
 905	int prio;
 906
 907	for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) {
 908		struct skb_array *q = band2list(priv, prio);
 909
 910		bands[prio] = q;
 911	}
 912
 913	return skb_array_resize_multiple_bh(bands, PFIFO_FAST_BANDS, new_len,
 914					    GFP_KERNEL);
 915}
 916
 917struct Qdisc_ops pfifo_fast_ops __read_mostly = {
 918	.id		=	"pfifo_fast",
 919	.priv_size	=	sizeof(struct pfifo_fast_priv),
 920	.enqueue	=	pfifo_fast_enqueue,
 921	.dequeue	=	pfifo_fast_dequeue,
 922	.peek		=	pfifo_fast_peek,
 923	.init		=	pfifo_fast_init,
 924	.destroy	=	pfifo_fast_destroy,
 925	.reset		=	pfifo_fast_reset,
 926	.dump		=	pfifo_fast_dump,
 927	.change_tx_queue_len =  pfifo_fast_change_tx_queue_len,
 928	.owner		=	THIS_MODULE,
 929	.static_flags	=	TCQ_F_NOLOCK | TCQ_F_CPUSTATS,
 930};
 931EXPORT_SYMBOL(pfifo_fast_ops);
 932
 933static struct lock_class_key qdisc_tx_busylock;
 934
 935struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 936			  const struct Qdisc_ops *ops,
 937			  struct netlink_ext_ack *extack)
 938{
 939	struct Qdisc *sch;
 940	unsigned int size = sizeof(*sch) + ops->priv_size;
 941	int err = -ENOBUFS;
 942	struct net_device *dev;
 943
 944	if (!dev_queue) {
 945		NL_SET_ERR_MSG(extack, "No device queue given");
 946		err = -EINVAL;
 947		goto errout;
 948	}
 949
 950	dev = dev_queue->dev;
 951	sch = kzalloc_node(size, GFP_KERNEL, netdev_queue_numa_node_read(dev_queue));
 952
 953	if (!sch)
 954		goto errout;
 955	__skb_queue_head_init(&sch->gso_skb);
 956	__skb_queue_head_init(&sch->skb_bad_txq);
 957	gnet_stats_basic_sync_init(&sch->bstats);
 958	lockdep_register_key(&sch->root_lock_key);
 959	spin_lock_init(&sch->q.lock);
 960	lockdep_set_class(&sch->q.lock, &sch->root_lock_key);
 961
 962	if (ops->static_flags & TCQ_F_CPUSTATS) {
 963		sch->cpu_bstats =
 964			netdev_alloc_pcpu_stats(struct gnet_stats_basic_sync);
 965		if (!sch->cpu_bstats)
 966			goto errout1;
 967
 968		sch->cpu_qstats = alloc_percpu(struct gnet_stats_queue);
 969		if (!sch->cpu_qstats) {
 970			free_percpu(sch->cpu_bstats);
 971			goto errout1;
 972		}
 973	}
 974
 975	/* seqlock has the same scope of busylock, for NOLOCK qdisc */
 976	spin_lock_init(&sch->seqlock);
 977	lockdep_set_class(&sch->seqlock,
 978			  dev->qdisc_tx_busylock ?: &qdisc_tx_busylock);
 979
 980	sch->ops = ops;
 981	sch->flags = ops->static_flags;
 982	sch->enqueue = ops->enqueue;
 983	sch->dequeue = ops->dequeue;
 984	sch->dev_queue = dev_queue;
 985	netdev_hold(dev, &sch->dev_tracker, GFP_KERNEL);
 986	refcount_set(&sch->refcnt, 1);
 987
 988	return sch;
 989errout1:
 990	lockdep_unregister_key(&sch->root_lock_key);
 991	kfree(sch);
 992errout:
 993	return ERR_PTR(err);
 994}
 995
 996struct Qdisc *qdisc_create_dflt(struct netdev_queue *dev_queue,
 997				const struct Qdisc_ops *ops,
 998				unsigned int parentid,
 999				struct netlink_ext_ack *extack)
1000{
1001	struct Qdisc *sch;
1002
1003	if (!bpf_try_module_get(ops, ops->owner)) {
1004		NL_SET_ERR_MSG(extack, "Failed to increase module reference counter");
1005		return NULL;
1006	}
1007
1008	sch = qdisc_alloc(dev_queue, ops, extack);
1009	if (IS_ERR(sch)) {
1010		bpf_module_put(ops, ops->owner);
1011		return NULL;
1012	}
1013	sch->parent = parentid;
1014
1015	if (!ops->init || ops->init(sch, NULL, extack) == 0) {
1016		trace_qdisc_create(ops, dev_queue->dev, parentid);
1017		return sch;
1018	}
1019
1020	qdisc_put(sch);
1021	return NULL;
1022}
1023EXPORT_SYMBOL(qdisc_create_dflt);
1024
1025/* Under qdisc_lock(qdisc) and BH! */
1026
1027void qdisc_reset(struct Qdisc *qdisc)
1028{
1029	const struct Qdisc_ops *ops = qdisc->ops;
1030
1031	trace_qdisc_reset(qdisc);
1032
1033	if (ops->reset)
1034		ops->reset(qdisc);
1035
1036	__skb_queue_purge(&qdisc->gso_skb);
1037	__skb_queue_purge(&qdisc->skb_bad_txq);
1038
1039	qdisc->q.qlen = 0;
1040	qdisc->qstats.backlog = 0;
1041}
1042EXPORT_SYMBOL(qdisc_reset);
1043
1044void qdisc_free(struct Qdisc *qdisc)
1045{
1046	if (qdisc_is_percpu_stats(qdisc)) {
1047		free_percpu(qdisc->cpu_bstats);
1048		free_percpu(qdisc->cpu_qstats);
1049	}
1050
1051	kfree(qdisc);
1052}
1053
1054static void qdisc_free_cb(struct rcu_head *head)
1055{
1056	struct Qdisc *q = container_of(head, struct Qdisc, rcu);
1057
1058	qdisc_free(q);
1059}
1060
1061static void __qdisc_destroy(struct Qdisc *qdisc)
1062{
1063	const struct Qdisc_ops  *ops = qdisc->ops;
1064	struct net_device *dev = qdisc_dev(qdisc);
1065
1066#ifdef CONFIG_NET_SCHED
1067	qdisc_hash_del(qdisc);
1068
1069	qdisc_put_stab(rtnl_dereference(qdisc->stab));
1070#endif
1071	gen_kill_estimator(&qdisc->rate_est);
1072
1073	qdisc_reset(qdisc);
1074
1075
1076	if (ops->destroy)
1077		ops->destroy(qdisc);
1078
1079	lockdep_unregister_key(&qdisc->root_lock_key);
1080	bpf_module_put(ops, ops->owner);
1081	netdev_put(dev, &qdisc->dev_tracker);
1082
1083	trace_qdisc_destroy(qdisc);
1084
1085	call_rcu(&qdisc->rcu, qdisc_free_cb);
1086}
1087
1088void qdisc_destroy(struct Qdisc *qdisc)
1089{
1090	if (qdisc->flags & TCQ_F_BUILTIN)
1091		return;
1092
1093	__qdisc_destroy(qdisc);
1094}
1095
1096void qdisc_put(struct Qdisc *qdisc)
1097{
1098	if (!qdisc)
1099		return;
1100
1101	if (qdisc->flags & TCQ_F_BUILTIN ||
1102	    !refcount_dec_and_test(&qdisc->refcnt))
1103		return;
1104
1105	__qdisc_destroy(qdisc);
1106}
1107EXPORT_SYMBOL(qdisc_put);
1108
1109/* Version of qdisc_put() that is called with rtnl mutex unlocked.
1110 * Intended to be used as optimization, this function only takes rtnl lock if
1111 * qdisc reference counter reached zero.
1112 */
1113
1114void qdisc_put_unlocked(struct Qdisc *qdisc)
1115{
1116	if (qdisc->flags & TCQ_F_BUILTIN ||
1117	    !refcount_dec_and_rtnl_lock(&qdisc->refcnt))
1118		return;
1119
1120	__qdisc_destroy(qdisc);
1121	rtnl_unlock();
1122}
1123EXPORT_SYMBOL(qdisc_put_unlocked);
1124
1125/* Attach toplevel qdisc to device queue. */
1126struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue,
1127			      struct Qdisc *qdisc)
1128{
1129	struct Qdisc *oqdisc = rtnl_dereference(dev_queue->qdisc_sleeping);
1130	spinlock_t *root_lock;
1131
1132	root_lock = qdisc_lock(oqdisc);
1133	spin_lock_bh(root_lock);
1134
1135	/* ... and graft new one */
1136	if (qdisc == NULL)
1137		qdisc = &noop_qdisc;
1138	rcu_assign_pointer(dev_queue->qdisc_sleeping, qdisc);
1139	rcu_assign_pointer(dev_queue->qdisc, &noop_qdisc);
1140
1141	spin_unlock_bh(root_lock);
1142
1143	return oqdisc;
1144}
1145EXPORT_SYMBOL(dev_graft_qdisc);
1146
1147static void shutdown_scheduler_queue(struct net_device *dev,
1148				     struct netdev_queue *dev_queue,
1149				     void *_qdisc_default)
1150{
1151	struct Qdisc *qdisc = rtnl_dereference(dev_queue->qdisc_sleeping);
1152	struct Qdisc *qdisc_default = _qdisc_default;
1153
1154	if (qdisc) {
1155		rcu_assign_pointer(dev_queue->qdisc, qdisc_default);
1156		rcu_assign_pointer(dev_queue->qdisc_sleeping, qdisc_default);
1157
1158		qdisc_put(qdisc);
1159	}
1160}
1161
1162static void attach_one_default_qdisc(struct net_device *dev,
1163				     struct netdev_queue *dev_queue,
1164				     void *_unused)
1165{
1166	struct Qdisc *qdisc;
1167	const struct Qdisc_ops *ops = default_qdisc_ops;
1168
1169	if (dev->priv_flags & IFF_NO_QUEUE)
1170		ops = &noqueue_qdisc_ops;
1171	else if(dev->type == ARPHRD_CAN)
1172		ops = &pfifo_fast_ops;
1173
1174	qdisc = qdisc_create_dflt(dev_queue, ops, TC_H_ROOT, NULL);
1175	if (!qdisc)
1176		return;
1177
1178	if (!netif_is_multiqueue(dev))
1179		qdisc->flags |= TCQ_F_ONETXQUEUE | TCQ_F_NOPARENT;
1180	rcu_assign_pointer(dev_queue->qdisc_sleeping, qdisc);
1181}
1182
1183static void attach_default_qdiscs(struct net_device *dev)
1184{
1185	struct netdev_queue *txq;
1186	struct Qdisc *qdisc;
1187
1188	txq = netdev_get_tx_queue(dev, 0);
1189
1190	if (!netif_is_multiqueue(dev) ||
1191	    dev->priv_flags & IFF_NO_QUEUE) {
1192		netdev_for_each_tx_queue(dev, attach_one_default_qdisc, NULL);
1193		qdisc = rtnl_dereference(txq->qdisc_sleeping);
1194		rcu_assign_pointer(dev->qdisc, qdisc);
1195		qdisc_refcount_inc(qdisc);
1196	} else {
1197		qdisc = qdisc_create_dflt(txq, &mq_qdisc_ops, TC_H_ROOT, NULL);
1198		if (qdisc) {
1199			rcu_assign_pointer(dev->qdisc, qdisc);
1200			qdisc->ops->attach(qdisc);
1201		}
1202	}
1203	qdisc = rtnl_dereference(dev->qdisc);
1204
1205	/* Detect default qdisc setup/init failed and fallback to "noqueue" */
1206	if (qdisc == &noop_qdisc) {
1207		netdev_warn(dev, "default qdisc (%s) fail, fallback to %s\n",
1208			    default_qdisc_ops->id, noqueue_qdisc_ops.id);
1209		netdev_for_each_tx_queue(dev, shutdown_scheduler_queue, &noop_qdisc);
1210		dev->priv_flags |= IFF_NO_QUEUE;
1211		netdev_for_each_tx_queue(dev, attach_one_default_qdisc, NULL);
1212		qdisc = rtnl_dereference(txq->qdisc_sleeping);
1213		rcu_assign_pointer(dev->qdisc, qdisc);
1214		qdisc_refcount_inc(qdisc);
1215		dev->priv_flags ^= IFF_NO_QUEUE;
1216	}
1217
1218#ifdef CONFIG_NET_SCHED
1219	if (qdisc != &noop_qdisc)
1220		qdisc_hash_add(qdisc, false);
1221#endif
1222}
1223
1224static void transition_one_qdisc(struct net_device *dev,
1225				 struct netdev_queue *dev_queue,
1226				 void *_need_watchdog)
1227{
1228	struct Qdisc *new_qdisc = rtnl_dereference(dev_queue->qdisc_sleeping);
1229	int *need_watchdog_p = _need_watchdog;
1230
1231	if (!(new_qdisc->flags & TCQ_F_BUILTIN))
1232		clear_bit(__QDISC_STATE_DEACTIVATED, &new_qdisc->state);
1233
1234	rcu_assign_pointer(dev_queue->qdisc, new_qdisc);
1235	if (need_watchdog_p) {
1236		WRITE_ONCE(dev_queue->trans_start, 0);
1237		*need_watchdog_p = 1;
1238	}
1239}
1240
1241void dev_activate(struct net_device *dev)
1242{
1243	int need_watchdog;
1244
1245	/* No queueing discipline is attached to device;
1246	 * create default one for devices, which need queueing
1247	 * and noqueue_qdisc for virtual interfaces
1248	 */
1249
1250	if (rtnl_dereference(dev->qdisc) == &noop_qdisc)
1251		attach_default_qdiscs(dev);
1252
1253	if (!netif_carrier_ok(dev))
1254		/* Delay activation until next carrier-on event */
1255		return;
1256
1257	need_watchdog = 0;
1258	netdev_for_each_tx_queue(dev, transition_one_qdisc, &need_watchdog);
1259	if (dev_ingress_queue(dev))
1260		transition_one_qdisc(dev, dev_ingress_queue(dev), NULL);
1261
1262	if (need_watchdog) {
1263		netif_trans_update(dev);
1264		netdev_watchdog_up(dev);
1265	}
1266}
1267EXPORT_SYMBOL(dev_activate);
1268
1269static void qdisc_deactivate(struct Qdisc *qdisc)
1270{
1271	if (qdisc->flags & TCQ_F_BUILTIN)
1272		return;
1273
1274	set_bit(__QDISC_STATE_DEACTIVATED, &qdisc->state);
1275}
1276
1277static void dev_deactivate_queue(struct net_device *dev,
1278				 struct netdev_queue *dev_queue,
1279				 void *_sync_needed)
1280{
1281	bool *sync_needed = _sync_needed;
1282	struct Qdisc *qdisc;
1283
1284	qdisc = rtnl_dereference(dev_queue->qdisc);
1285	if (qdisc) {
1286		if (qdisc->enqueue)
1287			*sync_needed = true;
1288		qdisc_deactivate(qdisc);
1289		rcu_assign_pointer(dev_queue->qdisc, &noop_qdisc);
1290	}
1291}
1292
1293static bool some_qdisc_is_busy(struct net_device *dev)
1294{
1295	unsigned int i;
1296
1297	for (i = 0; i < dev->num_tx_queues; i++) {
1298		struct netdev_queue *dev_queue;
1299		spinlock_t *root_lock;
1300		struct Qdisc *q;
1301		int val;
1302
1303		dev_queue = netdev_get_tx_queue(dev, i);
1304		q = rtnl_dereference(dev_queue->qdisc_sleeping);
1305
1306		root_lock = qdisc_lock(q);
1307		spin_lock_bh(root_lock);
1308
1309		val = (qdisc_is_running(q) ||
1310		       test_bit(__QDISC_STATE_SCHED, &q->state));
1311
1312		spin_unlock_bh(root_lock);
1313
1314		if (val)
1315			return true;
1316	}
1317	return false;
1318}
1319
1320/**
1321 * 	dev_deactivate_many - deactivate transmissions on several devices
1322 * 	@head: list of devices to deactivate
1323 *
1324 *	This function returns only when all outstanding transmissions
1325 *	have completed, unless all devices are in dismantle phase.
1326 */
1327void dev_deactivate_many(struct list_head *head)
1328{
1329	bool sync_needed = false;
1330	struct net_device *dev;
1331
1332	list_for_each_entry(dev, head, close_list) {
1333		netdev_for_each_tx_queue(dev, dev_deactivate_queue,
1334					 &sync_needed);
1335		if (dev_ingress_queue(dev))
1336			dev_deactivate_queue(dev, dev_ingress_queue(dev),
1337					     &sync_needed);
1338
1339		netdev_watchdog_down(dev);
1340	}
1341
1342	/* Wait for outstanding qdisc enqueuing calls. */
1343	if (sync_needed)
1344		synchronize_net();
1345
1346	list_for_each_entry(dev, head, close_list) {
1347		netdev_for_each_tx_queue(dev, dev_reset_queue, NULL);
1348
1349		if (dev_ingress_queue(dev))
1350			dev_reset_queue(dev, dev_ingress_queue(dev), NULL);
1351	}
1352
1353	/* Wait for outstanding qdisc_run calls. */
1354	list_for_each_entry(dev, head, close_list) {
1355		while (some_qdisc_is_busy(dev)) {
1356			/* wait_event() would avoid this sleep-loop but would
1357			 * require expensive checks in the fast paths of packet
1358			 * processing which isn't worth it.
1359			 */
1360			schedule_timeout_uninterruptible(1);
1361		}
1362	}
1363}
1364
1365void dev_deactivate(struct net_device *dev)
1366{
1367	LIST_HEAD(single);
1368
1369	list_add(&dev->close_list, &single);
1370	dev_deactivate_many(&single);
1371	list_del(&single);
1372}
1373EXPORT_SYMBOL(dev_deactivate);
1374
1375static int qdisc_change_tx_queue_len(struct net_device *dev,
1376				     struct netdev_queue *dev_queue)
1377{
1378	struct Qdisc *qdisc = rtnl_dereference(dev_queue->qdisc_sleeping);
1379	const struct Qdisc_ops *ops = qdisc->ops;
1380
1381	if (ops->change_tx_queue_len)
1382		return ops->change_tx_queue_len(qdisc, dev->tx_queue_len);
1383	return 0;
1384}
1385
1386void dev_qdisc_change_real_num_tx(struct net_device *dev,
1387				  unsigned int new_real_tx)
1388{
1389	struct Qdisc *qdisc = rtnl_dereference(dev->qdisc);
1390
1391	if (qdisc->ops->change_real_num_tx)
1392		qdisc->ops->change_real_num_tx(qdisc, new_real_tx);
1393}
1394
1395void mq_change_real_num_tx(struct Qdisc *sch, unsigned int new_real_tx)
1396{
1397#ifdef CONFIG_NET_SCHED
1398	struct net_device *dev = qdisc_dev(sch);
1399	struct Qdisc *qdisc;
1400	unsigned int i;
1401
1402	for (i = new_real_tx; i < dev->real_num_tx_queues; i++) {
1403		qdisc = rtnl_dereference(netdev_get_tx_queue(dev, i)->qdisc_sleeping);
1404		/* Only update the default qdiscs we created,
1405		 * qdiscs with handles are always hashed.
1406		 */
1407		if (qdisc != &noop_qdisc && !qdisc->handle)
1408			qdisc_hash_del(qdisc);
1409	}
1410	for (i = dev->real_num_tx_queues; i < new_real_tx; i++) {
1411		qdisc = rtnl_dereference(netdev_get_tx_queue(dev, i)->qdisc_sleeping);
1412		if (qdisc != &noop_qdisc && !qdisc->handle)
1413			qdisc_hash_add(qdisc, false);
1414	}
1415#endif
1416}
1417EXPORT_SYMBOL(mq_change_real_num_tx);
1418
1419int dev_qdisc_change_tx_queue_len(struct net_device *dev)
1420{
1421	bool up = dev->flags & IFF_UP;
1422	unsigned int i;
1423	int ret = 0;
1424
1425	if (up)
1426		dev_deactivate(dev);
1427
1428	for (i = 0; i < dev->num_tx_queues; i++) {
1429		ret = qdisc_change_tx_queue_len(dev, &dev->_tx[i]);
1430
1431		/* TODO: revert changes on a partial failure */
1432		if (ret)
1433			break;
1434	}
1435
1436	if (up)
1437		dev_activate(dev);
1438	return ret;
1439}
1440
1441static void dev_init_scheduler_queue(struct net_device *dev,
1442				     struct netdev_queue *dev_queue,
1443				     void *_qdisc)
1444{
1445	struct Qdisc *qdisc = _qdisc;
1446
1447	rcu_assign_pointer(dev_queue->qdisc, qdisc);
1448	rcu_assign_pointer(dev_queue->qdisc_sleeping, qdisc);
1449}
1450
1451void dev_init_scheduler(struct net_device *dev)
1452{
1453	rcu_assign_pointer(dev->qdisc, &noop_qdisc);
1454	netdev_for_each_tx_queue(dev, dev_init_scheduler_queue, &noop_qdisc);
1455	if (dev_ingress_queue(dev))
1456		dev_init_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc);
1457
1458	timer_setup(&dev->watchdog_timer, dev_watchdog, 0);
1459}
1460
1461void dev_shutdown(struct net_device *dev)
1462{
1463	netdev_for_each_tx_queue(dev, shutdown_scheduler_queue, &noop_qdisc);
1464	if (dev_ingress_queue(dev))
1465		shutdown_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc);
1466	qdisc_put(rtnl_dereference(dev->qdisc));
1467	rcu_assign_pointer(dev->qdisc, &noop_qdisc);
1468
1469	WARN_ON(timer_pending(&dev->watchdog_timer));
1470}
1471
1472/**
1473 * psched_ratecfg_precompute__() - Pre-compute values for reciprocal division
1474 * @rate:   Rate to compute reciprocal division values of
1475 * @mult:   Multiplier for reciprocal division
1476 * @shift:  Shift for reciprocal division
1477 *
1478 * The multiplier and shift for reciprocal division by rate are stored
1479 * in mult and shift.
1480 *
1481 * The deal here is to replace a divide by a reciprocal one
1482 * in fast path (a reciprocal divide is a multiply and a shift)
1483 *
1484 * Normal formula would be :
1485 *  time_in_ns = (NSEC_PER_SEC * len) / rate_bps
1486 *
1487 * We compute mult/shift to use instead :
1488 *  time_in_ns = (len * mult) >> shift;
1489 *
1490 * We try to get the highest possible mult value for accuracy,
1491 * but have to make sure no overflows will ever happen.
1492 *
1493 * reciprocal_value() is not used here it doesn't handle 64-bit values.
1494 */
1495static void psched_ratecfg_precompute__(u64 rate, u32 *mult, u8 *shift)
1496{
1497	u64 factor = NSEC_PER_SEC;
1498
1499	*mult = 1;
1500	*shift = 0;
1501
1502	if (rate <= 0)
1503		return;
1504
1505	for (;;) {
1506		*mult = div64_u64(factor, rate);
1507		if (*mult & (1U << 31) || factor & (1ULL << 63))
1508			break;
1509		factor <<= 1;
1510		(*shift)++;
1511	}
1512}
1513
1514void psched_ratecfg_precompute(struct psched_ratecfg *r,
1515			       const struct tc_ratespec *conf,
1516			       u64 rate64)
1517{
1518	memset(r, 0, sizeof(*r));
1519	r->overhead = conf->overhead;
1520	r->mpu = conf->mpu;
1521	r->rate_bytes_ps = max_t(u64, conf->rate, rate64);
1522	r->linklayer = (conf->linklayer & TC_LINKLAYER_MASK);
1523	psched_ratecfg_precompute__(r->rate_bytes_ps, &r->mult, &r->shift);
1524}
1525EXPORT_SYMBOL(psched_ratecfg_precompute);
1526
1527void psched_ppscfg_precompute(struct psched_pktrate *r, u64 pktrate64)
1528{
1529	r->rate_pkts_ps = pktrate64;
1530	psched_ratecfg_precompute__(r->rate_pkts_ps, &r->mult, &r->shift);
1531}
1532EXPORT_SYMBOL(psched_ppscfg_precompute);
1533
1534void mini_qdisc_pair_swap(struct mini_Qdisc_pair *miniqp,
1535			  struct tcf_proto *tp_head)
1536{
1537	/* Protected with chain0->filter_chain_lock.
1538	 * Can't access chain directly because tp_head can be NULL.
1539	 */
1540	struct mini_Qdisc *miniq_old =
1541		rcu_dereference_protected(*miniqp->p_miniq, 1);
1542	struct mini_Qdisc *miniq;
1543
1544	if (!tp_head) {
1545		RCU_INIT_POINTER(*miniqp->p_miniq, NULL);
1546	} else {
1547		miniq = miniq_old != &miniqp->miniq1 ?
1548			&miniqp->miniq1 : &miniqp->miniq2;
1549
1550		/* We need to make sure that readers won't see the miniq
1551		 * we are about to modify. So ensure that at least one RCU
1552		 * grace period has elapsed since the miniq was made
1553		 * inactive.
1554		 */
1555		if (IS_ENABLED(CONFIG_PREEMPT_RT))
1556			cond_synchronize_rcu(miniq->rcu_state);
1557		else if (!poll_state_synchronize_rcu(miniq->rcu_state))
1558			synchronize_rcu_expedited();
1559
1560		miniq->filter_list = tp_head;
1561		rcu_assign_pointer(*miniqp->p_miniq, miniq);
1562	}
1563
1564	if (miniq_old)
1565		/* This is counterpart of the rcu sync above. We need to
1566		 * block potential new user of miniq_old until all readers
1567		 * are not seeing it.
1568		 */
1569		miniq_old->rcu_state = start_poll_synchronize_rcu();
1570}
1571EXPORT_SYMBOL(mini_qdisc_pair_swap);
1572
1573void mini_qdisc_pair_block_init(struct mini_Qdisc_pair *miniqp,
1574				struct tcf_block *block)
1575{
1576	miniqp->miniq1.block = block;
1577	miniqp->miniq2.block = block;
1578}
1579EXPORT_SYMBOL(mini_qdisc_pair_block_init);
1580
1581void mini_qdisc_pair_init(struct mini_Qdisc_pair *miniqp, struct Qdisc *qdisc,
1582			  struct mini_Qdisc __rcu **p_miniq)
1583{
1584	miniqp->miniq1.cpu_bstats = qdisc->cpu_bstats;
1585	miniqp->miniq1.cpu_qstats = qdisc->cpu_qstats;
1586	miniqp->miniq2.cpu_bstats = qdisc->cpu_bstats;
1587	miniqp->miniq2.cpu_qstats = qdisc->cpu_qstats;
1588	miniqp->miniq1.rcu_state = get_state_synchronize_rcu();
1589	miniqp->miniq2.rcu_state = miniqp->miniq1.rcu_state;
1590	miniqp->p_miniq = p_miniq;
1591}
1592EXPORT_SYMBOL(mini_qdisc_pair_init);