blob: e5593c083a7883f99e548e182e90d8a2ae84bb65 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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
Stephen Hemminger798b6b12006-10-22 20:16:57 -07007 * 2 of the License.
Linus Torvalds1da177e2005-04-16 15:20:36 -07008 *
9 * Many of the algorithms and ideas for this came from
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090010 * NIST Net which is not copyrighted.
Linus Torvalds1da177e2005-04-16 15:20:36 -070011 *
12 * Authors: Stephen Hemminger <shemminger@osdl.org>
13 * Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
14 */
15
Linus Torvalds1da177e2005-04-16 15:20:36 -070016#include <linux/module.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090017#include <linux/slab.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include <linux/types.h>
19#include <linux/kernel.h>
20#include <linux/errno.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include <linux/skbuff.h>
22#include <linux/rtnetlink.h>
23
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -070024#include <net/netlink.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070025#include <net/pkt_sched.h>
26
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -080027#define VERSION "1.2"
Stephen Hemmingereb229c42005-11-03 13:49:01 -080028
Linus Torvalds1da177e2005-04-16 15:20:36 -070029/* Network Emulation Queuing algorithm.
30 ====================================
31
32 Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
33 Network Emulation Tool
34 [2] Luigi Rizzo, DummyNet for FreeBSD
35
36 ----------------------------------------------------------------
37
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.
45
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.
Linus Torvalds1da177e2005-04-16 15:20:36 -070050*/
51
52struct netem_sched_data {
53 struct Qdisc *qdisc;
Patrick McHardy59cb5c62007-03-16 01:20:31 -070054 struct qdisc_watchdog watchdog;
Linus Torvalds1da177e2005-04-16 15:20:36 -070055
Stephen Hemmingerb4076212007-03-22 12:16:21 -070056 psched_tdiff_t latency;
57 psched_tdiff_t jitter;
58
Linus Torvalds1da177e2005-04-16 15:20:36 -070059 u32 loss;
60 u32 limit;
61 u32 counter;
62 u32 gap;
Linus Torvalds1da177e2005-04-16 15:20:36 -070063 u32 duplicate;
Stephen Hemminger0dca51d2005-05-26 12:55:48 -070064 u32 reorder;
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -080065 u32 corrupt;
Linus Torvalds1da177e2005-04-16 15:20:36 -070066
67 struct crndstate {
Stephen Hemmingerb4076212007-03-22 12:16:21 -070068 u32 last;
69 u32 rho;
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -080070 } delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor;
Linus Torvalds1da177e2005-04-16 15:20:36 -070071
72 struct disttable {
73 u32 size;
74 s16 table[0];
75 } *delay_dist;
76};
77
78/* Time stamp put into socket buffer control block */
79struct netem_skb_cb {
80 psched_time_t time_to_send;
81};
82
Jussi Kivilinna5f861732008-07-20 00:08:04 -070083static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb)
84{
Jussi Kivilinna175f9c12008-07-20 00:08:47 -070085 BUILD_BUG_ON(sizeof(skb->cb) <
86 sizeof(struct qdisc_skb_cb) + sizeof(struct netem_skb_cb));
87 return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data;
Jussi Kivilinna5f861732008-07-20 00:08:04 -070088}
89
Linus Torvalds1da177e2005-04-16 15:20:36 -070090/* init_crandom - initialize correlated random number generator
91 * Use entropy source for initial seed.
92 */
93static void init_crandom(struct crndstate *state, unsigned long rho)
94{
95 state->rho = rho;
96 state->last = net_random();
97}
98
99/* get_crandom - correlated random number generator
100 * Next number depends on last value.
101 * rho is scaled to avoid floating point.
102 */
Stephen Hemmingerb4076212007-03-22 12:16:21 -0700103static u32 get_crandom(struct crndstate *state)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700104{
105 u64 value, rho;
106 unsigned long answer;
107
Stephen Hemmingerbb2f8cc2007-03-23 00:12:09 -0700108 if (state->rho == 0) /* no correlation */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 return net_random();
110
111 value = net_random();
112 rho = (u64)state->rho + 1;
113 answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
114 state->last = answer;
115 return answer;
116}
117
118/* tabledist - return a pseudo-randomly distributed value with mean mu and
119 * std deviation sigma. Uses table lookup to approximate the desired
120 * distribution, and a uniformly-distributed pseudo-random source.
121 */
Stephen Hemmingerb4076212007-03-22 12:16:21 -0700122static psched_tdiff_t tabledist(psched_tdiff_t mu, psched_tdiff_t sigma,
123 struct crndstate *state,
124 const struct disttable *dist)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125{
Stephen Hemmingerb4076212007-03-22 12:16:21 -0700126 psched_tdiff_t x;
127 long t;
128 u32 rnd;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129
130 if (sigma == 0)
131 return mu;
132
133 rnd = get_crandom(state);
134
135 /* default uniform distribution */
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900136 if (dist == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700137 return (rnd % (2*sigma)) - sigma + mu;
138
139 t = dist->table[rnd % dist->size];
140 x = (sigma % NETEM_DIST_SCALE) * t;
141 if (x >= 0)
142 x += NETEM_DIST_SCALE/2;
143 else
144 x -= NETEM_DIST_SCALE/2;
145
146 return x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu;
147}
148
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700149/*
150 * Insert one skb into qdisc.
151 * Note: parent depends on return value to account for queue length.
152 * NET_XMIT_DROP: queue length didn't change.
153 * NET_XMIT_SUCCESS: one skb was queued.
154 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
156{
157 struct netem_sched_data *q = qdisc_priv(sch);
Guillaume Chazarain89e1df72006-07-21 14:45:25 -0700158 /* We don't fill cb now as skb_unshare() may invalidate it */
159 struct netem_skb_cb *cb;
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700160 struct sk_buff *skb2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700161 int ret;
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700162 int count = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163
Stephen Hemminger771018e2005-05-03 16:24:32 -0700164 pr_debug("netem_enqueue skb=%p\n", skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700166 /* Random duplication */
167 if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
168 ++count;
169
Linus Torvalds1da177e2005-04-16 15:20:36 -0700170 /* Random packet drop 0 => none, ~0 => all */
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700171 if (q->loss && q->loss >= get_crandom(&q->loss_cor))
172 --count;
173
174 if (count == 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700175 sch->qstats.drops++;
176 kfree_skb(skb);
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700177 return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178 }
179
David S. Miller4e8a5202006-10-22 21:00:33 -0700180 skb_orphan(skb);
181
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700182 /*
183 * If we need to duplicate packet, then re-insert at top of the
184 * qdisc tree, since parent queuer expects that only one
185 * skb will be queued.
186 */
187 if (count > 1 && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) {
David S. Miller7698b4f2008-07-16 01:42:40 -0700188 struct Qdisc *rootq = qdisc_root(sch);
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700189 u32 dupsave = q->duplicate; /* prevent duplicating a dup... */
190 q->duplicate = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700192 qdisc_enqueue_root(skb2, rootq);
Stephen Hemminger0afb51e2005-05-26 12:53:49 -0700193 q->duplicate = dupsave;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700194 }
195
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800196 /*
197 * Randomized packet corruption.
198 * Make copy if needed since we are modifying
199 * If packet is going to be hardware checksummed, then
200 * do it now in software before we mangle it.
201 */
202 if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor)) {
Joe Perchesf64f9e72009-11-29 16:55:45 -0800203 if (!(skb = skb_unshare(skb, GFP_ATOMIC)) ||
204 (skb->ip_summed == CHECKSUM_PARTIAL &&
205 skb_checksum_help(skb))) {
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800206 sch->qstats.drops++;
207 return NET_XMIT_DROP;
208 }
209
210 skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8);
211 }
212
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700213 cb = netem_skb_cb(skb);
Joe Perchesf64f9e72009-11-29 16:55:45 -0800214 if (q->gap == 0 || /* not doing reordering */
215 q->counter < q->gap || /* inside last reordering gap */
216 q->reorder < get_crandom(&q->reorder_cor)) {
Stephen Hemminger0f9f32a2005-05-26 12:55:01 -0700217 psched_time_t now;
Stephen Hemminger07aaa112005-11-03 13:43:07 -0800218 psched_tdiff_t delay;
219
220 delay = tabledist(q->latency, q->jitter,
221 &q->delay_cor, q->delay_dist);
222
Patrick McHardy3bebcda2007-03-23 11:29:25 -0700223 now = psched_get_time();
Patrick McHardy7c59e252007-03-23 11:27:45 -0700224 cb->time_to_send = now + delay;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700225 ++q->counter;
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700226 ret = qdisc_enqueue(skb, q->qdisc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227 } else {
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900228 /*
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700229 * Do re-ordering by putting one out of N packets at the front
230 * of the queue.
231 */
Patrick McHardy3bebcda2007-03-23 11:29:25 -0700232 cb->time_to_send = psched_get_time();
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700233 q->counter = 0;
Jarek Poplawski8ba25da2008-11-02 00:36:03 -0700234
235 __skb_queue_head(&q->qdisc->q, skb);
236 q->qdisc->qstats.backlog += qdisc_pkt_len(skb);
237 q->qdisc->qstats.requeues++;
238 ret = NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700239 }
240
241 if (likely(ret == NET_XMIT_SUCCESS)) {
242 sch->q.qlen++;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700243 sch->bstats.bytes += qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700244 sch->bstats.packets++;
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700245 } else if (net_xmit_drop_count(ret)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700246 sch->qstats.drops++;
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700247 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248
Stephen Hemmingerd5d75cd2005-05-03 16:24:57 -0700249 pr_debug("netem: enqueue ret %d\n", ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700250 return ret;
251}
252
Linus Torvalds1da177e2005-04-16 15:20:36 -0700253static unsigned int netem_drop(struct Qdisc* sch)
254{
255 struct netem_sched_data *q = qdisc_priv(sch);
Patrick McHardy6d037a22006-03-20 19:00:49 -0800256 unsigned int len = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257
Patrick McHardy6d037a22006-03-20 19:00:49 -0800258 if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700259 sch->q.qlen--;
260 sch->qstats.drops++;
261 }
262 return len;
263}
264
Linus Torvalds1da177e2005-04-16 15:20:36 -0700265static struct sk_buff *netem_dequeue(struct Qdisc *sch)
266{
267 struct netem_sched_data *q = qdisc_priv(sch);
268 struct sk_buff *skb;
269
Stephen Hemminger11274e52007-03-22 12:17:42 -0700270 if (sch->flags & TCQ_F_THROTTLED)
271 return NULL;
272
Jarek Poplawski03c05f02008-10-31 00:46:19 -0700273 skb = q->qdisc->ops->peek(q->qdisc);
Stephen Hemminger771018e2005-05-03 16:24:32 -0700274 if (skb) {
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700275 const struct netem_skb_cb *cb = netem_skb_cb(skb);
Patrick McHardy3bebcda2007-03-23 11:29:25 -0700276 psched_time_t now = psched_get_time();
Stephen Hemminger771018e2005-05-03 16:24:32 -0700277
Stephen Hemminger0f9f32a2005-05-26 12:55:01 -0700278 /* if more time remaining? */
Patrick McHardy104e0872007-03-23 11:28:07 -0700279 if (cb->time_to_send <= now) {
Jarek Poplawski77be1552008-10-31 00:47:01 -0700280 skb = qdisc_dequeue_peeked(q->qdisc);
281 if (unlikely(!skb))
Jarek Poplawski03c05f02008-10-31 00:46:19 -0700282 return NULL;
283
Jarek Poplawski8caf1532009-04-17 10:08:49 +0000284#ifdef CONFIG_NET_CLS_ACT
285 /*
286 * If it's at ingress let's pretend the delay is
287 * from the network (tstamp will be updated).
288 */
289 if (G_TC_FROM(skb->tc_verd) & AT_INGRESS)
290 skb->tstamp.tv64 = 0;
291#endif
Stephen Hemminger0f9f32a2005-05-26 12:55:01 -0700292 pr_debug("netem_dequeue: return skb=%p\n", skb);
293 sch->q.qlen--;
Stephen Hemminger0f9f32a2005-05-26 12:55:01 -0700294 return skb;
295 }
Stephen Hemminger11274e52007-03-22 12:17:42 -0700296
Stephen Hemminger11274e52007-03-22 12:17:42 -0700297 qdisc_watchdog_schedule(&q->watchdog, cb->time_to_send);
Stephen Hemminger0f9f32a2005-05-26 12:55:01 -0700298 }
299
300 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301}
302
Linus Torvalds1da177e2005-04-16 15:20:36 -0700303static void netem_reset(struct Qdisc *sch)
304{
305 struct netem_sched_data *q = qdisc_priv(sch);
306
307 qdisc_reset(q->qdisc);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308 sch->q.qlen = 0;
Patrick McHardy59cb5c62007-03-16 01:20:31 -0700309 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700310}
311
Linus Torvalds1da177e2005-04-16 15:20:36 -0700312/*
313 * Distribution data is a variable size payload containing
314 * signed 16 bit values.
315 */
Patrick McHardy1e904742008-01-22 22:11:17 -0800316static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700317{
318 struct netem_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800319 unsigned long n = nla_len(attr)/sizeof(__s16);
320 const __s16 *data = nla_data(attr);
David S. Miller7698b4f2008-07-16 01:42:40 -0700321 spinlock_t *root_lock;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700322 struct disttable *d;
323 int i;
324
325 if (n > 65536)
326 return -EINVAL;
327
328 d = kmalloc(sizeof(*d) + n*sizeof(d->table[0]), GFP_KERNEL);
329 if (!d)
330 return -ENOMEM;
331
332 d->size = n;
333 for (i = 0; i < n; i++)
334 d->table[i] = data[i];
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900335
Jarek Poplawski102396a2008-08-29 14:21:52 -0700336 root_lock = qdisc_root_sleeping_lock(sch);
David S. Miller7698b4f2008-07-16 01:42:40 -0700337
338 spin_lock_bh(root_lock);
Patrick McHardyb94c8af2008-11-20 04:11:36 -0800339 kfree(q->delay_dist);
340 q->delay_dist = d;
David S. Miller7698b4f2008-07-16 01:42:40 -0700341 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700342 return 0;
343}
344
Stephen Hemminger265eb672008-11-03 21:13:26 -0800345static void get_correlation(struct Qdisc *sch, const struct nlattr *attr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700346{
347 struct netem_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800348 const struct tc_netem_corr *c = nla_data(attr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700349
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 init_crandom(&q->delay_cor, c->delay_corr);
351 init_crandom(&q->loss_cor, c->loss_corr);
352 init_crandom(&q->dup_cor, c->dup_corr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353}
354
Stephen Hemminger265eb672008-11-03 21:13:26 -0800355static void get_reorder(struct Qdisc *sch, const struct nlattr *attr)
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700356{
357 struct netem_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800358 const struct tc_netem_reorder *r = nla_data(attr);
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700359
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700360 q->reorder = r->probability;
361 init_crandom(&q->reorder_cor, r->correlation);
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700362}
363
Stephen Hemminger265eb672008-11-03 21:13:26 -0800364static void get_corrupt(struct Qdisc *sch, const struct nlattr *attr)
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800365{
366 struct netem_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800367 const struct tc_netem_corrupt *r = nla_data(attr);
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800368
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800369 q->corrupt = r->probability;
370 init_crandom(&q->corrupt_cor, r->correlation);
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800371}
372
Patrick McHardy27a34212008-01-23 20:35:39 -0800373static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = {
374 [TCA_NETEM_CORR] = { .len = sizeof(struct tc_netem_corr) },
375 [TCA_NETEM_REORDER] = { .len = sizeof(struct tc_netem_reorder) },
376 [TCA_NETEM_CORRUPT] = { .len = sizeof(struct tc_netem_corrupt) },
377};
378
Thomas Graf2c10b322008-09-02 17:30:27 -0700379static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr *nla,
380 const struct nla_policy *policy, int len)
381{
382 int nested_len = nla_len(nla) - NLA_ALIGN(len);
383
384 if (nested_len < 0)
385 return -EINVAL;
386 if (nested_len >= nla_attr_size(0))
387 return nla_parse(tb, maxtype, nla_data(nla) + NLA_ALIGN(len),
388 nested_len, policy);
389 memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1));
390 return 0;
391}
392
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800393/* Parse netlink message to set options */
Patrick McHardy1e904742008-01-22 22:11:17 -0800394static int netem_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700395{
396 struct netem_sched_data *q = qdisc_priv(sch);
Patrick McHardyb03f4672008-01-23 20:32:21 -0800397 struct nlattr *tb[TCA_NETEM_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398 struct tc_netem_qopt *qopt;
399 int ret;
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900400
Patrick McHardyb03f4672008-01-23 20:32:21 -0800401 if (opt == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402 return -EINVAL;
403
Thomas Graf2c10b322008-09-02 17:30:27 -0700404 qopt = nla_data(opt);
405 ret = parse_attr(tb, TCA_NETEM_MAX, opt, netem_policy, sizeof(*qopt));
Patrick McHardyb03f4672008-01-23 20:32:21 -0800406 if (ret < 0)
407 return ret;
408
Patrick McHardyfb0305c2008-07-05 23:40:21 -0700409 ret = fifo_set_limit(q->qdisc, qopt->limit);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700410 if (ret) {
411 pr_debug("netem: can't set fifo limit\n");
412 return ret;
413 }
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900414
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 q->latency = qopt->latency;
416 q->jitter = qopt->jitter;
417 q->limit = qopt->limit;
418 q->gap = qopt->gap;
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700419 q->counter = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700420 q->loss = qopt->loss;
421 q->duplicate = qopt->duplicate;
422
Stephen Hemmingerbb2f8cc2007-03-23 00:12:09 -0700423 /* for compatibility with earlier versions.
424 * if gap is set, need to assume 100% probability
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700425 */
Stephen Hemmingera362e0a2007-03-22 12:15:45 -0700426 if (q->gap)
427 q->reorder = ~0;
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700428
Stephen Hemminger265eb672008-11-03 21:13:26 -0800429 if (tb[TCA_NETEM_CORR])
430 get_correlation(sch, tb[TCA_NETEM_CORR]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431
Patrick McHardyb03f4672008-01-23 20:32:21 -0800432 if (tb[TCA_NETEM_DELAY_DIST]) {
433 ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]);
434 if (ret)
435 return ret;
436 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700437
Stephen Hemminger265eb672008-11-03 21:13:26 -0800438 if (tb[TCA_NETEM_REORDER])
439 get_reorder(sch, tb[TCA_NETEM_REORDER]);
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800440
Stephen Hemminger265eb672008-11-03 21:13:26 -0800441 if (tb[TCA_NETEM_CORRUPT])
442 get_corrupt(sch, tb[TCA_NETEM_CORRUPT]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443
444 return 0;
445}
446
Stephen Hemminger300ce172005-10-30 13:47:34 -0800447/*
448 * Special case version of FIFO queue for use by netem.
449 * It queues in order based on timestamps in skb's
450 */
451struct fifo_sched_data {
452 u32 limit;
Stephen Hemminger075aa572007-03-22 12:17:05 -0700453 psched_time_t oldest;
Stephen Hemminger300ce172005-10-30 13:47:34 -0800454};
455
456static int tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
457{
458 struct fifo_sched_data *q = qdisc_priv(sch);
459 struct sk_buff_head *list = &sch->q;
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700460 psched_time_t tnext = netem_skb_cb(nskb)->time_to_send;
Stephen Hemminger300ce172005-10-30 13:47:34 -0800461 struct sk_buff *skb;
462
463 if (likely(skb_queue_len(list) < q->limit)) {
Stephen Hemminger075aa572007-03-22 12:17:05 -0700464 /* Optimize for add at tail */
Patrick McHardy104e0872007-03-23 11:28:07 -0700465 if (likely(skb_queue_empty(list) || tnext >= q->oldest)) {
Stephen Hemminger075aa572007-03-22 12:17:05 -0700466 q->oldest = tnext;
467 return qdisc_enqueue_tail(nskb, sch);
468 }
469
Stephen Hemminger300ce172005-10-30 13:47:34 -0800470 skb_queue_reverse_walk(list, skb) {
Jussi Kivilinna5f861732008-07-20 00:08:04 -0700471 const struct netem_skb_cb *cb = netem_skb_cb(skb);
Stephen Hemminger300ce172005-10-30 13:47:34 -0800472
Patrick McHardy104e0872007-03-23 11:28:07 -0700473 if (tnext >= cb->time_to_send)
Stephen Hemminger300ce172005-10-30 13:47:34 -0800474 break;
475 }
476
477 __skb_queue_after(list, skb, nskb);
478
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700479 sch->qstats.backlog += qdisc_pkt_len(nskb);
480 sch->bstats.bytes += qdisc_pkt_len(nskb);
Stephen Hemminger300ce172005-10-30 13:47:34 -0800481 sch->bstats.packets++;
482
483 return NET_XMIT_SUCCESS;
484 }
485
Stephen Hemminger075aa572007-03-22 12:17:05 -0700486 return qdisc_reshape_fail(nskb, sch);
Stephen Hemminger300ce172005-10-30 13:47:34 -0800487}
488
Patrick McHardy1e904742008-01-22 22:11:17 -0800489static int tfifo_init(struct Qdisc *sch, struct nlattr *opt)
Stephen Hemminger300ce172005-10-30 13:47:34 -0800490{
491 struct fifo_sched_data *q = qdisc_priv(sch);
492
493 if (opt) {
Patrick McHardy1e904742008-01-22 22:11:17 -0800494 struct tc_fifo_qopt *ctl = nla_data(opt);
495 if (nla_len(opt) < sizeof(*ctl))
Stephen Hemminger300ce172005-10-30 13:47:34 -0800496 return -EINVAL;
497
498 q->limit = ctl->limit;
499 } else
David S. Miller5ce2d482008-07-08 17:06:30 -0700500 q->limit = max_t(u32, qdisc_dev(sch)->tx_queue_len, 1);
Stephen Hemminger300ce172005-10-30 13:47:34 -0800501
Patrick McHardya0849802007-03-23 11:28:30 -0700502 q->oldest = PSCHED_PASTPERFECT;
Stephen Hemminger300ce172005-10-30 13:47:34 -0800503 return 0;
504}
505
506static int tfifo_dump(struct Qdisc *sch, struct sk_buff *skb)
507{
508 struct fifo_sched_data *q = qdisc_priv(sch);
509 struct tc_fifo_qopt opt = { .limit = q->limit };
510
Patrick McHardy1e904742008-01-22 22:11:17 -0800511 NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
Stephen Hemminger300ce172005-10-30 13:47:34 -0800512 return skb->len;
513
Patrick McHardy1e904742008-01-22 22:11:17 -0800514nla_put_failure:
Stephen Hemminger300ce172005-10-30 13:47:34 -0800515 return -1;
516}
517
Eric Dumazet20fea082007-11-14 01:44:41 -0800518static struct Qdisc_ops tfifo_qdisc_ops __read_mostly = {
Stephen Hemminger300ce172005-10-30 13:47:34 -0800519 .id = "tfifo",
520 .priv_size = sizeof(struct fifo_sched_data),
521 .enqueue = tfifo_enqueue,
522 .dequeue = qdisc_dequeue_head,
Jarek Poplawski8e3af972008-10-31 00:45:55 -0700523 .peek = qdisc_peek_head,
Stephen Hemminger300ce172005-10-30 13:47:34 -0800524 .drop = qdisc_queue_drop,
525 .init = tfifo_init,
526 .reset = qdisc_reset_queue,
527 .change = tfifo_init,
528 .dump = tfifo_dump,
529};
530
Patrick McHardy1e904742008-01-22 22:11:17 -0800531static int netem_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532{
533 struct netem_sched_data *q = qdisc_priv(sch);
534 int ret;
535
536 if (!opt)
537 return -EINVAL;
538
Patrick McHardy59cb5c62007-03-16 01:20:31 -0700539 qdisc_watchdog_init(&q->watchdog, sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700540
Changli Gao3511c912010-10-16 13:04:08 +0000541 q->qdisc = qdisc_create_dflt(sch->dev_queue, &tfifo_qdisc_ops,
Patrick McHardy9f9afec2006-11-29 17:35:18 -0800542 TC_H_MAKE(sch->handle, 1));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700543 if (!q->qdisc) {
544 pr_debug("netem: qdisc create failed\n");
545 return -ENOMEM;
546 }
547
548 ret = netem_change(sch, opt);
549 if (ret) {
550 pr_debug("netem: change failed\n");
551 qdisc_destroy(q->qdisc);
552 }
553 return ret;
554}
555
556static void netem_destroy(struct Qdisc *sch)
557{
558 struct netem_sched_data *q = qdisc_priv(sch);
559
Patrick McHardy59cb5c62007-03-16 01:20:31 -0700560 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561 qdisc_destroy(q->qdisc);
562 kfree(q->delay_dist);
563}
564
565static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
566{
567 const struct netem_sched_data *q = qdisc_priv(sch);
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -0700568 unsigned char *b = skb_tail_pointer(skb);
Patrick McHardy1e904742008-01-22 22:11:17 -0800569 struct nlattr *nla = (struct nlattr *) b;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570 struct tc_netem_qopt qopt;
571 struct tc_netem_corr cor;
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700572 struct tc_netem_reorder reorder;
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800573 struct tc_netem_corrupt corrupt;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574
575 qopt.latency = q->latency;
576 qopt.jitter = q->jitter;
577 qopt.limit = q->limit;
578 qopt.loss = q->loss;
579 qopt.gap = q->gap;
580 qopt.duplicate = q->duplicate;
Patrick McHardy1e904742008-01-22 22:11:17 -0800581 NLA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700582
583 cor.delay_corr = q->delay_cor.rho;
584 cor.loss_corr = q->loss_cor.rho;
585 cor.dup_corr = q->dup_cor.rho;
Patrick McHardy1e904742008-01-22 22:11:17 -0800586 NLA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor);
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700587
588 reorder.probability = q->reorder;
589 reorder.correlation = q->reorder_cor.rho;
Patrick McHardy1e904742008-01-22 22:11:17 -0800590 NLA_PUT(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder);
Stephen Hemminger0dca51d2005-05-26 12:55:48 -0700591
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800592 corrupt.probability = q->corrupt;
593 corrupt.correlation = q->corrupt_cor.rho;
Patrick McHardy1e904742008-01-22 22:11:17 -0800594 NLA_PUT(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt);
Stephen Hemmingerc865e5d2005-12-21 19:03:44 -0800595
Patrick McHardy1e904742008-01-22 22:11:17 -0800596 nla->nla_len = skb_tail_pointer(skb) - b;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597
598 return skb->len;
599
Patrick McHardy1e904742008-01-22 22:11:17 -0800600nla_put_failure:
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -0700601 nlmsg_trim(skb, b);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700602 return -1;
603}
604
Eric Dumazet20fea082007-11-14 01:44:41 -0800605static struct Qdisc_ops netem_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700606 .id = "netem",
Linus Torvalds1da177e2005-04-16 15:20:36 -0700607 .priv_size = sizeof(struct netem_sched_data),
608 .enqueue = netem_enqueue,
609 .dequeue = netem_dequeue,
Jarek Poplawski77be1552008-10-31 00:47:01 -0700610 .peek = qdisc_peek_dequeued,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700611 .drop = netem_drop,
612 .init = netem_init,
613 .reset = netem_reset,
614 .destroy = netem_destroy,
615 .change = netem_change,
616 .dump = netem_dump,
617 .owner = THIS_MODULE,
618};
619
620
621static int __init netem_module_init(void)
622{
Stephen Hemmingereb229c42005-11-03 13:49:01 -0800623 pr_info("netem: version " VERSION "\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700624 return register_qdisc(&netem_qdisc_ops);
625}
626static void __exit netem_module_exit(void)
627{
628 unregister_qdisc(&netem_qdisc_ops);
629}
630module_init(netem_module_init)
631module_exit(netem_module_exit)
632MODULE_LICENSE("GPL");