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 return NULL; 645 646 sch = qdisc_alloc(dev_queue, ops); 647 if (IS_ERR(sch)) { 648 module_put(ops->owner); 649 return NULL; 650 } 651 sch->parent = parentid; 652 653 if (!ops->init || ops->init(sch, NULL) == 0) 654 return sch; 655 656 qdisc_destroy(sch); 657 return NULL; 658 } 659 EXPORT_SYMBOL(qdisc_create_dflt); 660 661 /* Under qdisc_lock(qdisc) and BH! */ 662 663 void qdisc_reset(struct Qdisc *qdisc) 664 { 665 const struct Qdisc_ops *ops = qdisc->ops; 666 667 if (ops->reset) 668 ops->reset(qdisc); 669 670 kfree_skb(qdisc->skb_bad_txq); 671 qdisc->skb_bad_txq = NULL; 672 673 if (qdisc->gso_skb) { 674 kfree_skb_list(qdisc->gso_skb); 675 qdisc->gso_skb = NULL; 676 } 677 qdisc->q.qlen = 0; 678 } 679 EXPORT_SYMBOL(qdisc_reset); 680 681 static void qdisc_rcu_free(struct rcu_head *head) 682 { 683 struct Qdisc *qdisc = container_of(head, struct Qdisc, rcu_head); 684 685 if (qdisc_is_percpu_stats(qdisc)) { 686 free_percpu(qdisc->cpu_bstats); 687 free_percpu(qdisc->cpu_qstats); 688 } 689 690 kfree((char *) qdisc - qdisc->padded); 691 } 692 693 void qdisc_destroy(struct Qdisc *qdisc) 694 { 695 const struct Qdisc_ops *ops = qdisc->ops; 696 697 if (qdisc->flags & TCQ_F_BUILTIN || 698 !atomic_dec_and_test(&qdisc->refcnt)) 699 return; 700 701 #ifdef CONFIG_NET_SCHED 702 qdisc_hash_del(qdisc); 703 704 qdisc_put_stab(rtnl_dereference(qdisc->stab)); 705 #endif 706 gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est); 707 if (ops->reset) 708 ops->reset(qdisc); 709 if (ops->destroy) 710 ops->destroy(qdisc); 711 712 module_put(ops->owner); 713 dev_put(qdisc_dev(qdisc)); 714 715 kfree_skb_list(qdisc->gso_skb); 716 kfree_skb(qdisc->skb_bad_txq); 717 /* 718 * gen_estimator est_timer() might access qdisc->q.lock, 719 * wait a RCU grace period before freeing qdisc. 720 */ 721 call_rcu(&qdisc->rcu_head, qdisc_rcu_free); 722 } 723 EXPORT_SYMBOL(qdisc_destroy); 724 725 /* Attach toplevel qdisc to device queue. */ 726 struct Qdisc *dev_graft_qdisc(struct netdev_queue *dev_queue, 727 struct Qdisc *qdisc) 728 { 729 struct Qdisc *oqdisc = dev_queue->qdisc_sleeping; 730 spinlock_t *root_lock; 731 732 root_lock = qdisc_lock(oqdisc); 733 spin_lock_bh(root_lock); 734 735 /* Prune old scheduler */ 736 if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1) 737 qdisc_reset(oqdisc); 738 739 /* ... and graft new one */ 740 if (qdisc == NULL) 741 qdisc = &noop_qdisc; 742 dev_queue->qdisc_sleeping = qdisc; 743 rcu_assign_pointer(dev_queue->qdisc, &noop_qdisc); 744 745 spin_unlock_bh(root_lock); 746 747 return oqdisc; 748 } 749 EXPORT_SYMBOL(dev_graft_qdisc); 750 751 static void attach_one_default_qdisc(struct net_device *dev, 752 struct netdev_queue *dev_queue, 753 void *_unused) 754 { 755 struct Qdisc *qdisc; 756 const struct Qdisc_ops *ops = default_qdisc_ops; 757 758 if (dev->priv_flags & IFF_NO_QUEUE) 759 ops = &noqueue_qdisc_ops; 760 761 qdisc = qdisc_create_dflt(dev_queue, ops, TC_H_ROOT); 762 if (!qdisc) { 763 netdev_info(dev, "activation failed\n"); 764 return; 765 } 766 if (!netif_is_multiqueue(dev)) 767 qdisc->flags |= TCQ_F_ONETXQUEUE | TCQ_F_NOPARENT; 768 dev_queue->qdisc_sleeping = qdisc; 769 } 770 771 static void attach_default_qdiscs(struct net_device *dev) 772 { 773 struct netdev_queue *txq; 774 struct Qdisc *qdisc; 775 776 txq = netdev_get_tx_queue(dev, 0); 777 778 if (!netif_is_multiqueue(dev) || 779 dev->priv_flags & IFF_NO_QUEUE) { 780 netdev_for_each_tx_queue(dev, attach_one_default_qdisc, NULL); 781 dev->qdisc = txq->qdisc_sleeping; 782 atomic_inc(&dev->qdisc->refcnt); 783 } else { 784 qdisc = qdisc_create_dflt(txq, &mq_qdisc_ops, TC_H_ROOT); 785 if (qdisc) { 786 dev->qdisc = qdisc; 787 qdisc->ops->attach(qdisc); 788 } 789 } 790 #ifdef CONFIG_NET_SCHED 791 if (dev->qdisc) 792 qdisc_hash_add(dev->qdisc); 793 #endif 794 } 795 796 static void transition_one_qdisc(struct net_device *dev, 797 struct netdev_queue *dev_queue, 798 void *_need_watchdog) 799 { 800 struct Qdisc *new_qdisc = dev_queue->qdisc_sleeping; 801 int *need_watchdog_p = _need_watchdog; 802 803 if (!(new_qdisc->flags & TCQ_F_BUILTIN)) 804 clear_bit(__QDISC_STATE_DEACTIVATED, &new_qdisc->state); 805 806 rcu_assign_pointer(dev_queue->qdisc, new_qdisc); 807 if (need_watchdog_p) { 808 dev_queue->trans_start = 0; 809 *need_watchdog_p = 1; 810 } 811 } 812 813 void dev_activate(struct net_device *dev) 814 { 815 int need_watchdog; 816 817 /* No queueing discipline is attached to device; 818 * create default one for devices, which need queueing 819 * and noqueue_qdisc for virtual interfaces 820 */ 821 822 if (dev->qdisc == &noop_qdisc) 823 attach_default_qdiscs(dev); 824 825 if (!netif_carrier_ok(dev)) 826 /* Delay activation until next carrier-on event */ 827 return; 828 829 need_watchdog = 0; 830 netdev_for_each_tx_queue(dev, transition_one_qdisc, &need_watchdog); 831 if (dev_ingress_queue(dev)) 832 transition_one_qdisc(dev, dev_ingress_queue(dev), NULL); 833 834 if (need_watchdog) { 835 netif_trans_update(dev); 836 dev_watchdog_up(dev); 837 } 838 } 839 EXPORT_SYMBOL(dev_activate); 840 841 static void dev_deactivate_queue(struct net_device *dev, 842 struct netdev_queue *dev_queue, 843 void *_qdisc_default) 844 { 845 struct Qdisc *qdisc_default = _qdisc_default; 846 struct Qdisc *qdisc; 847 848 qdisc = rtnl_dereference(dev_queue->qdisc); 849 if (qdisc) { 850 spin_lock_bh(qdisc_lock(qdisc)); 851 852 if (!(qdisc->flags & TCQ_F_BUILTIN)) 853 set_bit(__QDISC_STATE_DEACTIVATED, &qdisc->state); 854 855 rcu_assign_pointer(dev_queue->qdisc, qdisc_default); 856 qdisc_reset(qdisc); 857 858 spin_unlock_bh(qdisc_lock(qdisc)); 859 } 860 } 861 862 static bool some_qdisc_is_busy(struct net_device *dev) 863 { 864 unsigned int i; 865 866 for (i = 0; i < dev->num_tx_queues; i++) { 867 struct netdev_queue *dev_queue; 868 spinlock_t *root_lock; 869 struct Qdisc *q; 870 int val; 871 872 dev_queue = netdev_get_tx_queue(dev, i); 873 q = dev_queue->qdisc_sleeping; 874 root_lock = qdisc_lock(q); 875 876 spin_lock_bh(root_lock); 877 878 val = (qdisc_is_running(q) || 879 test_bit(__QDISC_STATE_SCHED, &q->state)); 880 881 spin_unlock_bh(root_lock); 882 883 if (val) 884 return true; 885 } 886 return false; 887 } 888 889 /** 890 * dev_deactivate_many - deactivate transmissions on several devices 891 * @head: list of devices to deactivate 892 * 893 * This function returns only when all outstanding transmissions 894 * have completed, unless all devices are in dismantle phase. 895 */ 896 void dev_deactivate_many(struct list_head *head) 897 { 898 struct net_device *dev; 899 bool sync_needed = false; 900 901 list_for_each_entry(dev, head, close_list) { 902 netdev_for_each_tx_queue(dev, dev_deactivate_queue, 903 &noop_qdisc); 904 if (dev_ingress_queue(dev)) 905 dev_deactivate_queue(dev, dev_ingress_queue(dev), 906 &noop_qdisc); 907 908 dev_watchdog_down(dev); 909 sync_needed |= !dev->dismantle; 910 } 911 912 /* Wait for outstanding qdisc-less dev_queue_xmit calls. 913 * This is avoided if all devices are in dismantle phase : 914 * Caller will call synchronize_net() for us 915 */ 916 if (sync_needed) 917 synchronize_net(); 918 919 /* Wait for outstanding qdisc_run calls. */ 920 list_for_each_entry(dev, head, close_list) 921 while (some_qdisc_is_busy(dev)) 922 yield(); 923 } 924 925 void dev_deactivate(struct net_device *dev) 926 { 927 LIST_HEAD(single); 928 929 list_add(&dev->close_list, &single); 930 dev_deactivate_many(&single); 931 list_del(&single); 932 } 933 EXPORT_SYMBOL(dev_deactivate); 934 935 static void dev_init_scheduler_queue(struct net_device *dev, 936 struct netdev_queue *dev_queue, 937 void *_qdisc) 938 { 939 struct Qdisc *qdisc = _qdisc; 940 941 rcu_assign_pointer(dev_queue->qdisc, qdisc); 942 dev_queue->qdisc_sleeping = qdisc; 943 } 944 945 void dev_init_scheduler(struct net_device *dev) 946 { 947 dev->qdisc = &noop_qdisc; 948 netdev_for_each_tx_queue(dev, dev_init_scheduler_queue, &noop_qdisc); 949 if (dev_ingress_queue(dev)) 950 dev_init_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc); 951 952 setup_timer(&dev->watchdog_timer, dev_watchdog, (unsigned long)dev); 953 } 954 955 static void shutdown_scheduler_queue(struct net_device *dev, 956 struct netdev_queue *dev_queue, 957 void *_qdisc_default) 958 { 959 struct Qdisc *qdisc = dev_queue->qdisc_sleeping; 960 struct Qdisc *qdisc_default = _qdisc_default; 961 962 if (qdisc) { 963 rcu_assign_pointer(dev_queue->qdisc, qdisc_default); 964 dev_queue->qdisc_sleeping = qdisc_default; 965 966 qdisc_destroy(qdisc); 967 } 968 } 969 970 void dev_shutdown(struct net_device *dev) 971 { 972 netdev_for_each_tx_queue(dev, shutdown_scheduler_queue, &noop_qdisc); 973 if (dev_ingress_queue(dev)) 974 shutdown_scheduler_queue(dev, dev_ingress_queue(dev), &noop_qdisc); 975 qdisc_destroy(dev->qdisc); 976 dev->qdisc = &noop_qdisc; 977 978 WARN_ON(timer_pending(&dev->watchdog_timer)); 979 } 980 981 void psched_ratecfg_precompute(struct psched_ratecfg *r, 982 const struct tc_ratespec *conf, 983 u64 rate64) 984 { 985 memset(r, 0, sizeof(*r)); 986 r->overhead = conf->overhead; 987 r->rate_bytes_ps = max_t(u64, conf->rate, rate64); 988 r->linklayer = (conf->linklayer & TC_LINKLAYER_MASK); 989 r->mult = 1; 990 /* 991 * The deal here is to replace a divide by a reciprocal one 992 * in fast path (a reciprocal divide is a multiply and a shift) 993 * 994 * Normal formula would be : 995 * time_in_ns = (NSEC_PER_SEC * len) / rate_bps 996 * 997 * We compute mult/shift to use instead : 998 * time_in_ns = (len * mult) >> shift; 999 * 1000 * We try to get the highest possible mult value for accuracy, 1001 * but have to make sure no overflows will ever happen. 1002 */ 1003 if (r->rate_bytes_ps > 0) { 1004 u64 factor = NSEC_PER_SEC; 1005 1006 for (;;) { 1007 r->mult = div64_u64(factor, r->rate_bytes_ps); 1008 if (r->mult & (1U << 31) || factor & (1ULL << 63)) 1009 break; 1010 factor <<= 1; 1011 r->shift++; 1012 } 1013 } 1014 } 1015 EXPORT_SYMBOL(psched_ratecfg_precompute); 1016