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