* [PATCH 2.6] (1/4) netem - update API for new features
@ 2004-08-25 17:53 Stephen Hemminger
2004-08-25 17:57 ` [PATCH 2.6] (2/4) netem - comment update Stephen Hemminger
` (6 more replies)
0 siblings, 7 replies; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-25 17:53 UTC (permalink / raw)
To: David S. Miller; +Cc: netdev
Extend netem options to support new features.
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
diff -Nru a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
--- a/include/linux/pkt_sched.h 2004-08-24 14:43:33 -07:00
+++ b/include/linux/pkt_sched.h 2004-08-24 14:43:33 -07:00
@@ -401,7 +401,8 @@
#define TCA_ATM_MAX TCA_ATM_STATE
-/* Network emulator */
+/* Network section */
+
struct tc_netem_qopt
{
__u32 latency; /* added delay (us) */
@@ -409,6 +410,13 @@
__u32 loss; /* random packet loss (0=none ~0=100%) */
__u32 gap; /* re-ordering gap (0 for delay all) */
__u32 duplicate; /* random packet dup (0=none ~0=100%) */
- __u32 jitter; /* random jitter in latency (us) */
+ __u32 jitter; /* delay sigma (us) */
+
+ __u32 delay_corr; /* delay correllation (0=none ~0=100%) */
+ __u32 loss_corr; /* packet loss correllation (0=none ~0=100%) */
+ __u32 dup_corr; /* duplicate correlation (0=none ~0=100%) */
+
+ __s16 delay_dist[0]; /* delay distribution table (optional) */
+#define TCA_NETEM_TABLEFACTOR 8192
};
#endif
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2.6] (2/4) netem - comment update
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
@ 2004-08-25 17:57 ` Stephen Hemminger
2004-08-25 17:59 ` [PATCH 2.6] (3/4) netem - support packet duplication Stephen Hemminger
` (5 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-25 17:57 UTC (permalink / raw)
To: David S. Miller; +Cc: netdev
Update comments in netem.
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c 2004-08-24 14:43:05 -07:00
+++ b/net/sched/sch_netem.c 2004-08-24 14:43:05 -07:00
@@ -6,6 +6,9 @@
* as published by the Free Software Foundation; either version
* 2 of the License, or (at your option) any later version.
*
+ * Many of the algorithms and ideas for this came from
+ * NIST Net which is not copyrighted.
+ *
* Authors: Stephen Hemminger <shemminger@osdl.org>
* Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
*/
@@ -22,11 +25,31 @@
#include <net/pkt_sched.h>
-/* Network emulator
- *
- * This scheduler can alters spacing and order
- * Similar to NISTnet and BSD Dummynet.
- */
+/* Network Emulation Queuing algorithm.
+ ====================================
+
+ Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
+ Network Emulation Tool
+ [2] Luigi Rizzo, DummyNet for FreeBSD
+
+ ----------------------------------------------------------------
+
+ This started out as a simple way to delay outgoing packets to
+ test TCP but has grown to include most of the functionality
+ of a full blown network emulator like NISTnet. It can delay
+ packets and add random jitter (and correlation). The random
+ distribution can be loaded from a table as well to provide
+ normal, Pareto, or experimental curves. Packet loss,
+ duplication, and reordering can also be emulated.
+
+ This qdisc does not do classification that can be handled in
+ layering other disciplines. It does not need to do bandwidth
+ control either since that can be handled by using token
+ bucket or other rate control.
+
+ The simulator is limited by the Linux timer resolution
+ and will create packet bursts on the HZ boundary (1ms).
+*/
struct netem_sched_data {
struct Qdisc *qdisc;
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2.6] (3/4) netem - support packet duplication
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
2004-08-25 17:57 ` [PATCH 2.6] (2/4) netem - comment update Stephen Hemminger
@ 2004-08-25 17:59 ` Stephen Hemminger
2004-08-25 18:01 ` [PATCH 2.6] (4/4) netem - change parameters shouldn't destroy child qdisc Stephen Hemminger
` (4 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-25 17:59 UTC (permalink / raw)
To: David S. Miller; +Cc: netdev
Add support for duplicating packets.
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c 2004-08-24 16:58:13 -07:00
+++ b/net/sched/sch_netem.c 2004-08-24 16:58:13 -07:00
@@ -62,6 +62,7 @@
u32 counter;
u32 gap;
u32 jitter;
+ u32 duplicate;
};
/* Time stamp put into socket buffer control block */
@@ -624,22 +625,13 @@
/* Enqueue packets with underlying discipline (fifo)
* but mark them with current time first.
*/
-static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+static int netem_add_packet(struct Qdisc *sch, struct sk_buff *skb)
{
struct netem_sched_data *q = qdisc_priv(sch);
struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
psched_time_t now;
long delay;
- pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
-
- /* Random packet drop 0 => none, ~0 => all */
- if (q->loss && q->loss >= net_random()) {
- sch->stats.drops++;
- return 0; /* lie about loss so TCP doesn't know */
- }
-
-
/* If doing simple delay then gap == 0 so all packets
* go into the delayed holding queue
* otherwise if doing out of order only "1 out of gap"
@@ -671,7 +663,7 @@
sch->q.qlen++;
sch->stats.bytes += skb->len;
sch->stats.packets++;
- return 0;
+ return NET_XMIT_SUCCESS;
}
sch->stats.drops++;
@@ -679,6 +671,31 @@
return NET_XMIT_DROP;
}
+static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
+ struct netem_sched_data *q = qdisc_priv(sch);
+
+ pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
+
+ /* Random packet drop 0 => none, ~0 => all */
+ if (q->loss && q->loss >= net_random()) {
+ pr_debug("netem_enqueue: random loss\n");
+ sch->stats.drops++;
+ return 0; /* lie about loss so TCP doesn't know */
+ }
+
+ /* Random duplication */
+ if (q->duplicate && q->duplicate >= net_random()) {
+ struct sk_buff *skb2 = skb_clone(skb, GFP_ATOMIC);
+
+ pr_debug("netem_enqueue: dup %p\n", skb2);
+ if (skb2)
+ netem_add_packet(sch, skb2);
+ }
+
+ return netem_add_packet(sch, skb);
+}
+
/* Requeue packets but don't change time stamp */
static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
{
@@ -806,6 +823,7 @@
q->limit = qopt->limit;
q->gap = qopt->gap;
q->loss = qopt->loss;
+ q->duplicate = qopt->duplicate;
}
sch_tree_unlock(sch);
@@ -849,6 +867,7 @@
qopt.limit = q->limit;
qopt.loss = q->loss;
qopt.gap = q->gap;
+ qopt.duplicate = q->duplicate;
RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2.6] (4/4) netem - change parameters shouldn't destroy child qdisc
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
2004-08-25 17:57 ` [PATCH 2.6] (2/4) netem - comment update Stephen Hemminger
2004-08-25 17:59 ` [PATCH 2.6] (3/4) netem - support packet duplication Stephen Hemminger
@ 2004-08-25 18:01 ` Stephen Hemminger
2004-08-25 23:15 ` [PATCH 2.6] netem - add correlated random number support Stephen Hemminger
2004-08-25 18:08 ` [PATCH 2.6] netem - configurable distributions Stephen Hemminger
` (3 subsequent siblings)
6 siblings, 1 reply; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-25 18:01 UTC (permalink / raw)
To: David S. Miller; +Cc: netdev
Fix netem to allow changing parameters without zapping the underlying
qdisc.
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c 2004-08-24 16:58:27 -07:00
+++ b/net/sched/sch_netem.c 2004-08-24 16:58:27 -07:00
@@ -795,37 +795,17 @@
static int netem_change(struct Qdisc *sch, struct rtattr *opt)
{
struct netem_sched_data *q = qdisc_priv(sch);
- struct tc_netem_qopt *qopt = RTA_DATA(opt);
- struct Qdisc *child;
- int ret;
+ const struct tc_netem_qopt *qopt = RTA_DATA(opt);
if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
return -EINVAL;
- child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
- if (!child)
- return -EINVAL;
-
- ret = set_fifo_limit(child, qopt->limit);
- if (ret) {
- qdisc_destroy(child);
- return ret;
- }
-
- sch_tree_lock(sch);
- if (child) {
- child = xchg(&q->qdisc, child);
- if (child != &noop_qdisc)
- qdisc_destroy(child);
-
- q->latency = qopt->latency;
- q->jitter = qopt->jitter;
- q->limit = qopt->limit;
- q->gap = qopt->gap;
- q->loss = qopt->loss;
- q->duplicate = qopt->duplicate;
- }
- sch_tree_unlock(sch);
+ q->latency = qopt->latency;
+ q->jitter = qopt->jitter;
+ q->limit = qopt->limit;
+ q->gap = qopt->gap;
+ q->loss = qopt->loss;
+ q->duplicate = qopt->duplicate;
return 0;
}
@@ -833,19 +813,42 @@
static int netem_init(struct Qdisc *sch, struct rtattr *opt)
{
struct netem_sched_data *q = qdisc_priv(sch);
+ const struct tc_netem_qopt *qopt;
+ int ret;
- if (!opt)
+ if (!opt || opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
return -EINVAL;
skb_queue_head_init(&q->delayed);
- q->qdisc = &noop_qdisc;
-
init_timer(&q->timer);
q->timer.function = netem_watchdog;
q->timer.data = (unsigned long) sch;
q->counter = 0;
- return netem_change(sch, opt);
+ q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+ if (!q->qdisc) {
+ pr_debug("netem: qdisc create failed\n");
+ return -ENOMEM;
+ }
+
+ qopt = RTA_DATA(opt);
+ ret = set_fifo_limit(q->qdisc, qopt->limit);
+ if (ret) {
+ pr_debug("netem: can't set fifo limit\n");
+ goto error;
+ }
+
+ ret = netem_change(sch, opt);
+ if (ret) {
+ pr_debug("netem: change failed\n");
+ goto error;
+ }
+
+ return 0;
+
+ error:
+ qdisc_destroy(q->qdisc);
+ return ret;
}
static void netem_destroy(struct Qdisc *sch)
@@ -862,6 +865,7 @@
unsigned char *b = skb->tail;
struct tc_netem_qopt qopt;
+ memset(&qopt, 0, sizeof(qopt));
qopt.latency = q->latency;
qopt.jitter = q->jitter;
qopt.limit = q->limit;
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2.6] netem - configurable distributions
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
` (2 preceding siblings ...)
2004-08-25 18:01 ` [PATCH 2.6] (4/4) netem - change parameters shouldn't destroy child qdisc Stephen Hemminger
@ 2004-08-25 18:08 ` Stephen Hemminger
2004-08-25 20:50 ` [PATCH 2.4] netem -- update to match new 2.6 version Stephen Hemminger
` (2 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-25 18:08 UTC (permalink / raw)
To: David S. Miller; +Cc: netdev
Instead of the hard coded normal distribution, allow the distribution
table to be loaded by tc. The new version of tc/netem loads the data
from a file.
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c 2004-08-25 11:08:08 -07:00
+++ b/net/sched/sch_netem.c 2004-08-25 11:08:08 -07:00
@@ -63,6 +63,12 @@
u32 gap;
u32 jitter;
u32 duplicate;
+
+ struct dtable {
+ u32 size;
+ struct rcu_head rcu;
+ s16 table[0];
+ } *distribution;
struct crndstate {
unsigned long last;
@@ -103,556 +109,35 @@
return answer;
}
-/* This is the distribution table for the normal distribution produced
- * with NISTnet tools.
- * The entries represent a scaled inverse of the cumulative distribution
- * function.
- */
-#define TABLESIZE 2048
-#define TABLEFACTOR 8192
-
-static const short disttable[TABLESIZE] = {
- -31473, -26739, -25226, -24269,
- -23560, -22993, -22518, -22109,
- -21749, -21426, -21133, -20865,
- -20618, -20389, -20174, -19972,
- -19782, -19601, -19430, -19267,
- -19112, -18962, -18819, -18681,
- -18549, -18421, -18298, -18178,
- -18062, -17950, -17841, -17735,
- -17632, -17532, -17434, -17339,
- -17245, -17155, -17066, -16979,
- -16894, -16811, -16729, -16649,
- -16571, -16494, -16419, -16345,
- -16272, -16201, -16130, -16061,
- -15993, -15926, -15861, -15796,
- -15732, -15669, -15607, -15546,
- -15486, -15426, -15368, -15310,
- -15253, -15196, -15140, -15086,
- -15031, -14977, -14925, -14872,
- -14821, -14769, -14719, -14669,
- -14619, -14570, -14522, -14473,
- -14426, -14379, -14332, -14286,
- -14241, -14196, -14150, -14106,
- -14062, -14019, -13976, -13933,
- -13890, -13848, -13807, -13765,
- -13724, -13684, -13643, -13604,
- -13564, -13525, -13486, -13447,
- -13408, -13370, -13332, -13295,
- -13258, -13221, -13184, -13147,
- -13111, -13075, -13040, -13004,
- -12969, -12934, -12899, -12865,
- -12830, -12796, -12762, -12729,
- -12695, -12662, -12629, -12596,
- -12564, -12531, -12499, -12467,
- -12435, -12404, -12372, -12341,
- -12310, -12279, -12248, -12218,
- -12187, -12157, -12127, -12097,
- -12067, -12038, -12008, -11979,
- -11950, -11921, -11892, -11863,
- -11835, -11806, -11778, -11750,
- -11722, -11694, -11666, -11639,
- -11611, -11584, -11557, -11530,
- -11503, -11476, -11450, -11423,
- -11396, -11370, -11344, -11318,
- -11292, -11266, -11240, -11214,
- -11189, -11164, -11138, -11113,
- -11088, -11063, -11038, -11013,
- -10988, -10964, -10939, -10915,
- -10891, -10866, -10843, -10818,
- -10794, -10770, -10747, -10723,
- -10700, -10676, -10652, -10630,
- -10606, -10583, -10560, -10537,
- -10514, -10491, -10469, -10446,
- -10424, -10401, -10378, -10356,
- -10334, -10312, -10290, -10267,
- -10246, -10224, -10202, -10180,
- -10158, -10137, -10115, -10094,
- -10072, -10051, -10030, -10009,
- -9988, -9967, -9945, -9925,
- -9904, -9883, -9862, -9842,
- -9821, -9800, -9780, -9760,
- -9739, -9719, -9699, -9678,
- -9658, -9638, -9618, -9599,
- -9578, -9559, -9539, -9519,
- -9499, -9480, -9461, -9441,
- -9422, -9402, -9383, -9363,
- -9344, -9325, -9306, -9287,
- -9268, -9249, -9230, -9211,
- -9192, -9173, -9155, -9136,
- -9117, -9098, -9080, -9062,
- -9043, -9025, -9006, -8988,
- -8970, -8951, -8933, -8915,
- -8897, -8879, -8861, -8843,
- -8825, -8807, -8789, -8772,
- -8754, -8736, -8718, -8701,
- -8683, -8665, -8648, -8630,
- -8613, -8595, -8578, -8561,
- -8543, -8526, -8509, -8492,
- -8475, -8458, -8441, -8423,
- -8407, -8390, -8373, -8356,
- -8339, -8322, -8305, -8289,
- -8272, -8255, -8239, -8222,
- -8206, -8189, -8172, -8156,
- -8140, -8123, -8107, -8090,
- -8074, -8058, -8042, -8025,
- -8009, -7993, -7977, -7961,
- -7945, -7929, -7913, -7897,
- -7881, -7865, -7849, -7833,
- -7817, -7802, -7786, -7770,
- -7754, -7739, -7723, -7707,
- -7692, -7676, -7661, -7645,
- -7630, -7614, -7599, -7583,
- -7568, -7553, -7537, -7522,
- -7507, -7492, -7476, -7461,
- -7446, -7431, -7416, -7401,
- -7385, -7370, -7356, -7340,
- -7325, -7311, -7296, -7281,
- -7266, -7251, -7236, -7221,
- -7207, -7192, -7177, -7162,
- -7148, -7133, -7118, -7104,
- -7089, -7075, -7060, -7046,
- -7031, -7016, -7002, -6988,
- -6973, -6959, -6944, -6930,
- -6916, -6901, -6887, -6873,
- -6859, -6844, -6830, -6816,
- -6802, -6788, -6774, -6760,
- -6746, -6731, -6717, -6704,
- -6690, -6675, -6661, -6647,
- -6633, -6620, -6606, -6592,
- -6578, -6564, -6550, -6537,
- -6523, -6509, -6495, -6482,
- -6468, -6454, -6441, -6427,
- -6413, -6400, -6386, -6373,
- -6359, -6346, -6332, -6318,
- -6305, -6291, -6278, -6264,
- -6251, -6238, -6224, -6211,
- -6198, -6184, -6171, -6158,
- -6144, -6131, -6118, -6105,
- -6091, -6078, -6065, -6052,
- -6039, -6025, -6012, -5999,
- -5986, -5973, -5960, -5947,
- -5934, -5921, -5908, -5895,
- -5882, -5869, -5856, -5843,
- -5830, -5817, -5804, -5791,
- -5779, -5766, -5753, -5740,
- -5727, -5714, -5702, -5689,
- -5676, -5663, -5650, -5638,
- -5625, -5612, -5600, -5587,
- -5575, -5562, -5549, -5537,
- -5524, -5512, -5499, -5486,
- -5474, -5461, -5449, -5436,
- -5424, -5411, -5399, -5386,
- -5374, -5362, -5349, -5337,
- -5324, -5312, -5299, -5287,
- -5275, -5263, -5250, -5238,
- -5226, -5213, -5201, -5189,
- -5177, -5164, -5152, -5140,
- -5128, -5115, -5103, -5091,
- -5079, -5067, -5055, -5043,
- -5030, -5018, -5006, -4994,
- -4982, -4970, -4958, -4946,
- -4934, -4922, -4910, -4898,
- -4886, -4874, -4862, -4850,
- -4838, -4826, -4814, -4803,
- -4791, -4778, -4767, -4755,
- -4743, -4731, -4719, -4708,
- -4696, -4684, -4672, -4660,
- -4649, -4637, -4625, -4613,
- -4601, -4590, -4578, -4566,
- -4554, -4543, -4531, -4520,
- -4508, -4496, -4484, -4473,
- -4461, -4449, -4438, -4427,
- -4415, -4403, -4392, -4380,
- -4368, -4357, -4345, -4334,
- -4322, -4311, -4299, -4288,
- -4276, -4265, -4253, -4242,
- -4230, -4219, -4207, -4196,
- -4184, -4173, -4162, -4150,
- -4139, -4128, -4116, -4105,
- -4094, -4082, -4071, -4060,
- -4048, -4037, -4026, -4014,
- -4003, -3992, -3980, -3969,
- -3958, -3946, -3935, -3924,
- -3913, -3901, -3890, -3879,
- -3868, -3857, -3845, -3834,
- -3823, -3812, -3801, -3790,
- -3779, -3767, -3756, -3745,
- -3734, -3723, -3712, -3700,
- -3689, -3678, -3667, -3656,
- -3645, -3634, -3623, -3612,
- -3601, -3590, -3579, -3568,
- -3557, -3545, -3535, -3524,
- -3513, -3502, -3491, -3480,
- -3469, -3458, -3447, -3436,
- -3425, -3414, -3403, -3392,
- -3381, -3370, -3360, -3348,
- -3337, -3327, -3316, -3305,
- -3294, -3283, -3272, -3262,
- -3251, -3240, -3229, -3218,
- -3207, -3197, -3185, -3175,
- -3164, -3153, -3142, -3132,
- -3121, -3110, -3099, -3088,
- -3078, -3067, -3056, -3045,
- -3035, -3024, -3013, -3003,
- -2992, -2981, -2970, -2960,
- -2949, -2938, -2928, -2917,
- -2906, -2895, -2885, -2874,
- -2864, -2853, -2842, -2832,
- -2821, -2810, -2800, -2789,
- -2778, -2768, -2757, -2747,
- -2736, -2725, -2715, -2704,
- -2694, -2683, -2673, -2662,
- -2651, -2641, -2630, -2620,
- -2609, -2599, -2588, -2578,
- -2567, -2556, -2546, -2535,
- -2525, -2515, -2504, -2493,
- -2483, -2472, -2462, -2451,
- -2441, -2431, -2420, -2410,
- -2399, -2389, -2378, -2367,
- -2357, -2347, -2336, -2326,
- -2315, -2305, -2295, -2284,
- -2274, -2263, -2253, -2243,
- -2232, -2222, -2211, -2201,
- -2191, -2180, -2170, -2159,
- -2149, -2139, -2128, -2118,
- -2107, -2097, -2087, -2076,
- -2066, -2056, -2046, -2035,
- -2025, -2014, -2004, -1994,
- -1983, -1973, -1963, -1953,
- -1942, -1932, -1921, -1911,
- -1901, -1891, -1880, -1870,
- -1860, -1849, -1839, -1829,
- -1819, -1808, -1798, -1788,
- -1778, -1767, -1757, -1747,
- -1736, -1726, -1716, -1706,
- -1695, -1685, -1675, -1665,
- -1654, -1644, -1634, -1624,
- -1613, -1603, -1593, -1583,
- -1573, -1563, -1552, -1542,
- -1532, -1522, -1511, -1501,
- -1491, -1481, -1471, -1461,
- -1450, -1440, -1430, -1420,
- -1409, -1400, -1389, -1379,
- -1369, -1359, -1348, -1339,
- -1328, -1318, -1308, -1298,
- -1288, -1278, -1267, -1257,
- -1247, -1237, -1227, -1217,
- -1207, -1196, -1186, -1176,
- -1166, -1156, -1146, -1135,
- -1126, -1115, -1105, -1095,
- -1085, -1075, -1065, -1055,
- -1044, -1034, -1024, -1014,
- -1004, -994, -984, -974,
- -964, -954, -944, -933,
- -923, -913, -903, -893,
- -883, -873, -863, -853,
- -843, -833, -822, -812,
- -802, -792, -782, -772,
- -762, -752, -742, -732,
- -722, -712, -702, -691,
- -682, -671, -662, -651,
- -641, -631, -621, -611,
- -601, -591, -581, -571,
- -561, -551, -541, -531,
- -521, -511, -501, -491,
- -480, -471, -460, -451,
- -440, -430, -420, -410,
- -400, -390, -380, -370,
- -360, -350, -340, -330,
- -320, -310, -300, -290,
- -280, -270, -260, -250,
- -240, -230, -220, -210,
- -199, -190, -179, -170,
- -159, -150, -139, -129,
- -119, -109, -99, -89,
- -79, -69, -59, -49,
- -39, -29, -19, -9,
- 1, 11, 21, 31,
- 41, 51, 61, 71,
- 81, 91, 101, 111,
- 121, 131, 141, 152,
- 161, 172, 181, 192,
- 202, 212, 222, 232,
- 242, 252, 262, 272,
- 282, 292, 302, 312,
- 322, 332, 342, 352,
- 362, 372, 382, 392,
- 402, 412, 422, 433,
- 442, 453, 462, 473,
- 483, 493, 503, 513,
- 523, 533, 543, 553,
- 563, 573, 583, 593,
- 603, 613, 623, 633,
- 643, 653, 664, 673,
- 684, 694, 704, 714,
- 724, 734, 744, 754,
- 764, 774, 784, 794,
- 804, 815, 825, 835,
- 845, 855, 865, 875,
- 885, 895, 905, 915,
- 925, 936, 946, 956,
- 966, 976, 986, 996,
- 1006, 1016, 1026, 1037,
- 1047, 1057, 1067, 1077,
- 1087, 1097, 1107, 1117,
- 1128, 1138, 1148, 1158,
- 1168, 1178, 1188, 1198,
- 1209, 1219, 1229, 1239,
- 1249, 1259, 1269, 1280,
- 1290, 1300, 1310, 1320,
- 1330, 1341, 1351, 1361,
- 1371, 1381, 1391, 1402,
- 1412, 1422, 1432, 1442,
- 1452, 1463, 1473, 1483,
- 1493, 1503, 1513, 1524,
- 1534, 1544, 1554, 1565,
- 1575, 1585, 1595, 1606,
- 1616, 1626, 1636, 1647,
- 1656, 1667, 1677, 1687,
- 1697, 1708, 1718, 1729,
- 1739, 1749, 1759, 1769,
- 1780, 1790, 1800, 1810,
- 1821, 1831, 1841, 1851,
- 1862, 1872, 1883, 1893,
- 1903, 1913, 1923, 1934,
- 1944, 1955, 1965, 1975,
- 1985, 1996, 2006, 2016,
- 2027, 2037, 2048, 2058,
- 2068, 2079, 2089, 2099,
- 2110, 2120, 2130, 2141,
- 2151, 2161, 2172, 2182,
- 2193, 2203, 2213, 2224,
- 2234, 2245, 2255, 2265,
- 2276, 2286, 2297, 2307,
- 2318, 2328, 2338, 2349,
- 2359, 2370, 2380, 2391,
- 2401, 2412, 2422, 2433,
- 2443, 2454, 2464, 2475,
- 2485, 2496, 2506, 2517,
- 2527, 2537, 2548, 2559,
- 2569, 2580, 2590, 2601,
- 2612, 2622, 2632, 2643,
- 2654, 2664, 2675, 2685,
- 2696, 2707, 2717, 2728,
- 2738, 2749, 2759, 2770,
- 2781, 2791, 2802, 2813,
- 2823, 2834, 2845, 2855,
- 2866, 2877, 2887, 2898,
- 2909, 2919, 2930, 2941,
- 2951, 2962, 2973, 2984,
- 2994, 3005, 3015, 3027,
- 3037, 3048, 3058, 3069,
- 3080, 3091, 3101, 3113,
- 3123, 3134, 3145, 3156,
- 3166, 3177, 3188, 3199,
- 3210, 3220, 3231, 3242,
- 3253, 3264, 3275, 3285,
- 3296, 3307, 3318, 3329,
- 3340, 3351, 3362, 3373,
- 3384, 3394, 3405, 3416,
- 3427, 3438, 3449, 3460,
- 3471, 3482, 3493, 3504,
- 3515, 3526, 3537, 3548,
- 3559, 3570, 3581, 3592,
- 3603, 3614, 3625, 3636,
- 3647, 3659, 3670, 3681,
- 3692, 3703, 3714, 3725,
- 3736, 3747, 3758, 3770,
- 3781, 3792, 3803, 3814,
- 3825, 3837, 3848, 3859,
- 3870, 3881, 3893, 3904,
- 3915, 3926, 3937, 3949,
- 3960, 3971, 3983, 3994,
- 4005, 4017, 4028, 4039,
- 4051, 4062, 4073, 4085,
- 4096, 4107, 4119, 4130,
- 4141, 4153, 4164, 4175,
- 4187, 4198, 4210, 4221,
- 4233, 4244, 4256, 4267,
- 4279, 4290, 4302, 4313,
- 4325, 4336, 4348, 4359,
- 4371, 4382, 4394, 4406,
- 4417, 4429, 4440, 4452,
- 4464, 4475, 4487, 4499,
- 4510, 4522, 4533, 4545,
- 4557, 4569, 4581, 4592,
- 4604, 4616, 4627, 4639,
- 4651, 4663, 4674, 4686,
- 4698, 4710, 4722, 4734,
- 4746, 4758, 4769, 4781,
- 4793, 4805, 4817, 4829,
- 4841, 4853, 4865, 4877,
- 4889, 4900, 4913, 4925,
- 4936, 4949, 4961, 4973,
- 4985, 4997, 5009, 5021,
- 5033, 5045, 5057, 5070,
- 5081, 5094, 5106, 5118,
- 5130, 5143, 5155, 5167,
- 5179, 5191, 5204, 5216,
- 5228, 5240, 5253, 5265,
- 5278, 5290, 5302, 5315,
- 5327, 5340, 5352, 5364,
- 5377, 5389, 5401, 5414,
- 5426, 5439, 5451, 5464,
- 5476, 5489, 5502, 5514,
- 5527, 5539, 5552, 5564,
- 5577, 5590, 5603, 5615,
- 5628, 5641, 5653, 5666,
- 5679, 5691, 5704, 5717,
- 5730, 5743, 5756, 5768,
- 5781, 5794, 5807, 5820,
- 5833, 5846, 5859, 5872,
- 5885, 5897, 5911, 5924,
- 5937, 5950, 5963, 5976,
- 5989, 6002, 6015, 6028,
- 6042, 6055, 6068, 6081,
- 6094, 6108, 6121, 6134,
- 6147, 6160, 6174, 6187,
- 6201, 6214, 6227, 6241,
- 6254, 6267, 6281, 6294,
- 6308, 6321, 6335, 6348,
- 6362, 6375, 6389, 6403,
- 6416, 6430, 6443, 6457,
- 6471, 6485, 6498, 6512,
- 6526, 6540, 6554, 6567,
- 6581, 6595, 6609, 6623,
- 6637, 6651, 6665, 6679,
- 6692, 6706, 6721, 6735,
- 6749, 6763, 6777, 6791,
- 6805, 6819, 6833, 6848,
- 6862, 6876, 6890, 6905,
- 6919, 6933, 6948, 6962,
- 6976, 6991, 7005, 7020,
- 7034, 7049, 7064, 7078,
- 7093, 7107, 7122, 7136,
- 7151, 7166, 7180, 7195,
- 7210, 7225, 7240, 7254,
- 7269, 7284, 7299, 7314,
- 7329, 7344, 7359, 7374,
- 7389, 7404, 7419, 7434,
- 7449, 7465, 7480, 7495,
- 7510, 7526, 7541, 7556,
- 7571, 7587, 7602, 7618,
- 7633, 7648, 7664, 7680,
- 7695, 7711, 7726, 7742,
- 7758, 7773, 7789, 7805,
- 7821, 7836, 7852, 7868,
- 7884, 7900, 7916, 7932,
- 7948, 7964, 7981, 7997,
- 8013, 8029, 8045, 8061,
- 8078, 8094, 8110, 8127,
- 8143, 8160, 8176, 8193,
- 8209, 8226, 8242, 8259,
- 8276, 8292, 8309, 8326,
- 8343, 8360, 8377, 8394,
- 8410, 8428, 8444, 8462,
- 8479, 8496, 8513, 8530,
- 8548, 8565, 8582, 8600,
- 8617, 8634, 8652, 8670,
- 8687, 8704, 8722, 8740,
- 8758, 8775, 8793, 8811,
- 8829, 8847, 8865, 8883,
- 8901, 8919, 8937, 8955,
- 8974, 8992, 9010, 9029,
- 9047, 9066, 9084, 9103,
- 9121, 9140, 9159, 9177,
- 9196, 9215, 9234, 9253,
- 9272, 9291, 9310, 9329,
- 9349, 9368, 9387, 9406,
- 9426, 9445, 9465, 9484,
- 9504, 9524, 9544, 9563,
- 9583, 9603, 9623, 9643,
- 9663, 9683, 9703, 9723,
- 9744, 9764, 9785, 9805,
- 9826, 9846, 9867, 9888,
- 9909, 9930, 9950, 9971,
- 9993, 10013, 10035, 10056,
- 10077, 10099, 10120, 10142,
- 10163, 10185, 10207, 10229,
- 10251, 10273, 10294, 10317,
- 10339, 10361, 10384, 10406,
- 10428, 10451, 10474, 10496,
- 10519, 10542, 10565, 10588,
- 10612, 10635, 10658, 10682,
- 10705, 10729, 10752, 10776,
- 10800, 10824, 10848, 10872,
- 10896, 10921, 10945, 10969,
- 10994, 11019, 11044, 11069,
- 11094, 11119, 11144, 11169,
- 11195, 11221, 11246, 11272,
- 11298, 11324, 11350, 11376,
- 11402, 11429, 11456, 11482,
- 11509, 11536, 11563, 11590,
- 11618, 11645, 11673, 11701,
- 11728, 11756, 11785, 11813,
- 11842, 11870, 11899, 11928,
- 11957, 11986, 12015, 12045,
- 12074, 12104, 12134, 12164,
- 12194, 12225, 12255, 12286,
- 12317, 12348, 12380, 12411,
- 12443, 12475, 12507, 12539,
- 12571, 12604, 12637, 12670,
- 12703, 12737, 12771, 12804,
- 12839, 12873, 12907, 12942,
- 12977, 13013, 13048, 13084,
- 13120, 13156, 13192, 13229,
- 13267, 13304, 13341, 13379,
- 13418, 13456, 13495, 13534,
- 13573, 13613, 13653, 13693,
- 13734, 13775, 13817, 13858,
- 13901, 13943, 13986, 14029,
- 14073, 14117, 14162, 14206,
- 14252, 14297, 14343, 14390,
- 14437, 14485, 14533, 14582,
- 14631, 14680, 14731, 14782,
- 14833, 14885, 14937, 14991,
- 15044, 15099, 15154, 15210,
- 15266, 15324, 15382, 15441,
- 15500, 15561, 15622, 15684,
- 15747, 15811, 15877, 15943,
- 16010, 16078, 16148, 16218,
- 16290, 16363, 16437, 16513,
- 16590, 16669, 16749, 16831,
- 16915, 17000, 17088, 17177,
- 17268, 17362, 17458, 17556,
- 17657, 17761, 17868, 17977,
- 18090, 18207, 18328, 18452,
- 18581, 18715, 18854, 18998,
- 19149, 19307, 19472, 19645,
- 19828, 20021, 20226, 20444,
- 20678, 20930, 21204, 21503,
- 21835, 22206, 22630, 23124,
- 23721, 24478, 25529, 27316,
-};
-
-/* tabledist - return a pseudo-randomly distributed value with mean mu and
+/* table_dist - return a pseudo-randomly distributed value with mean mu and
* std deviation sigma. Uses table lookup to approximate the desired
* distribution, and a uniformly-distributed pseudo-random source.
*/
-static inline int tabledist(int mu, int sigma)
+static int table_dist(const struct dtable *dist,
+ struct crndstate *state,
+ int mu, int sigma)
{
- int x;
- int index;
- int sigmamod, sigmadiv;
+ int t, x;
+ unsigned long rnd;
if (sigma == 0)
return mu;
+
+ rnd = get_crandom(state);
- index = (net_random() & (TABLESIZE-1));
- sigmamod = sigma%TABLEFACTOR;
- sigmadiv = sigma/TABLEFACTOR;
- x = sigmamod*disttable[index];
+ /* default uniform distribution */
+ if (dist == NULL)
+ return (rnd % (2*sigma)) - sigma + mu;
+
+ t = dist->table[rnd % dist->size];
+ x = (sigma % TCA_NETEM_TABLEFACTOR) * t;
if (x >= 0)
- x += TABLEFACTOR/2;
+ x += TCA_NETEM_TABLEFACTOR/2;
else
- x -= TABLEFACTOR/2;
+ x -= TCA_NETEM_TABLEFACTOR/2;
- x /= TABLEFACTOR;
- x += sigmadiv*disttable[index];
- x += mu;
- return x;
+ return (x + sigma * t)/TCA_NETEM_TABLEFACTOR + mu;
}
/* Enqueue packets with underlying discipline (fifo)
@@ -683,10 +168,14 @@
q->counter = 0;
PSCHED_GET_TIME(now);
- if (q->jitter)
- delay = tabledist(q->latency, q->jitter);
- else
- delay = q->latency;
+
+ rcu_read_lock();
+ delay = table_dist(rcu_dereference(q->distribution),
+ &q->delay_cor, q->latency, q->jitter);
+ rcu_read_unlock();
+
+ pr_debug("netem_enqueue: delay %ld (mu=%u sigma=%u)\n",
+ delay, q->latency, q->jitter);
PSCHED_TADD2(now, delay, cb->time_to_send);
@@ -825,13 +314,50 @@
return ret;
}
+static struct dtable *new_dtable(int size, const __s16 *data)
+{
+ struct dtable *d;
+ int i;
+
+ d = kmalloc(sizeof(*d) + size*sizeof(d->table[0]), GFP_KERNEL);
+ if (d) {
+ d->size = size;
+ for (i = 0; i < size; i++)
+ d->table[i] = data[i];
+ }
+ return d;
+}
+
+static void dtable_rcu_free(struct rcu_head *rcu)
+{
+ kfree(container_of(rcu, struct dtable, rcu));
+}
+
static int netem_change(struct Qdisc *sch, struct rtattr *opt)
{
struct netem_sched_data *q = qdisc_priv(sch);
const struct tc_netem_qopt *qopt = RTA_DATA(opt);
+ long data_size = opt->rta_len - RTA_LENGTH(sizeof(*qopt));
+ struct dtable *dt;
+
+ if (data_size < 0) {
+ pr_debug("netem: requested options < current api\n");
+ return -EINVAL;
+ }
- if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
+ data_size /= sizeof(qopt->delay_dist[0]);
+ if (data_size > 16384) {
+ pr_debug("netem: bad distribution data size\n");
return -EINVAL;
+ }
+
+ if (data_size > 0) {
+ dt = new_dtable(data_size, qopt->delay_dist);
+ if (!dt)
+ return -ENOMEM;
+ } else
+ dt = NULL;
+
q->latency = qopt->latency;
q->jitter = qopt->jitter;
@@ -840,6 +366,11 @@
q->loss = qopt->loss;
q->duplicate = qopt->duplicate;
+ /* handle race with enqueue and change? */
+ dt = xchg(&q->distribution, dt);
+ if (dt)
+ call_rcu(&dt->rcu, dtable_rcu_free);
+
init_crandom(&q->delay_cor, qopt->delay_corr);
init_crandom(&q->loss_cor, qopt->loss_corr);
init_crandom(&q->dup_cor, qopt->dup_corr);
@@ -861,7 +392,8 @@
q->timer.function = netem_watchdog;
q->timer.data = (unsigned long) sch;
q->counter = 0;
-
+ q->distribution = NULL;
+
q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
if (!q->qdisc) {
pr_debug("netem: qdisc create failed\n");
@@ -893,12 +425,14 @@
struct netem_sched_data *q = qdisc_priv(sch);
del_timer_sync(&q->timer);
+
+ kfree(q->distribution);
qdisc_destroy(q->qdisc);
}
static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
{
- struct netem_sched_data *q = qdisc_priv(sch);
+ const struct netem_sched_data *q = qdisc_priv(sch);
unsigned char *b = skb->tail;
struct tc_netem_qopt qopt;
@@ -913,6 +447,7 @@
qopt.loss_corr = q->loss_cor.rho;
qopt.dup_corr = q->dup_cor.rho;
+ /* don't dump out distribution table */
RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
return skb->len;
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2.4] netem -- update to match new 2.6 version
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
` (3 preceding siblings ...)
2004-08-25 18:08 ` [PATCH 2.6] netem - configurable distributions Stephen Hemminger
@ 2004-08-25 20:50 ` Stephen Hemminger
2004-08-25 23:25 ` [PATCH 2.6] (1/4) netem - update API for new features David S. Miller
2004-08-26 12:08 ` jamal
6 siblings, 0 replies; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-25 20:50 UTC (permalink / raw)
To: David S. Miller; +Cc: netdev
This combines the previous 5 changes to netem for 2.6 to
support duplication, correlation and distribution tables.
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
diff -Nru a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
--- a/include/linux/pkt_sched.h 2004-08-25 13:46:01 -07:00
+++ b/include/linux/pkt_sched.h 2004-08-25 13:46:01 -07:00
@@ -432,7 +432,8 @@
#define TCA_ATM_MAX TCA_ATM_STATE
-/* Network emulator */
+/* Network section */
+
struct tc_netem_qopt
{
__u32 latency; /* added delay (us) */
@@ -440,7 +441,14 @@
__u32 loss; /* random packet loss (0=none ~0=100%) */
__u32 gap; /* re-ordering gap (0 for delay all) */
__u32 duplicate; /* random packet dup (0=none ~0=100%) */
- __u32 jitter; /* random jitter in latency (us) */
+ __u32 jitter; /* delay sigma (us) */
+
+ __u32 delay_corr; /* delay correllation (0=none ~0=100%) */
+ __u32 loss_corr; /* packet loss correllation (0=none ~0=100%) */
+ __u32 dup_corr; /* duplicate correlation (0=none ~0=100%) */
+
+ __s16 delay_dist[0]; /* delay distribution table (optional) */
+#define TCA_NETEM_TABLEFACTOR 8192
};
#endif
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c 2004-08-25 13:46:01 -07:00
+++ b/net/sched/sch_netem.c 2004-08-25 13:46:01 -07:00
@@ -6,6 +6,9 @@
* as published by the Free Software Foundation; either version
* 2 of the License, or (at your option) any later version.
*
+ * Many of the algorithms and ideas for this came from
+ * NIST Net which is not copyrighted.
+ *
* Authors: Stephen Hemminger <shemminger@osdl.org>
* Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
*/
@@ -23,11 +26,31 @@
#include <net/pkt_sched.h>
-/* Network emulator
- *
- * This scheduler can alters spacing and order
- * Similar to NISTnet and BSD Dummynet.
- */
+/* Network Emulation Queuing algorithm.
+ ====================================
+
+ Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
+ Network Emulation Tool
+ [2] Luigi Rizzo, DummyNet for FreeBSD
+
+ ----------------------------------------------------------------
+
+ This started out as a simple way to delay outgoing packets to
+ test TCP but has grown to include most of the functionality
+ of a full blown network emulator like NISTnet. It can delay
+ packets and add random jitter (and correlation). The random
+ distribution can be loaded from a table as well to provide
+ normal, Pareto, or experimental curves. Packet loss,
+ duplication, and reordering can also be emulated.
+
+ This qdisc does not do classification that can be handled in
+ layering other disciplines. It does not need to do bandwidth
+ control either since that can be handled by using token
+ bucket or other rate control.
+
+ The simulator is limited by the Linux timer resolution
+ and will create packet bursts on the HZ boundary (1ms).
+*/
struct netem_sched_data {
struct Qdisc *qdisc;
@@ -40,6 +63,17 @@
u32 counter;
u32 gap;
u32 jitter;
+ u32 duplicate;
+
+ struct dtable {
+ u32 size;
+ s16 table[0];
+ } *distribution;
+
+ struct crndstate {
+ unsigned long last;
+ unsigned long rho;
+ } delay_cor, loss_cor, dup_cor;
};
/* Time stamp put into socket buffer control block */
@@ -47,577 +81,75 @@
psched_time_t time_to_send;
};
-/* This is the distribution table for the normal distribution produced
- * with NISTnet tools.
- * The entries represent a scaled inverse of the cumulative distribution
- * function.
+/* init_crandom - initialize correlated random number generator
+ * Use entropy source for initial seed.
*/
-#define TABLESIZE 2048
-#define TABLEFACTOR 8192
+static void init_crandom(struct crndstate *state, unsigned long rho)
+{
+ state->rho = rho;
+ state->last = net_random();
+}
-static const short disttable[TABLESIZE] = {
- -31473, -26739, -25226, -24269,
- -23560, -22993, -22518, -22109,
- -21749, -21426, -21133, -20865,
- -20618, -20389, -20174, -19972,
- -19782, -19601, -19430, -19267,
- -19112, -18962, -18819, -18681,
- -18549, -18421, -18298, -18178,
- -18062, -17950, -17841, -17735,
- -17632, -17532, -17434, -17339,
- -17245, -17155, -17066, -16979,
- -16894, -16811, -16729, -16649,
- -16571, -16494, -16419, -16345,
- -16272, -16201, -16130, -16061,
- -15993, -15926, -15861, -15796,
- -15732, -15669, -15607, -15546,
- -15486, -15426, -15368, -15310,
- -15253, -15196, -15140, -15086,
- -15031, -14977, -14925, -14872,
- -14821, -14769, -14719, -14669,
- -14619, -14570, -14522, -14473,
- -14426, -14379, -14332, -14286,
- -14241, -14196, -14150, -14106,
- -14062, -14019, -13976, -13933,
- -13890, -13848, -13807, -13765,
- -13724, -13684, -13643, -13604,
- -13564, -13525, -13486, -13447,
- -13408, -13370, -13332, -13295,
- -13258, -13221, -13184, -13147,
- -13111, -13075, -13040, -13004,
- -12969, -12934, -12899, -12865,
- -12830, -12796, -12762, -12729,
- -12695, -12662, -12629, -12596,
- -12564, -12531, -12499, -12467,
- -12435, -12404, -12372, -12341,
- -12310, -12279, -12248, -12218,
- -12187, -12157, -12127, -12097,
- -12067, -12038, -12008, -11979,
- -11950, -11921, -11892, -11863,
- -11835, -11806, -11778, -11750,
- -11722, -11694, -11666, -11639,
- -11611, -11584, -11557, -11530,
- -11503, -11476, -11450, -11423,
- -11396, -11370, -11344, -11318,
- -11292, -11266, -11240, -11214,
- -11189, -11164, -11138, -11113,
- -11088, -11063, -11038, -11013,
- -10988, -10964, -10939, -10915,
- -10891, -10866, -10843, -10818,
- -10794, -10770, -10747, -10723,
- -10700, -10676, -10652, -10630,
- -10606, -10583, -10560, -10537,
- -10514, -10491, -10469, -10446,
- -10424, -10401, -10378, -10356,
- -10334, -10312, -10290, -10267,
- -10246, -10224, -10202, -10180,
- -10158, -10137, -10115, -10094,
- -10072, -10051, -10030, -10009,
- -9988, -9967, -9945, -9925,
- -9904, -9883, -9862, -9842,
- -9821, -9800, -9780, -9760,
- -9739, -9719, -9699, -9678,
- -9658, -9638, -9618, -9599,
- -9578, -9559, -9539, -9519,
- -9499, -9480, -9461, -9441,
- -9422, -9402, -9383, -9363,
- -9344, -9325, -9306, -9287,
- -9268, -9249, -9230, -9211,
- -9192, -9173, -9155, -9136,
- -9117, -9098, -9080, -9062,
- -9043, -9025, -9006, -8988,
- -8970, -8951, -8933, -8915,
- -8897, -8879, -8861, -8843,
- -8825, -8807, -8789, -8772,
- -8754, -8736, -8718, -8701,
- -8683, -8665, -8648, -8630,
- -8613, -8595, -8578, -8561,
- -8543, -8526, -8509, -8492,
- -8475, -8458, -8441, -8423,
- -8407, -8390, -8373, -8356,
- -8339, -8322, -8305, -8289,
- -8272, -8255, -8239, -8222,
- -8206, -8189, -8172, -8156,
- -8140, -8123, -8107, -8090,
- -8074, -8058, -8042, -8025,
- -8009, -7993, -7977, -7961,
- -7945, -7929, -7913, -7897,
- -7881, -7865, -7849, -7833,
- -7817, -7802, -7786, -7770,
- -7754, -7739, -7723, -7707,
- -7692, -7676, -7661, -7645,
- -7630, -7614, -7599, -7583,
- -7568, -7553, -7537, -7522,
- -7507, -7492, -7476, -7461,
- -7446, -7431, -7416, -7401,
- -7385, -7370, -7356, -7340,
- -7325, -7311, -7296, -7281,
- -7266, -7251, -7236, -7221,
- -7207, -7192, -7177, -7162,
- -7148, -7133, -7118, -7104,
- -7089, -7075, -7060, -7046,
- -7031, -7016, -7002, -6988,
- -6973, -6959, -6944, -6930,
- -6916, -6901, -6887, -6873,
- -6859, -6844, -6830, -6816,
- -6802, -6788, -6774, -6760,
- -6746, -6731, -6717, -6704,
- -6690, -6675, -6661, -6647,
- -6633, -6620, -6606, -6592,
- -6578, -6564, -6550, -6537,
- -6523, -6509, -6495, -6482,
- -6468, -6454, -6441, -6427,
- -6413, -6400, -6386, -6373,
- -6359, -6346, -6332, -6318,
- -6305, -6291, -6278, -6264,
- -6251, -6238, -6224, -6211,
- -6198, -6184, -6171, -6158,
- -6144, -6131, -6118, -6105,
- -6091, -6078, -6065, -6052,
- -6039, -6025, -6012, -5999,
- -5986, -5973, -5960, -5947,
- -5934, -5921, -5908, -5895,
- -5882, -5869, -5856, -5843,
- -5830, -5817, -5804, -5791,
- -5779, -5766, -5753, -5740,
- -5727, -5714, -5702, -5689,
- -5676, -5663, -5650, -5638,
- -5625, -5612, -5600, -5587,
- -5575, -5562, -5549, -5537,
- -5524, -5512, -5499, -5486,
- -5474, -5461, -5449, -5436,
- -5424, -5411, -5399, -5386,
- -5374, -5362, -5349, -5337,
- -5324, -5312, -5299, -5287,
- -5275, -5263, -5250, -5238,
- -5226, -5213, -5201, -5189,
- -5177, -5164, -5152, -5140,
- -5128, -5115, -5103, -5091,
- -5079, -5067, -5055, -5043,
- -5030, -5018, -5006, -4994,
- -4982, -4970, -4958, -4946,
- -4934, -4922, -4910, -4898,
- -4886, -4874, -4862, -4850,
- -4838, -4826, -4814, -4803,
- -4791, -4778, -4767, -4755,
- -4743, -4731, -4719, -4708,
- -4696, -4684, -4672, -4660,
- -4649, -4637, -4625, -4613,
- -4601, -4590, -4578, -4566,
- -4554, -4543, -4531, -4520,
- -4508, -4496, -4484, -4473,
- -4461, -4449, -4438, -4427,
- -4415, -4403, -4392, -4380,
- -4368, -4357, -4345, -4334,
- -4322, -4311, -4299, -4288,
- -4276, -4265, -4253, -4242,
- -4230, -4219, -4207, -4196,
- -4184, -4173, -4162, -4150,
- -4139, -4128, -4116, -4105,
- -4094, -4082, -4071, -4060,
- -4048, -4037, -4026, -4014,
- -4003, -3992, -3980, -3969,
- -3958, -3946, -3935, -3924,
- -3913, -3901, -3890, -3879,
- -3868, -3857, -3845, -3834,
- -3823, -3812, -3801, -3790,
- -3779, -3767, -3756, -3745,
- -3734, -3723, -3712, -3700,
- -3689, -3678, -3667, -3656,
- -3645, -3634, -3623, -3612,
- -3601, -3590, -3579, -3568,
- -3557, -3545, -3535, -3524,
- -3513, -3502, -3491, -3480,
- -3469, -3458, -3447, -3436,
- -3425, -3414, -3403, -3392,
- -3381, -3370, -3360, -3348,
- -3337, -3327, -3316, -3305,
- -3294, -3283, -3272, -3262,
- -3251, -3240, -3229, -3218,
- -3207, -3197, -3185, -3175,
- -3164, -3153, -3142, -3132,
- -3121, -3110, -3099, -3088,
- -3078, -3067, -3056, -3045,
- -3035, -3024, -3013, -3003,
- -2992, -2981, -2970, -2960,
- -2949, -2938, -2928, -2917,
- -2906, -2895, -2885, -2874,
- -2864, -2853, -2842, -2832,
- -2821, -2810, -2800, -2789,
- -2778, -2768, -2757, -2747,
- -2736, -2725, -2715, -2704,
- -2694, -2683, -2673, -2662,
- -2651, -2641, -2630, -2620,
- -2609, -2599, -2588, -2578,
- -2567, -2556, -2546, -2535,
- -2525, -2515, -2504, -2493,
- -2483, -2472, -2462, -2451,
- -2441, -2431, -2420, -2410,
- -2399, -2389, -2378, -2367,
- -2357, -2347, -2336, -2326,
- -2315, -2305, -2295, -2284,
- -2274, -2263, -2253, -2243,
- -2232, -2222, -2211, -2201,
- -2191, -2180, -2170, -2159,
- -2149, -2139, -2128, -2118,
- -2107, -2097, -2087, -2076,
- -2066, -2056, -2046, -2035,
- -2025, -2014, -2004, -1994,
- -1983, -1973, -1963, -1953,
- -1942, -1932, -1921, -1911,
- -1901, -1891, -1880, -1870,
- -1860, -1849, -1839, -1829,
- -1819, -1808, -1798, -1788,
- -1778, -1767, -1757, -1747,
- -1736, -1726, -1716, -1706,
- -1695, -1685, -1675, -1665,
- -1654, -1644, -1634, -1624,
- -1613, -1603, -1593, -1583,
- -1573, -1563, -1552, -1542,
- -1532, -1522, -1511, -1501,
- -1491, -1481, -1471, -1461,
- -1450, -1440, -1430, -1420,
- -1409, -1400, -1389, -1379,
- -1369, -1359, -1348, -1339,
- -1328, -1318, -1308, -1298,
- -1288, -1278, -1267, -1257,
- -1247, -1237, -1227, -1217,
- -1207, -1196, -1186, -1176,
- -1166, -1156, -1146, -1135,
- -1126, -1115, -1105, -1095,
- -1085, -1075, -1065, -1055,
- -1044, -1034, -1024, -1014,
- -1004, -994, -984, -974,
- -964, -954, -944, -933,
- -923, -913, -903, -893,
- -883, -873, -863, -853,
- -843, -833, -822, -812,
- -802, -792, -782, -772,
- -762, -752, -742, -732,
- -722, -712, -702, -691,
- -682, -671, -662, -651,
- -641, -631, -621, -611,
- -601, -591, -581, -571,
- -561, -551, -541, -531,
- -521, -511, -501, -491,
- -480, -471, -460, -451,
- -440, -430, -420, -410,
- -400, -390, -380, -370,
- -360, -350, -340, -330,
- -320, -310, -300, -290,
- -280, -270, -260, -250,
- -240, -230, -220, -210,
- -199, -190, -179, -170,
- -159, -150, -139, -129,
- -119, -109, -99, -89,
- -79, -69, -59, -49,
- -39, -29, -19, -9,
- 1, 11, 21, 31,
- 41, 51, 61, 71,
- 81, 91, 101, 111,
- 121, 131, 141, 152,
- 161, 172, 181, 192,
- 202, 212, 222, 232,
- 242, 252, 262, 272,
- 282, 292, 302, 312,
- 322, 332, 342, 352,
- 362, 372, 382, 392,
- 402, 412, 422, 433,
- 442, 453, 462, 473,
- 483, 493, 503, 513,
- 523, 533, 543, 553,
- 563, 573, 583, 593,
- 603, 613, 623, 633,
- 643, 653, 664, 673,
- 684, 694, 704, 714,
- 724, 734, 744, 754,
- 764, 774, 784, 794,
- 804, 815, 825, 835,
- 845, 855, 865, 875,
- 885, 895, 905, 915,
- 925, 936, 946, 956,
- 966, 976, 986, 996,
- 1006, 1016, 1026, 1037,
- 1047, 1057, 1067, 1077,
- 1087, 1097, 1107, 1117,
- 1128, 1138, 1148, 1158,
- 1168, 1178, 1188, 1198,
- 1209, 1219, 1229, 1239,
- 1249, 1259, 1269, 1280,
- 1290, 1300, 1310, 1320,
- 1330, 1341, 1351, 1361,
- 1371, 1381, 1391, 1402,
- 1412, 1422, 1432, 1442,
- 1452, 1463, 1473, 1483,
- 1493, 1503, 1513, 1524,
- 1534, 1544, 1554, 1565,
- 1575, 1585, 1595, 1606,
- 1616, 1626, 1636, 1647,
- 1656, 1667, 1677, 1687,
- 1697, 1708, 1718, 1729,
- 1739, 1749, 1759, 1769,
- 1780, 1790, 1800, 1810,
- 1821, 1831, 1841, 1851,
- 1862, 1872, 1883, 1893,
- 1903, 1913, 1923, 1934,
- 1944, 1955, 1965, 1975,
- 1985, 1996, 2006, 2016,
- 2027, 2037, 2048, 2058,
- 2068, 2079, 2089, 2099,
- 2110, 2120, 2130, 2141,
- 2151, 2161, 2172, 2182,
- 2193, 2203, 2213, 2224,
- 2234, 2245, 2255, 2265,
- 2276, 2286, 2297, 2307,
- 2318, 2328, 2338, 2349,
- 2359, 2370, 2380, 2391,
- 2401, 2412, 2422, 2433,
- 2443, 2454, 2464, 2475,
- 2485, 2496, 2506, 2517,
- 2527, 2537, 2548, 2559,
- 2569, 2580, 2590, 2601,
- 2612, 2622, 2632, 2643,
- 2654, 2664, 2675, 2685,
- 2696, 2707, 2717, 2728,
- 2738, 2749, 2759, 2770,
- 2781, 2791, 2802, 2813,
- 2823, 2834, 2845, 2855,
- 2866, 2877, 2887, 2898,
- 2909, 2919, 2930, 2941,
- 2951, 2962, 2973, 2984,
- 2994, 3005, 3015, 3027,
- 3037, 3048, 3058, 3069,
- 3080, 3091, 3101, 3113,
- 3123, 3134, 3145, 3156,
- 3166, 3177, 3188, 3199,
- 3210, 3220, 3231, 3242,
- 3253, 3264, 3275, 3285,
- 3296, 3307, 3318, 3329,
- 3340, 3351, 3362, 3373,
- 3384, 3394, 3405, 3416,
- 3427, 3438, 3449, 3460,
- 3471, 3482, 3493, 3504,
- 3515, 3526, 3537, 3548,
- 3559, 3570, 3581, 3592,
- 3603, 3614, 3625, 3636,
- 3647, 3659, 3670, 3681,
- 3692, 3703, 3714, 3725,
- 3736, 3747, 3758, 3770,
- 3781, 3792, 3803, 3814,
- 3825, 3837, 3848, 3859,
- 3870, 3881, 3893, 3904,
- 3915, 3926, 3937, 3949,
- 3960, 3971, 3983, 3994,
- 4005, 4017, 4028, 4039,
- 4051, 4062, 4073, 4085,
- 4096, 4107, 4119, 4130,
- 4141, 4153, 4164, 4175,
- 4187, 4198, 4210, 4221,
- 4233, 4244, 4256, 4267,
- 4279, 4290, 4302, 4313,
- 4325, 4336, 4348, 4359,
- 4371, 4382, 4394, 4406,
- 4417, 4429, 4440, 4452,
- 4464, 4475, 4487, 4499,
- 4510, 4522, 4533, 4545,
- 4557, 4569, 4581, 4592,
- 4604, 4616, 4627, 4639,
- 4651, 4663, 4674, 4686,
- 4698, 4710, 4722, 4734,
- 4746, 4758, 4769, 4781,
- 4793, 4805, 4817, 4829,
- 4841, 4853, 4865, 4877,
- 4889, 4900, 4913, 4925,
- 4936, 4949, 4961, 4973,
- 4985, 4997, 5009, 5021,
- 5033, 5045, 5057, 5070,
- 5081, 5094, 5106, 5118,
- 5130, 5143, 5155, 5167,
- 5179, 5191, 5204, 5216,
- 5228, 5240, 5253, 5265,
- 5278, 5290, 5302, 5315,
- 5327, 5340, 5352, 5364,
- 5377, 5389, 5401, 5414,
- 5426, 5439, 5451, 5464,
- 5476, 5489, 5502, 5514,
- 5527, 5539, 5552, 5564,
- 5577, 5590, 5603, 5615,
- 5628, 5641, 5653, 5666,
- 5679, 5691, 5704, 5717,
- 5730, 5743, 5756, 5768,
- 5781, 5794, 5807, 5820,
- 5833, 5846, 5859, 5872,
- 5885, 5897, 5911, 5924,
- 5937, 5950, 5963, 5976,
- 5989, 6002, 6015, 6028,
- 6042, 6055, 6068, 6081,
- 6094, 6108, 6121, 6134,
- 6147, 6160, 6174, 6187,
- 6201, 6214, 6227, 6241,
- 6254, 6267, 6281, 6294,
- 6308, 6321, 6335, 6348,
- 6362, 6375, 6389, 6403,
- 6416, 6430, 6443, 6457,
- 6471, 6485, 6498, 6512,
- 6526, 6540, 6554, 6567,
- 6581, 6595, 6609, 6623,
- 6637, 6651, 6665, 6679,
- 6692, 6706, 6721, 6735,
- 6749, 6763, 6777, 6791,
- 6805, 6819, 6833, 6848,
- 6862, 6876, 6890, 6905,
- 6919, 6933, 6948, 6962,
- 6976, 6991, 7005, 7020,
- 7034, 7049, 7064, 7078,
- 7093, 7107, 7122, 7136,
- 7151, 7166, 7180, 7195,
- 7210, 7225, 7240, 7254,
- 7269, 7284, 7299, 7314,
- 7329, 7344, 7359, 7374,
- 7389, 7404, 7419, 7434,
- 7449, 7465, 7480, 7495,
- 7510, 7526, 7541, 7556,
- 7571, 7587, 7602, 7618,
- 7633, 7648, 7664, 7680,
- 7695, 7711, 7726, 7742,
- 7758, 7773, 7789, 7805,
- 7821, 7836, 7852, 7868,
- 7884, 7900, 7916, 7932,
- 7948, 7964, 7981, 7997,
- 8013, 8029, 8045, 8061,
- 8078, 8094, 8110, 8127,
- 8143, 8160, 8176, 8193,
- 8209, 8226, 8242, 8259,
- 8276, 8292, 8309, 8326,
- 8343, 8360, 8377, 8394,
- 8410, 8428, 8444, 8462,
- 8479, 8496, 8513, 8530,
- 8548, 8565, 8582, 8600,
- 8617, 8634, 8652, 8670,
- 8687, 8704, 8722, 8740,
- 8758, 8775, 8793, 8811,
- 8829, 8847, 8865, 8883,
- 8901, 8919, 8937, 8955,
- 8974, 8992, 9010, 9029,
- 9047, 9066, 9084, 9103,
- 9121, 9140, 9159, 9177,
- 9196, 9215, 9234, 9253,
- 9272, 9291, 9310, 9329,
- 9349, 9368, 9387, 9406,
- 9426, 9445, 9465, 9484,
- 9504, 9524, 9544, 9563,
- 9583, 9603, 9623, 9643,
- 9663, 9683, 9703, 9723,
- 9744, 9764, 9785, 9805,
- 9826, 9846, 9867, 9888,
- 9909, 9930, 9950, 9971,
- 9993, 10013, 10035, 10056,
- 10077, 10099, 10120, 10142,
- 10163, 10185, 10207, 10229,
- 10251, 10273, 10294, 10317,
- 10339, 10361, 10384, 10406,
- 10428, 10451, 10474, 10496,
- 10519, 10542, 10565, 10588,
- 10612, 10635, 10658, 10682,
- 10705, 10729, 10752, 10776,
- 10800, 10824, 10848, 10872,
- 10896, 10921, 10945, 10969,
- 10994, 11019, 11044, 11069,
- 11094, 11119, 11144, 11169,
- 11195, 11221, 11246, 11272,
- 11298, 11324, 11350, 11376,
- 11402, 11429, 11456, 11482,
- 11509, 11536, 11563, 11590,
- 11618, 11645, 11673, 11701,
- 11728, 11756, 11785, 11813,
- 11842, 11870, 11899, 11928,
- 11957, 11986, 12015, 12045,
- 12074, 12104, 12134, 12164,
- 12194, 12225, 12255, 12286,
- 12317, 12348, 12380, 12411,
- 12443, 12475, 12507, 12539,
- 12571, 12604, 12637, 12670,
- 12703, 12737, 12771, 12804,
- 12839, 12873, 12907, 12942,
- 12977, 13013, 13048, 13084,
- 13120, 13156, 13192, 13229,
- 13267, 13304, 13341, 13379,
- 13418, 13456, 13495, 13534,
- 13573, 13613, 13653, 13693,
- 13734, 13775, 13817, 13858,
- 13901, 13943, 13986, 14029,
- 14073, 14117, 14162, 14206,
- 14252, 14297, 14343, 14390,
- 14437, 14485, 14533, 14582,
- 14631, 14680, 14731, 14782,
- 14833, 14885, 14937, 14991,
- 15044, 15099, 15154, 15210,
- 15266, 15324, 15382, 15441,
- 15500, 15561, 15622, 15684,
- 15747, 15811, 15877, 15943,
- 16010, 16078, 16148, 16218,
- 16290, 16363, 16437, 16513,
- 16590, 16669, 16749, 16831,
- 16915, 17000, 17088, 17177,
- 17268, 17362, 17458, 17556,
- 17657, 17761, 17868, 17977,
- 18090, 18207, 18328, 18452,
- 18581, 18715, 18854, 18998,
- 19149, 19307, 19472, 19645,
- 19828, 20021, 20226, 20444,
- 20678, 20930, 21204, 21503,
- 21835, 22206, 22630, 23124,
- 23721, 24478, 25529, 27316,
-};
+/* get_crandom - correlated random number generator
+ * Next number depends on last value.
+ * rho is scaled to avoid floating point.
+ */
+static unsigned long get_crandom(struct crndstate *state)
+{
+ u64 value, rho;
+ unsigned long answer;
-/* tabledist - return a pseudo-randomly distributed value with mean mu and
+ if (state->rho == 0) /* no correllation */
+ return net_random();
+
+ value = net_random();
+ rho = (u64)state->rho + 1;
+ answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
+ state->last = answer;
+ return answer;
+}
+
+/* table_dist - return a pseudo-randomly distributed value with mean mu and
* std deviation sigma. Uses table lookup to approximate the desired
* distribution, and a uniformly-distributed pseudo-random source.
*/
-static inline int tabledist(int mu, int sigma)
+static int table_dist(const struct dtable *dist,
+ struct crndstate *state,
+ int mu, int sigma)
{
- int x;
- int index;
- int sigmamod, sigmadiv;
+ int t, x;
+ unsigned long rnd;
if (sigma == 0)
return mu;
+
+ rnd = get_crandom(state);
+
+ /* default uniform distribution */
+ if (dist == NULL)
+ return (rnd % (2*sigma)) - sigma + mu;
- index = (net_random() & (TABLESIZE-1));
- sigmamod = sigma%TABLEFACTOR;
- sigmadiv = sigma/TABLEFACTOR;
- x = sigmamod*disttable[index];
+ t = dist->table[rnd % dist->size];
+ x = (sigma % TCA_NETEM_TABLEFACTOR) * t;
if (x >= 0)
- x += TABLEFACTOR/2;
+ x += TCA_NETEM_TABLEFACTOR/2;
else
- x -= TABLEFACTOR/2;
+ x -= TCA_NETEM_TABLEFACTOR/2;
- x /= TABLEFACTOR;
- x += sigmadiv*disttable[index];
- x += mu;
- return x;
+ return (x + sigma * t)/TCA_NETEM_TABLEFACTOR + mu;
}
/* Enqueue packets with underlying discipline (fifo)
* but mark them with current time first.
*/
-static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+static int netem_add_packet(struct Qdisc *sch, struct sk_buff *skb)
{
struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
psched_time_t now;
long delay;
- pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
-
- /* Random packet drop 0 => none, ~0 => all */
- if (q->loss && q->loss >= net_random()) {
- sch->stats.drops++;
- return 0; /* lie about loss so TCP doesn't know */
- }
-
-
/* If doing simple delay then gap == 0 so all packets
* go into the delayed holding queue
* otherwise if doing out of order only "1 out of gap"
@@ -636,10 +168,12 @@
q->counter = 0;
PSCHED_GET_TIME(now);
- if (q->jitter)
- delay = tabledist(q->latency, q->jitter);
- else
- delay = q->latency;
+
+ delay = table_dist(q->distribution,
+ &q->delay_cor, q->latency, q->jitter);
+
+ pr_debug("netem_enqueue: delay %ld (mu=%u sigma=%u)\n",
+ delay, q->latency, q->jitter);
PSCHED_TADD2(now, delay, cb->time_to_send);
@@ -649,7 +183,7 @@
sch->q.qlen++;
sch->stats.bytes += skb->len;
sch->stats.packets++;
- return 0;
+ return NET_XMIT_SUCCESS;
}
sch->stats.drops++;
@@ -657,6 +191,31 @@
return NET_XMIT_DROP;
}
+static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
+ struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+
+ pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
+
+ /* Random packet drop 0 => none, ~0 => all */
+ if (q->loss && q->loss >= get_crandom(&q->loss_cor)) {
+ pr_debug("netem_enqueue: random loss\n");
+ sch->stats.drops++;
+ return 0; /* lie about loss so TCP doesn't know */
+ }
+
+ /* Random duplication */
+ if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) {
+ struct sk_buff *skb2 = skb_clone(skb, GFP_ATOMIC);
+
+ pr_debug("netem_enqueue: dup %p\n", skb2);
+ if (skb2)
+ netem_add_packet(sch, skb2);
+ }
+
+ return netem_add_packet(sch, skb);
+}
+
/* Requeue packets but don't change time stamp */
static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
{
@@ -753,90 +312,139 @@
return ret;
}
-static int netem_change(struct Qdisc *sch, struct rtattr *opt)
+static struct dtable *new_dtable(int size, const __s16 *data)
{
- struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
- struct tc_netem_qopt *qopt = RTA_DATA(opt);
- struct Qdisc *child;
- int ret;
+ struct dtable *d;
+ int i;
- if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
- return -EINVAL;
+ d = kmalloc(sizeof(*d) + size*sizeof(d->table[0]), GFP_KERNEL);
+ if (d) {
+ d->size = size;
+ for (i = 0; i < size; i++)
+ d->table[i] = data[i];
+ }
+ return d;
+}
- child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
- if (!child)
+static int netem_change(struct Qdisc *sch, struct rtattr *opt)
+{
+ struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+ const struct tc_netem_qopt *qopt = RTA_DATA(opt);
+ long data_size = opt->rta_len - RTA_LENGTH(sizeof(*qopt));
+ struct dtable *dt;
+
+ if (data_size < 0) {
+ pr_debug( "netem: requested options < current api\n");
return -EINVAL;
-
- ret = set_fifo_limit(child, qopt->limit);
- if (ret) {
- qdisc_destroy(child);
- return ret;
}
- sch_tree_lock(sch);
- if (child) {
- child = xchg(&q->qdisc, child);
- if (child != &noop_qdisc)
- qdisc_destroy(child);
-
- q->latency = qopt->latency;
- q->jitter = qopt->jitter;
- q->limit = qopt->limit;
- q->gap = qopt->gap;
- q->loss = qopt->loss;
+ data_size /= sizeof(qopt->delay_dist[0]);
+ if (data_size > 16384) {
+ pr_debug("netem: bad distribution data size\n");
+ return -EINVAL;
}
- sch_tree_unlock(sch);
+
+ if (data_size > 0) {
+ dt = new_dtable(data_size, qopt->delay_dist);
+ if (!dt)
+ return -ENOMEM;
+ } else
+ dt = NULL;
+
+
+ q->latency = qopt->latency;
+ q->jitter = qopt->jitter;
+ q->limit = qopt->limit;
+ q->gap = qopt->gap;
+ q->loss = qopt->loss;
+ q->duplicate = qopt->duplicate;
+
+ spin_lock_bh(&sch->dev->queue_lock);
+ dt = xchg(&q->distribution, dt);
+ kfree(dt);
+ spin_unlock_bh(&sch->dev->queue_lock);
+
+ init_crandom(&q->delay_cor, qopt->delay_corr);
+ init_crandom(&q->loss_cor, qopt->loss_corr);
+ init_crandom(&q->dup_cor, qopt->dup_corr);
return 0;
}
static int netem_init(struct Qdisc *sch, struct rtattr *opt)
{
- struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
- int err;
+ struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+ const struct tc_netem_qopt *qopt;
+ int ret;
- if (!opt)
+ if (!opt || opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
return -EINVAL;
MOD_INC_USE_COUNT;
skb_queue_head_init(&q->delayed);
- q->qdisc = &noop_qdisc;
-
init_timer(&q->timer);
q->timer.function = netem_watchdog;
q->timer.data = (unsigned long) sch;
q->counter = 0;
+ q->distribution = NULL;
+
+ q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+ if (!q->qdisc) {
+ pr_debug("netem: qdisc create failed\n");
+ return -ENOMEM;
+ }
+
+ qopt = RTA_DATA(opt);
+ ret = set_fifo_limit(q->qdisc, qopt->limit);
+ if (ret) {
+ pr_debug("netem: can't set fifo limit\n");
+ goto error;
+ }
- err = netem_change(sch, opt);
- if (err != 0)
- MOD_DEC_USE_COUNT;
- return err;
+ ret = netem_change(sch, opt);
+ if (ret) {
+ pr_debug("netem: change failed\n");
+ goto error;
+ }
+
+ return 0;
+
+ error:
+ MOD_DEC_USE_COUNT;
+ qdisc_destroy(q->qdisc);
+ return ret;
}
static void netem_destroy(struct Qdisc *sch)
{
- struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+ struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
del_timer(&q->timer);
-
+
+ kfree(q->distribution);
qdisc_destroy(q->qdisc);
- q->qdisc = &noop_qdisc;
-
MOD_DEC_USE_COUNT;
}
static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
{
- struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+ const struct netem_sched_data *q
+ = (struct netem_sched_data *)sch->data;
unsigned char *b = skb->tail;
struct tc_netem_qopt qopt;
+ memset(&qopt, 0, sizeof(qopt));
qopt.latency = q->latency;
qopt.jitter = q->jitter;
qopt.limit = q->limit;
qopt.loss = q->loss;
qopt.gap = q->gap;
+ qopt.duplicate = q->duplicate;
+ qopt.delay_corr = q->delay_cor.rho;
+ qopt.loss_corr = q->loss_cor.rho;
+ qopt.dup_corr = q->dup_cor.rho;
+ /* don't dump out distribution table */
RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
return skb->len;
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2.6] netem - add correlated random number support
2004-08-25 18:01 ` [PATCH 2.6] (4/4) netem - change parameters shouldn't destroy child qdisc Stephen Hemminger
@ 2004-08-25 23:15 ` Stephen Hemminger
2004-08-25 23:52 ` David S. Miller
0 siblings, 1 reply; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-25 23:15 UTC (permalink / raw)
To: David S. Miller; +Cc: netdev
This patch adds correlated random number support (really just a sliding
average). Like most of this stuff, the concept came from NISTnet.
Dave, this applies after "(4/4) netem - change parameters shouldn't destroy child qdisc"
but before the patch to add loadable distributions, sorry for the confusion.
Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c 2004-08-25 16:14:27 -07:00
+++ b/net/sched/sch_netem.c 2004-08-25 16:14:27 -07:00
@@ -63,6 +63,11 @@
u32 gap;
u32 jitter;
u32 duplicate;
+
+ struct crndstate {
+ unsigned long last;
+ unsigned long rho;
+ } delay_cor, loss_cor, dup_cor;
};
/* Time stamp put into socket buffer control block */
@@ -70,6 +75,34 @@
psched_time_t time_to_send;
};
+/* init_crandom - initialize correlated random number generator
+ * Use entropy source for initial seed.
+ */
+static void init_crandom(struct crndstate *state, unsigned long rho)
+{
+ state->rho = rho;
+ state->last = net_random();
+}
+
+/* get_crandom - correlated random number generator
+ * Next number depends on last value.
+ * rho is scaled to avoid floating point.
+ */
+static unsigned long get_crandom(struct crndstate *state)
+{
+ u64 value, rho;
+ unsigned long answer;
+
+ if (state->rho == 0) /* no correllation */
+ return net_random();
+
+ value = net_random();
+ rho = (u64)state->rho + 1;
+ answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
+ state->last = answer;
+ return answer;
+}
+
/* This is the distribution table for the normal distribution produced
* with NISTnet tools.
* The entries represent a scaled inverse of the cumulative distribution
@@ -678,14 +711,14 @@
pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
/* Random packet drop 0 => none, ~0 => all */
- if (q->loss && q->loss >= net_random()) {
+ if (q->loss && q->loss >= get_crandom(&q->loss_cor)) {
pr_debug("netem_enqueue: random loss\n");
sch->stats.drops++;
return 0; /* lie about loss so TCP doesn't know */
}
/* Random duplication */
- if (q->duplicate && q->duplicate >= net_random()) {
+ if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) {
struct sk_buff *skb2 = skb_clone(skb, GFP_ATOMIC);
pr_debug("netem_enqueue: dup %p\n", skb2);
@@ -807,6 +840,10 @@
q->loss = qopt->loss;
q->duplicate = qopt->duplicate;
+ init_crandom(&q->delay_cor, qopt->delay_corr);
+ init_crandom(&q->loss_cor, qopt->loss_corr);
+ init_crandom(&q->dup_cor, qopt->dup_corr);
+
return 0;
}
@@ -872,6 +909,9 @@
qopt.loss = q->loss;
qopt.gap = q->gap;
qopt.duplicate = q->duplicate;
+ qopt.delay_corr = q->delay_cor.rho;
+ qopt.loss_corr = q->loss_cor.rho;
+ qopt.dup_corr = q->dup_cor.rho;
RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2.6] (1/4) netem - update API for new features
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
` (4 preceding siblings ...)
2004-08-25 20:50 ` [PATCH 2.4] netem -- update to match new 2.6 version Stephen Hemminger
@ 2004-08-25 23:25 ` David S. Miller
2004-08-26 12:08 ` jamal
6 siblings, 0 replies; 12+ messages in thread
From: David S. Miller @ 2004-08-25 23:25 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: netdev
On Wed, 25 Aug 2004 10:53:39 -0700
Stephen Hemminger <shemminger@osdl.org> wrote:
> Extend netem options to support new features.
This breaks all existing tc binaries. We have to stop
doing this.
Yes, you can extend the structure, but when you do that you
have to teach functions like netem_change() how to cope
with the old structure layout.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2.6] netem - add correlated random number support
2004-08-25 23:15 ` [PATCH 2.6] netem - add correlated random number support Stephen Hemminger
@ 2004-08-25 23:52 ` David S. Miller
0 siblings, 0 replies; 12+ messages in thread
From: David S. Miller @ 2004-08-25 23:52 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: netdev
On Wed, 25 Aug 2004 16:15:35 -0700
Stephen Hemminger <shemminger@osdl.org> wrote:
> Dave, this applies after "(4/4) netem - change parameters shouldn't destroy child qdisc"
> but before the patch to add loadable distributions, sorry for the confusion.
Just making sure you understand that I've rejected that whole
patch set because of the netem options structure breakage issue.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2.6] (1/4) netem - update API for new features
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
` (5 preceding siblings ...)
2004-08-25 23:25 ` [PATCH 2.6] (1/4) netem - update API for new features David S. Miller
@ 2004-08-26 12:08 ` jamal
2004-08-26 16:16 ` Stephen Hemminger
6 siblings, 1 reply; 12+ messages in thread
From: jamal @ 2004-08-26 12:08 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: David S. Miller, netdev
On Wed, 2004-08-25 at 13:53, Stephen Hemminger wrote:
> Extend netem options to support new features.
>
> struct tc_netem_qopt
> {
> __u32 latency; /* added delay (us) */
> @@ -409,6 +410,13 @@
> __u32 loss; /* random packet loss (0=none ~0=100%) */
> __u32 gap; /* re-ordering gap (0 for delay all) */
> __u32 duplicate; /* random packet dup (0=none ~0=100%) */
> - __u32 jitter; /* random jitter in latency (us) */
> + __u32 jitter; /* delay sigma (us) */
> +
> + __u32 delay_corr; /* delay correllation (0=none ~0=100%) */
> + __u32 loss_corr; /* packet loss correllation (0=none ~0=100%) */
> + __u32 dup_corr; /* duplicate correlation (0=none ~0=100%) */
> +
> + __s16 delay_dist[0]; /* delay distribution table (optional) */
> +#define TCA_NETEM_TABLEFACTOR 8192
> };
You should really send the delay_dist in its own TLV to avoid
the kind of mistakes that showed up in u32 classifier.
Also allows you to extend that structure in the future.
cheers,
jamal
PS:- kudos on moving that stuff to user space.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2.6] (1/4) netem - update API for new features
2004-08-26 12:08 ` jamal
@ 2004-08-26 16:16 ` Stephen Hemminger
2004-08-26 18:13 ` jamal
0 siblings, 1 reply; 12+ messages in thread
From: Stephen Hemminger @ 2004-08-26 16:16 UTC (permalink / raw)
To: hadi; +Cc: David S. Miller, netdev
On 26 Aug 2004 08:08:51 -0400
jamal <hadi@cyberus.ca> wrote:
> On Wed, 2004-08-25 at 13:53, Stephen Hemminger wrote:
> > Extend netem options to support new features.
> >
>
> > struct tc_netem_qopt
> > {
> > __u32 latency; /* added delay (us) */
> > @@ -409,6 +410,13 @@
> > __u32 loss; /* random packet loss (0=none ~0=100%) */
> > __u32 gap; /* re-ordering gap (0 for delay all) */
> > __u32 duplicate; /* random packet dup (0=none ~0=100%) */
> > - __u32 jitter; /* random jitter in latency (us) */
> > + __u32 jitter; /* delay sigma (us) */
> > +
> > + __u32 delay_corr; /* delay correllation (0=none ~0=100%) */
> > + __u32 loss_corr; /* packet loss correllation (0=none ~0=100%) */
> > + __u32 dup_corr; /* duplicate correlation (0=none ~0=100%) */
> > +
> > + __s16 delay_dist[0]; /* delay distribution table (optional) */
> > +#define TCA_NETEM_TABLEFACTOR 8192
> > };
>
> You should really send the delay_dist in its own TLV to avoid
> the kind of mistakes that showed up in u32 classifier.
> Also allows you to extend that structure in the future.
>
> cheers,
> jamal
It would be good but the whole qdisc api (init, change) is really structured
around a single TLV.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2.6] (1/4) netem - update API for new features
2004-08-26 16:16 ` Stephen Hemminger
@ 2004-08-26 18:13 ` jamal
0 siblings, 0 replies; 12+ messages in thread
From: jamal @ 2004-08-26 18:13 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: David S. Miller, netdev
On Thu, 2004-08-26 at 12:16, Stephen Hemminger wrote:
> On 26 Aug 2004 08:08:51 -0400
> jamal <hadi@cyberus.ca> wrote:
[..]
> >
> > You should really send the delay_dist in its own TLV to avoid
> > the kind of mistakes that showed up in u32 classifier.
> > Also allows you to extend that structure in the future.
> >
> > cheers,
> > jamal
>
> It would be good but the whole qdisc api (init, change) is really structured
> around a single TLV.
Just pass nested attributes. The API is fine.
cheers,
jamal
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2004-08-26 18:13 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2004-08-25 17:53 [PATCH 2.6] (1/4) netem - update API for new features Stephen Hemminger
2004-08-25 17:57 ` [PATCH 2.6] (2/4) netem - comment update Stephen Hemminger
2004-08-25 17:59 ` [PATCH 2.6] (3/4) netem - support packet duplication Stephen Hemminger
2004-08-25 18:01 ` [PATCH 2.6] (4/4) netem - change parameters shouldn't destroy child qdisc Stephen Hemminger
2004-08-25 23:15 ` [PATCH 2.6] netem - add correlated random number support Stephen Hemminger
2004-08-25 23:52 ` David S. Miller
2004-08-25 18:08 ` [PATCH 2.6] netem - configurable distributions Stephen Hemminger
2004-08-25 20:50 ` [PATCH 2.4] netem -- update to match new 2.6 version Stephen Hemminger
2004-08-25 23:25 ` [PATCH 2.6] (1/4) netem - update API for new features David S. Miller
2004-08-26 12:08 ` jamal
2004-08-26 16:16 ` Stephen Hemminger
2004-08-26 18:13 ` jamal
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).