Blame view
net/sched/sch_netem.c
23.5 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 4 5 6 |
/* * net/sched/sch_netem.c Network emulator * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version |
798b6b19d [PATCH] skge, sky... |
7 |
* 2 of the License. |
1da177e4c Linux-2.6.12-rc2 |
8 9 |
* * Many of the algorithms and ideas for this came from |
10297b993 [NET] SCHED: Fix ... |
10 |
* NIST Net which is not copyrighted. |
1da177e4c Linux-2.6.12-rc2 |
11 12 13 14 |
* * Authors: Stephen Hemminger <shemminger@osdl.org> * Catalin(ux aka Dino) BOIE <catab at umbrella dot ro> */ |
b7f080cfe net: remove mm.h ... |
15 |
#include <linux/mm.h> |
1da177e4c Linux-2.6.12-rc2 |
16 |
#include <linux/module.h> |
5a0e3ad6a include cleanup: ... |
17 |
#include <linux/slab.h> |
1da177e4c Linux-2.6.12-rc2 |
18 19 20 |
#include <linux/types.h> #include <linux/kernel.h> #include <linux/errno.h> |
1da177e4c Linux-2.6.12-rc2 |
21 |
#include <linux/skbuff.h> |
78776d3f2 sch_netem: Need t... |
22 |
#include <linux/vmalloc.h> |
1da177e4c Linux-2.6.12-rc2 |
23 |
#include <linux/rtnetlink.h> |
90b41a1cd netem: add cell c... |
24 |
#include <linux/reciprocal_div.h> |
1da177e4c Linux-2.6.12-rc2 |
25 |
|
dc5fc579b [NETLINK]: Use nl... |
26 |
#include <net/netlink.h> |
1da177e4c Linux-2.6.12-rc2 |
27 |
#include <net/pkt_sched.h> |
250a65f78 netem: update ver... |
28 |
#define VERSION "1.3" |
eb229c4cd [NETEM]: Add vers... |
29 |
|
1da177e4c Linux-2.6.12-rc2 |
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
/* Network Emulation Queuing algorithm. ==================================== Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based Network Emulation Tool [2] Luigi Rizzo, DummyNet for FreeBSD ---------------------------------------------------------------- This started out as a simple way to delay outgoing packets to test TCP but has grown to include most of the functionality of a full blown network emulator like NISTnet. It can delay packets and add random jitter (and correlation). The random distribution can be loaded from a table as well to provide normal, Pareto, or experimental curves. Packet loss, duplication, and reordering can also be emulated. This qdisc does not do classification that can be handled in layering other disciplines. It does not need to do bandwidth control either since that can be handled by using token bucket or other rate control. |
661b79725 netem: revised co... |
51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
Correlated Loss Generator models Added generation of correlated loss according to the "Gilbert-Elliot" model, a 4-state markov model. References: [1] NetemCLG Home http://netgroup.uniroma2.it/NetemCLG [2] S. Salsano, F. Ludovici, A. Ordine, "Definition of a general and intuitive loss model for packet networks and its implementation in the Netem module in the Linux kernel", available in [1] Authors: Stefano Salsano <stefano.salsano at uniroma2.it Fabio Ludovici <fabio.ludovici at yahoo.it> |
1da177e4c Linux-2.6.12-rc2 |
65 66 67 |
*/ struct netem_sched_data { |
50612537e netem: fix classf... |
68 69 70 |
/* internal t(ime)fifo qdisc uses sch->q and sch->limit */ /* optional qdisc for classful handling (NULL at netem init) */ |
1da177e4c Linux-2.6.12-rc2 |
71 |
struct Qdisc *qdisc; |
50612537e netem: fix classf... |
72 |
|
59cb5c673 [NET_SCHED]: sch_... |
73 |
struct qdisc_watchdog watchdog; |
1da177e4c Linux-2.6.12-rc2 |
74 |
|
b407621c3 [NETEM]: use bett... |
75 76 |
psched_tdiff_t latency; psched_tdiff_t jitter; |
1da177e4c Linux-2.6.12-rc2 |
77 78 79 80 |
u32 loss; u32 limit; u32 counter; u32 gap; |
1da177e4c Linux-2.6.12-rc2 |
81 |
u32 duplicate; |
0dca51d36 [PKT_SCHED] netem... |
82 |
u32 reorder; |
c865e5d99 [PKT_SCHED] netem... |
83 |
u32 corrupt; |
7bc0f28c7 netem: rate exten... |
84 |
u32 rate; |
90b41a1cd netem: add cell c... |
85 86 87 88 |
s32 packet_overhead; u32 cell_size; u32 cell_size_reciprocal; s32 cell_overhead; |
1da177e4c Linux-2.6.12-rc2 |
89 90 |
struct crndstate { |
b407621c3 [NETEM]: use bett... |
91 92 |
u32 last; u32 rho; |
c865e5d99 [PKT_SCHED] netem... |
93 |
} delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor; |
1da177e4c Linux-2.6.12-rc2 |
94 95 96 97 98 |
struct disttable { u32 size; s16 table[0]; } *delay_dist; |
661b79725 netem: revised co... |
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
enum { CLG_RANDOM, CLG_4_STATES, CLG_GILB_ELL, } loss_model; /* Correlated Loss Generation models */ struct clgstate { /* state of the Markov chain */ u8 state; /* 4-states and Gilbert-Elliot models */ u32 a1; /* p13 for 4-states or p for GE */ u32 a2; /* p31 for 4-states or r for GE */ u32 a3; /* p32 for 4-states or h for GE */ u32 a4; /* p14 for 4-states or 1-k for GE */ u32 a5; /* p23 used only in 4-states */ } clg; |
1da177e4c Linux-2.6.12-rc2 |
118 |
}; |
50612537e netem: fix classf... |
119 120 121 |
/* Time stamp put into socket buffer control block * Only valid when skbs are in our internal t(ime)fifo queue. */ |
1da177e4c Linux-2.6.12-rc2 |
122 123 124 |
struct netem_skb_cb { psched_time_t time_to_send; }; |
5f86173bd net_sched: Add qd... |
125 126 |
static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb) { |
175f9c1bb net_sched: Add si... |
127 128 129 |
BUILD_BUG_ON(sizeof(skb->cb) < sizeof(struct qdisc_skb_cb) + sizeof(struct netem_skb_cb)); return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data; |
5f86173bd net_sched: Add qd... |
130 |
} |
1da177e4c Linux-2.6.12-rc2 |
131 132 133 134 135 136 137 138 139 140 141 142 143 |
/* init_crandom - initialize correlated random number generator * Use entropy source for initial seed. */ static void init_crandom(struct crndstate *state, unsigned long rho) { state->rho = rho; state->last = net_random(); } /* get_crandom - correlated random number generator * Next number depends on last value. * rho is scaled to avoid floating point. */ |
b407621c3 [NETEM]: use bett... |
144 |
static u32 get_crandom(struct crndstate *state) |
1da177e4c Linux-2.6.12-rc2 |
145 146 147 |
{ u64 value, rho; unsigned long answer; |
bb2f8cc0e [NETEM]: spelling... |
148 |
if (state->rho == 0) /* no correlation */ |
1da177e4c Linux-2.6.12-rc2 |
149 150 151 152 153 154 155 156 |
return net_random(); value = net_random(); rho = (u64)state->rho + 1; answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32; state->last = answer; return answer; } |
661b79725 netem: revised co... |
157 158 159 160 161 162 163 164 165 166 |
/* loss_4state - 4-state model loss generator * Generates losses according to the 4-state Markov chain adopted in * the GI (General and Intuitive) loss model. */ static bool loss_4state(struct netem_sched_data *q) { struct clgstate *clg = &q->clg; u32 rnd = net_random(); /* |
25985edce Fix common misspe... |
167 |
* Makes a comparison between rnd and the transition |
661b79725 netem: revised co... |
168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 |
* probabilities outgoing from the current state, then decides the * next state and if the next packet has to be transmitted or lost. * The four states correspond to: * 1 => successfully transmitted packets within a gap period * 4 => isolated losses within a gap period * 3 => lost packets within a burst period * 2 => successfully transmitted packets within a burst period */ switch (clg->state) { case 1: if (rnd < clg->a4) { clg->state = 4; return true; } else if (clg->a4 < rnd && rnd < clg->a1) { clg->state = 3; return true; } else if (clg->a1 < rnd) clg->state = 1; break; case 2: if (rnd < clg->a5) { clg->state = 3; return true; } else clg->state = 2; break; case 3: if (rnd < clg->a3) clg->state = 2; else if (clg->a3 < rnd && rnd < clg->a2 + clg->a3) { clg->state = 1; return true; } else if (clg->a2 + clg->a3 < rnd) { clg->state = 3; return true; } break; case 4: clg->state = 1; break; } return false; } /* loss_gilb_ell - Gilbert-Elliot model loss generator * Generates losses according to the Gilbert-Elliot loss model or * its special cases (Gilbert or Simple Gilbert) * |
25985edce Fix common misspe... |
219 |
* Makes a comparison between random number and the transition |
661b79725 netem: revised co... |
220 |
* probabilities outgoing from the current state, then decides the |
25985edce Fix common misspe... |
221 |
* next state. A second random number is extracted and the comparison |
661b79725 netem: revised co... |
222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 |
* with the loss probability of the current state decides if the next * packet will be transmitted or lost. */ static bool loss_gilb_ell(struct netem_sched_data *q) { struct clgstate *clg = &q->clg; switch (clg->state) { case 1: if (net_random() < clg->a1) clg->state = 2; if (net_random() < clg->a4) return true; case 2: if (net_random() < clg->a2) clg->state = 1; if (clg->a3 > net_random()) return true; } return false; } static bool loss_event(struct netem_sched_data *q) { switch (q->loss_model) { case CLG_RANDOM: /* Random packet drop 0 => none, ~0 => all */ return q->loss && q->loss >= get_crandom(&q->loss_cor); case CLG_4_STATES: /* 4state loss model algorithm (used also for GI model) * Extracts a value from the markov 4 state loss generator, * if it is 1 drops a packet and if needed writes the event in * the kernel logs */ return loss_4state(q); case CLG_GILB_ELL: /* Gilbert-Elliot loss model algorithm * Extracts a value from the Gilbert-Elliot loss generator, * if it is 1 drops a packet and if needed writes the event in * the kernel logs */ return loss_gilb_ell(q); } return false; /* not reached */ } |
1da177e4c Linux-2.6.12-rc2 |
271 272 273 274 |
/* tabledist - return a pseudo-randomly distributed value with mean mu and * std deviation sigma. Uses table lookup to approximate the desired * distribution, and a uniformly-distributed pseudo-random source. */ |
b407621c3 [NETEM]: use bett... |
275 276 277 |
static psched_tdiff_t tabledist(psched_tdiff_t mu, psched_tdiff_t sigma, struct crndstate *state, const struct disttable *dist) |
1da177e4c Linux-2.6.12-rc2 |
278 |
{ |
b407621c3 [NETEM]: use bett... |
279 280 281 |
psched_tdiff_t x; long t; u32 rnd; |
1da177e4c Linux-2.6.12-rc2 |
282 283 284 285 286 287 288 |
if (sigma == 0) return mu; rnd = get_crandom(state); /* default uniform distribution */ |
10297b993 [NET] SCHED: Fix ... |
289 |
if (dist == NULL) |
1da177e4c Linux-2.6.12-rc2 |
290 291 292 293 294 295 296 297 298 299 300 |
return (rnd % (2*sigma)) - sigma + mu; t = dist->table[rnd % dist->size]; x = (sigma % NETEM_DIST_SCALE) * t; if (x >= 0) x += NETEM_DIST_SCALE/2; else x -= NETEM_DIST_SCALE/2; return x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu; } |
90b41a1cd netem: add cell c... |
301 |
static psched_time_t packet_len_2_sched_time(unsigned int len, struct netem_sched_data *q) |
7bc0f28c7 netem: rate exten... |
302 |
{ |
90b41a1cd netem: add cell c... |
303 |
u64 ticks; |
fc33cc724 netem: fix build ... |
304 |
|
90b41a1cd netem: add cell c... |
305 306 307 308 309 310 311 312 313 314 315 316 317 |
len += q->packet_overhead; if (q->cell_size) { u32 cells = reciprocal_divide(len, q->cell_size_reciprocal); if (len > cells * q->cell_size) /* extra cell needed for remainder */ cells++; len = cells * (q->cell_size + q->cell_overhead); } ticks = (u64)len * NSEC_PER_SEC; do_div(ticks, q->rate); |
fc33cc724 netem: fix build ... |
318 |
return PSCHED_NS2TICKS(ticks); |
7bc0f28c7 netem: rate exten... |
319 |
} |
50612537e netem: fix classf... |
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 |
static int tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch) { struct sk_buff_head *list = &sch->q; psched_time_t tnext = netem_skb_cb(nskb)->time_to_send; struct sk_buff *skb; if (likely(skb_queue_len(list) < sch->limit)) { skb = skb_peek_tail(list); /* Optimize for add at tail */ if (likely(!skb || tnext >= netem_skb_cb(skb)->time_to_send)) return qdisc_enqueue_tail(nskb, sch); skb_queue_reverse_walk(list, skb) { if (tnext >= netem_skb_cb(skb)->time_to_send) break; } __skb_queue_after(list, skb, nskb); sch->qstats.backlog += qdisc_pkt_len(nskb); return NET_XMIT_SUCCESS; } return qdisc_reshape_fail(nskb, sch); } |
0afb51e72 [PKT_SCHED]: nete... |
344 345 346 347 348 349 |
/* * Insert one skb into qdisc. * Note: parent depends on return value to account for queue length. * NET_XMIT_DROP: queue length didn't change. * NET_XMIT_SUCCESS: one skb was queued. */ |
1da177e4c Linux-2.6.12-rc2 |
350 351 352 |
static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch) { struct netem_sched_data *q = qdisc_priv(sch); |
89e1df74f [PKT_SCHED] netem... |
353 354 |
/* We don't fill cb now as skb_unshare() may invalidate it */ struct netem_skb_cb *cb; |
0afb51e72 [PKT_SCHED]: nete... |
355 |
struct sk_buff *skb2; |
1da177e4c Linux-2.6.12-rc2 |
356 |
int ret; |
0afb51e72 [PKT_SCHED]: nete... |
357 |
int count = 1; |
1da177e4c Linux-2.6.12-rc2 |
358 |
|
0afb51e72 [PKT_SCHED]: nete... |
359 360 361 |
/* Random duplication */ if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) ++count; |
661b79725 netem: revised co... |
362 363 |
/* Drop packet? */ if (loss_event(q)) |
0afb51e72 [PKT_SCHED]: nete... |
364 365 366 |
--count; if (count == 0) { |
1da177e4c Linux-2.6.12-rc2 |
367 368 |
sch->qstats.drops++; kfree_skb(skb); |
c27f339af net_sched: Add qd... |
369 |
return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; |
1da177e4c Linux-2.6.12-rc2 |
370 |
} |
4e8a52015 [PKT_SCHED] netem... |
371 |
skb_orphan(skb); |
0afb51e72 [PKT_SCHED]: nete... |
372 373 374 375 376 377 |
/* * If we need to duplicate packet, then re-insert at top of the * qdisc tree, since parent queuer expects that only one * skb will be queued. */ if (count > 1 && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) { |
7698b4fca pkt_sched: Add an... |
378 |
struct Qdisc *rootq = qdisc_root(sch); |
0afb51e72 [PKT_SCHED]: nete... |
379 380 |
u32 dupsave = q->duplicate; /* prevent duplicating a dup... */ q->duplicate = 0; |
5f86173bd net_sched: Add qd... |
381 |
qdisc_enqueue_root(skb2, rootq); |
0afb51e72 [PKT_SCHED]: nete... |
382 |
q->duplicate = dupsave; |
1da177e4c Linux-2.6.12-rc2 |
383 |
} |
c865e5d99 [PKT_SCHED] netem... |
384 385 386 387 388 389 390 |
/* * Randomized packet corruption. * Make copy if needed since we are modifying * If packet is going to be hardware checksummed, then * do it now in software before we mangle it. */ if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor)) { |
f64f9e719 net: Move && and ... |
391 392 393 |
if (!(skb = skb_unshare(skb, GFP_ATOMIC)) || (skb->ip_summed == CHECKSUM_PARTIAL && skb_checksum_help(skb))) { |
c865e5d99 [PKT_SCHED] netem... |
394 395 396 397 398 399 |
sch->qstats.drops++; return NET_XMIT_DROP; } skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8); } |
5f86173bd net_sched: Add qd... |
400 |
cb = netem_skb_cb(skb); |
cc7ec456f net_sched: cleanups |
401 402 |
if (q->gap == 0 || /* not doing reordering */ q->counter < q->gap || /* inside last reordering gap */ |
f64f9e719 net: Move && and ... |
403 |
q->reorder < get_crandom(&q->reorder_cor)) { |
0f9f32ac6 [PKT_SCHED] netem... |
404 |
psched_time_t now; |
07aaa1154 [NETEM]: use PSCH... |
405 406 407 408 |
psched_tdiff_t delay; delay = tabledist(q->latency, q->jitter, &q->delay_cor, q->delay_dist); |
3bebcda28 [NET_SCHED]: turn... |
409 |
now = psched_get_time(); |
7bc0f28c7 netem: rate exten... |
410 411 |
if (q->rate) { |
50612537e netem: fix classf... |
412 |
struct sk_buff_head *list = &sch->q; |
7bc0f28c7 netem: rate exten... |
413 |
|
90b41a1cd netem: add cell c... |
414 |
delay += packet_len_2_sched_time(skb->len, q); |
7bc0f28c7 netem: rate exten... |
415 416 417 418 419 420 421 422 423 424 425 426 |
if (!skb_queue_empty(list)) { /* * Last packet in queue is reference point (now). * First packet in queue is already in flight, * calculate this time bonus and substract * from delay. */ delay -= now - netem_skb_cb(skb_peek(list))->time_to_send; now = netem_skb_cb(skb_peek_tail(list))->time_to_send; } } |
7c59e25f3 [NET_SCHED]: kill... |
427 |
cb->time_to_send = now + delay; |
1da177e4c Linux-2.6.12-rc2 |
428 |
++q->counter; |
50612537e netem: fix classf... |
429 |
ret = tfifo_enqueue(skb, sch); |
1da177e4c Linux-2.6.12-rc2 |
430 |
} else { |
10297b993 [NET] SCHED: Fix ... |
431 |
/* |
0dca51d36 [PKT_SCHED] netem... |
432 433 434 |
* Do re-ordering by putting one out of N packets at the front * of the queue. */ |
3bebcda28 [NET_SCHED]: turn... |
435 |
cb->time_to_send = psched_get_time(); |
0dca51d36 [PKT_SCHED] netem... |
436 |
q->counter = 0; |
8ba25dad0 sch_netem: Replac... |
437 |
|
50612537e netem: fix classf... |
438 |
__skb_queue_head(&sch->q, skb); |
eb1019244 net_sched: Bug in... |
439 440 |
sch->qstats.backlog += qdisc_pkt_len(skb); sch->qstats.requeues++; |
8ba25dad0 sch_netem: Replac... |
441 |
ret = NET_XMIT_SUCCESS; |
1da177e4c Linux-2.6.12-rc2 |
442 |
} |
10f6dfcfd Revert "sch_netem... |
443 444 445 446 447 |
if (ret != NET_XMIT_SUCCESS) { if (net_xmit_drop_count(ret)) { sch->qstats.drops++; return ret; } |
378a2f090 net_sched: Add qd... |
448 |
} |
1da177e4c Linux-2.6.12-rc2 |
449 |
|
10f6dfcfd Revert "sch_netem... |
450 |
return NET_XMIT_SUCCESS; |
1da177e4c Linux-2.6.12-rc2 |
451 |
} |
cc7ec456f net_sched: cleanups |
452 |
static unsigned int netem_drop(struct Qdisc *sch) |
1da177e4c Linux-2.6.12-rc2 |
453 454 |
{ struct netem_sched_data *q = qdisc_priv(sch); |
50612537e netem: fix classf... |
455 |
unsigned int len; |
1da177e4c Linux-2.6.12-rc2 |
456 |
|
50612537e netem: fix classf... |
457 458 459 460 |
len = qdisc_queue_drop(sch); if (!len && q->qdisc && q->qdisc->ops->drop) len = q->qdisc->ops->drop(q->qdisc); if (len) |
1da177e4c Linux-2.6.12-rc2 |
461 |
sch->qstats.drops++; |
50612537e netem: fix classf... |
462 |
|
1da177e4c Linux-2.6.12-rc2 |
463 464 |
return len; } |
1da177e4c Linux-2.6.12-rc2 |
465 466 467 468 |
static struct sk_buff *netem_dequeue(struct Qdisc *sch) { struct netem_sched_data *q = qdisc_priv(sch); struct sk_buff *skb; |
fd245a4ad net_sched: move T... |
469 |
if (qdisc_is_throttled(sch)) |
11274e5a4 [NETEM]: avoid ex... |
470 |
return NULL; |
50612537e netem: fix classf... |
471 472 |
tfifo_dequeue: skb = qdisc_peek_head(sch); |
771018e76 [PKT_SCHED]: nete... |
473 |
if (skb) { |
5f86173bd net_sched: Add qd... |
474 |
const struct netem_skb_cb *cb = netem_skb_cb(skb); |
0f9f32ac6 [PKT_SCHED] netem... |
475 476 |
/* if more time remaining? */ |
50612537e netem: fix classf... |
477 478 |
if (cb->time_to_send <= psched_get_time()) { skb = qdisc_dequeue_tail(sch); |
77be155cb pkt_sched: Add pe... |
479 |
if (unlikely(!skb)) |
50612537e netem: fix classf... |
480 |
goto qdisc_dequeue; |
03c05f0d4 pkt_sched: Use qd... |
481 |
|
8caf15397 net: sch_netem: F... |
482 483 484 485 486 487 488 489 |
#ifdef CONFIG_NET_CLS_ACT /* * If it's at ingress let's pretend the delay is * from the network (tstamp will be updated). */ if (G_TC_FROM(skb->tc_verd) & AT_INGRESS) skb->tstamp.tv64 = 0; #endif |
10f6dfcfd Revert "sch_netem... |
490 |
|
50612537e netem: fix classf... |
491 492 493 494 495 496 497 498 499 500 501 502 |
if (q->qdisc) { int err = qdisc_enqueue(skb, q->qdisc); if (unlikely(err != NET_XMIT_SUCCESS)) { if (net_xmit_drop_count(err)) { sch->qstats.drops++; qdisc_tree_decrease_qlen(sch, 1); } } goto tfifo_dequeue; } deliver: |
10f6dfcfd Revert "sch_netem... |
503 504 |
qdisc_unthrottled(sch); qdisc_bstats_update(sch, skb); |
0f9f32ac6 [PKT_SCHED] netem... |
505 |
return skb; |
07aaa1154 [NETEM]: use PSCH... |
506 |
} |
11274e5a4 [NETEM]: avoid ex... |
507 |
|
50612537e netem: fix classf... |
508 509 510 511 512 |
if (q->qdisc) { skb = q->qdisc->ops->dequeue(q->qdisc); if (skb) goto deliver; } |
11274e5a4 [NETEM]: avoid ex... |
513 |
qdisc_watchdog_schedule(&q->watchdog, cb->time_to_send); |
0f9f32ac6 [PKT_SCHED] netem... |
514 |
} |
50612537e netem: fix classf... |
515 516 517 518 519 520 |
qdisc_dequeue: if (q->qdisc) { skb = q->qdisc->ops->dequeue(q->qdisc); if (skb) goto deliver; } |
0f9f32ac6 [PKT_SCHED] netem... |
521 |
return NULL; |
1da177e4c Linux-2.6.12-rc2 |
522 |
} |
1da177e4c Linux-2.6.12-rc2 |
523 524 525 |
static void netem_reset(struct Qdisc *sch) { struct netem_sched_data *q = qdisc_priv(sch); |
50612537e netem: fix classf... |
526 527 528 |
qdisc_reset_queue(sch); if (q->qdisc) qdisc_reset(q->qdisc); |
59cb5c673 [NET_SCHED]: sch_... |
529 |
qdisc_watchdog_cancel(&q->watchdog); |
1da177e4c Linux-2.6.12-rc2 |
530 |
} |
6373a9a28 netem: use vmallo... |
531 532 533 534 535 536 537 538 539 |
static void dist_free(struct disttable *d) { if (d) { if (is_vmalloc_addr(d)) vfree(d); else kfree(d); } } |
1da177e4c Linux-2.6.12-rc2 |
540 541 542 543 |
/* * Distribution data is a variable size payload containing * signed 16 bit values. */ |
1e90474c3 [NET_SCHED]: Conv... |
544 |
static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr) |
1da177e4c Linux-2.6.12-rc2 |
545 546 |
{ struct netem_sched_data *q = qdisc_priv(sch); |
6373a9a28 netem: use vmallo... |
547 |
size_t n = nla_len(attr)/sizeof(__s16); |
1e90474c3 [NET_SCHED]: Conv... |
548 |
const __s16 *data = nla_data(attr); |
7698b4fca pkt_sched: Add an... |
549 |
spinlock_t *root_lock; |
1da177e4c Linux-2.6.12-rc2 |
550 551 |
struct disttable *d; int i; |
6373a9a28 netem: use vmallo... |
552 |
size_t s; |
1da177e4c Linux-2.6.12-rc2 |
553 |
|
df173bda2 netem: define NET... |
554 |
if (n > NETEM_DIST_MAX) |
1da177e4c Linux-2.6.12-rc2 |
555 |
return -EINVAL; |
6373a9a28 netem: use vmallo... |
556 |
s = sizeof(struct disttable) + n * sizeof(s16); |
bb52c7acf netem: dont call ... |
557 |
d = kmalloc(s, GFP_KERNEL | __GFP_NOWARN); |
6373a9a28 netem: use vmallo... |
558 559 |
if (!d) d = vmalloc(s); |
1da177e4c Linux-2.6.12-rc2 |
560 561 562 563 564 565 |
if (!d) return -ENOMEM; d->size = n; for (i = 0; i < n; i++) d->table[i] = data[i]; |
10297b993 [NET] SCHED: Fix ... |
566 |
|
102396ae6 pkt_sched: Fix lo... |
567 |
root_lock = qdisc_root_sleeping_lock(sch); |
7698b4fca pkt_sched: Add an... |
568 569 |
spin_lock_bh(root_lock); |
bb52c7acf netem: dont call ... |
570 |
swap(q->delay_dist, d); |
7698b4fca pkt_sched: Add an... |
571 |
spin_unlock_bh(root_lock); |
bb52c7acf netem: dont call ... |
572 573 |
dist_free(d); |
1da177e4c Linux-2.6.12-rc2 |
574 575 |
return 0; } |
265eb67fb netem: eliminate ... |
576 |
static void get_correlation(struct Qdisc *sch, const struct nlattr *attr) |
1da177e4c Linux-2.6.12-rc2 |
577 578 |
{ struct netem_sched_data *q = qdisc_priv(sch); |
1e90474c3 [NET_SCHED]: Conv... |
579 |
const struct tc_netem_corr *c = nla_data(attr); |
1da177e4c Linux-2.6.12-rc2 |
580 |
|
1da177e4c Linux-2.6.12-rc2 |
581 582 583 |
init_crandom(&q->delay_cor, c->delay_corr); init_crandom(&q->loss_cor, c->loss_corr); init_crandom(&q->dup_cor, c->dup_corr); |
1da177e4c Linux-2.6.12-rc2 |
584 |
} |
265eb67fb netem: eliminate ... |
585 |
static void get_reorder(struct Qdisc *sch, const struct nlattr *attr) |
0dca51d36 [PKT_SCHED] netem... |
586 587 |
{ struct netem_sched_data *q = qdisc_priv(sch); |
1e90474c3 [NET_SCHED]: Conv... |
588 |
const struct tc_netem_reorder *r = nla_data(attr); |
0dca51d36 [PKT_SCHED] netem... |
589 |
|
0dca51d36 [PKT_SCHED] netem... |
590 591 |
q->reorder = r->probability; init_crandom(&q->reorder_cor, r->correlation); |
0dca51d36 [PKT_SCHED] netem... |
592 |
} |
265eb67fb netem: eliminate ... |
593 |
static void get_corrupt(struct Qdisc *sch, const struct nlattr *attr) |
c865e5d99 [PKT_SCHED] netem... |
594 595 |
{ struct netem_sched_data *q = qdisc_priv(sch); |
1e90474c3 [NET_SCHED]: Conv... |
596 |
const struct tc_netem_corrupt *r = nla_data(attr); |
c865e5d99 [PKT_SCHED] netem... |
597 |
|
c865e5d99 [PKT_SCHED] netem... |
598 599 |
q->corrupt = r->probability; init_crandom(&q->corrupt_cor, r->correlation); |
c865e5d99 [PKT_SCHED] netem... |
600 |
} |
7bc0f28c7 netem: rate exten... |
601 602 603 604 605 606 |
static void get_rate(struct Qdisc *sch, const struct nlattr *attr) { struct netem_sched_data *q = qdisc_priv(sch); const struct tc_netem_rate *r = nla_data(attr); q->rate = r->rate; |
90b41a1cd netem: add cell c... |
607 608 609 610 611 |
q->packet_overhead = r->packet_overhead; q->cell_size = r->cell_size; if (q->cell_size) q->cell_size_reciprocal = reciprocal_value(q->cell_size); q->cell_overhead = r->cell_overhead; |
7bc0f28c7 netem: rate exten... |
612 |
} |
661b79725 netem: revised co... |
613 614 615 616 617 618 619 620 621 622 623 624 |
static int get_loss_clg(struct Qdisc *sch, const struct nlattr *attr) { struct netem_sched_data *q = qdisc_priv(sch); const struct nlattr *la; int rem; nla_for_each_nested(la, attr, rem) { u16 type = nla_type(la); switch(type) { case NETEM_LOSS_GI: { const struct tc_netem_gimodel *gi = nla_data(la); |
2494654d4 netem: loss model... |
625 |
if (nla_len(la) < sizeof(struct tc_netem_gimodel)) { |
661b79725 netem: revised co... |
626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 |
pr_info("netem: incorrect gi model size "); return -EINVAL; } q->loss_model = CLG_4_STATES; q->clg.state = 1; q->clg.a1 = gi->p13; q->clg.a2 = gi->p31; q->clg.a3 = gi->p32; q->clg.a4 = gi->p14; q->clg.a5 = gi->p23; break; } case NETEM_LOSS_GE: { const struct tc_netem_gemodel *ge = nla_data(la); |
2494654d4 netem: loss model... |
644 645 646 |
if (nla_len(la) < sizeof(struct tc_netem_gemodel)) { pr_info("netem: incorrect ge model size "); |
661b79725 netem: revised co... |
647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 |
return -EINVAL; } q->loss_model = CLG_GILB_ELL; q->clg.state = 1; q->clg.a1 = ge->p; q->clg.a2 = ge->r; q->clg.a3 = ge->h; q->clg.a4 = ge->k1; break; } default: pr_info("netem: unknown loss type %u ", type); return -EINVAL; } } return 0; } |
27a3421e4 [NET_SCHED]: Use ... |
668 669 670 671 |
static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = { [TCA_NETEM_CORR] = { .len = sizeof(struct tc_netem_corr) }, [TCA_NETEM_REORDER] = { .len = sizeof(struct tc_netem_reorder) }, [TCA_NETEM_CORRUPT] = { .len = sizeof(struct tc_netem_corrupt) }, |
7bc0f28c7 netem: rate exten... |
672 |
[TCA_NETEM_RATE] = { .len = sizeof(struct tc_netem_rate) }, |
661b79725 netem: revised co... |
673 |
[TCA_NETEM_LOSS] = { .type = NLA_NESTED }, |
27a3421e4 [NET_SCHED]: Use ... |
674 |
}; |
2c10b32bf netlink: Remove c... |
675 676 677 678 |
static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr *nla, const struct nla_policy *policy, int len) { int nested_len = nla_len(nla) - NLA_ALIGN(len); |
661b79725 netem: revised co... |
679 680 681 |
if (nested_len < 0) { pr_info("netem: invalid attributes len %d ", nested_len); |
2c10b32bf netlink: Remove c... |
682 |
return -EINVAL; |
661b79725 netem: revised co... |
683 |
} |
2c10b32bf netlink: Remove c... |
684 685 686 |
if (nested_len >= nla_attr_size(0)) return nla_parse(tb, maxtype, nla_data(nla) + NLA_ALIGN(len), nested_len, policy); |
661b79725 netem: revised co... |
687 |
|
2c10b32bf netlink: Remove c... |
688 689 690 |
memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1)); return 0; } |
c865e5d99 [PKT_SCHED] netem... |
691 |
/* Parse netlink message to set options */ |
1e90474c3 [NET_SCHED]: Conv... |
692 |
static int netem_change(struct Qdisc *sch, struct nlattr *opt) |
1da177e4c Linux-2.6.12-rc2 |
693 694 |
{ struct netem_sched_data *q = qdisc_priv(sch); |
b03f46720 [NET_SCHED]: sch_... |
695 |
struct nlattr *tb[TCA_NETEM_MAX + 1]; |
1da177e4c Linux-2.6.12-rc2 |
696 697 |
struct tc_netem_qopt *qopt; int ret; |
10297b993 [NET] SCHED: Fix ... |
698 |
|
b03f46720 [NET_SCHED]: sch_... |
699 |
if (opt == NULL) |
1da177e4c Linux-2.6.12-rc2 |
700 |
return -EINVAL; |
2c10b32bf netlink: Remove c... |
701 702 |
qopt = nla_data(opt); ret = parse_attr(tb, TCA_NETEM_MAX, opt, netem_policy, sizeof(*qopt)); |
b03f46720 [NET_SCHED]: sch_... |
703 704 |
if (ret < 0) return ret; |
50612537e netem: fix classf... |
705 |
sch->limit = qopt->limit; |
10297b993 [NET] SCHED: Fix ... |
706 |
|
1da177e4c Linux-2.6.12-rc2 |
707 708 709 710 |
q->latency = qopt->latency; q->jitter = qopt->jitter; q->limit = qopt->limit; q->gap = qopt->gap; |
0dca51d36 [PKT_SCHED] netem... |
711 |
q->counter = 0; |
1da177e4c Linux-2.6.12-rc2 |
712 713 |
q->loss = qopt->loss; q->duplicate = qopt->duplicate; |
bb2f8cc0e [NETEM]: spelling... |
714 715 |
/* for compatibility with earlier versions. * if gap is set, need to assume 100% probability |
0dca51d36 [PKT_SCHED] netem... |
716 |
*/ |
a362e0a78 [NETEM]: report r... |
717 718 |
if (q->gap) q->reorder = ~0; |
0dca51d36 [PKT_SCHED] netem... |
719 |
|
265eb67fb netem: eliminate ... |
720 721 |
if (tb[TCA_NETEM_CORR]) get_correlation(sch, tb[TCA_NETEM_CORR]); |
1da177e4c Linux-2.6.12-rc2 |
722 |
|
b03f46720 [NET_SCHED]: sch_... |
723 724 725 726 727 |
if (tb[TCA_NETEM_DELAY_DIST]) { ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]); if (ret) return ret; } |
c865e5d99 [PKT_SCHED] netem... |
728 |
|
265eb67fb netem: eliminate ... |
729 730 |
if (tb[TCA_NETEM_REORDER]) get_reorder(sch, tb[TCA_NETEM_REORDER]); |
1da177e4c Linux-2.6.12-rc2 |
731 |
|
265eb67fb netem: eliminate ... |
732 733 |
if (tb[TCA_NETEM_CORRUPT]) get_corrupt(sch, tb[TCA_NETEM_CORRUPT]); |
1da177e4c Linux-2.6.12-rc2 |
734 |
|
7bc0f28c7 netem: rate exten... |
735 736 |
if (tb[TCA_NETEM_RATE]) get_rate(sch, tb[TCA_NETEM_RATE]); |
661b79725 netem: revised co... |
737 738 739 740 741 |
q->loss_model = CLG_RANDOM; if (tb[TCA_NETEM_LOSS]) ret = get_loss_clg(sch, tb[TCA_NETEM_LOSS]); return ret; |
1da177e4c Linux-2.6.12-rc2 |
742 |
} |
1e90474c3 [NET_SCHED]: Conv... |
743 |
static int netem_init(struct Qdisc *sch, struct nlattr *opt) |
1da177e4c Linux-2.6.12-rc2 |
744 745 746 747 748 749 |
{ struct netem_sched_data *q = qdisc_priv(sch); int ret; if (!opt) return -EINVAL; |
59cb5c673 [NET_SCHED]: sch_... |
750 |
qdisc_watchdog_init(&q->watchdog, sch); |
1da177e4c Linux-2.6.12-rc2 |
751 |
|
661b79725 netem: revised co... |
752 |
q->loss_model = CLG_RANDOM; |
1da177e4c Linux-2.6.12-rc2 |
753 |
ret = netem_change(sch, opt); |
50612537e netem: fix classf... |
754 |
if (ret) |
250a65f78 netem: update ver... |
755 756 |
pr_info("netem: change failed "); |
1da177e4c Linux-2.6.12-rc2 |
757 758 759 760 761 762 |
return ret; } static void netem_destroy(struct Qdisc *sch) { struct netem_sched_data *q = qdisc_priv(sch); |
59cb5c673 [NET_SCHED]: sch_... |
763 |
qdisc_watchdog_cancel(&q->watchdog); |
50612537e netem: fix classf... |
764 765 |
if (q->qdisc) qdisc_destroy(q->qdisc); |
6373a9a28 netem: use vmallo... |
766 |
dist_free(q->delay_dist); |
1da177e4c Linux-2.6.12-rc2 |
767 |
} |
661b79725 netem: revised co... |
768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 |
static int dump_loss_model(const struct netem_sched_data *q, struct sk_buff *skb) { struct nlattr *nest; nest = nla_nest_start(skb, TCA_NETEM_LOSS); if (nest == NULL) goto nla_put_failure; switch (q->loss_model) { case CLG_RANDOM: /* legacy loss model */ nla_nest_cancel(skb, nest); return 0; /* no data */ case CLG_4_STATES: { struct tc_netem_gimodel gi = { .p13 = q->clg.a1, .p31 = q->clg.a2, .p32 = q->clg.a3, .p14 = q->clg.a4, .p23 = q->clg.a5, }; NLA_PUT(skb, NETEM_LOSS_GI, sizeof(gi), &gi); break; } case CLG_GILB_ELL: { struct tc_netem_gemodel ge = { .p = q->clg.a1, .r = q->clg.a2, .h = q->clg.a3, .k1 = q->clg.a4, }; NLA_PUT(skb, NETEM_LOSS_GE, sizeof(ge), &ge); break; } } nla_nest_end(skb, nest); return 0; nla_put_failure: nla_nest_cancel(skb, nest); return -1; } |
1da177e4c Linux-2.6.12-rc2 |
815 816 817 |
static int netem_dump(struct Qdisc *sch, struct sk_buff *skb) { const struct netem_sched_data *q = qdisc_priv(sch); |
861d7f745 netem: cleanup du... |
818 |
struct nlattr *nla = (struct nlattr *) skb_tail_pointer(skb); |
1da177e4c Linux-2.6.12-rc2 |
819 820 |
struct tc_netem_qopt qopt; struct tc_netem_corr cor; |
0dca51d36 [PKT_SCHED] netem... |
821 |
struct tc_netem_reorder reorder; |
c865e5d99 [PKT_SCHED] netem... |
822 |
struct tc_netem_corrupt corrupt; |
7bc0f28c7 netem: rate exten... |
823 |
struct tc_netem_rate rate; |
1da177e4c Linux-2.6.12-rc2 |
824 825 826 827 828 829 830 |
qopt.latency = q->latency; qopt.jitter = q->jitter; qopt.limit = q->limit; qopt.loss = q->loss; qopt.gap = q->gap; qopt.duplicate = q->duplicate; |
1e90474c3 [NET_SCHED]: Conv... |
831 |
NLA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt); |
1da177e4c Linux-2.6.12-rc2 |
832 833 834 835 |
cor.delay_corr = q->delay_cor.rho; cor.loss_corr = q->loss_cor.rho; cor.dup_corr = q->dup_cor.rho; |
1e90474c3 [NET_SCHED]: Conv... |
836 |
NLA_PUT(skb, TCA_NETEM_CORR, sizeof(cor), &cor); |
0dca51d36 [PKT_SCHED] netem... |
837 838 839 |
reorder.probability = q->reorder; reorder.correlation = q->reorder_cor.rho; |
1e90474c3 [NET_SCHED]: Conv... |
840 |
NLA_PUT(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder); |
0dca51d36 [PKT_SCHED] netem... |
841 |
|
c865e5d99 [PKT_SCHED] netem... |
842 843 |
corrupt.probability = q->corrupt; corrupt.correlation = q->corrupt_cor.rho; |
1e90474c3 [NET_SCHED]: Conv... |
844 |
NLA_PUT(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt); |
c865e5d99 [PKT_SCHED] netem... |
845 |
|
7bc0f28c7 netem: rate exten... |
846 |
rate.rate = q->rate; |
90b41a1cd netem: add cell c... |
847 848 849 |
rate.packet_overhead = q->packet_overhead; rate.cell_size = q->cell_size; rate.cell_overhead = q->cell_overhead; |
7bc0f28c7 netem: rate exten... |
850 |
NLA_PUT(skb, TCA_NETEM_RATE, sizeof(rate), &rate); |
661b79725 netem: revised co... |
851 852 |
if (dump_loss_model(q, skb) != 0) goto nla_put_failure; |
861d7f745 netem: cleanup du... |
853 |
return nla_nest_end(skb, nla); |
1da177e4c Linux-2.6.12-rc2 |
854 |
|
1e90474c3 [NET_SCHED]: Conv... |
855 |
nla_put_failure: |
861d7f745 netem: cleanup du... |
856 |
nlmsg_trim(skb, nla); |
1da177e4c Linux-2.6.12-rc2 |
857 858 |
return -1; } |
10f6dfcfd Revert "sch_netem... |
859 860 861 862 |
static int netem_dump_class(struct Qdisc *sch, unsigned long cl, struct sk_buff *skb, struct tcmsg *tcm) { struct netem_sched_data *q = qdisc_priv(sch); |
50612537e netem: fix classf... |
863 |
if (cl != 1 || !q->qdisc) /* only one class */ |
10f6dfcfd Revert "sch_netem... |
864 865 866 867 868 869 870 871 872 873 874 875 |
return -ENOENT; tcm->tcm_handle |= TC_H_MIN(1); tcm->tcm_info = q->qdisc->handle; return 0; } static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, struct Qdisc **old) { struct netem_sched_data *q = qdisc_priv(sch); |
10f6dfcfd Revert "sch_netem... |
876 877 878 |
sch_tree_lock(sch); *old = q->qdisc; q->qdisc = new; |
50612537e netem: fix classf... |
879 880 881 882 |
if (*old) { qdisc_tree_decrease_qlen(*old, (*old)->q.qlen); qdisc_reset(*old); } |
10f6dfcfd Revert "sch_netem... |
883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 |
sch_tree_unlock(sch); return 0; } static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg) { struct netem_sched_data *q = qdisc_priv(sch); return q->qdisc; } static unsigned long netem_get(struct Qdisc *sch, u32 classid) { return 1; } static void netem_put(struct Qdisc *sch, unsigned long arg) { } static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker) { if (!walker->stop) { if (walker->count >= walker->skip) if (walker->fn(sch, 1, walker) < 0) { walker->stop = 1; return; } walker->count++; } } static const struct Qdisc_class_ops netem_class_ops = { .graft = netem_graft, .leaf = netem_leaf, .get = netem_get, .put = netem_put, .walk = netem_walk, .dump = netem_dump_class, }; |
20fea08b5 [NET]: Move Qdisc... |
923 |
static struct Qdisc_ops netem_qdisc_ops __read_mostly = { |
1da177e4c Linux-2.6.12-rc2 |
924 |
.id = "netem", |
10f6dfcfd Revert "sch_netem... |
925 |
.cl_ops = &netem_class_ops, |
1da177e4c Linux-2.6.12-rc2 |
926 927 928 |
.priv_size = sizeof(struct netem_sched_data), .enqueue = netem_enqueue, .dequeue = netem_dequeue, |
77be155cb pkt_sched: Add pe... |
929 |
.peek = qdisc_peek_dequeued, |
1da177e4c Linux-2.6.12-rc2 |
930 931 932 933 934 935 936 937 938 939 940 941 |
.drop = netem_drop, .init = netem_init, .reset = netem_reset, .destroy = netem_destroy, .change = netem_change, .dump = netem_dump, .owner = THIS_MODULE, }; static int __init netem_module_init(void) { |
eb229c4cd [NETEM]: Add vers... |
942 943 |
pr_info("netem: version " VERSION " "); |
1da177e4c Linux-2.6.12-rc2 |
944 945 946 947 948 949 950 951 952 |
return register_qdisc(&netem_qdisc_ops); } static void __exit netem_module_exit(void) { unregister_qdisc(&netem_qdisc_ops); } module_init(netem_module_init) module_exit(netem_module_exit) MODULE_LICENSE("GPL"); |