ip_dummynet.h revision 107899
1275970Scy/* 2275970Scy * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa 3275970Scy * Portions Copyright (c) 2000 Akamba Corp. 4275970Scy * All rights reserved 5275970Scy * 6275970Scy * Redistribution and use in source and binary forms, with or without 7275970Scy * modification, are permitted provided that the following conditions 8275970Scy * are met: 9275970Scy * 1. Redistributions of source code must retain the above copyright 10275970Scy * notice, this list of conditions and the following disclaimer. 11275970Scy * 2. Redistributions in binary form must reproduce the above copyright 12275970Scy * notice, this list of conditions and the following disclaimer in the 13275970Scy * documentation and/or other materials provided with the distribution. 14275970Scy * 15275970Scy * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16275970Scy * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17275970Scy * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18275970Scy * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19275970Scy * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20275970Scy * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21275970Scy * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22275970Scy * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23275970Scy * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24275970Scy * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25275970Scy * SUCH DAMAGE. 26275970Scy * 27275970Scy * $FreeBSD: head/sys/netinet/ip_dummynet.h 107899 2002-12-15 10:23:02Z maxim $ 28275970Scy */ 29275970Scy 30275970Scy#ifndef _IP_DUMMYNET_H 31275970Scy#define _IP_DUMMYNET_H 32275970Scy 33275970Scy/* 34275970Scy * Definition of dummynet data structures. In the structures, I decided 35275970Scy * not to use the macros in <sys/queue.h> in the hope of making the code 36275970Scy * easier to port to other architectures. The type of lists and queue we 37275970Scy * use here is pretty simple anyways. 38275970Scy */ 39275970Scy 40275970Scy/* 41275970Scy * We start with a heap, which is used in the scheduler to decide when 42275970Scy * to transmit packets etc. 43275970Scy * 44275970Scy * The key for the heap is used for two different values: 45275970Scy * 46275970Scy * 1. timer ticks- max 10K/second, so 32 bits are enough; 47275970Scy * 48285612Sdelphij * 2. virtual times. These increase in steps of len/x, where len is the 49285612Sdelphij * packet length, and x is either the weight of the flow, or the 50275970Scy * sum of all weights. 51275970Scy * If we limit to max 1000 flows and a max weight of 100, then 52275970Scy * x needs 17 bits. The packet size is 16 bits, so we can easily 53275970Scy * overflow if we do not allow errors. 54275970Scy * So we use a key "dn_key" which is 64 bits. Some macros are used to 55275970Scy * compare key values and handle wraparounds. 56275970Scy * MAX64 returns the largest of two key values. 57275970Scy * MY_M is used as a shift count when doing fixed point arithmetic 58275970Scy * (a better name would be useful...). 59275970Scy */ 60275970Scytypedef u_int64_t dn_key ; /* sorting key */ 61275970Scy#define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 62275970Scy#define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 63275970Scy#define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) 64275970Scy#define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) 65275970Scy#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) 66275970Scy#define MY_M 16 /* number of left shift to obtain a larger precision */ 67275970Scy 68275970Scy/* 69275970Scy * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 70275970Scy * virtual time wraps every 15 days. 71275970Scy */ 72275970Scy 73275970Scy/* 74275970Scy * The OFFSET_OF macro is used to return the offset of a field within 75275970Scy * a structure. It is used by the heap management routines. 76275970Scy */ 77275970Scy#define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) 78275970Scy 79275970Scy/* 80275970Scy * The maximum hash table size for queues. This value must be a power 81275970Scy * of 2. 82275970Scy */ 83275970Scy#define DN_MAX_HASH_SIZE 65536 84275970Scy 85275970Scy/* 86275970Scy * A heap entry is made of a key and a pointer to the actual 87275970Scy * object stored in the heap. 88275970Scy * The heap is an array of dn_heap_entry entries, dynamically allocated. 89275970Scy * Current size is "size", with "elements" actually in use. 90275970Scy * The heap normally supports only ordered insert and extract from the top. 91275970Scy * If we want to extract an object from the middle of the heap, we 92275970Scy * have to know where the object itself is located in the heap (or we 93275970Scy * need to scan the whole array). To this purpose, an object has a 94275970Scy * field (int) which contains the index of the object itself into the 95275970Scy * heap. When the object is moved, the field must also be updated. 96275970Scy * The offset of the index in the object is stored in the 'offset' 97275970Scy * field in the heap descriptor. The assumption is that this offset 98275970Scy * is non-zero if we want to support extract from the middle. 99275970Scy */ 100275970Scystruct dn_heap_entry { 101275970Scy dn_key key ; /* sorting key. Topmost element is smallest one */ 102275970Scy void *object ; /* object pointer */ 103275970Scy} ; 104275970Scy 105275970Scystruct dn_heap { 106275970Scy int size ; 107275970Scy int elements ; 108275970Scy int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 109275970Scy struct dn_heap_entry *p ; /* really an array of "size" entries */ 110275970Scy} ; 111275970Scy 112275970Scy/* 113275970Scy * struct dn_pkt identifies a packet in the dummynet queue, but 114275970Scy * is also used to tag packets passed back to the various destinations 115275970Scy * (ip_input(), ip_output(), bdg_forward() and so on). 116275970Scy * As such the first part of the structure must be a struct m_hdr, 117275970Scy * followed by dummynet-specific parameters. The m_hdr must be 118275970Scy * initialized with 119275970Scy * mh_type = MT_TAG; 120275970Scy * mh_flags = PACKET_TYPE_DUMMYNET; 121275970Scy * mh_next = <pointer to the actual mbuf> 122275970Scy * 123275970Scy * mh_nextpkt, mh_data are free for dummynet use (mh_nextpkt is used to 124275970Scy * build a linked list of packets in a dummynet queue). 125275970Scy */ 126275970Scystruct dn_pkt { 127275970Scy struct m_hdr hdr ; 128275970Scy#define DN_NEXT(x) (struct dn_pkt *)(x)->hdr.mh_nextpkt 129275970Scy#define dn_m hdr.mh_next /* packet to be forwarded */ 130275970Scy 131275970Scy struct ip_fw *rule; /* matching rule */ 132275970Scy int dn_dir; /* action when packet comes out. */ 133275970Scy#define DN_TO_IP_OUT 1 134275970Scy#define DN_TO_IP_IN 2 135275970Scy#define DN_TO_BDG_FWD 3 136275970Scy#define DN_TO_ETH_DEMUX 4 137275970Scy#define DN_TO_ETH_OUT 5 138275970Scy 139275970Scy dn_key output_time; /* when the pkt is due for delivery */ 140275970Scy struct ifnet *ifp; /* interface, for ip_output */ 141275970Scy struct sockaddr_in *dn_dst ; 142275970Scy struct route ro; /* route, for ip_output. MUST COPY */ 143275970Scy int flags ; /* flags, for ip_output (IPv6 ?) */ 144275970Scy}; 145275970Scy 146275970Scy/* 147275970Scy * Overall structure of dummynet (with WF2Q+): 148275970Scy 149275970ScyIn dummynet, packets are selected with the firewall rules, and passed 150275970Scyto two different objects: PIPE or QUEUE. 151275970Scy 152275970ScyA QUEUE is just a queue with configurable size and queue management 153275970Scypolicy. It is also associated with a mask (to discriminate among 154275970Scydifferent flows), a weight (used to give different shares of the 155275970Scybandwidth to different flows) and a "pipe", which essentially 156275970Scysupplies the transmit clock for all queues associated with that 157275970Scypipe. 158275970Scy 159275970ScyA PIPE emulates a fixed-bandwidth link, whose bandwidth is 160275970Scyconfigurable. The "clock" for a pipe can come from either an 161275970Scyinternal timer, or from the transmit interrupt of an interface. 162275970ScyA pipe is also associated with one (or more, if masks are used) 163275970Scyqueue, where all packets for that pipe are stored. 164275970Scy 165275970ScyThe bandwidth available on the pipe is shared by the queues 166275970Scyassociated with that pipe (only one in case the packet is sent 167275970Scyto a PIPE) according to the WF2Q+ scheduling algorithm and the 168275970Scyconfigured weights. 169275970Scy 170275970ScyIn general, incoming packets are stored in the appropriate queue, 171275970Scywhich is then placed into one of a few heaps managed by a scheduler 172275970Scyto decide when the packet should be extracted. 173275970ScyThe scheduler (a function called dummynet()) is run at every timer 174275970Scytick, and grabs queues from the head of the heaps when they are 175275970Scyready for processing. 176275970Scy 177275970ScyThere are three data structures definining a pipe and associated queues: 178275970Scy 179275970Scy + dn_pipe, which contains the main configuration parameters related 180275970Scy to delay and bandwidth; 181275970Scy + dn_flow_set, which contains WF2Q+ configuration, flow 182275970Scy masks, plr and RED configuration; 183275970Scy + dn_flow_queue, which is the per-flow queue (containing the packets) 184275970Scy 185275970ScyMultiple dn_flow_set can be linked to the same pipe, and multiple 186275970Scydn_flow_queue can be linked to the same dn_flow_set. 187275970ScyAll data structures are linked in a linear list which is used for 188275970Scyhousekeeping purposes. 189275970Scy 190275970ScyDuring configuration, we create and initialize the dn_flow_set 191275970Scyand dn_pipe structures (a dn_pipe also contains a dn_flow_set). 192275970Scy 193275970ScyAt runtime: packets are sent to the appropriate dn_flow_set (either 194275970ScyWFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 195275970Scywhich in turn dispatches them to the appropriate dn_flow_queue 196275970Scy(created dynamically according to the masks). 197275970Scy 198275970ScyThe transmit clock for fixed rate flows (ready_event()) selects the 199275970Scydn_flow_queue to be used to transmit the next packet. For WF2Q, 200275970Scywfq_ready_event() extract a pipe which in turn selects the right 201275970Scyflow using a number of heaps defined into the pipe itself. 202275970Scy 203275970Scy * 204275970Scy */ 205275970Scy 206275970Scy/* 207275970Scy * per flow queue. This contains the flow identifier, the queue 208275970Scy * of packets, counters, and parameters used to support both RED and 209275970Scy * WF2Q+. 210275970Scy * 211275970Scy * A dn_flow_queue is created and initialized whenever a packet for 212275970Scy * a new flow arrives. 213275970Scy */ 214275970Scystruct dn_flow_queue { 215275970Scy struct dn_flow_queue *next ; 216275970Scy struct ipfw_flow_id id ; 217275970Scy 218275970Scy struct dn_pkt *head, *tail ; /* queue of packets */ 219275970Scy u_int len ; 220275970Scy u_int len_bytes ; 221275970Scy long numbytes ; /* credit for transmission (dynamic queues) */ 222275970Scy 223275970Scy u_int64_t tot_pkts ; /* statistics counters */ 224275970Scy u_int64_t tot_bytes ; 225275970Scy u_int32_t drops ; 226275970Scy 227275970Scy int hash_slot ; /* debugging/diagnostic */ 228275970Scy 229275970Scy /* RED parameters */ 230275970Scy int avg ; /* average queue length est. (scaled) */ 231275970Scy int count ; /* arrivals since last RED drop */ 232275970Scy int random ; /* random value (scaled) */ 233275970Scy u_int32_t q_time ; /* start of queue idle time */ 234275970Scy 235275970Scy /* WF2Q+ support */ 236275970Scy struct dn_flow_set *fs ; /* parent flow set */ 237275970Scy int heap_pos ; /* position (index) of struct in heap */ 238275970Scy dn_key sched_time ; /* current time when queue enters ready_heap */ 239275970Scy 240275970Scy dn_key S,F ; /* start time, finish time */ 241275970Scy /* 242275970Scy * Setting F < S means the timestamp is invalid. We only need 243275970Scy * to test this when the queue is empty. 244275970Scy */ 245275970Scy} ; 246275970Scy 247275970Scy/* 248275970Scy * flow_set descriptor. Contains the "template" parameters for the 249275970Scy * queue configuration, and pointers to the hash table of dn_flow_queue's. 250275970Scy * 251275970Scy * The hash table is an array of lists -- we identify the slot by 252275970Scy * hashing the flow-id, then scan the list looking for a match. 253275970Scy * The size of the hash table (buckets) is configurable on a per-queue 254275970Scy * basis. 255275970Scy * 256275970Scy * A dn_flow_set is created whenever a new queue or pipe is created (in the 257275970Scy * latter case, the structure is located inside the struct dn_pipe). 258275970Scy */ 259275970Scystruct dn_flow_set { 260275970Scy struct dn_flow_set *next; /* next flow set in all_flow_sets list */ 261275970Scy 262275970Scy u_short fs_nr ; /* flow_set number */ 263275970Scy u_short flags_fs; 264275970Scy#define DN_HAVE_FLOW_MASK 0x0001 265275970Scy#define DN_IS_RED 0x0002 266275970Scy#define DN_IS_GENTLE_RED 0x0004 267275970Scy#define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 268275970Scy#define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 269275970Scy#define DN_IS_PIPE 0x4000 270285612Sdelphij#define DN_IS_QUEUE 0x8000 271275970Scy 272275970Scy struct dn_pipe *pipe ; /* pointer to parent pipe */ 273275970Scy u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 274275970Scy 275275970Scy int weight ; /* WFQ queue weight */ 276285612Sdelphij int qsize ; /* queue size in slots or bytes */ 277285612Sdelphij int plr ; /* pkt loss rate (2^31-1 means 100%) */ 278285612Sdelphij 279285612Sdelphij struct ipfw_flow_id flow_mask ; 280285612Sdelphij 281285612Sdelphij /* hash table of queues onto this flow_set */ 282285612Sdelphij int rq_size ; /* number of slots */ 283285612Sdelphij int rq_elements ; /* active elements */ 284285612Sdelphij struct dn_flow_queue **rq; /* array of rq_size entries */ 285285612Sdelphij 286285612Sdelphij u_int32_t last_expired ; /* do not expire too frequently */ 287285612Sdelphij int backlogged ; /* #active queues for this flowset */ 288285612Sdelphij 289285612Sdelphij /* RED parameters */ 290285612Sdelphij#define SCALE_RED 16 291285612Sdelphij#define SCALE(x) ( (x) << SCALE_RED ) 292285612Sdelphij#define SCALE_VAL(x) ( (x) >> SCALE_RED ) 293285612Sdelphij#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 294285612Sdelphij int w_q ; /* queue weight (scaled) */ 295285612Sdelphij int max_th ; /* maximum threshold for queue (scaled) */ 296285612Sdelphij int min_th ; /* minimum threshold for queue (scaled) */ 297285612Sdelphij int max_p ; /* maximum value for p_b (scaled) */ 298285612Sdelphij u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 299285612Sdelphij u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 300285612Sdelphij u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 301285612Sdelphij u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 302285612Sdelphij u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 303285612Sdelphij u_int lookup_depth ; /* depth of lookup table */ 304275970Scy int lookup_step ; /* granularity inside the lookup table */ 305275970Scy int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 306275970Scy int avg_pkt_size ; /* medium packet size */ 307275970Scy int max_pkt_size ; /* max packet size */ 308275970Scy} ; 309275970Scy 310275970Scy/* 311275970Scy * Pipe descriptor. Contains global parameters, delay-line queue, 312275970Scy * and the flow_set used for fixed-rate queues. 313275970Scy * 314275970Scy * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 315275970Scy * not_eligible_heap, for queues whose start time is higher 316275970Scy * than the virtual time. Sorted by start time. 317275970Scy * scheduler_heap, for queues eligible for scheduling. Sorted by 318275970Scy * finish time. 319275970Scy * idle_heap, all flows that are idle and can be removed. We 320275970Scy * do that on each tick so we do not slow down too much 321275970Scy * operations during forwarding. 322275970Scy * 323275970Scy */ 324275970Scystruct dn_pipe { /* a pipe */ 325275970Scy struct dn_pipe *next ; 326275970Scy 327275970Scy int pipe_nr ; /* number */ 328275970Scy int bandwidth; /* really, bytes/tick. */ 329275970Scy int delay ; /* really, ticks */ 330275970Scy 331275970Scy struct dn_pkt *head, *tail ; /* packets in delay line */ 332275970Scy 333275970Scy /* WF2Q+ */ 334275970Scy struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ 335275970Scy struct dn_heap not_eligible_heap; /* top extract- key Start time */ 336275970Scy struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ 337275970Scy 338275970Scy dn_key V ; /* virtual time */ 339275970Scy int sum; /* sum of weights of all active sessions */ 340275970Scy int numbytes; /* bits I can transmit (more or less). */ 341275970Scy 342275970Scy dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 343275970Scy 344275970Scy /* 345275970Scy * When the tx clock come from an interface (if_name[0] != '\0'), its name 346275970Scy * is stored below, whereas the ifp is filled when the rule is configured. 347275970Scy */ 348275970Scy char if_name[IFNAMSIZ]; 349275970Scy struct ifnet *ifp ; 350275970Scy int ready ; /* set if ifp != NULL and we got a signal from it */ 351275970Scy 352275970Scy struct dn_flow_set fs ; /* used with fixed-rate flows */ 353275970Scy}; 354285612Sdelphij 355275970Scy#ifdef _KERNEL 356275970Scytypedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ 357275970Scytypedef void ip_dn_ruledel_t(void *); /* ip_fw.c */ 358275970Scytypedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir, 359 struct ip_fw_args *fwa); 360extern ip_dn_ctl_t *ip_dn_ctl_ptr; 361extern ip_dn_ruledel_t *ip_dn_ruledel_ptr; 362extern ip_dn_io_t *ip_dn_io_ptr; 363#define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) 364#endif 365 366#endif /* _IP_DUMMYNET_H */ 367