sch_netem.c 24 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>
Linus Torvalds's avatar
Linus Torvalds committed
26

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

31
#define VERSION "1.3"
32

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

     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
68 69 70
*/

struct netem_sched_data {
Eric Dumazet's avatar
Eric Dumazet committed
71 72 73
	/* internal t(ime)fifo qdisc uses sch->q and sch->limit */

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

76
	struct qdisc_watchdog watchdog;
Linus Torvalds's avatar
Linus Torvalds committed
77

78 79 80
	psched_tdiff_t latency;
	psched_tdiff_t jitter;

Linus Torvalds's avatar
Linus Torvalds committed
81
	u32 loss;
Eric Dumazet's avatar
Eric Dumazet committed
82
	u32 ecn;
Linus Torvalds's avatar
Linus Torvalds committed
83 84 85 86
	u32 limit;
	u32 counter;
	u32 gap;
	u32 duplicate;
87
	u32 reorder;
88
	u32 corrupt;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
89
	u32 rate;
90 91 92 93
	s32 packet_overhead;
	u32 cell_size;
	u32 cell_size_reciprocal;
	s32 cell_overhead;
Linus Torvalds's avatar
Linus Torvalds committed
94 95

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

	struct disttable {
		u32  size;
		s16 table[0];
	} *delay_dist;
104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

	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
124 125
};

Eric Dumazet's avatar
Eric Dumazet committed
126 127 128
/* 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
129 130 131 132
struct netem_skb_cb {
	psched_time_t	time_to_send;
};

133 134
static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb)
{
135
	qdisc_cb_private_validate(skb, sizeof(struct netem_skb_cb));
136
	return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data;
137 138
}

Linus Torvalds's avatar
Linus Torvalds committed
139 140 141 142 143 144 145 146 147 148 149 150 151
/* 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.
 */
152
static u32 get_crandom(struct crndstate *state)
Linus Torvalds's avatar
Linus Torvalds committed
153 154 155 156
{
	u64 value, rho;
	unsigned long answer;

Stephen Hemminger's avatar
Stephen Hemminger committed
157
	if (state->rho == 0)	/* no correlation */
Linus Torvalds's avatar
Linus Torvalds committed
158 159 160 161 162 163 164 165 166
		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;
}

167 168 169 170 171 172 173 174 175 176
/* 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
177
	 * Makes a comparison between rnd and the transition
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 219 220 221 222 223 224 225 226 227 228
	 * 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
229
 * Makes a comparison between random number and the transition
230
 * probabilities outgoing from the current state, then decides the
Lucas De Marchi's avatar
Lucas De Marchi committed
231
 * next state. A second random number is extracted and the comparison
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 271 272 273 274 275 276 277 278 279 280 281 282
 * 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
283 284 285 286
/* 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.
 */
287 288 289
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
290
{
291 292 293
	psched_tdiff_t x;
	long t;
	u32 rnd;
Linus Torvalds's avatar
Linus Torvalds committed
294 295 296 297 298 299 300

	if (sigma == 0)
		return mu;

	rnd = get_crandom(state);

	/* default uniform distribution */
301
	if (dist == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
302 303 304 305 306 307 308 309 310 311 312 313
		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;
}

314
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
315
{
316
	u64 ticks;
317

318 319 320 321 322 323 324 325 326 327 328 329 330
	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);
331
	return PSCHED_NS2TICKS(ticks);
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
332 333
}

334
static void tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch)
Eric Dumazet's avatar
Eric Dumazet committed
335 336 337
{
	struct sk_buff_head *list = &sch->q;
	psched_time_t tnext = netem_skb_cb(nskb)->time_to_send;
338
	struct sk_buff *skb = skb_peek_tail(list);
Eric Dumazet's avatar
Eric Dumazet committed
339

340 341 342
	/* Optimize for add at tail */
	if (likely(!skb || tnext >= netem_skb_cb(skb)->time_to_send))
		return __skb_queue_tail(list, nskb);
Eric Dumazet's avatar
Eric Dumazet committed
343

344 345 346
	skb_queue_reverse_walk(list, skb) {
		if (tnext >= netem_skb_cb(skb)->time_to_send)
			break;
Eric Dumazet's avatar
Eric Dumazet committed
347 348
	}

349
	__skb_queue_after(list, skb, nskb);
Eric Dumazet's avatar
Eric Dumazet committed
350 351
}

352 353 354 355 356 357
/*
 * 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
358 359 360
static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
	struct netem_sched_data *q = qdisc_priv(sch);
361 362
	/* We don't fill cb now as skb_unshare() may invalidate it */
	struct netem_skb_cb *cb;
363 364
	struct sk_buff *skb2;
	int count = 1;
Linus Torvalds's avatar
Linus Torvalds committed
365

366 367 368 369
	/* Random duplication */
	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor))
		++count;

370
	/* Drop packet? */
Eric Dumazet's avatar
Eric Dumazet committed
371 372 373 374 375 376
	if (loss_event(q)) {
		if (q->ecn && INET_ECN_set_ce(skb))
			sch->qstats.drops++; /* mark packet */
		else
			--count;
	}
377
	if (count == 0) {
Linus Torvalds's avatar
Linus Torvalds committed
378 379
		sch->qstats.drops++;
		kfree_skb(skb);
380
		return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds's avatar
Linus Torvalds committed
381 382
	}

383 384 385 386 387 388 389 390
	/* If a delay is expected, orphan the skb. (orphaning usually takes
	 * place at TX completion time, so _before_ the link transit delay)
	 * Ideally, this orphaning should be done after the rate limiting
	 * module, because this breaks TCP Small Queue, and other mechanisms
	 * based on socket sk_wmem_alloc.
	 */
	if (q->latency || q->jitter)
		skb_orphan(skb);
391

392 393 394 395 396 397
	/*
	 * 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) {
398
		struct Qdisc *rootq = qdisc_root(sch);
399 400 401
		u32 dupsave = q->duplicate; /* prevent duplicating a dup... */
		q->duplicate = 0;

402
		qdisc_enqueue_root(skb2, rootq);
403
		q->duplicate = dupsave;
Linus Torvalds's avatar
Linus Torvalds committed
404 405
	}

406 407 408 409 410 411 412
	/*
	 * 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)) {
413 414
		if (!(skb = skb_unshare(skb, GFP_ATOMIC)) ||
		    (skb->ip_summed == CHECKSUM_PARTIAL &&
Eric Dumazet's avatar
Eric Dumazet committed
415 416
		     skb_checksum_help(skb)))
			return qdisc_drop(skb, sch);
417 418 419 420

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

421 422 423 424 425
	if (unlikely(skb_queue_len(&sch->q) >= sch->limit))
		return qdisc_reshape_fail(skb, sch);

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

426
	cb = netem_skb_cb(skb);
Eric Dumazet's avatar
Eric Dumazet committed
427
	if (q->gap == 0 ||		/* not doing reordering */
428
	    q->counter < q->gap - 1 ||	/* inside last reordering gap */
429
	    q->reorder < get_crandom(&q->reorder_cor)) {
430
		psched_time_t now;
Stephen Hemminger's avatar
Stephen Hemminger committed
431 432 433 434 435
		psched_tdiff_t delay;

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

436
		now = psched_get_time();
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
437 438

		if (q->rate) {
Eric Dumazet's avatar
Eric Dumazet committed
439
			struct sk_buff_head *list = &sch->q;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
440

441
			delay += packet_len_2_sched_time(skb->len, q);
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
442 443 444 445 446 447 448 449 450 451 452 453 454

			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;
			}
		}

455
		cb->time_to_send = now + delay;
Linus Torvalds's avatar
Linus Torvalds committed
456
		++q->counter;
457
		tfifo_enqueue(skb, sch);
Linus Torvalds's avatar
Linus Torvalds committed
458
	} else {
459
		/*
460 461 462
		 * Do re-ordering by putting one out of N packets at the front
		 * of the queue.
		 */
463
		cb->time_to_send = psched_get_time();
464
		q->counter = 0;
465

Eric Dumazet's avatar
Eric Dumazet committed
466
		__skb_queue_head(&sch->q, skb);
467
		sch->qstats.requeues++;
468
	}
Linus Torvalds's avatar
Linus Torvalds committed
469

470
	return NET_XMIT_SUCCESS;
Linus Torvalds's avatar
Linus Torvalds committed
471 472
}

Eric Dumazet's avatar
Eric Dumazet committed
473
static unsigned int netem_drop(struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
474 475
{
	struct netem_sched_data *q = qdisc_priv(sch);
Eric Dumazet's avatar
Eric Dumazet committed
476
	unsigned int len;
Linus Torvalds's avatar
Linus Torvalds committed
477

Eric Dumazet's avatar
Eric Dumazet committed
478 479 480 481
	len = qdisc_queue_drop(sch);
	if (!len && q->qdisc && q->qdisc->ops->drop)
	    len = q->qdisc->ops->drop(q->qdisc);
	if (len)
Linus Torvalds's avatar
Linus Torvalds committed
482
		sch->qstats.drops++;
Eric Dumazet's avatar
Eric Dumazet committed
483

Linus Torvalds's avatar
Linus Torvalds committed
484 485 486 487 488 489 490 491
	return len;
}

static struct sk_buff *netem_dequeue(struct Qdisc *sch)
{
	struct netem_sched_data *q = qdisc_priv(sch);
	struct sk_buff *skb;

492
	if (qdisc_is_throttled(sch))
493 494
		return NULL;

Eric Dumazet's avatar
Eric Dumazet committed
495 496
tfifo_dequeue:
	skb = qdisc_peek_head(sch);
497
	if (skb) {
498
		const struct netem_skb_cb *cb = netem_skb_cb(skb);
499 500

		/* if more time remaining? */
Eric Dumazet's avatar
Eric Dumazet committed
501
		if (cb->time_to_send <= psched_get_time()) {
Eric Dumazet's avatar
Eric Dumazet committed
502 503
			__skb_unlink(skb, &sch->q);
			sch->qstats.backlog -= qdisc_pkt_len(skb);
504

505 506 507 508 509 510 511 512
#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
513

Eric Dumazet's avatar
Eric Dumazet committed
514 515 516 517 518 519 520 521 522 523 524 525
			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:
526 527
			qdisc_unthrottled(sch);
			qdisc_bstats_update(sch, skb);
528
			return skb;
Stephen Hemminger's avatar
Stephen Hemminger committed
529
		}
530

Eric Dumazet's avatar
Eric Dumazet committed
531 532 533 534 535
		if (q->qdisc) {
			skb = q->qdisc->ops->dequeue(q->qdisc);
			if (skb)
				goto deliver;
		}
536
		qdisc_watchdog_schedule(&q->watchdog, cb->time_to_send);
537 538
	}

Eric Dumazet's avatar
Eric Dumazet committed
539 540 541 542 543
	if (q->qdisc) {
		skb = q->qdisc->ops->dequeue(q->qdisc);
		if (skb)
			goto deliver;
	}
544
	return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
545 546 547 548 549 550
}

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

Eric Dumazet's avatar
Eric Dumazet committed
551 552 553
	qdisc_reset_queue(sch);
	if (q->qdisc)
		qdisc_reset(q->qdisc);
554
	qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds's avatar
Linus Torvalds committed
555 556
}

557 558 559 560 561 562 563 564 565 566
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
567 568 569 570
/*
 * Distribution data is a variable size payload containing
 * signed 16 bit values.
 */
571
static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr)
Linus Torvalds's avatar
Linus Torvalds committed
572 573
{
	struct netem_sched_data *q = qdisc_priv(sch);
574
	size_t n = nla_len(attr)/sizeof(__s16);
575
	const __s16 *data = nla_data(attr);
576
	spinlock_t *root_lock;
Linus Torvalds's avatar
Linus Torvalds committed
577 578
	struct disttable *d;
	int i;
579
	size_t s;
Linus Torvalds's avatar
Linus Torvalds committed
580

581
	if (n > NETEM_DIST_MAX)
Linus Torvalds's avatar
Linus Torvalds committed
582 583
		return -EINVAL;

584
	s = sizeof(struct disttable) + n * sizeof(s16);
585
	d = kmalloc(s, GFP_KERNEL | __GFP_NOWARN);
586 587
	if (!d)
		d = vmalloc(s);
Linus Torvalds's avatar
Linus Torvalds committed
588 589 590 591 592 593
	if (!d)
		return -ENOMEM;

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

595
	root_lock = qdisc_root_sleeping_lock(sch);
596 597

	spin_lock_bh(root_lock);
598
	swap(q->delay_dist, d);
599
	spin_unlock_bh(root_lock);
600 601

	dist_free(d);
Linus Torvalds's avatar
Linus Torvalds committed
602 603 604
	return 0;
}

605
static void get_correlation(struct Qdisc *sch, const struct nlattr *attr)
Linus Torvalds's avatar
Linus Torvalds committed
606 607
{
	struct netem_sched_data *q = qdisc_priv(sch);
608
	const struct tc_netem_corr *c = nla_data(attr);
Linus Torvalds's avatar
Linus Torvalds committed
609 610 611 612 613 614

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

615
static void get_reorder(struct Qdisc *sch, const struct nlattr *attr)
616 617
{
	struct netem_sched_data *q = qdisc_priv(sch);
618
	const struct tc_netem_reorder *r = nla_data(attr);
619 620 621 622 623

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

624
static void get_corrupt(struct Qdisc *sch, const struct nlattr *attr)
625 626
{
	struct netem_sched_data *q = qdisc_priv(sch);
627
	const struct tc_netem_corrupt *r = nla_data(attr);
628 629 630 631 632

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

Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
633 634 635 636 637 638
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;
639 640 641 642 643
	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
644 645
}

646 647 648 649 650 651 652 653 654 655 656 657 658
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);

659
			if (nla_len(la) < sizeof(struct tc_netem_gimodel)) {
660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677
				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);

678 679
			if (nla_len(la) < sizeof(struct tc_netem_gemodel)) {
				pr_info("netem: incorrect ge model size\n");
680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
				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;
}

701 702 703 704
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
705
	[TCA_NETEM_RATE]	= { .len = sizeof(struct tc_netem_rate) },
706
	[TCA_NETEM_LOSS]	= { .type = NLA_NESTED },
Eric Dumazet's avatar
Eric Dumazet committed
707
	[TCA_NETEM_ECN]		= { .type = NLA_U32 },
708 709
};

710 711 712 713 714
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);

715 716
	if (nested_len < 0) {
		pr_info("netem: invalid attributes len %d\n", nested_len);
717
		return -EINVAL;
718 719
	}

720 721 722
	if (nested_len >= nla_attr_size(0))
		return nla_parse(tb, maxtype, nla_data(nla) + NLA_ALIGN(len),
				 nested_len, policy);
723

724 725 726 727
	memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1));
	return 0;
}

728
/* Parse netlink message to set options */
729
static int netem_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds's avatar
Linus Torvalds committed
730 731
{
	struct netem_sched_data *q = qdisc_priv(sch);
732
	struct nlattr *tb[TCA_NETEM_MAX + 1];
Linus Torvalds's avatar
Linus Torvalds committed
733 734
	struct tc_netem_qopt *qopt;
	int ret;
735

736
	if (opt == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
737 738
		return -EINVAL;

739 740
	qopt = nla_data(opt);
	ret = parse_attr(tb, TCA_NETEM_MAX, opt, netem_policy, sizeof(*qopt));
741 742 743
	if (ret < 0)
		return ret;

Eric Dumazet's avatar
Eric Dumazet committed
744
	sch->limit = qopt->limit;
745

Linus Torvalds's avatar
Linus Torvalds committed
746 747 748 749
	q->latency = qopt->latency;
	q->jitter = qopt->jitter;
	q->limit = qopt->limit;
	q->gap = qopt->gap;
750
	q->counter = 0;
Linus Torvalds's avatar
Linus Torvalds committed
751 752 753
	q->loss = qopt->loss;
	q->duplicate = qopt->duplicate;

Stephen Hemminger's avatar
Stephen Hemminger committed
754 755
	/* for compatibility with earlier versions.
	 * if gap is set, need to assume 100% probability
756
	 */
757 758
	if (q->gap)
		q->reorder = ~0;
759

760 761
	if (tb[TCA_NETEM_CORR])
		get_correlation(sch, tb[TCA_NETEM_CORR]);
Linus Torvalds's avatar
Linus Torvalds committed
762

763 764 765 766 767
	if (tb[TCA_NETEM_DELAY_DIST]) {
		ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]);
		if (ret)
			return ret;
	}
768

769 770
	if (tb[TCA_NETEM_REORDER])
		get_reorder(sch, tb[TCA_NETEM_REORDER]);
Linus Torvalds's avatar
Linus Torvalds committed
771

772 773
	if (tb[TCA_NETEM_CORRUPT])
		get_corrupt(sch, tb[TCA_NETEM_CORRUPT]);
Linus Torvalds's avatar
Linus Torvalds committed
774

Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
775 776 777
	if (tb[TCA_NETEM_RATE])
		get_rate(sch, tb[TCA_NETEM_RATE]);

Eric Dumazet's avatar
Eric Dumazet committed
778 779 780
	if (tb[TCA_NETEM_ECN])
		q->ecn = nla_get_u32(tb[TCA_NETEM_ECN]);

781 782 783 784 785
	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
786 787
}

788
static int netem_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds's avatar
Linus Torvalds committed
789 790 791 792 793 794 795
{
	struct netem_sched_data *q = qdisc_priv(sch);
	int ret;

	if (!opt)
		return -EINVAL;

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

798
	q->loss_model = CLG_RANDOM;
Linus Torvalds's avatar
Linus Torvalds committed
799
	ret = netem_change(sch, opt);
Eric Dumazet's avatar
Eric Dumazet committed
800
	if (ret)
801
		pr_info("netem: change failed\n");
Linus Torvalds's avatar
Linus Torvalds committed
802 803 804 805 806 807 808
	return ret;
}

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

809
	qdisc_watchdog_cancel(&q->watchdog);
Eric Dumazet's avatar
Eric Dumazet committed
810 811
	if (q->qdisc)
		qdisc_destroy(q->qdisc);
812
	dist_free(q->delay_dist);
Linus Torvalds's avatar
Linus Torvalds committed
813 814
}

815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838
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,
		};

839 840
		if (nla_put(skb, NETEM_LOSS_GI, sizeof(gi), &gi))
			goto nla_put_failure;
841 842 843 844 845 846 847 848 849 850
		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,
		};

851 852
		if (nla_put(skb, NETEM_LOSS_GE, sizeof(ge), &ge))
			goto nla_put_failure;
853 854 855 856 857 858 859 860 861 862 863 864
		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
865 866 867
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
868
	struct nlattr *nla = (struct nlattr *) skb_tail_pointer(skb);
Linus Torvalds's avatar
Linus Torvalds committed
869 870
	struct tc_netem_qopt qopt;
	struct tc_netem_corr cor;
871
	struct tc_netem_reorder reorder;
872
	struct tc_netem_corrupt corrupt;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
873
	struct tc_netem_rate rate;
Linus Torvalds's avatar
Linus Torvalds committed
874 875 876 877 878 879 880

	qopt.latency = q->latency;
	qopt.jitter = q->jitter;
	qopt.limit = q->limit;
	qopt.loss = q->loss;
	qopt.gap = q->gap;
	qopt.duplicate = q->duplicate;
881 882
	if (nla_put(skb, TCA_OPTIONS, sizeof(qopt), &qopt))
		goto nla_put_failure;
Linus Torvalds's avatar
Linus Torvalds committed
883 884 885 886

	cor.delay_corr = q->delay_cor.rho;
	cor.loss_corr = q->loss_cor.rho;
	cor.dup_corr = q->dup_cor.rho;
887 888
	if (nla_put(skb, TCA_NETEM_CORR, sizeof(cor), &cor))
		goto nla_put_failure;
889 890 891

	reorder.probability = q->reorder;
	reorder.correlation = q->reorder_cor.rho;
892 893
	if (nla_put(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder))
		goto nla_put_failure;
894

895 896
	corrupt.probability = q->corrupt;
	corrupt.correlation = q->corrupt_cor.rho;
897 898
	if (nla_put(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt))
		goto nla_put_failure;
899

Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
900
	rate.rate = q->rate;
901 902 903
	rate.packet_overhead = q->packet_overhead;
	rate.cell_size = q->cell_size;
	rate.cell_overhead = q->cell_overhead;
904 905
	if (nla_put(skb, TCA_NETEM_RATE, sizeof(rate), &rate))
		goto nla_put_failure;
Hagen Paul Pfeifer's avatar
Hagen Paul Pfeifer committed
906

Eric Dumazet's avatar
Eric Dumazet committed
907 908 909
	if (q->ecn && nla_put_u32(skb, TCA_NETEM_ECN, q->ecn))
		goto nla_put_failure;

910 911 912
	if (dump_loss_model(q, skb) != 0)
		goto nla_put_failure;

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

915
nla_put_failure:
stephen hemminger's avatar
stephen hemminger committed
916
	nlmsg_trim(skb, nla);
Linus Torvalds's avatar
Linus Torvalds committed
917 918 919
	return -1;
}

920 921 922 923 924
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
925
	if (cl != 1 || !q->qdisc) 	/* only one class */
926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941
		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
942 943 944 945
	if (*old) {
		qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
		qdisc_reset(*old);
	}
946 947 948 949 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 976 977 978 979 980 981 982 983 984 985 986
	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,
};

987
static struct Qdisc_ops netem_qdisc_ops __read_mostly = {
Linus Torvalds's avatar
Linus Torvalds committed
988
	.id		=	"netem",
989
	.cl_ops		=	&netem_class_ops,
Linus Torvalds's avatar
Linus Torvalds committed
990 991 992
	.priv_size	=	sizeof(struct netem_sched_data),
	.enqueue	=	netem_enqueue,
	.dequeue	=	netem_dequeue,
993
	.peek		=	qdisc_peek_dequeued,
Linus Torvalds's avatar
Linus Torvalds committed
994 995 996 997 998 999 1000 1001 1002 1003 1004 1005
	.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)
{
1006
	pr_info("netem: version " VERSION "\n");
Linus Torvalds's avatar
Linus Torvalds committed
1007 1008 1009 1010 1011 1012 1013 1014 1015
	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");