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