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