?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
initial commit with v2.6.32.60
[linux-2.6.32.60-moxart.git] / net / sched / sch_netem.c
blob0ae345a24888f5f403e6ebf97b8edc2443bc14a8
1 /*
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
7 * 2 of the License.
8 *
9 * Many of the algorithms and ideas for this came from
10 * NIST Net which is not copyrighted.
11 *
12 * Authors: Stephen Hemminger <shemminger@osdl.org>
13 * Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
14 */
15
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>
22
23 #include <net/netlink.h>
24 #include <net/pkt_sched.h>
25
26 #define VERSION "1.2"
27
28 /* Network Emulation Queuing algorithm.
29 ====================================
30
31 Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
32 Network Emulation Tool
33 [2] Luigi Rizzo, DummyNet for FreeBSD
34
35 ----------------------------------------------------------------
36
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.
44
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.
49 */
50
51 struct netem_sched_data {
52 struct Qdisc *qdisc;
53 struct qdisc_watchdog watchdog;
54
55 psched_tdiff_t latency;
56 psched_tdiff_t jitter;
57
58 u32 loss;
59 u32 limit;
60 u32 counter;
61 u32 gap;
62 u32 duplicate;
63 u32 reorder;
64 u32 corrupt;
65
66 struct crndstate {
67 u32 last;
68 u32 rho;
69 } delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor;
70
71 struct disttable {
72 u32 size;
73 s16 table[0];
74 } *delay_dist;
75 };
76
77 /* Time stamp put into socket buffer control block */
78 struct netem_skb_cb {
79 psched_time_t time_to_send;
80 };
81
82 static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb)
83 {
84 BUILD_BUG_ON(sizeof(skb->cb) <
85 sizeof(struct qdisc_skb_cb) + sizeof(struct netem_skb_cb));
86 return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data;
87 }
88
89 /* init_crandom - initialize correlated random number generator
90 * Use entropy source for initial seed.
91 */
92 static void init_crandom(struct crndstate *state, unsigned long rho)
93 {
94 state->rho = rho;
95 state->last = net_random();
96 }
97
98 /* get_crandom - correlated random number generator
99 * Next number depends on last value.
100 * rho is scaled to avoid floating point.
101 */
102 static u32 get_crandom(struct crndstate *state)
103 {
104 u64 value, rho;
105 unsigned long answer;
106
107 if (state->rho == 0) /* no correlation */
108 return net_random();
109
110 value = net_random();
111 rho = (u64)state->rho + 1;
112 answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
113 state->last = answer;
114 return answer;
115 }
116
117 /* tabledist - return a pseudo-randomly distributed value with mean mu and
118 * std deviation sigma. Uses table lookup to approximate the desired
119 * distribution, and a uniformly-distributed pseudo-random source.
120 */
121 static psched_tdiff_t tabledist(psched_tdiff_t mu, psched_tdiff_t sigma,
122 struct crndstate *state,
123 const struct disttable *dist)
124 {
125 psched_tdiff_t x;
126 long t;
127 u32 rnd;
128
129 if (sigma == 0)
130 return mu;
131
132 rnd = get_crandom(state);
133
134 /* default uniform distribution */
135 if (dist == NULL)
136 return (rnd % (2*sigma)) - sigma + mu;
137
138 t = dist->table[rnd % dist->size];
139 x = (sigma % NETEM_DIST_SCALE) * t;
140 if (x >= 0)
141 x += NETEM_DIST_SCALE/2;
142 else
143 x -= NETEM_DIST_SCALE/2;
144
145 return x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu;
146 }
147
148 /*
149 * Insert one skb into qdisc.
150 * Note: parent depends on return value to account for queue length.
151 * NET_XMIT_DROP: queue length didn't change.
152 * NET_XMIT_SUCCESS: one skb was queued.
153 */
154 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
155 {
156 struct netem_sched_data *q = qdisc_priv(sch);
157 /* We don't fill cb now as skb_unshare() may invalidate it */
158 struct netem_skb_cb *cb;
159 struct sk_buff *skb2;
160 int ret;
161 int count = 1;
162
163 pr_debug("netem_enqueue skb=%p\n", skb);
164
165 /* Random duplication */
166 if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
167 ++count;
168
169 /* Random packet drop 0 => none, ~0 => all */
170 if (q->loss && q->loss >= get_crandom(&q->loss_cor))
171 --count;
172
173 if (count == 0) {
174 sch->qstats.drops++;
175 kfree_skb(skb);
176 return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
177 }
178
179 skb_orphan(skb);
180
181 /*
182 * If we need to duplicate packet, then re-insert at top of the
183 * qdisc tree, since parent queuer expects that only one
184 * skb will be queued.
185 */
186 if (count > 1 && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) {
187 struct Qdisc *rootq = qdisc_root(sch);
188 u32 dupsave = q->duplicate; /* prevent duplicating a dup... */
189 q->duplicate = 0;
190
191 qdisc_enqueue_root(skb2, rootq);
192 q->duplicate = dupsave;
193 }
194
195 /*
196 * Randomized packet corruption.
197 * Make copy if needed since we are modifying
198 * If packet is going to be hardware checksummed, then
199 * do it now in software before we mangle it.
200 */
201 if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor)) {
202 if (!(skb = skb_unshare(skb, GFP_ATOMIC)) ||
203 (skb->ip_summed == CHECKSUM_PARTIAL &&
204 skb_checksum_help(skb)))
205 return qdisc_drop(skb, sch);
206
207 skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8);
208 }
209
210 cb = netem_skb_cb(skb);
211 if (q->gap == 0 /* not doing reordering */
212 || q->counter < q->gap /* inside last reordering gap */
213 || q->reorder < get_crandom(&q->reorder_cor)) {
214 psched_time_t now;
215 psched_tdiff_t delay;
216
217 delay = tabledist(q->latency, q->jitter,
218 &q->delay_cor, q->delay_dist);
219
220 now = psched_get_time();
221 cb->time_to_send = now + delay;
222 ++q->counter;
223 ret = qdisc_enqueue(skb, q->qdisc);
224 } else {
225 /*
226 * Do re-ordering by putting one out of N packets at the front
227 * of the queue.
228 */
229 cb->time_to_send = psched_get_time();
230 q->counter = 0;
231
232 __skb_queue_head(&q->qdisc->q, skb);
233 q->qdisc->qstats.backlog += qdisc_pkt_len(skb);
234 q->qdisc->qstats.requeues++;
235 ret = NET_XMIT_SUCCESS;
236 }
237
238 if (likely(ret == NET_XMIT_SUCCESS)) {
239 sch->q.qlen++;
240 sch->bstats.bytes += qdisc_pkt_len(skb);
241 sch->bstats.packets++;
242 } else if (net_xmit_drop_count(ret)) {
243 sch->qstats.drops++;
244 }
245
246 pr_debug("netem: enqueue ret %d\n", ret);
247 return ret;
248 }
249
250 static unsigned int netem_drop(struct Qdisc* sch)
251 {
252 struct netem_sched_data *q = qdisc_priv(sch);
253 unsigned int len = 0;
254
255 if (q->qdisc->ops->drop && (len = q->qdisc->ops->drop(q->qdisc)) != 0) {
256 sch->q.qlen--;
257 sch->qstats.drops++;
258 }
259 return len;
260 }
261
262 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
263 {
264 struct netem_sched_data *q = qdisc_priv(sch);
265 struct sk_buff *skb;
266
267 if (sch->flags & TCQ_F_THROTTLED)
268 return NULL;
269
270 skb = q->qdisc->ops->peek(q->qdisc);
271 if (skb) {
272 const struct netem_skb_cb *cb = netem_skb_cb(skb);
273 psched_time_t now = psched_get_time();
274
275 /* if more time remaining? */
276 if (cb->time_to_send <= now) {
277 skb = qdisc_dequeue_peeked(q->qdisc);
278 if (unlikely(!skb))
279 return NULL;
280
281 #ifdef CONFIG_NET_CLS_ACT
282 /*
283 * If it's at ingress let's pretend the delay is
284 * from the network (tstamp will be updated).
285 */
286 if (G_TC_FROM(skb->tc_verd) & AT_INGRESS)
287 skb->tstamp.tv64 = 0;
288 #endif
289 pr_debug("netem_dequeue: return skb=%p\n", skb);
290 sch->q.qlen--;
291 return skb;
292 }
293
294 qdisc_watchdog_schedule(&q->watchdog, cb->time_to_send);
295 }
296
297 return NULL;
298 }
299
300 static void netem_reset(struct Qdisc *sch)
301 {
302 struct netem_sched_data *q = qdisc_priv(sch);
303
304 qdisc_reset(q->qdisc);
305 sch->q.qlen = 0;
306 qdisc_watchdog_cancel(&q->watchdog);
307 }
308
309 /*
310 * Distribution data is a variable size payload containing
311 * signed 16 bit values.
312 */
313 static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr)
314 {
315 struct netem_sched_data *q = qdisc_priv(sch);
316 unsigned long n = nla_len(attr)/sizeof(__s16);
317 const __s16 *data = nla_data(attr);
318 spinlock_t *root_lock;
319 struct disttable *d;
320 int i;
321
322 if (n > 65536)
323 return -EINVAL;
324
325 d = kmalloc(sizeof(*d) + n*sizeof(d->table[0]), GFP_KERNEL);
326 if (!d)
327 return -ENOMEM;
328
329 d->size = n;
330 for (i = 0; i < n; i++)
331 d->table[i] = data[i];
332
333 root_lock = qdisc_root_sleeping_lock(sch);
334
335 spin_lock_bh(root_lock);
336 kfree(q->delay_dist);
337 q->delay_dist = d;
338 spin_unlock_bh(root_lock);
339 return 0;
340 }
341
342 static void get_correlation(struct Qdisc *sch, const struct nlattr *attr)
343 {
344 struct netem_sched_data *q = qdisc_priv(sch);
345 const struct tc_netem_corr *c = nla_data(attr);
346
347 init_crandom(&q->delay_cor, c->delay_corr);
348 init_crandom(&q->loss_cor, c->loss_corr);
349 init_crandom(&q->dup_cor, c->dup_corr);
350 }
351
352 static void get_reorder(struct Qdisc *sch, const struct nlattr *attr)
353 {
354 struct netem_sched_data *q = qdisc_priv(sch);
355 const struct tc_netem_reorder *r = nla_data(attr);
356
357 q->reorder = r->probability;
358 init_crandom(&q->reorder_cor, r->correlation);
359 }
360
361 static void get_corrupt(struct Qdisc *sch, const struct nlattr *attr)
362 {
363 struct netem_sched_data *q = qdisc_priv(sch);
364 const struct tc_netem_corrupt *r = nla_data(attr);
365
366 q->corrupt = r->probability;
367 init_crandom(&q->corrupt_cor, r->correlation);
368 }
369
370 static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = {
371 [TCA_NETEM_CORR] = { .len = sizeof(struct tc_netem_corr) },
372 [TCA_NETEM_REORDER] = { .len = sizeof(struct tc_netem_reorder) },
373 [TCA_NETEM_CORRUPT] = { .len = sizeof(struct tc_netem_corrupt) },
374 };
375
376 static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr *nla,
377 const struct nla_policy *policy, int len)
378 {
379 int nested_len = nla_len(nla) - NLA_ALIGN(len);
380
381 if (nested_len < 0)
382 return -EINVAL;
383 if (nested_len >= nla_attr_size(0))
384 return nla_parse(tb, maxtype, nla_data(nla) + NLA_ALIGN(len),
385 nested_len, policy);
386 memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1));
387 return 0;
388 }
389
390 /* Parse netlink message to set options */
391 static int netem_change(struct Qdisc *sch, struct nlattr *opt)
392 {
393 struct netem_sched_data *q = qdisc_priv(sch);
394 struct nlattr *tb[TCA_NETEM_MAX + 1];
395 struct tc_netem_qopt *qopt;
396 int ret;
397
398 if (opt == NULL)
399 return -EINVAL;
400
401 qopt = nla_data(opt);
402 ret = parse_attr(tb, TCA_NETEM_MAX, opt, netem_policy, sizeof(*qopt));
403 if (ret < 0)
404 return ret;
405
406 ret = fifo_set_limit(q->qdisc, qopt->limit);
407 if (ret) {
408 pr_debug("netem: can't set fifo limit\n");
409 return ret;
410 }
411
412 q->latency = qopt->latency;
413 q->jitter = qopt->jitter;
414 q->limit = qopt->limit;
415 q->gap = qopt->gap;
416 q->counter = 0;
417 q->loss = qopt->loss;
418 q->duplicate = qopt->duplicate;
419
420 /* for compatibility with earlier versions.
421 * if gap is set, need to assume 100% probability
422 */
423 if (q->gap)
424 q->reorder = ~0;
425
426 if (tb[TCA_NETEM_CORR])
427 get_correlation(sch, tb[TCA_NETEM_CORR]);
428
429 if (tb[TCA_NETEM_DELAY_DIST]) {
430 ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]);
431 if (ret)
432 return ret;
433 }
434
435 if (tb[TCA_NETEM_REORDER])
436 get_reorder(sch, tb[TCA_NETEM_REORDER]);
437
438 if (tb[TCA_NETEM_CORRUPT])
439 get_corrupt(sch, tb[TCA_NETEM_CORRUPT]);
440
441 return 0;
442 }
443
444 /*
445 * Special case version of FIFO queue for use by netem.
446 * It queues in order based on timestamps in skb's
447 */
448 struct fifo_sched_data {
449 u32 limit;
450 psched_time_t oldest;
451 };
452
453 static int tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
454 {
455 struct fifo_sched_data *q = qdisc_priv(sch);
456 struct sk_buff_head *list = &sch->q;
457 psched_time_t tnext = netem_skb_cb(nskb)->time_to_send;
458 struct sk_buff *skb;
459
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)) {
463 q->oldest = tnext;
464 return qdisc_enqueue_tail(nskb, sch);
465 }
466
467 skb_queue_reverse_walk(list, skb) {
468 const struct netem_skb_cb *cb = netem_skb_cb(skb);
469
470 if (tnext >= cb->time_to_send)
471 break;
472 }
473
474 __skb_queue_after(list, skb, nskb);
475
476 sch->qstats.backlog += qdisc_pkt_len(nskb);
477 sch->bstats.bytes += qdisc_pkt_len(nskb);
478 sch->bstats.packets++;
479
480 return NET_XMIT_SUCCESS;
481 }
482
483 return qdisc_reshape_fail(nskb, sch);
484 }
485
486 static int tfifo_init(struct Qdisc *sch, struct nlattr *opt)
487 {
488 struct fifo_sched_data *q = qdisc_priv(sch);
489
490 if (opt) {
491 struct tc_fifo_qopt *ctl = nla_data(opt);
492 if (nla_len(opt) < sizeof(*ctl))
493 return -EINVAL;
494
495 q->limit = ctl->limit;
496 } else
497 q->limit = max_t(u32, qdisc_dev(sch)->tx_queue_len, 1);
498
499 q->oldest = PSCHED_PASTPERFECT;
500 return 0;
501 }
502
503 static int tfifo_dump(struct Qdisc *sch, struct sk_buff *skb)
504 {
505 struct fifo_sched_data *q = qdisc_priv(sch);
506 struct tc_fifo_qopt opt = { .limit = q->limit };
507
508 NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
509 return skb->len;
510
511 nla_put_failure:
512 return -1;
513 }
514
515 static struct Qdisc_ops tfifo_qdisc_ops __read_mostly = {
516 .id = "tfifo",
517 .priv_size = sizeof(struct fifo_sched_data),
518 .enqueue = tfifo_enqueue,
519 .dequeue = qdisc_dequeue_head,
520 .peek = qdisc_peek_head,
521 .drop = qdisc_queue_drop,
522 .init = tfifo_init,
523 .reset = qdisc_reset_queue,
524 .change = tfifo_init,
525 .dump = tfifo_dump,
526 };
527
528 static int netem_init(struct Qdisc *sch, struct nlattr *opt)
529 {
530 struct netem_sched_data *q = qdisc_priv(sch);
531 int ret;
532
533 if (!opt)
534 return -EINVAL;
535
536 qdisc_watchdog_init(&q->watchdog, sch);
537
538 q->qdisc = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
539 &tfifo_qdisc_ops,
540 TC_H_MAKE(sch->handle, 1));
541 if (!q->qdisc) {
542 pr_debug("netem: qdisc create failed\n");
543 return -ENOMEM;
544 }
545
546 ret = netem_change(sch, opt);
547 if (ret) {
548 pr_debug("netem: change failed\n");
549 qdisc_destroy(q->qdisc);
550 }
551 return ret;
552 }
553
554 static void netem_destroy(struct Qdisc *sch)
555 {
556 struct netem_sched_data *q = qdisc_priv(sch);
557
558 qdisc_watchdog_cancel(&q->watchdog);
559 qdisc_destroy(q->qdisc);
560 kfree(q->delay_dist);
561 }
562
563 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
564 {
565 const struct netem_sched_data *q = qdisc_priv(sch);
566 unsigned char *b = skb_tail_pointer(skb);
567 struct nlattr *nla = (struct nlattr *) b;
568 struct tc_netem_qopt qopt;
569 struct tc_netem_corr cor;
570 struct tc_netem_reorder reorder;
571 struct tc_netem_corrupt corrupt;
572
573 qopt.latency = q->latency;
574 qopt.jitter = q->jitter;
575 qopt.limit = q->limit;
576 qopt.loss = q->loss;
577 qopt.gap = q->gap;
578 qopt.duplicate = q->duplicate;
579 NLA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
580
581 cor.delay_corr = q->delay_cor.rho;
582 cor.loss_corr = q->loss_cor.rho;
583 cor.dup_corr = q->dup_cor.rho;
584 NLA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor);
585
586 reorder.probability = q->reorder;
587 reorder.correlation = q->reorder_cor.rho;
588 NLA_PUT(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder);
589
590 corrupt.probability = q->corrupt;
591 corrupt.correlation = q->corrupt_cor.rho;
592 NLA_PUT(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt);
593
594 nla->nla_len = skb_tail_pointer(skb) - b;
595
596 return skb->len;
597
598 nla_put_failure:
599 nlmsg_trim(skb, b);
600 return -1;
601 }
602
603 static struct Qdisc_ops netem_qdisc_ops __read_mostly = {
604 .id = "netem",
605 .priv_size = sizeof(struct netem_sched_data),
606 .enqueue = netem_enqueue,
607 .dequeue = netem_dequeue,
608 .peek = qdisc_peek_dequeued,
609 .drop = netem_drop,
610 .init = netem_init,
611 .reset = netem_reset,
612 .destroy = netem_destroy,
613 .change = netem_change,
614 .dump = netem_dump,
615 .owner = THIS_MODULE,
616 };
617
618
619 static int __init netem_module_init(void)
620 {
621 pr_info("netem: version " VERSION "\n");
622 return register_qdisc(&netem_qdisc_ops);
623 }
624 static void __exit netem_module_exit(void)
625 {
626 unregister_qdisc(&netem_qdisc_ops);
627 }
628 module_init(netem_module_init)
629 module_exit(netem_module_exit)
630 MODULE_LICENSE("GPL");
Linux ARM platform port for MOXA ART SoC