1 /* 2 * net/sched/sch_netem.c Network emulator 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 * Many of the algorithms and ideas for this came from 10 * NIST Net which is not copyrighted. 11 * 12 * Authors: Stephen Hemminger <shemminger@osdl.org> 13 * Catalin(ux aka Dino) BOIE <catab at umbrella dot ro> 14 */ 15 16 #include <linux/config.h> 17 #include <linux/module.h> 18 #include <linux/bitops.h> 19 #include <linux/types.h> 20 #include <linux/kernel.h> 21 #include <linux/errno.h> 22 #include <linux/netdevice.h> 23 #include <linux/skbuff.h> 24 #include <linux/rtnetlink.h> 25 26 #include <net/pkt_sched.h> 27 28 /* Network Emulation Queuing algorithm. 29 ==================================== 30 31 Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based 32 Network Emulation Tool 33 [2] Luigi Rizzo, DummyNet for FreeBSD 34 35 ---------------------------------------------------------------- 36 37 This started out as a simple way to delay outgoing packets to 38 test TCP but has grown to include most of the functionality 39 of a full blown network emulator like NISTnet. It can delay 40 packets and add random jitter (and correlation). The random 41 distribution can be loaded from a table as well to provide 42 normal, Pareto, or experimental curves. Packet loss, 43 duplication, and reordering can also be emulated. 44 45 This qdisc does not do classification that can be handled in 46 layering other disciplines. It does not need to do bandwidth 47 control either since that can be handled by using token 48 bucket or other rate control. 49 50 The simulator is limited by the Linux timer resolution 51 and will create packet bursts on the HZ boundary (1ms). 52 */ 53 54 struct netem_sched_data { 55 struct Qdisc *qdisc; 56 struct sk_buff_head delayed; 57 struct timer_list timer; 58 59 u32 latency; 60 u32 loss; 61 u32 limit; 62 u32 counter; 63 u32 gap; 64 u32 jitter; 65 u32 duplicate; 66 67 struct crndstate { 68 unsigned long last; 69 unsigned long rho; 70 } delay_cor, loss_cor, dup_cor; 71 72 struct disttable { 73 u32 size; 74 s16 table[0]; 75 } *delay_dist; 76 }; 77 78 /* Time stamp put into socket buffer control block */ 79 struct netem_skb_cb { 80 psched_time_t time_to_send; 81 }; 82 83 /* init_crandom - initialize correlated random number generator 84 * Use entropy source for initial seed. 85 */ 86 static void init_crandom(struct crndstate *state, unsigned long rho) 87 { 88 state->rho = rho; 89 state->last = net_random(); 90 } 91 92 /* get_crandom - correlated random number generator 93 * Next number depends on last value. 94 * rho is scaled to avoid floating point. 95 */ 96 static unsigned long get_crandom(struct crndstate *state) 97 { 98 u64 value, rho; 99 unsigned long answer; 100 101 if (state->rho == 0) /* no correllation */ 102 return net_random(); 103 104 value = net_random(); 105 rho = (u64)state->rho + 1; 106 answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32; 107 state->last = answer; 108 return answer; 109 } 110 111 /* tabledist - return a pseudo-randomly distributed value with mean mu and 112 * std deviation sigma. Uses table lookup to approximate the desired 113 * distribution, and a uniformly-distributed pseudo-random source. 114 */ 115 static long tabledist(unsigned long mu, long sigma, 116 struct crndstate *state, const struct disttable *dist) 117 { 118 long t, x; 119 unsigned long rnd; 120 121 if (sigma == 0) 122 return mu; 123 124 rnd = get_crandom(state); 125 126 /* default uniform distribution */ 127 if (dist == NULL) 128 return (rnd % (2*sigma)) - sigma + mu; 129 130 t = dist->table[rnd % dist->size]; 131 x = (sigma % NETEM_DIST_SCALE) * t; 132 if (x >= 0) 133 x += NETEM_DIST_SCALE/2; 134 else 135 x -= NETEM_DIST_SCALE/2; 136 137 return x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu; 138 } 139 140 /* Put skb in the private delayed queue. */ 141 static int netem_delay(struct Qdisc *sch, struct sk_buff *skb) 142 { 143 struct netem_sched_data *q = qdisc_priv(sch); 144 psched_tdiff_t td; 145 psched_time_t now; 146 147 PSCHED_GET_TIME(now); 148 td = tabledist(q->latency, q->jitter, &q->delay_cor, q->delay_dist); 149 150 /* Always queue at tail to keep packets in order */ 151 if (likely(q->delayed.qlen < q->limit)) { 152 struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb; 153 154 PSCHED_TADD2(now, td, cb->time_to_send); 155 156 pr_debug("netem_delay: skb=%p now=%llu tosend=%llu\n", skb, 157 now, cb->time_to_send); 158 159 __skb_queue_tail(&q->delayed, skb); 160 return NET_XMIT_SUCCESS; 161 } 162 163 pr_debug("netem_delay: queue over limit %d\n", q->limit); 164 sch->qstats.overlimits++; 165 kfree_skb(skb); 166 return NET_XMIT_DROP; 167 } 168 169 /* 170 * Move a packet that is ready to send from the delay holding 171 * list to the underlying qdisc. 172 */ 173 static int netem_run(struct Qdisc *sch) 174 { 175 struct netem_sched_data *q = qdisc_priv(sch); 176 struct sk_buff *skb; 177 psched_time_t now; 178 179 PSCHED_GET_TIME(now); 180 181 skb = skb_peek(&q->delayed); 182 if (skb) { 183 const struct netem_skb_cb *cb 184 = (const struct netem_skb_cb *)skb->cb; 185 long delay 186 = PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now)); 187 pr_debug("netem_run: skb=%p delay=%ld\n", skb, delay); 188 189 /* if more time remaining? */ 190 if (delay > 0) { 191 mod_timer(&q->timer, jiffies + delay); 192 return 1; 193 } 194 195 __skb_unlink(skb, &q->delayed); 196 197 if (q->qdisc->enqueue(skb, q->qdisc)) { 198 sch->q.qlen--; 199 sch->qstats.drops++; 200 } 201 } 202 203 return 0; 204 } 205 206 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch) 207 { 208 struct netem_sched_data *q = qdisc_priv(sch); 209 int ret; 210 211 pr_debug("netem_enqueue skb=%p\n", skb); 212 213 /* Random packet drop 0 => none, ~0 => all */ 214 if (q->loss && q->loss >= get_crandom(&q->loss_cor)) { 215 pr_debug("netem_enqueue: random loss\n"); 216 sch->qstats.drops++; 217 kfree_skb(skb); 218 return 0; /* lie about loss so TCP doesn't know */ 219 } 220 221 /* Random duplication */ 222 if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) { 223 struct sk_buff *skb2; 224 225 skb2 = skb_clone(skb, GFP_ATOMIC); 226 if (skb2 && netem_delay(sch, skb2) == NET_XMIT_SUCCESS) { 227 struct Qdisc *qp; 228 229 /* Since one packet can generate two packets in the 230 * queue, the parent's qlen accounting gets confused, 231 * so fix it. 232 */ 233 qp = qdisc_lookup(sch->dev, TC_H_MAJ(sch->parent)); 234 if (qp) 235 qp->q.qlen++; 236 237 sch->q.qlen++; 238 sch->bstats.bytes += skb2->len; 239 sch->bstats.packets++; 240 } else 241 sch->qstats.drops++; 242 } 243 244 /* If doing simple delay then gap == 0 so all packets 245 * go into the delayed holding queue 246 * otherwise if doing out of order only "1 out of gap" 247 * packets will be delayed. 248 */ 249 if (q->counter < q->gap) { 250 ++q->counter; 251 ret = q->qdisc->enqueue(skb, q->qdisc); 252 } else { 253 q->counter = 0; 254 ret = netem_delay(sch, skb); 255 netem_run(sch); 256 } 257 258 if (likely(ret == NET_XMIT_SUCCESS)) { 259 sch->q.qlen++; 260 sch->bstats.bytes += skb->len; 261 sch->bstats.packets++; 262 } else 263 sch->qstats.drops++; 264 265 pr_debug("netem: enqueue ret %d\n", ret); 266 return ret; 267 } 268 269 /* Requeue packets but don't change time stamp */ 270 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch) 271 { 272 struct netem_sched_data *q = qdisc_priv(sch); 273 int ret; 274 275 if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0) { 276 sch->q.qlen++; 277 sch->qstats.requeues++; 278 } 279 280 return ret; 281 } 282 283 static unsigned int netem_drop(struct Qdisc* sch) 284 { 285 struct netem_sched_data *q = qdisc_priv(sch); 286 unsigned int len; 287 288 if ((len = q->qdisc->ops->drop(q->qdisc)) != 0) { 289 sch->q.qlen--; 290 sch->qstats.drops++; 291 } 292 return len; 293 } 294 295 static struct sk_buff *netem_dequeue(struct Qdisc *sch) 296 { 297 struct netem_sched_data *q = qdisc_priv(sch); 298 struct sk_buff *skb; 299 int pending; 300 301 pending = netem_run(sch); 302 303 skb = q->qdisc->dequeue(q->qdisc); 304 if (skb) { 305 pr_debug("netem_dequeue: return skb=%p\n", skb); 306 sch->q.qlen--; 307 sch->flags &= ~TCQ_F_THROTTLED; 308 } 309 else if (pending) { 310 pr_debug("netem_dequeue: throttling\n"); 311 sch->flags |= TCQ_F_THROTTLED; 312 } 313 314 return skb; 315 } 316 317 static void netem_watchdog(unsigned long arg) 318 { 319 struct Qdisc *sch = (struct Qdisc *)arg; 320 321 pr_debug("netem_watchdog qlen=%d\n", sch->q.qlen); 322 sch->flags &= ~TCQ_F_THROTTLED; 323 netif_schedule(sch->dev); 324 } 325 326 static void netem_reset(struct Qdisc *sch) 327 { 328 struct netem_sched_data *q = qdisc_priv(sch); 329 330 qdisc_reset(q->qdisc); 331 skb_queue_purge(&q->delayed); 332 333 sch->q.qlen = 0; 334 sch->flags &= ~TCQ_F_THROTTLED; 335 del_timer_sync(&q->timer); 336 } 337 338 static int set_fifo_limit(struct Qdisc *q, int limit) 339 { 340 struct rtattr *rta; 341 int ret = -ENOMEM; 342 343 rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL); 344 if (rta) { 345 rta->rta_type = RTM_NEWQDISC; 346 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt)); 347 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit; 348 349 ret = q->ops->change(q, rta); 350 kfree(rta); 351 } 352 return ret; 353 } 354 355 /* 356 * Distribution data is a variable size payload containing 357 * signed 16 bit values. 358 */ 359 static int get_dist_table(struct Qdisc *sch, const struct rtattr *attr) 360 { 361 struct netem_sched_data *q = qdisc_priv(sch); 362 unsigned long n = RTA_PAYLOAD(attr)/sizeof(__s16); 363 const __s16 *data = RTA_DATA(attr); 364 struct disttable *d; 365 int i; 366 367 if (n > 65536) 368 return -EINVAL; 369 370 d = kmalloc(sizeof(*d) + n*sizeof(d->table[0]), GFP_KERNEL); 371 if (!d) 372 return -ENOMEM; 373 374 d->size = n; 375 for (i = 0; i < n; i++) 376 d->table[i] = data[i]; 377 378 spin_lock_bh(&sch->dev->queue_lock); 379 d = xchg(&q->delay_dist, d); 380 spin_unlock_bh(&sch->dev->queue_lock); 381 382 kfree(d); 383 return 0; 384 } 385 386 static int get_correlation(struct Qdisc *sch, const struct rtattr *attr) 387 { 388 struct netem_sched_data *q = qdisc_priv(sch); 389 const struct tc_netem_corr *c = RTA_DATA(attr); 390 391 if (RTA_PAYLOAD(attr) != sizeof(*c)) 392 return -EINVAL; 393 394 init_crandom(&q->delay_cor, c->delay_corr); 395 init_crandom(&q->loss_cor, c->loss_corr); 396 init_crandom(&q->dup_cor, c->dup_corr); 397 return 0; 398 } 399 400 static int netem_change(struct Qdisc *sch, struct rtattr *opt) 401 { 402 struct netem_sched_data *q = qdisc_priv(sch); 403 struct tc_netem_qopt *qopt; 404 int ret; 405 406 if (opt == NULL || RTA_PAYLOAD(opt) < sizeof(*qopt)) 407 return -EINVAL; 408 409 qopt = RTA_DATA(opt); 410 ret = set_fifo_limit(q->qdisc, qopt->limit); 411 if (ret) { 412 pr_debug("netem: can't set fifo limit\n"); 413 return ret; 414 } 415 416 q->latency = qopt->latency; 417 q->jitter = qopt->jitter; 418 q->limit = qopt->limit; 419 q->gap = qopt->gap; 420 q->loss = qopt->loss; 421 q->duplicate = qopt->duplicate; 422 423 /* Handle nested options after initial queue options. 424 * Should have put all options in nested format but too late now. 425 */ 426 if (RTA_PAYLOAD(opt) > sizeof(*qopt)) { 427 struct rtattr *tb[TCA_NETEM_MAX]; 428 if (rtattr_parse(tb, TCA_NETEM_MAX, 429 RTA_DATA(opt) + sizeof(*qopt), 430 RTA_PAYLOAD(opt) - sizeof(*qopt))) 431 return -EINVAL; 432 433 if (tb[TCA_NETEM_CORR-1]) { 434 ret = get_correlation(sch, tb[TCA_NETEM_CORR-1]); 435 if (ret) 436 return ret; 437 } 438 439 if (tb[TCA_NETEM_DELAY_DIST-1]) { 440 ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST-1]); 441 if (ret) 442 return ret; 443 } 444 } 445 446 447 return 0; 448 } 449 450 static int netem_init(struct Qdisc *sch, struct rtattr *opt) 451 { 452 struct netem_sched_data *q = qdisc_priv(sch); 453 int ret; 454 455 if (!opt) 456 return -EINVAL; 457 458 skb_queue_head_init(&q->delayed); 459 init_timer(&q->timer); 460 q->timer.function = netem_watchdog; 461 q->timer.data = (unsigned long) sch; 462 q->counter = 0; 463 464 q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops); 465 if (!q->qdisc) { 466 pr_debug("netem: qdisc create failed\n"); 467 return -ENOMEM; 468 } 469 470 ret = netem_change(sch, opt); 471 if (ret) { 472 pr_debug("netem: change failed\n"); 473 qdisc_destroy(q->qdisc); 474 } 475 return ret; 476 } 477 478 static void netem_destroy(struct Qdisc *sch) 479 { 480 struct netem_sched_data *q = qdisc_priv(sch); 481 482 del_timer_sync(&q->timer); 483 qdisc_destroy(q->qdisc); 484 kfree(q->delay_dist); 485 } 486 487 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb) 488 { 489 const struct netem_sched_data *q = qdisc_priv(sch); 490 unsigned char *b = skb->tail; 491 struct rtattr *rta = (struct rtattr *) b; 492 struct tc_netem_qopt qopt; 493 struct tc_netem_corr cor; 494 495 qopt.latency = q->latency; 496 qopt.jitter = q->jitter; 497 qopt.limit = q->limit; 498 qopt.loss = q->loss; 499 qopt.gap = q->gap; 500 qopt.duplicate = q->duplicate; 501 RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt); 502 503 cor.delay_corr = q->delay_cor.rho; 504 cor.loss_corr = q->loss_cor.rho; 505 cor.dup_corr = q->dup_cor.rho; 506 RTA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor); 507 rta->rta_len = skb->tail - b; 508 509 return skb->len; 510 511 rtattr_failure: 512 skb_trim(skb, b - skb->data); 513 return -1; 514 } 515 516 static int netem_dump_class(struct Qdisc *sch, unsigned long cl, 517 struct sk_buff *skb, struct tcmsg *tcm) 518 { 519 struct netem_sched_data *q = qdisc_priv(sch); 520 521 if (cl != 1) /* only one class */ 522 return -ENOENT; 523 524 tcm->tcm_handle |= TC_H_MIN(1); 525 tcm->tcm_info = q->qdisc->handle; 526 527 return 0; 528 } 529 530 static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, 531 struct Qdisc **old) 532 { 533 struct netem_sched_data *q = qdisc_priv(sch); 534 535 if (new == NULL) 536 new = &noop_qdisc; 537 538 sch_tree_lock(sch); 539 *old = xchg(&q->qdisc, new); 540 qdisc_reset(*old); 541 sch->q.qlen = 0; 542 sch_tree_unlock(sch); 543 544 return 0; 545 } 546 547 static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg) 548 { 549 struct netem_sched_data *q = qdisc_priv(sch); 550 return q->qdisc; 551 } 552 553 static unsigned long netem_get(struct Qdisc *sch, u32 classid) 554 { 555 return 1; 556 } 557 558 static void netem_put(struct Qdisc *sch, unsigned long arg) 559 { 560 } 561 562 static int netem_change_class(struct Qdisc *sch, u32 classid, u32 parentid, 563 struct rtattr **tca, unsigned long *arg) 564 { 565 return -ENOSYS; 566 } 567 568 static int netem_delete(struct Qdisc *sch, unsigned long arg) 569 { 570 return -ENOSYS; 571 } 572 573 static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker) 574 { 575 if (!walker->stop) { 576 if (walker->count >= walker->skip) 577 if (walker->fn(sch, 1, walker) < 0) { 578 walker->stop = 1; 579 return; 580 } 581 walker->count++; 582 } 583 } 584 585 static struct tcf_proto **netem_find_tcf(struct Qdisc *sch, unsigned long cl) 586 { 587 return NULL; 588 } 589 590 static struct Qdisc_class_ops netem_class_ops = { 591 .graft = netem_graft, 592 .leaf = netem_leaf, 593 .get = netem_get, 594 .put = netem_put, 595 .change = netem_change_class, 596 .delete = netem_delete, 597 .walk = netem_walk, 598 .tcf_chain = netem_find_tcf, 599 .dump = netem_dump_class, 600 }; 601 602 static struct Qdisc_ops netem_qdisc_ops = { 603 .id = "netem", 604 .cl_ops = &netem_class_ops, 605 .priv_size = sizeof(struct netem_sched_data), 606 .enqueue = netem_enqueue, 607 .dequeue = netem_dequeue, 608 .requeue = netem_requeue, 609 .drop = netem_drop, 610 .init = netem_init, 611 .reset = netem_reset, 612 .destroy = netem_destroy, 613 .change = netem_change, 614 .dump = netem_dump, 615 .owner = THIS_MODULE, 616 }; 617 618 619 static int __init netem_module_init(void) 620 { 621 return register_qdisc(&netem_qdisc_ops); 622 } 623 static void __exit netem_module_exit(void) 624 { 625 unregister_qdisc(&netem_qdisc_ops); 626 } 627 module_init(netem_module_init) 628 module_exit(netem_module_exit) 629 MODULE_LICENSE("GPL"); 630