/*
* 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;
s64 latency;
s64 jitter;
u32 loss;
u32 ecn;
u32 limit;
u32 counter;
u32 gap;
u32 duplicate;
u32 reorder;
u32 corrupt;
u64 rate;
s32 packet_overhead;
u32 cell_size;
struct reciprocal_value 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;
enum {
TX_IN_GAP_PERIOD = 1,
TX_IN_BURST_PERIOD,
LOST_IN_GAP_PERIOD,
LOST_IN_BURST_PERIOD,
} _4_state_model;
enum {
GOOD_STATE = 1,
BAD_STATE,
} GE_state_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;
struct tc_netem_slot slot_config;
struct slotstate {
u64 slot_next;
s32 packets_left;
s32 bytes_left;
} slot;
};
/* Time stamp put into socket buffer control block
* Only valid when skbs are in our internal t(ime)fifo queue.
*
* 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.
*/
struct netem_skb_cb {
u64 time_to_send;
};
static inline struct netem_skb_cb *netem_skb_cb