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 <linux/skb_array.h> 30 #include <linux/if_macvlan.h> 31 #include <net/sch_generic.h> 32 #include <net/pkt_sched.h> 33 #include <net/dst.h> 34 #include <trace/events/qdisc.h> 35 #include <net/xfrm.h> 36 37 /* Qdisc to use by default */ 38 const struct Qdisc_ops *default_qdisc_ops = &pfifo_fast_ops; 39 EXPORT_SYMBOL(default_qdisc_ops); 40 41 /* Main transmission queue. */ 42 43 /* Modifications to data participating in scheduling must be protected with 44 * qdisc_lock(qdisc) spinlock. 45 * 46 * The idea is the following: 47 * - enqueue, dequeue are serialized via qdisc root lock 48 * - ingress filtering is also serialized via qdisc root lock 49 * - updates to tree and tree walking are only done under the rtnl mutex. 50 */ 51 52 static inline struct sk_buff *__skb_dequeue_bad_txq(struct Qdisc *q) 53 { 54 const struct netdev_queue *txq = q->dev_queue; 55 spinlock_t *lock = NULL; 56 struct sk_buff *skb; 57 58 if (q->flags & TCQ_F_NOLOCK) { 59 lock = qdisc_lock(q); 60 spin_lock(lock); 61 } 62 63 skb = skb_peek(&q->skb_bad_txq); 64 if (skb) { 65 /* check the reason of requeuing without tx lock first */ 66 txq = skb_get_tx_queue(txq->dev, skb); 67 if (!netif_xmit_frozen_or_stopped(txq)) { 68 skb = __skb_dequeue(&q->skb_bad_txq); 69 if (qdisc_is_percpu_stats(q)) { 70 qdisc_qstats_cpu_backlog_dec(q, skb); 71 qdisc_qstats_cpu_qlen_dec(q); 72 } else { 73 qdisc_qstats_backlog_dec(q, skb); 74 q->q.qlen--; 75 } 76 } else { 77 skb = NULL; 78 } 79 } 80 81 if (lock) 82 spin_unlock(lock); 83 84 return skb; 85 } 86 87 static inline struct sk_buff *qdisc_dequeue_skb_bad_txq(struct Qdisc *q) 88 { 89 struct sk_buff *skb = skb_peek(&q->skb_bad_txq); 90 91 if (unlikely(skb)) 92 skb = __skb_dequeue_bad_txq(q); 93 94 return skb; 95 } 96 97 static inline void qdisc_enqueue_skb_bad_txq(struct Qdisc *q, 98 struct sk_buff *skb) 99 { 100 spinlock_t *lock = NULL; 101 102 if (q->flags & TCQ_F_NOLOCK) { 103 lock = qdisc_lock(q); 104 spin_lock(lock); 105 } 106 107 __skb_queue_tail(&q->skb_bad_txq, skb); 108 109 if (lock) 110 spin_unlock(lock); 111 } 112 113 static inline int __dev_requeue_skb(struct sk_buff *skb, struct Qdisc *q) 114 { 115 __skb_queue_head(&q->gso_skb, skb); 116 q->qstats.requeues++; 117 qdisc_qstats_backlog_inc(q, skb); 118 q->q.qlen++; /* it's still part of the queue */ 119 __netif_schedule(q); 120 121 return 0; 122 } 123 124 static inline int dev_requeue_skb_locked(struct sk_buff *skb, struct Qdisc *q) 125 { 126 spinlock_t *lock = qdisc_lock(q); 127 128 spin_lock(lock); 129 __skb_queue_tail(&q->gso_skb, skb); 130 spin_unlock(lock); 131 132 qdisc_qstats_cpu_requeues_inc(q); 133 qdisc_qstats_cpu_backlog_inc(q, skb); 134 qdisc_qstats_cpu_qlen_inc(q); 135 __netif_schedule(q); 136 137 return 0; 138 } 139 140 static inline int dev_requeue_skb(struct sk_buff *skb, struct Qdisc *q) 141 { 142 if (q->flags & TCQ_F_NOLOCK) 143 return dev_requeue_skb_locked(skb, q); 144 else 145 return __dev_requeue_skb(skb, q); 146 } 147 148 static void try_bulk_dequeue_skb(struct Qdisc *q, 149 struct sk_buff *skb, 150 const struct netdev_queue *txq, 151 int *packets) 152 { 153 int bytelimit = qdisc_avail_bulklimit(txq) - skb->len; 154 155 while (bytelimit > 0) { 156 struct sk_buff *nskb = q->dequeue(q); 157 158 if (!nskb) 159 break; 160 161 bytelimit -= nskb->len; /* covers GSO len */ 162 skb->next = nskb; 163 skb = nskb; 164 (*packets)++; /* GSO counts as one pkt */ 165 } 166 skb->next = NULL; 167 } 168 169 /* This variant of try_bulk_dequeue_skb() makes sure 170 * all skbs in the chain are for the same txq 171 */ 172 static void try_bulk_dequeue_skb_slow(struct Qdisc *q, 173 struct sk_buff *skb, 174 int *packets) 175 { 176 int mapping = skb_get_queue_mapping(skb); 177 struct sk_buff *nskb; 178 int cnt = 0; 179 180 do { 181 nskb = q->dequeue(q); 182 if (!nskb) 183 break; 184 if (unlikely(skb_get_queue_mapping(nskb) != mapping)) { 185 qdisc_enqueue_skb_bad_txq(q, nskb); 186 187 if (qdisc_is_percpu_stats(q)) { 188 qdisc_qstats_cpu_backlog_inc(q, nskb); 189 qdisc_qstats_cpu_qlen_inc(q); 190 } else { 191 qdisc_qstats_backlog_inc(q, nskb); 192 q->q.qlen++; 193 } 194 break; 195 } 196 skb->next = nskb; 197 skb = nskb; 198 } while (++cnt < 8); 199 (*packets) += cnt; 200 skb->next = NULL; 201 } 202 203 /* Note that dequeue_skb can possibly return a SKB list (via skb->next). 204 * A requeued skb (via q->gso_skb) can also be a SKB list. 205 */ 206 static struct sk_buff *dequeue_skb(struct Qdisc *q, bool *validate, 207 int *packets) 208 { 209 const struct netdev_queue *txq = q->dev_queue; 210 struct sk_buff *skb = NULL; 211 212 *packets = 1; 213 if (unlikely(!skb_queue_empty(&q->gso_skb))) { 214 spinlock_t *lock = NULL; 215 216 if (q->flags & TCQ_F_NOLOCK) { 217 lock = qdisc_lock(q); 218 spin_lock(lock); 219 } 220 221 skb = skb_peek(&q->gso_skb); 222 223 /* skb may be null if another cpu pulls gso_skb off in between 224 * empty check and lock. 225 */ 226 if (!skb) { 227 if (lock) 228 spin_unlock(lock); 229 goto validate; 230 } 231 232 /* skb in gso_skb were already validated */ 233 *validate = false; 234 if (xfrm_offload(skb)) 235 *validate = true; 236 /* check the reason of requeuing without tx lock first */ 237 txq = skb_get_tx_queue(txq->dev, skb); 238 if (!netif_xmit_frozen_or_stopped(txq)) { 239 skb = __skb_dequeue(&q->gso_skb); 240 if (qdisc_is_percpu_stats(q)) { 241 qdisc_qstats_cpu_backlog_dec(q, skb); 242 qdisc_qstats_cpu_qlen_dec(q); 243 } else { 244 qdisc_qstats_backlog_dec(q, skb); 245 q->q.qlen--; 246 } 247 } else { 248 skb = NULL; 249 } 250 if (lock) 251 spin_unlock(lock); 252 goto trace; 253 } 254 validate: 255 *validate = true; 256 257 if ((q->flags & TCQ_F_ONETXQUEUE) && 258 netif_xmit_frozen_or_stopped(txq)) 259 return skb; 260 261 skb = qdisc_dequeue_skb_bad_txq(q); 262 if (unlikely(skb)) 263 goto bulk; 264 skb = q->dequeue(q); 265 if (skb) { 266 bulk: 267 if (qdisc_may_bulk(q)) 268 try_bulk_dequeue_skb(q, skb, txq, packets); 269 else 270 try_bulk_dequeue_skb_slow(q, skb, packets); 271 } 272 trace: 273 trace_qdisc_dequeue(q, txq, *packets, skb); 274 return skb; 275 } 276 277 /* 278 * Transmit possibly several skbs, and handle the return status as 279 * required. Owning running seqcount bit guarantees that 280 * only one CPU can execute this function. 281 * 282 * Returns to the caller: 283 * false - hardware queue frozen backoff 284 * true - feel free to send more pkts 285 */ 286 bool sch_direct_xmit(struct sk_buff *skb, struct Qdisc *q, 287 struct net_device *dev, struct netdev_queue *txq, 288 spinlock_t *root_lock, bool validate) 289 { 290 int ret = NETDEV_TX_BUSY; 291 bool again = false; 292 293 /* And release qdisc */ 294 if (root_lock) 295 spin_unlock(root_lock); 296 297 /* Note that we validate skb (GSO, checksum, ...) outside of locks */ 298 if (validate) 299 skb = validate_xmit_skb_list(skb, dev, &again); 300 301 #ifdef CONFIG_XFRM_OFFLOAD 302 if (unlikely(again)) { 303 if (root_lock) 304 spin_lock(root_lock); 305 306 dev_requeue_skb(skb, q); 307 return false; 308 } 309 #endif 310 311 if (likely(skb)) { 312 HARD_TX_LOCK(dev, txq, smp_processor_id()); 313 if (!netif_xmit_frozen_or_stopped(txq)) 314 skb = dev_hard_start_xmit(skb, dev, txq, &ret); 315 316 HARD_TX_UNLOCK(dev, txq); 317 } else { 318 if (root_lock) 319 spin_lock(root_lock); 320 return true; 321 } 322 323 if (root_lock) 324 spin_lock(root_lock); 325 326 if (!dev_xmit_complete(ret)) { 327 /* Driver returned NETDEV_TX_BUSY - requeue skb */ 328 if (unlikely(ret != NETDEV_TX_BUSY)) 329 net_warn_ratelimited("BUG %s code %d qlen %d\n", 330 dev->name, ret, q->q.qlen); 331 332 dev_requeue_skb(skb, q); 333 return false; 334 } 335 336 if (ret && netif_xmit_frozen_or_stopped(txq)) 337 return false; 338 339 return true; 340 } 341 342 /* 343 * NOTE: Called under qdisc_lock(q) with locally disabled BH. 344 * 345 * running seqcount guarantees only one CPU can process 346 * this qdisc at a time. qdisc_lock(q) serializes queue accesses for 347 * this queue. 348 * 349 * netif_tx_lock serializes accesses to device driver. 350 * 351 * qdisc_lock(q) and netif_tx_lock are mutually exclusive, 352 * if one is grabbed, another must be free. 353 * 354 * Note, that this procedure can be called by a watchdog timer 355 * 356 * Returns to the caller: 357 * 0 - queue is empty or throttled. 358 * >0 - queue is not empty. 359 * 360 */ 361 static inline bool qdisc_restart(struct Qdisc *q, int *packets) 362 { 363 spinlock_t *root_lock = NULL; 364 struct netdev_queue *txq; 365 struct net_device *dev; 366 struct sk_buff *skb; 367 bool validate; 368 369 /* Dequeue packet */ 370 skb = dequeue_skb(q, &validate, packets); 371 if (unlikely(!skb)) 372 return false; 373 374 if (!(q->flags & TCQ_F_NOLOCK)) 375 root_lock = qdisc_lock(q); 376 377 dev = qdisc_dev(q); 378 txq = skb_get_tx_queue(dev, skb); 379 380 return sch_direct_xmit(skb, q, dev, txq, root_lock, validate); 381 } 382 383 void __qdisc_run(struct Qdisc *q) 384 { 385 int quota = dev_tx_weight; 386 int packets; 387 388 while (qdisc_restart(q, &packets)) { 389 /* 390 * Ordered by possible occurrence: Postpone processing if 391 * 1. we've exceeded packet quota 392 * 2. another process needs the CPU; 393 */ 394 quota -= packets; 395 if (quota <= 0 || need_resched()) { 396 __netif_schedule(q); 397 break; 398 } 399 } 400 } 401 402 unsigned long dev_trans_start(struct net_device *dev) 403 { 404 unsigned long val, res; 405 unsigned int i; 406 407 if (is_vlan_dev(dev)) 408 dev = vlan_dev_real_dev(dev); 409 else if (netif_is_macvlan(dev)) 410 dev = macvlan_dev_real_dev(dev); 411 res = netdev_get_tx_queue(dev, 0)->trans_start; 412 for (i = 1; i < dev->num_tx_queues; i++) { 413 val = netdev_get_tx_queue(dev, i)->trans_start; 414 if (val && time_after(val, res)) 415 res = val; 416 } 417 418 return res; 419 } 420 EXPORT_SYMBOL(dev_trans_start); 421 422 static void dev_watchdog(struct timer_list *t) 423 { 424 struct net_device *dev = from_timer(dev, t, watchdog_timer); 425 426 netif_tx_lock(dev); 427 if (!qdisc_tx_is_noop(dev)) { 428 if (netif_device_present(dev) && 429 netif_running(dev) && 430 netif_carrier_ok(dev)) { 431 int some_queue_timedout = 0; 432 unsigned int i; 433 unsigned long trans_start; 434 435 for (i = 0; i < dev->num_tx_queues; i++) { 436 struct netdev_queue *txq; 437 438 txq = netdev_get_tx_queue(dev, i); 439 trans_start = txq->trans_start; 440 if (netif_xmit_stopped(txq) && 441 time_after(jiffies, (trans_start + 442 dev->watchdog_timeo))) { 443 some_queue_timedout = 1; 444 txq->trans_timeout++; 445 break; 446 } 447 } 448 449 if (some_queue_timedout) { 450 WARN_ONCE(1, KERN_INFO "NETDEV WATCHDOG: %s (%s): transmit queue %u timed out\n", 451 dev->name, netdev_drivername(dev), i); 452 dev->netdev_ops->ndo_tx_timeout(dev); 453 } 454 if (!mod_timer(&dev->watchdog_timer, 455 round_jiffies(jiffies + 456 dev->watchdog_timeo))) 457 dev_hold(dev); 458 } 459 } 460 netif_tx_unlock(dev); 461 462 dev_put(dev); 463 } 464 465 void __netdev_watchdog_up(struct net_device *dev) 466 { 467 if (dev->netdev_ops->ndo_tx_timeout) { 468 if (dev->watchdog_timeo <= 0) 469 dev->watchdog_timeo = 5*HZ; 470 if (!mod_timer(&dev->watchdog_timer, 471 round_jiffies(jiffies + dev->watchdog_timeo))) 472 dev_hold(dev); 473 } 474 } 475 476 static void dev_watchdog_up(struct net_device *dev) 477 { 478 __netdev_watchdog_up(dev); 479 } 480 481 static void dev_watchdog_down(struct net_device *dev) 482 { 483 netif_tx_lock_bh(dev); 484 if (del_timer(&dev->watchdog_timer)) 485 dev_put(dev); 486 netif_tx_unlock_bh(dev); 487 } 488 489 /** 490 * netif_carrier_on - set carrier 491 * @dev: network device 492 * 493 * Device has detected that carrier. 494 */ 495 void netif_carrier_on(struct net_device *dev) 496 { 497 if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state)) { 498 if (dev->reg_state == NETREG_UNINITIALIZED) 499 return; 500 atomic_inc(&dev->carrier_changes); 501 linkwatch_fire_event(dev); 502 if (netif_running(dev)) 503 __netdev_watchdog_up(dev); 504 } 505 } 506 EXPORT_SYMBOL(netif_carrier_on); 507 508 /** 509 * netif_carrier_off - clear carrier 510 * @dev: network device 511 * 512 * Device has detected loss of carrier. 513 */ 514 void netif_carrier_off(struct net_device *dev) 515 { 516 if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state)) { 517 if (dev->reg_state == NETREG_UNINITIALIZED) 518 return; 519 atomic_inc(&dev->carrier_changes); 520 linkwatch_fire_event(dev); 521 } 522 } 523 EXPORT_SYMBOL(netif_carrier_off); 524 525 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces 526 under all circumstances. It is difficult to invent anything faster or 527 cheaper. 528 */ 529 530 static int noop_enqueue(struct sk_buff *skb, struct Qdisc *qdisc, 531 struct sk_buff **to_free) 532 { 533 __qdisc_drop(skb, to_free); 534 return NET_XMIT_CN; 535 } 536 537 static struct sk_buff *noop_dequeue(struct Qdisc *qdisc) 538 { 539 return NULL; 540 } 541 542 struct Qdisc_ops noop_qdisc_ops __read_mostly = { 543 .id = "noop", 544 .priv_size = 0, 545 .enqueue = noop_enqueue, 546 .dequeue = noop_dequeue, 547 .peek = noop_dequeue, 548 .owner = THIS_MODULE, 549 }; 550 551 static struct netdev_queue noop_netdev_queue = { 552 .qdisc = &noop_qdisc, 553 .qdisc_sleeping = &noop_qdisc, 554 }; 555 556 struct Qdisc noop_qdisc = { 557 .enqueue = noop_enqueue, 558 .dequeue = noop_dequeue, 559 .flags = TCQ_F_BUILTIN, 560 .ops = &noop_qdisc_ops, 561 .q.lock = __SPIN_LOCK_UNLOCKED(noop_qdisc.q.lock), 562 .dev_queue = &noop_netdev_queue, 563 .running = SEQCNT_ZERO(noop_qdisc.running), 564 .busylock = __SPIN_LOCK_UNLOCKED(noop_qdisc.busylock), 565 }; 566 EXPORT_SYMBOL(noop_qdisc); 567 568 static int noqueue_init(struct Qdisc *qdisc, struct nlattr *opt, 569 struct netlink_ext_ack *extack) 570 { 571 /* register_qdisc() assigns a default of noop_enqueue if unset, 572 * but __dev_queue_xmit() treats noqueue only as such 573 * if this is NULL - so clear it here. */ 574 qdisc->enqueue = NULL; 575 return 0; 576 } 577 578 struct Qdisc_ops noqueue_qdisc_ops __read_mostly = { 579 .id = "noqueue", 580 .priv_size = 0, 581 .init = noqueue_init, 582 .enqueue = noop_enqueue, 583 .dequeue = noop_dequeue, 584 .peek = noop_dequeue, 585 .owner = THIS_MODULE, 586 }; 587 588 static const u8 prio2band[TC_PRIO_MAX + 1] = { 589 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 590 }; 591 592 /* 3-band FIFO queue: old style, but should be a bit faster than 593 generic prio+fifo combination. 594 */ 595 596 #define PFIFO_FAST_BANDS 3 597 598 /* 599 * Private data for a pfifo_fast scheduler containing: 600 * - rings for priority bands 601 */ 602 struct pfifo_fast_priv { 603 struct skb_array q[PFIFO_FAST_BANDS]; 604 }; 605 606 static inline struct skb_array *band2list(struct pfifo_fast_priv *priv, 607 int band) 608 { 609 return &priv->q[band]; 610 } 611 612 static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc *qdisc, 613 struct sk_buff **to_free) 614 { 615 int band = prio2band[skb->priority & TC_PRIO_MAX]; 616 struct pfifo_fast_priv *priv = qdisc_priv(qdisc); 617 struct skb_array *q = band2list(priv, band); 618 int err; 619 620 err = skb_array_produce(q, skb); 621 622 if (unlikely(err)) 623 return qdisc_drop_cpu(skb, qdisc, to_free); 624 625 qdisc_qstats_cpu_qlen_inc(qdisc); 626 qdisc_qstats_cpu_backlog_inc(qdisc, skb); 627 return NET_XMIT_SUCCESS; 628 } 629 630 static struct sk_buff *pfifo_fast_dequeue(struct Qdisc *qdisc) 631 { 632 struct pfifo_fast_priv *priv = qdisc_priv(qdisc); 633 struct sk_buff *skb = NULL; 634 int band; 635 636 for (band = 0; band < PFIFO_FAST_BANDS && !skb; band++) { 637 struct skb_array *q = band2list(priv, band); 638 639 if (__skb_array_empty(q)) 640 continue; 641 642 skb = skb_array_consume_bh(q); 643 } 644 if (likely(skb)) { 645 qdisc_qstats_cpu_backlog_dec(qdisc, skb); 646 qdisc_bstats_cpu_update(qdisc, skb); 647 qdisc_qstats_cpu_qlen_dec(qdisc); 648 } 649 650 return skb; 651 } 652 653 static struct sk_buff *pfifo_fast_peek(struct Qdisc *qdisc) 654 { 655 struct pfifo_fast_priv *priv = qdisc_priv(qdisc); 656 struct sk_buff *skb = NULL; 657 int band; 658 659 for (band = 0; band < PFIFO_FAST_BANDS && !skb; band++) { 660 struct skb_array *q = band2list(priv, band); 661 662 skb = __skb_array_peek(q); 663 } 664 665 return skb; 666 } 667 668 static void pfifo_fast_reset(struct Qdisc *qdisc) 669 { 670 int i, band; 671 struct pfifo_fast_priv *priv = qdisc_priv(qdisc); 672 673 for (band = 0; band < PFIFO_FAST_BANDS; band++) { 674 struct skb_array *q = band2list(priv, band); 675 struct sk_buff *skb; 676 677 /* NULL ring is possible if destroy path is due to a failed 678 * skb_array_init() in pfifo_fast_init() case. 679 */ 680 if (!q->ring.queue) 681 continue; 682 683 while ((skb = skb_array_consume_bh(q)) != NULL) 684 kfree_skb(skb); 685 } 686 687 for_each_possible_cpu(i) { 688 struct gnet_stats_queue *q = per_cpu_ptr(qdisc->cpu_qstats, i); 689 690 q->backlog = 0; 691 q->qlen = 0; 692 } 693 } 694 695 static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb) 696 { 697 struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS }; 698 699 memcpy(&opt.priomap, prio2band, TC_PRIO_MAX + 1); 700 if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt)) 701 goto nla_put_failure; 702 return skb->len; 703 704 nla_put_failure: 705 return -1; 706 } 707 708 static int pfifo_fast_init(struct Qdisc *qdisc, struct nlattr *opt, 709 struct netlink_ext_ack *extack) 710 { 711 unsigned int qlen = qdisc_dev(qdisc)->tx_queue_len; 712 struct pfifo_fast_priv *priv = qdisc_priv(qdisc); 713 int prio; 714 715 /* guard against zero length rings */ 716 if (!qlen) 717 return -EINVAL; 718 719 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) { 720 struct skb_array *q = band2list(priv, prio); 721 int err; 722 723 err = skb_array_init(q, qlen, GFP_KERNEL); 724 if (err) 725 return -ENOMEM; 726 } 727 728 /* Can by-pass the queue discipline */ 729 qdisc->flags |= TCQ_F_CAN_BYPASS; 730 return 0; 731 } 732 733 static void pfifo_fast_destroy(struct Qdisc *sch) 734 { 735 struct pfifo_fast_priv *priv = qdisc_priv(sch); 736 int prio; 737 738 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) { 739 struct skb_array *q = band2list(priv, prio); 740 741 /* NULL ring is possible if destroy path is due to a failed 742 * skb_array_init() in pfifo_fast_init() case. 743 */ 744 if (!q->ring.queue) 745 continue; 746 /* Destroy ring but no need to kfree_skb because a call to 747 * pfifo_fast_reset() has already done that work. 748 */ 749 ptr_ring_cleanup(&q->ring, NULL); 750 } 751 } 752 753 struct Qdisc_ops pfifo_fast_ops __read_mostly = { 754 .id = "pfifo_fast", 755 .priv_size = sizeof(struct pfifo_fast_priv), 756 .enqueue = pfifo_fast_enqueue, 757 .dequeue = pfifo_fast_dequeue, 758 .peek = pfifo_fast_peek, 759 .init = pfifo_fast_init, 760 .destroy = pfifo_fast_destroy, 761 .reset = pfifo_fast_reset, 762 .dump = pfifo_fast_dump, 763 .owner = THIS_MODULE, 764 .static_flags = TCQ_F_NOLOCK | TCQ_F_CPUSTATS, 765 }; 766 EXPORT_SYMBOL(pfifo_fast_ops); 767 768 static struct lock_class_key qdisc_tx_busylock; 769 static struct lock_class_key qdisc_running_key; 770 771 struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue, 772 const struct Qdisc_ops *ops, 773 struct netlink_ext_ack *extack) 774 { 775 void *p; 776 struct Qdisc *sch; 777 unsigned int size = QDISC_ALIGN(sizeof(*sch)) + ops->priv_size; 778 int err = -ENOBUFS; 779 struct net_device *dev; 780 781 if (!dev_queue) { 782 NL_SET_ERR_MSG(extack, "No device queue given"); 783 err = -EINVAL; 784 goto errout; 785 } 786 787 dev = dev_queue->dev; 788 p = kzalloc_node(size, GFP_KERNEL, 789 netdev_queue_numa_node_read(dev_queue)); 790 791 if (!p) 792 goto errout; 793 sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p); 794 /* if we got non aligned memory, ask more and do alignment ourself */ 795 if (sch != p) { 796 kfree(p); 797 p = kzalloc_node(size + QDISC_ALIGNTO - 1, GFP_KERNEL, 798 netdev_queue_numa_node_read(dev_queue)); 799 if (!p) 800 goto errout; 801 sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p); 802 sch->padded = (char *) sch - (char *) p; 803 } 804 __skb_queue_head_init(&sch->gso_skb); 805 __skb_queue_head_init(&sch->skb_bad_txq); 806 qdisc_skb_head_init(&sch->q); 807 spin_lock_init(&sch->q.lock); 808 809 if (ops->static_flags & TCQ_F_CPUSTATS) { 810 sch->cpu_bstats = 811 netdev_alloc_pcpu_stats(struct gnet_stats_basic_cpu); 812 if (!sch->cpu_bstats) 813 goto errout1; 814 815 sch->cpu_qstats = alloc_percpu(struct gnet_stats_queue); 816 if (!sch->cpu_qstats) { 817 free_percpu(sch->cpu_bstats); 818 goto errout1; 819 } 820 } 821 822 spin_lock_init(&sch->busylock); 823 lockdep_set_class(&sch->busylock, 824 dev->qdisc_tx_busylock ?: &qdisc_tx_busylock); 825 826 seqcount_init(&sch->running); 827 lockdep_set_class(&sch->running, 828 dev->qdisc_running_key ?: &qdisc_running_key); 829 830 sch->ops = ops; 831 sch->flags = ops->static_flags; 832 sch->enqueue = ops->enqueue; 833 sch->dequeue = ops->dequeue; 834 sch->dev_queue = dev_queue; 835 dev_hold(dev); 836 refcount_set(&sch->refcnt, 1); 837 838 return sch; 839 errout1: 840 kfree(p); 841 errout: 842 return ERR_PTR(err); 843 } 844 845 struct Qdisc *qdisc_create_dflt(struct netdev_queue *dev_queue, 846 const struct Qdisc_ops *ops, 847 unsigned int parentid, 848 struct netlink_ext_ack *extack) 849 { 850 struct Qdisc *sch; 851 852 if (!try_module_get(ops->owner)) { 853 NL_SET_ERR_MSG(extack, "Failed to increase module reference counter"); 854 return NULL; 855 } 856 857 sch = qdisc_alloc(dev_queue, ops, extack); 858 if (IS_ERR(sch)) { 859 module_put(ops->owner); 860 return NULL; 861 } 862 sch->parent = parentid; 863 864 if (!ops->init || ops->init(sch, NULL, extack) == 0) 865 return sch; 866 867 qdisc_destroy(sch); 868 return NULL; 869 } 870 EXPORT_SYMBOL(qdisc_create_dflt); 871 872 /* Under qdisc_lock(qdisc) and BH! */ 873 874 void qdisc_reset(struct Qdisc *qdisc) 875 { 876 const struct Qdisc_ops *ops = qdisc->ops; 877 struct sk_buff *skb, *tmp; 878 879 if (ops->reset) 880 ops->reset(qdisc); 881 882 skb_queue_walk_safe(&qdisc->gso_skb, skb, tmp) { 883 __skb_unlink(skb, &qdisc->gso_skb); 884 kfree_skb_list(skb); 885 } 886 887 skb_queue_walk_safe(&qdisc->skb_bad_txq, skb, tmp) { 888 __skb_unlink(skb, &qdisc->skb_bad_txq); 889 kfree_skb_list(skb); 890 } 891 892 qdisc->q.qlen = 0; 893 qdisc->qstats.backlog = 0; 894 } 895 EXPORT_SYMBOL(qdisc_reset); 896 897 static void qdisc_free(struct Qdisc *qdisc) 898 { 899 if (qdisc_is_percpu_stats(qdisc)) { 900 free_percpu(qdisc->cpu_bstats); 901 free_percpu(qdisc->cpu_qstats); 902 } 903 904 kfree((char *) qdisc - qdisc->padded); 905 } 906 907 void qdisc_destroy(struct Qdisc *qdisc) 908 { 909 const struct Qdisc_ops *ops = qdisc->ops; 910 struct sk_buff *skb, *tmp; 911 912 if (qdisc->flags & TCQ_F_BUILTIN || 913 !refcount_dec_and_test(&qdisc->refcnt)) 914 return; 915 916 #ifdef CONFIG_NET_SCHED 917 qdisc_hash_del(qdisc); 918 919 qdisc_put_stab(rtnl_dereference(qdisc->stab)); 920 #endif 921 gen_kill_estimator(&qdisc->rate_est); 922 if (ops->reset) 923 ops->reset(qdisc); 924 if (ops->destroy) 925 ops->destroy(qdisc); 926 927 module_put(ops->owner); 928 dev_put(qdisc_dev(qdisc)); 929 930 skb_queue_walk_safe(&qdisc->gso_skb, skb, tmp) { 931 __skb_unlink(skb, &qdisc->gso_skb); 932 kfree_skb_list(skb); 933 } 934 935 skb_queue_walk_safe(&qdisc->skb_bad_txq, skb, tmp) { 936 __skb_unlink(skb, &qdisc->skb_bad_txq); 937 kfree_skb_list(skb); 938 } 939 940 qdisc_free(qdisc); 941 } 942 EXPORT_SYMBOL(qdisc_destroy); 943 944 /* Attach toplevel qdisc to device queue. */ 945 struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue, 946 struct Qdisc *qdisc) 947 { 948 struct Qdisc *oqdisc = dev_queue->qdisc_sleeping; 949 spinlock_t *root_lock; 950 951 root_lock = qdisc_lock(oqdisc); 952 spin_lock_bh(root_lock); 953 954 /* ... and graft new one */ 955 if (qdisc == NULL) 956 qdisc = &noop_qdisc; 957 dev_queue->qdisc_sleeping = qdisc; 958 rcu_assign_pointer(dev_queue->qdisc, &noop_qdisc); 959 960 spin_unlock_bh(root_lock); 961 962 return oqdisc; 963 } 964 EXPORT_SYMBOL(dev_graft_qdisc); 965 966 static void attach_one_default_qdisc(struct net_device *dev, 967 struct netdev_queue *dev_queue, 968 void *_unused) 969 { 970 struct Qdisc *qdisc; 971 const struct Qdisc_ops *ops = default_qdisc_ops; 972 973 if (dev->priv_flags & IFF_NO_QUEUE) 974 ops = &noqueue_qdisc_ops; 975 976 qdisc = qdisc_create_dflt(dev_queue, ops, TC_H_ROOT, NULL); 977 if (!qdisc) { 978 netdev_info(dev, "activation failed\n"); 979 return; 980 } 981 if (!netif_is_multiqueue(dev)) 982 qdisc->flags |= TCQ_F_ONETXQUEUE | TCQ_F_NOPARENT; 983 dev_queue->qdisc_sleeping = qdisc; 984 } 985 986 static void attach_default_qdiscs(struct net_device *dev) 987 { 988 struct netdev_queue *txq; 989 struct Qdisc *qdisc; 990 991 txq = netdev_get_tx_queue(dev, 0); 992 993 if (!netif_is_multiqueue(dev) || 994 dev->priv_flags & IFF_NO_QUEUE) { 995 netdev_for_each_tx_queue(dev, attach_one_default_qdisc, NULL); 996 dev->qdisc = txq->qdisc_sleeping; 997 qdisc_refcount_inc(dev->qdisc); 998 } else { 999 qdisc = qdisc_create_dflt(txq, &mq_qdisc_ops, TC_H_ROOT, NULL); 1000 if (qdisc) { 1001 dev->qdisc = qdisc; 1002 qdisc->ops->attach(qdisc); 1003 } 1004 } 1005 #ifdef CONFIG_NET_SCHED 1006 if (dev->qdisc != &noop_qdisc) 1007 qdisc_hash_add(dev->qdisc, false); 1008 #endif 1009 } 1010 1011 static void transition_one_qdisc(struct net_device *dev, 1012 struct netdev_queue *dev_queue, 1013 void *_need_watchdog) 1014 { 1015 struct Qdisc *new_qdisc = dev_queue->qdisc_sleeping; 1016 int *need_watchdog_p = _need_watchdog; 1017 1018 if (!(new_qdisc->flags & TCQ_F_BUILTIN)) 1019 clear_bit(__QDISC_STATE_DEACTIVATED, &new_qdisc->state); 1020 1021 rcu_assign_pointer(dev_queue->qdisc, new_qdisc); 1022 if (need_watchdog_p) { 1023 dev_queue->trans_start = 0; 1024 *need_watchdog_p = 1; 1025 } 1026 } 1027 1028 void dev_activate(struct net_device *dev) 1029 { 1030 int need_watchdog; 1031 1032 /* No queueing discipline is attached to device; 1033 * create default one for devices, which need queueing 1034 * and noqueue_qdisc for virtual interfaces 1035 */ 1036 1037 if (dev->qdisc == &noop_qdisc) 1038 attach_default_qdiscs(dev); 1039 1040 if (!netif_carrier_ok(dev)) 1041 /* Delay activation until next carrier-on event */ 1042 return; 1043 1044 need_watchdog = 0; 1045 netdev_for_each_tx_queue(dev, transition_one_qdisc, &need_watchdog); 1046 if (dev_ingress_queue(dev)) 1047 transition_one_qdisc(dev, dev_ingress_queue(dev), NULL); 1048 1049 if (need_watchdog) { 1050 netif_trans_update(dev); 1051 dev_watchdog_up(dev); 1052 } 1053 } 1054 EXPORT_SYMBOL(dev_activate); 1055 1056 static void dev_deactivate_queue(struct net_device *dev, 1057 struct netdev_queue *dev_queue, 1058 void *_qdisc_default) 1059 { 1060 struct Qdisc *qdisc_default = _qdisc_default; 1061 struct Qdisc *qdisc; 1062 1063 qdisc = rtnl_dereference(dev_queue->qdisc); 1064 if (qdisc) { 1065 spin_lock_bh(qdisc_lock(qdisc)); 1066 1067 if (!(qdisc->flags & TCQ_F_BUILTIN)) 1068 set_bit(__QDISC_STATE_DEACTIVATED, &qdisc->state); 1069 1070 rcu_assign_pointer(dev_queue->qdisc, qdisc_default); 1071 qdisc_reset(qdisc); 1072 1073 spin_unlock_bh(qdisc_lock(qdisc)); 1074 } 1075 } 1076 1077 static bool some_qdisc_is_busy(struct net_device *dev) 1078 { 1079 unsigned int i; 1080 1081 for (i = 0; i < dev->num_tx_queues; i++) { 1082 struct netdev_queue *dev_queue; 1083 spinlock_t *root_lock; 1084 struct Qdisc *q; 1085 int val; 1086 1087 dev_queue = netdev_get_tx_queue(dev, i); 1088 q = dev_queue->qdisc_sleeping; 1089 1090 if (q->flags & TCQ_F_NOLOCK) { 1091 val = test_bit(__QDISC_STATE_SCHED, &q->state); 1092 } else { 1093 root_lock = qdisc_lock(q); 1094 spin_lock_bh(root_lock); 1095 1096 val = (qdisc_is_running(q) || 1097 test_bit(__QDISC_STATE_SCHED, &q->state)); 1098 1099 spin_unlock_bh(root_lock); 1100 } 1101 1102 if (val) 1103 return true; 1104 } 1105 return false; 1106 } 1107 1108 static void dev_qdisc_reset(struct net_device *dev, 1109 struct netdev_queue *dev_queue, 1110 void *none) 1111 { 1112 struct Qdisc *qdisc = dev_queue->qdisc_sleeping; 1113 1114 if (qdisc) 1115 qdisc_reset(qdisc); 1116 } 1117 1118 /** 1119 * dev_deactivate_many - deactivate transmissions on several devices 1120 * @head: list of devices to deactivate 1121 * 1122 * This function returns only when all outstanding transmissions 1123 * have completed, unless all devices are in dismantle phase. 1124 */ 1125 void dev_deactivate_many(struct list_head *head) 1126 { 1127 struct net_device *dev; 1128 1129 list_for_each_entry(dev, head, close_list) { 1130 netdev_for_each_tx_queue(dev, dev_deactivate_queue, 1131 &noop_qdisc); 1132 if (dev_ingress_queue(dev)) 1133 dev_deactivate_queue(dev, dev_ingress_queue(dev), 1134 &noop_qdisc); 1135 1136 dev_watchdog_down(dev); 1137 } 1138 1139 /* Wait for outstanding qdisc-less dev_queue_xmit calls. 1140 * This is avoided if all devices are in dismantle phase : 1141 * Caller will call synchronize_net() for us 1142 */ 1143 synchronize_net(); 1144 1145 /* Wait for outstanding qdisc_run calls. */ 1146 list_for_each_entry(dev, head, close_list) { 1147 while (some_qdisc_is_busy(dev)) 1148 yield(); 1149 /* The new qdisc is assigned at this point so we can safely 1150 * unwind stale skb lists and qdisc statistics 1151 */ 1152 netdev_for_each_tx_queue(dev, dev_qdisc_reset, NULL); 1153 if (dev_ingress_queue(dev)) 1154 dev_qdisc_reset(dev, dev_ingress_queue(dev), NULL); 1155 } 1156 } 1157 1158 void dev_deactivate(struct net_device *dev) 1159 { 1160 LIST_HEAD(single); 1161 1162 list_add(&dev->close_list, &single); 1163 dev_deactivate_many(&single); 1164 list_del(&single); 1165 } 1166 EXPORT_SYMBOL(dev_deactivate); 1167 1168 static void dev_init_scheduler_queue(struct net_device *dev, 1169 struct netdev_queue *dev_queue, 1170 void *_qdisc) 1171 { 1172 struct Qdisc *qdisc = _qdisc; 1173 1174 rcu_assign_pointer(dev_queue->qdisc, qdisc); 1175 dev_queue->qdisc_sleeping = qdisc; 1176 __skb_queue_head_init(&qdisc->gso_skb); 1177 __skb_queue_head_init(&qdisc->skb_bad_txq); 1178 } 1179 1180 void dev_init_scheduler(struct net_device *dev) 1181 { 1182 dev->qdisc = &noop_qdisc; 1183 netdev_for_each_tx_queue(dev, dev_init_scheduler_queue, &noop_qdisc); 1184 if (dev_ingress_queue(dev)) 1185 dev_init_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc); 1186 1187 timer_setup(&dev->watchdog_timer, dev_watchdog, 0); 1188 } 1189 1190 static void shutdown_scheduler_queue(struct net_device *dev, 1191 struct netdev_queue *dev_queue, 1192 void *_qdisc_default) 1193 { 1194 struct Qdisc *qdisc = dev_queue->qdisc_sleeping; 1195 struct Qdisc *qdisc_default = _qdisc_default; 1196 1197 if (qdisc) { 1198 rcu_assign_pointer(dev_queue->qdisc, qdisc_default); 1199 dev_queue->qdisc_sleeping = qdisc_default; 1200 1201 qdisc_destroy(qdisc); 1202 } 1203 } 1204 1205 void dev_shutdown(struct net_device *dev) 1206 { 1207 netdev_for_each_tx_queue(dev, shutdown_scheduler_queue, &noop_qdisc); 1208 if (dev_ingress_queue(dev)) 1209 shutdown_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc); 1210 qdisc_destroy(dev->qdisc); 1211 dev->qdisc = &noop_qdisc; 1212 1213 WARN_ON(timer_pending(&dev->watchdog_timer)); 1214 } 1215 1216 void psched_ratecfg_precompute(struct psched_ratecfg *r, 1217 const struct tc_ratespec *conf, 1218 u64 rate64) 1219 { 1220 memset(r, 0, sizeof(*r)); 1221 r->overhead = conf->overhead; 1222 r->rate_bytes_ps = max_t(u64, conf->rate, rate64); 1223 r->linklayer = (conf->linklayer & TC_LINKLAYER_MASK); 1224 r->mult = 1; 1225 /* 1226 * The deal here is to replace a divide by a reciprocal one 1227 * in fast path (a reciprocal divide is a multiply and a shift) 1228 * 1229 * Normal formula would be : 1230 * time_in_ns = (NSEC_PER_SEC * len) / rate_bps 1231 * 1232 * We compute mult/shift to use instead : 1233 * time_in_ns = (len * mult) >> shift; 1234 * 1235 * We try to get the highest possible mult value for accuracy, 1236 * but have to make sure no overflows will ever happen. 1237 */ 1238 if (r->rate_bytes_ps > 0) { 1239 u64 factor = NSEC_PER_SEC; 1240 1241 for (;;) { 1242 r->mult = div64_u64(factor, r->rate_bytes_ps); 1243 if (r->mult & (1U << 31) || factor & (1ULL << 63)) 1244 break; 1245 factor <<= 1; 1246 r->shift++; 1247 } 1248 } 1249 } 1250 EXPORT_SYMBOL(psched_ratecfg_precompute); 1251 1252 static void mini_qdisc_rcu_func(struct rcu_head *head) 1253 { 1254 } 1255 1256 void mini_qdisc_pair_swap(struct mini_Qdisc_pair *miniqp, 1257 struct tcf_proto *tp_head) 1258 { 1259 struct mini_Qdisc *miniq_old = rtnl_dereference(*miniqp->p_miniq); 1260 struct mini_Qdisc *miniq; 1261 1262 if (!tp_head) { 1263 RCU_INIT_POINTER(*miniqp->p_miniq, NULL); 1264 /* Wait for flying RCU callback before it is freed. */ 1265 rcu_barrier_bh(); 1266 return; 1267 } 1268 1269 miniq = !miniq_old || miniq_old == &miniqp->miniq2 ? 1270 &miniqp->miniq1 : &miniqp->miniq2; 1271 1272 /* We need to make sure that readers won't see the miniq 1273 * we are about to modify. So wait until previous call_rcu_bh callback 1274 * is done. 1275 */ 1276 rcu_barrier_bh(); 1277 miniq->filter_list = tp_head; 1278 rcu_assign_pointer(*miniqp->p_miniq, miniq); 1279 1280 if (miniq_old) 1281 /* This is counterpart of the rcu barriers above. We need to 1282 * block potential new user of miniq_old until all readers 1283 * are not seeing it. 1284 */ 1285 call_rcu_bh(&miniq_old->rcu, mini_qdisc_rcu_func); 1286 } 1287 EXPORT_SYMBOL(mini_qdisc_pair_swap); 1288 1289 void mini_qdisc_pair_init(struct mini_Qdisc_pair *miniqp, struct Qdisc *qdisc, 1290 struct mini_Qdisc __rcu **p_miniq) 1291 { 1292 miniqp->miniq1.cpu_bstats = qdisc->cpu_bstats; 1293 miniqp->miniq1.cpu_qstats = qdisc->cpu_qstats; 1294 miniqp->miniq2.cpu_bstats = qdisc->cpu_bstats; 1295 miniqp->miniq2.cpu_qstats = qdisc->cpu_qstats; 1296 miniqp->p_miniq = p_miniq; 1297 } 1298 EXPORT_SYMBOL(mini_qdisc_pair_init); 1299