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 */
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 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 */
139struct dn_heap_entry {
140 dn_key key ; /* sorting key. Topmost element is smallest one */
141 void *object ; /* object pointer */
142} ;
143
144struct 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
165struct 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
206struct dn_pkt;
207#endif /* KERNEL */
208
209/*
210 * Overall structure of dummynet (with WF2Q+):
211
212In dummynet, packets are selected with the firewall rules, and passed
213to two different objects: PIPE or QUEUE.
214
215A QUEUE is just a queue with configurable size and queue management
216policy. It is also associated with a mask (to discriminate among
217different flows), a weight (used to give different shares of the
218bandwidth to different flows) and a "pipe", which essentially
219supplies the transmit clock for all queues associated with that
220pipe.
221
222A PIPE emulates a fixed-bandwidth link, whose bandwidth is
223configurable. The "clock" for a pipe can come from either an
224internal timer, or from the transmit interrupt of an interface.
225A pipe is also associated with one (or more, if masks are used)
226queue, where all packets for that pipe are stored.
227
228The bandwidth available on the pipe is shared by the queues
229associated with that pipe (only one in case the packet is sent
230to a PIPE) according to the WF2Q+ scheduling algorithm and the
231configured weights.
232
233In general, incoming packets are stored in the appropriate queue,
234which is then placed into one of a few heaps managed by a scheduler
235to decide when the packet should be extracted.
236The scheduler (a function called dummynet()) is run at every timer
237tick, and grabs queues from the head of the heaps when they are
238ready for processing.
239
240There 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
248Multiple dn_flow_set can be linked to the same pipe, and multiple
249dn_flow_queue can be linked to the same dn_flow_set.
250All data structures are linked in a linear list which is used for
251housekeeping purposes.
252
253During configuration, we create and initialize the dn_flow_set
254and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
255
256At runtime: packets are sent to the appropriate dn_flow_set (either
257WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
258which in turn dispatches them to the appropriate dn_flow_queue
259(created dynamically according to the masks).
260
261The transmit clock for fixed rate flows (ready_event()) selects the
262dn_flow_queue to be used to transmit the next packet. For WF2Q,
263wfq_ready_event() extract a pipe which in turn selects the right
264flow 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 */
277struct 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 */
322struct 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
373SLIST_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 */
389struct 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
420SLIST_HEAD(dn_pipe_head, dn_pipe);
421
422#ifdef BSD_KERNEL_PRIVATE
423extern uint32_t my_random(void);
424void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */
425
426typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
427typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
428 struct ip_fw_args *fwa, int );
429extern ip_dn_ctl_t *ip_dn_ctl_ptr;
430extern ip_dn_io_t *ip_dn_io_ptr;
431void dn_ipfw_rule_delete(void *);
432#define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
433
434#pragma pack(4)
435
436struct 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
443struct 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
476struct 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
527struct 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
560struct 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
568struct 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
601struct 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
652struct 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 */
687static __inline struct ip_fw *
688ip_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 */
701extern struct eventhandler_lists_ctxt dummynet_evhdlr_ctxt;
702extern void dummynet_init(void);
703
704struct dn_pipe_mini_config {
705 uint32_t bandwidth;
706 uint32_t delay;
707 uint32_t plr;
708};
709
710struct 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
727struct 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
738extern void dummynet_event_enqueue_nwk_wq_entry(struct dummynet_event *);
739
740enum {
741 DUMMYNET_RULE_CONFIG,
742 DUMMYNET_RULE_DELETE,
743 DUMMYNET_PIPE_CONFIG,
744 DUMMYNET_PIPE_DELETE,
745 DUMMYNET_NLC_DISABLED,
746};
747
748enum { 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 */
754typedef void (*dummynet_event_fn) (struct eventhandler_entry_arg, struct dummynet_event *);
755EVENTHANDLER_DECLARE(dummynet_event, dummynet_event_fn);
756#endif /* BSD_KERNEL_PRIVATE */
757#endif /* PRIVATE */
758#endif /* _IP_DUMMYNET_H */
759