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
7 * 2 of the License, or (at your option) any later 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/pkt_sched.h>
29 /* Network Emulation Queuing algorithm.
30 ====================================
32 Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
33 Network Emulation Tool
34 [2] Luigi Rizzo, DummyNet for FreeBSD
36 ----------------------------------------------------------------
38 This started out as a simple way to delay outgoing packets to
39 test TCP but has grown to include most of the functionality
40 of a full blown network emulator like NISTnet. It can delay
41 packets and add random jitter (and correlation). The random
42 distribution can be loaded from a table as well to provide
43 normal, Pareto, or experimental curves. Packet loss,
44 duplication, and reordering can also be emulated.
46 This qdisc does not do classification that can be handled in
47 layering other disciplines. It does not need to do bandwidth
48 control either since that can be handled by using token
49 bucket or other rate control.
51 The simulator is limited by the Linux timer resolution
52 and will create packet bursts on the HZ boundary (1ms).
55 struct netem_sched_data
{
57 struct timer_list timer
;
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 unsigned long get_crandom(struct crndstate
*state
)
101 unsigned long answer
;
103 if (state
->rho
== 0) /* no correllation */
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 long tabledist(unsigned long mu
, long sigma
,
118 struct crndstate
*state
, const struct disttable
*dist
)
126 rnd
= get_crandom(state
);
128 /* default uniform distribution */
130 return (rnd
% (2*sigma
)) - sigma
+ mu
;
132 t
= dist
->table
[rnd
% dist
->size
];
133 x
= (sigma
% NETEM_DIST_SCALE
) * t
;
135 x
+= NETEM_DIST_SCALE
/2;
137 x
-= NETEM_DIST_SCALE
/2;
139 return x
/ NETEM_DIST_SCALE
+ (sigma
/ NETEM_DIST_SCALE
) * t
+ mu
;
143 * Insert one skb into qdisc.
144 * Note: parent depends on return value to account for queue length.
145 * NET_XMIT_DROP: queue length didn't change.
146 * NET_XMIT_SUCCESS: one skb was queued.
148 static int netem_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
)
150 struct netem_sched_data
*q
= qdisc_priv(sch
);
151 /* We don't fill cb now as skb_unshare() may invalidate it */
152 struct netem_skb_cb
*cb
;
153 struct sk_buff
*skb2
;
157 pr_debug("netem_enqueue skb=%p\n", skb
);
159 /* Random duplication */
160 if (q
->duplicate
&& q
->duplicate
>= get_crandom(&q
->dup_cor
))
163 /* Random packet drop 0 => none, ~0 => all */
164 if (q
->loss
&& q
->loss
>= get_crandom(&q
->loss_cor
))
170 return NET_XMIT_BYPASS
;
174 * If we need to duplicate packet, then re-insert at top of the
175 * qdisc tree, since parent queuer expects that only one
176 * skb will be queued.
178 if (count
> 1 && (skb2
= skb_clone(skb
, GFP_ATOMIC
)) != NULL
) {
179 struct Qdisc
*rootq
= sch
->dev
->qdisc
;
180 u32 dupsave
= q
->duplicate
; /* prevent duplicating a dup... */
183 rootq
->enqueue(skb2
, rootq
);
184 q
->duplicate
= dupsave
;
188 * Randomized packet corruption.
189 * Make copy if needed since we are modifying
190 * If packet is going to be hardware checksummed, then
191 * do it now in software before we mangle it.
193 if (q
->corrupt
&& q
->corrupt
>= get_crandom(&q
->corrupt_cor
)) {
194 if (!(skb
= skb_unshare(skb
, GFP_ATOMIC
))
195 || (skb
->ip_summed
== CHECKSUM_PARTIAL
196 && skb_checksum_help(skb
))) {
198 return NET_XMIT_DROP
;
201 skb
->data
[net_random() % skb_headlen(skb
)] ^= 1<<(net_random() % 8);
204 cb
= (struct netem_skb_cb
*)skb
->cb
;
205 if (q
->gap
== 0 /* not doing reordering */
206 || q
->counter
< q
->gap
/* inside last reordering gap */
207 || q
->reorder
< get_crandom(&q
->reorder_cor
)) {
209 psched_tdiff_t delay
;
211 delay
= tabledist(q
->latency
, q
->jitter
,
212 &q
->delay_cor
, q
->delay_dist
);
214 PSCHED_GET_TIME(now
);
215 PSCHED_TADD2(now
, delay
, cb
->time_to_send
);
217 ret
= q
->qdisc
->enqueue(skb
, q
->qdisc
);
220 * Do re-ordering by putting one out of N packets at the front
223 PSCHED_GET_TIME(cb
->time_to_send
);
225 ret
= q
->qdisc
->ops
->requeue(skb
, q
->qdisc
);
228 if (likely(ret
== NET_XMIT_SUCCESS
)) {
230 sch
->bstats
.bytes
+= skb
->len
;
231 sch
->bstats
.packets
++;
235 pr_debug("netem: enqueue ret %d\n", ret
);
239 /* Requeue packets but don't change time stamp */
240 static int netem_requeue(struct sk_buff
*skb
, struct Qdisc
*sch
)
242 struct netem_sched_data
*q
= qdisc_priv(sch
);
245 if ((ret
= q
->qdisc
->ops
->requeue(skb
, q
->qdisc
)) == 0) {
247 sch
->qstats
.requeues
++;
253 static unsigned int netem_drop(struct Qdisc
* sch
)
255 struct netem_sched_data
*q
= qdisc_priv(sch
);
256 unsigned int len
= 0;
258 if (q
->qdisc
->ops
->drop
&& (len
= q
->qdisc
->ops
->drop(q
->qdisc
)) != 0) {
265 static struct sk_buff
*netem_dequeue(struct Qdisc
*sch
)
267 struct netem_sched_data
*q
= qdisc_priv(sch
);
270 skb
= q
->qdisc
->dequeue(q
->qdisc
);
272 const struct netem_skb_cb
*cb
273 = (const struct netem_skb_cb
*)skb
->cb
;
276 /* if more time remaining? */
277 PSCHED_GET_TIME(now
);
279 if (PSCHED_TLESS(cb
->time_to_send
, now
)) {
280 pr_debug("netem_dequeue: return skb=%p\n", skb
);
282 sch
->flags
&= ~TCQ_F_THROTTLED
;
285 psched_tdiff_t delay
= PSCHED_TDIFF(cb
->time_to_send
, now
);
287 if (q
->qdisc
->ops
->requeue(skb
, q
->qdisc
) != NET_XMIT_SUCCESS
) {
290 /* After this qlen is confused */
291 printk(KERN_ERR
"netem: queue discpline %s could not requeue\n",
297 mod_timer(&q
->timer
, jiffies
+ PSCHED_US2JIFFIE(delay
));
298 sch
->flags
|= TCQ_F_THROTTLED
;
305 static void netem_watchdog(unsigned long arg
)
307 struct Qdisc
*sch
= (struct Qdisc
*)arg
;
309 pr_debug("netem_watchdog qlen=%d\n", sch
->q
.qlen
);
310 sch
->flags
&= ~TCQ_F_THROTTLED
;
311 netif_schedule(sch
->dev
);
314 static void netem_reset(struct Qdisc
*sch
)
316 struct netem_sched_data
*q
= qdisc_priv(sch
);
318 qdisc_reset(q
->qdisc
);
320 sch
->flags
&= ~TCQ_F_THROTTLED
;
321 del_timer_sync(&q
->timer
);
324 /* Pass size change message down to embedded FIFO */
325 static int set_fifo_limit(struct Qdisc
*q
, int limit
)
330 /* Hack to avoid sending change message to non-FIFO */
331 if (strncmp(q
->ops
->id
+ 1, "fifo", 4) != 0)
334 rta
= kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt
)), GFP_KERNEL
);
336 rta
->rta_type
= RTM_NEWQDISC
;
337 rta
->rta_len
= RTA_LENGTH(sizeof(struct tc_fifo_qopt
));
338 ((struct tc_fifo_qopt
*)RTA_DATA(rta
))->limit
= limit
;
340 ret
= q
->ops
->change(q
, rta
);
347 * Distribution data is a variable size payload containing
348 * signed 16 bit values.
350 static int get_dist_table(struct Qdisc
*sch
, const struct rtattr
*attr
)
352 struct netem_sched_data
*q
= qdisc_priv(sch
);
353 unsigned long n
= RTA_PAYLOAD(attr
)/sizeof(__s16
);
354 const __s16
*data
= RTA_DATA(attr
);
361 d
= kmalloc(sizeof(*d
) + n
*sizeof(d
->table
[0]), GFP_KERNEL
);
366 for (i
= 0; i
< n
; i
++)
367 d
->table
[i
] = data
[i
];
369 spin_lock_bh(&sch
->dev
->queue_lock
);
370 d
= xchg(&q
->delay_dist
, d
);
371 spin_unlock_bh(&sch
->dev
->queue_lock
);
377 static int get_correlation(struct Qdisc
*sch
, const struct rtattr
*attr
)
379 struct netem_sched_data
*q
= qdisc_priv(sch
);
380 const struct tc_netem_corr
*c
= RTA_DATA(attr
);
382 if (RTA_PAYLOAD(attr
) != sizeof(*c
))
385 init_crandom(&q
->delay_cor
, c
->delay_corr
);
386 init_crandom(&q
->loss_cor
, c
->loss_corr
);
387 init_crandom(&q
->dup_cor
, c
->dup_corr
);
391 static int get_reorder(struct Qdisc
*sch
, const struct rtattr
*attr
)
393 struct netem_sched_data
*q
= qdisc_priv(sch
);
394 const struct tc_netem_reorder
*r
= RTA_DATA(attr
);
396 if (RTA_PAYLOAD(attr
) != sizeof(*r
))
399 q
->reorder
= r
->probability
;
400 init_crandom(&q
->reorder_cor
, r
->correlation
);
404 static int get_corrupt(struct Qdisc
*sch
, const struct rtattr
*attr
)
406 struct netem_sched_data
*q
= qdisc_priv(sch
);
407 const struct tc_netem_corrupt
*r
= RTA_DATA(attr
);
409 if (RTA_PAYLOAD(attr
) != sizeof(*r
))
412 q
->corrupt
= r
->probability
;
413 init_crandom(&q
->corrupt_cor
, r
->correlation
);
417 /* Parse netlink message to set options */
418 static int netem_change(struct Qdisc
*sch
, struct rtattr
*opt
)
420 struct netem_sched_data
*q
= qdisc_priv(sch
);
421 struct tc_netem_qopt
*qopt
;
424 if (opt
== NULL
|| RTA_PAYLOAD(opt
) < sizeof(*qopt
))
427 qopt
= RTA_DATA(opt
);
428 ret
= set_fifo_limit(q
->qdisc
, qopt
->limit
);
430 pr_debug("netem: can't set fifo limit\n");
434 q
->latency
= qopt
->latency
;
435 q
->jitter
= qopt
->jitter
;
436 q
->limit
= qopt
->limit
;
439 q
->loss
= qopt
->loss
;
440 q
->duplicate
= qopt
->duplicate
;
442 /* for compatiablity with earlier versions.
443 * if gap is set, need to assume 100% probablity
447 /* Handle nested options after initial queue options.
448 * Should have put all options in nested format but too late now.
450 if (RTA_PAYLOAD(opt
) > sizeof(*qopt
)) {
451 struct rtattr
*tb
[TCA_NETEM_MAX
];
452 if (rtattr_parse(tb
, TCA_NETEM_MAX
,
453 RTA_DATA(opt
) + sizeof(*qopt
),
454 RTA_PAYLOAD(opt
) - sizeof(*qopt
)))
457 if (tb
[TCA_NETEM_CORR
-1]) {
458 ret
= get_correlation(sch
, tb
[TCA_NETEM_CORR
-1]);
463 if (tb
[TCA_NETEM_DELAY_DIST
-1]) {
464 ret
= get_dist_table(sch
, tb
[TCA_NETEM_DELAY_DIST
-1]);
469 if (tb
[TCA_NETEM_REORDER
-1]) {
470 ret
= get_reorder(sch
, tb
[TCA_NETEM_REORDER
-1]);
475 if (tb
[TCA_NETEM_CORRUPT
-1]) {
476 ret
= get_corrupt(sch
, tb
[TCA_NETEM_CORRUPT
-1]);
486 * Special case version of FIFO queue for use by netem.
487 * It queues in order based on timestamps in skb's
489 struct fifo_sched_data
{
493 static int tfifo_enqueue(struct sk_buff
*nskb
, struct Qdisc
*sch
)
495 struct fifo_sched_data
*q
= qdisc_priv(sch
);
496 struct sk_buff_head
*list
= &sch
->q
;
497 const struct netem_skb_cb
*ncb
498 = (const struct netem_skb_cb
*)nskb
->cb
;
501 if (likely(skb_queue_len(list
) < q
->limit
)) {
502 skb_queue_reverse_walk(list
, skb
) {
503 const struct netem_skb_cb
*cb
504 = (const struct netem_skb_cb
*)skb
->cb
;
506 if (!PSCHED_TLESS(ncb
->time_to_send
, cb
->time_to_send
))
510 __skb_queue_after(list
, skb
, nskb
);
512 sch
->qstats
.backlog
+= nskb
->len
;
513 sch
->bstats
.bytes
+= nskb
->len
;
514 sch
->bstats
.packets
++;
516 return NET_XMIT_SUCCESS
;
519 return qdisc_drop(nskb
, sch
);
522 static int tfifo_init(struct Qdisc
*sch
, struct rtattr
*opt
)
524 struct fifo_sched_data
*q
= qdisc_priv(sch
);
527 struct tc_fifo_qopt
*ctl
= RTA_DATA(opt
);
528 if (RTA_PAYLOAD(opt
) < sizeof(*ctl
))
531 q
->limit
= ctl
->limit
;
533 q
->limit
= max_t(u32
, sch
->dev
->tx_queue_len
, 1);
538 static int tfifo_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
540 struct fifo_sched_data
*q
= qdisc_priv(sch
);
541 struct tc_fifo_qopt opt
= { .limit
= q
->limit
};
543 RTA_PUT(skb
, TCA_OPTIONS
, sizeof(opt
), &opt
);
550 static struct Qdisc_ops tfifo_qdisc_ops
= {
552 .priv_size
= sizeof(struct fifo_sched_data
),
553 .enqueue
= tfifo_enqueue
,
554 .dequeue
= qdisc_dequeue_head
,
555 .requeue
= qdisc_requeue
,
556 .drop
= qdisc_queue_drop
,
558 .reset
= qdisc_reset_queue
,
559 .change
= tfifo_init
,
563 static int netem_init(struct Qdisc
*sch
, struct rtattr
*opt
)
565 struct netem_sched_data
*q
= qdisc_priv(sch
);
571 init_timer(&q
->timer
);
572 q
->timer
.function
= netem_watchdog
;
573 q
->timer
.data
= (unsigned long) sch
;
575 q
->qdisc
= qdisc_create_dflt(sch
->dev
, &tfifo_qdisc_ops
);
577 pr_debug("netem: qdisc create failed\n");
581 ret
= netem_change(sch
, opt
);
583 pr_debug("netem: change failed\n");
584 qdisc_destroy(q
->qdisc
);
589 static void netem_destroy(struct Qdisc
*sch
)
591 struct netem_sched_data
*q
= qdisc_priv(sch
);
593 del_timer_sync(&q
->timer
);
594 qdisc_destroy(q
->qdisc
);
595 kfree(q
->delay_dist
);
598 static int netem_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
600 const struct netem_sched_data
*q
= qdisc_priv(sch
);
601 unsigned char *b
= skb
->tail
;
602 struct rtattr
*rta
= (struct rtattr
*) b
;
603 struct tc_netem_qopt qopt
;
604 struct tc_netem_corr cor
;
605 struct tc_netem_reorder reorder
;
606 struct tc_netem_corrupt corrupt
;
608 qopt
.latency
= q
->latency
;
609 qopt
.jitter
= q
->jitter
;
610 qopt
.limit
= q
->limit
;
613 qopt
.duplicate
= q
->duplicate
;
614 RTA_PUT(skb
, TCA_OPTIONS
, sizeof(qopt
), &qopt
);
616 cor
.delay_corr
= q
->delay_cor
.rho
;
617 cor
.loss_corr
= q
->loss_cor
.rho
;
618 cor
.dup_corr
= q
->dup_cor
.rho
;
619 RTA_PUT(skb
, TCA_NETEM_CORR
, sizeof(cor
), &cor
);
621 reorder
.probability
= q
->reorder
;
622 reorder
.correlation
= q
->reorder_cor
.rho
;
623 RTA_PUT(skb
, TCA_NETEM_REORDER
, sizeof(reorder
), &reorder
);
625 corrupt
.probability
= q
->corrupt
;
626 corrupt
.correlation
= q
->corrupt_cor
.rho
;
627 RTA_PUT(skb
, TCA_NETEM_CORRUPT
, sizeof(corrupt
), &corrupt
);
629 rta
->rta_len
= skb
->tail
- b
;
634 skb_trim(skb
, b
- skb
->data
);
638 static int netem_dump_class(struct Qdisc
*sch
, unsigned long cl
,
639 struct sk_buff
*skb
, struct tcmsg
*tcm
)
641 struct netem_sched_data
*q
= qdisc_priv(sch
);
643 if (cl
!= 1) /* only one class */
646 tcm
->tcm_handle
|= TC_H_MIN(1);
647 tcm
->tcm_info
= q
->qdisc
->handle
;
652 static int netem_graft(struct Qdisc
*sch
, unsigned long arg
, struct Qdisc
*new,
655 struct netem_sched_data
*q
= qdisc_priv(sch
);
661 *old
= xchg(&q
->qdisc
, new);
664 sch_tree_unlock(sch
);
669 static struct Qdisc
*netem_leaf(struct Qdisc
*sch
, unsigned long arg
)
671 struct netem_sched_data
*q
= qdisc_priv(sch
);
675 static unsigned long netem_get(struct Qdisc
*sch
, u32 classid
)
680 static void netem_put(struct Qdisc
*sch
, unsigned long arg
)
684 static int netem_change_class(struct Qdisc
*sch
, u32 classid
, u32 parentid
,
685 struct rtattr
**tca
, unsigned long *arg
)
690 static int netem_delete(struct Qdisc
*sch
, unsigned long arg
)
695 static void netem_walk(struct Qdisc
*sch
, struct qdisc_walker
*walker
)
698 if (walker
->count
>= walker
->skip
)
699 if (walker
->fn(sch
, 1, walker
) < 0) {
707 static struct tcf_proto
**netem_find_tcf(struct Qdisc
*sch
, unsigned long cl
)
712 static struct Qdisc_class_ops netem_class_ops
= {
713 .graft
= netem_graft
,
717 .change
= netem_change_class
,
718 .delete = netem_delete
,
720 .tcf_chain
= netem_find_tcf
,
721 .dump
= netem_dump_class
,
724 static struct Qdisc_ops netem_qdisc_ops
= {
726 .cl_ops
= &netem_class_ops
,
727 .priv_size
= sizeof(struct netem_sched_data
),
728 .enqueue
= netem_enqueue
,
729 .dequeue
= netem_dequeue
,
730 .requeue
= netem_requeue
,
733 .reset
= netem_reset
,
734 .destroy
= netem_destroy
,
735 .change
= netem_change
,
737 .owner
= THIS_MODULE
,
741 static int __init
netem_module_init(void)
743 pr_info("netem: version " VERSION
"\n");
744 return register_qdisc(&netem_qdisc_ops
);
746 static void __exit
netem_module_exit(void)
748 unregister_qdisc(&netem_qdisc_ops
);
750 module_init(netem_module_init
)
751 module_exit(netem_module_exit
)
752 MODULE_LICENSE("GPL");