ip_dummynet.h revision 107900
1184588Sdfr/* 2184588Sdfr * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa 3184588Sdfr * Portions Copyright (c) 2000 Akamba Corp. 4184588Sdfr * All rights reserved 5184588Sdfr * 6184588Sdfr * Redistribution and use in source and binary forms, with or without 7184588Sdfr * modification, are permitted provided that the following conditions 8184588Sdfr * are met: 9184588Sdfr * 1. Redistributions of source code must retain the above copyright 10184588Sdfr * notice, this list of conditions and the following disclaimer. 11184588Sdfr * 2. Redistributions in binary form must reproduce the above copyright 12184588Sdfr * notice, this list of conditions and the following disclaimer in the 13184588Sdfr * documentation and/or other materials provided with the distribution. 14184588Sdfr * 15184588Sdfr * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16184588Sdfr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17184588Sdfr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18184588Sdfr * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19184588Sdfr * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20184588Sdfr * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21184588Sdfr * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22184588Sdfr * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23184588Sdfr * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24184588Sdfr * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25184588Sdfr * SUCH DAMAGE. 26184588Sdfr * 27184588Sdfr * $FreeBSD: head/sys/netinet/ip_dummynet.h 107900 2002-12-15 10:24:36Z maxim $ 28184588Sdfr */ 29184588Sdfr 30184588Sdfr#ifndef _IP_DUMMYNET_H 31184588Sdfr#define _IP_DUMMYNET_H 32184588Sdfr 33184588Sdfr/* 34184588Sdfr * Definition of dummynet data structures. In the structures, I decided 35184588Sdfr * not to use the macros in <sys/queue.h> in the hope of making the code 36184588Sdfr * easier to port to other architectures. The type of lists and queue we 37184588Sdfr * use here is pretty simple anyways. 38184588Sdfr */ 39184588Sdfr 40184588Sdfr/* 41184588Sdfr * We start with a heap, which is used in the scheduler to decide when 42184588Sdfr * to transmit packets etc. 43184588Sdfr * 44184588Sdfr * The key for the heap is used for two different values: 45184588Sdfr * 46184588Sdfr * 1. timer ticks- max 10K/second, so 32 bits are enough; 47184588Sdfr * 48184588Sdfr * 2. virtual times. These increase in steps of len/x, where len is the 49184588Sdfr * packet length, and x is either the weight of the flow, or the 50184588Sdfr * sum of all weights. 51184588Sdfr * If we limit to max 1000 flows and a max weight of 100, then 52184588Sdfr * x needs 17 bits. The packet size is 16 bits, so we can easily 53184588Sdfr * overflow if we do not allow errors. 54184588Sdfr * So we use a key "dn_key" which is 64 bits. Some macros are used to 55184588Sdfr * compare key values and handle wraparounds. 56184588Sdfr * MAX64 returns the largest of two key values. 57184588Sdfr * MY_M is used as a shift count when doing fixed point arithmetic 58184588Sdfr * (a better name would be useful...). 59184588Sdfr */ 60184588Sdfrtypedef u_int64_t dn_key ; /* sorting key */ 61184588Sdfr#define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 62184588Sdfr#define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 63184588Sdfr#define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) 64184588Sdfr#define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) 65184588Sdfr#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) 66184588Sdfr#define MY_M 16 /* number of left shift to obtain a larger precision */ 67184588Sdfr 68184588Sdfr/* 69184588Sdfr * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 70184588Sdfr * virtual time wraps every 15 days. 71184588Sdfr */ 72184588Sdfr 73184588Sdfr/* 74184588Sdfr * The OFFSET_OF macro is used to return the offset of a field within 75184588Sdfr * a structure. It is used by the heap management routines. 76184588Sdfr */ 77184588Sdfr#define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) 78184588Sdfr 79184588Sdfr/* 80184588Sdfr * The maximum hash table size for queues. This value must be a power 81184588Sdfr * of 2. 82184588Sdfr */ 83184588Sdfr#define DN_MAX_HASH_SIZE 65536 84184588Sdfr 85184588Sdfr/* 86184588Sdfr * A heap entry is made of a key and a pointer to the actual 87184588Sdfr * object stored in the heap. 88184588Sdfr * The heap is an array of dn_heap_entry entries, dynamically allocated. 89184588Sdfr * Current size is "size", with "elements" actually in use. 90184588Sdfr * The heap normally supports only ordered insert and extract from the top. 91184588Sdfr * If we want to extract an object from the middle of the heap, we 92184588Sdfr * have to know where the object itself is located in the heap (or we 93184588Sdfr * need to scan the whole array). To this purpose, an object has a 94184588Sdfr * field (int) which contains the index of the object itself into the 95184588Sdfr * heap. When the object is moved, the field must also be updated. 96184588Sdfr * The offset of the index in the object is stored in the 'offset' 97184588Sdfr * field in the heap descriptor. The assumption is that this offset 98184588Sdfr * is non-zero if we want to support extract from the middle. 99184588Sdfr */ 100184588Sdfrstruct dn_heap_entry { 101184588Sdfr dn_key key ; /* sorting key. Topmost element is smallest one */ 102184588Sdfr void *object ; /* object pointer */ 103184588Sdfr} ; 104184588Sdfr 105184588Sdfrstruct dn_heap { 106184588Sdfr int size ; 107184588Sdfr int elements ; 108184588Sdfr int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 109184588Sdfr struct dn_heap_entry *p ; /* really an array of "size" entries */ 110184588Sdfr} ; 111184588Sdfr 112184588Sdfr/* 113184588Sdfr * struct dn_pkt identifies a packet in the dummynet queue, but 114184588Sdfr * is also used to tag packets passed back to the various destinations 115184588Sdfr * (ip_input(), ip_output(), bdg_forward() and so on). 116184588Sdfr * As such the first part of the structure must be a struct m_hdr, 117184588Sdfr * followed by dummynet-specific parameters. The m_hdr must be 118184588Sdfr * initialized with 119184588Sdfr * mh_type = MT_TAG; 120184588Sdfr * mh_flags = PACKET_TYPE_DUMMYNET; 121184588Sdfr * mh_next = <pointer to the actual mbuf> 122184588Sdfr * 123184588Sdfr * mh_nextpkt, mh_data are free for dummynet use (mh_nextpkt is used to 124184588Sdfr * build a linked list of packets in a dummynet queue). 125184588Sdfr */ 126184588Sdfrstruct dn_pkt { 127184588Sdfr struct m_hdr hdr ; 128184588Sdfr#define DN_NEXT(x) (struct dn_pkt *)(x)->hdr.mh_nextpkt 129184588Sdfr#define dn_m hdr.mh_next /* packet to be forwarded */ 130184588Sdfr 131184588Sdfr struct ip_fw *rule; /* matching rule */ 132184588Sdfr int dn_dir; /* action when packet comes out. */ 133184588Sdfr#define DN_TO_IP_OUT 1 134184588Sdfr#define DN_TO_IP_IN 2 135184588Sdfr#define DN_TO_BDG_FWD 3 136184588Sdfr#define DN_TO_ETH_DEMUX 4 137184588Sdfr#define DN_TO_ETH_OUT 5 138184588Sdfr 139184588Sdfr dn_key output_time; /* when the pkt is due for delivery */ 140184588Sdfr struct ifnet *ifp; /* interface, for ip_output */ 141184588Sdfr struct sockaddr_in *dn_dst ; 142184588Sdfr struct route ro; /* route, for ip_output. MUST COPY */ 143184588Sdfr int flags ; /* flags, for ip_output (IPv6 ?) */ 144184588Sdfr}; 145184588Sdfr 146184588Sdfr/* 147184588Sdfr * Overall structure of dummynet (with WF2Q+): 148184588Sdfr 149184588SdfrIn dummynet, packets are selected with the firewall rules, and passed 150184588Sdfrto two different objects: PIPE or QUEUE. 151184588Sdfr 152184588SdfrA QUEUE is just a queue with configurable size and queue management 153184588Sdfrpolicy. It is also associated with a mask (to discriminate among 154184588Sdfrdifferent flows), a weight (used to give different shares of the 155184588Sdfrbandwidth to different flows) and a "pipe", which essentially 156184588Sdfrsupplies the transmit clock for all queues associated with that 157184588Sdfrpipe. 158184588Sdfr 159184588SdfrA PIPE emulates a fixed-bandwidth link, whose bandwidth is 160184588Sdfrconfigurable. The "clock" for a pipe can come from either an 161184588Sdfrinternal timer, or from the transmit interrupt of an interface. 162184588SdfrA pipe is also associated with one (or more, if masks are used) 163184588Sdfrqueue, where all packets for that pipe are stored. 164184588Sdfr 165184588SdfrThe bandwidth available on the pipe is shared by the queues 166184588Sdfrassociated with that pipe (only one in case the packet is sent 167184588Sdfrto a PIPE) according to the WF2Q+ scheduling algorithm and the 168184588Sdfrconfigured weights. 169184588Sdfr 170184588SdfrIn general, incoming packets are stored in the appropriate queue, 171184588Sdfrwhich is then placed into one of a few heaps managed by a scheduler 172184588Sdfrto decide when the packet should be extracted. 173184588SdfrThe scheduler (a function called dummynet()) is run at every timer 174184588Sdfrtick, and grabs queues from the head of the heaps when they are 175184588Sdfrready for processing. 176184588Sdfr 177184588SdfrThere are three data structures definining a pipe and associated queues: 178184588Sdfr 179184588Sdfr + dn_pipe, which contains the main configuration parameters related 180184588Sdfr to delay and bandwidth; 181184588Sdfr + dn_flow_set, which contains WF2Q+ configuration, flow 182184588Sdfr masks, plr and RED configuration; 183184588Sdfr + dn_flow_queue, which is the per-flow queue (containing the packets) 184184588Sdfr 185184588SdfrMultiple dn_flow_set can be linked to the same pipe, and multiple 186184588Sdfrdn_flow_queue can be linked to the same dn_flow_set. 187184588SdfrAll data structures are linked in a linear list which is used for 188184588Sdfrhousekeeping purposes. 189184588Sdfr 190184588SdfrDuring configuration, we create and initialize the dn_flow_set 191184588Sdfrand dn_pipe structures (a dn_pipe also contains a dn_flow_set). 192184588Sdfr 193184588SdfrAt runtime: packets are sent to the appropriate dn_flow_set (either 194184588SdfrWFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 195184588Sdfrwhich in turn dispatches them to the appropriate dn_flow_queue 196184588Sdfr(created dynamically according to the masks). 197184588Sdfr 198184588SdfrThe transmit clock for fixed rate flows (ready_event()) selects the 199184588Sdfrdn_flow_queue to be used to transmit the next packet. For WF2Q, 200184588Sdfrwfq_ready_event() extract a pipe which in turn selects the right 201184588Sdfrflow using a number of heaps defined into the pipe itself. 202184588Sdfr 203184588Sdfr * 204184588Sdfr */ 205184588Sdfr 206184588Sdfr/* 207184588Sdfr * per flow queue. This contains the flow identifier, the queue 208184588Sdfr * of packets, counters, and parameters used to support both RED and 209184588Sdfr * WF2Q+. 210184588Sdfr * 211184588Sdfr * A dn_flow_queue is created and initialized whenever a packet for 212184588Sdfr * a new flow arrives. 213184588Sdfr */ 214184588Sdfrstruct dn_flow_queue { 215184588Sdfr struct dn_flow_queue *next ; 216184588Sdfr struct ipfw_flow_id id ; 217184588Sdfr 218184588Sdfr struct dn_pkt *head, *tail ; /* queue of packets */ 219184588Sdfr u_int len ; 220184588Sdfr u_int len_bytes ; 221184588Sdfr long numbytes ; /* credit for transmission (dynamic queues) */ 222184588Sdfr 223184588Sdfr u_int64_t tot_pkts ; /* statistics counters */ 224184588Sdfr u_int64_t tot_bytes ; 225184588Sdfr u_int32_t drops ; 226184588Sdfr 227184588Sdfr int hash_slot ; /* debugging/diagnostic */ 228184588Sdfr 229184588Sdfr /* RED parameters */ 230184588Sdfr int avg ; /* average queue length est. (scaled) */ 231184588Sdfr int count ; /* arrivals since last RED drop */ 232184588Sdfr int random ; /* random value (scaled) */ 233184588Sdfr u_int32_t q_time ; /* start of queue idle time */ 234184588Sdfr 235184588Sdfr /* WF2Q+ support */ 236184588Sdfr struct dn_flow_set *fs ; /* parent flow set */ 237184588Sdfr int heap_pos ; /* position (index) of struct in heap */ 238184588Sdfr dn_key sched_time ; /* current time when queue enters ready_heap */ 239184588Sdfr 240184588Sdfr dn_key S,F ; /* start time, finish time */ 241184588Sdfr /* 242184588Sdfr * Setting F < S means the timestamp is invalid. We only need 243184588Sdfr * to test this when the queue is empty. 244184588Sdfr */ 245184588Sdfr} ; 246184588Sdfr 247184588Sdfr/* 248184588Sdfr * flow_set descriptor. Contains the "template" parameters for the 249184588Sdfr * queue configuration, and pointers to the hash table of dn_flow_queue's. 250184588Sdfr * 251184588Sdfr * The hash table is an array of lists -- we identify the slot by 252184588Sdfr * hashing the flow-id, then scan the list looking for a match. 253184588Sdfr * The size of the hash table (buckets) is configurable on a per-queue 254184588Sdfr * basis. 255184588Sdfr * 256184588Sdfr * A dn_flow_set is created whenever a new queue or pipe is created (in the 257184588Sdfr * latter case, the structure is located inside the struct dn_pipe). 258184588Sdfr */ 259184588Sdfrstruct dn_flow_set { 260184588Sdfr struct dn_flow_set *next; /* next flow set in all_flow_sets list */ 261184588Sdfr 262184588Sdfr u_short fs_nr ; /* flow_set number */ 263184588Sdfr u_short flags_fs; 264184588Sdfr#define DN_HAVE_FLOW_MASK 0x0001 265184588Sdfr#define DN_IS_RED 0x0002 266184588Sdfr#define DN_IS_GENTLE_RED 0x0004 267#define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 268#define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 269#define DN_IS_PIPE 0x4000 270#define DN_IS_QUEUE 0x8000 271 272 struct dn_pipe *pipe ; /* pointer to parent pipe */ 273 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 274 275 int weight ; /* WFQ queue weight */ 276 int qsize ; /* queue size in slots or bytes */ 277 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 278 279 struct ipfw_flow_id flow_mask ; 280 281 /* hash table of queues onto this flow_set */ 282 int rq_size ; /* number of slots */ 283 int rq_elements ; /* active elements */ 284 struct dn_flow_queue **rq; /* array of rq_size entries */ 285 286 u_int32_t last_expired ; /* do not expire too frequently */ 287 int backlogged ; /* #active queues for this flowset */ 288 289 /* RED parameters */ 290#define SCALE_RED 16 291#define SCALE(x) ( (x) << SCALE_RED ) 292#define SCALE_VAL(x) ( (x) >> SCALE_RED ) 293#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 294 int w_q ; /* queue weight (scaled) */ 295 int max_th ; /* maximum threshold for queue (scaled) */ 296 int min_th ; /* minimum threshold for queue (scaled) */ 297 int max_p ; /* maximum value for p_b (scaled) */ 298 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 299 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 300 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 301 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 302 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 303 u_int lookup_depth ; /* depth of lookup table */ 304 int lookup_step ; /* granularity inside the lookup table */ 305 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 306 int avg_pkt_size ; /* medium packet size */ 307 int max_pkt_size ; /* max packet size */ 308} ; 309 310/* 311 * Pipe descriptor. Contains global parameters, delay-line queue, 312 * and the flow_set used for fixed-rate queues. 313 * 314 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 315 * not_eligible_heap, for queues whose start time is higher 316 * than the virtual time. Sorted by start time. 317 * scheduler_heap, for queues eligible for scheduling. Sorted by 318 * finish time. 319 * idle_heap, all flows that are idle and can be removed. We 320 * do that on each tick so we do not slow down too much 321 * operations during forwarding. 322 * 323 */ 324struct dn_pipe { /* a pipe */ 325 struct dn_pipe *next ; 326 327 int pipe_nr ; /* number */ 328 int bandwidth; /* really, bytes/tick. */ 329 int delay ; /* really, ticks */ 330 331 struct dn_pkt *head, *tail ; /* packets in delay line */ 332 333 /* WF2Q+ */ 334 struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ 335 struct dn_heap not_eligible_heap; /* top extract- key Start time */ 336 struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ 337 338 dn_key V ; /* virtual time */ 339 int sum; /* sum of weights of all active sessions */ 340 int numbytes; /* bits I can transmit (more or less). */ 341 342 dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 343 344 /* 345 * When the tx clock come from an interface (if_name[0] != '\0'), its name 346 * is stored below, whereas the ifp is filled when the rule is configured. 347 */ 348 char if_name[IFNAMSIZ]; 349 struct ifnet *ifp ; 350 int ready ; /* set if ifp != NULL and we got a signal from it */ 351 352 struct dn_flow_set fs ; /* used with fixed-rate flows */ 353}; 354 355#ifdef _KERNEL 356typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ 357typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */ 358typedef 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