// SPDX-License-Identifier: GPL-2.0-only
/*
* net/sched/sch_netem.c Network emulator
*
* 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 disttable {
u32 size;
s16 table[0];
};
struct netem_sched_data {
/* internal t(ime)fifo qdisc uses t_root and sch->limit */
struct rb_root t_root;
/* a linear queue; reduces rbtree rebalancing when jitter is low */
struct sk_buff *t_head;
struct sk_buff *t_tail;
/* 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 *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