// 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 <[email protected]> * 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/gso.h> #include <net/netlink.h> #include <net/pkt_sched.h> #include <net/inet_ecn.h> #define VERSION … /* 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 { … }; struct netem_sched_data { … }; /* 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 { … }; static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb) { … } /* init_crandom - initialize correlated random number generator * Use entropy source for initial seed. */ static void init_crandom(struct crndstate *state, unsigned long rho) { … } /* get_crandom - correlated random number generator * Next number depends on last value. * rho is scaled to avoid floating point. */ static u32 get_crandom(struct crndstate *state, struct prng *p) { … } /* 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) { … } /* 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) * * Makes a comparison between random number and the transition * probabilities outgoing from the current state, then decides the * next state. A second random number is extracted and the comparison * 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) { … } static bool loss_event(struct netem_sched_data *q) { … } /* 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. */ static s64 tabledist(s64 mu, s32 sigma, struct crndstate *state, struct prng *prng, const struct disttable *dist) { … } static u64 packet_time_ns(u64 len, const struct netem_sched_data *q) { … } static void tfifo_reset(struct Qdisc *sch) { … } static void tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch) { … } /* netem can't properly corrupt a megapacket (like we get from GSO), so instead * when we statistically choose to corrupt one, we instead segment it, returning * the first packet to be corrupted, and re-enqueue the remaining frames */ static struct sk_buff *netem_segment(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free) { … } /* * 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. */ static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free) { … } /* Delay the next round with a new future slot with a * correct number of bytes and packets. */ static void get_slot_next(struct netem_sched_data *q, u64 now) { … } static struct sk_buff *netem_peek(struct netem_sched_data *q) { … } static void netem_erase_head(struct netem_sched_data *q, struct sk_buff *skb) { … } static struct sk_buff *netem_dequeue(struct Qdisc *sch) { … } static void netem_reset(struct Qdisc *sch) { … } static void dist_free(struct disttable *d) { … } /* * Distribution data is a variable size payload containing * signed 16 bit values. */ static int get_dist_table(struct disttable **tbl, const struct nlattr *attr) { … } static void get_slot(struct netem_sched_data *q, const struct nlattr *attr) { … } static void get_correlation(struct netem_sched_data *q, const struct nlattr *attr) { … } static void get_reorder(struct netem_sched_data *q, const struct nlattr *attr) { … } static void get_corrupt(struct netem_sched_data *q, const struct nlattr *attr) { … } static void get_rate(struct netem_sched_data *q, const struct nlattr *attr) { … } static int get_loss_clg(struct netem_sched_data *q, const struct nlattr *attr) { … } static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = …; static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr *nla, const struct nla_policy *policy, int len) { … } /* Parse netlink message to set options */ static int netem_change(struct Qdisc *sch, struct nlattr *opt, struct netlink_ext_ack *extack) { … } static int netem_init(struct Qdisc *sch, struct nlattr *opt, struct netlink_ext_ack *extack) { … } static void netem_destroy(struct Qdisc *sch) { … } static int dump_loss_model(const struct netem_sched_data *q, struct sk_buff *skb) { … } static int netem_dump(struct Qdisc *sch, struct sk_buff *skb) { … } static int netem_dump_class(struct Qdisc *sch, unsigned long cl, struct sk_buff *skb, struct tcmsg *tcm) { … } static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, struct Qdisc **old, struct netlink_ext_ack *extack) { … } static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg) { … } static unsigned long netem_find(struct Qdisc *sch, u32 classid) { … } static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker) { … } static const struct Qdisc_class_ops netem_class_ops = …; static struct Qdisc_ops netem_qdisc_ops __read_mostly = …; MODULE_ALIAS_NET_SCH(…) …; static int __init netem_module_init(void) { … } static void __exit netem_module_exit(void) { … } module_init(…) … module_exit(…) MODULE_LICENSE(…) …; MODULE_DESCRIPTION(…) …;
Codebase Browser
linux