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