netdev
[Top] [All Lists]

[RFC] netem - add jitter support.

To: "David S. Miller" <davem@xxxxxxxxxx>
Subject: [RFC] netem - add jitter support.
From: Stephen Hemminger <shemminger@xxxxxxxx>
Date: Thu, 8 Jul 2004 13:53:20 -0700
Cc: netdev@xxxxxxxxxxx
Organization: Open Source Development Lab
Sender: netdev-bounce@xxxxxxxxxxx
This patch adds jitter if desired to the delayed packets in the
netem scheduler.  I dropped the rate stuff out and reorganized so
that an underlying pfifo queue is used (next plan is to make it
have class ops).

The jitter is given as sigma to a Gaussian normal distribution.  The actual
implementation is a reduced form of the table driven stuff in NISTnet
(free). 

Signed-off-by: Stephen Hemminger <shemminger@xxxxxxxx>


diff -Nru a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
--- a/include/linux/pkt_sched.h 2004-07-08 13:45:06 -07:00
+++ b/include/linux/pkt_sched.h 2004-07-08 13:45:06 -07:00
@@ -447,6 +447,6 @@
        __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   rate;           /* maximum transmit rate (bytes/sec) */
+       __u32   jitter;         /* random jitter in latency (us) */
 };
 #endif
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c     2004-07-08 13:45:06 -07:00
+++ b/net/sched/sch_netem.c     2004-07-08 13:45:06 -07:00
@@ -18,6 +18,7 @@
 #include <linux/errno.h>
 #include <linux/netdevice.h>
 #include <linux/skbuff.h>
+#include <linux/rtnetlink.h>
 
 #include <net/pkt_sched.h>
 
@@ -28,14 +29,16 @@
  */
 
 struct netem_sched_data {
-       struct sk_buff_head qnormal;
-       struct sk_buff_head qdelay;
+       struct Qdisc    *qdisc;
+       struct sk_buff_head delayed;
        struct timer_list timer;
 
        u32 latency;
        u32 loss;
+       u32 limit;
        u32 counter;
        u32 gap;
+       u32 jitter;
 };
 
 /* Time stamp put into socket buffer control block */
@@ -43,6 +46,558 @@
        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.
+ */
+#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
+ * 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)
+{
+       int x;
+       int index;
+       int sigmamod, sigmadiv;
+
+       if (sigma == 0)
+               return mu;
+
+       index = (net_random() & (TABLESIZE-1));
+       sigmamod = sigma%TABLEFACTOR;
+       sigmadiv = sigma/TABLEFACTOR;
+       x = sigmamod*disttable[index];
+
+       if (x >= 0)
+               x += TABLEFACTOR/2;
+       else
+               x -= TABLEFACTOR/2;
+
+       x /= TABLEFACTOR;
+       x += sigmadiv*disttable[index];
+       x += mu;
+       return x;
+}
+
 /* Enqueue packets with underlying discipline (fifo)
  * but mark them with current time first.
  */
@@ -50,110 +605,116 @@
 {
        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 >= net_random()) {
+       if (q->loss && q->loss >= net_random()) {
                sch->stats.drops++;
                return 0;       /* lie about loss so TCP doesn't know */
        }
 
-       if (q->qnormal.qlen < sch->dev->tx_queue_len) {
-               PSCHED_GET_TIME(cb->time_to_send);
-               PSCHED_TADD(cb->time_to_send, q->latency);
 
-               __skb_queue_tail(&q->qnormal, skb);
-               sch->q.qlen++;
-               sch->stats.bytes += skb->len;
-               sch->stats.packets++;
-               return 0;
+       /* 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"
+        * packets will be delayed.
+        */
+       if (q->counter < q->gap) {
+               int ret;
+
+               ++q->counter;
+               ret = q->qdisc->enqueue(skb, q->qdisc);
+               if (ret)
+                       sch->stats.drops++;
+               return ret;
        }
-
-       sch->stats.drops++;
-       kfree_skb(skb);
-       return NET_XMIT_DROP;
+       
+       q->counter = 0;
+       
+       PSCHED_GET_TIME(now);
+       if (q->jitter) 
+               delay = tabledist(q->latency, q->jitter);
+       else
+               delay = q->latency;
+
+       PSCHED_TADD2(now, delay, cb->time_to_send);
+       
+       /* Always queue at tail to keep packets in order */
+       __skb_queue_tail(&q->delayed, skb);
+       sch->q.qlen++;
+       sch->stats.bytes += skb->len;
+       sch->stats.packets++;
+       return 0;
 }
 
 /* Requeue packets but don't change time stamp */
 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
 {
        struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+       int ret;
 
-       __skb_queue_head(&q->qnormal, skb);
-       sch->q.qlen++;
-       return 0;
+       if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0)
+               sch->q.qlen++;
+
+       return ret;
 }
 
-/*
- * Check the look aside buffer list, and see if any freshly baked buffers.
- * If head of queue is not baked, set timer.
- */
-static struct sk_buff *netem_get_delayed(struct netem_sched_data *q)
+static unsigned int netem_drop(struct Qdisc* sch)
 {
-       struct sk_buff *skb;
-       psched_time_t now;
-       long delay;
-
-       skb = skb_peek(&q->qdelay);
-       if (skb) {
-               const struct netem_skb_cb *cb
-                       = (const struct netem_skb_cb *)skb->cb;
-
-               PSCHED_GET_TIME(now);
-               delay = PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now));
-               pr_debug("netem_dequeue: delay queue %p@%lu %ld\n",
-                        skb, jiffies, delay);
-
-               /* it's baked enough */
-               if (delay <= 0) {
-                       __skb_unlink(skb, &q->qdelay);
-                       del_timer(&q->timer);
-                       return skb;
-               }
+       struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+       unsigned int len;
 
-               if (!timer_pending(&q->timer)) {
-                       q->timer.expires = jiffies + delay;
-                       add_timer(&q->timer);
-               }
+       if ((len = q->qdisc->ops->drop(q->qdisc)) != 0) {
+               sch->q.qlen--;
+               sch->stats.drops++;
        }
-       return NULL;
+       return len;
 }
 
 /* Dequeue packet.
- * If packet needs to be held up, then put in the delay
- * queue and set timer to wakeup later.
+ *  Move all packets that are ready to send from the delay holding
+ *  list to the underlying qdisc, then just call dequeue
  */
 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
 {
        struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
        struct sk_buff *skb;
+       psched_time_t now;
+
+       PSCHED_GET_TIME(now);
+       while ((skb = skb_peek(&q->delayed)) != NULL) {
+               const struct netem_skb_cb *cb
+                       = (const struct netem_skb_cb *)skb->cb;
+               long delay 
+                       = PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now));
+               pr_debug("netem_dequeue: delay queue %p@%lu %ld\n",
+                        skb, jiffies, delay);
 
-       skb = netem_get_delayed(q);
-       if (!skb && (skb = __skb_dequeue(&q->qnormal))) {
-               /* are we doing out of order packet skip? */
-               if (q->counter < q->gap) {
-                       pr_debug("netem_dequeue: send %p normally\n", skb);
-                       q->counter++;
-               } else {
-                       /* don't send now hold for later */
-                       pr_debug("netem_dequeue: hold [%p]@%lu\n", skb, 
jiffies);
-                       __skb_queue_tail(&q->qdelay, skb);
-                       q->counter = 0;
-                       skb = netem_get_delayed(q);
+               /* if more time remaining? */
+               if (delay > 0) {
+                       mod_timer(&q->timer, jiffies + delay);
+                       break;
                }
+               __skb_unlink(skb, &q->delayed);
+
+               if (q->qdisc->enqueue(skb, q->qdisc))
+                       sch->stats.drops++;
        }
 
-       if (skb)
+       skb = q->qdisc->dequeue(q->qdisc);
+       if (skb) 
                sch->q.qlen--;
        return skb;
 }
 
-static void netem_timer(unsigned long arg)
+static void netem_watchdog(unsigned long arg)
 {
        struct Qdisc *sch = (struct Qdisc *)arg;
 
-       pr_debug("netem_timer: fired @%lu\n", jiffies);
+       pr_debug("netem_watchdog: fired @%lu\n", jiffies);
        netif_schedule(sch->dev);
 }
 
@@ -161,24 +722,63 @@
 {
        struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 
-       skb_queue_purge(&q->qnormal);
-       skb_queue_purge(&q->qdelay);
+       qdisc_reset(q->qdisc);
+       skb_queue_purge(&q->delayed);
 
        sch->q.qlen = 0;
        del_timer_sync(&q->timer);
 }
 
+static int set_fifo_limit(struct Qdisc *q, int limit)
+{
+        struct rtattr *rta;
+       int ret = -ENOMEM;
+
+       rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
+       if (rta) {
+               rta->rta_type = RTM_NEWQDISC;
+               rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt)); 
+               ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
+               
+               ret = q->ops->change(q, rta);
+               kfree(rta);
+       }
+       return ret;
+}
+
 static int netem_change(struct Qdisc *sch, struct rtattr *opt)
 {
        struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
        struct tc_netem_qopt *qopt = RTA_DATA(opt);
+       struct Qdisc *child;
+       int ret;
 
-       if (qopt->limit)
-               sch->dev->tx_queue_len = qopt->limit;
+       if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
+               return -EINVAL;
 
-       q->gap = qopt->gap;
-       q->loss = qopt->loss;
-       q->latency = qopt->latency;
+       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;
+       }
+       sch_tree_unlock(sch);
 
        return 0;
 }
@@ -190,10 +790,11 @@
        if (!opt)
                return -EINVAL;
 
-       skb_queue_head_init(&q->qnormal);
-       skb_queue_head_init(&q->qdelay);
+       skb_queue_head_init(&q->delayed);
+       q->qdisc = &noop_qdisc;
+
        init_timer(&q->timer);
-       q->timer.function = netem_timer;
+       q->timer.function = netem_watchdog;
        q->timer.data = (unsigned long) sch;
        q->counter = 0;
 
@@ -214,6 +815,7 @@
        struct tc_netem_qopt qopt;
 
        qopt.latency = q->latency;
+       qopt.jitter = q->jitter;
        qopt.limit = sch->dev->tx_queue_len;
        qopt.loss = q->loss;
        qopt.gap = q->gap;
@@ -233,6 +835,7 @@
        .enqueue        =       netem_enqueue,
        .dequeue        =       netem_dequeue,
        .requeue        =       netem_requeue,
+       .drop           =       netem_drop,
        .init           =       netem_init,
        .reset          =       netem_reset,
        .destroy        =       netem_destroy,

<Prev in Thread] Current Thread [Next in Thread>