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.19 2008/09/20 04:36:51 sephe Exp $ 29 */ 30 31 #ifndef _IP_DUMMYNET_H 32 #define _IP_DUMMYNET_H 33 34 /* 35 * We start with a heap, which is used in the scheduler to decide when to 36 * transmit packets etc. 37 * 38 * The key for the heap is used for two different values: 39 * 40 * 1. Timer ticks- max 10K/second, so 32 bits are enough; 41 * 42 * 2. Virtual times. These increase in steps of len/x, where len is the 43 * packet length, and x is either the weight of the flow, or the sum 44 * of all weights. 45 * If we limit to max 1000 flows and a max weight of 100, then x needs 46 * 17 bits. The packet size is 16 bits, so we can easily overflow if 47 * we do not allow errors. 48 * 49 * So we use a key "dn_key" which is 64 bits. 50 * 51 * MY_M is used as a shift count when doing fixed point arithmetic 52 * (a better name would be useful...). 53 */ 54 typedef uint64_t dn_key; /* sorting key */ 55 56 /* 57 * Number of left shift to obtain a larger precision 58 * 59 * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 60 * virtual time wraps every 15 days. 61 */ 62 #define MY_M 16 63 64 #ifdef _KERNEL 65 66 /* 67 * A heap entry is made of a key and a pointer to the actual object stored 68 * in the heap. 69 * 70 * The heap is an array of dn_heap_entry entries, dynamically allocated. 71 * Current size is "size", with "elements" actually in use. 72 * 73 * The heap normally supports only ordered insert and extract from the top. 74 * If we want to extract an object from the middle of the heap, we have to 75 * know where the object itself is located in the heap (or we need to scan 76 * the whole array). To this purpose, an object has a field (int) which 77 * contains the index of the object itself into the heap. When the object 78 * is moved, the field must also be updated. The offset of the index in the 79 * object is stored in the 'offset' field in the heap descriptor. The 80 * assumption is that this offset is non-zero if we want to support extract 81 * from the middle. 82 */ 83 struct dn_heap_entry { 84 dn_key key; /* sorting key. Topmost element is smallest one */ 85 void *object; /* object pointer */ 86 }; 87 88 struct dn_heap { 89 int size; 90 int elements; 91 int offset; /* XXX if > 0 this is the offset of direct ptr to obj */ 92 struct dn_heap_entry *p; /* really an array of "size" entries */ 93 }; 94 95 struct dn_flow_id { 96 uint16_t fid_type; /* ETHERTYPE_ */ 97 uint16_t pad; 98 union { 99 struct { 100 uint32_t dst_ip; 101 uint32_t src_ip; 102 uint16_t dst_port; 103 uint16_t src_port; 104 uint8_t proto; 105 uint8_t flags; 106 } inet; 107 } fid_u; 108 #define fid_dst_ip fid_u.inet.dst_ip 109 #define fid_src_ip fid_u.inet.src_ip 110 #define fid_dst_port fid_u.inet.dst_port 111 #define fid_src_port fid_u.inet.src_port 112 #define fid_proto fid_u.inet.proto 113 #define fid_flags fid_u.inet.flags 114 }; 115 116 typedef void (*ip_dn_unref_priv_t)(void *); 117 struct lwkt_port; 118 119 /* 120 * struct dn_pkt identifies a packet in the dummynet queue, but is also used 121 * to tag packets passed back to the various destinations (ip_input(), 122 * ip_output() and so on). 123 * 124 * It is a tag (PACKET_TAG_DUMMYNET) associated with the actual mbuf. 125 */ 126 struct dn_pkt { 127 struct mbuf *dn_m; 128 TAILQ_ENTRY(dn_pkt) dn_next; 129 130 void *dn_priv; 131 ip_dn_unref_priv_t dn_unref_priv; 132 133 uint32_t dn_flags; /* action when packet comes out. */ 134 #define DN_FLAGS_IS_PIPE 0x10 135 #define DN_FLAGS_DIR_MASK 0x0f 136 #define DN_TO_IP_OUT 1 137 #define DN_TO_IP_IN 2 138 #define DN_TO_ETH_DEMUX 4 139 #define DN_TO_ETH_OUT 5 140 #define DN_TO_MAX 6 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 u_short pipe_nr; /* pipe/flow_set number */ 149 u_short pad; 150 151 struct dn_flow_id id; /* flow id */ 152 int cpuid; /* target cpuid, for assertion */ 153 struct lwkt_port *msgport; /* target msgport */ 154 }; 155 TAILQ_HEAD(dn_pkt_queue, dn_pkt); 156 157 /* 158 * Overall structure of dummynet (with WF2Q+): 159 * 160 * In dummynet, packets are selected with the firewall rules, and passed to 161 * two different objects: PIPE or QUEUE. 162 * 163 * A QUEUE is just a queue with configurable size and queue management policy. 164 * It is also associated with a mask (to discriminate among different flows), 165 * a weight (used to give different shares of the bandwidth to different flows) 166 * and a "pipe", which essentially supplies the transmit clock for all queues 167 * associated with that pipe. 168 * 169 * A PIPE emulates a fixed-bandwidth link, whose bandwidth is configurable. 170 * The "clock" for a pipe comes from an internal timer. A pipe is also 171 * associated with one (or more, if masks are used) queue, where all packets 172 * for that pipe are stored. 173 * 174 * The bandwidth available on the pipe is shared by the queues associated with 175 * that pipe (only one in case the packet is sent to a PIPE) according to the 176 * WF2Q+ scheduling algorithm and the configured weights. 177 * 178 * In general, incoming packets are stored in the appropriate queue, which is 179 * then placed into one of a few heaps managed by a scheduler to decide when 180 * the packet should be extracted. The scheduler (a function called dummynet()) 181 * is run at every timer tick, and grabs queues from the head of the heaps when 182 * they are ready for processing. 183 * 184 * There are three data structures definining a pipe and associated queues: 185 * 186 * + dn_pipe, which contains the main configuration parameters related to 187 * delay and bandwidth; 188 * + dn_flow_set, which contains WF2Q+ configuration, flow masks, plr and 189 * RED configuration; 190 * + dn_flow_queue, which is the per-flow queue (containing the packets) 191 * 192 * Multiple dn_flow_set can be linked to the same pipe, and multiple 193 * dn_flow_queue can be linked to the same dn_flow_set. 194 * All data structures are linked in a linear list which is used for 195 * housekeeping purposes. 196 * 197 * During configuration, we create and initialize the dn_flow_set and dn_pipe 198 * structures (a dn_pipe also contains a dn_flow_set). 199 * 200 * At runtime: packets are sent to the appropriate dn_flow_set (either WFQ 201 * ones, or the one embedded in the dn_pipe for fixed-rate flows), which in 202 * turn dispatches them to the appropriate dn_flow_queue (created dynamically 203 * according to the masks). 204 * 205 * The transmit clock for fixed rate flows (ready_event()) selects the 206 * dn_flow_queue to be used to transmit the next packet. For WF2Q, 207 * wfq_ready_event() extract a pipe which in turn selects the right flow using 208 * a number of heaps defined into the pipe itself. 209 */ 210 211 /* 212 * Per flow queue. This contains the flow identifier, the queue of packets, 213 * counters, and parameters used to support both RED and WF2Q+. 214 * 215 * A dn_flow_queue is created and initialized whenever a packet for a new 216 * flow arrives. 217 */ 218 struct dn_flow_queue { 219 struct dn_flow_id id; 220 LIST_ENTRY(dn_flow_queue) q_link; 221 222 struct dn_pkt_queue queue; /* queue of packets */ 223 u_int len; 224 u_int len_bytes; 225 u_long numbytes; /* credit for transmission (dynamic queues) */ 226 227 uint64_t tot_pkts; /* statistics counters */ 228 uint64_t tot_bytes; 229 uint32_t drops; 230 231 int hash_slot; /* debugging/diagnostic */ 232 233 /* RED parameters */ 234 int avg; /* average queue length est. (scaled) */ 235 int count; /* arrivals since last RED drop */ 236 int random; /* random value (scaled) */ 237 uint32_t q_time; /* start of queue idle time */ 238 239 /* WF2Q+ support */ 240 struct dn_flow_set *fs; /* parent flow set */ 241 int heap_pos; /* position (index) of struct in heap */ 242 dn_key sched_time; /* current time when queue enters ready_heap */ 243 244 dn_key S, F; /* start time, finish time */ 245 /* 246 * Setting F < S means the timestamp is invalid. We only need 247 * to test this when the queue is empty. 248 */ 249 }; 250 LIST_HEAD(dn_flowqueue_head, dn_flow_queue); 251 252 /* 253 * flow_set descriptor. Contains the "template" parameters for the queue 254 * 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 hashing 257 * 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 basis. 259 * 260 * A dn_flow_set is created whenever a new queue or pipe is created (in the 261 * latter case, the structure is located inside the struct dn_pipe). 262 */ 263 struct dn_flow_set { 264 u_short fs_nr; /* flow_set number */ 265 u_short flags_fs; /* see 'Flow set flags' */ 266 267 LIST_ENTRY(dn_flow_set) fs_link; 268 269 struct dn_pipe *pipe; /* pointer to parent pipe */ 270 u_short parent_nr; /* parent pipe#, 0 if local to a pipe */ 271 272 int weight; /* WFQ queue weight */ 273 int qsize; /* queue size in slots or bytes */ 274 int plr; /* pkt loss rate (2^31-1 means 100%) */ 275 276 struct dn_flow_id flow_mask; 277 278 /* hash table of queues onto this flow_set */ 279 int rq_size; /* number of slots */ 280 int rq_elements; /* active elements */ 281 struct dn_flowqueue_head *rq;/* array of rq_size entries */ 282 283 uint32_t last_expired; /* do not expire too frequently */ 284 int backlogged; /* #active queues for this flowset */ 285 286 /* RED parameters */ 287 int w_q; /* queue weight (scaled) */ 288 int max_th; /* maximum threshold for queue (scaled) */ 289 int min_th; /* minimum threshold for queue (scaled) */ 290 int max_p; /* maximum value for p_b (scaled) */ 291 u_int c_1; /* max_p/(max_th-min_th) (scaled) */ 292 u_int c_2; /* max_p*min_th/(max_th-min_th) (scaled) */ 293 u_int c_3; /* for GRED, (1-max_p)/max_th (scaled) */ 294 u_int c_4; /* for GRED, 1 - 2*max_p (scaled) */ 295 u_int *w_q_lookup; /* lookup table for computing (1-w_q)^t */ 296 u_int lookup_depth; /* depth of lookup table */ 297 int lookup_step; /* granularity inside the lookup table */ 298 int lookup_weight; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 299 int avg_pkt_size; /* medium packet size */ 300 int max_pkt_size; /* max packet size */ 301 }; 302 LIST_HEAD(dn_flowset_head, dn_flow_set); 303 304 /* 305 * Pipe descriptor. Contains global parameters, delay-line queue, and the 306 * flow_set used for fixed-rate queues. 307 * 308 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 309 * + not_eligible_heap, for queues whose start time is higher than the 310 * virtual time. Sorted by start time. 311 * + scheduler_heap, for queues eligible for scheduling. Sorted by finish 312 * time. 313 * + idle_heap, all flows that are idle and can be removed. We do that on 314 * each tick so we do not slow down too much operations during forwarding. 315 */ 316 struct dn_pipe { /* a pipe */ 317 int pipe_nr; /* number */ 318 int bandwidth; /* really, bytes/tick. */ 319 int delay; /* really, ticks */ 320 321 struct dn_pkt_queue p_queue;/* packets in delay line */ 322 LIST_ENTRY(dn_pipe) p_link; 323 324 /* WF2Q+ */ 325 struct dn_heap scheduler_heap; /* top extract - key Finish time*/ 326 struct dn_heap not_eligible_heap; /* top extract- key Start time */ 327 struct dn_heap idle_heap; /* random extract - key Start=Finish time */ 328 329 dn_key V; /* virtual time */ 330 int sum; /* sum of weights of all active sessions */ 331 int numbytes; /* bits I can transmit (more or less). */ 332 333 dn_key sched_time; /* time pipe was scheduled in ready_heap */ 334 335 struct dn_flow_set fs; /* used with fixed-rate flows */ 336 }; 337 LIST_HEAD(dn_pipe_head, dn_pipe); 338 339 struct dn_sopt { 340 int dn_sopt_name; 341 void *dn_sopt_arg; 342 size_t dn_sopt_arglen; 343 }; 344 345 typedef int ip_dn_ctl_t(struct dn_sopt *); 346 typedef int ip_dn_io_t(struct mbuf *); 347 348 extern ip_dn_ctl_t *ip_dn_ctl_ptr; 349 extern ip_dn_io_t *ip_dn_io_ptr; 350 351 void ip_dn_queue(struct mbuf *); 352 void ip_dn_packet_free(struct dn_pkt *); 353 void ip_dn_packet_redispatch(struct dn_pkt *); 354 int ip_dn_sockopt(struct sockopt *); 355 356 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) 357 358 #endif /* _KERNEL */ 359 360 struct dn_ioc_flowid { 361 uint16_t type; /* ETHERTYPE_ */ 362 uint16_t pad; 363 union { 364 struct { 365 uint32_t dst_ip; 366 uint32_t src_ip; 367 uint16_t dst_port; 368 uint16_t src_port; 369 uint8_t proto; 370 uint8_t flags; 371 } ip; 372 uint8_t pad[64]; 373 } u; 374 }; 375 376 struct dn_ioc_flowqueue { 377 u_int len; 378 u_int len_bytes; 379 380 uint64_t tot_pkts; 381 uint64_t tot_bytes; 382 uint32_t drops; 383 384 int hash_slot; /* debugging/diagnostic */ 385 dn_key S; /* virtual start time */ 386 dn_key F; /* virtual finish time */ 387 388 struct dn_ioc_flowid id; 389 uint8_t reserved[16]; 390 }; 391 392 struct dn_ioc_flowset { 393 u_short fs_type; /* DN_IS_{QUEUE,PIPE}, MUST be first */ 394 395 u_short fs_nr; /* flow_set number */ 396 u_short flags_fs; /* see 'Flow set flags' */ 397 u_short parent_nr; /* parent pipe#, 0 if local to a pipe */ 398 399 int weight; /* WFQ queue weight */ 400 int qsize; /* queue size in slots or bytes */ 401 int plr; /* pkt loss rate (2^31-1 means 100%) */ 402 403 /* Hash table information */ 404 int rq_size; /* number of slots */ 405 int rq_elements; /* active elements */ 406 407 /* RED parameters */ 408 int w_q; /* queue weight (scaled) */ 409 int max_th; /* maximum threshold for queue (scaled) */ 410 int min_th; /* minimum threshold for queue (scaled) */ 411 int max_p; /* maximum value for p_b (scaled) */ 412 int lookup_step; /* granularity inside the lookup table */ 413 int lookup_weight; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 414 415 struct dn_ioc_flowid flow_mask; 416 uint8_t reserved[16]; 417 }; 418 419 struct dn_ioc_pipe { 420 struct dn_ioc_flowset fs; /* MUST be first */ 421 422 int pipe_nr; /* pipe number */ 423 int bandwidth; /* bit/second */ 424 int delay; /* milliseconds */ 425 426 dn_key V; /* virtual time */ 427 428 uint8_t reserved[16]; 429 }; 430 431 /* 432 * Flow set flags 433 */ 434 #define DN_HAVE_FLOW_MASK 0x0001 435 #define DN_IS_RED 0x0002 436 #define DN_IS_GENTLE_RED 0x0004 437 #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 438 #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 439 #define DN_IS_PIPE 0x4000 440 #define DN_IS_QUEUE 0x8000 441 442 /* 443 * Macros for RED 444 */ 445 #define SCALE_RED 16 446 #define SCALE(x) ((x) << SCALE_RED) 447 #define SCALE_VAL(x) ((x) >> SCALE_RED) 448 #define SCALE_MUL(x, y) (((x) * (y)) >> SCALE_RED) 449 450 /* 451 * Maximum pipe number 452 */ 453 #define DN_PIPE_NR_MAX 65536 454 455 #endif /* !_IP_DUMMYNET_H */ 456