Commit | Line | Data |
---|---|---|
1c79356b | 1 | /* |
5d5c5d0d A |
2 | * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. |
3 | * | |
2d21ac55 | 4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
1c79356b | 5 | * |
2d21ac55 A |
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. | |
8f6c56a5 | 14 | * |
2d21ac55 A |
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 | |
8f6c56a5 A |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, | |
2d21ac55 A |
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. | |
8f6c56a5 | 25 | * |
2d21ac55 | 26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
1c79356b A |
27 | */ |
28 | /* | |
91447636 A |
29 | * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa |
30 | * Portions Copyright (c) 2000 Akamba Corp. | |
31 | * All rights reserved | |
1c79356b | 32 | * |
91447636 A |
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. | |
1c79356b | 41 | * |
91447636 A |
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. | |
1c79356b | 53 | * |
91447636 | 54 | * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.32 2004/08/17 22:05:54 andre Exp $ |
1c79356b A |
55 | */ |
56 | ||
57 | #ifndef _IP_DUMMYNET_H | |
58 | #define _IP_DUMMYNET_H | |
2d21ac55 A |
59 | |
60 | #if !__LP64__ | |
61 | ||
9bccf70c | 62 | #include <sys/appleapiopts.h> |
1c79356b | 63 | |
91447636 | 64 | #ifdef PRIVATE |
1c79356b | 65 | /* |
9bccf70c A |
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. | |
1c79356b | 75 | * |
9bccf70c | 76 | * The key for the heap is used for two different values: |
1c79356b | 77 | * |
9bccf70c A |
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 | */ | |
92 | typedef 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 | ||
91447636 A |
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 | ||
9bccf70c A |
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 | */ | |
132 | struct dn_heap_entry { | |
133 | dn_key key ; /* sorting key. Topmost element is smallest one */ | |
134 | void *object ; /* object pointer */ | |
135 | } ; | |
136 | ||
137 | struct 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 | /* | |
91447636 A |
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. | |
1c79356b | 149 | */ |
91447636 A |
150 | #ifdef KERNEL |
151 | struct dn_pkt_tag { | |
152 | struct ip_fw *rule; /* matching rule */ | |
153 | int dn_dir; /* action when packet comes out. */ | |
9bccf70c A |
154 | #define DN_TO_IP_OUT 1 |
155 | #define DN_TO_IP_IN 2 | |
156 | #define DN_TO_BDG_FWD 3 | |
157 | ||
91447636 A |
158 | dn_key output_time; /* when the pkt is due for delivery */ |
159 | struct ifnet *ifp; /* interface, for ip_output */ | |
160 | struct sockaddr_in *dn_dst ; | |
161 | struct route ro; /* route, for ip_output. MUST COPY */ | |
162 | int flags ; /* flags, for ip_output (IPv6 ?) */ | |
1c79356b | 163 | }; |
91447636 A |
164 | #else |
165 | struct dn_pkt; | |
166 | #endif /* KERNEL */ | |
1c79356b | 167 | |
9bccf70c A |
168 | /* |
169 | * Overall structure of dummynet (with WF2Q+): | |
170 | ||
171 | In dummynet, packets are selected with the firewall rules, and passed | |
172 | to two different objects: PIPE or QUEUE. | |
173 | ||
174 | A QUEUE is just a queue with configurable size and queue management | |
175 | policy. It is also associated with a mask (to discriminate among | |
176 | different flows), a weight (used to give different shares of the | |
177 | bandwidth to different flows) and a "pipe", which essentially | |
178 | supplies the transmit clock for all queues associated with that | |
179 | pipe. | |
180 | ||
181 | A PIPE emulates a fixed-bandwidth link, whose bandwidth is | |
182 | configurable. The "clock" for a pipe can come from either an | |
183 | internal timer, or from the transmit interrupt of an interface. | |
184 | A pipe is also associated with one (or more, if masks are used) | |
185 | queue, where all packets for that pipe are stored. | |
186 | ||
187 | The bandwidth available on the pipe is shared by the queues | |
188 | associated with that pipe (only one in case the packet is sent | |
189 | to a PIPE) according to the WF2Q+ scheduling algorithm and the | |
190 | configured weights. | |
191 | ||
192 | In general, incoming packets are stored in the appropriate queue, | |
193 | which is then placed into one of a few heaps managed by a scheduler | |
194 | to decide when the packet should be extracted. | |
195 | The scheduler (a function called dummynet()) is run at every timer | |
196 | tick, and grabs queues from the head of the heaps when they are | |
197 | ready for processing. | |
198 | ||
199 | There are three data structures definining a pipe and associated queues: | |
200 | ||
201 | + dn_pipe, which contains the main configuration parameters related | |
202 | to delay and bandwidth; | |
203 | + dn_flow_set, which contains WF2Q+ configuration, flow | |
204 | masks, plr and RED configuration; | |
205 | + dn_flow_queue, which is the per-flow queue (containing the packets) | |
206 | ||
207 | Multiple dn_flow_set can be linked to the same pipe, and multiple | |
208 | dn_flow_queue can be linked to the same dn_flow_set. | |
209 | All data structures are linked in a linear list which is used for | |
210 | housekeeping purposes. | |
211 | ||
212 | During configuration, we create and initialize the dn_flow_set | |
213 | and dn_pipe structures (a dn_pipe also contains a dn_flow_set). | |
214 | ||
215 | At runtime: packets are sent to the appropriate dn_flow_set (either | |
216 | WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), | |
217 | which in turn dispatches them to the appropriate dn_flow_queue | |
218 | (created dynamically according to the masks). | |
219 | ||
220 | The transmit clock for fixed rate flows (ready_event()) selects the | |
221 | dn_flow_queue to be used to transmit the next packet. For WF2Q, | |
222 | wfq_ready_event() extract a pipe which in turn selects the right | |
223 | flow using a number of heaps defined into the pipe itself. | |
224 | ||
225 | * | |
226 | */ | |
227 | ||
228 | /* | |
229 | * per flow queue. This contains the flow identifier, the queue | |
230 | * of packets, counters, and parameters used to support both RED and | |
231 | * WF2Q+. | |
91447636 A |
232 | * |
233 | * A dn_flow_queue is created and initialized whenever a packet for | |
234 | * a new flow arrives. | |
9bccf70c A |
235 | */ |
236 | struct dn_flow_queue { | |
237 | struct dn_flow_queue *next ; | |
238 | struct ipfw_flow_id id ; | |
91447636 A |
239 | |
240 | struct mbuf *head, *tail ; /* queue of packets */ | |
9bccf70c A |
241 | u_int len ; |
242 | u_int len_bytes ; | |
91447636 | 243 | u_long numbytes ; /* credit for transmission (dynamic queues) */ |
9bccf70c A |
244 | |
245 | u_int64_t tot_pkts ; /* statistics counters */ | |
246 | u_int64_t tot_bytes ; | |
247 | u_int32_t drops ; | |
91447636 A |
248 | |
249 | int hash_slot ; /* debugging/diagnostic */ | |
9bccf70c A |
250 | |
251 | /* RED parameters */ | |
252 | int avg ; /* average queue length est. (scaled) */ | |
253 | int count ; /* arrivals since last RED drop */ | |
254 | int random ; /* random value (scaled) */ | |
255 | u_int32_t q_time ; /* start of queue idle time */ | |
256 | ||
257 | /* WF2Q+ support */ | |
91447636 A |
258 | struct dn_flow_set *fs ; /* parent flow set */ |
259 | int heap_pos ; /* position (index) of struct in heap */ | |
260 | dn_key sched_time ; /* current time when queue enters ready_heap */ | |
9bccf70c | 261 | |
91447636 A |
262 | dn_key S,F ; /* start time, finish time */ |
263 | /* | |
264 | * Setting F < S means the timestamp is invalid. We only need | |
9bccf70c A |
265 | * to test this when the queue is empty. |
266 | */ | |
1c79356b A |
267 | } ; |
268 | ||
269 | /* | |
9bccf70c A |
270 | * flow_set descriptor. Contains the "template" parameters for the |
271 | * queue configuration, and pointers to the hash table of dn_flow_queue's. | |
272 | * | |
273 | * The hash table is an array of lists -- we identify the slot by | |
274 | * hashing the flow-id, then scan the list looking for a match. | |
275 | * The size of the hash table (buckets) is configurable on a per-queue | |
276 | * basis. | |
91447636 A |
277 | * |
278 | * A dn_flow_set is created whenever a new queue or pipe is created (in the | |
279 | * latter case, the structure is located inside the struct dn_pipe). | |
9bccf70c A |
280 | */ |
281 | struct dn_flow_set { | |
282 | struct dn_flow_set *next; /* next flow set in all_flow_sets list */ | |
283 | ||
284 | u_short fs_nr ; /* flow_set number */ | |
285 | u_short flags_fs; | |
286 | #define DN_HAVE_FLOW_MASK 0x0001 | |
9bccf70c A |
287 | #define DN_IS_RED 0x0002 |
288 | #define DN_IS_GENTLE_RED 0x0004 | |
91447636 A |
289 | #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ |
290 | #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ | |
291 | #define DN_IS_PIPE 0x4000 | |
292 | #define DN_IS_QUEUE 0x8000 | |
9bccf70c | 293 | |
91447636 | 294 | struct dn_pipe *pipe ; /* pointer to parent pipe */ |
9bccf70c A |
295 | u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ |
296 | ||
91447636 A |
297 | int weight ; /* WFQ queue weight */ |
298 | int qsize ; /* queue size in slots or bytes */ | |
299 | int plr ; /* pkt loss rate (2^31-1 means 100%) */ | |
9bccf70c A |
300 | |
301 | struct ipfw_flow_id flow_mask ; | |
91447636 | 302 | |
9bccf70c A |
303 | /* hash table of queues onto this flow_set */ |
304 | int rq_size ; /* number of slots */ | |
305 | int rq_elements ; /* active elements */ | |
306 | struct dn_flow_queue **rq; /* array of rq_size entries */ | |
91447636 | 307 | |
9bccf70c | 308 | u_int32_t last_expired ; /* do not expire too frequently */ |
9bccf70c A |
309 | int backlogged ; /* #active queues for this flowset */ |
310 | ||
311 | /* RED parameters */ | |
312 | #define SCALE_RED 16 | |
313 | #define SCALE(x) ( (x) << SCALE_RED ) | |
314 | #define SCALE_VAL(x) ( (x) >> SCALE_RED ) | |
315 | #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) | |
91447636 A |
316 | int w_q ; /* queue weight (scaled) */ |
317 | int max_th ; /* maximum threshold for queue (scaled) */ | |
318 | int min_th ; /* minimum threshold for queue (scaled) */ | |
319 | int max_p ; /* maximum value for p_b (scaled) */ | |
320 | u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ | |
321 | u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ | |
322 | u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ | |
323 | u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ | |
324 | u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ | |
325 | u_int lookup_depth ; /* depth of lookup table */ | |
326 | int lookup_step ; /* granularity inside the lookup table */ | |
327 | int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ | |
328 | int avg_pkt_size ; /* medium packet size */ | |
329 | int max_pkt_size ; /* max packet size */ | |
9bccf70c A |
330 | } ; |
331 | ||
332 | /* | |
333 | * Pipe descriptor. Contains global parameters, delay-line queue, | |
334 | * and the flow_set used for fixed-rate queues. | |
91447636 A |
335 | * |
336 | * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: | |
9bccf70c A |
337 | * not_eligible_heap, for queues whose start time is higher |
338 | * than the virtual time. Sorted by start time. | |
339 | * scheduler_heap, for queues eligible for scheduling. Sorted by | |
340 | * finish time. | |
9bccf70c A |
341 | * idle_heap, all flows that are idle and can be removed. We |
342 | * do that on each tick so we do not slow down too much | |
343 | * operations during forwarding. | |
344 | * | |
1c79356b | 345 | */ |
91447636 A |
346 | struct dn_pipe { /* a pipe */ |
347 | struct dn_pipe *next ; | |
1c79356b | 348 | |
9bccf70c | 349 | int pipe_nr ; /* number */ |
91447636 A |
350 | int bandwidth; /* really, bytes/tick. */ |
351 | int delay ; /* really, ticks */ | |
1c79356b | 352 | |
91447636 | 353 | struct mbuf *head, *tail ; /* packets in delay line */ |
1c79356b | 354 | |
9bccf70c A |
355 | /* WF2Q+ */ |
356 | struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ | |
357 | struct dn_heap not_eligible_heap; /* top extract- key Start time */ | |
358 | struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ | |
359 | ||
91447636 A |
360 | dn_key V ; /* virtual time */ |
361 | int sum; /* sum of weights of all active sessions */ | |
362 | int numbytes; /* bits I can transmit (more or less). */ | |
9bccf70c | 363 | |
91447636 | 364 | dn_key sched_time ; /* time pipe was scheduled in ready_heap */ |
1c79356b | 365 | |
91447636 A |
366 | /* |
367 | * When the tx clock come from an interface (if_name[0] != '\0'), its name | |
368 | * is stored below, whereas the ifp is filled when the rule is configured. | |
9bccf70c | 369 | */ |
91447636 | 370 | char if_name[IFNAMSIZ]; |
9bccf70c A |
371 | struct ifnet *ifp ; |
372 | int ready ; /* set if ifp != NULL and we got a signal from it */ | |
373 | ||
374 | struct dn_flow_set fs ; /* used with fixed-rate flows */ | |
375 | }; | |
376 | ||
377 | #ifdef KERNEL | |
1c79356b | 378 | |
91447636 | 379 | void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */ |
1c79356b | 380 | |
91447636 A |
381 | typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ |
382 | typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */ | |
383 | typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir, | |
384 | struct ip_fw_args *fwa); | |
385 | extern ip_dn_ctl_t *ip_dn_ctl_ptr; | |
386 | extern ip_dn_ruledel_t *ip_dn_ruledel_ptr; | |
387 | extern ip_dn_io_t *ip_dn_io_ptr; | |
388 | #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) | |
1c79356b | 389 | |
91447636 A |
390 | /* |
391 | * Return the IPFW rule associated with the dummynet tag; if any. | |
392 | * Make sure that the dummynet tag is not reused by lower layers. | |
393 | */ | |
394 | static __inline struct ip_fw * | |
395 | ip_dn_claim_rule(struct mbuf *m) | |
396 | { | |
397 | struct m_tag *mtag = m_tag_locate(m, KERNEL_MODULE_TAG_ID, | |
398 | KERNEL_TAG_TYPE_DUMMYNET, NULL); | |
399 | if (mtag != NULL) { | |
400 | mtag->m_tag_type = KERNEL_TAG_TYPE_NONE; | |
401 | return (((struct dn_pkt_tag *)(mtag+1))->rule); | |
402 | } else | |
403 | return (NULL); | |
404 | } | |
405 | #endif /* KERNEL */ | |
406 | ||
407 | #endif /* PRIVATE */ | |
2d21ac55 | 408 | #endif /* !__LP64__ */ |
1c79356b | 409 | #endif /* _IP_DUMMYNET_H */ |