1/* 2 * Copyright (c) 2000-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28/* 29 * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa 30 * Portions Copyright (c) 2000 Akamba Corp. 31 * All rights reserved 32 * 33 * Redistribution and use in source and binary forms, with or without 34 * modification, are permitted provided that the following conditions 35 * are met: 36 * 1. Redistributions of source code must retain the above copyright 37 * notice, this list of conditions and the following disclaimer. 38 * 2. Redistributions in binary form must reproduce the above copyright 39 * notice, this list of conditions and the following disclaimer in the 40 * documentation and/or other materials provided with the distribution. 41 * 42 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 43 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 44 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 45 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 46 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 47 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 48 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 49 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 50 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 51 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 52 * SUCH DAMAGE. 53 * 54 * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.32 2004/08/17 22:05:54 andre Exp $ 55 */ 56 57#ifndef _IP_DUMMYNET_H 58#define _IP_DUMMYNET_H 59 60#if !__LP64__ 61 62#include <sys/appleapiopts.h> 63 64#ifdef PRIVATE 65/* 66 * Definition of dummynet data structures. In the structures, I decided 67 * not to use the macros in <sys/queue.h> in the hope of making the code 68 * easier to port to other architectures. The type of lists and queue we 69 * use here is pretty simple anyways. 70 */ 71 72/* 73 * We start with a heap, which is used in the scheduler to decide when 74 * to transmit packets etc. 75 * 76 * The key for the heap is used for two different values: 77 * 78 * 1. timer ticks- max 10K/second, so 32 bits are enough; 79 * 80 * 2. virtual times. These increase in steps of len/x, where len is the 81 * packet length, and x is either the weight of the flow, or the 82 * sum of all weights. 83 * If we limit to max 1000 flows and a max weight of 100, then 84 * x needs 17 bits. The packet size is 16 bits, so we can easily 85 * overflow if we do not allow errors. 86 * So we use a key "dn_key" which is 64 bits. Some macros are used to 87 * compare key values and handle wraparounds. 88 * MAX64 returns the largest of two key values. 89 * MY_M is used as a shift count when doing fixed point arithmetic 90 * (a better name would be useful...). 91 */ 92typedef u_int64_t dn_key ; /* sorting key */ 93#define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 94#define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 95#define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) 96#define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) 97#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) 98#define MY_M 16 /* number of left shift to obtain a larger precision */ 99 100/* 101 * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 102 * virtual time wraps every 15 days. 103 */ 104 105/* 106 * The OFFSET_OF macro is used to return the offset of a field within 107 * a structure. It is used by the heap management routines. 108 */ 109#define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) 110 111/* 112 * The maximum hash table size for queues. This value must be a power 113 * of 2. 114 */ 115#define DN_MAX_HASH_SIZE 65536 116 117/* 118 * A heap entry is made of a key and a pointer to the actual 119 * object stored in the heap. 120 * The heap is an array of dn_heap_entry entries, dynamically allocated. 121 * Current size is "size", with "elements" actually in use. 122 * The heap normally supports only ordered insert and extract from the top. 123 * If we want to extract an object from the middle of the heap, we 124 * have to know where the object itself is located in the heap (or we 125 * need to scan the whole array). To this purpose, an object has a 126 * field (int) which contains the index of the object itself into the 127 * heap. When the object is moved, the field must also be updated. 128 * The offset of the index in the object is stored in the 'offset' 129 * field in the heap descriptor. The assumption is that this offset 130 * is non-zero if we want to support extract from the middle. 131 */ 132struct dn_heap_entry { 133 dn_key key ; /* sorting key. Topmost element is smallest one */ 134 void *object ; /* object pointer */ 135} ; 136 137struct dn_heap { 138 int size ; 139 int elements ; 140 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 141 struct dn_heap_entry *p ; /* really an array of "size" entries */ 142} ; 143 144/* 145 * Packets processed by dummynet have an mbuf tag associated with 146 * them that carries their dummynet state. This is used within 147 * the dummynet code as well as outside when checking for special 148 * processing requirements. 149 */ 150#ifdef KERNEL 151#include <netinet/ip_var.h> /* for ip_out_args */ 152 153struct dn_pkt_tag { 154 struct ip_fw *rule; /* matching rule */ 155 int dn_dir; /* action when packet comes out. */ 156#define DN_TO_IP_OUT 1 157#define DN_TO_IP_IN 2 158#define DN_TO_BDG_FWD 3 159 160 dn_key output_time; /* when the pkt is due for delivery */ 161 struct ifnet *ifp; /* interface, for ip_output */ 162 struct sockaddr_in *dn_dst ; 163 struct route ro; /* route, for ip_output. MUST COPY */ 164 int flags ; /* flags, for ip_output (IPv6 ?) */ 165 struct ip_out_args ipoa; /* output args, for ip_output. MUST COPY */ 166}; 167#else 168struct dn_pkt; 169#endif /* KERNEL */ 170 171/* 172 * Overall structure of dummynet (with WF2Q+): 173 174In dummynet, packets are selected with the firewall rules, and passed 175to two different objects: PIPE or QUEUE. 176 177A QUEUE is just a queue with configurable size and queue management 178policy. It is also associated with a mask (to discriminate among 179different flows), a weight (used to give different shares of the 180bandwidth to different flows) and a "pipe", which essentially 181supplies the transmit clock for all queues associated with that 182pipe. 183 184A PIPE emulates a fixed-bandwidth link, whose bandwidth is 185configurable. The "clock" for a pipe can come from either an 186internal timer, or from the transmit interrupt of an interface. 187A pipe is also associated with one (or more, if masks are used) 188queue, where all packets for that pipe are stored. 189 190The bandwidth available on the pipe is shared by the queues 191associated with that pipe (only one in case the packet is sent 192to a PIPE) according to the WF2Q+ scheduling algorithm and the 193configured weights. 194 195In general, incoming packets are stored in the appropriate queue, 196which is then placed into one of a few heaps managed by a scheduler 197to decide when the packet should be extracted. 198The scheduler (a function called dummynet()) is run at every timer 199tick, and grabs queues from the head of the heaps when they are 200ready for processing. 201 202There are three data structures definining a pipe and associated queues: 203 204 + dn_pipe, which contains the main configuration parameters related 205 to delay and bandwidth; 206 + dn_flow_set, which contains WF2Q+ configuration, flow 207 masks, plr and RED configuration; 208 + dn_flow_queue, which is the per-flow queue (containing the packets) 209 210Multiple dn_flow_set can be linked to the same pipe, and multiple 211dn_flow_queue can be linked to the same dn_flow_set. 212All data structures are linked in a linear list which is used for 213housekeeping purposes. 214 215During configuration, we create and initialize the dn_flow_set 216and dn_pipe structures (a dn_pipe also contains a dn_flow_set). 217 218At runtime: packets are sent to the appropriate dn_flow_set (either 219WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 220which in turn dispatches them to the appropriate dn_flow_queue 221(created dynamically according to the masks). 222 223The transmit clock for fixed rate flows (ready_event()) selects the 224dn_flow_queue to be used to transmit the next packet. For WF2Q, 225wfq_ready_event() extract a pipe which in turn selects the right 226flow using a number of heaps defined into the pipe itself. 227 228 * 229 */ 230 231/* 232 * per flow queue. This contains the flow identifier, the queue 233 * of packets, counters, and parameters used to support both RED and 234 * WF2Q+. 235 * 236 * A dn_flow_queue is created and initialized whenever a packet for 237 * a new flow arrives. 238 */ 239struct dn_flow_queue { 240 struct dn_flow_queue *next ; 241 struct ipfw_flow_id id ; 242 243 struct mbuf *head, *tail ; /* queue of packets */ 244 u_int len ; 245 u_int len_bytes ; 246 u_long numbytes ; /* credit for transmission (dynamic queues) */ 247 248 u_int64_t tot_pkts ; /* statistics counters */ 249 u_int64_t tot_bytes ; 250 u_int32_t drops ; 251 252 int hash_slot ; /* debugging/diagnostic */ 253 254 /* RED parameters */ 255 int avg ; /* average queue length est. (scaled) */ 256 int count ; /* arrivals since last RED drop */ 257 int random ; /* random value (scaled) */ 258 u_int32_t q_time ; /* start of queue idle time */ 259 260 /* WF2Q+ support */ 261 struct dn_flow_set *fs ; /* parent flow set */ 262 int heap_pos ; /* position (index) of struct in heap */ 263 dn_key sched_time ; /* current time when queue enters ready_heap */ 264 265 dn_key S,F ; /* start time, finish time */ 266 /* 267 * Setting F < S means the timestamp is invalid. We only need 268 * to test this when the queue is empty. 269 */ 270} ; 271 272/* 273 * flow_set descriptor. Contains the "template" parameters for the 274 * queue configuration, and pointers to the hash table of dn_flow_queue's. 275 * 276 * The hash table is an array of lists -- we identify the slot by 277 * hashing the flow-id, then scan the list looking for a match. 278 * The size of the hash table (buckets) is configurable on a per-queue 279 * basis. 280 * 281 * A dn_flow_set is created whenever a new queue or pipe is created (in the 282 * latter case, the structure is located inside the struct dn_pipe). 283 */ 284struct dn_flow_set { 285 struct dn_flow_set *next; /* next flow set in all_flow_sets list */ 286 287 u_short fs_nr ; /* flow_set number */ 288 u_short flags_fs; 289#define DN_HAVE_FLOW_MASK 0x0001 290#define DN_IS_RED 0x0002 291#define DN_IS_GENTLE_RED 0x0004 292#define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 293#define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 294#define DN_IS_PIPE 0x4000 295#define DN_IS_QUEUE 0x8000 296 297 struct dn_pipe *pipe ; /* pointer to parent pipe */ 298 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 299 300 int weight ; /* WFQ queue weight */ 301 int qsize ; /* queue size in slots or bytes */ 302 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 303 304 struct ipfw_flow_id flow_mask ; 305 306 /* hash table of queues onto this flow_set */ 307 int rq_size ; /* number of slots */ 308 int rq_elements ; /* active elements */ 309 struct dn_flow_queue **rq; /* array of rq_size entries */ 310 311 u_int32_t last_expired ; /* do not expire too frequently */ 312 int backlogged ; /* #active queues for this flowset */ 313 314 /* RED parameters */ 315#define SCALE_RED 16 316#define SCALE(x) ( (x) << SCALE_RED ) 317#define SCALE_VAL(x) ( (x) >> SCALE_RED ) 318#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 319 int w_q ; /* queue weight (scaled) */ 320 int max_th ; /* maximum threshold for queue (scaled) */ 321 int min_th ; /* minimum threshold for queue (scaled) */ 322 int max_p ; /* maximum value for p_b (scaled) */ 323 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 324 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 325 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 326 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 327 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 328 u_int lookup_depth ; /* depth of lookup table */ 329 int lookup_step ; /* granularity inside the lookup table */ 330 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 331 int avg_pkt_size ; /* medium packet size */ 332 int max_pkt_size ; /* max packet size */ 333} ; 334 335/* 336 * Pipe descriptor. Contains global parameters, delay-line queue, 337 * and the flow_set used for fixed-rate queues. 338 * 339 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 340 * not_eligible_heap, for queues whose start time is higher 341 * than the virtual time. Sorted by start time. 342 * scheduler_heap, for queues eligible for scheduling. Sorted by 343 * finish time. 344 * idle_heap, all flows that are idle and can be removed. We 345 * do that on each tick so we do not slow down too much 346 * operations during forwarding. 347 * 348 */ 349struct dn_pipe { /* a pipe */ 350 struct dn_pipe *next ; 351 352 int pipe_nr ; /* number */ 353 int bandwidth; /* really, bytes/tick. */ 354 int delay ; /* really, ticks */ 355 356 struct mbuf *head, *tail ; /* packets in delay line */ 357 358 /* WF2Q+ */ 359 struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ 360 struct dn_heap not_eligible_heap; /* top extract- key Start time */ 361 struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ 362 363 dn_key V ; /* virtual time */ 364 int sum; /* sum of weights of all active sessions */ 365 int numbytes; /* bits I can transmit (more or less). */ 366 367 dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 368 369 /* 370 * When the tx clock come from an interface (if_name[0] != '\0'), its name 371 * is stored below, whereas the ifp is filled when the rule is configured. 372 */ 373 char if_name[IFNAMSIZ]; 374 struct ifnet *ifp ; 375 int ready ; /* set if ifp != NULL and we got a signal from it */ 376 377 struct dn_flow_set fs ; /* used with fixed-rate flows */ 378}; 379 380#ifdef KERNEL 381 382void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */ 383 384typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ 385typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */ 386typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir, 387 struct ip_fw_args *fwa); 388extern ip_dn_ctl_t *ip_dn_ctl_ptr; 389extern ip_dn_ruledel_t *ip_dn_ruledel_ptr; 390extern ip_dn_io_t *ip_dn_io_ptr; 391#define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) 392 393/* 394 * Return the IPFW rule associated with the dummynet tag; if any. 395 * Make sure that the dummynet tag is not reused by lower layers. 396 */ 397static __inline struct ip_fw * 398ip_dn_claim_rule(struct mbuf *m) 399{ 400 struct m_tag *mtag = m_tag_locate(m, KERNEL_MODULE_TAG_ID, 401 KERNEL_TAG_TYPE_DUMMYNET, NULL); 402 if (mtag != NULL) { 403 mtag->m_tag_type = KERNEL_TAG_TYPE_NONE; 404 return (((struct dn_pkt_tag *)(mtag+1))->rule); 405 } else 406 return (NULL); 407} 408#endif /* KERNEL */ 409 410#endif /* PRIVATE */ 411#endif /* !__LP64__ */ 412#endif /* _IP_DUMMYNET_H */ 413