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