1 /*-
2 * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
3 * Portions Copyright (c) 2000 Akamba Corp.
4 * All rights reserved
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
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.
14 *
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
25 * SUCH DAMAGE.
26 *
27 * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.32.2.3 2006/02/27 17:24:13 glebius Exp $
28 */
29
30 #ifndef _IP_DUMMYNET_H
31 #define _IP_DUMMYNET_H
32
33 /*
34 * Definition of dummynet data structures. In the structures, I decided
35 * not to use the macros in <sys/queue.h> in the hope of making the code
36 * easier to port to other architectures. The type of lists and queue we
37 * use here is pretty simple anyways.
38 */
39
40 /*
41 * We start with a heap, which is used in the scheduler to decide when
42 * to transmit packets etc.
43 *
44 * The key for the heap is used for two different values:
45 *
46 * 1. timer ticks- max 10K/second, so 32 bits are enough;
47 *
48 * 2. virtual times. These increase in steps of len/x, where len is the
49 * packet length, and x is either the weight of the flow, or the
50 * sum of all weights.
51 * If we limit to max 1000 flows and a max weight of 100, then
52 * x needs 17 bits. The packet size is 16 bits, so we can easily
53 * overflow if we do not allow errors.
54 * So we use a key "dn_key" which is 64 bits. Some macros are used to
55 * compare key values and handle wraparounds.
56 * MAX64 returns the largest of two key values.
57 * MY_M is used as a shift count when doing fixed point arithmetic
58 * (a better name would be useful...).
59 */
60 typedef u_int64_t dn_key ; /* sorting key */
61 #define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0)
62 #define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0)
63 #define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0)
64 #define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0)
65 #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
66 #define MY_M 16 /* number of left shift to obtain a larger precision */
67
68 /*
69 * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
70 * virtual time wraps every 15 days.
71 */
72
73 /*
74 * The OFFSET_OF macro is used to return the offset of a field within
75 * a structure. It is used by the heap management routines.
76 */
77 #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) )
78
79 /*
80 * The maximum hash table size for queues. This value must be a power
81 * of 2.
82 */
83 #define DN_MAX_HASH_SIZE 65536
84
85 /*
86 * A heap entry is made of a key and a pointer to the actual
87 * object stored in the heap.
88 * The heap is an array of dn_heap_entry entries, dynamically allocated.
89 * Current size is "size", with "elements" actually in use.
90 * The heap normally supports only ordered insert and extract from the top.
91 * If we want to extract an object from the middle of the heap, we
92 * have to know where the object itself is located in the heap (or we
93 * need to scan the whole array). To this purpose, an object has a
94 * field (int) which contains the index of the object itself into the
95 * heap. When the object is moved, the field must also be updated.
96 * The offset of the index in the object is stored in the 'offset'
97 * field in the heap descriptor. The assumption is that this offset
98 * is non-zero if we want to support extract from the middle.
99 */
100 struct dn_heap_entry {
101 dn_key key ; /* sorting key. Topmost element is smallest one */
102 void *object ; /* object pointer */
103 } ;
104
105 struct dn_heap {
106 int size ;
107 int elements ;
108 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
109 struct dn_heap_entry *p ; /* really an array of "size" entries */
110 } ;
111
112 #ifdef _KERNEL
113 /*
114 * Packets processed by dummynet have an mbuf tag associated with
115 * them that carries their dummynet state. This is used within
116 * the dummynet code as well as outside when checking for special
117 * processing requirements.
118 */
119 struct dn_pkt_tag {
120 struct ip_fw *rule; /* matching rule */
121 int dn_dir; /* action when packet comes out. */
122 #define DN_TO_IP_OUT 1
123 #define DN_TO_IP_IN 2
124 #define DN_TO_BDG_FWD 3
125 #define DN_TO_ETH_DEMUX 4
126 #define DN_TO_ETH_OUT 5
127 /* Reserved for DN_TO_IP6_IN, DN_TO_IP6_OUT */
128 #define DN_TO_IFB_FWD 8
129
130 dn_key output_time; /* when the pkt is due for delivery */
131 struct ifnet *ifp; /* interface, for ip_output */
132 };
133 #endif /* _KERNEL */
134
135 /*
136 * Overall structure of dummynet (with WF2Q+):
137
138 In dummynet, packets are selected with the firewall rules, and passed
139 to two different objects: PIPE or QUEUE.
140
141 A QUEUE is just a queue with configurable size and queue management
142 policy. It is also associated with a mask (to discriminate among
143 different flows), a weight (used to give different shares of the
144 bandwidth to different flows) and a "pipe", which essentially
145 supplies the transmit clock for all queues associated with that
146 pipe.
147
148 A PIPE emulates a fixed-bandwidth link, whose bandwidth is
149 configurable. The "clock" for a pipe can come from either an
150 internal timer, or from the transmit interrupt of an interface.
151 A pipe is also associated with one (or more, if masks are used)
152 queue, where all packets for that pipe are stored.
153
154 The bandwidth available on the pipe is shared by the queues
155 associated with that pipe (only one in case the packet is sent
156 to a PIPE) according to the WF2Q+ scheduling algorithm and the
157 configured weights.
158
159 In general, incoming packets are stored in the appropriate queue,
160 which is then placed into one of a few heaps managed by a scheduler
161 to decide when the packet should be extracted.
162 The scheduler (a function called dummynet()) is run at every timer
163 tick, and grabs queues from the head of the heaps when they are
164 ready for processing.
165
166 There are three data structures definining a pipe and associated queues:
167
168 + dn_pipe, which contains the main configuration parameters related
169 to delay and bandwidth;
170 + dn_flow_set, which contains WF2Q+ configuration, flow
171 masks, plr and RED configuration;
172 + dn_flow_queue, which is the per-flow queue (containing the packets)
173
174 Multiple dn_flow_set can be linked to the same pipe, and multiple
175 dn_flow_queue can be linked to the same dn_flow_set.
176 All data structures are linked in a linear list which is used for
177 housekeeping purposes.
178
179 During configuration, we create and initialize the dn_flow_set
180 and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
181
182 At runtime: packets are sent to the appropriate dn_flow_set (either
183 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
184 which in turn dispatches them to the appropriate dn_flow_queue
185 (created dynamically according to the masks).
186
187 The transmit clock for fixed rate flows (ready_event()) selects the
188 dn_flow_queue to be used to transmit the next packet. For WF2Q,
189 wfq_ready_event() extract a pipe which in turn selects the right
190 flow using a number of heaps defined into the pipe itself.
191
192 *
193 */
194
195 /*
196 * per flow queue. This contains the flow identifier, the queue
197 * of packets, counters, and parameters used to support both RED and
198 * WF2Q+.
199 *
200 * A dn_flow_queue is created and initialized whenever a packet for
201 * a new flow arrives.
202 */
203 struct dn_flow_queue {
204 struct dn_flow_queue *next ;
205 struct ipfw_flow_id id ;
206
207 struct mbuf *head, *tail ; /* queue of packets */
208 u_int len ;
209 u_int len_bytes ;
210 u_long numbytes ; /* credit for transmission (dynamic queues) */
211
212 u_int64_t tot_pkts ; /* statistics counters */
213 u_int64_t tot_bytes ;
214 u_int32_t drops ;
215
216 int hash_slot ; /* debugging/diagnostic */
217
218 /* RED parameters */
219 int avg ; /* average queue length est. (scaled) */
220 int count ; /* arrivals since last RED drop */
221 int random ; /* random value (scaled) */
222 u_int32_t q_time ; /* start of queue idle time */
223
224 /* WF2Q+ support */
225 struct dn_flow_set *fs ; /* parent flow set */
226 int heap_pos ; /* position (index) of struct in heap */
227 dn_key sched_time ; /* current time when queue enters ready_heap */
228
229 dn_key S,F ; /* start time, finish time */
230 /*
231 * Setting F < S means the timestamp is invalid. We only need
232 * to test this when the queue is empty.
233 */
234 } ;
235
236 /*
237 * flow_set descriptor. Contains the "template" parameters for the
238 * queue configuration, and pointers to the hash table of dn_flow_queue's.
239 *
240 * The hash table is an array of lists -- we identify the slot by
241 * hashing the flow-id, then scan the list looking for a match.
242 * The size of the hash table (buckets) is configurable on a per-queue
243 * basis.
244 *
245 * A dn_flow_set is created whenever a new queue or pipe is created (in the
246 * latter case, the structure is located inside the struct dn_pipe).
247 */
248 struct dn_flow_set {
249 struct dn_flow_set *next; /* next flow set in all_flow_sets list */
250
251 u_short fs_nr ; /* flow_set number */
252 u_short flags_fs;
253 #define DN_HAVE_FLOW_MASK 0x0001
254 #define DN_IS_RED 0x0002
255 #define DN_IS_GENTLE_RED 0x0004
256 #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */
257 #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */
258 #define DN_IS_PIPE 0x4000
259 #define DN_IS_QUEUE 0x8000
260
261 struct dn_pipe *pipe ; /* pointer to parent pipe */
262 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */
263
264 int weight ; /* WFQ queue weight */
265 int qsize ; /* queue size in slots or bytes */
266 int plr ; /* pkt loss rate (2^31-1 means 100%) */
267
268 struct ipfw_flow_id flow_mask ;
269
270 /* hash table of queues onto this flow_set */
271 int rq_size ; /* number of slots */
272 int rq_elements ; /* active elements */
273 struct dn_flow_queue **rq; /* array of rq_size entries */
274
275 u_int32_t last_expired ; /* do not expire too frequently */
276 int backlogged ; /* #active queues for this flowset */
277
278 /* RED parameters */
279 #define SCALE_RED 16
280 #define SCALE(x) ( (x) << SCALE_RED )
281 #define SCALE_VAL(x) ( (x) >> SCALE_RED )
282 #define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED )
283 int w_q ; /* queue weight (scaled) */
284 int max_th ; /* maximum threshold for queue (scaled) */
285 int min_th ; /* minimum threshold for queue (scaled) */
286 int max_p ; /* maximum value for p_b (scaled) */
287 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */
288 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */
289 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */
290 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */
291 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */
292 u_int lookup_depth ; /* depth of lookup table */
293 int lookup_step ; /* granularity inside the lookup table */
294 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
295 int avg_pkt_size ; /* medium packet size */
296 int max_pkt_size ; /* max packet size */
297 } ;
298
299 /*
300 * Pipe descriptor. Contains global parameters, delay-line queue,
301 * and the flow_set used for fixed-rate queues.
302 *
303 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
304 * not_eligible_heap, for queues whose start time is higher
305 * than the virtual time. Sorted by start time.
306 * scheduler_heap, for queues eligible for scheduling. Sorted by
307 * finish time.
308 * idle_heap, all flows that are idle and can be removed. We
309 * do that on each tick so we do not slow down too much
310 * operations during forwarding.
311 *
312 */
313 struct dn_pipe { /* a pipe */
314 struct dn_pipe *next ;
315
316 int pipe_nr ; /* number */
317 int bandwidth; /* really, bytes/tick. */
318 int delay ; /* really, ticks */
319
320 struct mbuf *head, *tail ; /* packets in delay line */
321
322 /* WF2Q+ */
323 struct dn_heap scheduler_heap ; /* top extract - key Finish time*/
324 struct dn_heap not_eligible_heap; /* top extract- key Start time */
325 struct dn_heap idle_heap ; /* random extract - key Start=Finish time */
326
327 dn_key V ; /* virtual time */
328 int sum; /* sum of weights of all active sessions */
329 int numbytes; /* bits I can transmit (more or less). */
330
331 dn_key sched_time ; /* time pipe was scheduled in ready_heap */
332
333 /*
334 * When the tx clock come from an interface (if_name[0] != '\0'), its name
335 * is stored below, whereas the ifp is filled when the rule is configured.
336 */
337 char if_name[IFNAMSIZ];
338 struct ifnet *ifp ;
339 int ready ; /* set if ifp != NULL and we got a signal from it */
340
341 struct dn_flow_set fs ; /* used with fixed-rate flows */
342 };
343
344 #ifdef _KERNEL
345 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
346 typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */
347 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
348 struct ip_fw_args *fwa);
349 extern ip_dn_ctl_t *ip_dn_ctl_ptr;
350 extern ip_dn_ruledel_t *ip_dn_ruledel_ptr;
351 extern ip_dn_io_t *ip_dn_io_ptr;
352 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
353
354 /*
355 * Return the IPFW rule associated with the dummynet tag; if any.
356 * Make sure that the dummynet tag is not reused by lower layers.
357 */
358 static __inline struct ip_fw *
359 ip_dn_claim_rule(struct mbuf *m)
360 {
361 struct m_tag *mtag = m_tag_find(m, PACKET_TAG_DUMMYNET, NULL);
362 if (mtag != NULL) {
363 mtag->m_tag_id = PACKET_TAG_NONE;
364 return (((struct dn_pkt_tag *)(mtag+1))->rule);
365 } else
366 return (NULL);
367 }
368 #endif
369 #endif /* _IP_DUMMYNET_H */
Cache object: 41b8a957a755272df5243b5a8d7dceb5
|