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/types.h>
18 #include <linux/kernel.h>
19 #include <linux/errno.h>
20 #include <linux/skbuff.h>
21 #include <linux/rtnetlink.h>
23 #include <net/netlink.h>
24 #include <net/pkt_sched.h>
28 /* Network Emulation Queuing algorithm.
29 ====================================
31 Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
32 Network Emulation Tool
33 [2] Luigi Rizzo, DummyNet for FreeBSD
35 ----------------------------------------------------------------
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.
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.
50 The simulator is limited by the Linux timer resolution
51 and will create packet bursts on the HZ boundary (1ms).
54 struct netem_sched_data {
56 struct qdisc_watchdog watchdog;
58 psched_tdiff_t latency;
59 psched_tdiff_t jitter;
72 } delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor;
80 /* Time stamp put into socket buffer control block */
82 psched_time_t time_to_send;
85 /* init_crandom - initialize correlated random number generator
86 * Use entropy source for initial seed.
88 static void init_crandom(struct crndstate *state, unsigned long rho)
91 state->last = net_random();
94 /* get_crandom - correlated random number generator
95 * Next number depends on last value.
96 * rho is scaled to avoid floating point.
98 static u32 get_crandom(struct crndstate *state)
101 unsigned long answer;
103 if (state->rho == 0) /* no correlation */
106 value = net_random();
107 rho = (u64)state->rho + 1;
108 answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
109 state->last = answer;
113 /* tabledist - return a pseudo-randomly distributed value with mean mu and
114 * std deviation sigma. Uses table lookup to approximate the desired
115 * distribution, and a uniformly-distributed pseudo-random source.
117 static psched_tdiff_t tabledist(psched_tdiff_t mu, psched_tdiff_t sigma,
118 struct crndstate *state,
119 const struct disttable *dist)
128 rnd = get_crandom(state);
130 /* default uniform distribution */
132 return (rnd % (2*sigma)) - sigma + mu;
134 t = dist->table[rnd % dist->size];
135 x = (sigma % NETEM_DIST_SCALE) * t;
137 x += NETEM_DIST_SCALE/2;
139 x -= NETEM_DIST_SCALE/2;
141 return x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu;
145 * Insert one skb into qdisc.
146 * Note: parent depends on return value to account for queue length.
147 * NET_XMIT_DROP: queue length didn't change.
148 * NET_XMIT_SUCCESS: one skb was queued.
150 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
152 struct netem_sched_data *q = qdisc_priv(sch);
153 /* We don't fill cb now as skb_unshare() may invalidate it */
154 struct netem_skb_cb *cb;
155 struct sk_buff *skb2;
159 pr_debug("netem_enqueue skb=%p\n", skb);
161 /* Random duplication */
162 if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
165 /* Random packet drop 0 => none, ~0 => all */
166 if (q->loss && q->loss >= get_crandom(&q->loss_cor))
172 return NET_XMIT_BYPASS;
178 * If we need to duplicate packet, then re-insert at top of the
179 * qdisc tree, since parent queuer expects that only one
180 * skb will be queued.
182 if (count > 1 && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) {
183 struct Qdisc *rootq = qdisc_dev(sch)->qdisc;
184 u32 dupsave = q->duplicate; /* prevent duplicating a dup... */
187 rootq->enqueue(skb2, rootq);
188 q->duplicate = dupsave;
192 * Randomized packet corruption.
193 * Make copy if needed since we are modifying
194 * If packet is going to be hardware checksummed, then
195 * do it now in software before we mangle it.
197 if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor)) {
198 if (!(skb = skb_unshare(skb, GFP_ATOMIC))
199 || (skb->ip_summed == CHECKSUM_PARTIAL
200 && skb_checksum_help(skb))) {
202 return NET_XMIT_DROP;
205 skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8);
208 cb = (struct netem_skb_cb *)skb->cb;
209 if (q->gap == 0 /* not doing reordering */
210 || q->counter < q->gap /* inside last reordering gap */
211 || q->reorder < get_crandom(&q->reorder_cor)) {
213 psched_tdiff_t delay;
215 delay = tabledist(q->latency, q->jitter,
216 &q->delay_cor, q->delay_dist);
218 now = psched_get_time();
219 cb->time_to_send = now + delay;
221 ret = q->qdisc->enqueue(skb, q->qdisc);
224 * Do re-ordering by putting one out of N packets at the front
227 cb->time_to_send = psched_get_time();
229 ret = q->qdisc->ops->requeue(skb, q->qdisc);
232 if (likely(ret == NET_XMIT_SUCCESS)) {
234 sch->bstats.bytes += skb->len;
235 sch->bstats.packets++;
239 pr_debug("netem: enqueue ret %d\n", ret);
243 /* Requeue packets but don't change time stamp */
244 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
246 struct netem_sched_data *q = qdisc_priv(sch);
249 if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0) {
251 sch->qstats.requeues++;
257 static unsigned int netem_drop(struct Qdisc* sch)
259 struct netem_sched_data *q = qdisc_priv(sch);
260 unsigned int len = 0;
262 if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
269 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
271 struct netem_sched_data *q = qdisc_priv(sch);
275 if (sch->flags & TCQ_F_THROTTLED)
278 skb = q->qdisc->dequeue(q->qdisc);
280 const struct netem_skb_cb *cb
281 = (const struct netem_skb_cb *)skb->cb;
282 psched_time_t now = psched_get_time();
284 /* if more time remaining? */
285 if (cb->time_to_send <= now) {
286 pr_debug("netem_dequeue: return skb=%p\n", skb);
291 if (unlikely(q->qdisc->ops->requeue(skb, q->qdisc) != NET_XMIT_SUCCESS)) {
292 qdisc_tree_decrease_qlen(q->qdisc, 1);
294 printk(KERN_ERR "netem: %s could not requeue\n",
298 qdisc_watchdog_schedule(&q->watchdog, cb->time_to_send);
304 static void netem_reset(struct Qdisc *sch)
306 struct netem_sched_data *q = qdisc_priv(sch);
308 qdisc_reset(q->qdisc);
310 qdisc_watchdog_cancel(&q->watchdog);
314 * Distribution data is a variable size payload containing
315 * signed 16 bit values.
317 static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr)
319 struct netem_sched_data *q = qdisc_priv(sch);
320 unsigned long n = nla_len(attr)/sizeof(__s16);
321 const __s16 *data = nla_data(attr);
328 d = kmalloc(sizeof(*d) + n*sizeof(d->table[0]), GFP_KERNEL);
333 for (i = 0; i < n; i++)
334 d->table[i] = data[i];
336 spin_lock_bh(&qdisc_dev(sch)->queue_lock);
337 d = xchg(&q->delay_dist, d);
338 spin_unlock_bh(&qdisc_dev(sch)->queue_lock);
344 static int get_correlation(struct Qdisc *sch, const struct nlattr *attr)
346 struct netem_sched_data *q = qdisc_priv(sch);
347 const struct tc_netem_corr *c = nla_data(attr);
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);
355 static int get_reorder(struct Qdisc *sch, const struct nlattr *attr)
357 struct netem_sched_data *q = qdisc_priv(sch);
358 const struct tc_netem_reorder *r = nla_data(attr);
360 q->reorder = r->probability;
361 init_crandom(&q->reorder_cor, r->correlation);
365 static int get_corrupt(struct Qdisc *sch, const struct nlattr *attr)
367 struct netem_sched_data *q = qdisc_priv(sch);
368 const struct tc_netem_corrupt *r = nla_data(attr);
370 q->corrupt = r->probability;
371 init_crandom(&q->corrupt_cor, r->correlation);
375 static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = {
376 [TCA_NETEM_CORR] = { .len = sizeof(struct tc_netem_corr) },
377 [TCA_NETEM_REORDER] = { .len = sizeof(struct tc_netem_reorder) },
378 [TCA_NETEM_CORRUPT] = { .len = sizeof(struct tc_netem_corrupt) },
381 /* Parse netlink message to set options */
382 static int netem_change(struct Qdisc *sch, struct nlattr *opt)
384 struct netem_sched_data *q = qdisc_priv(sch);
385 struct nlattr *tb[TCA_NETEM_MAX + 1];
386 struct tc_netem_qopt *qopt;
392 ret = nla_parse_nested_compat(tb, TCA_NETEM_MAX, opt, netem_policy,
393 qopt, sizeof(*qopt));
397 ret = fifo_set_limit(q->qdisc, qopt->limit);
399 pr_debug("netem: can't set fifo limit\n");
403 q->latency = qopt->latency;
404 q->jitter = qopt->jitter;
405 q->limit = qopt->limit;
408 q->loss = qopt->loss;
409 q->duplicate = qopt->duplicate;
411 /* for compatibility with earlier versions.
412 * if gap is set, need to assume 100% probability
417 if (tb[TCA_NETEM_CORR]) {
418 ret = get_correlation(sch, tb[TCA_NETEM_CORR]);
423 if (tb[TCA_NETEM_DELAY_DIST]) {
424 ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]);
429 if (tb[TCA_NETEM_REORDER]) {
430 ret = get_reorder(sch, tb[TCA_NETEM_REORDER]);
435 if (tb[TCA_NETEM_CORRUPT]) {
436 ret = get_corrupt(sch, tb[TCA_NETEM_CORRUPT]);
445 * Special case version of FIFO queue for use by netem.
446 * It queues in order based on timestamps in skb's
448 struct fifo_sched_data {
450 psched_time_t oldest;
453 static int tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
455 struct fifo_sched_data *q = qdisc_priv(sch);
456 struct sk_buff_head *list = &sch->q;
457 psched_time_t tnext = ((struct netem_skb_cb *)nskb->cb)->time_to_send;
460 if (likely(skb_queue_len(list) < q->limit)) {
461 /* Optimize for add at tail */
462 if (likely(skb_queue_empty(list) || tnext >= q->oldest)) {
464 return qdisc_enqueue_tail(nskb, sch);
467 skb_queue_reverse_walk(list, skb) {
468 const struct netem_skb_cb *cb
469 = (const struct netem_skb_cb *)skb->cb;
471 if (tnext >= cb->time_to_send)
475 __skb_queue_after(list, skb, nskb);
477 sch->qstats.backlog += nskb->len;
478 sch->bstats.bytes += nskb->len;
479 sch->bstats.packets++;
481 return NET_XMIT_SUCCESS;
484 return qdisc_reshape_fail(nskb, sch);
487 static int tfifo_init(struct Qdisc *sch, struct nlattr *opt)
489 struct fifo_sched_data *q = qdisc_priv(sch);
492 struct tc_fifo_qopt *ctl = nla_data(opt);
493 if (nla_len(opt) < sizeof(*ctl))
496 q->limit = ctl->limit;
498 q->limit = max_t(u32, qdisc_dev(sch)->tx_queue_len, 1);
500 q->oldest = PSCHED_PASTPERFECT;
504 static int tfifo_dump(struct Qdisc *sch, struct sk_buff *skb)
506 struct fifo_sched_data *q = qdisc_priv(sch);
507 struct tc_fifo_qopt opt = { .limit = q->limit };
509 NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
516 static struct Qdisc_ops tfifo_qdisc_ops __read_mostly = {
518 .priv_size = sizeof(struct fifo_sched_data),
519 .enqueue = tfifo_enqueue,
520 .dequeue = qdisc_dequeue_head,
521 .requeue = qdisc_requeue,
522 .drop = qdisc_queue_drop,
524 .reset = qdisc_reset_queue,
525 .change = tfifo_init,
529 static int netem_init(struct Qdisc *sch, struct nlattr *opt)
531 struct netem_sched_data *q = qdisc_priv(sch);
537 qdisc_watchdog_init(&q->watchdog, sch);
539 q->qdisc = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
541 TC_H_MAKE(sch->handle, 1));
543 pr_debug("netem: qdisc create failed\n");
547 ret = netem_change(sch, opt);
549 pr_debug("netem: change failed\n");
550 qdisc_destroy(q->qdisc);
555 static void netem_destroy(struct Qdisc *sch)
557 struct netem_sched_data *q = qdisc_priv(sch);
559 qdisc_watchdog_cancel(&q->watchdog);
560 qdisc_destroy(q->qdisc);
561 kfree(q->delay_dist);
564 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
566 const struct netem_sched_data *q = qdisc_priv(sch);
567 unsigned char *b = skb_tail_pointer(skb);
568 struct nlattr *nla = (struct nlattr *) b;
569 struct tc_netem_qopt qopt;
570 struct tc_netem_corr cor;
571 struct tc_netem_reorder reorder;
572 struct tc_netem_corrupt corrupt;
574 qopt.latency = q->latency;
575 qopt.jitter = q->jitter;
576 qopt.limit = q->limit;
579 qopt.duplicate = q->duplicate;
580 NLA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
582 cor.delay_corr = q->delay_cor.rho;
583 cor.loss_corr = q->loss_cor.rho;
584 cor.dup_corr = q->dup_cor.rho;
585 NLA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor);
587 reorder.probability = q->reorder;
588 reorder.correlation = q->reorder_cor.rho;
589 NLA_PUT(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder);
591 corrupt.probability = q->corrupt;
592 corrupt.correlation = q->corrupt_cor.rho;
593 NLA_PUT(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt);
595 nla->nla_len = skb_tail_pointer(skb) - b;
604 static int netem_dump_class(struct Qdisc *sch, unsigned long cl,
605 struct sk_buff *skb, struct tcmsg *tcm)
607 struct netem_sched_data *q = qdisc_priv(sch);
609 if (cl != 1) /* only one class */
612 tcm->tcm_handle |= TC_H_MIN(1);
613 tcm->tcm_info = q->qdisc->handle;
618 static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
621 struct netem_sched_data *q = qdisc_priv(sch);
627 *old = xchg(&q->qdisc, new);
628 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
630 sch_tree_unlock(sch);
635 static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg)
637 struct netem_sched_data *q = qdisc_priv(sch);
641 static unsigned long netem_get(struct Qdisc *sch, u32 classid)
646 static void netem_put(struct Qdisc *sch, unsigned long arg)
650 static int netem_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
651 struct nlattr **tca, unsigned long *arg)
656 static int netem_delete(struct Qdisc *sch, unsigned long arg)
661 static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker)
664 if (walker->count >= walker->skip)
665 if (walker->fn(sch, 1, walker) < 0) {
673 static struct tcf_proto **netem_find_tcf(struct Qdisc *sch, unsigned long cl)
678 static const struct Qdisc_class_ops netem_class_ops = {
679 .graft = netem_graft,
683 .change = netem_change_class,
684 .delete = netem_delete,
686 .tcf_chain = netem_find_tcf,
687 .dump = netem_dump_class,
690 static struct Qdisc_ops netem_qdisc_ops __read_mostly = {
692 .cl_ops = &netem_class_ops,
693 .priv_size = sizeof(struct netem_sched_data),
694 .enqueue = netem_enqueue,
695 .dequeue = netem_dequeue,
696 .requeue = netem_requeue,
699 .reset = netem_reset,
700 .destroy = netem_destroy,
701 .change = netem_change,
703 .owner = THIS_MODULE,
707 static int __init netem_module_init(void)
709 pr_info("netem: version " VERSION "\n");
710 return register_qdisc(&netem_qdisc_ops);
712 static void __exit netem_module_exit(void)
714 unregister_qdisc(&netem_qdisc_ops);
716 module_init(netem_module_init)
717 module_exit(netem_module_exit)
718 MODULE_LICENSE("GPL");