1 /*- 2 * Copyright (c) 1998-2002 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 /* 75 * The maximum hash table size for queues. This value must be a power 76 * of 2. 77 */ 78 #define DN_MAX_HASH_SIZE 65536 79 80 /* 81 * A heap entry is made of a key and a pointer to the actual 82 * object stored in the heap. 83 * The heap is an array of dn_heap_entry entries, dynamically allocated. 84 * Current size is "size", with "elements" actually in use. 85 * The heap normally supports only ordered insert and extract from the top. 86 * If we want to extract an object from the middle of the heap, we 87 * have to know where the object itself is located in the heap (or we 88 * need to scan the whole array). To this purpose, an object has a 89 * field (int) which contains the index of the object itself into the 90 * heap. When the object is moved, the field must also be updated. 91 * The offset of the index in the object is stored in the 'offset' 92 * field in the heap descriptor. The assumption is that this offset 93 * is non-zero if we want to support extract from the middle. 94 */ 95 struct dn_heap_entry { 96 dn_key key ; /* sorting key. Topmost element is smallest one */ 97 void *object ; /* object pointer */ 98 } ; 99 100 struct dn_heap { 101 int size ; 102 int elements ; 103 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 104 struct dn_heap_entry *p ; /* really an array of "size" entries */ 105 } ; 106 107 #ifdef _KERNEL 108 /* 109 * Packets processed by dummynet have an mbuf tag associated with 110 * them that carries their dummynet state. This is used within 111 * the dummynet code as well as outside when checking for special 112 * processing requirements. 113 * Note that the first part is the reinject info and is common to 114 * other forms of packet reinjection. 115 */ 116 struct dn_pkt_tag { 117 /* first part, reinject info */ 118 uint32_t slot; /* slot of next rule to use */ 119 uint32_t rulenum; /* matching rule number */ 120 uint32_t rule_id; /* matching rule id */ 121 uint32_t chain_id; /* ruleset id */ 122 123 /* second part, dummynet specific */ 124 int dn_dir; /* action when packet comes out. */ 125 /* see ip_fw_private.h */ 126 127 dn_key output_time; /* when the pkt is due for delivery */ 128 struct ifnet *ifp; /* interface, for ip_output */ 129 struct _ip6dn_args ip6opt; /* XXX ipv6 options */ 130 }; 131 #endif /* _KERNEL */ 132 133 /* 134 * Overall structure of dummynet (with WF2Q+): 135 136 In dummynet, packets are selected with the firewall rules, and passed 137 to two different objects: PIPE or QUEUE. 138 139 A QUEUE is just a queue with configurable size and queue management 140 policy. It is also associated with a mask (to discriminate among 141 different flows), a weight (used to give different shares of the 142 bandwidth to different flows) and a "pipe", which essentially 143 supplies the transmit clock for all queues associated with that 144 pipe. 145 146 A PIPE emulates a fixed-bandwidth link, whose bandwidth is 147 configurable. The "clock" for a pipe can come from either an 148 internal timer, or from the transmit interrupt of an interface. 149 A pipe is also associated with one (or more, if masks are used) 150 queue, where all packets for that pipe are stored. 151 152 The bandwidth available on the pipe is shared by the queues 153 associated with that pipe (only one in case the packet is sent 154 to a PIPE) according to the WF2Q+ scheduling algorithm and the 155 configured weights. 156 157 In general, incoming packets are stored in the appropriate queue, 158 which is then placed into one of a few heaps managed by a scheduler 159 to decide when the packet should be extracted. 160 The scheduler (a function called dummynet()) is run at every timer 161 tick, and grabs queues from the head of the heaps when they are 162 ready for processing. 163 164 There are three data structures definining a pipe and associated queues: 165 166 + dn_pipe, which contains the main configuration parameters related 167 to delay and bandwidth; 168 + dn_flow_set, which contains WF2Q+ configuration, flow 169 masks, plr and RED configuration; 170 + dn_flow_queue, which is the per-flow queue (containing the packets) 171 172 Multiple dn_flow_set can be linked to the same pipe, and multiple 173 dn_flow_queue can be linked to the same dn_flow_set. 174 All data structures are linked in a linear list which is used for 175 housekeeping purposes. 176 177 During configuration, we create and initialize the dn_flow_set 178 and dn_pipe structures (a dn_pipe also contains a dn_flow_set). 179 180 At runtime: packets are sent to the appropriate dn_flow_set (either 181 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 182 which in turn dispatches them to the appropriate dn_flow_queue 183 (created dynamically according to the masks). 184 185 The transmit clock for fixed rate flows (ready_event()) selects the 186 dn_flow_queue to be used to transmit the next packet. For WF2Q, 187 wfq_ready_event() extract a pipe which in turn selects the right 188 flow using a number of heaps defined into the pipe itself. 189 190 * 191 */ 192 193 /* 194 * per flow queue. This contains the flow identifier, the queue 195 * of packets, counters, and parameters used to support both RED and 196 * WF2Q+. 197 * 198 * A dn_flow_queue is created and initialized whenever a packet for 199 * a new flow arrives. 200 */ 201 struct dn_flow_queue { 202 struct dn_flow_queue *next ; 203 struct ipfw_flow_id id ; 204 205 struct mbuf *head, *tail ; /* queue of packets */ 206 u_int len ; 207 u_int len_bytes ; 208 209 /* 210 * When we emulate MAC overheads, or channel unavailability due 211 * to other traffic on a shared medium, we augment the packet at 212 * the head of the queue with an 'extra_bits' field representsing 213 * the additional delay the packet will be subject to: 214 * extra_bits = bw*unavailable_time. 215 * With large bandwidth and large delays, extra_bits (and also numbytes) 216 * can become very large, so better play safe and use 64 bit 217 */ 218 uint64_t numbytes ; /* credit for transmission (dynamic queues) */ 219 int64_t extra_bits; /* extra bits simulating unavailable channel */ 220 221 u_int64_t tot_pkts ; /* statistics counters */ 222 u_int64_t tot_bytes ; 223 u_int32_t drops ; 224 225 int hash_slot ; /* debugging/diagnostic */ 226 227 /* RED parameters */ 228 int avg ; /* average queue length est. (scaled) */ 229 int count ; /* arrivals since last RED drop */ 230 int random ; /* random value (scaled) */ 231 dn_key idle_time; /* start of queue idle time */ 232 233 /* WF2Q+ support */ 234 struct dn_flow_set *fs ; /* parent flow set */ 235 int heap_pos ; /* position (index) of struct in heap */ 236 dn_key sched_time ; /* current time when queue enters ready_heap */ 237 238 dn_key S,F ; /* start time, finish time */ 239 /* 240 * Setting F < S means the timestamp is invalid. We only need 241 * to test this when the queue is empty. 242 */ 243 } ; 244 245 /* 246 * flow_set descriptor. Contains the "template" parameters for the 247 * queue configuration, and pointers to the hash table of dn_flow_queue's. 248 * 249 * The hash table is an array of lists -- we identify the slot by 250 * hashing the flow-id, then scan the list looking for a match. 251 * The size of the hash table (buckets) is configurable on a per-queue 252 * basis. 253 * 254 * A dn_flow_set is created whenever a new queue or pipe is created (in the 255 * latter case, the structure is located inside the struct dn_pipe). 256 */ 257 struct dn_flow_set { 258 SLIST_ENTRY(dn_flow_set) next; /* linked list in a hash slot */ 259 260 u_short fs_nr ; /* flow_set number */ 261 u_short flags_fs; 262 #define DN_HAVE_FLOW_MASK 0x0001 263 #define DN_IS_RED 0x0002 264 #define DN_IS_GENTLE_RED 0x0004 265 #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 266 #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 267 #define DN_HAS_PROFILE 0x0020 /* the pipe has a delay profile. */ 268 #define DN_IS_PIPE 0x4000 269 #define DN_IS_QUEUE 0x8000 270 271 struct dn_pipe *pipe ; /* pointer to parent pipe */ 272 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 273 274 int weight ; /* WFQ queue weight */ 275 int qsize ; /* queue size in slots or bytes */ 276 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 277 278 struct ipfw_flow_id flow_mask ; 279 280 /* hash table of queues onto this flow_set */ 281 int rq_size ; /* number of slots */ 282 int rq_elements ; /* active elements */ 283 struct dn_flow_queue **rq; /* array of rq_size entries */ 284 285 u_int32_t last_expired ; /* do not expire too frequently */ 286 int backlogged ; /* #active queues for this flowset */ 287 288 /* RED parameters */ 289 #define SCALE_RED 16 290 #define SCALE(x) ( (x) << SCALE_RED ) 291 #define SCALE_VAL(x) ( (x) >> SCALE_RED ) 292 #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 293 int w_q ; /* queue weight (scaled) */ 294 int max_th ; /* maximum threshold for queue (scaled) */ 295 int min_th ; /* minimum threshold for queue (scaled) */ 296 int max_p ; /* maximum value for p_b (scaled) */ 297 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 298 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 299 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 300 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 301 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 302 u_int lookup_depth ; /* depth of lookup table */ 303 int lookup_step ; /* granularity inside the lookup table */ 304 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 305 int avg_pkt_size ; /* medium packet size */ 306 int max_pkt_size ; /* max packet size */ 307 }; 308 SLIST_HEAD(dn_flow_set_head, dn_flow_set); 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 */ 324 struct dn_pipe { /* a pipe */ 325 SLIST_ENTRY(dn_pipe) next; /* linked list in a hash slot */ 326 327 int pipe_nr ; /* number */ 328 int bandwidth; /* really, bytes/tick. */ 329 int delay ; /* really, ticks */ 330 331 struct mbuf *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 341 /* Same as in dn_flow_queue, numbytes can become large */ 342 int64_t numbytes; /* bits I can transmit (more or less). */ 343 uint64_t burst; /* burst size, scaled: bits * hz */ 344 345 dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 346 dn_key idle_time; /* start of pipe idle time */ 347 348 /* 349 * When the tx clock come from an interface (if_name[0] != '\0'), its name 350 * is stored below, whereas the ifp is filled when the rule is configured. 351 */ 352 char if_name[IFNAMSIZ]; 353 struct ifnet *ifp ; 354 int ready ; /* set if ifp != NULL and we got a signal from it */ 355 356 struct dn_flow_set fs ; /* used with fixed-rate flows */ 357 358 /* fields to simulate a delay profile */ 359 360 #define ED_MAX_NAME_LEN 32 361 char name[ED_MAX_NAME_LEN]; 362 int loss_level; 363 int samples_no; 364 int *samples; 365 }; 366 367 /* dn_pipe_max is used to pass pipe configuration from userland onto 368 * kernel space and back 369 */ 370 #define ED_MAX_SAMPLES_NO 1024 371 struct dn_pipe_max { 372 struct dn_pipe pipe; 373 int samples[ED_MAX_SAMPLES_NO]; 374 }; 375 376 SLIST_HEAD(dn_pipe_head, dn_pipe); 377 378 #endif /* _IP_DUMMYNET_H */ 379