netdev
[Top] [All Lists]

[PATCH 2.6] netem update

To: "David S. Miller" <davem@xxxxxxxxxx>, Jamal Hadi Salim <hadi@xxxxxxxx>
Subject: [PATCH 2.6] netem update
From: Stephen Hemminger <shemminger@xxxxxxxx>
Date: Fri, 27 Aug 2004 12:17:52 -0700
Cc: netdev@xxxxxxxxxxx
Organization: Open Source Development Lab
Sender: netdev-bounce@xxxxxxxxxxx
This is a third revision of the netem extensions which provides
        * packet duplication
        * correlated random number
        * loading distribution table

The API is backwards compatible and now uses nested elements to allow
for easier future changes.

diff -urN -X dontdiff linux-2.6/include/linux/pkt_sched.h 
netem-2.6/include/linux/pkt_sched.h
--- linux-2.6/include/linux/pkt_sched.h 2004-07-12 08:05:35.000000000 -0700
+++ netem-2.6/include/linux/pkt_sched.h 2004-08-27 09:31:29.000000000 -0700
@@ -402,6 +402,16 @@
 #define TCA_ATM_MAX    TCA_ATM_STATE
 
 /* Network emulator */
+
+enum
+{
+       TCA_NETEM_UNSPEC,
+       TCA_NETEM_CORR,
+       TCA_NETEM_DELAY_DIST,
+};
+
+#define TCA_NETEM_MAX  TCA_NETEM_DELAY_DIST
+
 struct tc_netem_qopt
 {
        __u32   latency;        /* added delay (us) */
@@ -411,4 +421,19 @@
        __u32   duplicate;      /* random packet dup  (0=none ~0=100%) */
        __u32   jitter;         /* random jitter in latency (us) */
 };
+
+struct tc_netem_corr
+{
+       __u32   delay_corr;     /* delay correlation */
+       __u32   loss_corr;      /* packet loss correlation */
+       __u32   dup_corr;       /* duplicate correlation  */
+};
+
+struct tc_netem_dist
+{
+       __u32   size;           /* table size */
+       __u32   factor;         /* table scaling factor */
+       __s16   data[0];        /* distribution table values */
+};
+
 #endif
diff -urN -X dontdiff linux-2.6/net/sched/sch_netem.c 
netem-2.6/net/sched/sch_netem.c
--- linux-2.6/net/sched/sch_netem.c     2004-08-09 08:51:37.000000000 -0700
+++ netem-2.6/net/sched/sch_netem.c     2004-08-27 12:05:09.254998768 -0700
@@ -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@xxxxxxxx>
  *             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;
@@ -39,6 +62,18 @@
        u32 counter;
        u32 gap;
        u32 jitter;
+       u32 duplicate;
+
+       struct crndstate {
+               unsigned long last;
+               unsigned long rho;
+       } delay_cor, loss_cor, dup_cor;
+
+       struct disttable {
+               u32  size;
+               u32  factor;
+               s16 table[0];
+       } *delay_dist;
 };
 
 /* Time stamp put into socket buffer control block */
@@ -46,576 +81,113 @@
        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.
+ */
+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.
  */
-#define TABLESIZE      2048
-#define TABLEFACTOR    8192
+static unsigned long get_crandom(struct crndstate *state)
+{
+       u64 value, rho;
+       unsigned long answer;
 
-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,
-};
+       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;
+}
 
 /* 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)
+static unsigned long tabledist(int mu, int sigma, 
+                              struct crndstate *state,
+                              const struct disttable *dist)
 {
-       int x;
-       int index;
-       int sigmamod, sigmadiv;
+       int t, x, factor;
+       unsigned long rnd;
 
        if (sigma == 0)
                return mu;
 
-       index = (net_random() & (TABLESIZE-1));
-       sigmamod = sigma%TABLEFACTOR;
-       sigmadiv = sigma/TABLEFACTOR;
-       x = sigmamod*disttable[index];
+       rnd = get_crandom(state);
+
+       /* default uniform distribution */
+       if (dist == NULL) 
+               return (rnd % (2*sigma)) - sigma + mu;
+
+       factor = dist->factor;
+       t = dist->table[rnd % dist->size];
 
+       x = (sigma % factor) * t;
        if (x >= 0)
-               x += TABLEFACTOR/2;
+               x += factor/2;
        else
-               x -= TABLEFACTOR/2;
+               x -= factor/2;
 
-       x /= TABLEFACTOR;
-       x += sigmadiv*disttable[index];
-       x += mu;
-       return x;
+       return (x + (sigma / factor) * t) / factor + 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)
+/* Put skb in the private delayed queue. */
+static int delay_skb(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;
+       
+       PSCHED_GET_TIME(now);
+       PSCHED_TADD2(now, tabledist(q->latency, q->jitter, 
+                                   &q->delay_cor, q->delay_dist),
+                    cb->time_to_send);
+       
+       /* Always queue at tail to keep packets in order */
+       if (likely(q->delayed.qlen < q->limit)) {
+               __skb_queue_tail(&q->delayed, skb);
+               sch->q.qlen++;
+               sch->stats.bytes += skb->len;
+               sch->stats.packets++;
+               return NET_XMIT_SUCCESS;
+       }
+
+       sch->stats.drops++;
+       kfree_skb(skb);
+       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()) {
+       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)
+                       delay_skb(sch, skb2);
+       }
 
        /* If doing simple delay then gap == 0 so all packets
         * go into the delayed holding queue
@@ -633,27 +205,8 @@
        }
        
        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 */
-       if (likely(q->delayed.qlen < q->limit)) {
-               __skb_queue_tail(&q->delayed, skb);
-               sch->q.qlen++;
-               sch->stats.bytes += skb->len;
-               sch->stats.packets++;
-               return 0;
-       }
-
-       sch->stats.drops++;
-       kfree_skb(skb);
-       return NET_XMIT_DROP;
+       return delay_skb(sch, skb);
 }
 
 /* Requeue packets but don't change time stamp */
@@ -752,39 +305,94 @@
        return ret;
 }
 
-static int netem_change(struct Qdisc *sch, struct rtattr *opt)
+static int get_dist_table(struct Qdisc *sch, const struct rtattr *attr)
 {
        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_dist *dist = RTA_DATA(attr);
+       struct disttable *d;
+       int i;
+
+       if (RTA_PAYLOAD(attr) < sizeof(*dist) ||
+           dist->factor < 2 || dist->factor > 1<<16 || dist->size > 65536)
+               return -EINVAL;
 
-       if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
+       d = kmalloc(sizeof(*d) + dist->size*sizeof(d->table[0]), GFP_KERNEL);
+       if (!d)
+               return -ENOMEM;
+
+       d->size = dist->size;
+       d->factor = dist->factor;
+       for (i = 0; i < dist->size; i++)
+               d->table[i] = dist->data[i];
+       
+       spin_lock_bh(&sch->dev->queue_lock);
+       d = xchg(&q->delay_dist, d);
+       spin_unlock_bh(&sch->dev->queue_lock);
+
+       kfree(d);
+       return 0;
+}
+
+static int get_correlation(struct Qdisc *sch, const struct rtattr *attr)
+{
+       struct netem_sched_data *q = qdisc_priv(sch);
+       const struct tc_netem_corr *c = RTA_DATA(attr);
+
+       if (RTA_PAYLOAD(attr) != sizeof(*c))
                return -EINVAL;
 
-       child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
-       if (!child)
+       init_crandom(&q->delay_cor, c->delay_corr);
+       init_crandom(&q->loss_cor, c->loss_corr);
+       init_crandom(&q->dup_cor, c->dup_corr);
+       return 0;
+}
+
+static int netem_change(struct Qdisc *sch, struct rtattr *opt)
+{
+       struct netem_sched_data *q = qdisc_priv(sch);
+       struct tc_netem_qopt *qopt;
+       int ret;
+       
+       if (opt == NULL || RTA_PAYLOAD(opt) < sizeof(*qopt))
                return -EINVAL;
 
-       ret = set_fifo_limit(child, qopt->limit);
+       qopt = RTA_DATA(opt);
+       ret = set_fifo_limit(q->qdisc, qopt->limit);
        if (ret) {
-               qdisc_destroy(child);
+               pr_debug("netem: can't set fifo limit\n");
                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->latency = qopt->latency;
+       q->jitter = qopt->jitter;
+       q->limit = qopt->limit;
+       q->gap = qopt->gap;
+       q->loss = qopt->loss;
+       q->duplicate = qopt->duplicate;
+
+       /* Handle nested options after initial queue options.
+        * Should have put all options in nested format but too late now.
+        */ 
+       if (RTA_PAYLOAD(opt) > sizeof(*qopt)) {
+               struct rtattr *tb[TCA_NETEM_MAX];
+               if (rtattr_parse(tb, TCA_NETEM_MAX, 
+                                RTA_DATA(opt) + sizeof(*qopt),
+                                RTA_PAYLOAD(opt) - sizeof(*qopt)))
+                       return -EINVAL;
+
+               if (tb[TCA_NETEM_CORR-1]) {
+                       ret = get_correlation(sch, tb[TCA_NETEM_CORR-1]);
+                       if (ret)
+                               return ret;
+               }
+
+               if (tb[TCA_NETEM_DELAY_DIST-1]) {
+                       ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST-1]);
+                       if (ret)
+                               return ret;
+               }
        }
-       sch_tree_unlock(sch);
+
 
        return 0;
 }
@@ -792,19 +400,29 @@
 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
 {
        struct netem_sched_data *q = qdisc_priv(sch);
+       int ret;
 
        if (!opt)
                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;
+       }
+
+       ret = netem_change(sch, opt);
+       if (ret) {
+               pr_debug("netem: change failed\n");
+               qdisc_destroy(q->qdisc);
+       }
+       return ret;
 }
 
 static void netem_destroy(struct Qdisc *sch)
@@ -817,18 +435,26 @@
 
 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 rtattr *rta = (struct rtattr *) b;
        struct tc_netem_qopt qopt;
+       struct tc_netem_corr cor;
 
        qopt.latency = q->latency;
        qopt.jitter = q->jitter;
        qopt.limit = q->limit;
        qopt.loss = q->loss;
        qopt.gap = q->gap;
-
+       qopt.duplicate = q->duplicate;
        RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 
+       cor.delay_corr = q->delay_cor.rho;
+       cor.loss_corr = q->loss_cor.rho;
+       cor.dup_corr = q->dup_cor.rho;
+       RTA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor);
+       rta->rta_len = skb->tail - b;
+
        return skb->len;
 
 rtattr_failure:

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