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 */
99typedef 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 */
133struct dn_heap_entry {
134 dn_key key; /* sorting key. Topmost element is smallest one */
135 void *object; /* object pointer */
136};
137
138struct 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
159struct 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
195struct 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 */
266struct 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 */
311struct 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
362SLIST_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 */
378struct 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
409SLIST_HEAD(dn_pipe_head, dn_pipe);
410
411#ifdef BSD_KERNEL_PRIVATE
412extern uint32_t my_random(void);
413void ip_dn_init(void);
414
415typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
416typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
417 struct ip_fw_args *fwa);
418extern ip_dn_ctl_t *ip_dn_ctl_ptr;
419extern ip_dn_io_t *ip_dn_io_ptr;
420#define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
421
422#pragma pack(4)
423
424struct 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
431struct 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
464struct 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
515struct 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
548struct 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
556struct 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
589struct 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
640struct 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 */
673extern struct eventhandler_lists_ctxt dummynet_evhdlr_ctxt;
674extern void dummynet_init(void);
675
676extern void dummynet_register_m_tag(void);
677
678struct dn_pipe_mini_config {
679 uint32_t bandwidth;
680 uint32_t delay;
681 uint32_t plr;
682};
683
684struct 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
701struct 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
712extern void dummynet_event_enqueue_nwk_wq_entry(struct dummynet_event *);
713
714enum {
715 DUMMYNET_RULE_CONFIG,
716 DUMMYNET_RULE_DELETE,
717 DUMMYNET_PIPE_CONFIG,
718 DUMMYNET_PIPE_DELETE,
719 DUMMYNET_NLC_DISABLED,
720};
721
722enum { 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 */
728typedef void (*dummynet_event_fn) (struct eventhandler_entry_arg, struct dummynet_event *);
729EVENTHANDLER_DECLARE(dummynet_event, dummynet_event_fn);
730#endif /* BSD_KERNEL_PRIVATE */
731#endif /* PRIVATE */
732#endif /* _IP_DUMMYNET_H */
733