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 <asm/uaccess.h> 15 #include <asm/system.h> 16 #include <linux/bitops.h> 17 #include <linux/module.h> 18 #include <linux/types.h> 19 #include <linux/kernel.h> 20 #include <linux/sched.h> 21 #include <linux/string.h> 22 #include <linux/mm.h> 23 #include <linux/socket.h> 24 #include <linux/sockios.h> 25 #include <linux/in.h> 26 #include <linux/errno.h> 27 #include <linux/interrupt.h> 28 #include <linux/netdevice.h> 29 #include <linux/skbuff.h> 30 #include <linux/rtnetlink.h> 31 #include <linux/init.h> 32 #include <linux/rcupdate.h> 33 #include <linux/list.h> 34 #include <net/sock.h> 35 #include <net/pkt_sched.h> 36 37 /* Main transmission queue. */ 38 39 /* Main qdisc structure lock. 40 41 However, modifications 42 to data, participating in scheduling must be additionally 43 protected with dev->queue_lock spinlock. 44 45 The idea is the following: 46 - enqueue, dequeue are serialized via top level device 47 spinlock dev->queue_lock. 48 - tree walking is protected by read_lock_bh(qdisc_tree_lock) 49 and this lock is used only in process context. 50 - updates to tree are made under rtnl semaphore or 51 from softirq context (__qdisc_destroy rcu-callback) 52 hence this lock needs local bh disabling. 53 54 qdisc_tree_lock must be grabbed BEFORE dev->queue_lock! 55 */ 56 DEFINE_RWLOCK(qdisc_tree_lock); 57 58 void qdisc_lock_tree(struct net_device *dev) 59 { 60 write_lock_bh(&qdisc_tree_lock); 61 spin_lock_bh(&dev->queue_lock); 62 } 63 64 void qdisc_unlock_tree(struct net_device *dev) 65 { 66 spin_unlock_bh(&dev->queue_lock); 67 write_unlock_bh(&qdisc_tree_lock); 68 } 69 70 /* 71 dev->queue_lock serializes queue accesses for this device 72 AND dev->qdisc pointer itself. 73 74 netif_tx_lock serializes accesses to device driver. 75 76 dev->queue_lock and netif_tx_lock are mutually exclusive, 77 if one is grabbed, another must be free. 78 */ 79 80 81 /* Kick device. 82 Note, that this procedure can be called by a watchdog timer, so that 83 we do not check dev->tbusy flag here. 84 85 Returns: 0 - queue is empty. 86 >0 - queue is not empty, but throttled. 87 <0 - queue is not empty. Device is throttled, if dev->tbusy != 0. 88 89 NOTE: Called under dev->queue_lock with locally disabled BH. 90 */ 91 92 static inline int qdisc_restart(struct net_device *dev) 93 { 94 struct Qdisc *q = dev->qdisc; 95 struct sk_buff *skb; 96 97 /* Dequeue packet */ 98 if (((skb = dev->gso_skb)) || ((skb = q->dequeue(q)))) { 99 unsigned nolock = (dev->features & NETIF_F_LLTX); 100 101 dev->gso_skb = NULL; 102 103 /* 104 * When the driver has LLTX set it does its own locking 105 * in start_xmit. No need to add additional overhead by 106 * locking again. These checks are worth it because 107 * even uncongested locks can be quite expensive. 108 * The driver can do trylock like here too, in case 109 * of lock congestion it should return -1 and the packet 110 * will be requeued. 111 */ 112 if (!nolock) { 113 if (!netif_tx_trylock(dev)) { 114 collision: 115 /* So, someone grabbed the driver. */ 116 117 /* It may be transient configuration error, 118 when hard_start_xmit() recurses. We detect 119 it by checking xmit owner and drop the 120 packet when deadloop is detected. 121 */ 122 if (dev->xmit_lock_owner == smp_processor_id()) { 123 kfree_skb(skb); 124 if (net_ratelimit()) 125 printk(KERN_DEBUG "Dead loop on netdevice %s, fix it urgently!\n", dev->name); 126 return -1; 127 } 128 __get_cpu_var(netdev_rx_stat).cpu_collision++; 129 goto requeue; 130 } 131 } 132 133 { 134 /* And release queue */ 135 spin_unlock(&dev->queue_lock); 136 137 if (!netif_queue_stopped(dev)) { 138 int ret; 139 140 ret = dev_hard_start_xmit(skb, dev); 141 if (ret == NETDEV_TX_OK) { 142 if (!nolock) { 143 netif_tx_unlock(dev); 144 } 145 spin_lock(&dev->queue_lock); 146 return -1; 147 } 148 if (ret == NETDEV_TX_LOCKED && nolock) { 149 spin_lock(&dev->queue_lock); 150 goto collision; 151 } 152 } 153 154 /* NETDEV_TX_BUSY - we need to requeue */ 155 /* Release the driver */ 156 if (!nolock) { 157 netif_tx_unlock(dev); 158 } 159 spin_lock(&dev->queue_lock); 160 q = dev->qdisc; 161 } 162 163 /* Device kicked us out :( 164 This is possible in three cases: 165 166 0. driver is locked 167 1. fastroute is enabled 168 2. device cannot determine busy state 169 before start of transmission (f.e. dialout) 170 3. device is buggy (ppp) 171 */ 172 173 requeue: 174 if (skb->next) 175 dev->gso_skb = skb; 176 else 177 q->ops->requeue(skb, q); 178 netif_schedule(dev); 179 return 1; 180 } 181 BUG_ON((int) q->q.qlen < 0); 182 return q->q.qlen; 183 } 184 185 void __qdisc_run(struct net_device *dev) 186 { 187 if (unlikely(dev->qdisc == &noop_qdisc)) 188 goto out; 189 190 while (qdisc_restart(dev) < 0 && !netif_queue_stopped(dev)) 191 /* NOTHING */; 192 193 out: 194 clear_bit(__LINK_STATE_QDISC_RUNNING, &dev->state); 195 } 196 197 static void dev_watchdog(unsigned long arg) 198 { 199 struct net_device *dev = (struct net_device *)arg; 200 201 netif_tx_lock(dev); 202 if (dev->qdisc != &noop_qdisc) { 203 if (netif_device_present(dev) && 204 netif_running(dev) && 205 netif_carrier_ok(dev)) { 206 if (netif_queue_stopped(dev) && 207 time_after(jiffies, dev->trans_start + dev->watchdog_timeo)) { 208 209 printk(KERN_INFO "NETDEV WATCHDOG: %s: transmit timed out\n", 210 dev->name); 211 dev->tx_timeout(dev); 212 } 213 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo)) 214 dev_hold(dev); 215 } 216 } 217 netif_tx_unlock(dev); 218 219 dev_put(dev); 220 } 221 222 static void dev_watchdog_init(struct net_device *dev) 223 { 224 init_timer(&dev->watchdog_timer); 225 dev->watchdog_timer.data = (unsigned long)dev; 226 dev->watchdog_timer.function = dev_watchdog; 227 } 228 229 void __netdev_watchdog_up(struct net_device *dev) 230 { 231 if (dev->tx_timeout) { 232 if (dev->watchdog_timeo <= 0) 233 dev->watchdog_timeo = 5*HZ; 234 if (!mod_timer(&dev->watchdog_timer, jiffies + dev->watchdog_timeo)) 235 dev_hold(dev); 236 } 237 } 238 239 static void dev_watchdog_up(struct net_device *dev) 240 { 241 __netdev_watchdog_up(dev); 242 } 243 244 static void dev_watchdog_down(struct net_device *dev) 245 { 246 netif_tx_lock_bh(dev); 247 if (del_timer(&dev->watchdog_timer)) 248 dev_put(dev); 249 netif_tx_unlock_bh(dev); 250 } 251 252 void netif_carrier_on(struct net_device *dev) 253 { 254 if (test_and_clear_bit(__LINK_STATE_NOCARRIER, &dev->state)) 255 linkwatch_fire_event(dev); 256 if (netif_running(dev)) 257 __netdev_watchdog_up(dev); 258 } 259 260 void netif_carrier_off(struct net_device *dev) 261 { 262 if (!test_and_set_bit(__LINK_STATE_NOCARRIER, &dev->state)) 263 linkwatch_fire_event(dev); 264 } 265 266 /* "NOOP" scheduler: the best scheduler, recommended for all interfaces 267 under all circumstances. It is difficult to invent anything faster or 268 cheaper. 269 */ 270 271 static int noop_enqueue(struct sk_buff *skb, struct Qdisc * qdisc) 272 { 273 kfree_skb(skb); 274 return NET_XMIT_CN; 275 } 276 277 static struct sk_buff *noop_dequeue(struct Qdisc * qdisc) 278 { 279 return NULL; 280 } 281 282 static int noop_requeue(struct sk_buff *skb, struct Qdisc* qdisc) 283 { 284 if (net_ratelimit()) 285 printk(KERN_DEBUG "%s deferred output. It is buggy.\n", 286 skb->dev->name); 287 kfree_skb(skb); 288 return NET_XMIT_CN; 289 } 290 291 struct Qdisc_ops noop_qdisc_ops = { 292 .id = "noop", 293 .priv_size = 0, 294 .enqueue = noop_enqueue, 295 .dequeue = noop_dequeue, 296 .requeue = noop_requeue, 297 .owner = THIS_MODULE, 298 }; 299 300 struct Qdisc noop_qdisc = { 301 .enqueue = noop_enqueue, 302 .dequeue = noop_dequeue, 303 .flags = TCQ_F_BUILTIN, 304 .ops = &noop_qdisc_ops, 305 .list = LIST_HEAD_INIT(noop_qdisc.list), 306 }; 307 308 static struct Qdisc_ops noqueue_qdisc_ops = { 309 .id = "noqueue", 310 .priv_size = 0, 311 .enqueue = noop_enqueue, 312 .dequeue = noop_dequeue, 313 .requeue = noop_requeue, 314 .owner = THIS_MODULE, 315 }; 316 317 static struct Qdisc noqueue_qdisc = { 318 .enqueue = NULL, 319 .dequeue = noop_dequeue, 320 .flags = TCQ_F_BUILTIN, 321 .ops = &noqueue_qdisc_ops, 322 .list = LIST_HEAD_INIT(noqueue_qdisc.list), 323 }; 324 325 326 static const u8 prio2band[TC_PRIO_MAX+1] = 327 { 1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1 }; 328 329 /* 3-band FIFO queue: old style, but should be a bit faster than 330 generic prio+fifo combination. 331 */ 332 333 #define PFIFO_FAST_BANDS 3 334 335 static inline struct sk_buff_head *prio2list(struct sk_buff *skb, 336 struct Qdisc *qdisc) 337 { 338 struct sk_buff_head *list = qdisc_priv(qdisc); 339 return list + prio2band[skb->priority & TC_PRIO_MAX]; 340 } 341 342 static int pfifo_fast_enqueue(struct sk_buff *skb, struct Qdisc* qdisc) 343 { 344 struct sk_buff_head *list = prio2list(skb, qdisc); 345 346 if (skb_queue_len(list) < qdisc->dev->tx_queue_len) { 347 qdisc->q.qlen++; 348 return __qdisc_enqueue_tail(skb, qdisc, list); 349 } 350 351 return qdisc_drop(skb, qdisc); 352 } 353 354 static struct sk_buff *pfifo_fast_dequeue(struct Qdisc* qdisc) 355 { 356 int prio; 357 struct sk_buff_head *list = qdisc_priv(qdisc); 358 359 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) { 360 if (!skb_queue_empty(list + prio)) { 361 qdisc->q.qlen--; 362 return __qdisc_dequeue_head(qdisc, list + prio); 363 } 364 } 365 366 return NULL; 367 } 368 369 static int pfifo_fast_requeue(struct sk_buff *skb, struct Qdisc* qdisc) 370 { 371 qdisc->q.qlen++; 372 return __qdisc_requeue(skb, qdisc, prio2list(skb, qdisc)); 373 } 374 375 static void pfifo_fast_reset(struct Qdisc* qdisc) 376 { 377 int prio; 378 struct sk_buff_head *list = qdisc_priv(qdisc); 379 380 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) 381 __qdisc_reset_queue(qdisc, list + prio); 382 383 qdisc->qstats.backlog = 0; 384 qdisc->q.qlen = 0; 385 } 386 387 static int pfifo_fast_dump(struct Qdisc *qdisc, struct sk_buff *skb) 388 { 389 struct tc_prio_qopt opt = { .bands = PFIFO_FAST_BANDS }; 390 391 memcpy(&opt.priomap, prio2band, TC_PRIO_MAX+1); 392 RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt); 393 return skb->len; 394 395 rtattr_failure: 396 return -1; 397 } 398 399 static int pfifo_fast_init(struct Qdisc *qdisc, struct rtattr *opt) 400 { 401 int prio; 402 struct sk_buff_head *list = qdisc_priv(qdisc); 403 404 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) 405 skb_queue_head_init(list + prio); 406 407 return 0; 408 } 409 410 static struct Qdisc_ops pfifo_fast_ops = { 411 .id = "pfifo_fast", 412 .priv_size = PFIFO_FAST_BANDS * sizeof(struct sk_buff_head), 413 .enqueue = pfifo_fast_enqueue, 414 .dequeue = pfifo_fast_dequeue, 415 .requeue = pfifo_fast_requeue, 416 .init = pfifo_fast_init, 417 .reset = pfifo_fast_reset, 418 .dump = pfifo_fast_dump, 419 .owner = THIS_MODULE, 420 }; 421 422 struct Qdisc *qdisc_alloc(struct net_device *dev, struct Qdisc_ops *ops) 423 { 424 void *p; 425 struct Qdisc *sch; 426 unsigned int size; 427 int err = -ENOBUFS; 428 429 /* ensure that the Qdisc and the private data are 32-byte aligned */ 430 size = QDISC_ALIGN(sizeof(*sch)); 431 size += ops->priv_size + (QDISC_ALIGNTO - 1); 432 433 p = kzalloc(size, GFP_KERNEL); 434 if (!p) 435 goto errout; 436 sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p); 437 sch->padded = (char *) sch - (char *) p; 438 439 INIT_LIST_HEAD(&sch->list); 440 skb_queue_head_init(&sch->q); 441 sch->ops = ops; 442 sch->enqueue = ops->enqueue; 443 sch->dequeue = ops->dequeue; 444 sch->dev = dev; 445 dev_hold(dev); 446 sch->stats_lock = &dev->queue_lock; 447 atomic_set(&sch->refcnt, 1); 448 449 return sch; 450 errout: 451 return ERR_PTR(-err); 452 } 453 454 struct Qdisc * qdisc_create_dflt(struct net_device *dev, struct Qdisc_ops *ops) 455 { 456 struct Qdisc *sch; 457 458 sch = qdisc_alloc(dev, ops); 459 if (IS_ERR(sch)) 460 goto errout; 461 462 if (!ops->init || ops->init(sch, NULL) == 0) 463 return sch; 464 465 qdisc_destroy(sch); 466 errout: 467 return NULL; 468 } 469 470 /* Under dev->queue_lock and BH! */ 471 472 void qdisc_reset(struct Qdisc *qdisc) 473 { 474 struct Qdisc_ops *ops = qdisc->ops; 475 476 if (ops->reset) 477 ops->reset(qdisc); 478 } 479 480 /* this is the rcu callback function to clean up a qdisc when there 481 * are no further references to it */ 482 483 static void __qdisc_destroy(struct rcu_head *head) 484 { 485 struct Qdisc *qdisc = container_of(head, struct Qdisc, q_rcu); 486 struct Qdisc_ops *ops = qdisc->ops; 487 488 #ifdef CONFIG_NET_ESTIMATOR 489 gen_kill_estimator(&qdisc->bstats, &qdisc->rate_est); 490 #endif 491 write_lock(&qdisc_tree_lock); 492 if (ops->reset) 493 ops->reset(qdisc); 494 if (ops->destroy) 495 ops->destroy(qdisc); 496 write_unlock(&qdisc_tree_lock); 497 module_put(ops->owner); 498 499 dev_put(qdisc->dev); 500 kfree((char *) qdisc - qdisc->padded); 501 } 502 503 /* Under dev->queue_lock and BH! */ 504 505 void qdisc_destroy(struct Qdisc *qdisc) 506 { 507 struct list_head cql = LIST_HEAD_INIT(cql); 508 struct Qdisc *cq, *q, *n; 509 510 if (qdisc->flags & TCQ_F_BUILTIN || 511 !atomic_dec_and_test(&qdisc->refcnt)) 512 return; 513 514 if (!list_empty(&qdisc->list)) { 515 if (qdisc->ops->cl_ops == NULL) 516 list_del(&qdisc->list); 517 else 518 list_move(&qdisc->list, &cql); 519 } 520 521 /* unlink inner qdiscs from dev->qdisc_list immediately */ 522 list_for_each_entry(cq, &cql, list) 523 list_for_each_entry_safe(q, n, &qdisc->dev->qdisc_list, list) 524 if (TC_H_MAJ(q->parent) == TC_H_MAJ(cq->handle)) { 525 if (q->ops->cl_ops == NULL) 526 list_del_init(&q->list); 527 else 528 list_move_tail(&q->list, &cql); 529 } 530 list_for_each_entry_safe(cq, n, &cql, list) 531 list_del_init(&cq->list); 532 533 call_rcu(&qdisc->q_rcu, __qdisc_destroy); 534 } 535 536 void dev_activate(struct net_device *dev) 537 { 538 /* No queueing discipline is attached to device; 539 create default one i.e. pfifo_fast for devices, 540 which need queueing and noqueue_qdisc for 541 virtual interfaces 542 */ 543 544 if (dev->qdisc_sleeping == &noop_qdisc) { 545 struct Qdisc *qdisc; 546 if (dev->tx_queue_len) { 547 qdisc = qdisc_create_dflt(dev, &pfifo_fast_ops); 548 if (qdisc == NULL) { 549 printk(KERN_INFO "%s: activation failed\n", dev->name); 550 return; 551 } 552 write_lock_bh(&qdisc_tree_lock); 553 list_add_tail(&qdisc->list, &dev->qdisc_list); 554 write_unlock_bh(&qdisc_tree_lock); 555 } else { 556 qdisc = &noqueue_qdisc; 557 } 558 write_lock_bh(&qdisc_tree_lock); 559 dev->qdisc_sleeping = qdisc; 560 write_unlock_bh(&qdisc_tree_lock); 561 } 562 563 if (!netif_carrier_ok(dev)) 564 /* Delay activation until next carrier-on event */ 565 return; 566 567 spin_lock_bh(&dev->queue_lock); 568 rcu_assign_pointer(dev->qdisc, dev->qdisc_sleeping); 569 if (dev->qdisc != &noqueue_qdisc) { 570 dev->trans_start = jiffies; 571 dev_watchdog_up(dev); 572 } 573 spin_unlock_bh(&dev->queue_lock); 574 } 575 576 void dev_deactivate(struct net_device *dev) 577 { 578 struct Qdisc *qdisc; 579 580 spin_lock_bh(&dev->queue_lock); 581 qdisc = dev->qdisc; 582 dev->qdisc = &noop_qdisc; 583 584 qdisc_reset(qdisc); 585 586 spin_unlock_bh(&dev->queue_lock); 587 588 dev_watchdog_down(dev); 589 590 /* Wait for outstanding dev_queue_xmit calls. */ 591 synchronize_rcu(); 592 593 /* Wait for outstanding qdisc_run calls. */ 594 while (test_bit(__LINK_STATE_QDISC_RUNNING, &dev->state)) 595 yield(); 596 597 if (dev->gso_skb) { 598 kfree_skb(dev->gso_skb); 599 dev->gso_skb = NULL; 600 } 601 } 602 603 void dev_init_scheduler(struct net_device *dev) 604 { 605 qdisc_lock_tree(dev); 606 dev->qdisc = &noop_qdisc; 607 dev->qdisc_sleeping = &noop_qdisc; 608 INIT_LIST_HEAD(&dev->qdisc_list); 609 qdisc_unlock_tree(dev); 610 611 dev_watchdog_init(dev); 612 } 613 614 void dev_shutdown(struct net_device *dev) 615 { 616 struct Qdisc *qdisc; 617 618 qdisc_lock_tree(dev); 619 qdisc = dev->qdisc_sleeping; 620 dev->qdisc = &noop_qdisc; 621 dev->qdisc_sleeping = &noop_qdisc; 622 qdisc_destroy(qdisc); 623 #if defined(CONFIG_NET_SCH_INGRESS) || defined(CONFIG_NET_SCH_INGRESS_MODULE) 624 if ((qdisc = dev->qdisc_ingress) != NULL) { 625 dev->qdisc_ingress = NULL; 626 qdisc_destroy(qdisc); 627 } 628 #endif 629 BUG_TRAP(!timer_pending(&dev->watchdog_timer)); 630 qdisc_unlock_tree(dev); 631 } 632 633 EXPORT_SYMBOL(__netdev_watchdog_up); 634 EXPORT_SYMBOL(netif_carrier_on); 635 EXPORT_SYMBOL(netif_carrier_off); 636 EXPORT_SYMBOL(noop_qdisc); 637 EXPORT_SYMBOL(noop_qdisc_ops); 638 EXPORT_SYMBOL(qdisc_create_dflt); 639 EXPORT_SYMBOL(qdisc_alloc); 640 EXPORT_SYMBOL(qdisc_destroy); 641 EXPORT_SYMBOL(qdisc_reset); 642 EXPORT_SYMBOL(qdisc_lock_tree); 643 EXPORT_SYMBOL(qdisc_unlock_tree); 644