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