sch_netem.c 27.3 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
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
7
 * 		2 of the License.
Linus Torvalds's avatar
Linus Torvalds committed
8 9
 *
 *  		Many of the algorithms and ideas for this came from
10
 *		NIST Net which is not copyrighted.
Linus Torvalds's avatar
Linus Torvalds committed
11 12 13 14 15
 *
 * Authors:	Stephen Hemminger <shemminger@osdl.org>
 *		Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
 */

16
#include <linux/mm.h>
Linus Torvalds's avatar
Linus Torvalds committed
17
#include <linux/module.h>
18
#include <linux/slab.h>
Linus Torvalds's avatar
Linus Torvalds committed
19 20 21 22
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/skbuff.h>
23
#include <linux/vmalloc.h>
Linus Torvalds's avatar
Linus Torvalds committed
24
#include <linux/rtnetlink.h>
25
#include <linux/reciprocal_div.h>
26
#include <linux/rbtree.h>
Linus Torvalds's avatar
Linus Torvalds committed
27

28
#include <net/netlink.h>
Linus Torvalds's avatar
Linus Torvalds committed
29
#include <net/pkt_sched.h>
Eric Dumazet's avatar
Eric Dumazet committed
30
#include <net/inet_ecn.h>
Linus Torvalds's avatar
Linus Torvalds committed
31

32
#define VERSION "1.3"
33

Linus Torvalds's avatar
Linus Torvalds committed
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
/*	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.
55 56 57 58 59 60 61 62 63 64 65 66 67 68

     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>
Linus Torvalds's avatar
Linus Torvalds committed
69 70 71
*/

struct netem_sched_data {
72 73
	/* internal t(ime)fifo qdisc uses t_root and sch->limit */
	struct rb_root t_root;
Eric Dumazet's avatar
Eric Dumazet committed
74 75

	/* optional qdisc for classful handling (NULL at netem init) */
Linus Torvalds's avatar
Linus Torvalds committed
76
	struct Qdisc	*qdisc;
Eric Dumazet's avatar
Eric Dumazet committed
77

78
	struct qdisc_watchdog watchdog;
Linus Torvalds's avatar
Linus Torvalds committed
79

80 81 82
	psched_tdiff_t latency;
	psched_tdiff_t jitter;

Linus Torvalds's avatar
Linus Torvalds committed
83
	u32 loss;
Eric Dumazet's avatar
Eric Dumazet committed
84
	u32 ecn;
Linus Torvalds's avatar
Linus Torvalds committed
85 86 87 88
	u32 limit;
	u32 counter;
	u32 gap;
	u32 duplicate;
89
	u32 reorder;
90
	u32 corrupt;
91
	u64 rate;
92 93
	s32 packet_overhead;
	u32 cell_size;
94
	struct reciprocal_value cell_size_reciprocal;
95
	s32 cell_overhead;
Linus Torvalds's avatar
Linus Torvalds committed
96 97

	struct crndstate {
98 99
		u32 last;
		u32 rho;
100
	} delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor;
Linus Torvalds's avatar
Linus Torvalds committed
101 102 103 104 105

	struct disttable {
		u32  size;
		s16 table[0];
	} *delay_dist;
106 107 108 109 110 111 112

	enum  {
		CLG_RANDOM,
		CLG_4_STATES,
		CLG_GILB_ELL,
	} loss_model;

113 114 115 116 117 118 119
	enum {
		TX_IN_GAP_PERIOD = 1,
		TX_IN_BURST_PERIOD,
		LOST_IN_GAP_PERIOD,
		LOST_IN_BURST_PERIOD,
	} _4_state_model;

120 121 122 123 124
	enum {
		GOOD_STATE = 1,
		BAD_STATE,
	} GE_state_model;

125 126 127 128 129 130 131 132 133 134 135 136 137
	/* 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;

Linus Torvalds's avatar
Linus Torvalds committed
138 139
};

Eric Dumazet's avatar
Eric Dumazet committed
140 141
/* Time stamp put into socket buffer control block
 * Only valid when skbs are in our internal t(ime)fifo queue.
142 143 144 145
 *
 * As skb->rbnode uses same storage than skb->next, skb->prev and skb->tstamp,
 * and skb->next & skb->prev are scratch space for a qdisc,
 * we save skb->tstamp value in skb->cb[] before destroying it.
Eric Dumazet's avatar
Eric Dumazet committed
146
 */
Linus Torvalds's avatar
Linus Torvalds committed
147 148
struct netem_skb_cb {
	psched_time_t	time_to_send;
149
	ktime_t		tstamp_save;
Linus Torvalds's avatar
Linus Torvalds committed
150 151
};

152 153
static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb)
{
154
	/* we assume we can use skb next/prev/tstamp as storage for rb_node */
155
	qdisc_cb_private_validate(skb, sizeof(struct netem_skb_cb));
156
	return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data;
157 158
}

Linus Torvalds's avatar
Linus Torvalds committed
159 160 161 162 163 164
/* 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;
165
	state->last = prandom_u32();
Linus Torvalds's avatar
Linus Torvalds committed
166 167 168 169 170 171
}

/* get_crandom - correlated random number generator
 * Next number depends on last value.
 * rho is scaled to avoid floating point.
 */
172
static u32 get_crandom(struct crndstate *state)
Linus Torvalds's avatar
Linus Torvalds committed
173 174 175 176
{
	u64 value, rho;
	unsigned long answer;

Stephen Hemminger's avatar
Stephen Hemminger committed
177
	if (state->rho == 0)	/* no correlation */
178
		return prandom_u32();
Linus Torvalds's avatar
Linus Torvalds committed
179

180
	value = prandom_u32();
Linus Torvalds's avatar
Linus Torvalds committed
181 182 183 184 185 186
	rho = (u64)state->rho + 1;
	answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
	state->last = answer;
	return answer;
}

187 188 189 190 191 192 193
/* 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;
194
	u32 rnd = prandom_u32();
195 196

	/*
Lucas De Marchi's avatar
Lucas De Marchi committed
197
	 * Makes a comparison between rnd and the transition
198 199 200
	 * 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:
201 202 203 204
	 *   TX_IN_GAP_PERIOD => successfully transmitted packets within a gap period
	 *   LOST_IN_BURST_PERIOD => isolated losses within a gap period
	 *   LOST_IN_GAP_PERIOD => lost packets within a burst period
	 *   TX_IN_GAP_PERIOD => successfully transmitted packets within a burst period
205 206
	 */
	switch (clg->state) {
207
	case TX_IN_GAP_PERIOD:
208
		if (rnd < clg->a4) {
209
			clg->state = LOST_IN_BURST_PERIOD;
210
			return true;
211
		} else if (clg->a4 < rnd && rnd < clg->a1 + clg->a4) {
212
			clg->state = LOST_IN_GAP_PERIOD;
213
			return true;
214 215 216
		} else if (clg->a1 + clg->a4 < rnd) {
			clg->state = TX_IN_GAP_PERIOD;
		}
217 218

		break;
219
	case TX_IN_BURST_PERIOD:
220
		if (rnd < clg->a5) {
221
			clg->state = LOST_IN_GAP_PERIOD;
222
			return true;
223 224 225
		} else {
			clg->state = TX_IN_BURST_PERIOD;
		}
226 227

		break;
228
	case LOST_IN_GAP_PERIOD:
229
		if (rnd < clg->a3)
230
			clg->state = TX_IN_BURST_PERIOD;
231
		else if (clg->a3 < rnd && rnd < clg->a2 + clg->a3) {
232
			clg->state = TX_IN_GAP_PERIOD;
233
		} else if (clg->a2 + clg->a3 < rnd) {
234
			clg->state = LOST_IN_GAP_PERIOD;
235 236 237
			return true;
		}
		break;
238 239
	case LOST_IN_BURST_PERIOD:
		clg->state = TX_IN_GAP_PERIOD;
240 241 242 243 244 245 246 247 248 249
		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)
 *
Lucas De Marchi's avatar
Lucas De Marchi committed
250
 * Makes a comparison between random number and the transition
251
 * probabilities outgoing from the current state, then decides the
Lucas De Marchi's avatar
Lucas De Marchi committed
252
 * next state. A second random number is extracted and the comparison
253 254 255 256 257 258 259 260
 * 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) {
261
	case GOOD_STATE:
262
		if (prandom_u32() < clg->a1)
263
			clg->state = BAD_STATE;
264
		if (prandom_u32() < clg->a4)
265
			return true;
266
		break;
267
	case BAD_STATE:
268
		if (prandom_u32() < clg->a2)
269
			clg->state = GOOD_STATE;
270
		if (prandom_u32() > clg->a3)
271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304
			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 */
}


Linus Torvalds's avatar
Linus Torvalds committed
305 306 307 308
/* 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.
 */
309 310 311
static psched_tdiff_t tabledist(psched_tdiff_t mu, psched_tdiff_t sigma,
				struct crndstate *state,
				const struct disttable *dist)
Linus Torvalds's avatar
Linus Torvalds committed
312
{
313 314 315
	psched_tdiff_t x;
	long t;
	u32 rnd;
Linus Torvalds's avatar
Linus Torvalds committed
316 317 318 319 320 321 322

	if (sigma == 0)
		return mu;

	rnd = get_crandom(state);

	/* default uniform distribution */
323
	if (dist == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
324 325 326 327 328 329 330 331 332 333 334 335
		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;
}

336
static psched_time_t packet_len_2_sched_time(unsigned int len, struct netem_sched_data *q)
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
337
{
338
	u64 ticks;
339

340 341 342 343 344 345 346 347 348 349 350 351 352
	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);
353
	return PSCHED_NS2TICKS(ticks);
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
354 355
}

356 357 358 359 360 361
static void tfifo_reset(struct Qdisc *sch)
{
	struct netem_sched_data *q = qdisc_priv(sch);
	struct rb_node *p;

	while ((p = rb_first(&q->t_root))) {
362
		struct sk_buff *skb = rb_to_skb(p);
363 364

		rb_erase(p, &q->t_root);
365
		rtnl_kfree_skbs(skb, skb);
366 367 368
	}
}

369
static void tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
Eric Dumazet's avatar
Eric Dumazet committed
370
{
371
	struct netem_sched_data *q = qdisc_priv(sch);
Eric Dumazet's avatar
Eric Dumazet committed
372
	psched_time_t tnext = netem_skb_cb(nskb)->time_to_send;
373
	struct rb_node **p = &q->t_root.rb_node, *parent = NULL;
Eric Dumazet's avatar
Eric Dumazet committed
374

375 376
	while (*p) {
		struct sk_buff *skb;
Eric Dumazet's avatar
Eric Dumazet committed
377

378
		parent = *p;
379
		skb = rb_to_skb(parent);
380
		if (tnext >= netem_skb_cb(skb)->time_to_send)
381 382 383
			p = &parent->rb_right;
		else
			p = &parent->rb_left;
Eric Dumazet's avatar
Eric Dumazet committed
384
	}
385 386
	rb_link_node(&nskb->rbnode, parent, p);
	rb_insert_color(&nskb->rbnode, &q->t_root);
387
	sch->q.qlen++;
Eric Dumazet's avatar
Eric Dumazet committed
388 389
}

390 391 392 393
/* netem can't properly corrupt a megapacket (like we get from GSO), so instead
 * when we statistically choose to corrupt one, we instead segment it, returning
 * the first packet to be corrupted, and re-enqueue the remaining frames
 */
394 395
static struct sk_buff *netem_segment(struct sk_buff *skb, struct Qdisc *sch,
				     struct sk_buff **to_free)
396 397 398 399 400 401 402
{
	struct sk_buff *segs;
	netdev_features_t features = netif_skb_features(skb);

	segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);

	if (IS_ERR_OR_NULL(segs)) {
403
		qdisc_drop(skb, sch, to_free);
404 405 406 407 408 409
		return NULL;
	}
	consume_skb(skb);
	return segs;
}

410 411 412 413 414 415 416 417 418 419
static void netem_enqueue_skb_head(struct qdisc_skb_head *qh, struct sk_buff *skb)
{
	skb->next = qh->head;

	if (!qh->head)
		qh->tail = skb;
	qh->head = skb;
	qh->qlen++;
}

420 421 422 423 424 425
/*
 * 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.
 */
426 427
static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch,
			 struct sk_buff **to_free)
Linus Torvalds's avatar
Linus Torvalds committed
428 429
{
	struct netem_sched_data *q = qdisc_priv(sch);
430 431
	/* We don't fill cb now as skb_unshare() may invalidate it */
	struct netem_skb_cb *cb;
432
	struct sk_buff *skb2;
433 434 435
	struct sk_buff *segs = NULL;
	unsigned int len = 0, last_len, prev_len = qdisc_pkt_len(skb);
	int nb = 0;
436
	int count = 1;
437
	int rc = NET_XMIT_SUCCESS;
Linus Torvalds's avatar
Linus Torvalds committed
438

439 440 441 442
	/* Random duplication */
	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
		++count;

443
	/* Drop packet? */
Eric Dumazet's avatar
Eric Dumazet committed
444 445
	if (loss_event(q)) {
		if (q->ecn && INET_ECN_set_ce(skb))
446
			qdisc_qstats_drop(sch); /* mark packet */
Eric Dumazet's avatar
Eric Dumazet committed
447 448 449
		else
			--count;
	}
450
	if (count == 0) {
451
		qdisc_qstats_drop(sch);
452
		__qdisc_drop(skb, to_free);
453
		return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds's avatar
Linus Torvalds committed
454 455
	}

456 457 458
	/* If a delay is expected, orphan the skb. (orphaning usually takes
	 * place at TX completion time, so _before_ the link transit delay)
	 */
459
	if (q->latency || q->jitter || q->rate)
460
		skb_orphan_partial(skb);
461

462 463 464 465 466 467
	/*
	 * 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) {
468
		struct Qdisc *rootq = qdisc_root(sch);
469 470
		u32 dupsave = q->duplicate; /* prevent duplicating a dup... */

471
		q->duplicate = 0;
472
		rootq->enqueue(skb2, rootq, to_free);
473
		q->duplicate = dupsave;
Linus Torvalds's avatar
Linus Torvalds committed
474 475
	}

476 477 478 479 480 481 482
	/*
	 * 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)) {
483
		if (skb_is_gso(skb)) {
484
			segs = netem_segment(skb, sch, to_free);
485 486 487 488 489 490 491 492 493
			if (!segs)
				return NET_XMIT_DROP;
		} else {
			segs = skb;
		}

		skb = segs;
		segs = segs->next;

494 495 496 497 498 499 500 501
		skb = skb_unshare(skb, GFP_ATOMIC);
		if (unlikely(!skb)) {
			qdisc_qstats_drop(sch);
			goto finish_segs;
		}
		if (skb->ip_summed == CHECKSUM_PARTIAL &&
		    skb_checksum_help(skb)) {
			qdisc_drop(skb, sch, to_free);
502 503
			goto finish_segs;
		}
504

505 506
		skb->data[prandom_u32() % skb_headlen(skb)] ^=
			1<<(prandom_u32() % 8);
507 508
	}

509
	if (unlikely(sch->q.qlen >= sch->limit))
510
		return qdisc_drop_all(skb, sch, to_free);
511

512
	qdisc_qstats_backlog_inc(sch, skb);
513

514
	cb = netem_skb_cb(skb);
Eric Dumazet's avatar
Eric Dumazet committed
515
	if (q->gap == 0 ||		/* not doing reordering */
516
	    q->counter < q->gap - 1 ||	/* inside last reordering gap */
517
	    q->reorder < get_crandom(&q->reorder_cor)) {
518
		psched_time_t now;
Stephen Hemminger's avatar
Stephen Hemminger committed
519 520 521 522 523
		psched_tdiff_t delay;

		delay = tabledist(q->latency, q->jitter,
				  &q->delay_cor, q->delay_dist);

524
		now = psched_get_time();
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
525 526

		if (q->rate) {
527 528 529 530 531 532 533 534
			struct netem_skb_cb *last = NULL;

			if (sch->q.tail)
				last = netem_skb_cb(sch->q.tail);
			if (q->t_root.rb_node) {
				struct sk_buff *t_skb;
				struct netem_skb_cb *t_last;

535
				t_skb = skb_rb_last(&q->t_root);
536 537 538 539 540 541
				t_last = netem_skb_cb(t_skb);
				if (!last ||
				    t_last->time_to_send > last->time_to_send) {
					last = t_last;
				}
			}
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
542

543
			if (last) {
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
544
				/*
545 546
				 * Last packet in queue is reference point (now),
				 * calculate this time bonus and subtract
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
547 548
				 * from delay.
				 */
549
				delay -= last->time_to_send - now;
550
				delay = max_t(psched_tdiff_t, 0, delay);
551
				now = last->time_to_send;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
552
			}
553

554
			delay += packet_len_2_sched_time(qdisc_pkt_len(skb), q);
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
555 556
		}

557
		cb->time_to_send = now + delay;
558
		cb->tstamp_save = skb->tstamp;
Linus Torvalds's avatar
Linus Torvalds committed
559
		++q->counter;
560
		tfifo_enqueue(skb, sch);
Linus Torvalds's avatar
Linus Torvalds committed
561
	} else {
562
		/*
563 564 565
		 * Do re-ordering by putting one out of N packets at the front
		 * of the queue.
		 */
566
		cb->time_to_send = psched_get_time();
567
		q->counter = 0;
568

569
		netem_enqueue_skb_head(&sch->q, skb);
570
		sch->qstats.requeues++;
571
	}
Linus Torvalds's avatar
Linus Torvalds committed
572

573 574 575 576 577 578 579
finish_segs:
	if (segs) {
		while (segs) {
			skb2 = segs->next;
			segs->next = NULL;
			qdisc_skb_cb(segs)->pkt_len = segs->len;
			last_len = segs->len;
580
			rc = qdisc_enqueue(segs, sch, to_free);
581 582 583 584 585 586 587 588 589 590 591 592 593
			if (rc != NET_XMIT_SUCCESS) {
				if (net_xmit_drop_count(rc))
					qdisc_qstats_drop(sch);
			} else {
				nb++;
				len += last_len;
			}
			segs = skb2;
		}
		sch->q.qlen += nb;
		if (nb > 1)
			qdisc_tree_reduce_backlog(sch, 1 - nb, prev_len - len);
	}
594
	return NET_XMIT_SUCCESS;
Linus Torvalds's avatar
Linus Torvalds committed
595 596 597 598 599 600
}

static struct sk_buff *netem_dequeue(struct Qdisc *sch)
{
	struct netem_sched_data *q = qdisc_priv(sch);
	struct sk_buff *skb;
601
	struct rb_node *p;
Linus Torvalds's avatar
Linus Torvalds committed
602

Eric Dumazet's avatar
Eric Dumazet committed
603
tfifo_dequeue:
604
	skb = __qdisc_dequeue_head(&sch->q);
605
	if (skb) {
606
		qdisc_qstats_backlog_dec(sch, skb);
607
deliver:
608 609 610 611 612
		qdisc_bstats_update(sch, skb);
		return skb;
	}
	p = rb_first(&q->t_root);
	if (p) {
613 614
		psched_time_t time_to_send;

615
		skb = rb_to_skb(p);
616 617

		/* if more time remaining? */
618 619
		time_to_send = netem_skb_cb(skb)->time_to_send;
		if (time_to_send <= psched_get_time()) {
620 621 622
			rb_erase(p, &q->t_root);

			sch->q.qlen--;
623
			qdisc_qstats_backlog_dec(sch, skb);
624 625 626
			skb->next = NULL;
			skb->prev = NULL;
			skb->tstamp = netem_skb_cb(skb)->tstamp_save;
627

628 629 630 631 632
#ifdef CONFIG_NET_CLS_ACT
			/*
			 * If it's at ingress let's pretend the delay is
			 * from the network (tstamp will be updated).
			 */
633
			if (skb->tc_redirected && skb->tc_from_ingress)
Thomas Gleixner's avatar
Thomas Gleixner committed
634
				skb->tstamp = 0;
635
#endif
636

Eric Dumazet's avatar
Eric Dumazet committed
637
			if (q->qdisc) {
Eric Dumazet's avatar
Eric Dumazet committed
638
				unsigned int pkt_len = qdisc_pkt_len(skb);
639 640
				struct sk_buff *to_free = NULL;
				int err;
Eric Dumazet's avatar
Eric Dumazet committed
641

642 643
				err = qdisc_enqueue(skb, q->qdisc, &to_free);
				kfree_skb_list(to_free);
Eric Dumazet's avatar
Eric Dumazet committed
644 645 646 647 648
				if (err != NET_XMIT_SUCCESS &&
				    net_xmit_drop_count(err)) {
					qdisc_qstats_drop(sch);
					qdisc_tree_reduce_backlog(sch, 1,
								  pkt_len);
Eric Dumazet's avatar
Eric Dumazet committed
649 650 651
				}
				goto tfifo_dequeue;
			}
652
			goto deliver;
Stephen Hemminger's avatar
Stephen Hemminger committed
653
		}
654

Eric Dumazet's avatar
Eric Dumazet committed
655 656 657 658 659
		if (q->qdisc) {
			skb = q->qdisc->ops->dequeue(q->qdisc);
			if (skb)
				goto deliver;
		}
660
		qdisc_watchdog_schedule(&q->watchdog, time_to_send);
661 662
	}

Eric Dumazet's avatar
Eric Dumazet committed
663 664 665 666 667
	if (q->qdisc) {
		skb = q->qdisc->ops->dequeue(q->qdisc);
		if (skb)
			goto deliver;
	}
668
	return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
669 670 671 672 673 674
}

static void netem_reset(struct Qdisc *sch)
{
	struct netem_sched_data *q = qdisc_priv(sch);

Eric Dumazet's avatar
Eric Dumazet committed
675
	qdisc_reset_queue(sch);
676
	tfifo_reset(sch);
Eric Dumazet's avatar
Eric Dumazet committed
677 678
	if (q->qdisc)
		qdisc_reset(q->qdisc);
679
	qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds's avatar
Linus Torvalds committed
680 681
}

682 683
static void dist_free(struct disttable *d)
{
WANG Cong's avatar
WANG Cong committed
684
	kvfree(d);
685 686
}

Linus Torvalds's avatar
Linus Torvalds committed
687 688 689 690
/*
 * Distribution data is a variable size payload containing
 * signed 16 bit values.
 */
691
static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr)
Linus Torvalds's avatar
Linus Torvalds committed
692 693
{
	struct netem_sched_data *q = qdisc_priv(sch);
694
	size_t n = nla_len(attr)/sizeof(__s16);
695
	const __s16 *data = nla_data(attr);
696
	spinlock_t *root_lock;
Linus Torvalds's avatar
Linus Torvalds committed
697 698 699
	struct disttable *d;
	int i;

700
	if (n > NETEM_DIST_MAX)
Linus Torvalds's avatar
Linus Torvalds committed
701 702
		return -EINVAL;

703
	d = kvmalloc(sizeof(struct disttable) + n * sizeof(s16), GFP_KERNEL);
Linus Torvalds's avatar
Linus Torvalds committed
704 705 706 707 708 709
	if (!d)
		return -ENOMEM;

	d->size = n;
	for (i = 0; i < n; i++)
		d->table[i] = data[i];
710

711
	root_lock = qdisc_root_sleeping_lock(sch);
712 713

	spin_lock_bh(root_lock);
714
	swap(q->delay_dist, d);
715
	spin_unlock_bh(root_lock);
716 717

	dist_free(d);
Linus Torvalds's avatar
Linus Torvalds committed
718 719 720
	return 0;
}

721
static void get_correlation(struct netem_sched_data *q, const struct nlattr *attr)
Linus Torvalds's avatar
Linus Torvalds committed
722
{
723
	const struct tc_netem_corr *c = nla_data(attr);
Linus Torvalds's avatar
Linus Torvalds committed
724 725 726 727 728 729

	init_crandom(&q->delay_cor, c->delay_corr);
	init_crandom(&q->loss_cor, c->loss_corr);
	init_crandom(&q->dup_cor, c->dup_corr);
}

730
static void get_reorder(struct netem_sched_data *q, const struct nlattr *attr)
731
{
732
	const struct tc_netem_reorder *r = nla_data(attr);
733 734 735 736 737

	q->reorder = r->probability;
	init_crandom(&q->reorder_cor, r->correlation);
}

738
static void get_corrupt(struct netem_sched_data *q, const struct nlattr *attr)
739
{
740
	const struct tc_netem_corrupt *r = nla_data(attr);
741 742 743 744 745

	q->corrupt = r->probability;
	init_crandom(&q->corrupt_cor, r->correlation);
}

746
static void get_rate(struct netem_sched_data *q, const struct nlattr *attr)
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
747 748 749 750
{
	const struct tc_netem_rate *r = nla_data(attr);

	q->rate = r->rate;
751 752
	q->packet_overhead = r->packet_overhead;
	q->cell_size = r->cell_size;
753
	q->cell_overhead = r->cell_overhead;
754 755
	if (q->cell_size)
		q->cell_size_reciprocal = reciprocal_value(q->cell_size);
756 757
	else
		q->cell_size_reciprocal = (struct reciprocal_value) { 0 };
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
758 759
}

760
static int get_loss_clg(struct netem_sched_data *q, const struct nlattr *attr)
761 762 763 764 765 766 767
{
	const struct nlattr *la;
	int rem;

	nla_for_each_nested(la, attr, rem) {
		u16 type = nla_type(la);

768
		switch (type) {
769 770 771
		case NETEM_LOSS_GI: {
			const struct tc_netem_gimodel *gi = nla_data(la);

772
			if (nla_len(la) < sizeof(struct tc_netem_gimodel)) {
773 774 775 776 777 778
				pr_info("netem: incorrect gi model size\n");
				return -EINVAL;
			}

			q->loss_model = CLG_4_STATES;

779
			q->clg.state = TX_IN_GAP_PERIOD;
780 781 782 783 784 785 786 787 788 789 790
			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);

791 792
			if (nla_len(la) < sizeof(struct tc_netem_gemodel)) {
				pr_info("netem: incorrect ge model size\n");
793 794 795 796
				return -EINVAL;
			}

			q->loss_model = CLG_GILB_ELL;
797
			q->clg.state = GOOD_STATE;
798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813
			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\n", type);
			return -EINVAL;
		}
	}

	return 0;
}

814 815 816 817
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) },
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
818
	[TCA_NETEM_RATE]	= { .len = sizeof(struct tc_netem_rate) },
819
	[TCA_NETEM_LOSS]	= { .type = NLA_NESTED },
Eric Dumazet's avatar
Eric Dumazet committed
820
	[TCA_NETEM_ECN]		= { .type = NLA_U32 },
821
	[TCA_NETEM_RATE64]	= { .type = NLA_U64 },
822 823
};

824 825 826 827 828
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);

829 830
	if (nested_len < 0) {
		pr_info("netem: invalid attributes len %d\n", nested_len);
831
		return -EINVAL;
832 833
	}

834 835
	if (nested_len >= nla_attr_size(0))
		return nla_parse(tb, maxtype, nla_data(nla) + NLA_ALIGN(len),
836
				 nested_len, policy, NULL);
837

838 839 840 841
	memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1));
	return 0;
}

842
/* Parse netlink message to set options */
843
static int netem_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds's avatar
Linus Torvalds committed
844 845
{
	struct netem_sched_data *q = qdisc_priv(sch);
846
	struct nlattr *tb[TCA_NETEM_MAX + 1];
Linus Torvalds's avatar
Linus Torvalds committed
847
	struct tc_netem_qopt *qopt;
848 849
	struct clgstate old_clg;
	int old_loss_model = CLG_RANDOM;
Linus Torvalds's avatar
Linus Torvalds committed
850
	int ret;
851

852
	if (opt == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
853 854
		return -EINVAL;

855 856
	qopt = nla_data(opt);
	ret = parse_attr(tb, TCA_NETEM_MAX, opt, netem_policy, sizeof(*qopt));
857 858 859
	if (ret < 0)
		return ret;

860 861 862 863 864
	/* backup q->clg and q->loss_model */
	old_clg = q->clg;
	old_loss_model = q->loss_model;

	if (tb[TCA_NETEM_LOSS]) {
865
		ret = get_loss_clg(q, tb[TCA_NETEM_LOSS]);
866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886
		if (ret) {
			q->loss_model = old_loss_model;
			return ret;
		}
	} else {
		q->loss_model = CLG_RANDOM;
	}

	if (tb[TCA_NETEM_DELAY_DIST]) {
		ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]);
		if (ret) {
			/* recover clg and loss_model, in case of
			 * q->clg and q->loss_model were modified
			 * in get_loss_clg()
			 */
			q->clg = old_clg;
			q->loss_model = old_loss_model;
			return ret;
		}
	}

Eric Dumazet's avatar
Eric Dumazet committed
887
	sch->limit = qopt->limit;
888

Linus Torvalds's avatar
Linus Torvalds committed
889 890 891 892
	q->latency = qopt->latency;
	q->jitter = qopt->jitter;
	q->limit = qopt->limit;
	q->gap = qopt->gap;
893
	q->counter = 0;
Linus Torvalds's avatar
Linus Torvalds committed
894 895 896
	q->loss = qopt->loss;
	q->duplicate = qopt->duplicate;

Stephen Hemminger's avatar
Stephen Hemminger committed
897 898
	/* for compatibility with earlier versions.
	 * if gap is set, need to assume 100% probability
899
	 */
900 901
	if (q->gap)
		q->reorder = ~0;
902

903
	if (tb[TCA_NETEM_CORR])
904
		get_correlation(q, tb[TCA_NETEM_CORR]);
Linus Torvalds's avatar
Linus Torvalds committed
905

906
	if (tb[TCA_NETEM_REORDER])
907
		get_reorder(q, tb[TCA_NETEM_REORDER]);
Linus Torvalds's avatar
Linus Torvalds committed
908

909
	if (tb[TCA_NETEM_CORRUPT])
910
		get_corrupt(q, tb[TCA_NETEM_CORRUPT]);
Linus Torvalds's avatar
Linus Torvalds committed
911

Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
912
	if (tb[TCA_NETEM_RATE])
913
		get_rate(q, tb[TCA_NETEM_RATE]);
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
914

915 916 917 918
	if (tb[TCA_NETEM_RATE64])
		q->rate = max_t(u64, q->rate,
				nla_get_u64(tb[TCA_NETEM_RATE64]));

Eric Dumazet's avatar
Eric Dumazet committed
919 920 921
	if (tb[TCA_NETEM_ECN])
		q->ecn = nla_get_u32(tb[TCA_NETEM_ECN]);

922
	return ret;
Linus Torvalds's avatar
Linus Torvalds committed
923 924
}

925
static int netem_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds's avatar
Linus Torvalds committed
926 927 928 929
{
	struct netem_sched_data *q = qdisc_priv(sch);
	int ret;

930 931
	qdisc_watchdog_init(&q->watchdog, sch);

Linus Torvalds's avatar
Linus Torvalds committed
932 933 934
	if (!opt)
		return -EINVAL;

935
	q->loss_model = CLG_RANDOM;
Linus Torvalds's avatar
Linus Torvalds committed
936
	ret = netem_change(sch, opt);
Eric Dumazet's avatar
Eric Dumazet committed
937
	if (ret)
938
		pr_info("netem: change failed\n");
Linus Torvalds's avatar
Linus Torvalds committed
939 940 941 942 943 944 945
	return ret;
}

static void netem_destroy(struct Qdisc *sch)
{
	struct netem_sched_data *q = qdisc_priv(sch);

946
	qdisc_watchdog_cancel(&q->watchdog);
Eric Dumazet's avatar
Eric Dumazet committed
947 948
	if (q->qdisc)
		qdisc_destroy(q->qdisc);
949
	dist_free(q->delay_dist);
Linus Torvalds's avatar
Linus Torvalds committed
950 951
}

952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975
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,
		};

976 977
		if (nla_put(skb, NETEM_LOSS_GI, sizeof(gi), &gi))
			goto nla_put_failure;
978 979 980 981 982 983 984 985 986 987
		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,
		};

988 989
		if (nla_put(skb, NETEM_LOSS_GE, sizeof(ge), &ge))
			goto nla_put_failure;
990 991 992 993 994 995 996 997 998 999 1000 1001
		break;
	}
	}

	nla_nest_end(skb, nest);
	return 0;

nla_put_failure:
	nla_nest_cancel(skb, nest);
	return -1;
}

Linus Torvalds's avatar
Linus Torvalds committed
1002 1003 1004
static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
{
	const struct netem_sched_data *q = qdisc_priv(sch);
stephen hemminger's avatar
stephen hemminger committed
1005
	struct nlattr *nla = (struct nlattr *) skb_tail_pointer(skb);
Linus Torvalds's avatar
Linus Torvalds committed
1006 1007
	struct tc_netem_qopt qopt;
	struct tc_netem_corr cor;
1008
	struct tc_netem_reorder reorder;
1009
	struct tc_netem_corrupt corrupt;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
1010
	struct tc_netem_rate rate;
Linus Torvalds's avatar
Linus Torvalds committed
1011 1012 1013 1014 1015 1016 1017

	qopt.latency = q->latency;
	qopt.jitter = q->jitter;
	qopt.limit = q->limit;
	qopt.loss = q->loss;
	qopt.gap = q->gap;
	qopt.duplicate = q->duplicate;
1018 1019
	if (nla_put(skb, TCA_OPTIONS, sizeof(qopt), &qopt))
		goto nla_put_failure;
Linus Torvalds's avatar
Linus Torvalds committed
1020 1021 1022 1023

	cor.delay_corr = q->delay_cor.rho;
	cor.loss_corr = q->loss_cor.rho;
	cor.dup_corr = q->dup_cor.rho;
1024 1025
	if (nla_put(skb, TCA_NETEM_CORR, sizeof(cor), &cor))
		goto nla_put_failure;
1026 1027 1028

	reorder.probability = q->reorder;
	reorder.correlation = q->reorder_cor.rho;
1029 1030
	if (nla_put(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder))
		goto nla_put_failure;
1031

1032 1033
	corrupt.probability = q->corrupt;
	corrupt.correlation = q->corrupt_cor.rho;
1034 1035
	if (nla_put(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt))
		goto nla_put_failure;
1036

1037
	if (q->rate >= (1ULL << 32)) {
1038 1039
		if (nla_put_u64_64bit(skb, TCA_NETEM_RATE64, q->rate,
				      TCA_NETEM_PAD))
1040 1041 1042 1043 1044
			goto nla_put_failure;
		rate.rate = ~0U;
	} else {
		rate.rate = q->rate;
	}
1045 1046 1047
	rate.packet_overhead = q->packet_overhead;
	rate.cell_size = q->cell_size;
	rate.cell_overhead = q->cell_overhead;
1048 1049
	if (nla_put(skb, TCA_NETEM_RATE, sizeof(rate), &rate))
		goto nla_put_failure;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
1050

Eric Dumazet's avatar
Eric Dumazet committed
1051 1052 1053
	if (q->ecn && nla_put_u32(skb, TCA_NETEM_ECN, q->ecn))
		goto nla_put_failure;

1054 1055 1056
	if (dump_loss_model(q, skb) != 0)
		goto nla_put_failure;

stephen hemminger's avatar
stephen hemminger committed
1057
	return nla_nest_end(skb, nla);
Linus Torvalds's avatar
Linus Torvalds committed
1058

1059
nla_put_failure:
stephen hemminger's avatar
stephen hemminger committed
1060
	nlmsg_trim(skb, nla);
Linus Torvalds's avatar
Linus Torvalds committed
1061 1062 1063
	return -1;
}

1064 1065 1066 1067 1068
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);

Eric Dumazet's avatar
Eric Dumazet committed
1069
	if (cl != 1 || !q->qdisc) 	/* only one class */
1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082
		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);

1083
	*old = qdisc_replace(sch, new, &q->qdisc);
1084 1085 1086 1087 1088 1089 1090 1091 1092
	return 0;
}

static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg)
{
	struct netem_sched_data *q = qdisc_priv(sch);
	return q->qdisc;
}

1093
static unsigned long netem_find(struct Qdisc *sch, u32 classid)
1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112
{
	return 1;
}

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,
1113
	.find		=	netem_find,
1114 1115 1116 1117
	.walk		=	netem_walk,
	.dump		=	netem_dump_class,
};

1118
static struct Qdisc_ops netem_qdisc_ops __read_mostly = {
Linus Torvalds's avatar
Linus Torvalds committed
1119
	.id		=	"netem",
1120
	.cl_ops		=	&netem_class_ops,
Linus Torvalds's avatar
Linus Torvalds committed
1121 1122 1123
	.priv_size	=	sizeof(struct netem_sched_data),
	.enqueue	=	netem_enqueue,
	.dequeue	=	netem_dequeue,
1124
	.peek		=	qdisc_peek_dequeued,
Linus Torvalds's avatar
Linus Torvalds committed
1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135
	.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)
{
1136
	pr_info("netem: version " VERSION "\n");
Linus Torvalds's avatar
Linus Torvalds committed
1137 1138 1139 1140 1141 1142 1143 1144 1145
	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");