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
434 /* Handle nested options after initial queue options.
435 * Should have put all options in nested format but too late now.
437 if (RTA_PAYLOAD(opt) > sizeof(*qopt)) {
438 struct rtattr *tb[TCA_NETEM_MAX];
439 if (rtattr_parse(tb, TCA_NETEM_MAX,
440 RTA_DATA(opt) + sizeof(*qopt),
441 RTA_PAYLOAD(opt) - sizeof(*qopt)))
444 if (tb[TCA_NETEM_CORR-1]) {
445 ret = get_correlation(sch, tb[TCA_NETEM_CORR-1]);
450 if (tb[TCA_NETEM_DELAY_DIST-1]) {
451 ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST-1]);
456 if (tb[TCA_NETEM_REORDER-1]) {
457 ret = get_reorder(sch, tb[TCA_NETEM_REORDER-1]);
462 if (tb[TCA_NETEM_CORRUPT-1]) {
463 ret = get_corrupt(sch, tb[TCA_NETEM_CORRUPT-1]);
473 * Special case version of FIFO queue for use by netem.
474 * It queues in order based on timestamps in skb's
476 struct fifo_sched_data {
480 static int tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
482 struct fifo_sched_data *q = qdisc_priv(sch);
483 struct sk_buff_head *list = &sch->q;
484 const struct netem_skb_cb *ncb
485 = (const struct netem_skb_cb *)nskb->cb;
488 if (likely(skb_queue_len(list) < q->limit)) {
489 skb_queue_reverse_walk(list, skb) {
490 const struct netem_skb_cb *cb
491 = (const struct netem_skb_cb *)skb->cb;
493 if (!PSCHED_TLESS(ncb->time_to_send, cb->time_to_send))
497 __skb_queue_after(list, skb, nskb);
499 sch->qstats.backlog += nskb->len;
500 sch->bstats.bytes += nskb->len;
501 sch->bstats.packets++;
503 return NET_XMIT_SUCCESS;
506 return qdisc_drop(nskb, sch);
509 static int tfifo_init(struct Qdisc *sch, struct rtattr *opt)
511 struct fifo_sched_data *q = qdisc_priv(sch);
514 struct tc_fifo_qopt *ctl = RTA_DATA(opt);
515 if (RTA_PAYLOAD(opt) < sizeof(*ctl))
518 q->limit = ctl->limit;
520 q->limit = max_t(u32, sch->dev->tx_queue_len, 1);
525 static int tfifo_dump(struct Qdisc *sch, struct sk_buff *skb)
527 struct fifo_sched_data *q = qdisc_priv(sch);
528 struct tc_fifo_qopt opt = { .limit = q->limit };
530 RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
537 static struct Qdisc_ops tfifo_qdisc_ops = {
539 .priv_size = sizeof(struct fifo_sched_data),
540 .enqueue = tfifo_enqueue,
541 .dequeue = qdisc_dequeue_head,
542 .requeue = qdisc_requeue,
543 .drop = qdisc_queue_drop,
545 .reset = qdisc_reset_queue,
546 .change = tfifo_init,
550 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
552 struct netem_sched_data *q = qdisc_priv(sch);
558 qdisc_watchdog_init(&q->watchdog, sch);
560 q->qdisc = qdisc_create_dflt(sch->dev, &tfifo_qdisc_ops,
561 TC_H_MAKE(sch->handle, 1));
563 pr_debug("netem: qdisc create failed\n");
567 ret = netem_change(sch, opt);
569 pr_debug("netem: change failed\n");
570 qdisc_destroy(q->qdisc);
575 static void netem_destroy(struct Qdisc *sch)
577 struct netem_sched_data *q = qdisc_priv(sch);
579 qdisc_watchdog_cancel(&q->watchdog);
580 qdisc_destroy(q->qdisc);
581 kfree(q->delay_dist);
584 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
586 const struct netem_sched_data *q = qdisc_priv(sch);
587 unsigned char *b = skb_tail_pointer(skb);
588 struct rtattr *rta = (struct rtattr *) b;
589 struct tc_netem_qopt qopt;
590 struct tc_netem_corr cor;
591 struct tc_netem_reorder reorder;
592 struct tc_netem_corrupt corrupt;
594 qopt.latency = q->latency;
595 qopt.jitter = q->jitter;
596 qopt.limit = q->limit;
599 qopt.duplicate = q->duplicate;
600 RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
602 cor.delay_corr = q->delay_cor.rho;
603 cor.loss_corr = q->loss_cor.rho;
604 cor.dup_corr = q->dup_cor.rho;
605 RTA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor);
607 reorder.probability = q->reorder;
608 reorder.correlation = q->reorder_cor.rho;
609 RTA_PUT(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder);
611 corrupt.probability = q->corrupt;
612 corrupt.correlation = q->corrupt_cor.rho;
613 RTA_PUT(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt);
615 rta->rta_len = skb_tail_pointer(skb) - b;
624 static int netem_dump_class(struct Qdisc *sch, unsigned long cl,
625 struct sk_buff *skb, struct tcmsg *tcm)
627 struct netem_sched_data *q = qdisc_priv(sch);
629 if (cl != 1) /* only one class */
632 tcm->tcm_handle |= TC_H_MIN(1);
633 tcm->tcm_info = q->qdisc->handle;
638 static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
641 struct netem_sched_data *q = qdisc_priv(sch);
647 *old = xchg(&q->qdisc, new);
648 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
650 sch_tree_unlock(sch);
655 static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg)
657 struct netem_sched_data *q = qdisc_priv(sch);
661 static unsigned long netem_get(struct Qdisc *sch, u32 classid)
666 static void netem_put(struct Qdisc *sch, unsigned long arg)
670 static int netem_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
671 struct rtattr **tca, unsigned long *arg)
676 static int netem_delete(struct Qdisc *sch, unsigned long arg)
681 static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker)
684 if (walker->count >= walker->skip)
685 if (walker->fn(sch, 1, walker) < 0) {
693 static struct tcf_proto **netem_find_tcf(struct Qdisc *sch, unsigned long cl)
698 static struct Qdisc_class_ops netem_class_ops = {
699 .graft = netem_graft,
703 .change = netem_change_class,
704 .delete = netem_delete,
706 .tcf_chain = netem_find_tcf,
707 .dump = netem_dump_class,
710 static struct Qdisc_ops netem_qdisc_ops = {
712 .cl_ops = &netem_class_ops,
713 .priv_size = sizeof(struct netem_sched_data),
714 .enqueue = netem_enqueue,
715 .dequeue = netem_dequeue,
716 .requeue = netem_requeue,
719 .reset = netem_reset,
720 .destroy = netem_destroy,
721 .change = netem_change,
723 .owner = THIS_MODULE,
727 static int __init netem_module_init(void)
729 pr_info("netem: version " VERSION "\n");
730 return register_qdisc(&netem_qdisc_ops);
732 static void __exit netem_module_exit(void)
734 unregister_qdisc(&netem_qdisc_ops);
736 module_init(netem_module_init)
737 module_exit(netem_module_exit)
738 MODULE_LICENSE("GPL");