xref: /freebsd/sys/netpfil/ipfw/ip_dn_private.h (revision 3a92d97ff0f22d21608e1c19b83104c4937523b6)
1 /*-
2  * Copyright (c) 2010 Luigi Rizzo, Riccardo Panicucci, Universita` di Pisa
3  * All rights reserved
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  */
26 
27 /*
28  * internal dummynet APIs.
29  *
30  * $FreeBSD$
31  */
32 
33 #ifndef _IP_DN_PRIVATE_H
34 #define _IP_DN_PRIVATE_H
35 
36 /* debugging support
37  * use ND() to remove debugging, D() to print a line,
38  * DX(level, ...) to print above a certain level
39  * If you redefine D() you are expected to redefine all.
40  */
41 #ifndef D
42 #define ND(fmt, ...) do {} while (0)
43 #define D1(fmt, ...) do {} while (0)
44 #define D(fmt, ...) printf("%-10s " fmt "\n",      \
45         __FUNCTION__, ## __VA_ARGS__)
46 #define DX(lev, fmt, ...) do {              \
47         if (dn_cfg.debug > lev) D(fmt, ## __VA_ARGS__); } while (0)
48 #endif
49 
50 MALLOC_DECLARE(M_DUMMYNET);
51 
52 #ifndef __linux__
53 #define div64(a, b)  ((int64_t)(a) / (int64_t)(b))
54 #endif
55 
56 #define DN_LOCK_INIT() do {				\
57 	mtx_init(&dn_cfg.uh_mtx, "dn_uh", NULL, MTX_DEF);	\
58 	mtx_init(&dn_cfg.bh_mtx, "dn_bh", NULL, MTX_DEF);	\
59 	} while (0)
60 #define DN_LOCK_DESTROY() do {				\
61 	mtx_destroy(&dn_cfg.uh_mtx);			\
62 	mtx_destroy(&dn_cfg.bh_mtx);			\
63 	} while (0)
64 #if 0 /* not used yet */
65 #define DN_UH_RLOCK()		mtx_lock(&dn_cfg.uh_mtx)
66 #define DN_UH_RUNLOCK()		mtx_unlock(&dn_cfg.uh_mtx)
67 #define DN_UH_WLOCK()		mtx_lock(&dn_cfg.uh_mtx)
68 #define DN_UH_WUNLOCK()		mtx_unlock(&dn_cfg.uh_mtx)
69 #define DN_UH_LOCK_ASSERT()	mtx_assert(&dn_cfg.uh_mtx, MA_OWNED)
70 #endif
71 
72 #define DN_BH_RLOCK()		mtx_lock(&dn_cfg.uh_mtx)
73 #define DN_BH_RUNLOCK()		mtx_unlock(&dn_cfg.uh_mtx)
74 #define DN_BH_WLOCK()		mtx_lock(&dn_cfg.uh_mtx)
75 #define DN_BH_WUNLOCK()		mtx_unlock(&dn_cfg.uh_mtx)
76 #define DN_BH_LOCK_ASSERT()	mtx_assert(&dn_cfg.uh_mtx, MA_OWNED)
77 
78 SLIST_HEAD(dn_schk_head, dn_schk);
79 SLIST_HEAD(dn_sch_inst_head, dn_sch_inst);
80 SLIST_HEAD(dn_fsk_head, dn_fsk);
81 SLIST_HEAD(dn_queue_head, dn_queue);
82 SLIST_HEAD(dn_alg_head, dn_alg);
83 
84 struct mq {	/* a basic queue of packets*/
85         struct mbuf *head, *tail;
86 	int count;
87 };
88 
89 static inline void
90 set_oid(struct dn_id *o, int type, int len)
91 {
92         o->type = type;
93         o->len = len;
94         o->subtype = 0;
95 };
96 
97 /*
98  * configuration and global data for a dummynet instance
99  *
100  * When a configuration is modified from userland, 'id' is incremented
101  * so we can use the value to check for stale pointers.
102  */
103 struct dn_parms {
104 	uint32_t	id;		/* configuration version */
105 
106 	/* defaults (sysctl-accessible) */
107 	int	red_lookup_depth;
108 	int	red_avg_pkt_size;
109 	int	red_max_pkt_size;
110 	int	hash_size;
111 	int	max_hash_size;
112 	long	byte_limit;		/* max queue sizes */
113 	long	slot_limit;
114 
115 	int	io_fast;
116 	int	debug;
117 
118 	/* timekeeping */
119 	struct timeval prev_t;		/* last time dummynet_tick ran */
120 	struct dn_heap	evheap;		/* scheduled events */
121 
122 	/* counters of objects -- used for reporting space */
123 	int	schk_count;
124 	int	si_count;
125 	int	fsk_count;
126 	int	queue_count;
127 
128 	/* ticks and other stuff */
129 	uint64_t	curr_time;
130 	/* flowsets and schedulers are in hash tables, with 'hash_size'
131 	 * buckets. fshash is looked up at every packet arrival
132 	 * so better be generous if we expect many entries.
133 	 */
134 	struct dn_ht	*fshash;
135 	struct dn_ht	*schedhash;
136 	/* list of flowsets without a scheduler -- use sch_chain */
137 	struct dn_fsk_head	fsu;	/* list of unlinked flowsets */
138 	struct dn_alg_head	schedlist;	/* list of algorithms */
139 
140 	/* Store the fs/sch to scan when draining. The value is the
141 	 * bucket number of the hash table. Expire can be disabled
142 	 * with net.inet.ip.dummynet.expire=0, or it happens every
143 	 * expire ticks.
144 	 **/
145 	int drain_fs;
146 	int drain_sch;
147 	uint32_t expire;
148 	uint32_t expire_cycle;	/* tick count */
149 
150 	int init_done;
151 
152 	/* if the upper half is busy doing something long,
153 	 * can set the busy flag and we will enqueue packets in
154 	 * a queue for later processing.
155 	 */
156 	int	busy;
157 	struct	mq	pending;
158 
159 #ifdef _KERNEL
160 	/*
161 	 * This file is normally used in the kernel, unless we do
162 	 * some userland tests, in which case we do not need a mtx.
163 	 * uh_mtx arbitrates between system calls and also
164 	 * protects fshash, schedhash and fsunlinked.
165 	 * These structures are readonly for the lower half.
166 	 * bh_mtx protects all other structures which may be
167 	 * modified upon packet arrivals
168 	 */
169 #if defined( __linux__ ) || defined( _WIN32 )
170 	spinlock_t uh_mtx;
171 	spinlock_t bh_mtx;
172 #else
173 	struct mtx uh_mtx;
174 	struct mtx bh_mtx;
175 #endif
176 
177 #endif /* _KERNEL */
178 };
179 
180 /*
181  * Delay line, contains all packets on output from a link.
182  * Every scheduler instance has one.
183  */
184 struct delay_line {
185 	struct dn_id oid;
186 	struct dn_sch_inst *si;
187 	struct mq mq;
188 };
189 
190 /*
191  * The kernel side of a flowset. It is linked in a hash table
192  * of flowsets, and in a list of children of their parent scheduler.
193  * qht is either the queue or (if HAVE_MASK) a hash table queues.
194  * Note that the mask to use is the (flow_mask|sched_mask), which
195  * changes as we attach/detach schedulers. So we store it here.
196  *
197  * XXX If we want to add scheduler-specific parameters, we need to
198  * put them in external storage because the scheduler may not be
199  * available when the fsk is created.
200  */
201 struct dn_fsk { /* kernel side of a flowset */
202 	struct dn_fs fs;
203 	SLIST_ENTRY(dn_fsk) fsk_next;	/* hash chain for fshash */
204 
205 	struct ipfw_flow_id fsk_mask;
206 
207 	/* qht is a hash table of queues, or just a single queue
208 	 * a bit in fs.flags tells us which one
209 	 */
210 	struct dn_ht	*qht;
211 	struct dn_schk *sched;		/* Sched we are linked to */
212 	SLIST_ENTRY(dn_fsk) sch_chain;	/* list of fsk attached to sched */
213 
214 	/* bucket index used by drain routine to drain queues for this
215 	 * flowset
216 	 */
217 	int drain_bucket;
218 	/* Parameter realted to RED / GRED */
219 	/* original values are in dn_fs*/
220 	int w_q ;		/* queue weight (scaled) */
221 	int max_th ;		/* maximum threshold for queue (scaled) */
222 	int min_th ;		/* minimum threshold for queue (scaled) */
223 	int max_p ;		/* maximum value for p_b (scaled) */
224 
225 	u_int c_1 ;		/* max_p/(max_th-min_th) (scaled) */
226 	u_int c_2 ;		/* max_p*min_th/(max_th-min_th) (scaled) */
227 	u_int c_3 ;		/* for GRED, (1-max_p)/max_th (scaled) */
228 	u_int c_4 ;		/* for GRED, 1 - 2*max_p (scaled) */
229 	u_int * w_q_lookup ;	/* lookup table for computing (1-w_q)^t */
230 	u_int lookup_depth ;	/* depth of lookup table */
231 	int lookup_step ;	/* granularity inside the lookup table */
232 	int lookup_weight ;	/* equal to (1-w_q)^t / (1-w_q)^(t+1) */
233 	int avg_pkt_size ;	/* medium packet size */
234 	int max_pkt_size ;	/* max packet size */
235 };
236 
237 /*
238  * A queue is created as a child of a flowset unless it belongs to
239  * a !MULTIQUEUE scheduler. It is normally in a hash table in the
240  * flowset. fs always points to the parent flowset.
241  * si normally points to the sch_inst, unless the flowset has been
242  * detached from the scheduler -- in this case si == NULL and we
243  * should not enqueue.
244  */
245 struct dn_queue {
246 	struct dn_flow ni;	/* oid, flow_id, stats */
247 	struct mq mq;	/* packets queue */
248 	struct dn_sch_inst *_si;	/* owner scheduler instance */
249 	SLIST_ENTRY(dn_queue) q_next; /* hash chain list for qht */
250 	struct dn_fsk *fs;		/* parent flowset. */
251 
252 	/* RED parameters */
253 	int avg;		/* average queue length est. (scaled) */
254 	int count;		/* arrivals since last RED drop */
255 	int random;		/* random value (scaled) */
256 	uint64_t q_time;	/* start of queue idle time */
257 
258 };
259 
260 /*
261  * The kernel side of a scheduler. Contains the userland config,
262  * a link, pointer to extra config arguments from command line,
263  * kernel flags, and a pointer to the scheduler methods.
264  * It is stored in a hash table, and holds a list of all
265  * flowsets and scheduler instances.
266  * XXX sch must be at the beginning, see schk_hash().
267  */
268 struct dn_schk {
269 	struct dn_sch sch;
270 	struct dn_alg *fp;	/* Pointer to scheduler functions */
271 	struct dn_link link;	/* The link, embedded */
272 	struct dn_profile *profile; /* delay profile, if any */
273 	struct dn_id *cfg;	/* extra config arguments */
274 
275 	SLIST_ENTRY(dn_schk) schk_next;  /* hash chain for schedhash */
276 
277 	struct dn_fsk_head fsk_list;  /* all fsk linked to me */
278 	struct dn_fsk *fs;	/* Flowset for !MULTIQUEUE */
279 
280 	/* bucket index used by the drain routine to drain the scheduler
281 	 * instance for this flowset.
282 	 */
283 	int drain_bucket;
284 
285 	/* Hash table of all instances (through sch.sched_mask)
286 	 * or single instance if no mask. Always valid.
287 	 */
288 	struct dn_ht	*siht;
289 };
290 
291 
292 /*
293  * Scheduler instance.
294  * Contains variables and all queues relative to a this instance.
295  * This struct is created a runtime.
296  */
297 struct dn_sch_inst {
298 	struct dn_flow	ni;	/* oid, flowid and stats */
299 	SLIST_ENTRY(dn_sch_inst) si_next; /* hash chain for siht */
300 	struct delay_line dline;
301 	struct dn_schk *sched;	/* the template */
302 	int		kflags;	/* DN_ACTIVE */
303 
304 	int64_t	credit;		/* bits I can transmit (more or less). */
305 	uint64_t sched_time;	/* time link was scheduled in ready_heap */
306 	uint64_t idle_time;	/* start of scheduler instance idle time */
307 
308 	/* q_count is the number of queues that this instance is using.
309 	 * The counter is incremented or decremented when
310 	 * a reference from the queue is created or deleted.
311 	 * It is used to make sure that a scheduler instance can be safely
312 	 * deleted by the drain routine. See notes below.
313 	 */
314 	int q_count;
315 
316 };
317 
318 /*
319  * NOTE about object drain.
320  * The system will automatically (XXX check when) drain queues and
321  * scheduler instances when they are idle.
322  * A queue is idle when it has no packets; an instance is idle when
323  * it is not in the evheap heap, and the corresponding delay line is empty.
324  * A queue can be safely deleted when it is idle because of the scheduler
325  * function xxx_free_queue() will remove any references to it.
326  * An instance can be only deleted when no queues reference it. To be sure
327  * of that, a counter (q_count) stores the number of queues that are pointing
328  * to the instance.
329  *
330  * XXX
331  * Order of scan:
332  * - take all flowset in a bucket for the flowset hash table
333  * - take all queues in a bucket for the flowset
334  * - increment the queue bucket
335  * - scan next flowset bucket
336  * Nothing is done if a bucket contains no entries.
337  *
338  * The same schema is used for sceduler instances
339  */
340 
341 
342 /* kernel-side flags. Linux has DN_DELETE in fcntl.h
343  */
344 enum {
345 	/* 1 and 2 are reserved for the SCAN flags */
346 	DN_DESTROY	= 0x0004, /* destroy */
347 	DN_DELETE_FS	= 0x0008, /* destroy flowset */
348 	DN_DETACH	= 0x0010,
349 	DN_ACTIVE	= 0x0020, /* object is in evheap */
350 	DN_F_DLINE	= 0x0040, /* object is a delay line */
351 	DN_DEL_SAFE	= 0x0080, /* delete a queue only if no longer needed
352 				   * by scheduler */
353 	DN_QHT_IS_Q	= 0x0100, /* in flowset, qht is a single queue */
354 };
355 
356 extern struct dn_parms dn_cfg;
357 //VNET_DECLARE(struct dn_parms, _base_dn_cfg);
358 //#define dn_cfg	VNET(_base_dn_cfg)
359 
360 int dummynet_io(struct mbuf **, int , struct ip_fw_args *);
361 void dummynet_task(void *context, int pending);
362 void dn_reschedule(void);
363 
364 struct dn_queue *ipdn_q_find(struct dn_fsk *, struct dn_sch_inst *,
365         struct ipfw_flow_id *);
366 struct dn_sch_inst *ipdn_si_find(struct dn_schk *, struct ipfw_flow_id *);
367 
368 /*
369  * copy_range is a template for requests for ranges of pipes/queues/scheds.
370  * The number of ranges is variable and can be derived by o.len.
371  * As a default, we use a small number of entries so that the struct
372  * fits easily on the stack and is sufficient for most common requests.
373  */
374 #define DEFAULT_RANGES	5
375 struct copy_range {
376         struct dn_id o;
377         uint32_t	r[ 2 * DEFAULT_RANGES ];
378 };
379 
380 struct copy_args {
381 	char **start;
382 	char *end;
383 	int flags;
384 	int type;
385 	struct copy_range *extra;	/* extra filtering */
386 };
387 
388 struct sockopt;
389 int ip_dummynet_compat(struct sockopt *sopt);
390 int dummynet_get(struct sockopt *sopt, void **compat);
391 int dn_c_copy_q (void *_ni, void *arg);
392 int dn_c_copy_pipe(struct dn_schk *s, struct copy_args *a, int nq);
393 int dn_c_copy_fs(struct dn_fsk *f, struct copy_args *a, int nq);
394 int dn_compat_copy_queue(struct copy_args *a, void *_o);
395 int dn_compat_copy_pipe(struct copy_args *a, void *_o);
396 int copy_data_helper_compat(void *_o, void *_arg);
397 int dn_compat_calc_size(void);
398 int do_config(void *p, int l);
399 
400 /* function to drain idle object */
401 void dn_drain_scheduler(void);
402 void dn_drain_queue(void);
403 
404 #endif /* _IP_DN_PRIVATE_H */
405