2 * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
3 * Portions Copyright (c) 2000 Akamba Corp.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.10.2.9 2003/05/13 09:31:06 maxim Exp $
28 * $DragonFly: src/sys/net/dummynet/ip_dummynet.h,v 1.19 2008/09/20 04:36:51 sephe Exp $
31 #ifndef _IP_DUMMYNET_H
32 #define _IP_DUMMYNET_H
35 * We start with a heap, which is used in the scheduler to decide when to
36 * transmit packets etc.
38 * The key for the heap is used for two different values:
40 * 1. Timer ticks- max 10K/second, so 32 bits are enough;
42 * 2. Virtual times. These increase in steps of len/x, where len is the
43 * packet length, and x is either the weight of the flow, or the sum
45 * If we limit to max 1000 flows and a max weight of 100, then x needs
46 * 17 bits. The packet size is 16 bits, so we can easily overflow if
47 * we do not allow errors.
49 * So we use a key "dn_key" which is 64 bits.
51 * MY_M is used as a shift count when doing fixed point arithmetic
52 * (a better name would be useful...).
54 typedef uint64_t dn_key
; /* sorting key */
57 * Number of left shift to obtain a larger precision
59 * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
60 * virtual time wraps every 15 days.
67 * A heap entry is made of a key and a pointer to the actual object stored
70 * The heap is an array of dn_heap_entry entries, dynamically allocated.
71 * Current size is "size", with "elements" actually in use.
73 * The heap normally supports only ordered insert and extract from the top.
74 * If we want to extract an object from the middle of the heap, we have to
75 * know where the object itself is located in the heap (or we need to scan
76 * the whole array). To this purpose, an object has a field (int) which
77 * contains the index of the object itself into the heap. When the object
78 * is moved, the field must also be updated. The offset of the index in the
79 * object is stored in the 'offset' field in the heap descriptor. The
80 * assumption is that this offset is non-zero if we want to support extract
83 struct dn_heap_entry
{
84 dn_key key
; /* sorting key. Topmost element is smallest one */
85 void *object
; /* object pointer */
91 int offset
; /* XXX if > 0 this is the offset of direct ptr to obj */
92 struct dn_heap_entry
*p
; /* really an array of "size" entries */
96 uint16_t fid_type
; /* ETHERTYPE_ */
108 #define fid_dst_ip fid_u.inet.dst_ip
109 #define fid_src_ip fid_u.inet.src_ip
110 #define fid_dst_port fid_u.inet.dst_port
111 #define fid_src_port fid_u.inet.src_port
112 #define fid_proto fid_u.inet.proto
113 #define fid_flags fid_u.inet.flags
116 typedef void (*ip_dn_unref_priv_t
)(void *);
120 * struct dn_pkt identifies a packet in the dummynet queue, but is also used
121 * to tag packets passed back to the various destinations (ip_input(),
122 * ip_output() and so on).
124 * It is a tag (PACKET_TAG_DUMMYNET) associated with the actual mbuf.
128 TAILQ_ENTRY(dn_pkt
) dn_next
;
131 ip_dn_unref_priv_t dn_unref_priv
;
133 uint32_t dn_flags
; /* action when packet comes out. */
134 #define DN_FLAGS_IS_PIPE 0x10
135 #define DN_FLAGS_DIR_MASK 0x0f
136 #define DN_TO_IP_OUT 1
137 #define DN_TO_IP_IN 2
138 #define DN_TO_ETH_DEMUX 4
139 #define DN_TO_ETH_OUT 5
142 dn_key output_time
; /* when the pkt is due for delivery */
143 struct ifnet
*ifp
; /* interface, for ip_output */
144 struct sockaddr_in
*dn_dst
;
145 struct route ro
; /* route, for ip_output. MUST COPY */
146 int flags
; /* flags, for ip_output (IPv6 ?) */
148 u_short pipe_nr
; /* pipe/flow_set number */
151 struct dn_flow_id id
; /* flow id */
152 int cpuid
; /* target cpuid, for assertion */
153 struct lwkt_port
*msgport
; /* target msgport */
155 TAILQ_HEAD(dn_pkt_queue
, dn_pkt
);
158 * Overall structure of dummynet (with WF2Q+):
160 * In dummynet, packets are selected with the firewall rules, and passed to
161 * two different objects: PIPE or QUEUE.
163 * A QUEUE is just a queue with configurable size and queue management policy.
164 * It is also associated with a mask (to discriminate among different flows),
165 * a weight (used to give different shares of the bandwidth to different flows)
166 * and a "pipe", which essentially supplies the transmit clock for all queues
167 * associated with that pipe.
169 * A PIPE emulates a fixed-bandwidth link, whose bandwidth is configurable.
170 * The "clock" for a pipe comes from an internal timer. A pipe is also
171 * associated with one (or more, if masks are used) queue, where all packets
172 * for that pipe are stored.
174 * The bandwidth available on the pipe is shared by the queues associated with
175 * that pipe (only one in case the packet is sent to a PIPE) according to the
176 * WF2Q+ scheduling algorithm and the configured weights.
178 * In general, incoming packets are stored in the appropriate queue, which is
179 * then placed into one of a few heaps managed by a scheduler to decide when
180 * the packet should be extracted. The scheduler (a function called dummynet())
181 * is run at every timer tick, and grabs queues from the head of the heaps when
182 * they are ready for processing.
184 * There are three data structures definining a pipe and associated queues:
186 * + dn_pipe, which contains the main configuration parameters related to
187 * delay and bandwidth;
188 * + dn_flow_set, which contains WF2Q+ configuration, flow masks, plr and
190 * + dn_flow_queue, which is the per-flow queue (containing the packets)
192 * Multiple dn_flow_set can be linked to the same pipe, and multiple
193 * dn_flow_queue can be linked to the same dn_flow_set.
194 * All data structures are linked in a linear list which is used for
195 * housekeeping purposes.
197 * During configuration, we create and initialize the dn_flow_set and dn_pipe
198 * structures (a dn_pipe also contains a dn_flow_set).
200 * At runtime: packets are sent to the appropriate dn_flow_set (either WFQ
201 * ones, or the one embedded in the dn_pipe for fixed-rate flows), which in
202 * turn dispatches them to the appropriate dn_flow_queue (created dynamically
203 * according to the masks).
205 * The transmit clock for fixed rate flows (ready_event()) selects the
206 * dn_flow_queue to be used to transmit the next packet. For WF2Q,
207 * wfq_ready_event() extract a pipe which in turn selects the right flow using
208 * a number of heaps defined into the pipe itself.
212 * Per flow queue. This contains the flow identifier, the queue of packets,
213 * counters, and parameters used to support both RED and WF2Q+.
215 * A dn_flow_queue is created and initialized whenever a packet for a new
218 struct dn_flow_queue
{
219 struct dn_flow_id id
;
220 LIST_ENTRY(dn_flow_queue
) q_link
;
222 struct dn_pkt_queue queue
; /* queue of packets */
225 u_long numbytes
; /* credit for transmission (dynamic queues) */
227 uint64_t tot_pkts
; /* statistics counters */
231 int hash_slot
; /* debugging/diagnostic */
234 int avg
; /* average queue length est. (scaled) */
235 int count
; /* arrivals since last RED drop */
236 int random
; /* random value (scaled) */
237 uint32_t q_time
; /* start of queue idle time */
240 struct dn_flow_set
*fs
; /* parent flow set */
241 int heap_pos
; /* position (index) of struct in heap */
242 dn_key sched_time
; /* current time when queue enters ready_heap */
244 dn_key S
, F
; /* start time, finish time */
246 * Setting F < S means the timestamp is invalid. We only need
247 * to test this when the queue is empty.
250 LIST_HEAD(dn_flowqueue_head
, dn_flow_queue
);
253 * flow_set descriptor. Contains the "template" parameters for the queue
254 * configuration, and pointers to the hash table of dn_flow_queue's.
256 * The hash table is an array of lists -- we identify the slot by hashing
257 * the flow-id, then scan the list looking for a match.
258 * The size of the hash table (buckets) is configurable on a per-queue basis.
260 * A dn_flow_set is created whenever a new queue or pipe is created (in the
261 * latter case, the structure is located inside the struct dn_pipe).
264 u_short fs_nr
; /* flow_set number */
265 u_short flags_fs
; /* see 'Flow set flags' */
267 LIST_ENTRY(dn_flow_set
) fs_link
;
269 struct dn_pipe
*pipe
; /* pointer to parent pipe */
270 u_short parent_nr
; /* parent pipe#, 0 if local to a pipe */
272 int weight
; /* WFQ queue weight */
273 int qsize
; /* queue size in slots or bytes */
274 int plr
; /* pkt loss rate (2^31-1 means 100%) */
276 struct dn_flow_id flow_mask
;
278 /* hash table of queues onto this flow_set */
279 int rq_size
; /* number of slots */
280 int rq_elements
; /* active elements */
281 struct dn_flowqueue_head
*rq
;/* array of rq_size entries */
283 uint32_t last_expired
; /* do not expire too frequently */
284 int backlogged
; /* #active queues for this flowset */
287 int w_q
; /* queue weight (scaled) */
288 int max_th
; /* maximum threshold for queue (scaled) */
289 int min_th
; /* minimum threshold for queue (scaled) */
290 int max_p
; /* maximum value for p_b (scaled) */
291 u_int c_1
; /* max_p/(max_th-min_th) (scaled) */
292 u_int c_2
; /* max_p*min_th/(max_th-min_th) (scaled) */
293 u_int c_3
; /* for GRED, (1-max_p)/max_th (scaled) */
294 u_int c_4
; /* for GRED, 1 - 2*max_p (scaled) */
295 u_int
*w_q_lookup
; /* lookup table for computing (1-w_q)^t */
296 u_int lookup_depth
; /* depth of lookup table */
297 int lookup_step
; /* granularity inside the lookup table */
298 int lookup_weight
; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
299 int avg_pkt_size
; /* medium packet size */
300 int max_pkt_size
; /* max packet size */
302 LIST_HEAD(dn_flowset_head
, dn_flow_set
);
305 * Pipe descriptor. Contains global parameters, delay-line queue, and the
306 * flow_set used for fixed-rate queues.
308 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
309 * + not_eligible_heap, for queues whose start time is higher than the
310 * virtual time. Sorted by start time.
311 * + scheduler_heap, for queues eligible for scheduling. Sorted by finish
313 * + idle_heap, all flows that are idle and can be removed. We do that on
314 * each tick so we do not slow down too much operations during forwarding.
316 struct dn_pipe
{ /* a pipe */
317 int pipe_nr
; /* number */
318 int bandwidth
; /* really, bytes/tick. */
319 int delay
; /* really, ticks */
321 struct dn_pkt_queue p_queue
;/* packets in delay line */
322 LIST_ENTRY(dn_pipe
) p_link
;
325 struct dn_heap scheduler_heap
; /* top extract - key Finish time*/
326 struct dn_heap not_eligible_heap
; /* top extract- key Start time */
327 struct dn_heap idle_heap
; /* random extract - key Start=Finish time */
329 dn_key V
; /* virtual time */
330 int sum
; /* sum of weights of all active sessions */
331 int numbytes
; /* bits I can transmit (more or less). */
333 dn_key sched_time
; /* time pipe was scheduled in ready_heap */
335 struct dn_flow_set fs
; /* used with fixed-rate flows */
337 LIST_HEAD(dn_pipe_head
, dn_pipe
);
342 size_t dn_sopt_arglen
;
345 typedef int ip_dn_ctl_t(struct dn_sopt
*);
346 typedef int ip_dn_io_t(struct mbuf
*);
348 extern ip_dn_ctl_t
*ip_dn_ctl_ptr
;
349 extern ip_dn_io_t
*ip_dn_io_ptr
;
351 void ip_dn_queue(struct mbuf
*);
352 void ip_dn_packet_free(struct dn_pkt
*);
353 void ip_dn_packet_redispatch(struct dn_pkt
*);
354 int ip_dn_sockopt(struct sockopt
*);
356 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
360 struct dn_ioc_flowid
{
361 uint16_t type
; /* ETHERTYPE_ */
376 struct dn_ioc_flowqueue
{
384 int hash_slot
; /* debugging/diagnostic */
385 dn_key S
; /* virtual start time */
386 dn_key F
; /* virtual finish time */
388 struct dn_ioc_flowid id
;
389 uint8_t reserved
[16];
392 struct dn_ioc_flowset
{
393 u_short fs_type
; /* DN_IS_{QUEUE,PIPE}, MUST be first */
395 u_short fs_nr
; /* flow_set number */
396 u_short flags_fs
; /* see 'Flow set flags' */
397 u_short parent_nr
; /* parent pipe#, 0 if local to a pipe */
399 int weight
; /* WFQ queue weight */
400 int qsize
; /* queue size in slots or bytes */
401 int plr
; /* pkt loss rate (2^31-1 means 100%) */
403 /* Hash table information */
404 int rq_size
; /* number of slots */
405 int rq_elements
; /* active elements */
408 int w_q
; /* queue weight (scaled) */
409 int max_th
; /* maximum threshold for queue (scaled) */
410 int min_th
; /* minimum threshold for queue (scaled) */
411 int max_p
; /* maximum value for p_b (scaled) */
412 int lookup_step
; /* granularity inside the lookup table */
413 int lookup_weight
; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
415 struct dn_ioc_flowid flow_mask
;
416 uint8_t reserved
[16];
420 struct dn_ioc_flowset fs
; /* MUST be first */
422 int pipe_nr
; /* pipe number */
423 int bandwidth
; /* bit/second */
424 int delay
; /* milliseconds */
426 dn_key V
; /* virtual time */
428 uint8_t reserved
[16];
434 #define DN_HAVE_FLOW_MASK 0x0001
435 #define DN_IS_RED 0x0002
436 #define DN_IS_GENTLE_RED 0x0004
437 #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */
438 #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */
439 #define DN_IS_PIPE 0x4000
440 #define DN_IS_QUEUE 0x8000
446 #define SCALE(x) ((x) << SCALE_RED)
447 #define SCALE_VAL(x) ((x) >> SCALE_RED)
448 #define SCALE_MUL(x, y) (((x) * (y)) >> SCALE_RED)
451 * Maximum pipe number
453 #define DN_PIPE_NR_MAX 65536
455 #endif /* !_IP_DUMMYNET_H */