sch_netem.c 25.4 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;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
91
	u32 rate;
92 93 94 95
	s32 packet_overhead;
	u32 cell_size;
	u32 cell_size_reciprocal;
	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 113 114 115 116 117 118 119 120 121 122 123 124 125

	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;

Linus Torvalds's avatar
Linus Torvalds committed
126 127
};

Eric Dumazet's avatar
Eric Dumazet committed
128 129 130
/* Time stamp put into socket buffer control block
 * Only valid when skbs are in our internal t(ime)fifo queue.
 */
Linus Torvalds's avatar
Linus Torvalds committed
131 132
struct netem_skb_cb {
	psched_time_t	time_to_send;
133
	ktime_t		tstamp_save;
Linus Torvalds's avatar
Linus Torvalds committed
134 135
};

136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
/* Because space in skb->cb[] is tight, netem overloads skb->next/prev/tstamp
 * to hold a rb_node structure.
 *
 * If struct sk_buff layout is changed, the following checks will complain.
 */
static struct rb_node *netem_rb_node(struct sk_buff *skb)
{
	BUILD_BUG_ON(offsetof(struct sk_buff, next) != 0);
	BUILD_BUG_ON(offsetof(struct sk_buff, prev) !=
		     offsetof(struct sk_buff, next) + sizeof(skb->next));
	BUILD_BUG_ON(offsetof(struct sk_buff, tstamp) !=
		     offsetof(struct sk_buff, prev) + sizeof(skb->prev));
	BUILD_BUG_ON(sizeof(struct rb_node) > sizeof(skb->next) +
					      sizeof(skb->prev) +
					      sizeof(skb->tstamp));
	return (struct rb_node *)&skb->next;
}

static struct sk_buff *netem_rb_to_skb(struct rb_node *rb)
{
	return (struct sk_buff *)rb;
}

159 160
static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb)
{
161
	/* we assume we can use skb next/prev/tstamp as storage for rb_node */
162
	qdisc_cb_private_validate(skb, sizeof(struct netem_skb_cb));
163
	return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data;
164 165
}

Linus Torvalds's avatar
Linus Torvalds committed
166 167 168 169 170 171 172 173 174 175 176 177 178
/* 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.
 */
179
static u32 get_crandom(struct crndstate *state)
Linus Torvalds's avatar
Linus Torvalds committed
180 181 182 183
{
	u64 value, rho;
	unsigned long answer;

Stephen Hemminger's avatar
Stephen Hemminger committed
184
	if (state->rho == 0)	/* no correlation */
Linus Torvalds's avatar
Linus Torvalds committed
185 186 187 188 189 190 191 192 193
		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;
}

194 195 196 197 198 199 200 201 202 203
/* 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();

	/*
Lucas De Marchi's avatar
Lucas De Marchi committed
204
	 * Makes a comparison between rnd and the transition
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 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
	 * 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)
 *
Lucas De Marchi's avatar
Lucas De Marchi committed
256
 * Makes a comparison between random number and the transition
257
 * probabilities outgoing from the current state, then decides the
Lucas De Marchi's avatar
Lucas De Marchi committed
258
 * next state. A second random number is extracted and the comparison
259 260 261 262 263 264 265 266 267 268 269 270 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 305 306 307 308 309
 * 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 */
}


Linus Torvalds's avatar
Linus Torvalds committed
310 311 312 313
/* 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.
 */
314 315 316
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
317
{
318 319 320
	psched_tdiff_t x;
	long t;
	u32 rnd;
Linus Torvalds's avatar
Linus Torvalds committed
321 322 323 324 325 326 327

	if (sigma == 0)
		return mu;

	rnd = get_crandom(state);

	/* default uniform distribution */
328
	if (dist == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
329 330 331 332 333 334 335 336 337 338 339 340
		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;
}

341
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
342
{
343
	u64 ticks;
344

345 346 347 348 349 350 351 352 353 354 355 356 357
	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);
358
	return PSCHED_NS2TICKS(ticks);
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
359 360
}

361
static void tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
Eric Dumazet's avatar
Eric Dumazet committed
362
{
363
	struct netem_sched_data *q = qdisc_priv(sch);
Eric Dumazet's avatar
Eric Dumazet committed
364
	psched_time_t tnext = netem_skb_cb(nskb)->time_to_send;
365
	struct rb_node **p = &q->t_root.rb_node, *parent = NULL;
Eric Dumazet's avatar
Eric Dumazet committed
366

367 368
	while (*p) {
		struct sk_buff *skb;
Eric Dumazet's avatar
Eric Dumazet committed
369

370 371
		parent = *p;
		skb = netem_rb_to_skb(parent);
372
		if (tnext >= netem_skb_cb(skb)->time_to_send)
373 374 375
			p = &parent->rb_right;
		else
			p = &parent->rb_left;
Eric Dumazet's avatar
Eric Dumazet committed
376
	}
377 378 379
	rb_link_node(netem_rb_node(nskb), parent, p);
	rb_insert_color(netem_rb_node(nskb), &q->t_root);
	sch->q.qlen++;
Eric Dumazet's avatar
Eric Dumazet committed
380 381
}

382 383 384 385 386 387
/*
 * 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.
 */
Linus Torvalds's avatar
Linus Torvalds committed
388 389 390
static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
	struct netem_sched_data *q = qdisc_priv(sch);
391 392
	/* We don't fill cb now as skb_unshare() may invalidate it */
	struct netem_skb_cb *cb;
393 394
	struct sk_buff *skb2;
	int count = 1;
Linus Torvalds's avatar
Linus Torvalds committed
395

396 397 398 399
	/* Random duplication */
	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
		++count;

400
	/* Drop packet? */
Eric Dumazet's avatar
Eric Dumazet committed
401 402 403 404 405 406
	if (loss_event(q)) {
		if (q->ecn && INET_ECN_set_ce(skb))
			sch->qstats.drops++; /* mark packet */
		else
			--count;
	}
407
	if (count == 0) {
Linus Torvalds's avatar
Linus Torvalds committed
408 409
		sch->qstats.drops++;
		kfree_skb(skb);
410
		return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds's avatar
Linus Torvalds committed
411 412
	}

413 414 415 416
	/* If a delay is expected, orphan the skb. (orphaning usually takes
	 * place at TX completion time, so _before_ the link transit delay)
	 */
	if (q->latency || q->jitter)
417
		skb_orphan_partial(skb);
418

419 420 421 422 423 424
	/*
	 * 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) {
425
		struct Qdisc *rootq = qdisc_root(sch);
426 427 428
		u32 dupsave = q->duplicate; /* prevent duplicating a dup... */
		q->duplicate = 0;

429
		qdisc_enqueue_root(skb2, rootq);
430
		q->duplicate = dupsave;
Linus Torvalds's avatar
Linus Torvalds committed
431 432
	}

433 434 435 436 437 438 439
	/*
	 * 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)) {
440 441
		if (!(skb = skb_unshare(skb, GFP_ATOMIC)) ||
		    (skb->ip_summed == CHECKSUM_PARTIAL &&
Eric Dumazet's avatar
Eric Dumazet committed
442 443
		     skb_checksum_help(skb)))
			return qdisc_drop(skb, sch);
444 445 446 447

		skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8);
	}

448 449 450 451 452
	if (unlikely(skb_queue_len(&sch->q) >= sch->limit))
		return qdisc_reshape_fail(skb, sch);

	sch->qstats.backlog += qdisc_pkt_len(skb);

453
	cb = netem_skb_cb(skb);
Eric Dumazet's avatar
Eric Dumazet committed
454
	if (q->gap == 0 ||		/* not doing reordering */
455
	    q->counter < q->gap - 1 ||	/* inside last reordering gap */
456
	    q->reorder < get_crandom(&q->reorder_cor)) {
457
		psched_time_t now;
Stephen Hemminger's avatar
Stephen Hemminger committed
458 459 460 461 462
		psched_tdiff_t delay;

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

463
		now = psched_get_time();
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
464 465

		if (q->rate) {
466
			struct sk_buff *last;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
467

468 469 470 471 472
			if (!skb_queue_empty(&sch->q))
				last = skb_peek_tail(&sch->q);
			else
				last = netem_rb_to_skb(rb_last(&q->t_root));
			if (last) {
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
473
				/*
474 475
				 * Last packet in queue is reference point (now),
				 * calculate this time bonus and subtract
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
476 477
				 * from delay.
				 */
478
				delay -= netem_skb_cb(last)->time_to_send - now;
479
				delay = max_t(psched_tdiff_t, 0, delay);
480
				now = netem_skb_cb(last)->time_to_send;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
481
			}
482 483

			delay += packet_len_2_sched_time(skb->len, q);
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
484 485
		}

486
		cb->time_to_send = now + delay;
487
		cb->tstamp_save = skb->tstamp;
Linus Torvalds's avatar
Linus Torvalds committed
488
		++q->counter;
489
		tfifo_enqueue(skb, sch);
Linus Torvalds's avatar
Linus Torvalds committed
490
	} else {
491
		/*
492 493 494
		 * Do re-ordering by putting one out of N packets at the front
		 * of the queue.
		 */
495
		cb->time_to_send = psched_get_time();
496
		q->counter = 0;
497

Eric Dumazet's avatar
Eric Dumazet committed
498
		__skb_queue_head(&sch->q, skb);
499
		sch->qstats.requeues++;
500
	}
Linus Torvalds's avatar
Linus Torvalds committed
501

502
	return NET_XMIT_SUCCESS;
Linus Torvalds's avatar
Linus Torvalds committed
503 504
}

Eric Dumazet's avatar
Eric Dumazet committed
505
static unsigned int netem_drop(struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
506 507
{
	struct netem_sched_data *q = qdisc_priv(sch);
Eric Dumazet's avatar
Eric Dumazet committed
508
	unsigned int len;
Linus Torvalds's avatar
Linus Torvalds committed
509

Eric Dumazet's avatar
Eric Dumazet committed
510
	len = qdisc_queue_drop(sch);
511 512 513 514 515 516 517 518 519 520 521 522

	if (!len) {
		struct rb_node *p = rb_first(&q->t_root);

		if (p) {
			struct sk_buff *skb = netem_rb_to_skb(p);

			rb_erase(p, &q->t_root);
			sch->q.qlen--;
			skb->next = NULL;
			skb->prev = NULL;
			len = qdisc_pkt_len(skb);
523
			sch->qstats.backlog -= len;
524 525 526
			kfree_skb(skb);
		}
	}
Eric Dumazet's avatar
Eric Dumazet committed
527 528 529
	if (!len && q->qdisc && q->qdisc->ops->drop)
	    len = q->qdisc->ops->drop(q->qdisc);
	if (len)
Linus Torvalds's avatar
Linus Torvalds committed
530
		sch->qstats.drops++;
Eric Dumazet's avatar
Eric Dumazet committed
531

Linus Torvalds's avatar
Linus Torvalds committed
532 533 534 535 536 537 538
	return len;
}

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

541
	if (qdisc_is_throttled(sch))
542 543
		return NULL;

Eric Dumazet's avatar
Eric Dumazet committed
544
tfifo_dequeue:
545
	skb = __skb_dequeue(&sch->q);
546
	if (skb) {
547 548 549 550 551 552 553 554
deliver:
		sch->qstats.backlog -= qdisc_pkt_len(skb);
		qdisc_unthrottled(sch);
		qdisc_bstats_update(sch, skb);
		return skb;
	}
	p = rb_first(&q->t_root);
	if (p) {
555 556
		psched_time_t time_to_send;

557
		skb = netem_rb_to_skb(p);
558 559

		/* if more time remaining? */
560 561
		time_to_send = netem_skb_cb(skb)->time_to_send;
		if (time_to_send <= psched_get_time()) {
562 563 564 565 566 567
			rb_erase(p, &q->t_root);

			sch->q.qlen--;
			skb->next = NULL;
			skb->prev = NULL;
			skb->tstamp = netem_skb_cb(skb)->tstamp_save;
568

569 570 571 572 573 574 575 576
#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
577

Eric Dumazet's avatar
Eric Dumazet committed
578 579 580 581 582 583 584 585 586 587 588
			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;
			}
589
			goto deliver;
Stephen Hemminger's avatar
Stephen Hemminger committed
590
		}
591

Eric Dumazet's avatar
Eric Dumazet committed
592 593 594 595 596
		if (q->qdisc) {
			skb = q->qdisc->ops->dequeue(q->qdisc);
			if (skb)
				goto deliver;
		}
597
		qdisc_watchdog_schedule(&q->watchdog, time_to_send);
598 599
	}

Eric Dumazet's avatar
Eric Dumazet committed
600 601 602 603 604
	if (q->qdisc) {
		skb = q->qdisc->ops->dequeue(q->qdisc);
		if (skb)
			goto deliver;
	}
605
	return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
606 607 608 609 610 611
}

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

Eric Dumazet's avatar
Eric Dumazet committed
612 613 614
	qdisc_reset_queue(sch);
	if (q->qdisc)
		qdisc_reset(q->qdisc);
615
	qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds's avatar
Linus Torvalds committed
616 617
}

618 619 620 621 622 623 624 625 626 627
static void dist_free(struct disttable *d)
{
	if (d) {
		if (is_vmalloc_addr(d))
			vfree(d);
		else
			kfree(d);
	}
}

Linus Torvalds's avatar
Linus Torvalds committed
628 629 630 631
/*
 * Distribution data is a variable size payload containing
 * signed 16 bit values.
 */
632
static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr)
Linus Torvalds's avatar
Linus Torvalds committed
633 634
{
	struct netem_sched_data *q = qdisc_priv(sch);
635
	size_t n = nla_len(attr)/sizeof(__s16);
636
	const __s16 *data = nla_data(attr);
637
	spinlock_t *root_lock;
Linus Torvalds's avatar
Linus Torvalds committed
638 639
	struct disttable *d;
	int i;
640
	size_t s;
Linus Torvalds's avatar
Linus Torvalds committed
641

642
	if (n > NETEM_DIST_MAX)
Linus Torvalds's avatar
Linus Torvalds committed
643 644
		return -EINVAL;

645
	s = sizeof(struct disttable) + n * sizeof(s16);
646
	d = kmalloc(s, GFP_KERNEL | __GFP_NOWARN);
647 648
	if (!d)
		d = vmalloc(s);
Linus Torvalds's avatar
Linus Torvalds committed
649 650 651 652 653 654
	if (!d)
		return -ENOMEM;

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

656
	root_lock = qdisc_root_sleeping_lock(sch);
657 658

	spin_lock_bh(root_lock);
659
	swap(q->delay_dist, d);
660
	spin_unlock_bh(root_lock);
661 662

	dist_free(d);
Linus Torvalds's avatar
Linus Torvalds committed
663 664 665
	return 0;
}

666
static void get_correlation(struct Qdisc *sch, const struct nlattr *attr)
Linus Torvalds's avatar
Linus Torvalds committed
667 668
{
	struct netem_sched_data *q = qdisc_priv(sch);
669
	const struct tc_netem_corr *c = nla_data(attr);
Linus Torvalds's avatar
Linus Torvalds committed
670 671 672 673 674 675

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

676
static void get_reorder(struct Qdisc *sch, const struct nlattr *attr)
677 678
{
	struct netem_sched_data *q = qdisc_priv(sch);
679
	const struct tc_netem_reorder *r = nla_data(attr);
680 681 682 683 684

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

685
static void get_corrupt(struct Qdisc *sch, const struct nlattr *attr)
686 687
{
	struct netem_sched_data *q = qdisc_priv(sch);
688
	const struct tc_netem_corrupt *r = nla_data(attr);
689 690 691 692 693

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

Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
694 695 696 697 698 699
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;
700 701 702 703 704
	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;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
705 706
}

707 708 709 710 711 712 713 714 715 716 717 718 719
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);

720
			if (nla_len(la) < sizeof(struct tc_netem_gimodel)) {
721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738
				pr_info("netem: incorrect gi model size\n");
				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);

739 740
			if (nla_len(la) < sizeof(struct tc_netem_gemodel)) {
				pr_info("netem: incorrect ge model size\n");
741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761
				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\n", type);
			return -EINVAL;
		}
	}

	return 0;
}

762 763 764 765
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
766
	[TCA_NETEM_RATE]	= { .len = sizeof(struct tc_netem_rate) },
767
	[TCA_NETEM_LOSS]	= { .type = NLA_NESTED },
Eric Dumazet's avatar
Eric Dumazet committed
768
	[TCA_NETEM_ECN]		= { .type = NLA_U32 },
769 770
};

771 772 773 774 775
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);

776 777
	if (nested_len < 0) {
		pr_info("netem: invalid attributes len %d\n", nested_len);
778
		return -EINVAL;
779 780
	}

781 782 783
	if (nested_len >= nla_attr_size(0))
		return nla_parse(tb, maxtype, nla_data(nla) + NLA_ALIGN(len),
				 nested_len, policy);
784

785 786 787 788
	memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1));
	return 0;
}

789
/* Parse netlink message to set options */
790
static int netem_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds's avatar
Linus Torvalds committed
791 792
{
	struct netem_sched_data *q = qdisc_priv(sch);
793
	struct nlattr *tb[TCA_NETEM_MAX + 1];
Linus Torvalds's avatar
Linus Torvalds committed
794 795
	struct tc_netem_qopt *qopt;
	int ret;
796

797
	if (opt == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
798 799
		return -EINVAL;

800 801
	qopt = nla_data(opt);
	ret = parse_attr(tb, TCA_NETEM_MAX, opt, netem_policy, sizeof(*qopt));
802 803 804
	if (ret < 0)
		return ret;

Eric Dumazet's avatar
Eric Dumazet committed
805
	sch->limit = qopt->limit;
806

Linus Torvalds's avatar
Linus Torvalds committed
807 808 809 810
	q->latency = qopt->latency;
	q->jitter = qopt->jitter;
	q->limit = qopt->limit;
	q->gap = qopt->gap;
811
	q->counter = 0;
Linus Torvalds's avatar
Linus Torvalds committed
812 813 814
	q->loss = qopt->loss;
	q->duplicate = qopt->duplicate;

Stephen Hemminger's avatar
Stephen Hemminger committed
815 816
	/* for compatibility with earlier versions.
	 * if gap is set, need to assume 100% probability
817
	 */
818 819
	if (q->gap)
		q->reorder = ~0;
820

821 822
	if (tb[TCA_NETEM_CORR])
		get_correlation(sch, tb[TCA_NETEM_CORR]);
Linus Torvalds's avatar
Linus Torvalds committed
823

824 825 826 827 828
	if (tb[TCA_NETEM_DELAY_DIST]) {
		ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]);
		if (ret)
			return ret;
	}
829

830 831
	if (tb[TCA_NETEM_REORDER])
		get_reorder(sch, tb[TCA_NETEM_REORDER]);
Linus Torvalds's avatar
Linus Torvalds committed
832

833 834
	if (tb[TCA_NETEM_CORRUPT])
		get_corrupt(sch, tb[TCA_NETEM_CORRUPT]);
Linus Torvalds's avatar
Linus Torvalds committed
835

Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
836 837 838
	if (tb[TCA_NETEM_RATE])
		get_rate(sch, tb[TCA_NETEM_RATE]);

Eric Dumazet's avatar
Eric Dumazet committed
839 840 841
	if (tb[TCA_NETEM_ECN])
		q->ecn = nla_get_u32(tb[TCA_NETEM_ECN]);

842 843 844 845 846
	q->loss_model = CLG_RANDOM;
	if (tb[TCA_NETEM_LOSS])
		ret = get_loss_clg(sch, tb[TCA_NETEM_LOSS]);

	return ret;
Linus Torvalds's avatar
Linus Torvalds committed
847 848
}

849
static int netem_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds's avatar
Linus Torvalds committed
850 851 852 853 854 855 856
{
	struct netem_sched_data *q = qdisc_priv(sch);
	int ret;

	if (!opt)
		return -EINVAL;

857
	qdisc_watchdog_init(&q->watchdog, sch);
Linus Torvalds's avatar
Linus Torvalds committed
858

859
	q->loss_model = CLG_RANDOM;
Linus Torvalds's avatar
Linus Torvalds committed
860
	ret = netem_change(sch, opt);
Eric Dumazet's avatar
Eric Dumazet committed
861
	if (ret)
862
		pr_info("netem: change failed\n");
Linus Torvalds's avatar
Linus Torvalds committed
863 864 865 866 867 868 869
	return ret;
}

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

870
	qdisc_watchdog_cancel(&q->watchdog);
Eric Dumazet's avatar
Eric Dumazet committed
871 872
	if (q->qdisc)
		qdisc_destroy(q->qdisc);
873
	dist_free(q->delay_dist);
Linus Torvalds's avatar
Linus Torvalds committed
874 875
}

876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899
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,
		};

900 901
		if (nla_put(skb, NETEM_LOSS_GI, sizeof(gi), &gi))
			goto nla_put_failure;
902 903 904 905 906 907 908 909 910 911
		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,
		};

912 913
		if (nla_put(skb, NETEM_LOSS_GE, sizeof(ge), &ge))
			goto nla_put_failure;
914 915 916 917 918 919 920 921 922 923 924 925
		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
926 927 928
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
929
	struct nlattr *nla = (struct nlattr *) skb_tail_pointer(skb);
Linus Torvalds's avatar
Linus Torvalds committed
930 931
	struct tc_netem_qopt qopt;
	struct tc_netem_corr cor;
932
	struct tc_netem_reorder reorder;
933
	struct tc_netem_corrupt corrupt;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
934
	struct tc_netem_rate rate;
Linus Torvalds's avatar
Linus Torvalds committed
935 936 937 938 939 940 941

	qopt.latency = q->latency;
	qopt.jitter = q->jitter;
	qopt.limit = q->limit;
	qopt.loss = q->loss;
	qopt.gap = q->gap;
	qopt.duplicate = q->duplicate;
942 943
	if (nla_put(skb, TCA_OPTIONS, sizeof(qopt), &qopt))
		goto nla_put_failure;
Linus Torvalds's avatar
Linus Torvalds committed
944 945 946 947

	cor.delay_corr = q->delay_cor.rho;
	cor.loss_corr = q->loss_cor.rho;
	cor.dup_corr = q->dup_cor.rho;
948 949
	if (nla_put(skb, TCA_NETEM_CORR, sizeof(cor), &cor))
		goto nla_put_failure;
950 951 952

	reorder.probability = q->reorder;
	reorder.correlation = q->reorder_cor.rho;
953 954
	if (nla_put(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder))
		goto nla_put_failure;
955

956 957
	corrupt.probability = q->corrupt;
	corrupt.correlation = q->corrupt_cor.rho;
958 959
	if (nla_put(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt))
		goto nla_put_failure;
960

Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
961
	rate.rate = q->rate;
962 963 964
	rate.packet_overhead = q->packet_overhead;
	rate.cell_size = q->cell_size;
	rate.cell_overhead = q->cell_overhead;
965 966
	if (nla_put(skb, TCA_NETEM_RATE, sizeof(rate), &rate))
		goto nla_put_failure;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
967

Eric Dumazet's avatar
Eric Dumazet committed
968 969 970
	if (q->ecn && nla_put_u32(skb, TCA_NETEM_ECN, q->ecn))
		goto nla_put_failure;

971 972 973
	if (dump_loss_model(q, skb) != 0)
		goto nla_put_failure;

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

976
nla_put_failure:
stephen hemminger's avatar
stephen hemminger committed
977
	nlmsg_trim(skb, nla);
Linus Torvalds's avatar
Linus Torvalds committed
978 979 980
	return -1;
}

981 982 983 984 985
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
986
	if (cl != 1 || !q->qdisc) 	/* only one class */
987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002
		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);

	sch_tree_lock(sch);
	*old = q->qdisc;
	q->qdisc = new;
Eric Dumazet's avatar
Eric Dumazet committed
1003 1004 1005 1006
	if (*old) {
		qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
		qdisc_reset(*old);
	}
1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
	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,
};

1048
static struct Qdisc_ops netem_qdisc_ops __read_mostly = {
Linus Torvalds's avatar
Linus Torvalds committed
1049
	.id		=	"netem",
1050
	.cl_ops		=	&netem_class_ops,
Linus Torvalds's avatar
Linus Torvalds committed
1051 1052 1053
	.priv_size	=	sizeof(struct netem_sched_data),
	.enqueue	=	netem_enqueue,
	.dequeue	=	netem_dequeue,
1054
	.peek		=	qdisc_peek_dequeued,
Linus Torvalds's avatar
Linus Torvalds committed
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066
	.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)
{
1067
	pr_info("netem: version " VERSION "\n");
Linus Torvalds's avatar
Linus Torvalds committed
1068 1069 1070 1071 1072 1073 1074 1075 1076
	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");