1 /* 2 * Copyright (c) 1998-2000 Luigi Rizzo, Universita` di Pisa 3 * Portions Copyright (c) 2000 Akamba Corp. 4 * All rights reserved 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * $FreeBSD$ 28 */ 29 30 #ifndef _IP_DUMMYNET_H 31 #define _IP_DUMMYNET_H 32 33 /* 34 * Definition of dummynet data structures. In the structures, I decided 35 * not to use the macros in <sys/queue.h> in the hope of making the code 36 * easier to port to other architectures. The type of lists and queue we 37 * use here is pretty simple anyways. 38 */ 39 40 /* 41 * We start with a heap, which is used in the scheduler to decide when 42 * to transmit packets etc. 43 * 44 * The key for the heap is used for two different values: 45 * 46 * 1. timer ticks- max 10K/second, so 32 bits are enough; 47 * 48 * 2. virtual times. These increase in steps of len/x, where len is the 49 * packet length, and x is either the weight of the flow, or the 50 * sum of all weights. 51 * If we limit to max 1000 flows and a max weight of 100, then 52 * x needs 17 bits. The packet size is 16 bits, so we can easily 53 * overflow if we do not allow errors. 54 * So we use a key "dn_key" which is 64 bits. Some macros are used to 55 * compare key values and handle wraparounds. 56 * MAX64 returns the largest of two key values. 57 * MY_M is used as a shift count when doing fixed point arithmetic 58 * (a better name would be useful...). 59 */ 60 typedef u_int64_t dn_key ; /* sorting key */ 61 #define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 62 #define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 63 #define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) 64 #define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) 65 #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) 66 #define MY_M 16 /* number of left shift to obtain a larger precision */ 67 68 /* 69 * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 70 * virtual time wraps every 15 days. 71 */ 72 73 /* 74 * The OFFSET_OF macro is used to return the offset of a field within 75 * a structure. It is used by the heap management routines. 76 */ 77 #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) 78 79 /* 80 * A heap entry is made of a key and a pointer to the actual 81 * object stored in the heap. 82 * The heap is an array of dn_heap_entry entries, dynamically allocated. 83 * Current size is "size", with "elements" actually in use. 84 * The heap normally supports only ordered insert and extract from the top. 85 * If we want to extract an object from the middle of the heap, we 86 * have to know where the object itself is located in the heap (or we 87 * need to scan the whole array). To this purpose, an object has a 88 * field (int) which contains the index of the object itself into the 89 * heap. When the object is moved, the field must also be updated. 90 * The offset of the index in the object is stored in the 'offset' 91 * field in the heap descriptor. The assumption is that this offset 92 * is non-zero if we want to support extract from the middle. 93 */ 94 struct dn_heap_entry { 95 dn_key key ; /* sorting key. Topmost element is smallest one */ 96 void *object ; /* object pointer */ 97 } ; 98 99 struct dn_heap { 100 int size ; 101 int elements ; 102 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 103 struct dn_heap_entry *p ; /* really an array of "size" entries */ 104 } ; 105 106 /* 107 * MT_DUMMYNET is a new (fake) mbuf type that is prepended to the 108 * packet when it comes out of a pipe. The definition 109 * ought to go in /sys/sys/mbuf.h but here it is less intrusive. 110 */ 111 112 #define MT_DUMMYNET MT_CONTROL 113 114 /* 115 * struct dn_pkt identifies a packet in the dummynet queue. The 116 * first part is really an m_hdr for implementation purposes, and some 117 * fields are saved there. When passing the packet back to the ip_input/ 118 * ip_output()/bdg_forward, the struct is prepended to the mbuf chain with type 119 * MT_DUMMYNET, and contains the pointer to the matching rule. 120 * 121 * Note: there is no real need to make this structure contain an m_hdr, 122 * in the future this should be changed to a normal data structure. 123 */ 124 struct dn_pkt { 125 struct m_hdr hdr ; 126 #define dn_next hdr.mh_nextpkt /* next element in queue */ 127 #define DN_NEXT(x) (struct dn_pkt *)(x)->dn_next 128 #define dn_m hdr.mh_next /* packet to be forwarded */ 129 #define dn_dir hdr.mh_flags /* action when pkt extracted from a queue */ 130 #define DN_TO_IP_OUT 1 131 #define DN_TO_IP_IN 2 132 #define DN_TO_BDG_FWD 3 133 134 dn_key output_time; /* when the pkt is due for delivery */ 135 struct ifnet *ifp; /* interface, for ip_output */ 136 struct sockaddr_in *dn_dst ; 137 struct route ro; /* route, for ip_output. MUST COPY */ 138 int flags ; /* flags, for ip_output (IPv6 ?) */ 139 }; 140 141 /* 142 * Overall structure of dummynet (with WF2Q+): 143 144 In dummynet, packets are selected with the firewall rules, and passed 145 to two different objects: PIPE or QUEUE. 146 147 A QUEUE is just a queue with configurable size and queue management 148 policy. It is also associated with a mask (to discriminate among 149 different flows), a weight (used to give different shares of the 150 bandwidth to different flows) and a "pipe", which essentially 151 supplies the transmit clock for all queues associated with that 152 pipe. 153 154 A PIPE emulates a fixed-bandwidth link, whose bandwidth is 155 configurable. The "clock" for a pipe can come from either an 156 internal timer, or from the transmit interrupt of an interface. 157 A pipe is also associated with one (or more, if masks are used) 158 queue, where all packets for that pipe are stored. 159 160 The bandwidth available on the pipe is shared by the queues 161 associated with that pipe (only one in case the packet is sent 162 to a PIPE) according to the WF2Q+ scheduling algorithm and the 163 configured weights. 164 165 In general, incoming packets are stored in the appropriate queue, 166 which is then placed into one of a few heaps managed by a scheduler 167 to decide when the packet should be extracted. 168 The scheduler (a function called dummynet()) is run at every timer 169 tick, and grabs queues from the head of the heaps when they are 170 ready for processing. 171 172 There are three data structures definining a pipe and associated queues: 173 174 + dn_pipe, which contains the main configuration parameters related 175 to delay and bandwidth; 176 + dn_flow_set, which contains WF2Q+ configuration, flow 177 masks, plr and RED configuration; 178 + dn_flow_queue, which is the per-flow queue (containing the packets) 179 180 Multiple dn_flow_set can be linked to the same pipe, and multiple 181 dn_flow_queue can be linked to the same dn_flow_set. 182 All data structures are linked in a linear list which is used for 183 housekeeping purposes. 184 185 During configuration, we create and initialize the dn_flow_set 186 and dn_pipe structures (a dn_pipe also contains a dn_flow_set). 187 188 At runtime: packets are sent to the appropriate dn_flow_set (either 189 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 190 which in turn dispatches them to the appropriate dn_flow_queue 191 (created dynamically according to the masks). 192 193 The transmit clock for fixed rate flows (ready_event()) selects the 194 dn_flow_queue to be used to transmit the next packet. For WF2Q, 195 wfq_ready_event() extract a pipe which in turn selects the right 196 flow using a number of heaps defined into the pipe itself. 197 198 * 199 */ 200 201 /* 202 * per flow queue. This contains the flow identifier, the queue 203 * of packets, counters, and parameters used to support both RED and 204 * WF2Q+. 205 */ 206 struct dn_flow_queue { 207 struct dn_flow_queue *next ; 208 struct ipfw_flow_id id ; 209 struct dn_pkt *head, *tail ; /* queue of packets */ 210 u_int len ; 211 u_int len_bytes ; 212 long numbytes ; /* credit for transmission (dynamic queues) */ 213 214 u_int64_t tot_pkts ; /* statistics counters */ 215 u_int64_t tot_bytes ; 216 u_int32_t drops ; 217 int hash_slot ; /* debugging/diagnostic */ 218 219 /* RED parameters */ 220 int avg ; /* average queue length est. (scaled) */ 221 int count ; /* arrivals since last RED drop */ 222 int random ; /* random value (scaled) */ 223 u_int32_t q_time ; /* start of queue idle time */ 224 225 /* WF2Q+ support */ 226 struct dn_flow_set *fs ; /* parent flow set */ 227 int heap_pos ; /* position (index) of struct in heap */ 228 dn_key sched_time ; /* current time when queue enters ready_heap */ 229 230 dn_key S,F ; /* start-time, finishing time */ 231 /* setting F < S means the timestamp is invalid. We only need 232 * to test this when the queue is empty. 233 */ 234 } ; 235 236 /* 237 * flow_set descriptor. Contains the "template" parameters for the 238 * queue configuration, and pointers to the hash table of dn_flow_queue's. 239 * 240 * The hash table is an array of lists -- we identify the slot by 241 * hashing the flow-id, then scan the list looking for a match. 242 * The size of the hash table (buckets) is configurable on a per-queue 243 * basis. 244 */ 245 struct dn_flow_set { 246 struct dn_flow_set *next; /* next flow set in all_flow_sets list */ 247 248 u_short fs_nr ; /* flow_set number */ 249 u_short flags_fs; 250 #define DN_HAVE_FLOW_MASK 0x0001 251 #define DN_IS_PIPE 0x4000 252 #define DN_IS_QUEUE 0x8000 253 #define DN_IS_RED 0x0002 254 #define DN_IS_GENTLE_RED 0x0004 255 #define DN_QSIZE_IS_BYTES 0x0008 /* queue measured in bytes */ 256 257 struct dn_pipe *pipe ; /* pointer to parent pipe */ 258 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 259 260 int weight ; /* WFQ queue weight */ 261 int qsize ; /* queue size in slots or bytes */ 262 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 263 264 struct ipfw_flow_id flow_mask ; 265 /* hash table of queues onto this flow_set */ 266 int rq_size ; /* number of slots */ 267 int rq_elements ; /* active elements */ 268 struct dn_flow_queue **rq; /* array of rq_size entries */ 269 u_int32_t last_expired ; /* do not expire too frequently */ 270 /* XXX some RED parameters as well ? */ 271 int backlogged ; /* #active queues for this flowset */ 272 273 /* RED parameters */ 274 #define SCALE_RED 16 275 #define SCALE(x) ( (x) << SCALE_RED ) 276 #define SCALE_VAL(x) ( (x) >> SCALE_RED ) 277 #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 278 int w_q ; /* queue weight (scaled) */ 279 int max_th ; /* maximum threshold for queue (scaled) */ 280 int min_th ; /* minimum threshold for queue (scaled) */ 281 int max_p ; /* maximum value for p_b (scaled) */ 282 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 283 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 284 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 285 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 286 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 287 u_int lookup_depth ; /* depth of lookup table */ 288 int lookup_step ; /* granularity inside the lookup table */ 289 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 290 int avg_pkt_size ; /* medium packet size */ 291 int max_pkt_size ; /* max packet size */ 292 } ; 293 294 /* 295 * Pipe descriptor. Contains global parameters, delay-line queue, 296 * and the flow_set used for fixed-rate queues. 297 * 298 * For WF2Q support it also has 4 heaps holding dn_flow_queue: 299 * not_eligible_heap, for queues whose start time is higher 300 * than the virtual time. Sorted by start time. 301 * scheduler_heap, for queues eligible for scheduling. Sorted by 302 * finish time. 303 * backlogged_heap, all flows in the two heaps above, sorted by 304 * start time. This is used to compute the virtual time. 305 * idle_heap, all flows that are idle and can be removed. We 306 * do that on each tick so we do not slow down too much 307 * operations during forwarding. 308 * 309 */ 310 struct dn_pipe { /* a pipe */ 311 struct dn_pipe *next ; 312 313 int pipe_nr ; /* number */ 314 int bandwidth; /* really, bytes/tick. */ 315 int delay ; /* really, ticks */ 316 317 struct dn_pkt *head, *tail ; /* packets in delay line */ 318 319 /* WF2Q+ */ 320 struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ 321 struct dn_heap not_eligible_heap; /* top extract- key Start time */ 322 struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ 323 324 dn_key V ; /* virtual time */ 325 int sum; /* sum of weights of all active sessions */ 326 int numbytes; /* bit i can transmit (more or less). */ 327 328 dn_key sched_time ; /* first time pipe is scheduled in ready_heap */ 329 330 /* the tx clock can come from an interface. In this case, the 331 * name is below, and the pointer is filled when the rule is 332 * configured. We identify this by setting the if_name to a 333 * non-empty string. 334 */ 335 char if_name[16]; 336 struct ifnet *ifp ; 337 int ready ; /* set if ifp != NULL and we got a signal from it */ 338 339 struct dn_flow_set fs ; /* used with fixed-rate flows */ 340 }; 341 342 #ifdef _KERNEL 343 344 MALLOC_DECLARE(M_IPFW); 345 346 typedef int ip_dn_ctl_t __P((struct sockopt *)) ; 347 extern ip_dn_ctl_t *ip_dn_ctl_ptr; 348 349 void dn_rule_delete(void *r); /* used in ip_fw.c */ 350 int dummynet_io(int pipe, int dir, 351 struct mbuf *m, struct ifnet *ifp, struct route *ro, 352 struct sockaddr_in * dst, 353 struct ip_fw_chain *rule, int flags); 354 #endif 355 356 #endif /* _IP_DUMMYNET_H */ 357