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 = qdisc_priv(sch);
 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         if (likely(q->delayed.qlen < q->limit)) {
 647                 __skb_queue_tail(&q->delayed, skb);
 648                 sch->q.qlen++;
 649                 sch->stats.bytes += skb->len;
 650                 sch->stats.packets++;
 651                 return 0;
 652         }
 653
 654         sch->stats.drops++;
 655         kfree_skb(skb);
 656         return NET_XMIT_DROP;
 657 }
 658
 659 /* Requeue packets but don't change time stamp */
 660 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
 661 {
 662         struct netem_sched_data *q = qdisc_priv(sch);
 663         int ret;
 664
 665         if ((ret = q->qdisc->ops->requeue(skb, q->qdisc)) == 0)
 666                 sch->q.qlen++;
 667
 668         return ret;
 669 }
 670
 671 static unsigned int netem_drop(struct Qdisc* sch)
 672 {
 673         struct netem_sched_data *q = qdisc_priv(sch);
 674         unsigned int len;
 675
 676         if ((len = q->qdisc->ops->drop(q->qdisc)) != 0) {
 677                 sch->q.qlen--;
 678                 sch->stats.drops++;
 679         }
 680         return len;
 681 }
 682
 683 /* Dequeue packet.
 684  *  Move all packets that are ready to send from the delay holding
 685  *  list to the underlying qdisc, then just call dequeue
 686  */
 687 static struct sk_buff *netem_dequeue(struct Qdisc *sch)
 688 {
 689         struct netem_sched_data *q = qdisc_priv(sch);
 690         struct sk_buff *skb;
 691         psched_time_t now;
 692
 693         PSCHED_GET_TIME(now);
 694         while ((skb = skb_peek(&q->delayed)) != NULL) {
 695                 const struct netem_skb_cb *cb
 696                         = (const struct netem_skb_cb *)skb->cb;
 697                 long delay
 698                         = PSCHED_US2JIFFIE(PSCHED_TDIFF(cb->time_to_send, now));
 699                 pr_debug("netem_dequeue: delay queue %p@%lu %ld\n",
 700                          skb, jiffies, delay);
 701
 702                 /* if more time remaining? */
 703                 if (delay > 0) {
 704                         mod_timer(&q->timer, jiffies + delay);
 705                         break;
 706                 }
 707                 __skb_unlink(skb, &q->delayed);
 708
 709                 if (q->qdisc->enqueue(skb, q->qdisc))
 710                         sch->stats.drops++;
 711         }
 712
 713         skb = q->qdisc->dequeue(q->qdisc);
 714         if (skb)
 715                 sch->q.qlen--;
 716         return skb;
 717 }
 718
 719 static void netem_watchdog(unsigned long arg)
 720 {
 721         struct Qdisc *sch = (struct Qdisc *)arg;
 722
 723         pr_debug("netem_watchdog: fired @%lu\n", jiffies);
 724         netif_schedule(sch->dev);
 725 }
 726
 727 static void netem_reset(struct Qdisc *sch)
 728 {
 729         struct netem_sched_data *q = qdisc_priv(sch);
 730
 731         qdisc_reset(q->qdisc);
 732         skb_queue_purge(&q->delayed);
 733
 734         sch->q.qlen = 0;
 735         del_timer_sync(&q->timer);
 736 }
 737
 738 static int set_fifo_limit(struct Qdisc *q, int limit)
 739 {
 740         struct rtattr *rta;
 741         int ret = -ENOMEM;
 742
 743         rta = kmalloc(RTA_LENGTH(sizeof(struct tc_fifo_qopt)), GFP_KERNEL);
 744         if (rta) {
 745                 rta->rta_type = RTM_NEWQDISC;
 746                 rta->rta_len = RTA_LENGTH(sizeof(struct tc_fifo_qopt));
 747                 ((struct tc_fifo_qopt *)RTA_DATA(rta))->limit = limit;
 748
 749                 ret = q->ops->change(q, rta);
 750                 kfree(rta);
 751         }
 752         return ret;
 753 }
 754
 755 static int netem_change(struct Qdisc *sch, struct rtattr *opt)
 756 {
 757         struct netem_sched_data *q = qdisc_priv(sch);
 758         struct tc_netem_qopt *qopt = RTA_DATA(opt);
 759         struct Qdisc *child;
 760         int ret;
 761
 762         if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
 763                 return -EINVAL;
 764
 765         child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
 766         if (!child)
 767                 return -EINVAL;
 768
 769         ret = set_fifo_limit(child, qopt->limit);
 770         if (ret) {
 771                 qdisc_destroy(child);
 772                 return ret;
 773         }
 774
 775         sch_tree_lock(sch);
 776         if (child) {
 777                 child = xchg(&q->qdisc, child);
 778                 if (child != &noop_qdisc)
 779                         qdisc_destroy(child);
 780
 781                 q->latency = qopt->latency;
 782                 q->jitter = qopt->jitter;
 783                 q->limit = qopt->limit;
 784                 q->gap = qopt->gap;
 785                 q->loss = qopt->loss;
 786         }
 787         sch_tree_unlock(sch);
 788
 789         return 0;
 790 }
 791
 792 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
 793 {
 794         struct netem_sched_data *q = qdisc_priv(sch);
 795
 796         if (!opt)
 797                 return -EINVAL;
 798
 799         skb_queue_head_init(&q->delayed);
 800         q->qdisc = &noop_qdisc;
 801
 802         init_timer(&q->timer);
 803         q->timer.function = netem_watchdog;
 804         q->timer.data = (unsigned long) sch;
 805         q->counter = 0;
 806
 807         return netem_change(sch, opt);
 808 }
 809
 810 static void netem_destroy(struct Qdisc *sch)
 811 {
 812         struct netem_sched_data *q = qdisc_priv(sch);
 813
 814         del_timer_sync(&q->timer);
 815         qdisc_destroy(q->qdisc);
 816 }
 817
 818 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
 819 {
 820         struct netem_sched_data *q = qdisc_priv(sch);
 821         unsigned char    *b = skb->tail;
 822         struct tc_netem_qopt qopt;
 823
 824         qopt.latency = q->latency;
 825         qopt.jitter = q->jitter;
 826         qopt.limit = q->limit;
 827         qopt.loss = q->loss;
 828         qopt.gap = q->gap;
 829
 830         RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 831
 832         return skb->len;
 833
 834 rtattr_failure:
 835         skb_trim(skb, b - skb->data);
 836         return -1;
 837 }
 838
 839 static int netem_dump_class(struct Qdisc *sch, unsigned long cl,
 840                           struct sk_buff *skb, struct tcmsg *tcm)
 841 {
 842         struct netem_sched_data *q = qdisc_priv(sch);
 843
 844         if (cl != 1)    /* only one class */
 845                 return -ENOENT;
 846
 847         tcm->tcm_handle |= TC_H_MIN(1);
 848         tcm->tcm_info = q->qdisc->handle;
 849
 850         return 0;
 851 }
 852
 853 static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 854                      struct Qdisc **old)
 855 {
 856         struct netem_sched_data *q = qdisc_priv(sch);
 857
 858         if (new == NULL)
 859                 new = &noop_qdisc;
 860
 861         sch_tree_lock(sch);
 862         *old = xchg(&q->qdisc, new);
 863         qdisc_reset(*old);
 864         sch->q.qlen = 0;
 865         sch_tree_unlock(sch);
 866
 867         return 0;
 868 }
 869
 870 static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg)
 871 {
 872         struct netem_sched_data *q = qdisc_priv(sch);
 873         return q->qdisc;
 874 }
 875
 876 static unsigned long netem_get(struct Qdisc *sch, u32 classid)
 877 {
 878         return 1;
 879 }
 880
 881 static void netem_put(struct Qdisc *sch, unsigned long arg)
 882 {
 883 }
 884
 885 static int netem_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 886                             struct rtattr **tca, unsigned long *arg)
 887 {
 888         return -ENOSYS;
 889 }
 890
 891 static int netem_delete(struct Qdisc *sch, unsigned long arg)
 892 {
 893         return -ENOSYS;
 894 }
 895
 896 static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 897 {
 898         if (!walker->stop) {
 899                 if (walker->count >= walker->skip)
 900                         if (walker->fn(sch, 1, walker) < 0) {
 901                                 walker->stop = 1;
 902                                 return;
 903                         }
 904                 walker->count++;
 905         }
 906 }
 907
 908 static struct tcf_proto **netem_find_tcf(struct Qdisc *sch, unsigned long cl)
 909 {
 910         return NULL;
 911 }
 912
 913 static struct Qdisc_class_ops netem_class_ops = {
 914         .graft          =       netem_graft,
 915         .leaf           =       netem_leaf,
 916         .get            =       netem_get,
 917         .put            =       netem_put,
 918         .change         =       netem_change_class,
 919         .delete         =       netem_delete,
 920         .walk           =       netem_walk,
 921         .tcf_chain      =       netem_find_tcf,
 922         .dump           =       netem_dump_class,
 923 };
 924
 925 static struct Qdisc_ops netem_qdisc_ops = {
 926         .id             =       "netem",
 927         .cl_ops         =       &netem_class_ops,
 928         .priv_size      =       sizeof(struct netem_sched_data),
 929         .enqueue        =       netem_enqueue,
 930         .dequeue        =       netem_dequeue,
 931         .requeue        =       netem_requeue,
 932         .drop           =       netem_drop,
 933         .init           =       netem_init,
 934         .reset          =       netem_reset,
 935         .destroy        =       netem_destroy,
 936         .change         =       netem_change,
 937         .dump           =       netem_dump,
 938         .owner          =       THIS_MODULE,
 939 };
 940
 941
 942 static int __init netem_module_init(void)
 943 {
 944         return register_qdisc(&netem_qdisc_ops);
 945 }
 946 static void __exit netem_module_exit(void)
 947 {
 948         unregister_qdisc(&netem_qdisc_ops);
 949 }
 950 module_init(netem_module_init)
 951 module_exit(netem_module_exit)
 952 MODULE_LICENSE("GPL");