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: src/sys/netinet/ip_dummynet.h,v 1.10.2.9 2003/05/13 09:31:06 maxim Exp $ 28 * $DragonFly: src/sys/net/dummynet/ip_dummynet.h,v 1.5 2006/06/25 11:02:39 corecode Exp $ 29 */ 30 31 #ifndef _IP_DUMMYNET_H 32 #define _IP_DUMMYNET_H 33 34 /* 35 * Definition of dummynet data structures. In the structures, I decided 36 * not to use the macros in <sys/queue.h> in the hope of making the code 37 * easier to port to other architectures. The type of lists and queue we 38 * use here is pretty simple anyways. 39 */ 40 41 /* 42 * We start with a heap, which is used in the scheduler to decide when 43 * to transmit packets etc. 44 * 45 * The key for the heap is used for two different values: 46 * 47 * 1. timer ticks- max 10K/second, so 32 bits are enough; 48 * 49 * 2. virtual times. These increase in steps of len/x, where len is the 50 * packet length, and x is either the weight of the flow, or the 51 * sum of all weights. 52 * If we limit to max 1000 flows and a max weight of 100, then 53 * x needs 17 bits. The packet size is 16 bits, so we can easily 54 * overflow if we do not allow errors. 55 * So we use a key "dn_key" which is 64 bits. Some macros are used to 56 * compare key values and handle wraparounds. 57 * MAX64 returns the largest of two key values. 58 * MY_M is used as a shift count when doing fixed point arithmetic 59 * (a better name would be useful...). 60 */ 61 typedef u_int64_t dn_key ; /* sorting key */ 62 #define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 63 #define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 64 #define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) 65 #define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) 66 #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) 67 #define MY_M 16 /* number of left shift to obtain a larger precision */ 68 69 /* 70 * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 71 * virtual time wraps every 15 days. 72 */ 73 74 /* 75 * The OFFSET_OF macro is used to return the offset of a field within 76 * a structure. It is used by the heap management routines. 77 */ 78 #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) 79 80 /* 81 * The maximum hash table size for queues. This value must be a power 82 * of 2. 83 */ 84 #define DN_MAX_HASH_SIZE 65536 85 86 /* 87 * A heap entry is made of a key and a pointer to the actual 88 * object stored in the heap. 89 * The heap is an array of dn_heap_entry entries, dynamically allocated. 90 * Current size is "size", with "elements" actually in use. 91 * The heap normally supports only ordered insert and extract from the top. 92 * If we want to extract an object from the middle of the heap, we 93 * have to know where the object itself is located in the heap (or we 94 * need to scan the whole array). To this purpose, an object has a 95 * field (int) which contains the index of the object itself into the 96 * heap. When the object is moved, the field must also be updated. 97 * The offset of the index in the object is stored in the 'offset' 98 * field in the heap descriptor. The assumption is that this offset 99 * is non-zero if we want to support extract from the middle. 100 */ 101 struct dn_heap_entry { 102 dn_key key ; /* sorting key. Topmost element is smallest one */ 103 void *object ; /* object pointer */ 104 } ; 105 106 struct dn_heap { 107 int size ; 108 int elements ; 109 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 110 struct dn_heap_entry *p ; /* really an array of "size" entries */ 111 } ; 112 113 #if defined(_KERNEL) || defined(_KERNEL_STRUCTURES) 114 115 /* 116 * struct dn_pkt identifies a packet in the dummynet queue, but 117 * is also used to tag packets passed back to the various destinations 118 * (ip_input(), ip_output() and so on). 119 * As such the first part of the structure must be a struct m_hdr, 120 * followed by dummynet-specific parameters. The m_hdr must be 121 * initialized with 122 * mh_type = MT_TAG; 123 * mh_flags = PACKET_TYPE_DUMMYNET; 124 * mh_next = <pointer to the actual mbuf> 125 * 126 * mh_nextpkt, mh_data are free for dummynet use (mh_nextpkt is used to 127 * build a linked list of packets in a dummynet queue). 128 */ 129 struct dn_pkt { 130 struct m_hdr hdr ; 131 #define DN_NEXT_NC(x) (x)->hdr.mh_nextpkt 132 #define DN_NEXT(x) (struct dn_pkt *)DN_NEXT_NC(x) 133 #define dn_m hdr.mh_next /* packet to be forwarded */ 134 135 struct ip_fw *rule; /* matching rule */ 136 int dn_dir; /* action when packet comes out. */ 137 #define DN_TO_IP_OUT 1 138 #define DN_TO_IP_IN 2 139 #define DN_TO_ETH_DEMUX 4 140 #define DN_TO_ETH_OUT 5 141 142 dn_key output_time; /* when the pkt is due for delivery */ 143 struct ifnet *ifp; /* interface, for ip_output */ 144 struct sockaddr_in *dn_dst ; 145 struct route ro; /* route, for ip_output. MUST COPY */ 146 int flags ; /* flags, for ip_output (IPv6 ?) */ 147 }; 148 149 #endif 150 151 /* 152 * Overall structure of dummynet (with WF2Q+): 153 154 In dummynet, packets are selected with the firewall rules, and passed 155 to two different objects: PIPE or QUEUE. 156 157 A QUEUE is just a queue with configurable size and queue management 158 policy. It is also associated with a mask (to discriminate among 159 different flows), a weight (used to give different shares of the 160 bandwidth to different flows) and a "pipe", which essentially 161 supplies the transmit clock for all queues associated with that 162 pipe. 163 164 A PIPE emulates a fixed-bandwidth link, whose bandwidth is 165 configurable. The "clock" for a pipe can come from either an 166 internal timer, or from the transmit interrupt of an interface. 167 A pipe is also associated with one (or more, if masks are used) 168 queue, where all packets for that pipe are stored. 169 170 The bandwidth available on the pipe is shared by the queues 171 associated with that pipe (only one in case the packet is sent 172 to a PIPE) according to the WF2Q+ scheduling algorithm and the 173 configured weights. 174 175 In general, incoming packets are stored in the appropriate queue, 176 which is then placed into one of a few heaps managed by a scheduler 177 to decide when the packet should be extracted. 178 The scheduler (a function called dummynet()) is run at every timer 179 tick, and grabs queues from the head of the heaps when they are 180 ready for processing. 181 182 There are three data structures definining a pipe and associated queues: 183 184 + dn_pipe, which contains the main configuration parameters related 185 to delay and bandwidth; 186 + dn_flow_set, which contains WF2Q+ configuration, flow 187 masks, plr and RED configuration; 188 + dn_flow_queue, which is the per-flow queue (containing the packets) 189 190 Multiple dn_flow_set can be linked to the same pipe, and multiple 191 dn_flow_queue can be linked to the same dn_flow_set. 192 All data structures are linked in a linear list which is used for 193 housekeeping purposes. 194 195 During configuration, we create and initialize the dn_flow_set 196 and dn_pipe structures (a dn_pipe also contains a dn_flow_set). 197 198 At runtime: packets are sent to the appropriate dn_flow_set (either 199 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 200 which in turn dispatches them to the appropriate dn_flow_queue 201 (created dynamically according to the masks). 202 203 The transmit clock for fixed rate flows (ready_event()) selects the 204 dn_flow_queue to be used to transmit the next packet. For WF2Q, 205 wfq_ready_event() extract a pipe which in turn selects the right 206 flow using a number of heaps defined into the pipe itself. 207 208 * 209 */ 210 211 /* 212 * per flow queue. This contains the flow identifier, the queue 213 * of packets, counters, and parameters used to support both RED and 214 * WF2Q+. 215 * 216 * A dn_flow_queue is created and initialized whenever a packet for 217 * a new flow arrives. 218 */ 219 struct dn_flow_queue { 220 struct dn_flow_queue *next ; 221 struct ipfw_flow_id id ; 222 223 struct dn_pkt *head, *tail ; /* queue of packets */ 224 u_int len ; 225 u_int len_bytes ; 226 u_long numbytes ; /* credit for transmission (dynamic queues) */ 227 228 u_int64_t tot_pkts ; /* statistics counters */ 229 u_int64_t tot_bytes ; 230 u_int32_t drops ; 231 232 int hash_slot ; /* debugging/diagnostic */ 233 234 /* RED parameters */ 235 int avg ; /* average queue length est. (scaled) */ 236 int count ; /* arrivals since last RED drop */ 237 int random ; /* random value (scaled) */ 238 u_int32_t q_time ; /* start of queue idle time */ 239 240 /* WF2Q+ support */ 241 struct dn_flow_set *fs ; /* parent flow set */ 242 int heap_pos ; /* position (index) of struct in heap */ 243 dn_key sched_time ; /* current time when queue enters ready_heap */ 244 245 dn_key S,F ; /* start time, finish time */ 246 /* 247 * Setting F < S means the timestamp is invalid. We only need 248 * to test this when the queue is empty. 249 */ 250 } ; 251 252 /* 253 * flow_set descriptor. Contains the "template" parameters for the 254 * queue configuration, and pointers to the hash table of dn_flow_queue's. 255 * 256 * The hash table is an array of lists -- we identify the slot by 257 * hashing the flow-id, then scan the list looking for a match. 258 * The size of the hash table (buckets) is configurable on a per-queue 259 * basis. 260 * 261 * A dn_flow_set is created whenever a new queue or pipe is created (in the 262 * latter case, the structure is located inside the struct dn_pipe). 263 */ 264 struct dn_flow_set { 265 struct dn_flow_set *next; /* next flow set in all_flow_sets list */ 266 267 u_short fs_nr ; /* flow_set number */ 268 u_short flags_fs; 269 #define DN_HAVE_FLOW_MASK 0x0001 270 #define DN_IS_RED 0x0002 271 #define DN_IS_GENTLE_RED 0x0004 272 #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 273 #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 274 #define DN_IS_PIPE 0x4000 275 #define DN_IS_QUEUE 0x8000 276 277 struct dn_pipe *pipe ; /* pointer to parent pipe */ 278 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 279 280 int weight ; /* WFQ queue weight */ 281 int qsize ; /* queue size in slots or bytes */ 282 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 283 284 struct ipfw_flow_id flow_mask ; 285 286 /* hash table of queues onto this flow_set */ 287 int rq_size ; /* number of slots */ 288 int rq_elements ; /* active elements */ 289 struct dn_flow_queue **rq; /* array of rq_size entries */ 290 291 u_int32_t last_expired ; /* do not expire too frequently */ 292 int backlogged ; /* #active queues for this flowset */ 293 294 /* RED parameters */ 295 #define SCALE_RED 16 296 #define SCALE(x) ( (x) << SCALE_RED ) 297 #define SCALE_VAL(x) ( (x) >> SCALE_RED ) 298 #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 299 int w_q ; /* queue weight (scaled) */ 300 int max_th ; /* maximum threshold for queue (scaled) */ 301 int min_th ; /* minimum threshold for queue (scaled) */ 302 int max_p ; /* maximum value for p_b (scaled) */ 303 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 304 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 305 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 306 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 307 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 308 u_int lookup_depth ; /* depth of lookup table */ 309 int lookup_step ; /* granularity inside the lookup table */ 310 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 311 int avg_pkt_size ; /* medium packet size */ 312 int max_pkt_size ; /* max packet size */ 313 } ; 314 315 /* 316 * Pipe descriptor. Contains global parameters, delay-line queue, 317 * and the flow_set used for fixed-rate queues. 318 * 319 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 320 * not_eligible_heap, for queues whose start time is higher 321 * than the virtual time. Sorted by start time. 322 * scheduler_heap, for queues eligible for scheduling. Sorted by 323 * finish time. 324 * idle_heap, all flows that are idle and can be removed. We 325 * do that on each tick so we do not slow down too much 326 * operations during forwarding. 327 * 328 */ 329 struct dn_pipe { /* a pipe */ 330 struct dn_pipe *next ; 331 332 int pipe_nr ; /* number */ 333 int bandwidth; /* really, bytes/tick. */ 334 int delay ; /* really, ticks */ 335 336 struct dn_pkt *head, *tail ; /* packets in delay line */ 337 338 /* WF2Q+ */ 339 struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ 340 struct dn_heap not_eligible_heap; /* top extract- key Start time */ 341 struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ 342 343 dn_key V ; /* virtual time */ 344 int sum; /* sum of weights of all active sessions */ 345 int numbytes; /* bits I can transmit (more or less). */ 346 347 dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 348 349 /* 350 * When the tx clock come from an interface (if_name[0] != '\0'), its name 351 * is stored below, whereas the ifp is filled when the rule is configured. 352 */ 353 char if_name[IFNAMSIZ]; 354 struct ifnet *ifp ; 355 int ready ; /* set if ifp != NULL and we got a signal from it */ 356 357 struct dn_flow_set fs ; /* used with fixed-rate flows */ 358 }; 359 360 #ifdef _KERNEL 361 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ 362 typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */ 363 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir, 364 struct ip_fw_args *fwa); 365 extern ip_dn_ctl_t *ip_dn_ctl_ptr; 366 extern ip_dn_ruledel_t *ip_dn_ruledel_ptr; 367 extern ip_dn_io_t *ip_dn_io_ptr; 368 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) 369 #endif 370 371 #endif /* _IP_DUMMYNET_H */ 372