/*
* 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
* 2 of the License.
*
* Many of the algorithms and ideas for this came from
* NIST Net which is not copyrighted.
*
* Authors: Stephen Hemminger <shemminger@osdl.org>
* Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
*/
#include <linux/mm.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/skbuff.h>
#include <linux/vmalloc.h>
#include <linux/rtnetlink.h>
#include <linux/reciprocal_div.h>
#include <linux/rbtree.h>
#include <net/netlink.h>
#include <net/pkt_sched.h>
#include <net/inet_ecn.h>
#define VERSION "1.3"
/* 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.
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>
*/
struct netem_sched_data {
/* internal t(ime)fifo qdisc uses t_root and sch->limit */
struct rb_root t_root;
/* optional qdisc for classful handling (NULL at netem init) */
struct Qdisc *qdisc;
struct qdisc_watchdog watchdog;
psched_tdiff_t latency;
psched_tdiff_t jitter;
u32 loss;
u32 ecn;
u32 limit;
u32 counter;
u32 gap;
u32 duplicate;
u32 reorder;
u32 corrupt;
u32 rate;
s32 packet_overhead;
u32 cell_size;
u32 cell_size_reciprocal;
s32 cell_overhead;
struct crndstate {
u32 last;
u32 rho;
} delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor;
struct disttable {
u32 size;
s16 table[0];
} *delay_dist;
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;
};
/* Time stamp put into socket buffer control block
* Only valid when skbs are in our internal t(ime)fifo queue.
*/
struct netem_skb_cb {
psched_time_t time_to_send;
ktime_t tstamp_save;
};
/* 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;
}
static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb)
{
/* we assume we can use skb next/prev/tstamp as storage for rb_node */
qdisc_cb_private_validate(skb, sizeof(struct netem_skb_cb));
return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data;
}
/* 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.