net/sched/sch_netem.c

   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 timer_list timer;
  57
  58         u32 latency;
  59         u32 loss;
  60         u32 limit;
  61         u32 counter;
  62         u32 gap;
  63         u32 jitter;
  64         u32 duplicate;
  65         u32 reorder;
  66
  67         struct crndstate {
  68                 unsigned long last;
  69                 unsigned long rho;
  70         } delay_cor, loss_cor, dup_cor, reorder_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 /*
 141  * Insert one skb into qdisc.
 142  * Note: parent depends on return value to account for queue length.
 143  *      NET_XMIT_DROP: queue length didn't change.
 144  *      NET_XMIT_SUCCESS: one skb was queued.
 145  */
 146 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 147 {
 148         struct netem_sched_data *q = qdisc_priv(sch);
 149         struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
 150         struct sk_buff *skb2;
 151         int ret;
 152         int count = 1;
 153
 154         pr_debug("netem_enqueue skb=%p\n", skb);
 155
 156         /* Random duplication */
 157         if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
 158                 ++count;
 159
 160         /* Random packet drop 0 => none, ~0 => all */
 161         if (q->loss && q->loss >= get_crandom(&q->loss_cor))
 162                 --count;
 163
 164         if (count == 0) {
 165                 sch->qstats.drops++;
 166                 kfree_skb(skb);
 167                 return NET_XMIT_DROP;
 168         }
 169
 170         /*
 171          * If we need to duplicate packet, then re-insert at top of the
 172          * qdisc tree, since parent queuer expects that only one
 173          * skb will be queued.
 174          */
 175         if (count > 1 && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) {
 176                 struct Qdisc *rootq = sch->dev->qdisc;
 177                 u32 dupsave = q->duplicate; /* prevent duplicating a dup... */
 178                 q->duplicate = 0;
 179
 180                 rootq->enqueue(skb2, rootq);
 181                 q->duplicate = dupsave;
 182         }
 183
 184         if (q->gap == 0                 /* not doing reordering */
 185             || q->counter < q->gap      /* inside last reordering gap */
 186             || q->reorder < get_crandom(&q->reorder_cor)) {
 187                 psched_time_t now;
 188                 PSCHED_GET_TIME(now);
 189                 PSCHED_TADD2(now, tabledist(q->latency, q->jitter,
 190                                             &q->delay_cor, q->delay_dist),
 191                              cb->time_to_send);
 192                 ++q->counter;
 193                 ret = q->qdisc->enqueue(skb, q->qdisc);
 194         } else {
 195                 /*
 196                  * Do re-ordering by putting one out of N packets at the front
 197                  * of the queue.
 198                  */
 199                 PSCHED_GET_TIME(cb->time_to_send);
 200                 q->counter = 0;
 201                 ret = q->qdisc->ops->requeue(skb, q->qdisc);
 202         }
 203
 204         if (likely(ret == NET_XMIT_SUCCESS)) {
 205                 sch->q.qlen++;
 206                 sch->bstats.bytes += skb->len;
 207                 sch->bstats.packets++;
 208         } else
 209                 sch->qstats.drops++;
 210
 211         pr_debug("netem: enqueue ret %d\n", ret);
 212         return ret;
 213 }
 214
 215 /* Requeue packets but don't change time stamp */
 216 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
 217 {
 218         struct netem_sched_data *q = qdisc_priv(sch);
 219         int ret;
 220
 221         if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0) {
 222                 sch->q.qlen++;
 223                 sch->qstats.requeues++;
 224         }
 225
 226         return ret;
 227 }
 228
 229 static unsigned int netem_drop(struct Qdisc* sch)
 230 {
 231         struct netem_sched_data *q = qdisc_priv(sch);
 232         unsigned int len;
 233
 234         if ((len = q->qdisc->ops->drop(q->qdisc)) != 0) {
 235                 sch->q.qlen--;
 236                 sch->qstats.drops++;
 237         }
 238         return len;
 239 }
 240
 241 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
 242 {
 243         struct netem_sched_data *q = qdisc_priv(sch);
 244         struct sk_buff *skb;
 245
 246         skb = q->qdisc->dequeue(q->qdisc);
 247         if (skb) {
 248                 const struct netem_skb_cb *cb
 249                         = (const struct netem_skb_cb *)skb->cb;
 250                 psched_time_t now;
 251                 long delay;
 252
 253                 /* if more time remaining? */
 254                 PSCHED_GET_TIME(now);
 255                 delay = PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now));
 256                 pr_debug("netem_run: skb=%p delay=%ld\n", skb, delay);
 257                 if (delay <= 0) {
 258                         pr_debug("netem_dequeue: return skb=%p\n", skb);
 259                         sch->q.qlen--;
 260                         sch->flags &= ~TCQ_F_THROTTLED;
 261                         return skb;
 262                 }
 263
 264                 mod_timer(&q->timer, jiffies + delay);
 265                 sch->flags |= TCQ_F_THROTTLED;
 266
 267                 if (q->qdisc->ops->requeue(skb, q->qdisc) != 0)
 268                         sch->qstats.drops++;
 269         }
 270
 271         return NULL;
 272 }
 273
 274 static void netem_watchdog(unsigned long arg)
 275 {
 276         struct Qdisc *sch = (struct Qdisc *)arg;
 277
 278         pr_debug("netem_watchdog qlen=%d\n", sch->q.qlen);
 279         sch->flags &= ~TCQ_F_THROTTLED;
 280         netif_schedule(sch->dev);
 281 }
 282
 283 static void netem_reset(struct Qdisc *sch)
 284 {
 285         struct netem_sched_data *q = qdisc_priv(sch);
 286
 287         qdisc_reset(q->qdisc);
 288         sch->q.qlen = 0;
 289         sch->flags &= ~TCQ_F_THROTTLED;
 290         del_timer_sync(&q->timer);
 291 }
 292
 293 static int set_fifo_limit(struct Qdisc *q, int limit)
 294 {
 295         struct rtattr *rta;
 296         int ret = -ENOMEM;
 297
 298         rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
 299         if (rta) {
 300                 rta->rta_type = RTM_NEWQDISC;
 301                 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
 302                 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
 303
 304                 ret = q->ops->change(q, rta);
 305                 kfree(rta);
 306         }
 307         return ret;
 308 }
 309
 310 /*
 311  * Distribution data is a variable size payload containing
 312  * signed 16 bit values.
 313  */
 314 static int get_dist_table(struct Qdisc *sch, const struct rtattr *attr)
 315 {
 316         struct netem_sched_data *q = qdisc_priv(sch);
 317         unsigned long n = RTA_PAYLOAD(attr)/sizeof(__s16);
 318         const __s16 *data = RTA_DATA(attr);
 319         struct disttable *d;
 320         int i;
 321
 322         if (n > 65536)
 323                 return -EINVAL;
 324
 325         d = kmalloc(sizeof(*d) + n*sizeof(d->table[0]), GFP_KERNEL);
 326         if (!d)
 327                 return -ENOMEM;
 328
 329         d->size = n;
 330         for (i = 0; i < n; i++)
 331                 d->table[i] = data[i];
 332
 333         spin_lock_bh(&sch->dev->queue_lock);
 334         d = xchg(&q->delay_dist, d);
 335         spin_unlock_bh(&sch->dev->queue_lock);
 336
 337         kfree(d);
 338         return 0;
 339 }
 340
 341 static int get_correlation(struct Qdisc *sch, const struct rtattr *attr)
 342 {
 343         struct netem_sched_data *q = qdisc_priv(sch);
 344         const struct tc_netem_corr *c = RTA_DATA(attr);
 345
 346         if (RTA_PAYLOAD(attr) != sizeof(*c))
 347                 return -EINVAL;
 348
 349         init_crandom(&q->delay_cor, c->delay_corr);
 350         init_crandom(&q->loss_cor, c->loss_corr);
 351         init_crandom(&q->dup_cor, c->dup_corr);
 352         return 0;
 353 }
 354
 355 static int get_reorder(struct Qdisc *sch, const struct rtattr *attr)
 356 {
 357         struct netem_sched_data *q = qdisc_priv(sch);
 358         const struct tc_netem_reorder *r = RTA_DATA(attr);
 359
 360         if (RTA_PAYLOAD(attr) != sizeof(*r))
 361                 return -EINVAL;
 362
 363         q->reorder = r->probability;
 364         init_crandom(&q->reorder_cor, r->correlation);
 365         return 0;
 366 }
 367
 368 static int netem_change(struct Qdisc *sch, struct rtattr *opt)
 369 {
 370         struct netem_sched_data *q = qdisc_priv(sch);
 371         struct tc_netem_qopt *qopt;
 372         int ret;
 373
 374         if (opt == NULL || RTA_PAYLOAD(opt) < sizeof(*qopt))
 375                 return -EINVAL;
 376
 377         qopt = RTA_DATA(opt);
 378         ret = set_fifo_limit(q->qdisc, qopt->limit);
 379         if (ret) {
 380                 pr_debug("netem: can't set fifo limit\n");
 381                 return ret;
 382         }
 383
 384         q->latency = qopt->latency;
 385         q->jitter = qopt->jitter;
 386         q->limit = qopt->limit;
 387         q->gap = qopt->gap;
 388         q->counter = 0;
 389         q->loss = qopt->loss;
 390         q->duplicate = qopt->duplicate;
 391
 392         /* for compatiablity with earlier versions.
 393          * if gap is set, need to assume 100% probablity
 394          */
 395         q->reorder = ~0;
 396
 397         /* Handle nested options after initial queue options.
 398          * Should have put all options in nested format but too late now.
 399          */
 400         if (RTA_PAYLOAD(opt) > sizeof(*qopt)) {
 401                 struct rtattr *tb[TCA_NETEM_MAX];
 402                 if (rtattr_parse(tb, TCA_NETEM_MAX,
 403                                  RTA_DATA(opt) + sizeof(*qopt),
 404                                  RTA_PAYLOAD(opt) - sizeof(*qopt)))
 405                         return -EINVAL;
 406
 407                 if (tb[TCA_NETEM_CORR-1]) {
 408                         ret = get_correlation(sch, tb[TCA_NETEM_CORR-1]);
 409                         if (ret)
 410                                 return ret;
 411                 }
 412
 413                 if (tb[TCA_NETEM_DELAY_DIST-1]) {
 414                         ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST-1]);
 415                         if (ret)
 416                                 return ret;
 417                 }
 418                 if (tb[TCA_NETEM_REORDER-1]) {
 419                         ret = get_reorder(sch, tb[TCA_NETEM_REORDER-1]);
 420                         if (ret)
 421                                 return ret;
 422                 }
 423         }
 424
 425
 426         return 0;
 427 }
 428
 429 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
 430 {
 431         struct netem_sched_data *q = qdisc_priv(sch);
 432         int ret;
 433
 434         if (!opt)
 435                 return -EINVAL;
 436
 437         init_timer(&q->timer);
 438         q->timer.function = netem_watchdog;
 439         q->timer.data = (unsigned long) sch;
 440
 441         q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
 442         if (!q->qdisc) {
 443                 pr_debug("netem: qdisc create failed\n");
 444                 return -ENOMEM;
 445         }
 446
 447         ret = netem_change(sch, opt);
 448         if (ret) {
 449                 pr_debug("netem: change failed\n");
 450                 qdisc_destroy(q->qdisc);
 451         }
 452         return ret;
 453 }
 454
 455 static void netem_destroy(struct Qdisc *sch)
 456 {
 457         struct netem_sched_data *q = qdisc_priv(sch);
 458
 459         del_timer_sync(&q->timer);
 460         qdisc_destroy(q->qdisc);
 461         kfree(q->delay_dist);
 462 }
 463
 464 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
 465 {
 466         const struct netem_sched_data *q = qdisc_priv(sch);
 467         unsigned char    *b = skb->tail;
 468         struct rtattr *rta = (struct rtattr *) b;
 469         struct tc_netem_qopt qopt;
 470         struct tc_netem_corr cor;
 471         struct tc_netem_reorder reorder;
 472
 473         qopt.latency = q->latency;
 474         qopt.jitter = q->jitter;
 475         qopt.limit = q->limit;
 476         qopt.loss = q->loss;
 477         qopt.gap = q->gap;
 478         qopt.duplicate = q->duplicate;
 479         RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 480
 481         cor.delay_corr = q->delay_cor.rho;
 482         cor.loss_corr = q->loss_cor.rho;
 483         cor.dup_corr = q->dup_cor.rho;
 484         RTA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor);
 485
 486         reorder.probability = q->reorder;
 487         reorder.correlation = q->reorder_cor.rho;
 488         RTA_PUT(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder);
 489
 490         rta->rta_len = skb->tail - b;
 491
 492         return skb->len;
 493
 494 rtattr_failure:
 495         skb_trim(skb, b - skb->data);
 496         return -1;
 497 }
 498
 499 static int netem_dump_class(struct Qdisc *sch, unsigned long cl,
 500                           struct sk_buff *skb, struct tcmsg *tcm)
 501 {
 502         struct netem_sched_data *q = qdisc_priv(sch);
 503
 504         if (cl != 1)    /* only one class */
 505                 return -ENOENT;
 506
 507         tcm->tcm_handle |= TC_H_MIN(1);
 508         tcm->tcm_info = q->qdisc->handle;
 509
 510         return 0;
 511 }
 512
 513 static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 514                      struct Qdisc **old)
 515 {
 516         struct netem_sched_data *q = qdisc_priv(sch);
 517
 518         if (new == NULL)
 519                 new = &noop_qdisc;
 520
 521         sch_tree_lock(sch);
 522         *old = xchg(&q->qdisc, new);
 523         qdisc_reset(*old);
 524         sch->q.qlen = 0;
 525         sch_tree_unlock(sch);
 526
 527         return 0;
 528 }
 529
 530 static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg)
 531 {
 532         struct netem_sched_data *q = qdisc_priv(sch);
 533         return q->qdisc;
 534 }
 535
 536 static unsigned long netem_get(struct Qdisc *sch, u32 classid)
 537 {
 538         return 1;
 539 }
 540
 541 static void netem_put(struct Qdisc *sch, unsigned long arg)
 542 {
 543 }
 544
 545 static int netem_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 546                             struct rtattr **tca, unsigned long *arg)
 547 {
 548         return -ENOSYS;
 549 }
 550
 551 static int netem_delete(struct Qdisc *sch, unsigned long arg)
 552 {
 553         return -ENOSYS;
 554 }
 555
 556 static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 557 {
 558         if (!walker->stop) {
 559                 if (walker->count >= walker->skip)
 560                         if (walker->fn(sch, 1, walker) < 0) {
 561                                 walker->stop = 1;
 562                                 return;
 563                         }
 564                 walker->count++;
 565         }
 566 }
 567
 568 static struct tcf_proto **netem_find_tcf(struct Qdisc *sch, unsigned long cl)
 569 {
 570         return NULL;
 571 }
 572
 573 static struct Qdisc_class_ops netem_class_ops = {
 574         .graft          =       netem_graft,
 575         .leaf           =       netem_leaf,
 576         .get            =       netem_get,
 577         .put            =       netem_put,
 578         .change         =       netem_change_class,
 579         .delete         =       netem_delete,
 580         .walk           =       netem_walk,
 581         .tcf_chain      =       netem_find_tcf,
 582         .dump           =       netem_dump_class,
 583 };
 584
 585 static struct Qdisc_ops netem_qdisc_ops = {
 586         .id             =       "netem",
 587         .cl_ops         =       &netem_class_ops,
 588         .priv_size      =       sizeof(struct netem_sched_data),
 589         .enqueue        =       netem_enqueue,
 590         .dequeue        =       netem_dequeue,
 591         .requeue        =       netem_requeue,
 592         .drop           =       netem_drop,
 593         .init           =       netem_init,
 594         .reset          =       netem_reset,
 595         .destroy        =       netem_destroy,
 596         .change         =       netem_change,
 597         .dump           =       netem_dump,
 598         .owner          =       THIS_MODULE,
 599 };
 600
 601
 602 static int __init netem_module_init(void)
 603 {
 604         return register_qdisc(&netem_qdisc_ops);
 605 }
 606 static void __exit netem_module_exit(void)
 607 {
 608         unregister_qdisc(&netem_qdisc_ops);
 609 }
 610 module_init(netem_module_init)
 611 module_exit(netem_module_exit)
 612 MODULE_LICENSE("GPL");