1 | /* |
2 | * Copyright (c) 2000-2013 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 | #include <sys/appleapiopts.h> |
61 | |
62 | #ifdef PRIVATE |
63 | #include <netinet/ip_flowid.h> |
64 | |
65 | /* Apply ipv6 mask on ipv6 addr */ |
66 | #define APPLY_MASK(addr,mask) \ |
67 | (addr)->__u6_addr.__u6_addr32[0] &= (mask)->__u6_addr.__u6_addr32[0]; \ |
68 | (addr)->__u6_addr.__u6_addr32[1] &= (mask)->__u6_addr.__u6_addr32[1]; \ |
69 | (addr)->__u6_addr.__u6_addr32[2] &= (mask)->__u6_addr.__u6_addr32[2]; \ |
70 | (addr)->__u6_addr.__u6_addr32[3] &= (mask)->__u6_addr.__u6_addr32[3]; |
71 | |
72 | /* |
73 | * Definition of dummynet data structures. In the structures, I decided |
74 | * not to use the macros in <sys/queue.h> in the hope of making the code |
75 | * easier to port to other architectures. The type of lists and queue we |
76 | * use here is pretty simple anyways. |
77 | */ |
78 | |
79 | /* |
80 | * We start with a heap, which is used in the scheduler to decide when |
81 | * to transmit packets etc. |
82 | * |
83 | * The key for the heap is used for two different values: |
84 | * |
85 | * 1. timer ticks- max 10K/second, so 32 bits are enough; |
86 | * |
87 | * 2. virtual times. These increase in steps of len/x, where len is the |
88 | * packet length, and x is either the weight of the flow, or the |
89 | * sum of all weights. |
90 | * If we limit to max 1000 flows and a max weight of 100, then |
91 | * x needs 17 bits. The packet size is 16 bits, so we can easily |
92 | * overflow if we do not allow errors. |
93 | * So we use a key "dn_key" which is 64 bits. Some macros are used to |
94 | * compare key values and handle wraparounds. |
95 | * MAX64 returns the largest of two key values. |
96 | * MY_M is used as a shift count when doing fixed point arithmetic |
97 | * (a better name would be useful...). |
98 | */ |
99 | typedef u_int64_t dn_key ; /* sorting key */ |
100 | #define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) |
101 | #define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) |
102 | #define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) |
103 | #define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) |
104 | #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) |
105 | #define MY_M 16 /* number of left shift to obtain a larger precision */ |
106 | |
107 | /* |
108 | * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the |
109 | * virtual time wraps every 15 days. |
110 | */ |
111 | |
112 | /* |
113 | * The OFFSET_OF macro is used to return the offset of a field within |
114 | * a structure. It is used by the heap management routines. |
115 | */ |
116 | #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) |
117 | |
118 | /* |
119 | * The maximum hash table size for queues. This value must be a power |
120 | * of 2. |
121 | */ |
122 | #define DN_MAX_HASH_SIZE 65536 |
123 | |
124 | /* |
125 | * A heap entry is made of a key and a pointer to the actual |
126 | * object stored in the heap. |
127 | * The heap is an array of dn_heap_entry entries, dynamically allocated. |
128 | * Current size is "size", with "elements" actually in use. |
129 | * The heap normally supports only ordered insert and extract from the top. |
130 | * If we want to extract an object from the middle of the heap, we |
131 | * have to know where the object itself is located in the heap (or we |
132 | * need to scan the whole array). To this purpose, an object has a |
133 | * field (int) which contains the index of the object itself into the |
134 | * heap. When the object is moved, the field must also be updated. |
135 | * The offset of the index in the object is stored in the 'offset' |
136 | * field in the heap descriptor. The assumption is that this offset |
137 | * is non-zero if we want to support extract from the middle. |
138 | */ |
139 | struct dn_heap_entry { |
140 | dn_key key ; /* sorting key. Topmost element is smallest one */ |
141 | void *object ; /* object pointer */ |
142 | } ; |
143 | |
144 | struct dn_heap { |
145 | int size ; |
146 | int elements ; |
147 | int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ |
148 | struct dn_heap_entry *p ; /* really an array of "size" entries */ |
149 | } ; |
150 | |
151 | /* |
152 | * Packets processed by dummynet have an mbuf tag associated with |
153 | * them that carries their dummynet state. This is used within |
154 | * the dummynet code as well as outside when checking for special |
155 | * processing requirements. |
156 | */ |
157 | #ifdef KERNEL |
158 | #include <net/if_var.h> |
159 | #include <net/route.h> |
160 | #include <netinet/ip_var.h> /* for ip_out_args */ |
161 | #include <netinet/ip6.h> /* for ip6_out_args */ |
162 | #include <netinet/in.h> |
163 | #include <netinet6/ip6_var.h> /* for ip6_out_args */ |
164 | |
165 | struct dn_pkt_tag { |
166 | struct ip_fw *dn_ipfw_rule; /* matching IPFW rule */ |
167 | void *dn_pf_rule; /* matching PF rule */ |
168 | int dn_dir; /* action when packet comes out. */ |
169 | #define DN_TO_IP_OUT 1 |
170 | #define DN_TO_IP_IN 2 |
171 | #define DN_TO_BDG_FWD 3 |
172 | #define DN_TO_IP6_IN 4 |
173 | #define DN_TO_IP6_OUT 5 |
174 | dn_key dn_output_time; /* when the pkt is due for delivery */ |
175 | struct ifnet *dn_ifp; /* interface, for ip[6]_output */ |
176 | union { |
177 | struct sockaddr_in _dn_dst; |
178 | struct sockaddr_in6 _dn_dst6 ; |
179 | } dn_dst_; |
180 | #define dn_dst dn_dst_._dn_dst |
181 | #define dn_dst6 dn_dst_._dn_dst6 |
182 | union { |
183 | struct route _dn_ro; /* route, for ip_output. MUST COPY */ |
184 | struct route_in6 _dn_ro6; /* route, for ip6_output. MUST COPY */ |
185 | } dn_ro_; |
186 | #define dn_ro dn_ro_._dn_ro |
187 | #define dn_ro6 dn_ro_._dn_ro6 |
188 | struct route_in6 dn_ro6_pmtu; /* for ip6_output */ |
189 | struct ifnet *dn_origifp; /* for ip6_output */ |
190 | u_int32_t dn_mtu; /* for ip6_output */ |
191 | int dn_alwaysfrag; /* for ip6_output */ |
192 | u_int32_t dn_unfragpartlen; /* for ip6_output */ |
193 | struct ip6_exthdrs dn_exthdrs; /* for ip6_output */ |
194 | int dn_flags ; /* flags, for ip[6]_output */ |
195 | int dn_client; |
196 | #define DN_CLIENT_IPFW 1 |
197 | #define DN_CLIENT_PF 2 |
198 | union { |
199 | struct ip_out_args _dn_ipoa; /* output args, for ip_output. MUST COPY */ |
200 | struct ip6_out_args _dn_ip6oa; /* output args, for ip_output. MUST COPY */ |
201 | } dn_ipoa_; |
202 | #define dn_ipoa dn_ipoa_._dn_ipoa |
203 | #define dn_ip6oa dn_ipoa_._dn_ip6oa |
204 | }; |
205 | #else |
206 | struct dn_pkt; |
207 | #endif /* KERNEL */ |
208 | |
209 | /* |
210 | * Overall structure of dummynet (with WF2Q+): |
211 | |
212 | In dummynet, packets are selected with the firewall rules, and passed |
213 | to two different objects: PIPE or QUEUE. |
214 | |
215 | A QUEUE is just a queue with configurable size and queue management |
216 | policy. It is also associated with a mask (to discriminate among |
217 | different flows), a weight (used to give different shares of the |
218 | bandwidth to different flows) and a "pipe", which essentially |
219 | supplies the transmit clock for all queues associated with that |
220 | pipe. |
221 | |
222 | A PIPE emulates a fixed-bandwidth link, whose bandwidth is |
223 | configurable. The "clock" for a pipe can come from either an |
224 | internal timer, or from the transmit interrupt of an interface. |
225 | A pipe is also associated with one (or more, if masks are used) |
226 | queue, where all packets for that pipe are stored. |
227 | |
228 | The bandwidth available on the pipe is shared by the queues |
229 | associated with that pipe (only one in case the packet is sent |
230 | to a PIPE) according to the WF2Q+ scheduling algorithm and the |
231 | configured weights. |
232 | |
233 | In general, incoming packets are stored in the appropriate queue, |
234 | which is then placed into one of a few heaps managed by a scheduler |
235 | to decide when the packet should be extracted. |
236 | The scheduler (a function called dummynet()) is run at every timer |
237 | tick, and grabs queues from the head of the heaps when they are |
238 | ready for processing. |
239 | |
240 | There are three data structures definining a pipe and associated queues: |
241 | |
242 | + dn_pipe, which contains the main configuration parameters related |
243 | to delay and bandwidth; |
244 | + dn_flow_set, which contains WF2Q+ configuration, flow |
245 | masks, plr and RED configuration; |
246 | + dn_flow_queue, which is the per-flow queue (containing the packets) |
247 | |
248 | Multiple dn_flow_set can be linked to the same pipe, and multiple |
249 | dn_flow_queue can be linked to the same dn_flow_set. |
250 | All data structures are linked in a linear list which is used for |
251 | housekeeping purposes. |
252 | |
253 | During configuration, we create and initialize the dn_flow_set |
254 | and dn_pipe structures (a dn_pipe also contains a dn_flow_set). |
255 | |
256 | At runtime: packets are sent to the appropriate dn_flow_set (either |
257 | WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), |
258 | which in turn dispatches them to the appropriate dn_flow_queue |
259 | (created dynamically according to the masks). |
260 | |
261 | The transmit clock for fixed rate flows (ready_event()) selects the |
262 | dn_flow_queue to be used to transmit the next packet. For WF2Q, |
263 | wfq_ready_event() extract a pipe which in turn selects the right |
264 | flow using a number of heaps defined into the pipe itself. |
265 | |
266 | * |
267 | */ |
268 | |
269 | /* |
270 | * per flow queue. This contains the flow identifier, the queue |
271 | * of packets, counters, and parameters used to support both RED and |
272 | * WF2Q+. |
273 | * |
274 | * A dn_flow_queue is created and initialized whenever a packet for |
275 | * a new flow arrives. |
276 | */ |
277 | struct dn_flow_queue { |
278 | struct dn_flow_queue *next ; |
279 | struct ip_flow_id id ; |
280 | |
281 | struct mbuf *head, *tail ; /* queue of packets */ |
282 | u_int len ; |
283 | u_int len_bytes ; |
284 | u_int32_t numbytes ; /* credit for transmission (dynamic queues) */ |
285 | |
286 | u_int64_t tot_pkts ; /* statistics counters */ |
287 | u_int64_t tot_bytes ; |
288 | u_int32_t drops ; |
289 | |
290 | int hash_slot ; /* debugging/diagnostic */ |
291 | |
292 | /* RED parameters */ |
293 | int avg ; /* average queue length est. (scaled) */ |
294 | int count ; /* arrivals since last RED drop */ |
295 | int random ; /* random value (scaled) */ |
296 | u_int32_t q_time ; /* start of queue idle time */ |
297 | |
298 | /* WF2Q+ support */ |
299 | struct dn_flow_set *fs ; /* parent flow set */ |
300 | int heap_pos ; /* position (index) of struct in heap */ |
301 | dn_key sched_time ; /* current time when queue enters ready_heap */ |
302 | |
303 | dn_key S,F ; /* start time, finish time */ |
304 | /* |
305 | * Setting F < S means the timestamp is invalid. We only need |
306 | * to test this when the queue is empty. |
307 | */ |
308 | } ; |
309 | |
310 | /* |
311 | * flow_set descriptor. Contains the "template" parameters for the |
312 | * queue configuration, and pointers to the hash table of dn_flow_queue's. |
313 | * |
314 | * The hash table is an array of lists -- we identify the slot by |
315 | * hashing the flow-id, then scan the list looking for a match. |
316 | * The size of the hash table (buckets) is configurable on a per-queue |
317 | * basis. |
318 | * |
319 | * A dn_flow_set is created whenever a new queue or pipe is created (in the |
320 | * latter case, the structure is located inside the struct dn_pipe). |
321 | */ |
322 | struct dn_flow_set { |
323 | SLIST_ENTRY(dn_flow_set) next; /* linked list in a hash slot */ |
324 | |
325 | u_short fs_nr ; /* flow_set number */ |
326 | u_short flags_fs; |
327 | #define DN_HAVE_FLOW_MASK 0x0001 |
328 | #define DN_IS_RED 0x0002 |
329 | #define DN_IS_GENTLE_RED 0x0004 |
330 | #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ |
331 | #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ |
332 | #define DN_IS_PIPE 0x4000 |
333 | #define DN_IS_QUEUE 0x8000 |
334 | |
335 | struct dn_pipe *pipe ; /* pointer to parent pipe */ |
336 | u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ |
337 | |
338 | int weight ; /* WFQ queue weight */ |
339 | int qsize ; /* queue size in slots or bytes */ |
340 | int plr ; /* pkt loss rate (2^31-1 means 100%) */ |
341 | |
342 | struct ip_flow_id flow_mask ; |
343 | |
344 | /* hash table of queues onto this flow_set */ |
345 | int rq_size ; /* number of slots */ |
346 | int rq_elements ; /* active elements */ |
347 | struct dn_flow_queue **rq; /* array of rq_size entries */ |
348 | |
349 | u_int32_t last_expired ; /* do not expire too frequently */ |
350 | int backlogged ; /* #active queues for this flowset */ |
351 | |
352 | /* RED parameters */ |
353 | #define SCALE_RED 16 |
354 | #define SCALE(x) ( (x) << SCALE_RED ) |
355 | #define SCALE_VAL(x) ( (x) >> SCALE_RED ) |
356 | #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) |
357 | int w_q ; /* queue weight (scaled) */ |
358 | int max_th ; /* maximum threshold for queue (scaled) */ |
359 | int min_th ; /* minimum threshold for queue (scaled) */ |
360 | int max_p ; /* maximum value for p_b (scaled) */ |
361 | u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ |
362 | u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ |
363 | u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ |
364 | u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ |
365 | u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ |
366 | u_int lookup_depth ; /* depth of lookup table */ |
367 | int lookup_step ; /* granularity inside the lookup table */ |
368 | int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ |
369 | int avg_pkt_size ; /* medium packet size */ |
370 | int max_pkt_size ; /* max packet size */ |
371 | } ; |
372 | |
373 | SLIST_HEAD(dn_flow_set_head, dn_flow_set); |
374 | |
375 | /* |
376 | * Pipe descriptor. Contains global parameters, delay-line queue, |
377 | * and the flow_set used for fixed-rate queues. |
378 | * |
379 | * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: |
380 | * not_eligible_heap, for queues whose start time is higher |
381 | * than the virtual time. Sorted by start time. |
382 | * scheduler_heap, for queues eligible for scheduling. Sorted by |
383 | * finish time. |
384 | * idle_heap, all flows that are idle and can be removed. We |
385 | * do that on each tick so we do not slow down too much |
386 | * operations during forwarding. |
387 | * |
388 | */ |
389 | struct dn_pipe { /* a pipe */ |
390 | SLIST_ENTRY(dn_pipe) next; /* linked list in a hash slot */ |
391 | |
392 | int pipe_nr ; /* number */ |
393 | int bandwidth; /* really, bytes/tick. */ |
394 | int delay ; /* really, ticks */ |
395 | |
396 | struct mbuf *head, *tail ; /* packets in delay line */ |
397 | |
398 | /* WF2Q+ */ |
399 | struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ |
400 | struct dn_heap not_eligible_heap; /* top extract- key Start time */ |
401 | struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ |
402 | |
403 | dn_key V ; /* virtual time */ |
404 | int sum; /* sum of weights of all active sessions */ |
405 | int numbytes; /* bits I can transmit (more or less). */ |
406 | |
407 | dn_key sched_time ; /* time pipe was scheduled in ready_heap */ |
408 | |
409 | /* |
410 | * When the tx clock come from an interface (if_name[0] != '\0'), its name |
411 | * is stored below, whereas the ifp is filled when the rule is configured. |
412 | */ |
413 | char if_name[IFNAMSIZ]; |
414 | struct ifnet *ifp ; |
415 | int ready ; /* set if ifp != NULL and we got a signal from it */ |
416 | |
417 | struct dn_flow_set fs ; /* used with fixed-rate flows */ |
418 | }; |
419 | |
420 | SLIST_HEAD(dn_pipe_head, dn_pipe); |
421 | |
422 | #ifdef BSD_KERNEL_PRIVATE |
423 | extern uint32_t my_random(void); |
424 | void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */ |
425 | |
426 | typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ |
427 | typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir, |
428 | struct ip_fw_args *fwa, int ); |
429 | extern ip_dn_ctl_t *ip_dn_ctl_ptr; |
430 | extern ip_dn_io_t *ip_dn_io_ptr; |
431 | void dn_ipfw_rule_delete(void *); |
432 | #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) |
433 | |
434 | #pragma pack(4) |
435 | |
436 | struct dn_heap_32 { |
437 | int size ; |
438 | int elements ; |
439 | int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ |
440 | user32_addr_t p ; /* really an array of "size" entries */ |
441 | } ; |
442 | |
443 | struct dn_flow_queue_32 { |
444 | user32_addr_t next ; |
445 | struct ip_flow_id id ; |
446 | |
447 | user32_addr_t head, tail ; /* queue of packets */ |
448 | u_int len ; |
449 | u_int len_bytes ; |
450 | u_int32_t numbytes ; /* credit for transmission (dynamic queues) */ |
451 | |
452 | u_int64_t tot_pkts ; /* statistics counters */ |
453 | u_int64_t tot_bytes ; |
454 | u_int32_t drops ; |
455 | |
456 | int hash_slot ; /* debugging/diagnostic */ |
457 | |
458 | /* RED parameters */ |
459 | int avg ; /* average queue length est. (scaled) */ |
460 | int count ; /* arrivals since last RED drop */ |
461 | int random ; /* random value (scaled) */ |
462 | u_int32_t q_time ; /* start of queue idle time */ |
463 | |
464 | /* WF2Q+ support */ |
465 | user32_addr_t fs ; /* parent flow set */ |
466 | int heap_pos ; /* position (index) of struct in heap */ |
467 | dn_key sched_time ; /* current time when queue enters ready_heap */ |
468 | |
469 | dn_key S,F ; /* start time, finish time */ |
470 | /* |
471 | * Setting F < S means the timestamp is invalid. We only need |
472 | * to test this when the queue is empty. |
473 | */ |
474 | } ; |
475 | |
476 | struct dn_flow_set_32 { |
477 | user32_addr_t next; /* next flow set in all_flow_sets list */ |
478 | |
479 | u_short fs_nr ; /* flow_set number */ |
480 | u_short flags_fs; |
481 | #define DN_HAVE_FLOW_MASK 0x0001 |
482 | #define DN_IS_RED 0x0002 |
483 | #define DN_IS_GENTLE_RED 0x0004 |
484 | #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ |
485 | #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ |
486 | #define DN_IS_PIPE 0x4000 |
487 | #define DN_IS_QUEUE 0x8000 |
488 | |
489 | user32_addr_t pipe ; /* pointer to parent pipe */ |
490 | u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ |
491 | |
492 | int weight ; /* WFQ queue weight */ |
493 | int qsize ; /* queue size in slots or bytes */ |
494 | int plr ; /* pkt loss rate (2^31-1 means 100%) */ |
495 | |
496 | struct ip_flow_id flow_mask ; |
497 | |
498 | /* hash table of queues onto this flow_set */ |
499 | int rq_size ; /* number of slots */ |
500 | int rq_elements ; /* active elements */ |
501 | user32_addr_t rq; /* array of rq_size entries */ |
502 | |
503 | u_int32_t last_expired ; /* do not expire too frequently */ |
504 | int backlogged ; /* #active queues for this flowset */ |
505 | |
506 | /* RED parameters */ |
507 | #define SCALE_RED 16 |
508 | #define SCALE(x) ( (x) << SCALE_RED ) |
509 | #define SCALE_VAL(x) ( (x) >> SCALE_RED ) |
510 | #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) |
511 | int w_q ; /* queue weight (scaled) */ |
512 | int max_th ; /* maximum threshold for queue (scaled) */ |
513 | int min_th ; /* minimum threshold for queue (scaled) */ |
514 | int max_p ; /* maximum value for p_b (scaled) */ |
515 | u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ |
516 | u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ |
517 | u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ |
518 | u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ |
519 | user32_addr_t w_q_lookup ; /* lookup table for computing (1-w_q)^t */ |
520 | u_int lookup_depth ; /* depth of lookup table */ |
521 | int lookup_step ; /* granularity inside the lookup table */ |
522 | int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ |
523 | int avg_pkt_size ; /* medium packet size */ |
524 | int max_pkt_size ; /* max packet size */ |
525 | } ; |
526 | |
527 | struct dn_pipe_32 { /* a pipe */ |
528 | user32_addr_t next ; |
529 | |
530 | int pipe_nr ; /* number */ |
531 | int bandwidth; /* really, bytes/tick. */ |
532 | int delay ; /* really, ticks */ |
533 | |
534 | user32_addr_t head, tail ; /* packets in delay line */ |
535 | |
536 | /* WF2Q+ */ |
537 | struct dn_heap_32 scheduler_heap ; /* top extract - key Finish time*/ |
538 | struct dn_heap_32 not_eligible_heap; /* top extract- key Start time */ |
539 | struct dn_heap_32 idle_heap ; /* random extract - key Start=Finish time */ |
540 | |
541 | dn_key V ; /* virtual time */ |
542 | int sum; /* sum of weights of all active sessions */ |
543 | int numbytes; /* bits I can transmit (more or less). */ |
544 | |
545 | dn_key sched_time ; /* time pipe was scheduled in ready_heap */ |
546 | |
547 | /* |
548 | * When the tx clock come from an interface (if_name[0] != '\0'), its name |
549 | * is stored below, whereas the ifp is filled when the rule is configured. |
550 | */ |
551 | char if_name[IFNAMSIZ]; |
552 | user32_addr_t ifp ; |
553 | int ready ; /* set if ifp != NULL and we got a signal from it */ |
554 | |
555 | struct dn_flow_set_32 fs ; /* used with fixed-rate flows */ |
556 | }; |
557 | #pragma pack() |
558 | |
559 | |
560 | struct dn_heap_64 { |
561 | int size ; |
562 | int elements ; |
563 | int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ |
564 | user64_addr_t p ; /* really an array of "size" entries */ |
565 | } ; |
566 | |
567 | |
568 | struct dn_flow_queue_64 { |
569 | user64_addr_t next ; |
570 | struct ip_flow_id id ; |
571 | |
572 | user64_addr_t head, tail ; /* queue of packets */ |
573 | u_int len ; |
574 | u_int len_bytes ; |
575 | u_int32_t numbytes ; /* credit for transmission (dynamic queues) */ |
576 | |
577 | u_int64_t tot_pkts ; /* statistics counters */ |
578 | u_int64_t tot_bytes ; |
579 | u_int32_t drops ; |
580 | |
581 | int hash_slot ; /* debugging/diagnostic */ |
582 | |
583 | /* RED parameters */ |
584 | int avg ; /* average queue length est. (scaled) */ |
585 | int count ; /* arrivals since last RED drop */ |
586 | int random ; /* random value (scaled) */ |
587 | u_int32_t q_time ; /* start of queue idle time */ |
588 | |
589 | /* WF2Q+ support */ |
590 | user64_addr_t fs ; /* parent flow set */ |
591 | int heap_pos ; /* position (index) of struct in heap */ |
592 | dn_key sched_time ; /* current time when queue enters ready_heap */ |
593 | |
594 | dn_key S,F ; /* start time, finish time */ |
595 | /* |
596 | * Setting F < S means the timestamp is invalid. We only need |
597 | * to test this when the queue is empty. |
598 | */ |
599 | } ; |
600 | |
601 | struct dn_flow_set_64 { |
602 | user64_addr_t next; /* next flow set in all_flow_sets list */ |
603 | |
604 | u_short fs_nr ; /* flow_set number */ |
605 | u_short flags_fs; |
606 | #define DN_HAVE_FLOW_MASK 0x0001 |
607 | #define DN_IS_RED 0x0002 |
608 | #define DN_IS_GENTLE_RED 0x0004 |
609 | #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ |
610 | #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ |
611 | #define DN_IS_PIPE 0x4000 |
612 | #define DN_IS_QUEUE 0x8000 |
613 | |
614 | user64_addr_t pipe ; /* pointer to parent pipe */ |
615 | u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ |
616 | |
617 | int weight ; /* WFQ queue weight */ |
618 | int qsize ; /* queue size in slots or bytes */ |
619 | int plr ; /* pkt loss rate (2^31-1 means 100%) */ |
620 | |
621 | struct ip_flow_id flow_mask ; |
622 | |
623 | /* hash table of queues onto this flow_set */ |
624 | int rq_size ; /* number of slots */ |
625 | int rq_elements ; /* active elements */ |
626 | user64_addr_t rq; /* array of rq_size entries */ |
627 | |
628 | u_int32_t last_expired ; /* do not expire too frequently */ |
629 | int backlogged ; /* #active queues for this flowset */ |
630 | |
631 | /* RED parameters */ |
632 | #define SCALE_RED 16 |
633 | #define SCALE(x) ( (x) << SCALE_RED ) |
634 | #define SCALE_VAL(x) ( (x) >> SCALE_RED ) |
635 | #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) |
636 | int w_q ; /* queue weight (scaled) */ |
637 | int max_th ; /* maximum threshold for queue (scaled) */ |
638 | int min_th ; /* minimum threshold for queue (scaled) */ |
639 | int max_p ; /* maximum value for p_b (scaled) */ |
640 | u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ |
641 | u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ |
642 | u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ |
643 | u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ |
644 | user64_addr_t w_q_lookup ; /* lookup table for computing (1-w_q)^t */ |
645 | u_int lookup_depth ; /* depth of lookup table */ |
646 | int lookup_step ; /* granularity inside the lookup table */ |
647 | int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ |
648 | int avg_pkt_size ; /* medium packet size */ |
649 | int max_pkt_size ; /* max packet size */ |
650 | } ; |
651 | |
652 | struct dn_pipe_64 { /* a pipe */ |
653 | user64_addr_t next ; |
654 | |
655 | int pipe_nr ; /* number */ |
656 | int bandwidth; /* really, bytes/tick. */ |
657 | int delay ; /* really, ticks */ |
658 | |
659 | user64_addr_t head, tail ; /* packets in delay line */ |
660 | |
661 | /* WF2Q+ */ |
662 | struct dn_heap_64 scheduler_heap ; /* top extract - key Finish time*/ |
663 | struct dn_heap_64 not_eligible_heap; /* top extract- key Start time */ |
664 | struct dn_heap_64 idle_heap ; /* random extract - key Start=Finish time */ |
665 | |
666 | dn_key V ; /* virtual time */ |
667 | int sum; /* sum of weights of all active sessions */ |
668 | int numbytes; /* bits I can transmit (more or less). */ |
669 | |
670 | dn_key sched_time ; /* time pipe was scheduled in ready_heap */ |
671 | |
672 | /* |
673 | * When the tx clock come from an interface (if_name[0] != '\0'), its name |
674 | * is stored below, whereas the ifp is filled when the rule is configured. |
675 | */ |
676 | char if_name[IFNAMSIZ]; |
677 | user64_addr_t ifp ; |
678 | int ready ; /* set if ifp != NULL and we got a signal from it */ |
679 | |
680 | struct dn_flow_set_64 fs ; /* used with fixed-rate flows */ |
681 | }; |
682 | |
683 | /* |
684 | * Return the IPFW rule associated with the dummynet tag; if any. |
685 | * Make sure that the dummynet tag is not reused by lower layers. |
686 | */ |
687 | static __inline struct ip_fw * |
688 | ip_dn_claim_rule(struct mbuf *m) |
689 | { |
690 | struct m_tag *mtag = m_tag_locate(m, KERNEL_MODULE_TAG_ID, |
691 | KERNEL_TAG_TYPE_DUMMYNET, NULL); |
692 | if (mtag != NULL) { |
693 | mtag->m_tag_type = KERNEL_TAG_TYPE_NONE; |
694 | return (((struct dn_pkt_tag *)(mtag+1))->dn_ipfw_rule); |
695 | } else |
696 | return (NULL); |
697 | } |
698 | |
699 | #include <sys/eventhandler.h> |
700 | /* Dummynet event handling declarations */ |
701 | extern struct eventhandler_lists_ctxt dummynet_evhdlr_ctxt; |
702 | extern void dummynet_init(void); |
703 | |
704 | struct dn_pipe_mini_config { |
705 | uint32_t bandwidth; |
706 | uint32_t delay; |
707 | uint32_t plr; |
708 | }; |
709 | |
710 | struct dn_rule_mini_config { |
711 | uint32_t dir; |
712 | uint32_t af; |
713 | uint32_t proto; |
714 | /* |
715 | * XXX PF rules actually define ranges of ports and |
716 | * along with range goes an opcode ((not) equal to, less than |
717 | * greater than, etc. |
718 | * For now the following works assuming there's no port range |
719 | * and the rule is for specific port. |
720 | * Also the operation is assumed as equal to. |
721 | */ |
722 | uint32_t src_port; |
723 | uint32_t dst_port; |
724 | char ifname[IFXNAMSIZ]; |
725 | }; |
726 | |
727 | struct dummynet_event { |
728 | uint32_t dn_event_code; |
729 | union { |
730 | struct dn_pipe_mini_config _dnev_pipe_config; |
731 | struct dn_rule_mini_config _dnev_rule_config; |
732 | } dn_event; |
733 | }; |
734 | |
735 | #define dn_event_pipe_config dn_event._dnev_pipe_config |
736 | #define dn_event_rule_config dn_event._dnev_rule_config |
737 | |
738 | extern void dummynet_event_enqueue_nwk_wq_entry(struct dummynet_event *); |
739 | |
740 | enum { |
741 | DUMMYNET_RULE_CONFIG, |
742 | DUMMYNET_RULE_DELETE, |
743 | DUMMYNET_PIPE_CONFIG, |
744 | DUMMYNET_PIPE_DELETE, |
745 | DUMMYNET_NLC_DISABLED, |
746 | }; |
747 | |
748 | enum { DN_INOUT, DN_IN, DN_OUT }; |
749 | /* |
750 | * The signature for the callback is: |
751 | * eventhandler_entry_arg __unused |
752 | * dummynet_event pointer to dummynet event object |
753 | */ |
754 | typedef void (*dummynet_event_fn) (struct eventhandler_entry_arg, struct dummynet_event *); |
755 | EVENTHANDLER_DECLARE(dummynet_event, dummynet_event_fn); |
756 | #endif /* BSD_KERNEL_PRIVATE */ |
757 | #endif /* PRIVATE */ |
758 | #endif /* _IP_DUMMYNET_H */ |
759 | |