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