2 * net/sched/sch_netem.c Network emulator
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
9 * Many of the algorithms and ideas for this came from
10 * NIST Net which is not copyrighted.
12 * Authors: Stephen Hemminger <shemminger@osdl.org>
13 * Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
16 #include <linux/module.h>
17 #include <linux/bitops.h>
18 #include <linux/types.h>
19 #include <linux/kernel.h>
20 #include <linux/errno.h>
21 #include <linux/netdevice.h>
22 #include <linux/skbuff.h>
23 #include <linux/rtnetlink.h>
25 #include <net/netlink.h>
26 #include <net/pkt_sched.h>
30 /* Network Emulation Queuing algorithm.
31 ====================================
33 Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
34 Network Emulation Tool
35 [2] Luigi Rizzo, DummyNet for FreeBSD
37 ----------------------------------------------------------------
39 This started out as a simple way to delay outgoing packets to
40 test TCP but has grown to include most of the functionality
41 of a full blown network emulator like NISTnet. It can delay
42 packets and add random jitter (and correlation). The random
43 distribution can be loaded from a table as well to provide
44 normal, Pareto, or experimental curves. Packet loss,
45 duplication, and reordering can also be emulated.
47 This qdisc does not do classification that can be handled in
48 layering other disciplines. It does not need to do bandwidth
49 control either since that can be handled by using token
50 bucket or other rate control.
52 The simulator is limited by the Linux timer resolution
53 and will create packet bursts on the HZ boundary (1ms).
56 struct netem_sched_data {
58 struct qdisc_watchdog watchdog;
73 } delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor;
81 /* Time stamp put into socket buffer control block */
83 psched_time_t time_to_send;
86 /* init_crandom - initialize correlated random number generator
87 * Use entropy source for initial seed.
89 static void init_crandom(struct crndstate *state, unsigned long rho)
92 state->last = net_random();
95 /* get_crandom - correlated random number generator
96 * Next number depends on last value.
97 * rho is scaled to avoid floating point.
99 static unsigned long get_crandom(struct crndstate *state)
102 unsigned long answer;
104 if (state->rho == 0) /* no correllation */
107 value = net_random();
108 rho = (u64)state->rho + 1;
109 answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
110 state->last = answer;
114 /* tabledist - return a pseudo-randomly distributed value with mean mu and
115 * std deviation sigma. Uses table lookup to approximate the desired
116 * distribution, and a uniformly-distributed pseudo-random source.
118 static long tabledist(unsigned long mu, long sigma,
119 struct crndstate *state, const struct disttable *dist)
127 rnd = get_crandom(state);
129 /* default uniform distribution */
131 return (rnd % (2*sigma)) - sigma + mu;
133 t = dist->table[rnd % dist->size];
134 x = (sigma % NETEM_DIST_SCALE) * t;
136 x += NETEM_DIST_SCALE/2;
138 x -= NETEM_DIST_SCALE/2;
140 return x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu;
144 * Insert one skb into qdisc.
145 * Note: parent depends on return value to account for queue length.
146 * NET_XMIT_DROP: queue length didn't change.
147 * NET_XMIT_SUCCESS: one skb was queued.
149 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
151 struct netem_sched_data *q = qdisc_priv(sch);
152 /* We don't fill cb now as skb_unshare() may invalidate it */
153 struct netem_skb_cb *cb;
154 struct sk_buff *skb2;
158 pr_debug("netem_enqueue skb=%p\n", skb);
160 /* Random duplication */
161 if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
164 /* Random packet drop 0 => none, ~0 => all */
165 if (q->loss && q->loss >= get_crandom(&q->loss_cor))
171 return NET_XMIT_BYPASS;
177 * If we need to duplicate packet, then re-insert at top of the
178 * qdisc tree, since parent queuer expects that only one
179 * skb will be queued.
181 if (count > 1 && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) {
182 struct Qdisc *rootq = sch->dev->qdisc;
183 u32 dupsave = q->duplicate; /* prevent duplicating a dup... */
186 rootq->enqueue(skb2, rootq);
187 q->duplicate = dupsave;
191 * Randomized packet corruption.
192 * Make copy if needed since we are modifying
193 * If packet is going to be hardware checksummed, then
194 * do it now in software before we mangle it.
196 if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor)) {
197 if (!(skb = skb_unshare(skb, GFP_ATOMIC))
198 || (skb->ip_summed == CHECKSUM_PARTIAL
199 && skb_checksum_help(skb))) {
201 return NET_XMIT_DROP;
204 skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8);
207 cb = (struct netem_skb_cb *)skb->cb;
208 if (q->gap == 0 /* not doing reordering */
209 || q->counter < q->gap /* inside last reordering gap */
210 || q->reorder < get_crandom(&q->reorder_cor)) {
212 psched_tdiff_t delay;
214 delay = tabledist(q->latency, q->jitter,
215 &q->delay_cor, q->delay_dist);
217 PSCHED_GET_TIME(now);
218 PSCHED_TADD2(now, delay, cb->time_to_send);
220 ret = q->qdisc->enqueue(skb, q->qdisc);
223 * Do re-ordering by putting one out of N packets at the front
226 PSCHED_GET_TIME(cb->time_to_send);
228 ret = q->qdisc->ops->requeue(skb, q->qdisc);
231 if (likely(ret == NET_XMIT_SUCCESS)) {
233 sch->bstats.bytes += skb->len;
234 sch->bstats.packets++;
238 pr_debug("netem: enqueue ret %d\n", ret);
242 /* Requeue packets but don't change time stamp */
243 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
245 struct netem_sched_data *q = qdisc_priv(sch);
248 if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0) {
250 sch->qstats.requeues++;
256 static unsigned int netem_drop(struct Qdisc* sch)
258 struct netem_sched_data *q = qdisc_priv(sch);
259 unsigned int len = 0;
261 if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
268 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
270 struct netem_sched_data *q = qdisc_priv(sch);
273 skb = q->qdisc->dequeue(q->qdisc);
275 const struct netem_skb_cb *cb
276 = (const struct netem_skb_cb *)skb->cb;
279 /* if more time remaining? */
280 PSCHED_GET_TIME(now);
282 if (PSCHED_TLESS(cb->time_to_send, now)) {
283 pr_debug("netem_dequeue: return skb=%p\n", skb);
285 sch->flags &= ~TCQ_F_THROTTLED;
288 qdisc_watchdog_schedule(&q->watchdog, cb->time_to_send);
290 if (q->qdisc->ops->requeue(skb, q->qdisc) != NET_XMIT_SUCCESS) {
291 qdisc_tree_decrease_qlen(q->qdisc, 1);
293 printk(KERN_ERR "netem: queue discpline %s could not requeue\n",
302 static void netem_reset(struct Qdisc *sch)
304 struct netem_sched_data *q = qdisc_priv(sch);
306 qdisc_reset(q->qdisc);
308 qdisc_watchdog_cancel(&q->watchdog);
311 /* Pass size change message down to embedded FIFO */
312 static int set_fifo_limit(struct Qdisc *q, int limit)
317 /* Hack to avoid sending change message to non-FIFO */
318 if (strncmp(q->ops->id + 1, "fifo", 4) != 0)
321 rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
323 rta->rta_type = RTM_NEWQDISC;
324 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
325 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
327 ret = q->ops->change(q, rta);
334 * Distribution data is a variable size payload containing
335 * signed 16 bit values.
337 static int get_dist_table(struct Qdisc *sch, const struct rtattr *attr)
339 struct netem_sched_data *q = qdisc_priv(sch);
340 unsigned long n = RTA_PAYLOAD(attr)/sizeof(__s16);
341 const __s16 *data = RTA_DATA(attr);
348 d = kmalloc(sizeof(*d) + n*sizeof(d->table[0]), GFP_KERNEL);
353 for (i = 0; i < n; i++)
354 d->table[i] = data[i];
356 spin_lock_bh(&sch->dev->queue_lock);
357 d = xchg(&q->delay_dist, d);
358 spin_unlock_bh(&sch->dev->queue_lock);
364 static int get_correlation(struct Qdisc *sch, const struct rtattr *attr)
366 struct netem_sched_data *q = qdisc_priv(sch);
367 const struct tc_netem_corr *c = RTA_DATA(attr);
369 if (RTA_PAYLOAD(attr) != sizeof(*c))
372 init_crandom(&q->delay_cor, c->delay_corr);
373 init_crandom(&q->loss_cor, c->loss_corr);
374 init_crandom(&q->dup_cor, c->dup_corr);
378 static int get_reorder(struct Qdisc *sch, const struct rtattr *attr)
380 struct netem_sched_data *q = qdisc_priv(sch);
381 const struct tc_netem_reorder *r = RTA_DATA(attr);
383 if (RTA_PAYLOAD(attr) != sizeof(*r))
386 q->reorder = r->probability;
387 init_crandom(&q->reorder_cor, r->correlation);
391 static int get_corrupt(struct Qdisc *sch, const struct rtattr *attr)
393 struct netem_sched_data *q = qdisc_priv(sch);
394 const struct tc_netem_corrupt *r = RTA_DATA(attr);
396 if (RTA_PAYLOAD(attr) != sizeof(*r))
399 q->corrupt = r->probability;
400 init_crandom(&q->corrupt_cor, r->correlation);
404 /* Parse netlink message to set options */
405 static int netem_change(struct Qdisc *sch, struct rtattr *opt)
407 struct netem_sched_data *q = qdisc_priv(sch);
408 struct tc_netem_qopt *qopt;
411 if (opt == NULL || RTA_PAYLOAD(opt) < sizeof(*qopt))
414 qopt = RTA_DATA(opt);
415 ret = set_fifo_limit(q->qdisc, qopt->limit);
417 pr_debug("netem: can't set fifo limit\n");
421 q->latency = qopt->latency;
422 q->jitter = qopt->jitter;
423 q->limit = qopt->limit;
426 q->loss = qopt->loss;
427 q->duplicate = qopt->duplicate;
429 /* for compatiablity with earlier versions.
430 * if gap is set, need to assume 100% probablity
435 /* Handle nested options after initial queue options.
436 * Should have put all options in nested format but too late now.
438 if (RTA_PAYLOAD(opt) > sizeof(*qopt)) {
439 struct rtattr *tb[TCA_NETEM_MAX];
440 if (rtattr_parse(tb, TCA_NETEM_MAX,
441 RTA_DATA(opt) + sizeof(*qopt),
442 RTA_PAYLOAD(opt) - sizeof(*qopt)))
445 if (tb[TCA_NETEM_CORR-1]) {
446 ret = get_correlation(sch, tb[TCA_NETEM_CORR-1]);
451 if (tb[TCA_NETEM_DELAY_DIST-1]) {
452 ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST-1]);
457 if (tb[TCA_NETEM_REORDER-1]) {
458 ret = get_reorder(sch, tb[TCA_NETEM_REORDER-1]);
463 if (tb[TCA_NETEM_CORRUPT-1]) {
464 ret = get_corrupt(sch, tb[TCA_NETEM_CORRUPT-1]);
474 * Special case version of FIFO queue for use by netem.
475 * It queues in order based on timestamps in skb's
477 struct fifo_sched_data {
481 static int tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
483 struct fifo_sched_data *q = qdisc_priv(sch);
484 struct sk_buff_head *list = &sch->q;
485 const struct netem_skb_cb *ncb
486 = (const struct netem_skb_cb *)nskb->cb;
489 if (likely(skb_queue_len(list) < q->limit)) {
490 skb_queue_reverse_walk(list, skb) {
491 const struct netem_skb_cb *cb
492 = (const struct netem_skb_cb *)skb->cb;
494 if (!PSCHED_TLESS(ncb->time_to_send, cb->time_to_send))
498 __skb_queue_after(list, skb, nskb);
500 sch->qstats.backlog += nskb->len;
501 sch->bstats.bytes += nskb->len;
502 sch->bstats.packets++;
504 return NET_XMIT_SUCCESS;
507 return qdisc_drop(nskb, sch);
510 static int tfifo_init(struct Qdisc *sch, struct rtattr *opt)
512 struct fifo_sched_data *q = qdisc_priv(sch);
515 struct tc_fifo_qopt *ctl = RTA_DATA(opt);
516 if (RTA_PAYLOAD(opt) < sizeof(*ctl))
519 q->limit = ctl->limit;
521 q->limit = max_t(u32, sch->dev->tx_queue_len, 1);
526 static int tfifo_dump(struct Qdisc *sch, struct sk_buff *skb)
528 struct fifo_sched_data *q = qdisc_priv(sch);
529 struct tc_fifo_qopt opt = { .limit = q->limit };
531 RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
538 static struct Qdisc_ops tfifo_qdisc_ops = {
540 .priv_size = sizeof(struct fifo_sched_data),
541 .enqueue = tfifo_enqueue,
542 .dequeue = qdisc_dequeue_head,
543 .requeue = qdisc_requeue,
544 .drop = qdisc_queue_drop,
546 .reset = qdisc_reset_queue,
547 .change = tfifo_init,
551 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
553 struct netem_sched_data *q = qdisc_priv(sch);
559 qdisc_watchdog_init(&q->watchdog, sch);
561 q->qdisc = qdisc_create_dflt(sch->dev, &tfifo_qdisc_ops,
562 TC_H_MAKE(sch->handle, 1));
564 pr_debug("netem: qdisc create failed\n");
568 ret = netem_change(sch, opt);
570 pr_debug("netem: change failed\n");
571 qdisc_destroy(q->qdisc);
576 static void netem_destroy(struct Qdisc *sch)
578 struct netem_sched_data *q = qdisc_priv(sch);
580 qdisc_watchdog_cancel(&q->watchdog);
581 qdisc_destroy(q->qdisc);
582 kfree(q->delay_dist);
585 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
587 const struct netem_sched_data *q = qdisc_priv(sch);
588 unsigned char *b = skb_tail_pointer(skb);
589 struct rtattr *rta = (struct rtattr *) b;
590 struct tc_netem_qopt qopt;
591 struct tc_netem_corr cor;
592 struct tc_netem_reorder reorder;
593 struct tc_netem_corrupt corrupt;
595 qopt.latency = q->latency;
596 qopt.jitter = q->jitter;
597 qopt.limit = q->limit;
600 qopt.duplicate = q->duplicate;
601 RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
603 cor.delay_corr = q->delay_cor.rho;
604 cor.loss_corr = q->loss_cor.rho;
605 cor.dup_corr = q->dup_cor.rho;
606 RTA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor);
608 reorder.probability = q->reorder;
609 reorder.correlation = q->reorder_cor.rho;
610 RTA_PUT(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder);
612 corrupt.probability = q->corrupt;
613 corrupt.correlation = q->corrupt_cor.rho;
614 RTA_PUT(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt);
616 rta->rta_len = skb_tail_pointer(skb) - b;
625 static int netem_dump_class(struct Qdisc *sch, unsigned long cl,
626 struct sk_buff *skb, struct tcmsg *tcm)
628 struct netem_sched_data *q = qdisc_priv(sch);
630 if (cl != 1) /* only one class */
633 tcm->tcm_handle |= TC_H_MIN(1);
634 tcm->tcm_info = q->qdisc->handle;
639 static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
642 struct netem_sched_data *q = qdisc_priv(sch);
648 *old = xchg(&q->qdisc, new);
649 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
651 sch_tree_unlock(sch);
656 static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg)
658 struct netem_sched_data *q = qdisc_priv(sch);
662 static unsigned long netem_get(struct Qdisc *sch, u32 classid)
667 static void netem_put(struct Qdisc *sch, unsigned long arg)
671 static int netem_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
672 struct rtattr **tca, unsigned long *arg)
677 static int netem_delete(struct Qdisc *sch, unsigned long arg)
682 static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker)
685 if (walker->count >= walker->skip)
686 if (walker->fn(sch, 1, walker) < 0) {
694 static struct tcf_proto **netem_find_tcf(struct Qdisc *sch, unsigned long cl)
699 static struct Qdisc_class_ops netem_class_ops = {
700 .graft = netem_graft,
704 .change = netem_change_class,
705 .delete = netem_delete,
707 .tcf_chain = netem_find_tcf,
708 .dump = netem_dump_class,
711 static struct Qdisc_ops netem_qdisc_ops = {
713 .cl_ops = &netem_class_ops,
714 .priv_size = sizeof(struct netem_sched_data),
715 .enqueue = netem_enqueue,
716 .dequeue = netem_dequeue,
717 .requeue = netem_requeue,
720 .reset = netem_reset,
721 .destroy = netem_destroy,
722 .change = netem_change,
724 .owner = THIS_MODULE,
728 static int __init netem_module_init(void)
730 pr_info("netem: version " VERSION "\n");
731 return register_qdisc(&netem_qdisc_ops);
733 static void __exit netem_module_exit(void)
735 unregister_qdisc(&netem_qdisc_ops);
737 module_init(netem_module_init)
738 module_exit(netem_module_exit)
739 MODULE_LICENSE("GPL");