net/sched/sch_netem.c

   1 /*
   2  * net/sched/sch_netem.c        Network emulator
   3  *
   4  *              This program is free software; you can redistribute it and/or
   5  *              modify it under the terms of the GNU General Public License
   6  *              as published by the Free Software Foundation; either version
   7  *              2 of the License, or (at your option) any later version.
   8  *
   9  * Authors:     Stephen Hemminger <shemminger@osdl.org>
  10  *              Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
  11  */
  12
  13 #include <linux/config.h>
  14 #include <linux/module.h>
  15 #include <asm/bitops.h>
  16 #include <linux/types.h>
  17 #include <linux/kernel.h>
  18 #include <linux/errno.h>
  19 #include <linux/netdevice.h>
  20 #include <linux/skbuff.h>
  21 #include <linux/rtnetlink.h>
  22
  23 #include <net/pkt_sched.h>
  24
  25 /*      Network emulator
  26  *
  27  *      This scheduler can alters spacing and order
  28  *      Similar to NISTnet and BSD Dummynet.
  29  */
  30
  31 struct netem_sched_data {
  32         struct Qdisc    *qdisc;
  33         struct sk_buff_head delayed;
  34         struct timer_list timer;
  35
  36         u32 latency;
  37         u32 loss;
  38         u32 limit;
  39         u32 counter;
  40         u32 gap;
  41         u32 jitter;
  42 };
  43
  44 /* Time stamp put into socket buffer control block */
  45 struct netem_skb_cb {
  46         psched_time_t   time_to_send;
  47 };
  48
  49 /* This is the distribution table for the normal distribution produced
  50  * with NISTnet tools.
  51  * The entries represent a scaled inverse of the cumulative distribution
  52  * function.
  53  */
  54 #define TABLESIZE       2048
  55 #define TABLEFACTOR     8192
  56
  57 static const short disttable[TABLESIZE] = {
  58         -31473,         -26739,         -25226,         -24269,
  59         -23560,         -22993,         -22518,         -22109,
  60         -21749,         -21426,         -21133,         -20865,
  61         -20618,         -20389,         -20174,         -19972,
  62         -19782,         -19601,         -19430,         -19267,
  63         -19112,         -18962,         -18819,         -18681,
  64         -18549,         -18421,         -18298,         -18178,
  65         -18062,         -17950,         -17841,         -17735,
  66         -17632,         -17532,         -17434,         -17339,
  67         -17245,         -17155,         -17066,         -16979,
  68         -16894,         -16811,         -16729,         -16649,
  69         -16571,         -16494,         -16419,         -16345,
  70         -16272,         -16201,         -16130,         -16061,
  71         -15993,         -15926,         -15861,         -15796,
  72         -15732,         -15669,         -15607,         -15546,
  73         -15486,         -15426,         -15368,         -15310,
  74         -15253,         -15196,         -15140,         -15086,
  75         -15031,         -14977,         -14925,         -14872,
  76         -14821,         -14769,         -14719,         -14669,
  77         -14619,         -14570,         -14522,         -14473,
  78         -14426,         -14379,         -14332,         -14286,
  79         -14241,         -14196,         -14150,         -14106,
  80         -14062,         -14019,         -13976,         -13933,
  81         -13890,         -13848,         -13807,         -13765,
  82         -13724,         -13684,         -13643,         -13604,
  83         -13564,         -13525,         -13486,         -13447,
  84         -13408,         -13370,         -13332,         -13295,
  85         -13258,         -13221,         -13184,         -13147,
  86         -13111,         -13075,         -13040,         -13004,
  87         -12969,         -12934,         -12899,         -12865,
  88         -12830,         -12796,         -12762,         -12729,
  89         -12695,         -12662,         -12629,         -12596,
  90         -12564,         -12531,         -12499,         -12467,
  91         -12435,         -12404,         -12372,         -12341,
  92         -12310,         -12279,         -12248,         -12218,
  93         -12187,         -12157,         -12127,         -12097,
  94         -12067,         -12038,         -12008,         -11979,
  95         -11950,         -11921,         -11892,         -11863,
  96         -11835,         -11806,         -11778,         -11750,
  97         -11722,         -11694,         -11666,         -11639,
  98         -11611,         -11584,         -11557,         -11530,
  99         -11503,         -11476,         -11450,         -11423,
 100         -11396,         -11370,         -11344,         -11318,
 101         -11292,         -11266,         -11240,         -11214,
 102         -11189,         -11164,         -11138,         -11113,
 103         -11088,         -11063,         -11038,         -11013,
 104         -10988,         -10964,         -10939,         -10915,
 105         -10891,         -10866,         -10843,         -10818,
 106         -10794,         -10770,         -10747,         -10723,
 107         -10700,         -10676,         -10652,         -10630,
 108         -10606,         -10583,         -10560,         -10537,
 109         -10514,         -10491,         -10469,         -10446,
 110         -10424,         -10401,         -10378,         -10356,
 111         -10334,         -10312,         -10290,         -10267,
 112         -10246,         -10224,         -10202,         -10180,
 113         -10158,         -10137,         -10115,         -10094,
 114         -10072,         -10051,         -10030,         -10009,
 115         -9988,          -9967,          -9945,          -9925,
 116         -9904,          -9883,          -9862,          -9842,
 117         -9821,          -9800,          -9780,          -9760,
 118         -9739,          -9719,          -9699,          -9678,
 119         -9658,          -9638,          -9618,          -9599,
 120         -9578,          -9559,          -9539,          -9519,
 121         -9499,          -9480,          -9461,          -9441,
 122         -9422,          -9402,          -9383,          -9363,
 123         -9344,          -9325,          -9306,          -9287,
 124         -9268,          -9249,          -9230,          -9211,
 125         -9192,          -9173,          -9155,          -9136,
 126         -9117,          -9098,          -9080,          -9062,
 127         -9043,          -9025,          -9006,          -8988,
 128         -8970,          -8951,          -8933,          -8915,
 129         -8897,          -8879,          -8861,          -8843,
 130         -8825,          -8807,          -8789,          -8772,
 131         -8754,          -8736,          -8718,          -8701,
 132         -8683,          -8665,          -8648,          -8630,
 133         -8613,          -8595,          -8578,          -8561,
 134         -8543,          -8526,          -8509,          -8492,
 135         -8475,          -8458,          -8441,          -8423,
 136         -8407,          -8390,          -8373,          -8356,
 137         -8339,          -8322,          -8305,          -8289,
 138         -8272,          -8255,          -8239,          -8222,
 139         -8206,          -8189,          -8172,          -8156,
 140         -8140,          -8123,          -8107,          -8090,
 141         -8074,          -8058,          -8042,          -8025,
 142         -8009,          -7993,          -7977,          -7961,
 143         -7945,          -7929,          -7913,          -7897,
 144         -7881,          -7865,          -7849,          -7833,
 145         -7817,          -7802,          -7786,          -7770,
 146         -7754,          -7739,          -7723,          -7707,
 147         -7692,          -7676,          -7661,          -7645,
 148         -7630,          -7614,          -7599,          -7583,
 149         -7568,          -7553,          -7537,          -7522,
 150         -7507,          -7492,          -7476,          -7461,
 151         -7446,          -7431,          -7416,          -7401,
 152         -7385,          -7370,          -7356,          -7340,
 153         -7325,          -7311,          -7296,          -7281,
 154         -7266,          -7251,          -7236,          -7221,
 155         -7207,          -7192,          -7177,          -7162,
 156         -7148,          -7133,          -7118,          -7104,
 157         -7089,          -7075,          -7060,          -7046,
 158         -7031,          -7016,          -7002,          -6988,
 159         -6973,          -6959,          -6944,          -6930,
 160         -6916,          -6901,          -6887,          -6873,
 161         -6859,          -6844,          -6830,          -6816,
 162         -6802,          -6788,          -6774,          -6760,
 163         -6746,          -6731,          -6717,          -6704,
 164         -6690,          -6675,          -6661,          -6647,
 165         -6633,          -6620,          -6606,          -6592,
 166         -6578,          -6564,          -6550,          -6537,
 167         -6523,          -6509,          -6495,          -6482,
 168         -6468,          -6454,          -6441,          -6427,
 169         -6413,          -6400,          -6386,          -6373,
 170         -6359,          -6346,          -6332,          -6318,
 171         -6305,          -6291,          -6278,          -6264,
 172         -6251,          -6238,          -6224,          -6211,
 173         -6198,          -6184,          -6171,          -6158,
 174         -6144,          -6131,          -6118,          -6105,
 175         -6091,          -6078,          -6065,          -6052,
 176         -6039,          -6025,          -6012,          -5999,
 177         -5986,          -5973,          -5960,          -5947,
 178         -5934,          -5921,          -5908,          -5895,
 179         -5882,          -5869,          -5856,          -5843,
 180         -5830,          -5817,          -5804,          -5791,
 181         -5779,          -5766,          -5753,          -5740,
 182         -5727,          -5714,          -5702,          -5689,
 183         -5676,          -5663,          -5650,          -5638,
 184         -5625,          -5612,          -5600,          -5587,
 185         -5575,          -5562,          -5549,          -5537,
 186         -5524,          -5512,          -5499,          -5486,
 187         -5474,          -5461,          -5449,          -5436,
 188         -5424,          -5411,          -5399,          -5386,
 189         -5374,          -5362,          -5349,          -5337,
 190         -5324,          -5312,          -5299,          -5287,
 191         -5275,          -5263,          -5250,          -5238,
 192         -5226,          -5213,          -5201,          -5189,
 193         -5177,          -5164,          -5152,          -5140,
 194         -5128,          -5115,          -5103,          -5091,
 195         -5079,          -5067,          -5055,          -5043,
 196         -5030,          -5018,          -5006,          -4994,
 197         -4982,          -4970,          -4958,          -4946,
 198         -4934,          -4922,          -4910,          -4898,
 199         -4886,          -4874,          -4862,          -4850,
 200         -4838,          -4826,          -4814,          -4803,
 201         -4791,          -4778,          -4767,          -4755,
 202         -4743,          -4731,          -4719,          -4708,
 203         -4696,          -4684,          -4672,          -4660,
 204         -4649,          -4637,          -4625,          -4613,
 205         -4601,          -4590,          -4578,          -4566,
 206         -4554,          -4543,          -4531,          -4520,
 207         -4508,          -4496,          -4484,          -4473,
 208         -4461,          -4449,          -4438,          -4427,
 209         -4415,          -4403,          -4392,          -4380,
 210         -4368,          -4357,          -4345,          -4334,
 211         -4322,          -4311,          -4299,          -4288,
 212         -4276,          -4265,          -4253,          -4242,
 213         -4230,          -4219,          -4207,          -4196,
 214         -4184,          -4173,          -4162,          -4150,
 215         -4139,          -4128,          -4116,          -4105,
 216         -4094,          -4082,          -4071,          -4060,
 217         -4048,          -4037,          -4026,          -4014,
 218         -4003,          -3992,          -3980,          -3969,
 219         -3958,          -3946,          -3935,          -3924,
 220         -3913,          -3901,          -3890,          -3879,
 221         -3868,          -3857,          -3845,          -3834,
 222         -3823,          -3812,          -3801,          -3790,
 223         -3779,          -3767,          -3756,          -3745,
 224         -3734,          -3723,          -3712,          -3700,
 225         -3689,          -3678,          -3667,          -3656,
 226         -3645,          -3634,          -3623,          -3612,
 227         -3601,          -3590,          -3579,          -3568,
 228         -3557,          -3545,          -3535,          -3524,
 229         -3513,          -3502,          -3491,          -3480,
 230         -3469,          -3458,          -3447,          -3436,
 231         -3425,          -3414,          -3403,          -3392,
 232         -3381,          -3370,          -3360,          -3348,
 233         -3337,          -3327,          -3316,          -3305,
 234         -3294,          -3283,          -3272,          -3262,
 235         -3251,          -3240,          -3229,          -3218,
 236         -3207,          -3197,          -3185,          -3175,
 237         -3164,          -3153,          -3142,          -3132,
 238         -3121,          -3110,          -3099,          -3088,
 239         -3078,          -3067,          -3056,          -3045,
 240         -3035,          -3024,          -3013,          -3003,
 241         -2992,          -2981,          -2970,          -2960,
 242         -2949,          -2938,          -2928,          -2917,
 243         -2906,          -2895,          -2885,          -2874,
 244         -2864,          -2853,          -2842,          -2832,
 245         -2821,          -2810,          -2800,          -2789,
 246         -2778,          -2768,          -2757,          -2747,
 247         -2736,          -2725,          -2715,          -2704,
 248         -2694,          -2683,          -2673,          -2662,
 249         -2651,          -2641,          -2630,          -2620,
 250         -2609,          -2599,          -2588,          -2578,
 251         -2567,          -2556,          -2546,          -2535,
 252         -2525,          -2515,          -2504,          -2493,
 253         -2483,          -2472,          -2462,          -2451,
 254         -2441,          -2431,          -2420,          -2410,
 255         -2399,          -2389,          -2378,          -2367,
 256         -2357,          -2347,          -2336,          -2326,
 257         -2315,          -2305,          -2295,          -2284,
 258         -2274,          -2263,          -2253,          -2243,
 259         -2232,          -2222,          -2211,          -2201,
 260         -2191,          -2180,          -2170,          -2159,
 261         -2149,          -2139,          -2128,          -2118,
 262         -2107,          -2097,          -2087,          -2076,
 263         -2066,          -2056,          -2046,          -2035,
 264         -2025,          -2014,          -2004,          -1994,
 265         -1983,          -1973,          -1963,          -1953,
 266         -1942,          -1932,          -1921,          -1911,
 267         -1901,          -1891,          -1880,          -1870,
 268         -1860,          -1849,          -1839,          -1829,
 269         -1819,          -1808,          -1798,          -1788,
 270         -1778,          -1767,          -1757,          -1747,
 271         -1736,          -1726,          -1716,          -1706,
 272         -1695,          -1685,          -1675,          -1665,
 273         -1654,          -1644,          -1634,          -1624,
 274         -1613,          -1603,          -1593,          -1583,
 275         -1573,          -1563,          -1552,          -1542,
 276         -1532,          -1522,          -1511,          -1501,
 277         -1491,          -1481,          -1471,          -1461,
 278         -1450,          -1440,          -1430,          -1420,
 279         -1409,          -1400,          -1389,          -1379,
 280         -1369,          -1359,          -1348,          -1339,
 281         -1328,          -1318,          -1308,          -1298,
 282         -1288,          -1278,          -1267,          -1257,
 283         -1247,          -1237,          -1227,          -1217,
 284         -1207,          -1196,          -1186,          -1176,
 285         -1166,          -1156,          -1146,          -1135,
 286         -1126,          -1115,          -1105,          -1095,
 287         -1085,          -1075,          -1065,          -1055,
 288         -1044,          -1034,          -1024,          -1014,
 289         -1004,          -994,           -984,           -974,
 290         -964,           -954,           -944,           -933,
 291         -923,           -913,           -903,           -893,
 292         -883,           -873,           -863,           -853,
 293         -843,           -833,           -822,           -812,
 294         -802,           -792,           -782,           -772,
 295         -762,           -752,           -742,           -732,
 296         -722,           -712,           -702,           -691,
 297         -682,           -671,           -662,           -651,
 298         -641,           -631,           -621,           -611,
 299         -601,           -591,           -581,           -571,
 300         -561,           -551,           -541,           -531,
 301         -521,           -511,           -501,           -491,
 302         -480,           -471,           -460,           -451,
 303         -440,           -430,           -420,           -410,
 304         -400,           -390,           -380,           -370,
 305         -360,           -350,           -340,           -330,
 306         -320,           -310,           -300,           -290,
 307         -280,           -270,           -260,           -250,
 308         -240,           -230,           -220,           -210,
 309         -199,           -190,           -179,           -170,
 310         -159,           -150,           -139,           -129,
 311         -119,           -109,           -99,            -89,
 312         -79,            -69,            -59,            -49,
 313         -39,            -29,            -19,            -9,
 314         1,              11,             21,             31,
 315         41,             51,             61,             71,
 316         81,             91,             101,            111,
 317         121,            131,            141,            152,
 318         161,            172,            181,            192,
 319         202,            212,            222,            232,
 320         242,            252,            262,            272,
 321         282,            292,            302,            312,
 322         322,            332,            342,            352,
 323         362,            372,            382,            392,
 324         402,            412,            422,            433,
 325         442,            453,            462,            473,
 326         483,            493,            503,            513,
 327         523,            533,            543,            553,
 328         563,            573,            583,            593,
 329         603,            613,            623,            633,
 330         643,            653,            664,            673,
 331         684,            694,            704,            714,
 332         724,            734,            744,            754,
 333         764,            774,            784,            794,
 334         804,            815,            825,            835,
 335         845,            855,            865,            875,
 336         885,            895,            905,            915,
 337         925,            936,            946,            956,
 338         966,            976,            986,            996,
 339         1006,           1016,           1026,           1037,
 340         1047,           1057,           1067,           1077,
 341         1087,           1097,           1107,           1117,
 342         1128,           1138,           1148,           1158,
 343         1168,           1178,           1188,           1198,
 344         1209,           1219,           1229,           1239,
 345         1249,           1259,           1269,           1280,
 346         1290,           1300,           1310,           1320,
 347         1330,           1341,           1351,           1361,
 348         1371,           1381,           1391,           1402,
 349         1412,           1422,           1432,           1442,
 350         1452,           1463,           1473,           1483,
 351         1493,           1503,           1513,           1524,
 352         1534,           1544,           1554,           1565,
 353         1575,           1585,           1595,           1606,
 354         1616,           1626,           1636,           1647,
 355         1656,           1667,           1677,           1687,
 356         1697,           1708,           1718,           1729,
 357         1739,           1749,           1759,           1769,
 358         1780,           1790,           1800,           1810,
 359         1821,           1831,           1841,           1851,
 360         1862,           1872,           1883,           1893,
 361         1903,           1913,           1923,           1934,
 362         1944,           1955,           1965,           1975,
 363         1985,           1996,           2006,           2016,
 364         2027,           2037,           2048,           2058,
 365         2068,           2079,           2089,           2099,
 366         2110,           2120,           2130,           2141,
 367         2151,           2161,           2172,           2182,
 368         2193,           2203,           2213,           2224,
 369         2234,           2245,           2255,           2265,
 370         2276,           2286,           2297,           2307,
 371         2318,           2328,           2338,           2349,
 372         2359,           2370,           2380,           2391,
 373         2401,           2412,           2422,           2433,
 374         2443,           2454,           2464,           2475,
 375         2485,           2496,           2506,           2517,
 376         2527,           2537,           2548,           2559,
 377         2569,           2580,           2590,           2601,
 378         2612,           2622,           2632,           2643,
 379         2654,           2664,           2675,           2685,
 380         2696,           2707,           2717,           2728,
 381         2738,           2749,           2759,           2770,
 382         2781,           2791,           2802,           2813,
 383         2823,           2834,           2845,           2855,
 384         2866,           2877,           2887,           2898,
 385         2909,           2919,           2930,           2941,
 386         2951,           2962,           2973,           2984,
 387         2994,           3005,           3015,           3027,
 388         3037,           3048,           3058,           3069,
 389         3080,           3091,           3101,           3113,
 390         3123,           3134,           3145,           3156,
 391         3166,           3177,           3188,           3199,
 392         3210,           3220,           3231,           3242,
 393         3253,           3264,           3275,           3285,
 394         3296,           3307,           3318,           3329,
 395         3340,           3351,           3362,           3373,
 396         3384,           3394,           3405,           3416,
 397         3427,           3438,           3449,           3460,
 398         3471,           3482,           3493,           3504,
 399         3515,           3526,           3537,           3548,
 400         3559,           3570,           3581,           3592,
 401         3603,           3614,           3625,           3636,
 402         3647,           3659,           3670,           3681,
 403         3692,           3703,           3714,           3725,
 404         3736,           3747,           3758,           3770,
 405         3781,           3792,           3803,           3814,
 406         3825,           3837,           3848,           3859,
 407         3870,           3881,           3893,           3904,
 408         3915,           3926,           3937,           3949,
 409         3960,           3971,           3983,           3994,
 410         4005,           4017,           4028,           4039,
 411         4051,           4062,           4073,           4085,
 412         4096,           4107,           4119,           4130,
 413         4141,           4153,           4164,           4175,
 414         4187,           4198,           4210,           4221,
 415         4233,           4244,           4256,           4267,
 416         4279,           4290,           4302,           4313,
 417         4325,           4336,           4348,           4359,
 418         4371,           4382,           4394,           4406,
 419         4417,           4429,           4440,           4452,
 420         4464,           4475,           4487,           4499,
 421         4510,           4522,           4533,           4545,
 422         4557,           4569,           4581,           4592,
 423         4604,           4616,           4627,           4639,
 424         4651,           4663,           4674,           4686,
 425         4698,           4710,           4722,           4734,
 426         4746,           4758,           4769,           4781,
 427         4793,           4805,           4817,           4829,
 428         4841,           4853,           4865,           4877,
 429         4889,           4900,           4913,           4925,
 430         4936,           4949,           4961,           4973,
 431         4985,           4997,           5009,           5021,
 432         5033,           5045,           5057,           5070,
 433         5081,           5094,           5106,           5118,
 434         5130,           5143,           5155,           5167,
 435         5179,           5191,           5204,           5216,
 436         5228,           5240,           5253,           5265,
 437         5278,           5290,           5302,           5315,
 438         5327,           5340,           5352,           5364,
 439         5377,           5389,           5401,           5414,
 440         5426,           5439,           5451,           5464,
 441         5476,           5489,           5502,           5514,
 442         5527,           5539,           5552,           5564,
 443         5577,           5590,           5603,           5615,
 444         5628,           5641,           5653,           5666,
 445         5679,           5691,           5704,           5717,
 446         5730,           5743,           5756,           5768,
 447         5781,           5794,           5807,           5820,
 448         5833,           5846,           5859,           5872,
 449         5885,           5897,           5911,           5924,
 450         5937,           5950,           5963,           5976,
 451         5989,           6002,           6015,           6028,
 452         6042,           6055,           6068,           6081,
 453         6094,           6108,           6121,           6134,
 454         6147,           6160,           6174,           6187,
 455         6201,           6214,           6227,           6241,
 456         6254,           6267,           6281,           6294,
 457         6308,           6321,           6335,           6348,
 458         6362,           6375,           6389,           6403,
 459         6416,           6430,           6443,           6457,
 460         6471,           6485,           6498,           6512,
 461         6526,           6540,           6554,           6567,
 462         6581,           6595,           6609,           6623,
 463         6637,           6651,           6665,           6679,
 464         6692,           6706,           6721,           6735,
 465         6749,           6763,           6777,           6791,
 466         6805,           6819,           6833,           6848,
 467         6862,           6876,           6890,           6905,
 468         6919,           6933,           6948,           6962,
 469         6976,           6991,           7005,           7020,
 470         7034,           7049,           7064,           7078,
 471         7093,           7107,           7122,           7136,
 472         7151,           7166,           7180,           7195,
 473         7210,           7225,           7240,           7254,
 474         7269,           7284,           7299,           7314,
 475         7329,           7344,           7359,           7374,
 476         7389,           7404,           7419,           7434,
 477         7449,           7465,           7480,           7495,
 478         7510,           7526,           7541,           7556,
 479         7571,           7587,           7602,           7618,
 480         7633,           7648,           7664,           7680,
 481         7695,           7711,           7726,           7742,
 482         7758,           7773,           7789,           7805,
 483         7821,           7836,           7852,           7868,
 484         7884,           7900,           7916,           7932,
 485         7948,           7964,           7981,           7997,
 486         8013,           8029,           8045,           8061,
 487         8078,           8094,           8110,           8127,
 488         8143,           8160,           8176,           8193,
 489         8209,           8226,           8242,           8259,
 490         8276,           8292,           8309,           8326,
 491         8343,           8360,           8377,           8394,
 492         8410,           8428,           8444,           8462,
 493         8479,           8496,           8513,           8530,
 494         8548,           8565,           8582,           8600,
 495         8617,           8634,           8652,           8670,
 496         8687,           8704,           8722,           8740,
 497         8758,           8775,           8793,           8811,
 498         8829,           8847,           8865,           8883,
 499         8901,           8919,           8937,           8955,
 500         8974,           8992,           9010,           9029,
 501         9047,           9066,           9084,           9103,
 502         9121,           9140,           9159,           9177,
 503         9196,           9215,           9234,           9253,
 504         9272,           9291,           9310,           9329,
 505         9349,           9368,           9387,           9406,
 506         9426,           9445,           9465,           9484,
 507         9504,           9524,           9544,           9563,
 508         9583,           9603,           9623,           9643,
 509         9663,           9683,           9703,           9723,
 510         9744,           9764,           9785,           9805,
 511         9826,           9846,           9867,           9888,
 512         9909,           9930,           9950,           9971,
 513         9993,           10013,          10035,          10056,
 514         10077,          10099,          10120,          10142,
 515         10163,          10185,          10207,          10229,
 516         10251,          10273,          10294,          10317,
 517         10339,          10361,          10384,          10406,
 518         10428,          10451,          10474,          10496,
 519         10519,          10542,          10565,          10588,
 520         10612,          10635,          10658,          10682,
 521         10705,          10729,          10752,          10776,
 522         10800,          10824,          10848,          10872,
 523         10896,          10921,          10945,          10969,
 524         10994,          11019,          11044,          11069,
 525         11094,          11119,          11144,          11169,
 526         11195,          11221,          11246,          11272,
 527         11298,          11324,          11350,          11376,
 528         11402,          11429,          11456,          11482,
 529         11509,          11536,          11563,          11590,
 530         11618,          11645,          11673,          11701,
 531         11728,          11756,          11785,          11813,
 532         11842,          11870,          11899,          11928,
 533         11957,          11986,          12015,          12045,
 534         12074,          12104,          12134,          12164,
 535         12194,          12225,          12255,          12286,
 536         12317,          12348,          12380,          12411,
 537         12443,          12475,          12507,          12539,
 538         12571,          12604,          12637,          12670,
 539         12703,          12737,          12771,          12804,
 540         12839,          12873,          12907,          12942,
 541         12977,          13013,          13048,          13084,
 542         13120,          13156,          13192,          13229,
 543         13267,          13304,          13341,          13379,
 544         13418,          13456,          13495,          13534,
 545         13573,          13613,          13653,          13693,
 546         13734,          13775,          13817,          13858,
 547         13901,          13943,          13986,          14029,
 548         14073,          14117,          14162,          14206,
 549         14252,          14297,          14343,          14390,
 550         14437,          14485,          14533,          14582,
 551         14631,          14680,          14731,          14782,
 552         14833,          14885,          14937,          14991,
 553         15044,          15099,          15154,          15210,
 554         15266,          15324,          15382,          15441,
 555         15500,          15561,          15622,          15684,
 556         15747,          15811,          15877,          15943,
 557         16010,          16078,          16148,          16218,
 558         16290,          16363,          16437,          16513,
 559         16590,          16669,          16749,          16831,
 560         16915,          17000,          17088,          17177,
 561         17268,          17362,          17458,          17556,
 562         17657,          17761,          17868,          17977,
 563         18090,          18207,          18328,          18452,
 564         18581,          18715,          18854,          18998,
 565         19149,          19307,          19472,          19645,
 566         19828,          20021,          20226,          20444,
 567         20678,          20930,          21204,          21503,
 568         21835,          22206,          22630,          23124,
 569         23721,          24478,          25529,          27316,
 570 };
 571
 572 /* tabledist - return a pseudo-randomly distributed value with mean mu and
 573  * std deviation sigma.  Uses table lookup to approximate the desired
 574  * distribution, and a uniformly-distributed pseudo-random source.
 575  */
 576 static inline int tabledist(int mu, int sigma)
 577 {
 578         int x;
 579         int index;
 580         int sigmamod, sigmadiv;
 581
 582         if (sigma == 0)
 583                 return mu;
 584
 585         index = (net_random() & (TABLESIZE-1));
 586         sigmamod = sigma%TABLEFACTOR;
 587         sigmadiv = sigma/TABLEFACTOR;
 588         x = sigmamod*disttable[index];
 589
 590         if (x >= 0)
 591                 x += TABLEFACTOR/2;
 592         else
 593                 x -= TABLEFACTOR/2;
 594
 595         x /= TABLEFACTOR;
 596         x += sigmadiv*disttable[index];
 597         x += mu;
 598         return x;
 599 }
 600
 601 /* Enqueue packets with underlying discipline (fifo)
 602  * but mark them with current time first.
 603  */
 604 static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 605 {
 606         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 607         struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
 608         psched_time_t now;
 609         long delay;
 610
 611         pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
 612
 613         /* Random packet drop 0 => none, ~0 => all */
 614         if (q->loss && q->loss >= net_random()) {
 615                 sch->stats.drops++;
 616                 return 0;       /* lie about loss so TCP doesn't know */
 617         }
 618
 619
 620         /* If doing simple delay then gap == 0 so all packets
 621          * go into the delayed holding queue
 622          * otherwise if doing out of order only "1 out of gap"
 623          * packets will be delayed.
 624          */
 625         if (q->counter < q->gap) {
 626                 int ret;
 627
 628                 ++q->counter;
 629                 ret = q->qdisc->enqueue(skb, q->qdisc);
 630                 if (ret)
 631                         sch->stats.drops++;
 632                 return ret;
 633         }
 634
 635         q->counter = 0;
 636
 637         PSCHED_GET_TIME(now);
 638         if (q->jitter)
 639                 delay = tabledist(q->latency, q->jitter);
 640         else
 641                 delay = q->latency;
 642
 643         PSCHED_TADD2(now, delay, cb->time_to_send);
 644
 645         /* Always queue at tail to keep packets in order */
 646         __skb_queue_tail(&q->delayed, skb);
 647         sch->q.qlen++;
 648         sch->stats.bytes += skb->len;
 649         sch->stats.packets++;
 650         return 0;
 651 }
 652
 653 /* Requeue packets but don't change time stamp */
 654 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
 655 {
 656         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 657         int ret;
 658
 659         if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0)
 660                 sch->q.qlen++;
 661
 662         return ret;
 663 }
 664
 665 static unsigned int netem_drop(struct Qdisc* sch)
 666 {
 667         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 668         unsigned int len;
 669
 670         if ((len = q->qdisc->ops->drop(q->qdisc)) != 0) {
 671                 sch->q.qlen--;
 672                 sch->stats.drops++;
 673         }
 674         return len;
 675 }
 676
 677 /* Dequeue packet.
 678  *  Move all packets that are ready to send from the delay holding
 679  *  list to the underlying qdisc, then just call dequeue
 680  */
 681 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
 682 {
 683         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 684         struct sk_buff *skb;
 685         psched_time_t now;
 686
 687         PSCHED_GET_TIME(now);
 688         while ((skb = skb_peek(&q->delayed)) != NULL) {
 689                 const struct netem_skb_cb *cb
 690                         = (const struct netem_skb_cb *)skb->cb;
 691                 long delay
 692                         = PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now));
 693                 pr_debug("netem_dequeue: delay queue %p@%lu %ld\n",
 694                          skb, jiffies, delay);
 695
 696                 /* if more time remaining? */
 697                 if (delay > 0) {
 698                         mod_timer(&q->timer, jiffies + delay);
 699                         break;
 700                 }
 701                 __skb_unlink(skb, &q->delayed);
 702
 703                 if (q->qdisc->enqueue(skb, q->qdisc))
 704                         sch->stats.drops++;
 705         }
 706
 707         skb = q->qdisc->dequeue(q->qdisc);
 708         if (skb)
 709                 sch->q.qlen--;
 710         return skb;
 711 }
 712
 713 static void netem_watchdog(unsigned long arg)
 714 {
 715         struct Qdisc *sch = (struct Qdisc *)arg;
 716
 717         pr_debug("netem_watchdog: fired @%lu\n", jiffies);
 718         netif_schedule(sch->dev);
 719 }
 720
 721 static void netem_reset(struct Qdisc *sch)
 722 {
 723         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 724
 725         qdisc_reset(q->qdisc);
 726         skb_queue_purge(&q->delayed);
 727
 728         sch->q.qlen = 0;
 729         del_timer_sync(&q->timer);
 730 }
 731
 732 static int set_fifo_limit(struct Qdisc *q, int limit)
 733 {
 734         struct rtattr *rta;
 735         int ret = -ENOMEM;
 736
 737         rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
 738         if (rta) {
 739                 rta->rta_type = RTM_NEWQDISC;
 740                 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
 741                 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
 742
 743                 ret = q->ops->change(q, rta);
 744                 kfree(rta);
 745         }
 746         return ret;
 747 }
 748
 749 static int netem_change(struct Qdisc *sch, struct rtattr *opt)
 750 {
 751         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 752         struct tc_netem_qopt *qopt = RTA_DATA(opt);
 753         struct Qdisc *child;
 754         int ret;
 755
 756         if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
 757                 return -EINVAL;
 758
 759         child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
 760         if (!child)
 761                 return -EINVAL;
 762
 763         ret = set_fifo_limit(child, qopt->limit);
 764         if (ret) {
 765                 qdisc_destroy(child);
 766                 return ret;
 767         }
 768
 769         sch_tree_lock(sch);
 770         if (child) {
 771                 child = xchg(&q->qdisc, child);
 772                 if (child != &noop_qdisc)
 773                         qdisc_destroy(child);
 774
 775                 q->latency = qopt->latency;
 776                 q->jitter = qopt->jitter;
 777                 q->limit = qopt->limit;
 778                 q->gap = qopt->gap;
 779                 q->loss = qopt->loss;
 780         }
 781         sch_tree_unlock(sch);
 782
 783         return 0;
 784 }
 785
 786 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
 787 {
 788         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 789
 790         if (!opt)
 791                 return -EINVAL;
 792
 793         skb_queue_head_init(&q->delayed);
 794         q->qdisc = &noop_qdisc;
 795
 796         init_timer(&q->timer);
 797         q->timer.function = netem_watchdog;
 798         q->timer.data = (unsigned long) sch;
 799         q->counter = 0;
 800
 801         return netem_change(sch, opt);
 802 }
 803
 804 static void netem_destroy(struct Qdisc *sch)
 805 {
 806         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 807
 808         del_timer_sync(&q->timer);
 809 }
 810
 811 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
 812 {
 813         struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 814         unsigned char    *b = skb->tail;
 815         struct tc_netem_qopt qopt;
 816
 817         qopt.latency = q->latency;
 818         qopt.jitter = q->jitter;
 819         qopt.limit = sch->dev->tx_queue_len;
 820         qopt.loss = q->loss;
 821         qopt.gap = q->gap;
 822
 823         RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 824
 825         return skb->len;
 826
 827 rtattr_failure:
 828         skb_trim(skb, b - skb->data);
 829         return -1;
 830 }
 831
 832 static struct Qdisc_ops netem_qdisc_ops = {
 833         .id             =       "netem",
 834         .priv_size      =       sizeof(struct netem_sched_data),
 835         .enqueue        =       netem_enqueue,
 836         .dequeue        =       netem_dequeue,
 837         .requeue        =       netem_requeue,
 838         .drop           =       netem_drop,
 839         .init           =       netem_init,
 840         .reset          =       netem_reset,
 841         .destroy        =       netem_destroy,
 842         .change         =       netem_change,
 843         .dump           =       netem_dump,
 844         .owner          =       THIS_MODULE,
 845 };
 846
 847
 848 static int __init netem_module_init(void)
 849 {
 850         return register_qdisc(&netem_qdisc_ops);
 851 }
 852 static void __exit netem_module_exit(void)
 853 {
 854         unregister_qdisc(&netem_qdisc_ops);
 855 }
 856 module_init(netem_module_init)
 857 module_exit(netem_module_exit)
 858 MODULE_LICENSE("GPL");