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.8 2007/10/20 11:10:50 sephe 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 uint64_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 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 #if defined(_KERNEL) || defined(_KERNEL_STRUCTURES) 108 109 /* 110 * struct dn_pkt identifies a packet in the dummynet queue, but 111 * is also used to tag packets passed back to the various destinations 112 * (ip_input(), ip_output() and so on). 113 * As such the first part of the structure must be a struct m_hdr, 114 * followed by dummynet-specific parameters. The m_hdr must be 115 * initialized with 116 * mh_type = MT_TAG; 117 * mh_flags = PACKET_TYPE_DUMMYNET; 118 * mh_next = <pointer to the actual mbuf> 119 * 120 * mh_nextpkt, mh_data are free for dummynet use. 121 */ 122 struct dn_pkt { 123 struct m_hdr hdr; 124 #define dn_m hdr.mh_next /* packet to be forwarded */ 125 126 struct dn_pkt *dn_next; 127 128 struct ip_fw *rule; /* matching rule */ 129 int dn_dir; /* action when packet comes out. */ 130 #define DN_TO_IP_OUT 1 131 #define DN_TO_IP_IN 2 132 #define DN_TO_ETH_DEMUX 4 133 #define DN_TO_ETH_OUT 5 134 135 dn_key output_time; /* when the pkt is due for delivery */ 136 struct ifnet *ifp; /* interface, for ip_output */ 137 struct sockaddr_in *dn_dst; 138 struct route ro; /* route, for ip_output. MUST COPY */ 139 int flags; /* flags, for ip_output (IPv6 ?) */ 140 }; 141 142 #endif 143 144 /* 145 * Overall structure of dummynet (with WF2Q+): 146 * 147 * In dummynet, packets are selected with the firewall rules, and passed 148 * to two different objects: PIPE or QUEUE. 149 * 150 * A QUEUE is just a queue with configurable size and queue management 151 * policy. It is also associated with a mask (to discriminate among 152 * different flows), a weight (used to give different shares of the 153 * bandwidth to different flows) and a "pipe", which essentially 154 * supplies the transmit clock for all queues associated with that 155 * pipe. 156 * 157 * A PIPE emulates a fixed-bandwidth link, whose bandwidth is 158 * configurable. The "clock" for a pipe can come from either an 159 * internal timer, or from the transmit interrupt of an interface. 160 * A pipe is also associated with one (or more, if masks are used) 161 * queue, where all packets for that pipe are stored. 162 * 163 * The bandwidth available on the pipe is shared by the queues 164 * associated with that pipe (only one in case the packet is sent 165 * to a PIPE) according to the WF2Q+ scheduling algorithm and the 166 * configured weights. 167 * 168 * In general, incoming packets are stored in the appropriate queue, 169 * which is then placed into one of a few heaps managed by a scheduler 170 * to decide when the packet should be extracted. 171 * The scheduler (a function called dummynet()) is run at every timer 172 * tick, and grabs queues from the head of the heaps when they are 173 * ready for processing. 174 * 175 * There are three data structures definining a pipe and associated queues: 176 * 177 * + dn_pipe, which contains the main configuration parameters related 178 * to delay and bandwidth; 179 * + dn_flow_set, which contains WF2Q+ configuration, flow 180 * masks, plr and RED configuration; 181 * + dn_flow_queue, which is the per-flow queue (containing the packets) 182 * 183 * Multiple dn_flow_set can be linked to the same pipe, and multiple 184 * dn_flow_queue can be linked to the same dn_flow_set. 185 * All data structures are linked in a linear list which is used for 186 * housekeeping purposes. 187 * 188 * During configuration, we create and initialize the dn_flow_set 189 * and dn_pipe structures (a dn_pipe also contains a dn_flow_set). 190 * 191 * At runtime: packets are sent to the appropriate dn_flow_set (either 192 * WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 193 * which in turn dispatches them to the appropriate dn_flow_queue 194 * (created dynamically according to the masks). 195 * 196 * The transmit clock for fixed rate flows (ready_event()) selects the 197 * dn_flow_queue to be used to transmit the next packet. For WF2Q, 198 * wfq_ready_event() extract a pipe which in turn selects the right 199 * flow using a number of heaps defined into the pipe itself. 200 */ 201 202 /* 203 * per flow queue. This contains the flow identifier, the queue 204 * of packets, counters, and parameters used to support both RED and 205 * WF2Q+. 206 * 207 * A dn_flow_queue is created and initialized whenever a packet for 208 * a new flow arrives. 209 */ 210 struct dn_flow_queue { 211 struct dn_flow_queue *next; 212 struct ipfw_flow_id id; 213 214 struct dn_pkt *head, *tail; /* queue of packets */ 215 u_int len; 216 u_int len_bytes; 217 u_long numbytes; /* credit for transmission (dynamic queues) */ 218 219 uint64_t tot_pkts; /* statistics counters */ 220 uint64_t tot_bytes; 221 uint32_t drops; 222 223 int hash_slot; /* debugging/diagnostic */ 224 225 /* RED parameters */ 226 int avg; /* average queue length est. (scaled) */ 227 int count; /* arrivals since last RED drop */ 228 int random; /* random value (scaled) */ 229 uint32_t q_time; /* start of queue idle time */ 230 231 /* WF2Q+ support */ 232 struct dn_flow_set *fs; /* parent flow set */ 233 int heap_pos; /* position (index) of struct in heap */ 234 dn_key sched_time; /* current time when queue enters ready_heap */ 235 236 dn_key S, F; /* start time, finish time */ 237 /* 238 * Setting F < S means the timestamp is invalid. We only need 239 * to test this when the queue is empty. 240 */ 241 }; 242 243 /* 244 * flow_set descriptor. Contains the "template" parameters for the 245 * queue configuration, and pointers to the hash table of dn_flow_queue's. 246 * 247 * The hash table is an array of lists -- we identify the slot by 248 * hashing the flow-id, then scan the list looking for a match. 249 * The size of the hash table (buckets) is configurable on a per-queue 250 * basis. 251 * 252 * A dn_flow_set is created whenever a new queue or pipe is created (in the 253 * latter case, the structure is located inside the struct dn_pipe). 254 */ 255 struct dn_flow_set { 256 struct dn_flow_set *next; /* next flow set in all_flow_sets list */ 257 258 u_short fs_nr; /* flow_set number */ 259 u_short flags_fs; 260 #define DN_HAVE_FLOW_MASK 0x0001 261 #define DN_IS_RED 0x0002 262 #define DN_IS_GENTLE_RED 0x0004 263 #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 264 #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 265 #define DN_IS_PIPE 0x4000 266 #define DN_IS_QUEUE 0x8000 267 268 struct dn_pipe *pipe; /* pointer to parent pipe */ 269 u_short parent_nr; /* parent pipe#, 0 if local to a pipe */ 270 271 int weight; /* WFQ queue weight */ 272 int qsize; /* queue size in slots or bytes */ 273 int plr; /* pkt loss rate (2^31-1 means 100%) */ 274 275 struct ipfw_flow_id flow_mask; 276 277 /* hash table of queues onto this flow_set */ 278 int rq_size; /* number of slots */ 279 int rq_elements; /* active elements */ 280 struct dn_flow_queue **rq; /* array of rq_size entries */ 281 282 uint32_t last_expired; /* do not expire too frequently */ 283 int backlogged; /* #active queues for this flowset */ 284 285 /* RED parameters */ 286 #define SCALE_RED 16 287 #define SCALE(x) ((x) << SCALE_RED) 288 #define SCALE_VAL(x) ((x) >> SCALE_RED) 289 #define SCALE_MUL(x, y) (((x) * (y)) >> SCALE_RED) 290 int w_q; /* queue weight (scaled) */ 291 int max_th; /* maximum threshold for queue (scaled) */ 292 int min_th; /* minimum threshold for queue (scaled) */ 293 int max_p; /* maximum value for p_b (scaled) */ 294 u_int c_1; /* max_p/(max_th-min_th) (scaled) */ 295 u_int c_2; /* max_p*min_th/(max_th-min_th) (scaled) */ 296 u_int c_3; /* for GRED, (1-max_p)/max_th (scaled) */ 297 u_int c_4; /* for GRED, 1 - 2*max_p (scaled) */ 298 u_int *w_q_lookup; /* lookup table for computing (1-w_q)^t */ 299 u_int lookup_depth; /* depth of lookup table */ 300 int lookup_step; /* granularity inside the lookup table */ 301 int lookup_weight; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 302 int avg_pkt_size; /* medium packet size */ 303 int max_pkt_size; /* max packet size */ 304 }; 305 306 /* 307 * Pipe descriptor. Contains global parameters, delay-line queue, 308 * and the flow_set used for fixed-rate queues. 309 * 310 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 311 * not_eligible_heap, for queues whose start time is higher 312 * than the virtual time. Sorted by start time. 313 * scheduler_heap, for queues eligible for scheduling. Sorted by 314 * finish time. 315 * idle_heap, all flows that are idle and can be removed. We 316 * do that on each tick so we do not slow down too much 317 * operations during forwarding. 318 * 319 */ 320 struct dn_pipe { /* a pipe */ 321 struct dn_pipe *next; 322 323 int pipe_nr; /* number */ 324 int bandwidth; /* really, bytes/tick. */ 325 int delay; /* really, ticks */ 326 327 struct dn_pkt *head, *tail; /* packets in delay line */ 328 329 /* WF2Q+ */ 330 struct dn_heap scheduler_heap; /* top extract - key Finish time*/ 331 struct dn_heap not_eligible_heap; /* top extract- key Start time */ 332 struct dn_heap idle_heap; /* random extract - key Start=Finish time */ 333 334 dn_key V; /* virtual time */ 335 int sum; /* sum of weights of all active sessions */ 336 int numbytes; /* bits I can transmit (more or less). */ 337 338 dn_key sched_time; /* time pipe was scheduled in ready_heap */ 339 340 /* 341 * When the tx clock come from an interface (if_name[0] != '\0'), its name 342 * is stored below, whereas the ifp is filled when the rule is configured. 343 */ 344 char if_name[IFNAMSIZ]; 345 struct ifnet *ifp; 346 int ready; /* set if ifp != NULL and we got a signal from it */ 347 348 struct dn_flow_set fs; /* used with fixed-rate flows */ 349 }; 350 351 #ifdef _KERNEL 352 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ 353 typedef void ip_dn_ruledel_t(void *); /* ip_fw2.c */ 354 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir, 355 struct ip_fw_args *fwa); 356 extern ip_dn_ctl_t *ip_dn_ctl_ptr; 357 extern ip_dn_ruledel_t *ip_dn_ruledel_ptr; 358 extern ip_dn_io_t *ip_dn_io_ptr; 359 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) 360 #endif 361 362 #endif /* !_IP_DUMMYNET_H */ 363