11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * net/sched/sch_netem.c Network emulator 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * This program is free software; you can redistribute it and/or 51da177e4SLinus Torvalds * modify it under the terms of the GNU General Public License 61da177e4SLinus Torvalds * as published by the Free Software Foundation; either version 7798b6b19SStephen Hemminger * 2 of the License. 81da177e4SLinus Torvalds * 91da177e4SLinus Torvalds * Many of the algorithms and ideas for this came from 101da177e4SLinus Torvalds * NIST Net which is not copyrighted. 111da177e4SLinus Torvalds * 121da177e4SLinus Torvalds * Authors: Stephen Hemminger <shemminger@osdl.org> 131da177e4SLinus Torvalds * Catalin(ux aka Dino) BOIE <catab at umbrella dot ro> 141da177e4SLinus Torvalds */ 151da177e4SLinus Torvalds 16b7f080cfSAlexey Dobriyan #include <linux/mm.h> 171da177e4SLinus Torvalds #include <linux/module.h> 185a0e3ad6STejun Heo #include <linux/slab.h> 191da177e4SLinus Torvalds #include <linux/types.h> 201da177e4SLinus Torvalds #include <linux/kernel.h> 211da177e4SLinus Torvalds #include <linux/errno.h> 221da177e4SLinus Torvalds #include <linux/skbuff.h> 2378776d3fSDavid S. Miller #include <linux/vmalloc.h> 241da177e4SLinus Torvalds #include <linux/rtnetlink.h> 2590b41a1cSHagen Paul Pfeifer #include <linux/reciprocal_div.h> 26aec0a40aSEric Dumazet #include <linux/rbtree.h> 271da177e4SLinus Torvalds 28dc5fc579SArnaldo Carvalho de Melo #include <net/netlink.h> 291da177e4SLinus Torvalds #include <net/pkt_sched.h> 30e4ae004bSEric Dumazet #include <net/inet_ecn.h> 311da177e4SLinus Torvalds 32250a65f7Sstephen hemminger #define VERSION "1.3" 33eb229c4cSStephen Hemminger 341da177e4SLinus Torvalds /* Network Emulation Queuing algorithm. 351da177e4SLinus Torvalds ==================================== 361da177e4SLinus Torvalds 371da177e4SLinus Torvalds Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based 381da177e4SLinus Torvalds Network Emulation Tool 391da177e4SLinus Torvalds [2] Luigi Rizzo, DummyNet for FreeBSD 401da177e4SLinus Torvalds 411da177e4SLinus Torvalds ---------------------------------------------------------------- 421da177e4SLinus Torvalds 431da177e4SLinus Torvalds This started out as a simple way to delay outgoing packets to 441da177e4SLinus Torvalds test TCP but has grown to include most of the functionality 451da177e4SLinus Torvalds of a full blown network emulator like NISTnet. It can delay 461da177e4SLinus Torvalds packets and add random jitter (and correlation). The random 471da177e4SLinus Torvalds distribution can be loaded from a table as well to provide 481da177e4SLinus Torvalds normal, Pareto, or experimental curves. Packet loss, 491da177e4SLinus Torvalds duplication, and reordering can also be emulated. 501da177e4SLinus Torvalds 511da177e4SLinus Torvalds This qdisc does not do classification that can be handled in 521da177e4SLinus Torvalds layering other disciplines. It does not need to do bandwidth 531da177e4SLinus Torvalds control either since that can be handled by using token 541da177e4SLinus Torvalds bucket or other rate control. 55661b7972Sstephen hemminger 56661b7972Sstephen hemminger Correlated Loss Generator models 57661b7972Sstephen hemminger 58661b7972Sstephen hemminger Added generation of correlated loss according to the 59661b7972Sstephen hemminger "Gilbert-Elliot" model, a 4-state markov model. 60661b7972Sstephen hemminger 61661b7972Sstephen hemminger References: 62661b7972Sstephen hemminger [1] NetemCLG Home http://netgroup.uniroma2.it/NetemCLG 63661b7972Sstephen hemminger [2] S. Salsano, F. Ludovici, A. Ordine, "Definition of a general 64661b7972Sstephen hemminger and intuitive loss model for packet networks and its implementation 65661b7972Sstephen hemminger in the Netem module in the Linux kernel", available in [1] 66661b7972Sstephen hemminger 67661b7972Sstephen hemminger Authors: Stefano Salsano <stefano.salsano at uniroma2.it 68661b7972Sstephen hemminger Fabio Ludovici <fabio.ludovici at yahoo.it> 691da177e4SLinus Torvalds */ 701da177e4SLinus Torvalds 711da177e4SLinus Torvalds struct netem_sched_data { 72aec0a40aSEric Dumazet /* internal t(ime)fifo qdisc uses t_root and sch->limit */ 73aec0a40aSEric Dumazet struct rb_root t_root; 7450612537SEric Dumazet 7550612537SEric Dumazet /* optional qdisc for classful handling (NULL at netem init) */ 761da177e4SLinus Torvalds struct Qdisc *qdisc; 7750612537SEric Dumazet 7859cb5c67SPatrick McHardy struct qdisc_watchdog watchdog; 791da177e4SLinus Torvalds 80b407621cSStephen Hemminger psched_tdiff_t latency; 81b407621cSStephen Hemminger psched_tdiff_t jitter; 82b407621cSStephen Hemminger 831da177e4SLinus Torvalds u32 loss; 84e4ae004bSEric Dumazet u32 ecn; 851da177e4SLinus Torvalds u32 limit; 861da177e4SLinus Torvalds u32 counter; 871da177e4SLinus Torvalds u32 gap; 881da177e4SLinus Torvalds u32 duplicate; 890dca51d3SStephen Hemminger u32 reorder; 90c865e5d9SStephen Hemminger u32 corrupt; 916a031f67SYang Yingliang u64 rate; 9290b41a1cSHagen Paul Pfeifer s32 packet_overhead; 9390b41a1cSHagen Paul Pfeifer u32 cell_size; 94809fa972SHannes Frederic Sowa struct reciprocal_value cell_size_reciprocal; 9590b41a1cSHagen Paul Pfeifer s32 cell_overhead; 961da177e4SLinus Torvalds 971da177e4SLinus Torvalds struct crndstate { 98b407621cSStephen Hemminger u32 last; 99b407621cSStephen Hemminger u32 rho; 100c865e5d9SStephen Hemminger } delay_cor, loss_cor, dup_cor, reorder_cor, corrupt_cor; 1011da177e4SLinus Torvalds 1021da177e4SLinus Torvalds struct disttable { 1031da177e4SLinus Torvalds u32 size; 1041da177e4SLinus Torvalds s16 table[0]; 1051da177e4SLinus Torvalds } *delay_dist; 106661b7972Sstephen hemminger 107661b7972Sstephen hemminger enum { 108661b7972Sstephen hemminger CLG_RANDOM, 109661b7972Sstephen hemminger CLG_4_STATES, 110661b7972Sstephen hemminger CLG_GILB_ELL, 111661b7972Sstephen hemminger } loss_model; 112661b7972Sstephen hemminger 113a6e2fe17SYang Yingliang enum { 114a6e2fe17SYang Yingliang TX_IN_GAP_PERIOD = 1, 115a6e2fe17SYang Yingliang TX_IN_BURST_PERIOD, 116a6e2fe17SYang Yingliang LOST_IN_GAP_PERIOD, 117a6e2fe17SYang Yingliang LOST_IN_BURST_PERIOD, 118a6e2fe17SYang Yingliang } _4_state_model; 119a6e2fe17SYang Yingliang 120c045a734SYang Yingliang enum { 121c045a734SYang Yingliang GOOD_STATE = 1, 122c045a734SYang Yingliang BAD_STATE, 123c045a734SYang Yingliang } GE_state_model; 124c045a734SYang Yingliang 125661b7972Sstephen hemminger /* Correlated Loss Generation models */ 126661b7972Sstephen hemminger struct clgstate { 127661b7972Sstephen hemminger /* state of the Markov chain */ 128661b7972Sstephen hemminger u8 state; 129661b7972Sstephen hemminger 130661b7972Sstephen hemminger /* 4-states and Gilbert-Elliot models */ 131661b7972Sstephen hemminger u32 a1; /* p13 for 4-states or p for GE */ 132661b7972Sstephen hemminger u32 a2; /* p31 for 4-states or r for GE */ 133661b7972Sstephen hemminger u32 a3; /* p32 for 4-states or h for GE */ 134661b7972Sstephen hemminger u32 a4; /* p14 for 4-states or 1-k for GE */ 135661b7972Sstephen hemminger u32 a5; /* p23 used only in 4-states */ 136661b7972Sstephen hemminger } clg; 137661b7972Sstephen hemminger 1381da177e4SLinus Torvalds }; 1391da177e4SLinus Torvalds 14050612537SEric Dumazet /* Time stamp put into socket buffer control block 14150612537SEric Dumazet * Only valid when skbs are in our internal t(ime)fifo queue. 14256b17425SEric Dumazet * 14356b17425SEric Dumazet * As skb->rbnode uses same storage than skb->next, skb->prev and skb->tstamp, 14456b17425SEric Dumazet * and skb->next & skb->prev are scratch space for a qdisc, 14556b17425SEric Dumazet * we save skb->tstamp value in skb->cb[] before destroying it. 14650612537SEric Dumazet */ 1471da177e4SLinus Torvalds struct netem_skb_cb { 1481da177e4SLinus Torvalds psched_time_t time_to_send; 149aec0a40aSEric Dumazet ktime_t tstamp_save; 1501da177e4SLinus Torvalds }; 1511da177e4SLinus Torvalds 152aec0a40aSEric Dumazet 153aec0a40aSEric Dumazet static struct sk_buff *netem_rb_to_skb(struct rb_node *rb) 154aec0a40aSEric Dumazet { 15556b17425SEric Dumazet return container_of(rb, struct sk_buff, rbnode); 156aec0a40aSEric Dumazet } 157aec0a40aSEric Dumazet 1585f86173bSJussi Kivilinna static inline struct netem_skb_cb *netem_skb_cb(struct sk_buff *skb) 1595f86173bSJussi Kivilinna { 160aec0a40aSEric Dumazet /* we assume we can use skb next/prev/tstamp as storage for rb_node */ 16116bda13dSDavid S. Miller qdisc_cb_private_validate(skb, sizeof(struct netem_skb_cb)); 162175f9c1bSJussi Kivilinna return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data; 1635f86173bSJussi Kivilinna } 1645f86173bSJussi Kivilinna 1651da177e4SLinus Torvalds /* init_crandom - initialize correlated random number generator 1661da177e4SLinus Torvalds * Use entropy source for initial seed. 1671da177e4SLinus Torvalds */ 1681da177e4SLinus Torvalds static void init_crandom(struct crndstate *state, unsigned long rho) 1691da177e4SLinus Torvalds { 1701da177e4SLinus Torvalds state->rho = rho; 17163862b5bSAruna-Hewapathirane state->last = prandom_u32(); 1721da177e4SLinus Torvalds } 1731da177e4SLinus Torvalds 1741da177e4SLinus Torvalds /* get_crandom - correlated random number generator 1751da177e4SLinus Torvalds * Next number depends on last value. 1761da177e4SLinus Torvalds * rho is scaled to avoid floating point. 1771da177e4SLinus Torvalds */ 178b407621cSStephen Hemminger static u32 get_crandom(struct crndstate *state) 1791da177e4SLinus Torvalds { 1801da177e4SLinus Torvalds u64 value, rho; 1811da177e4SLinus Torvalds unsigned long answer; 1821da177e4SLinus Torvalds 183bb2f8cc0SStephen Hemminger if (state->rho == 0) /* no correlation */ 18463862b5bSAruna-Hewapathirane return prandom_u32(); 1851da177e4SLinus Torvalds 18663862b5bSAruna-Hewapathirane value = prandom_u32(); 1871da177e4SLinus Torvalds rho = (u64)state->rho + 1; 1881da177e4SLinus Torvalds answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32; 1891da177e4SLinus Torvalds state->last = answer; 1901da177e4SLinus Torvalds return answer; 1911da177e4SLinus Torvalds } 1921da177e4SLinus Torvalds 193661b7972Sstephen hemminger /* loss_4state - 4-state model loss generator 194661b7972Sstephen hemminger * Generates losses according to the 4-state Markov chain adopted in 195661b7972Sstephen hemminger * the GI (General and Intuitive) loss model. 196661b7972Sstephen hemminger */ 197661b7972Sstephen hemminger static bool loss_4state(struct netem_sched_data *q) 198661b7972Sstephen hemminger { 199661b7972Sstephen hemminger struct clgstate *clg = &q->clg; 20063862b5bSAruna-Hewapathirane u32 rnd = prandom_u32(); 201661b7972Sstephen hemminger 202661b7972Sstephen hemminger /* 20325985edcSLucas De Marchi * Makes a comparison between rnd and the transition 204661b7972Sstephen hemminger * probabilities outgoing from the current state, then decides the 205661b7972Sstephen hemminger * next state and if the next packet has to be transmitted or lost. 206661b7972Sstephen hemminger * The four states correspond to: 207a6e2fe17SYang Yingliang * TX_IN_GAP_PERIOD => successfully transmitted packets within a gap period 208a6e2fe17SYang Yingliang * LOST_IN_BURST_PERIOD => isolated losses within a gap period 209a6e2fe17SYang Yingliang * LOST_IN_GAP_PERIOD => lost packets within a burst period 210a6e2fe17SYang Yingliang * TX_IN_GAP_PERIOD => successfully transmitted packets within a burst period 211661b7972Sstephen hemminger */ 212661b7972Sstephen hemminger switch (clg->state) { 213a6e2fe17SYang Yingliang case TX_IN_GAP_PERIOD: 214661b7972Sstephen hemminger if (rnd < clg->a4) { 215a6e2fe17SYang Yingliang clg->state = LOST_IN_BURST_PERIOD; 216661b7972Sstephen hemminger return true; 217ab6c27beSstephen hemminger } else if (clg->a4 < rnd && rnd < clg->a1 + clg->a4) { 218a6e2fe17SYang Yingliang clg->state = LOST_IN_GAP_PERIOD; 219661b7972Sstephen hemminger return true; 220a6e2fe17SYang Yingliang } else if (clg->a1 + clg->a4 < rnd) { 221a6e2fe17SYang Yingliang clg->state = TX_IN_GAP_PERIOD; 222a6e2fe17SYang Yingliang } 223661b7972Sstephen hemminger 224661b7972Sstephen hemminger break; 225a6e2fe17SYang Yingliang case TX_IN_BURST_PERIOD: 226661b7972Sstephen hemminger if (rnd < clg->a5) { 227a6e2fe17SYang Yingliang clg->state = LOST_IN_GAP_PERIOD; 228661b7972Sstephen hemminger return true; 229a6e2fe17SYang Yingliang } else { 230a6e2fe17SYang Yingliang clg->state = TX_IN_BURST_PERIOD; 231a6e2fe17SYang Yingliang } 232661b7972Sstephen hemminger 233661b7972Sstephen hemminger break; 234a6e2fe17SYang Yingliang case LOST_IN_GAP_PERIOD: 235661b7972Sstephen hemminger if (rnd < clg->a3) 236a6e2fe17SYang Yingliang clg->state = TX_IN_BURST_PERIOD; 237661b7972Sstephen hemminger else if (clg->a3 < rnd && rnd < clg->a2 + clg->a3) { 238a6e2fe17SYang Yingliang clg->state = TX_IN_GAP_PERIOD; 239661b7972Sstephen hemminger } else if (clg->a2 + clg->a3 < rnd) { 240a6e2fe17SYang Yingliang clg->state = LOST_IN_GAP_PERIOD; 241661b7972Sstephen hemminger return true; 242661b7972Sstephen hemminger } 243661b7972Sstephen hemminger break; 244a6e2fe17SYang Yingliang case LOST_IN_BURST_PERIOD: 245a6e2fe17SYang Yingliang clg->state = TX_IN_GAP_PERIOD; 246661b7972Sstephen hemminger break; 247661b7972Sstephen hemminger } 248661b7972Sstephen hemminger 249661b7972Sstephen hemminger return false; 250661b7972Sstephen hemminger } 251661b7972Sstephen hemminger 252661b7972Sstephen hemminger /* loss_gilb_ell - Gilbert-Elliot model loss generator 253661b7972Sstephen hemminger * Generates losses according to the Gilbert-Elliot loss model or 254661b7972Sstephen hemminger * its special cases (Gilbert or Simple Gilbert) 255661b7972Sstephen hemminger * 25625985edcSLucas De Marchi * Makes a comparison between random number and the transition 257661b7972Sstephen hemminger * probabilities outgoing from the current state, then decides the 25825985edcSLucas De Marchi * next state. A second random number is extracted and the comparison 259661b7972Sstephen hemminger * with the loss probability of the current state decides if the next 260661b7972Sstephen hemminger * packet will be transmitted or lost. 261661b7972Sstephen hemminger */ 262661b7972Sstephen hemminger static bool loss_gilb_ell(struct netem_sched_data *q) 263661b7972Sstephen hemminger { 264661b7972Sstephen hemminger struct clgstate *clg = &q->clg; 265661b7972Sstephen hemminger 266661b7972Sstephen hemminger switch (clg->state) { 267c045a734SYang Yingliang case GOOD_STATE: 26863862b5bSAruna-Hewapathirane if (prandom_u32() < clg->a1) 269c045a734SYang Yingliang clg->state = BAD_STATE; 27063862b5bSAruna-Hewapathirane if (prandom_u32() < clg->a4) 271661b7972Sstephen hemminger return true; 2727c2781faSstephen hemminger break; 273c045a734SYang Yingliang case BAD_STATE: 27463862b5bSAruna-Hewapathirane if (prandom_u32() < clg->a2) 275c045a734SYang Yingliang clg->state = GOOD_STATE; 27663862b5bSAruna-Hewapathirane if (prandom_u32() > clg->a3) 277661b7972Sstephen hemminger return true; 278661b7972Sstephen hemminger } 279661b7972Sstephen hemminger 280661b7972Sstephen hemminger return false; 281661b7972Sstephen hemminger } 282661b7972Sstephen hemminger 283661b7972Sstephen hemminger static bool loss_event(struct netem_sched_data *q) 284661b7972Sstephen hemminger { 285661b7972Sstephen hemminger switch (q->loss_model) { 286661b7972Sstephen hemminger case CLG_RANDOM: 287661b7972Sstephen hemminger /* Random packet drop 0 => none, ~0 => all */ 288661b7972Sstephen hemminger return q->loss && q->loss >= get_crandom(&q->loss_cor); 289661b7972Sstephen hemminger 290661b7972Sstephen hemminger case CLG_4_STATES: 291661b7972Sstephen hemminger /* 4state loss model algorithm (used also for GI model) 292661b7972Sstephen hemminger * Extracts a value from the markov 4 state loss generator, 293661b7972Sstephen hemminger * if it is 1 drops a packet and if needed writes the event in 294661b7972Sstephen hemminger * the kernel logs 295661b7972Sstephen hemminger */ 296661b7972Sstephen hemminger return loss_4state(q); 297661b7972Sstephen hemminger 298661b7972Sstephen hemminger case CLG_GILB_ELL: 299661b7972Sstephen hemminger /* Gilbert-Elliot loss model algorithm 300661b7972Sstephen hemminger * Extracts a value from the Gilbert-Elliot loss generator, 301661b7972Sstephen hemminger * if it is 1 drops a packet and if needed writes the event in 302661b7972Sstephen hemminger * the kernel logs 303661b7972Sstephen hemminger */ 304661b7972Sstephen hemminger return loss_gilb_ell(q); 305661b7972Sstephen hemminger } 306661b7972Sstephen hemminger 307661b7972Sstephen hemminger return false; /* not reached */ 308661b7972Sstephen hemminger } 309661b7972Sstephen hemminger 310661b7972Sstephen hemminger 3111da177e4SLinus Torvalds /* tabledist - return a pseudo-randomly distributed value with mean mu and 3121da177e4SLinus Torvalds * std deviation sigma. Uses table lookup to approximate the desired 3131da177e4SLinus Torvalds * distribution, and a uniformly-distributed pseudo-random source. 3141da177e4SLinus Torvalds */ 315b407621cSStephen Hemminger static psched_tdiff_t tabledist(psched_tdiff_t mu, psched_tdiff_t sigma, 316b407621cSStephen Hemminger struct crndstate *state, 317b407621cSStephen Hemminger const struct disttable *dist) 3181da177e4SLinus Torvalds { 319b407621cSStephen Hemminger psched_tdiff_t x; 320b407621cSStephen Hemminger long t; 321b407621cSStephen Hemminger u32 rnd; 3221da177e4SLinus Torvalds 3231da177e4SLinus Torvalds if (sigma == 0) 3241da177e4SLinus Torvalds return mu; 3251da177e4SLinus Torvalds 3261da177e4SLinus Torvalds rnd = get_crandom(state); 3271da177e4SLinus Torvalds 3281da177e4SLinus Torvalds /* default uniform distribution */ 3291da177e4SLinus Torvalds if (dist == NULL) 3301da177e4SLinus Torvalds return (rnd % (2*sigma)) - sigma + mu; 3311da177e4SLinus Torvalds 3321da177e4SLinus Torvalds t = dist->table[rnd % dist->size]; 3331da177e4SLinus Torvalds x = (sigma % NETEM_DIST_SCALE) * t; 3341da177e4SLinus Torvalds if (x >= 0) 3351da177e4SLinus Torvalds x += NETEM_DIST_SCALE/2; 3361da177e4SLinus Torvalds else 3371da177e4SLinus Torvalds x -= NETEM_DIST_SCALE/2; 3381da177e4SLinus Torvalds 3391da177e4SLinus Torvalds return x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu; 3401da177e4SLinus Torvalds } 3411da177e4SLinus Torvalds 34290b41a1cSHagen Paul Pfeifer static psched_time_t packet_len_2_sched_time(unsigned int len, struct netem_sched_data *q) 3437bc0f28cSHagen Paul Pfeifer { 34490b41a1cSHagen Paul Pfeifer u64 ticks; 345fc33cc72SEric Dumazet 34690b41a1cSHagen Paul Pfeifer len += q->packet_overhead; 34790b41a1cSHagen Paul Pfeifer 34890b41a1cSHagen Paul Pfeifer if (q->cell_size) { 34990b41a1cSHagen Paul Pfeifer u32 cells = reciprocal_divide(len, q->cell_size_reciprocal); 35090b41a1cSHagen Paul Pfeifer 35190b41a1cSHagen Paul Pfeifer if (len > cells * q->cell_size) /* extra cell needed for remainder */ 35290b41a1cSHagen Paul Pfeifer cells++; 35390b41a1cSHagen Paul Pfeifer len = cells * (q->cell_size + q->cell_overhead); 35490b41a1cSHagen Paul Pfeifer } 35590b41a1cSHagen Paul Pfeifer 35690b41a1cSHagen Paul Pfeifer ticks = (u64)len * NSEC_PER_SEC; 35790b41a1cSHagen Paul Pfeifer 35890b41a1cSHagen Paul Pfeifer do_div(ticks, q->rate); 359fc33cc72SEric Dumazet return PSCHED_NS2TICKS(ticks); 3607bc0f28cSHagen Paul Pfeifer } 3617bc0f28cSHagen Paul Pfeifer 362ff704050Sstephen hemminger static void tfifo_reset(struct Qdisc *sch) 363ff704050Sstephen hemminger { 364ff704050Sstephen hemminger struct netem_sched_data *q = qdisc_priv(sch); 365ff704050Sstephen hemminger struct rb_node *p; 366ff704050Sstephen hemminger 367ff704050Sstephen hemminger while ((p = rb_first(&q->t_root))) { 368ff704050Sstephen hemminger struct sk_buff *skb = netem_rb_to_skb(p); 369ff704050Sstephen hemminger 370ff704050Sstephen hemminger rb_erase(p, &q->t_root); 371ff704050Sstephen hemminger skb->next = NULL; 372ff704050Sstephen hemminger skb->prev = NULL; 373ff704050Sstephen hemminger kfree_skb(skb); 374ff704050Sstephen hemminger } 375ff704050Sstephen hemminger } 376ff704050Sstephen hemminger 377960fb66eSEric Dumazet static void tfifo_enqueue(struct sk_buff *nskb, struct Qdisc *sch) 37850612537SEric Dumazet { 379aec0a40aSEric Dumazet struct netem_sched_data *q = qdisc_priv(sch); 38050612537SEric Dumazet psched_time_t tnext = netem_skb_cb(nskb)->time_to_send; 381aec0a40aSEric Dumazet struct rb_node **p = &q->t_root.rb_node, *parent = NULL; 38250612537SEric Dumazet 383aec0a40aSEric Dumazet while (*p) { 384aec0a40aSEric Dumazet struct sk_buff *skb; 38550612537SEric Dumazet 386aec0a40aSEric Dumazet parent = *p; 387aec0a40aSEric Dumazet skb = netem_rb_to_skb(parent); 38850612537SEric Dumazet if (tnext >= netem_skb_cb(skb)->time_to_send) 389aec0a40aSEric Dumazet p = &parent->rb_right; 390aec0a40aSEric Dumazet else 391aec0a40aSEric Dumazet p = &parent->rb_left; 39250612537SEric Dumazet } 39356b17425SEric Dumazet rb_link_node(&nskb->rbnode, parent, p); 39456b17425SEric Dumazet rb_insert_color(&nskb->rbnode, &q->t_root); 395aec0a40aSEric Dumazet sch->q.qlen++; 39650612537SEric Dumazet } 39750612537SEric Dumazet 3980afb51e7SStephen Hemminger /* 3990afb51e7SStephen Hemminger * Insert one skb into qdisc. 4000afb51e7SStephen Hemminger * Note: parent depends on return value to account for queue length. 4010afb51e7SStephen Hemminger * NET_XMIT_DROP: queue length didn't change. 4020afb51e7SStephen Hemminger * NET_XMIT_SUCCESS: one skb was queued. 4030afb51e7SStephen Hemminger */ 4041da177e4SLinus Torvalds static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch) 4051da177e4SLinus Torvalds { 4061da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 40789e1df74SGuillaume Chazarain /* We don't fill cb now as skb_unshare() may invalidate it */ 40889e1df74SGuillaume Chazarain struct netem_skb_cb *cb; 4090afb51e7SStephen Hemminger struct sk_buff *skb2; 4100afb51e7SStephen Hemminger int count = 1; 4111da177e4SLinus Torvalds 4120afb51e7SStephen Hemminger /* Random duplication */ 4130afb51e7SStephen Hemminger if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) 4140afb51e7SStephen Hemminger ++count; 4150afb51e7SStephen Hemminger 416661b7972Sstephen hemminger /* Drop packet? */ 417e4ae004bSEric Dumazet if (loss_event(q)) { 418e4ae004bSEric Dumazet if (q->ecn && INET_ECN_set_ce(skb)) 41925331d6cSJohn Fastabend qdisc_qstats_drop(sch); /* mark packet */ 420e4ae004bSEric Dumazet else 4210afb51e7SStephen Hemminger --count; 422e4ae004bSEric Dumazet } 4230afb51e7SStephen Hemminger if (count == 0) { 42425331d6cSJohn Fastabend qdisc_qstats_drop(sch); 4251da177e4SLinus Torvalds kfree_skb(skb); 426c27f339aSJarek Poplawski return NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; 4271da177e4SLinus Torvalds } 4281da177e4SLinus Torvalds 4295a308f40SEric Dumazet /* If a delay is expected, orphan the skb. (orphaning usually takes 4305a308f40SEric Dumazet * place at TX completion time, so _before_ the link transit delay) 4315a308f40SEric Dumazet */ 4325a308f40SEric Dumazet if (q->latency || q->jitter) 433f2f872f9SEric Dumazet skb_orphan_partial(skb); 4344e8a5201SDavid S. Miller 4350afb51e7SStephen Hemminger /* 4360afb51e7SStephen Hemminger * If we need to duplicate packet, then re-insert at top of the 4370afb51e7SStephen Hemminger * qdisc tree, since parent queuer expects that only one 4380afb51e7SStephen Hemminger * skb will be queued. 439d5d75cd6SStephen Hemminger */ 4400afb51e7SStephen Hemminger if (count > 1 && (skb2 = skb_clone(skb, GFP_ATOMIC)) != NULL) { 4417698b4fcSDavid S. Miller struct Qdisc *rootq = qdisc_root(sch); 4420afb51e7SStephen Hemminger u32 dupsave = q->duplicate; /* prevent duplicating a dup... */ 443d5d75cd6SStephen Hemminger 444b396cca6SEric Dumazet q->duplicate = 0; 445b396cca6SEric Dumazet rootq->enqueue(skb2, rootq); 4460afb51e7SStephen Hemminger q->duplicate = dupsave; 4471da177e4SLinus Torvalds } 4481da177e4SLinus Torvalds 449c865e5d9SStephen Hemminger /* 450c865e5d9SStephen Hemminger * Randomized packet corruption. 451c865e5d9SStephen Hemminger * Make copy if needed since we are modifying 452c865e5d9SStephen Hemminger * If packet is going to be hardware checksummed, then 453c865e5d9SStephen Hemminger * do it now in software before we mangle it. 454c865e5d9SStephen Hemminger */ 455c865e5d9SStephen Hemminger if (q->corrupt && q->corrupt >= get_crandom(&q->corrupt_cor)) { 456f64f9e71SJoe Perches if (!(skb = skb_unshare(skb, GFP_ATOMIC)) || 457f64f9e71SJoe Perches (skb->ip_summed == CHECKSUM_PARTIAL && 458116a0fc3SEric Dumazet skb_checksum_help(skb))) 459116a0fc3SEric Dumazet return qdisc_drop(skb, sch); 460c865e5d9SStephen Hemminger 46163862b5bSAruna-Hewapathirane skb->data[prandom_u32() % skb_headlen(skb)] ^= 46263862b5bSAruna-Hewapathirane 1<<(prandom_u32() % 8); 463c865e5d9SStephen Hemminger } 464c865e5d9SStephen Hemminger 465960fb66eSEric Dumazet if (unlikely(skb_queue_len(&sch->q) >= sch->limit)) 466960fb66eSEric Dumazet return qdisc_reshape_fail(skb, sch); 467960fb66eSEric Dumazet 46825331d6cSJohn Fastabend qdisc_qstats_backlog_inc(sch, skb); 469960fb66eSEric Dumazet 4705f86173bSJussi Kivilinna cb = netem_skb_cb(skb); 471f64f9e71SJoe Perches if (q->gap == 0 || /* not doing reordering */ 472a42b4799SVijay Subramanian q->counter < q->gap - 1 || /* inside last reordering gap */ 473f64f9e71SJoe Perches q->reorder < get_crandom(&q->reorder_cor)) { 4740f9f32acSStephen Hemminger psched_time_t now; 47507aaa115SStephen Hemminger psched_tdiff_t delay; 47607aaa115SStephen Hemminger 47707aaa115SStephen Hemminger delay = tabledist(q->latency, q->jitter, 47807aaa115SStephen Hemminger &q->delay_cor, q->delay_dist); 47907aaa115SStephen Hemminger 4803bebcda2SPatrick McHardy now = psched_get_time(); 4817bc0f28cSHagen Paul Pfeifer 4827bc0f28cSHagen Paul Pfeifer if (q->rate) { 483aec0a40aSEric Dumazet struct sk_buff *last; 4847bc0f28cSHagen Paul Pfeifer 485aec0a40aSEric Dumazet if (!skb_queue_empty(&sch->q)) 486aec0a40aSEric Dumazet last = skb_peek_tail(&sch->q); 487aec0a40aSEric Dumazet else 488aec0a40aSEric Dumazet last = netem_rb_to_skb(rb_last(&q->t_root)); 489aec0a40aSEric Dumazet if (last) { 4907bc0f28cSHagen Paul Pfeifer /* 491a13d3104SJohannes Naab * Last packet in queue is reference point (now), 492a13d3104SJohannes Naab * calculate this time bonus and subtract 4937bc0f28cSHagen Paul Pfeifer * from delay. 4947bc0f28cSHagen Paul Pfeifer */ 495aec0a40aSEric Dumazet delay -= netem_skb_cb(last)->time_to_send - now; 496a13d3104SJohannes Naab delay = max_t(psched_tdiff_t, 0, delay); 497aec0a40aSEric Dumazet now = netem_skb_cb(last)->time_to_send; 4987bc0f28cSHagen Paul Pfeifer } 499a13d3104SJohannes Naab 5008cfd88d6SYang Yingliang delay += packet_len_2_sched_time(qdisc_pkt_len(skb), q); 5017bc0f28cSHagen Paul Pfeifer } 5027bc0f28cSHagen Paul Pfeifer 5037c59e25fSPatrick McHardy cb->time_to_send = now + delay; 504aec0a40aSEric Dumazet cb->tstamp_save = skb->tstamp; 5051da177e4SLinus Torvalds ++q->counter; 506960fb66eSEric Dumazet tfifo_enqueue(skb, sch); 5071da177e4SLinus Torvalds } else { 5080dca51d3SStephen Hemminger /* 5090dca51d3SStephen Hemminger * Do re-ordering by putting one out of N packets at the front 5100dca51d3SStephen Hemminger * of the queue. 5110dca51d3SStephen Hemminger */ 5123bebcda2SPatrick McHardy cb->time_to_send = psched_get_time(); 5130dca51d3SStephen Hemminger q->counter = 0; 5148ba25dadSJarek Poplawski 51550612537SEric Dumazet __skb_queue_head(&sch->q, skb); 516eb101924SHagen Paul Pfeifer sch->qstats.requeues++; 517378a2f09SJarek Poplawski } 5181da177e4SLinus Torvalds 51910f6dfcfSstephen hemminger return NET_XMIT_SUCCESS; 5201da177e4SLinus Torvalds } 5211da177e4SLinus Torvalds 5221da177e4SLinus Torvalds static unsigned int netem_drop(struct Qdisc *sch) 5231da177e4SLinus Torvalds { 5241da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 52550612537SEric Dumazet unsigned int len; 5261da177e4SLinus Torvalds 52750612537SEric Dumazet len = qdisc_queue_drop(sch); 528aec0a40aSEric Dumazet 529aec0a40aSEric Dumazet if (!len) { 530aec0a40aSEric Dumazet struct rb_node *p = rb_first(&q->t_root); 531aec0a40aSEric Dumazet 532aec0a40aSEric Dumazet if (p) { 533aec0a40aSEric Dumazet struct sk_buff *skb = netem_rb_to_skb(p); 534aec0a40aSEric Dumazet 535aec0a40aSEric Dumazet rb_erase(p, &q->t_root); 536aec0a40aSEric Dumazet sch->q.qlen--; 537aec0a40aSEric Dumazet skb->next = NULL; 538aec0a40aSEric Dumazet skb->prev = NULL; 53925331d6cSJohn Fastabend qdisc_qstats_backlog_dec(sch, skb); 540aec0a40aSEric Dumazet kfree_skb(skb); 541aec0a40aSEric Dumazet } 542aec0a40aSEric Dumazet } 54350612537SEric Dumazet if (!len && q->qdisc && q->qdisc->ops->drop) 54450612537SEric Dumazet len = q->qdisc->ops->drop(q->qdisc); 54550612537SEric Dumazet if (len) 54625331d6cSJohn Fastabend qdisc_qstats_drop(sch); 54750612537SEric Dumazet 5481da177e4SLinus Torvalds return len; 5491da177e4SLinus Torvalds } 5501da177e4SLinus Torvalds 5511da177e4SLinus Torvalds static struct sk_buff *netem_dequeue(struct Qdisc *sch) 5521da177e4SLinus Torvalds { 5531da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 5541da177e4SLinus Torvalds struct sk_buff *skb; 555aec0a40aSEric Dumazet struct rb_node *p; 5561da177e4SLinus Torvalds 557fd245a4aSEric Dumazet if (qdisc_is_throttled(sch)) 55811274e5aSStephen Hemminger return NULL; 55911274e5aSStephen Hemminger 56050612537SEric Dumazet tfifo_dequeue: 561aec0a40aSEric Dumazet skb = __skb_dequeue(&sch->q); 562771018e7SStephen Hemminger if (skb) { 56325331d6cSJohn Fastabend qdisc_qstats_backlog_dec(sch, skb); 5640ad2a836SBeshay, Joseph deliver: 565aec0a40aSEric Dumazet qdisc_unthrottled(sch); 566aec0a40aSEric Dumazet qdisc_bstats_update(sch, skb); 567aec0a40aSEric Dumazet return skb; 568aec0a40aSEric Dumazet } 569aec0a40aSEric Dumazet p = rb_first(&q->t_root); 570aec0a40aSEric Dumazet if (p) { 57136b7bfe0SEric Dumazet psched_time_t time_to_send; 57236b7bfe0SEric Dumazet 573aec0a40aSEric Dumazet skb = netem_rb_to_skb(p); 5740f9f32acSStephen Hemminger 5750f9f32acSStephen Hemminger /* if more time remaining? */ 57636b7bfe0SEric Dumazet time_to_send = netem_skb_cb(skb)->time_to_send; 57736b7bfe0SEric Dumazet if (time_to_send <= psched_get_time()) { 578aec0a40aSEric Dumazet rb_erase(p, &q->t_root); 579aec0a40aSEric Dumazet 580aec0a40aSEric Dumazet sch->q.qlen--; 5810ad2a836SBeshay, Joseph qdisc_qstats_backlog_dec(sch, skb); 582aec0a40aSEric Dumazet skb->next = NULL; 583aec0a40aSEric Dumazet skb->prev = NULL; 584aec0a40aSEric Dumazet skb->tstamp = netem_skb_cb(skb)->tstamp_save; 58503c05f0dSJarek Poplawski 5868caf1539SJarek Poplawski #ifdef CONFIG_NET_CLS_ACT 5878caf1539SJarek Poplawski /* 5888caf1539SJarek Poplawski * If it's at ingress let's pretend the delay is 5898caf1539SJarek Poplawski * from the network (tstamp will be updated). 5908caf1539SJarek Poplawski */ 5918caf1539SJarek Poplawski if (G_TC_FROM(skb->tc_verd) & AT_INGRESS) 5928caf1539SJarek Poplawski skb->tstamp.tv64 = 0; 5938caf1539SJarek Poplawski #endif 59410f6dfcfSstephen hemminger 59550612537SEric Dumazet if (q->qdisc) { 59650612537SEric Dumazet int err = qdisc_enqueue(skb, q->qdisc); 59750612537SEric Dumazet 59850612537SEric Dumazet if (unlikely(err != NET_XMIT_SUCCESS)) { 59950612537SEric Dumazet if (net_xmit_drop_count(err)) { 60025331d6cSJohn Fastabend qdisc_qstats_drop(sch); 6012ccccf5fSWANG Cong qdisc_tree_reduce_backlog(sch, 1, 6022ccccf5fSWANG Cong qdisc_pkt_len(skb)); 60350612537SEric Dumazet } 60450612537SEric Dumazet } 60550612537SEric Dumazet goto tfifo_dequeue; 60650612537SEric Dumazet } 607aec0a40aSEric Dumazet goto deliver; 60811274e5aSStephen Hemminger } 60907aaa115SStephen Hemminger 61050612537SEric Dumazet if (q->qdisc) { 61150612537SEric Dumazet skb = q->qdisc->ops->dequeue(q->qdisc); 61250612537SEric Dumazet if (skb) 61350612537SEric Dumazet goto deliver; 61450612537SEric Dumazet } 61536b7bfe0SEric Dumazet qdisc_watchdog_schedule(&q->watchdog, time_to_send); 6160f9f32acSStephen Hemminger } 6170f9f32acSStephen Hemminger 61850612537SEric Dumazet if (q->qdisc) { 61950612537SEric Dumazet skb = q->qdisc->ops->dequeue(q->qdisc); 62050612537SEric Dumazet if (skb) 62150612537SEric Dumazet goto deliver; 62250612537SEric Dumazet } 6230f9f32acSStephen Hemminger return NULL; 6241da177e4SLinus Torvalds } 6251da177e4SLinus Torvalds 6261da177e4SLinus Torvalds static void netem_reset(struct Qdisc *sch) 6271da177e4SLinus Torvalds { 6281da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 6291da177e4SLinus Torvalds 63050612537SEric Dumazet qdisc_reset_queue(sch); 631ff704050Sstephen hemminger tfifo_reset(sch); 63250612537SEric Dumazet if (q->qdisc) 6331da177e4SLinus Torvalds qdisc_reset(q->qdisc); 63459cb5c67SPatrick McHardy qdisc_watchdog_cancel(&q->watchdog); 6351da177e4SLinus Torvalds } 6361da177e4SLinus Torvalds 6376373a9a2Sstephen hemminger static void dist_free(struct disttable *d) 6386373a9a2Sstephen hemminger { 6394cb28970SWANG Cong kvfree(d); 6406373a9a2Sstephen hemminger } 6416373a9a2Sstephen hemminger 6421da177e4SLinus Torvalds /* 6431da177e4SLinus Torvalds * Distribution data is a variable size payload containing 6441da177e4SLinus Torvalds * signed 16 bit values. 6451da177e4SLinus Torvalds */ 6461e90474cSPatrick McHardy static int get_dist_table(struct Qdisc *sch, const struct nlattr *attr) 6471da177e4SLinus Torvalds { 6481da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 6496373a9a2Sstephen hemminger size_t n = nla_len(attr)/sizeof(__s16); 6501e90474cSPatrick McHardy const __s16 *data = nla_data(attr); 6517698b4fcSDavid S. Miller spinlock_t *root_lock; 6521da177e4SLinus Torvalds struct disttable *d; 6531da177e4SLinus Torvalds int i; 6546373a9a2Sstephen hemminger size_t s; 6551da177e4SLinus Torvalds 656df173bdaSstephen hemminger if (n > NETEM_DIST_MAX) 6571da177e4SLinus Torvalds return -EINVAL; 6581da177e4SLinus Torvalds 6596373a9a2Sstephen hemminger s = sizeof(struct disttable) + n * sizeof(s16); 660bb52c7acSEric Dumazet d = kmalloc(s, GFP_KERNEL | __GFP_NOWARN); 6616373a9a2Sstephen hemminger if (!d) 6626373a9a2Sstephen hemminger d = vmalloc(s); 6631da177e4SLinus Torvalds if (!d) 6641da177e4SLinus Torvalds return -ENOMEM; 6651da177e4SLinus Torvalds 6661da177e4SLinus Torvalds d->size = n; 6671da177e4SLinus Torvalds for (i = 0; i < n; i++) 6681da177e4SLinus Torvalds d->table[i] = data[i]; 6691da177e4SLinus Torvalds 670102396aeSJarek Poplawski root_lock = qdisc_root_sleeping_lock(sch); 6717698b4fcSDavid S. Miller 6727698b4fcSDavid S. Miller spin_lock_bh(root_lock); 673bb52c7acSEric Dumazet swap(q->delay_dist, d); 6747698b4fcSDavid S. Miller spin_unlock_bh(root_lock); 675bb52c7acSEric Dumazet 676bb52c7acSEric Dumazet dist_free(d); 6771da177e4SLinus Torvalds return 0; 6781da177e4SLinus Torvalds } 6791da177e4SLinus Torvalds 68049545a77SYang Yingliang static void get_correlation(struct netem_sched_data *q, const struct nlattr *attr) 6811da177e4SLinus Torvalds { 6821e90474cSPatrick McHardy const struct tc_netem_corr *c = nla_data(attr); 6831da177e4SLinus Torvalds 6841da177e4SLinus Torvalds init_crandom(&q->delay_cor, c->delay_corr); 6851da177e4SLinus Torvalds init_crandom(&q->loss_cor, c->loss_corr); 6861da177e4SLinus Torvalds init_crandom(&q->dup_cor, c->dup_corr); 6871da177e4SLinus Torvalds } 6881da177e4SLinus Torvalds 68949545a77SYang Yingliang static void get_reorder(struct netem_sched_data *q, const struct nlattr *attr) 6900dca51d3SStephen Hemminger { 6911e90474cSPatrick McHardy const struct tc_netem_reorder *r = nla_data(attr); 6920dca51d3SStephen Hemminger 6930dca51d3SStephen Hemminger q->reorder = r->probability; 6940dca51d3SStephen Hemminger init_crandom(&q->reorder_cor, r->correlation); 6950dca51d3SStephen Hemminger } 6960dca51d3SStephen Hemminger 69749545a77SYang Yingliang static void get_corrupt(struct netem_sched_data *q, const struct nlattr *attr) 698c865e5d9SStephen Hemminger { 6991e90474cSPatrick McHardy const struct tc_netem_corrupt *r = nla_data(attr); 700c865e5d9SStephen Hemminger 701c865e5d9SStephen Hemminger q->corrupt = r->probability; 702c865e5d9SStephen Hemminger init_crandom(&q->corrupt_cor, r->correlation); 703c865e5d9SStephen Hemminger } 704c865e5d9SStephen Hemminger 70549545a77SYang Yingliang static void get_rate(struct netem_sched_data *q, const struct nlattr *attr) 7067bc0f28cSHagen Paul Pfeifer { 7077bc0f28cSHagen Paul Pfeifer const struct tc_netem_rate *r = nla_data(attr); 7087bc0f28cSHagen Paul Pfeifer 7097bc0f28cSHagen Paul Pfeifer q->rate = r->rate; 71090b41a1cSHagen Paul Pfeifer q->packet_overhead = r->packet_overhead; 71190b41a1cSHagen Paul Pfeifer q->cell_size = r->cell_size; 712809fa972SHannes Frederic Sowa q->cell_overhead = r->cell_overhead; 71390b41a1cSHagen Paul Pfeifer if (q->cell_size) 71490b41a1cSHagen Paul Pfeifer q->cell_size_reciprocal = reciprocal_value(q->cell_size); 715809fa972SHannes Frederic Sowa else 716809fa972SHannes Frederic Sowa q->cell_size_reciprocal = (struct reciprocal_value) { 0 }; 7177bc0f28cSHagen Paul Pfeifer } 7187bc0f28cSHagen Paul Pfeifer 71949545a77SYang Yingliang static int get_loss_clg(struct netem_sched_data *q, const struct nlattr *attr) 720661b7972Sstephen hemminger { 721661b7972Sstephen hemminger const struct nlattr *la; 722661b7972Sstephen hemminger int rem; 723661b7972Sstephen hemminger 724661b7972Sstephen hemminger nla_for_each_nested(la, attr, rem) { 725661b7972Sstephen hemminger u16 type = nla_type(la); 726661b7972Sstephen hemminger 727661b7972Sstephen hemminger switch (type) { 728661b7972Sstephen hemminger case NETEM_LOSS_GI: { 729661b7972Sstephen hemminger const struct tc_netem_gimodel *gi = nla_data(la); 730661b7972Sstephen hemminger 7312494654dSstephen hemminger if (nla_len(la) < sizeof(struct tc_netem_gimodel)) { 732661b7972Sstephen hemminger pr_info("netem: incorrect gi model size\n"); 733661b7972Sstephen hemminger return -EINVAL; 734661b7972Sstephen hemminger } 735661b7972Sstephen hemminger 736661b7972Sstephen hemminger q->loss_model = CLG_4_STATES; 737661b7972Sstephen hemminger 7383fbac2a8SYang Yingliang q->clg.state = TX_IN_GAP_PERIOD; 739661b7972Sstephen hemminger q->clg.a1 = gi->p13; 740661b7972Sstephen hemminger q->clg.a2 = gi->p31; 741661b7972Sstephen hemminger q->clg.a3 = gi->p32; 742661b7972Sstephen hemminger q->clg.a4 = gi->p14; 743661b7972Sstephen hemminger q->clg.a5 = gi->p23; 744661b7972Sstephen hemminger break; 745661b7972Sstephen hemminger } 746661b7972Sstephen hemminger 747661b7972Sstephen hemminger case NETEM_LOSS_GE: { 748661b7972Sstephen hemminger const struct tc_netem_gemodel *ge = nla_data(la); 749661b7972Sstephen hemminger 7502494654dSstephen hemminger if (nla_len(la) < sizeof(struct tc_netem_gemodel)) { 7512494654dSstephen hemminger pr_info("netem: incorrect ge model size\n"); 752661b7972Sstephen hemminger return -EINVAL; 753661b7972Sstephen hemminger } 754661b7972Sstephen hemminger 755661b7972Sstephen hemminger q->loss_model = CLG_GILB_ELL; 7563fbac2a8SYang Yingliang q->clg.state = GOOD_STATE; 757661b7972Sstephen hemminger q->clg.a1 = ge->p; 758661b7972Sstephen hemminger q->clg.a2 = ge->r; 759661b7972Sstephen hemminger q->clg.a3 = ge->h; 760661b7972Sstephen hemminger q->clg.a4 = ge->k1; 761661b7972Sstephen hemminger break; 762661b7972Sstephen hemminger } 763661b7972Sstephen hemminger 764661b7972Sstephen hemminger default: 765661b7972Sstephen hemminger pr_info("netem: unknown loss type %u\n", type); 766661b7972Sstephen hemminger return -EINVAL; 767661b7972Sstephen hemminger } 768661b7972Sstephen hemminger } 769661b7972Sstephen hemminger 770661b7972Sstephen hemminger return 0; 771661b7972Sstephen hemminger } 772661b7972Sstephen hemminger 77327a3421eSPatrick McHardy static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = { 77427a3421eSPatrick McHardy [TCA_NETEM_CORR] = { .len = sizeof(struct tc_netem_corr) }, 77527a3421eSPatrick McHardy [TCA_NETEM_REORDER] = { .len = sizeof(struct tc_netem_reorder) }, 77627a3421eSPatrick McHardy [TCA_NETEM_CORRUPT] = { .len = sizeof(struct tc_netem_corrupt) }, 7777bc0f28cSHagen Paul Pfeifer [TCA_NETEM_RATE] = { .len = sizeof(struct tc_netem_rate) }, 778661b7972Sstephen hemminger [TCA_NETEM_LOSS] = { .type = NLA_NESTED }, 779e4ae004bSEric Dumazet [TCA_NETEM_ECN] = { .type = NLA_U32 }, 7806a031f67SYang Yingliang [TCA_NETEM_RATE64] = { .type = NLA_U64 }, 78127a3421eSPatrick McHardy }; 78227a3421eSPatrick McHardy 7832c10b32bSThomas Graf static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr *nla, 7842c10b32bSThomas Graf const struct nla_policy *policy, int len) 7852c10b32bSThomas Graf { 7862c10b32bSThomas Graf int nested_len = nla_len(nla) - NLA_ALIGN(len); 7872c10b32bSThomas Graf 788661b7972Sstephen hemminger if (nested_len < 0) { 789661b7972Sstephen hemminger pr_info("netem: invalid attributes len %d\n", nested_len); 7902c10b32bSThomas Graf return -EINVAL; 791661b7972Sstephen hemminger } 792661b7972Sstephen hemminger 7932c10b32bSThomas Graf if (nested_len >= nla_attr_size(0)) 7942c10b32bSThomas Graf return nla_parse(tb, maxtype, nla_data(nla) + NLA_ALIGN(len), 7952c10b32bSThomas Graf nested_len, policy); 796661b7972Sstephen hemminger 7972c10b32bSThomas Graf memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1)); 7982c10b32bSThomas Graf return 0; 7992c10b32bSThomas Graf } 8002c10b32bSThomas Graf 801c865e5d9SStephen Hemminger /* Parse netlink message to set options */ 8021e90474cSPatrick McHardy static int netem_change(struct Qdisc *sch, struct nlattr *opt) 8031da177e4SLinus Torvalds { 8041da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 805b03f4672SPatrick McHardy struct nlattr *tb[TCA_NETEM_MAX + 1]; 8061da177e4SLinus Torvalds struct tc_netem_qopt *qopt; 80754a4b05cSYang Yingliang struct clgstate old_clg; 80854a4b05cSYang Yingliang int old_loss_model = CLG_RANDOM; 8091da177e4SLinus Torvalds int ret; 8101da177e4SLinus Torvalds 811b03f4672SPatrick McHardy if (opt == NULL) 8121da177e4SLinus Torvalds return -EINVAL; 8131da177e4SLinus Torvalds 8142c10b32bSThomas Graf qopt = nla_data(opt); 8152c10b32bSThomas Graf ret = parse_attr(tb, TCA_NETEM_MAX, opt, netem_policy, sizeof(*qopt)); 816b03f4672SPatrick McHardy if (ret < 0) 817b03f4672SPatrick McHardy return ret; 818b03f4672SPatrick McHardy 81954a4b05cSYang Yingliang /* backup q->clg and q->loss_model */ 82054a4b05cSYang Yingliang old_clg = q->clg; 82154a4b05cSYang Yingliang old_loss_model = q->loss_model; 82254a4b05cSYang Yingliang 82354a4b05cSYang Yingliang if (tb[TCA_NETEM_LOSS]) { 82449545a77SYang Yingliang ret = get_loss_clg(q, tb[TCA_NETEM_LOSS]); 82554a4b05cSYang Yingliang if (ret) { 82654a4b05cSYang Yingliang q->loss_model = old_loss_model; 82754a4b05cSYang Yingliang return ret; 82854a4b05cSYang Yingliang } 82954a4b05cSYang Yingliang } else { 83054a4b05cSYang Yingliang q->loss_model = CLG_RANDOM; 83154a4b05cSYang Yingliang } 83254a4b05cSYang Yingliang 83354a4b05cSYang Yingliang if (tb[TCA_NETEM_DELAY_DIST]) { 83454a4b05cSYang Yingliang ret = get_dist_table(sch, tb[TCA_NETEM_DELAY_DIST]); 83554a4b05cSYang Yingliang if (ret) { 83654a4b05cSYang Yingliang /* recover clg and loss_model, in case of 83754a4b05cSYang Yingliang * q->clg and q->loss_model were modified 83854a4b05cSYang Yingliang * in get_loss_clg() 83954a4b05cSYang Yingliang */ 84054a4b05cSYang Yingliang q->clg = old_clg; 84154a4b05cSYang Yingliang q->loss_model = old_loss_model; 84254a4b05cSYang Yingliang return ret; 84354a4b05cSYang Yingliang } 84454a4b05cSYang Yingliang } 84554a4b05cSYang Yingliang 84650612537SEric Dumazet sch->limit = qopt->limit; 8471da177e4SLinus Torvalds 8481da177e4SLinus Torvalds q->latency = qopt->latency; 8491da177e4SLinus Torvalds q->jitter = qopt->jitter; 8501da177e4SLinus Torvalds q->limit = qopt->limit; 8511da177e4SLinus Torvalds q->gap = qopt->gap; 8520dca51d3SStephen Hemminger q->counter = 0; 8531da177e4SLinus Torvalds q->loss = qopt->loss; 8541da177e4SLinus Torvalds q->duplicate = qopt->duplicate; 8551da177e4SLinus Torvalds 856bb2f8cc0SStephen Hemminger /* for compatibility with earlier versions. 857bb2f8cc0SStephen Hemminger * if gap is set, need to assume 100% probability 8580dca51d3SStephen Hemminger */ 859a362e0a7SStephen Hemminger if (q->gap) 8600dca51d3SStephen Hemminger q->reorder = ~0; 8610dca51d3SStephen Hemminger 862265eb67fSStephen Hemminger if (tb[TCA_NETEM_CORR]) 86349545a77SYang Yingliang get_correlation(q, tb[TCA_NETEM_CORR]); 8641da177e4SLinus Torvalds 865265eb67fSStephen Hemminger if (tb[TCA_NETEM_REORDER]) 86649545a77SYang Yingliang get_reorder(q, tb[TCA_NETEM_REORDER]); 8671da177e4SLinus Torvalds 868265eb67fSStephen Hemminger if (tb[TCA_NETEM_CORRUPT]) 86949545a77SYang Yingliang get_corrupt(q, tb[TCA_NETEM_CORRUPT]); 8701da177e4SLinus Torvalds 8717bc0f28cSHagen Paul Pfeifer if (tb[TCA_NETEM_RATE]) 87249545a77SYang Yingliang get_rate(q, tb[TCA_NETEM_RATE]); 8737bc0f28cSHagen Paul Pfeifer 8746a031f67SYang Yingliang if (tb[TCA_NETEM_RATE64]) 8756a031f67SYang Yingliang q->rate = max_t(u64, q->rate, 8766a031f67SYang Yingliang nla_get_u64(tb[TCA_NETEM_RATE64])); 8776a031f67SYang Yingliang 878e4ae004bSEric Dumazet if (tb[TCA_NETEM_ECN]) 879e4ae004bSEric Dumazet q->ecn = nla_get_u32(tb[TCA_NETEM_ECN]); 880e4ae004bSEric Dumazet 881661b7972Sstephen hemminger return ret; 8821da177e4SLinus Torvalds } 8831da177e4SLinus Torvalds 8841e90474cSPatrick McHardy static int netem_init(struct Qdisc *sch, struct nlattr *opt) 8851da177e4SLinus Torvalds { 8861da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 8871da177e4SLinus Torvalds int ret; 8881da177e4SLinus Torvalds 8891da177e4SLinus Torvalds if (!opt) 8901da177e4SLinus Torvalds return -EINVAL; 8911da177e4SLinus Torvalds 89259cb5c67SPatrick McHardy qdisc_watchdog_init(&q->watchdog, sch); 8931da177e4SLinus Torvalds 894661b7972Sstephen hemminger q->loss_model = CLG_RANDOM; 8951da177e4SLinus Torvalds ret = netem_change(sch, opt); 89650612537SEric Dumazet if (ret) 897250a65f7Sstephen hemminger pr_info("netem: change failed\n"); 8981da177e4SLinus Torvalds return ret; 8991da177e4SLinus Torvalds } 9001da177e4SLinus Torvalds 9011da177e4SLinus Torvalds static void netem_destroy(struct Qdisc *sch) 9021da177e4SLinus Torvalds { 9031da177e4SLinus Torvalds struct netem_sched_data *q = qdisc_priv(sch); 9041da177e4SLinus Torvalds 90559cb5c67SPatrick McHardy qdisc_watchdog_cancel(&q->watchdog); 90650612537SEric Dumazet if (q->qdisc) 9071da177e4SLinus Torvalds qdisc_destroy(q->qdisc); 9086373a9a2Sstephen hemminger dist_free(q->delay_dist); 9091da177e4SLinus Torvalds } 9101da177e4SLinus Torvalds 911661b7972Sstephen hemminger static int dump_loss_model(const struct netem_sched_data *q, 912661b7972Sstephen hemminger struct sk_buff *skb) 913661b7972Sstephen hemminger { 914661b7972Sstephen hemminger struct nlattr *nest; 915661b7972Sstephen hemminger 916661b7972Sstephen hemminger nest = nla_nest_start(skb, TCA_NETEM_LOSS); 917661b7972Sstephen hemminger if (nest == NULL) 918661b7972Sstephen hemminger goto nla_put_failure; 919661b7972Sstephen hemminger 920661b7972Sstephen hemminger switch (q->loss_model) { 921661b7972Sstephen hemminger case CLG_RANDOM: 922661b7972Sstephen hemminger /* legacy loss model */ 923661b7972Sstephen hemminger nla_nest_cancel(skb, nest); 924661b7972Sstephen hemminger return 0; /* no data */ 925661b7972Sstephen hemminger 926661b7972Sstephen hemminger case CLG_4_STATES: { 927661b7972Sstephen hemminger struct tc_netem_gimodel gi = { 928661b7972Sstephen hemminger .p13 = q->clg.a1, 929661b7972Sstephen hemminger .p31 = q->clg.a2, 930661b7972Sstephen hemminger .p32 = q->clg.a3, 931661b7972Sstephen hemminger .p14 = q->clg.a4, 932661b7972Sstephen hemminger .p23 = q->clg.a5, 933661b7972Sstephen hemminger }; 934661b7972Sstephen hemminger 9351b34ec43SDavid S. Miller if (nla_put(skb, NETEM_LOSS_GI, sizeof(gi), &gi)) 9361b34ec43SDavid S. Miller goto nla_put_failure; 937661b7972Sstephen hemminger break; 938661b7972Sstephen hemminger } 939661b7972Sstephen hemminger case CLG_GILB_ELL: { 940661b7972Sstephen hemminger struct tc_netem_gemodel ge = { 941661b7972Sstephen hemminger .p = q->clg.a1, 942661b7972Sstephen hemminger .r = q->clg.a2, 943661b7972Sstephen hemminger .h = q->clg.a3, 944661b7972Sstephen hemminger .k1 = q->clg.a4, 945661b7972Sstephen hemminger }; 946661b7972Sstephen hemminger 9471b34ec43SDavid S. Miller if (nla_put(skb, NETEM_LOSS_GE, sizeof(ge), &ge)) 9481b34ec43SDavid S. Miller goto nla_put_failure; 949661b7972Sstephen hemminger break; 950661b7972Sstephen hemminger } 951661b7972Sstephen hemminger } 952661b7972Sstephen hemminger 953661b7972Sstephen hemminger nla_nest_end(skb, nest); 954661b7972Sstephen hemminger return 0; 955661b7972Sstephen hemminger 956661b7972Sstephen hemminger nla_put_failure: 957661b7972Sstephen hemminger nla_nest_cancel(skb, nest); 958661b7972Sstephen hemminger return -1; 959661b7972Sstephen hemminger } 960661b7972Sstephen hemminger 9611da177e4SLinus Torvalds static int netem_dump(struct Qdisc *sch, struct sk_buff *skb) 9621da177e4SLinus Torvalds { 9631da177e4SLinus Torvalds const struct netem_sched_data *q = qdisc_priv(sch); 964861d7f74Sstephen hemminger struct nlattr *nla = (struct nlattr *) skb_tail_pointer(skb); 9651da177e4SLinus Torvalds struct tc_netem_qopt qopt; 9661da177e4SLinus Torvalds struct tc_netem_corr cor; 9670dca51d3SStephen Hemminger struct tc_netem_reorder reorder; 968c865e5d9SStephen Hemminger struct tc_netem_corrupt corrupt; 9697bc0f28cSHagen Paul Pfeifer struct tc_netem_rate rate; 9701da177e4SLinus Torvalds 9711da177e4SLinus Torvalds qopt.latency = q->latency; 9721da177e4SLinus Torvalds qopt.jitter = q->jitter; 9731da177e4SLinus Torvalds qopt.limit = q->limit; 9741da177e4SLinus Torvalds qopt.loss = q->loss; 9751da177e4SLinus Torvalds qopt.gap = q->gap; 9761da177e4SLinus Torvalds qopt.duplicate = q->duplicate; 9771b34ec43SDavid S. Miller if (nla_put(skb, TCA_OPTIONS, sizeof(qopt), &qopt)) 9781b34ec43SDavid S. Miller goto nla_put_failure; 9791da177e4SLinus Torvalds 9801da177e4SLinus Torvalds cor.delay_corr = q->delay_cor.rho; 9811da177e4SLinus Torvalds cor.loss_corr = q->loss_cor.rho; 9821da177e4SLinus Torvalds cor.dup_corr = q->dup_cor.rho; 9831b34ec43SDavid S. Miller if (nla_put(skb, TCA_NETEM_CORR, sizeof(cor), &cor)) 9841b34ec43SDavid S. Miller goto nla_put_failure; 9850dca51d3SStephen Hemminger 9860dca51d3SStephen Hemminger reorder.probability = q->reorder; 9870dca51d3SStephen Hemminger reorder.correlation = q->reorder_cor.rho; 9881b34ec43SDavid S. Miller if (nla_put(skb, TCA_NETEM_REORDER, sizeof(reorder), &reorder)) 9891b34ec43SDavid S. Miller goto nla_put_failure; 9900dca51d3SStephen Hemminger 991c865e5d9SStephen Hemminger corrupt.probability = q->corrupt; 992c865e5d9SStephen Hemminger corrupt.correlation = q->corrupt_cor.rho; 9931b34ec43SDavid S. Miller if (nla_put(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt)) 9941b34ec43SDavid S. Miller goto nla_put_failure; 995c865e5d9SStephen Hemminger 9966a031f67SYang Yingliang if (q->rate >= (1ULL << 32)) { 9976a031f67SYang Yingliang if (nla_put_u64(skb, TCA_NETEM_RATE64, q->rate)) 9986a031f67SYang Yingliang goto nla_put_failure; 9996a031f67SYang Yingliang rate.rate = ~0U; 10006a031f67SYang Yingliang } else { 10017bc0f28cSHagen Paul Pfeifer rate.rate = q->rate; 10026a031f67SYang Yingliang } 100390b41a1cSHagen Paul Pfeifer rate.packet_overhead = q->packet_overhead; 100490b41a1cSHagen Paul Pfeifer rate.cell_size = q->cell_size; 100590b41a1cSHagen Paul Pfeifer rate.cell_overhead = q->cell_overhead; 10061b34ec43SDavid S. Miller if (nla_put(skb, TCA_NETEM_RATE, sizeof(rate), &rate)) 10071b34ec43SDavid S. Miller goto nla_put_failure; 10087bc0f28cSHagen Paul Pfeifer 1009e4ae004bSEric Dumazet if (q->ecn && nla_put_u32(skb, TCA_NETEM_ECN, q->ecn)) 1010e4ae004bSEric Dumazet goto nla_put_failure; 1011e4ae004bSEric Dumazet 1012661b7972Sstephen hemminger if (dump_loss_model(q, skb) != 0) 1013661b7972Sstephen hemminger goto nla_put_failure; 1014661b7972Sstephen hemminger 1015861d7f74Sstephen hemminger return nla_nest_end(skb, nla); 10161da177e4SLinus Torvalds 10171e90474cSPatrick McHardy nla_put_failure: 1018861d7f74Sstephen hemminger nlmsg_trim(skb, nla); 10191da177e4SLinus Torvalds return -1; 10201da177e4SLinus Torvalds } 10211da177e4SLinus Torvalds 102210f6dfcfSstephen hemminger static int netem_dump_class(struct Qdisc *sch, unsigned long cl, 102310f6dfcfSstephen hemminger struct sk_buff *skb, struct tcmsg *tcm) 102410f6dfcfSstephen hemminger { 102510f6dfcfSstephen hemminger struct netem_sched_data *q = qdisc_priv(sch); 102610f6dfcfSstephen hemminger 102750612537SEric Dumazet if (cl != 1 || !q->qdisc) /* only one class */ 102810f6dfcfSstephen hemminger return -ENOENT; 102910f6dfcfSstephen hemminger 103010f6dfcfSstephen hemminger tcm->tcm_handle |= TC_H_MIN(1); 103110f6dfcfSstephen hemminger tcm->tcm_info = q->qdisc->handle; 103210f6dfcfSstephen hemminger 103310f6dfcfSstephen hemminger return 0; 103410f6dfcfSstephen hemminger } 103510f6dfcfSstephen hemminger 103610f6dfcfSstephen hemminger static int netem_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, 103710f6dfcfSstephen hemminger struct Qdisc **old) 103810f6dfcfSstephen hemminger { 103910f6dfcfSstephen hemminger struct netem_sched_data *q = qdisc_priv(sch); 104010f6dfcfSstephen hemminger 104186a7996cSWANG Cong *old = qdisc_replace(sch, new, &q->qdisc); 104210f6dfcfSstephen hemminger return 0; 104310f6dfcfSstephen hemminger } 104410f6dfcfSstephen hemminger 104510f6dfcfSstephen hemminger static struct Qdisc *netem_leaf(struct Qdisc *sch, unsigned long arg) 104610f6dfcfSstephen hemminger { 104710f6dfcfSstephen hemminger struct netem_sched_data *q = qdisc_priv(sch); 104810f6dfcfSstephen hemminger return q->qdisc; 104910f6dfcfSstephen hemminger } 105010f6dfcfSstephen hemminger 105110f6dfcfSstephen hemminger static unsigned long netem_get(struct Qdisc *sch, u32 classid) 105210f6dfcfSstephen hemminger { 105310f6dfcfSstephen hemminger return 1; 105410f6dfcfSstephen hemminger } 105510f6dfcfSstephen hemminger 105610f6dfcfSstephen hemminger static void netem_put(struct Qdisc *sch, unsigned long arg) 105710f6dfcfSstephen hemminger { 105810f6dfcfSstephen hemminger } 105910f6dfcfSstephen hemminger 106010f6dfcfSstephen hemminger static void netem_walk(struct Qdisc *sch, struct qdisc_walker *walker) 106110f6dfcfSstephen hemminger { 106210f6dfcfSstephen hemminger if (!walker->stop) { 106310f6dfcfSstephen hemminger if (walker->count >= walker->skip) 106410f6dfcfSstephen hemminger if (walker->fn(sch, 1, walker) < 0) { 106510f6dfcfSstephen hemminger walker->stop = 1; 106610f6dfcfSstephen hemminger return; 106710f6dfcfSstephen hemminger } 106810f6dfcfSstephen hemminger walker->count++; 106910f6dfcfSstephen hemminger } 107010f6dfcfSstephen hemminger } 107110f6dfcfSstephen hemminger 107210f6dfcfSstephen hemminger static const struct Qdisc_class_ops netem_class_ops = { 107310f6dfcfSstephen hemminger .graft = netem_graft, 107410f6dfcfSstephen hemminger .leaf = netem_leaf, 107510f6dfcfSstephen hemminger .get = netem_get, 107610f6dfcfSstephen hemminger .put = netem_put, 107710f6dfcfSstephen hemminger .walk = netem_walk, 107810f6dfcfSstephen hemminger .dump = netem_dump_class, 107910f6dfcfSstephen hemminger }; 108010f6dfcfSstephen hemminger 108120fea08bSEric Dumazet static struct Qdisc_ops netem_qdisc_ops __read_mostly = { 10821da177e4SLinus Torvalds .id = "netem", 108310f6dfcfSstephen hemminger .cl_ops = &netem_class_ops, 10841da177e4SLinus Torvalds .priv_size = sizeof(struct netem_sched_data), 10851da177e4SLinus Torvalds .enqueue = netem_enqueue, 10861da177e4SLinus Torvalds .dequeue = netem_dequeue, 108777be155cSJarek Poplawski .peek = qdisc_peek_dequeued, 10881da177e4SLinus Torvalds .drop = netem_drop, 10891da177e4SLinus Torvalds .init = netem_init, 10901da177e4SLinus Torvalds .reset = netem_reset, 10911da177e4SLinus Torvalds .destroy = netem_destroy, 10921da177e4SLinus Torvalds .change = netem_change, 10931da177e4SLinus Torvalds .dump = netem_dump, 10941da177e4SLinus Torvalds .owner = THIS_MODULE, 10951da177e4SLinus Torvalds }; 10961da177e4SLinus Torvalds 10971da177e4SLinus Torvalds 10981da177e4SLinus Torvalds static int __init netem_module_init(void) 10991da177e4SLinus Torvalds { 1100eb229c4cSStephen Hemminger pr_info("netem: version " VERSION "\n"); 11011da177e4SLinus Torvalds return register_qdisc(&netem_qdisc_ops); 11021da177e4SLinus Torvalds } 11031da177e4SLinus Torvalds static void __exit netem_module_exit(void) 11041da177e4SLinus Torvalds { 11051da177e4SLinus Torvalds unregister_qdisc(&netem_qdisc_ops); 11061da177e4SLinus Torvalds } 11071da177e4SLinus Torvalds module_init(netem_module_init) 11081da177e4SLinus Torvalds module_exit(netem_module_exit) 11091da177e4SLinus Torvalds MODULE_LICENSE("GPL"); 1110