2 * Copyright (c) 2010 Luigi Rizzo, Riccardo Panicucci, Universita` di Pisa
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
28 * internal dummynet APIs.
30 * $FreeBSD: head/sys/netinet/ipfw/ip_dn_private.h 204591 2010-03-02 17:40:48Z luigi $
33 #ifndef _IP_DN_PRIVATE_H
34 #define _IP_DN_PRIVATE_H
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.
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)
50 MALLOC_DECLARE(M_DUMMYNET);
53 #define div64(a, b) ((int64_t)(a) / (int64_t)(b))
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); \
60 #define DN_LOCK_DESTROY() do { \
61 mtx_destroy(&dn_cfg.uh_mtx); \
62 mtx_destroy(&dn_cfg.bh_mtx); \
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)
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)
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);
84 struct mq { /* a basic queue of packets*/
85 struct mbuf *head, *tail;
89 set_oid(struct dn_id *o, int type, int len)
96 uint64_t readTSC (void);
98 * see if tsc (ot other timer) is supported.
99 * - FreeBSD has rdtsc macro for i386 and amd64
100 * - Linux has rdtscll and/or rdtsc (also for openWRT patched kernel source)
101 * - Windows has KeQueryPerformanceCounter() function that use tsc or other
104 #if defined(rdtscll) || defined(rdtsc) || defined(_WIN32)
108 * configuration and global data for a dummynet instance
110 * When a configuration is modified from userland, 'id' is incremented
111 * so we can use the value to check for stale pointers.
114 uint32_t id; /* configuration version */
116 /* defaults (sysctl-accessible) */
117 int red_lookup_depth;
118 int red_avg_pkt_size;
119 int red_max_pkt_size;
122 long byte_limit; /* max queue sizes */
129 struct timeval prev_t; /* last time dummynet_tick ran */
130 struct dn_heap evheap; /* scheduled events */
132 /* counters of objects -- used for reporting space */
138 /* ticks and other stuff */
139 uint64_t curr_time; /* in ticks */
142 * Variables to manage the time spent in the drain routines.
143 * max_drain is max the fraction of a tick (0..100) to be used
145 * We also need some variables to store the average number of
146 * timecounter ticks between calls to the periodic task, etc.
149 uint64_t cycle_task_new; /* TSC when dummynet_task() starts */
150 uint64_t cycle_task_old; /* TSC when prev. dummynet_task() starts */
152 uint64_t cycle_task_avg; /* Moving average of cicle_task */
154 /* flowsets and schedulers are in hash tables, with 'hash_size'
155 * buckets. fshash is looked up at every packet arrival
156 * so better be generous if we expect many entries.
158 struct dn_ht *fshash;
159 struct dn_ht *schedhash;
160 /* list of flowsets without a scheduler -- use sch_chain */
161 struct dn_fsk_head fsu; /* list of unlinked flowsets */
162 struct dn_alg_head schedlist; /* list of algorithms */
164 /* Counter of idle objects -- used by drain routine
165 * We scan when idle_queue (or idle_si) > expire_object.
166 * The drain routine is called every 'expire' cycles (the counter
167 * used is expire_cycle).
168 * We can disable the expire routine by setting expire to 0.
169 * An object is kept alive for at least object_idle_tick after it
170 * becomes idle. During the scan, we count the number of objects
171 * that are idle but not ready in 'idle_si_wait' and 'idle_queue_wait'
174 int idle_queue_wait; /* idle but not expired yet */
176 int idle_si_wait; /* idle but not expired yet */
177 uint32_t expire_object; /* threshold for expires */
178 uint32_t expire; /* how often to expire */
179 uint32_t expire_cycle;
180 uint32_t object_idle_tick; /* lifetime of objs */
181 uint32_t expire_object_examined; /* Burst of object examined */
183 /* drain_fs and drain_sch point to the next bucket to scan when
191 /* if the upper half is busy doing something long,
192 * can set the busy flag and we will enqueue packets in
193 * a queue for later processing.
200 * This file is normally used in the kernel, unless we do
201 * some userland tests, in which case we do not need a mtx.
202 * uh_mtx arbitrates between system calls and also
203 * protects fshash, schedhash and fsunlinked.
204 * These structures are readonly for the lower half.
205 * bh_mtx protects all other structures which may be
206 * modified upon packet arrivals
208 #if defined( __linux__ ) || defined( _WIN32 )
220 * Delay line, contains all packets on output from a link.
221 * Every scheduler instance has one.
225 struct dn_sch_inst *si;
230 * The kernel side of a flowset. It is linked in a hash table
231 * of flowsets, and in a list of children of their parent scheduler.
232 * qht is either the queue or (if HAVE_MASK) a hash table queues.
233 * Note that the mask to use is the (flow_mask|sched_mask), which
234 * changes as we attach/detach schedulers. So we store it here.
236 * XXX If we want to add scheduler-specific parameters, we need to
237 * put them in external storage because the scheduler may not be
238 * available when the fsk is created.
240 struct dn_fsk { /* kernel side of a flowset */
242 SLIST_ENTRY(dn_fsk) fsk_next; /* hash chain for fshash */
244 struct ipfw_flow_id fsk_mask;
246 /* qht is a hash table of queues, or just a single queue
247 * a bit in fs.flags tells us which one
250 struct dn_schk *sched; /* Sched we are linked to */
251 SLIST_ENTRY(dn_fsk) sch_chain; /* list of fsk attached to sched */
253 /* bucket index used by drain routine to drain queues for this
257 /* Parameter realted to RED / GRED */
258 /* original values are in dn_fs*/
259 int w_q ; /* queue weight (scaled) */
260 int max_th ; /* maximum threshold for queue (scaled) */
261 int min_th ; /* minimum threshold for queue (scaled) */
262 int max_p ; /* maximum value for p_b (scaled) */
264 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */
265 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */
266 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */
267 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */
268 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */
269 u_int lookup_depth ; /* depth of lookup table */
270 int lookup_step ; /* granularity inside the lookup table */
271 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
272 int avg_pkt_size ; /* medium packet size */
273 int max_pkt_size ; /* max packet size */
277 * A queue is created as a child of a flowset unless it belongs to
278 * a !MULTIQUEUE scheduler. It is normally in a hash table in the
279 * flowset. fs always points to the parent flowset.
280 * si normally points to the sch_inst, unless the flowset has been
281 * detached from the scheduler -- in this case si == NULL and we
282 * should not enqueue.
285 struct dn_flow ni; /* oid, flow_id, stats */
286 struct mq mq; /* packets queue */
287 struct dn_sch_inst *_si; /* owner scheduler instance */
288 SLIST_ENTRY(dn_queue) q_next; /* hash chain list for qht */
289 struct dn_fsk *fs; /* parent flowset. */
292 int avg; /* average queue length est. (scaled) */
293 int count; /* arrivals since last RED drop */
294 int random; /* random value (scaled) */
295 uint64_t q_time; /* start of queue idle time */
300 * The kernel side of a scheduler. Contains the userland config,
301 * a link, pointer to extra config arguments from command line,
302 * kernel flags, and a pointer to the scheduler methods.
303 * It is stored in a hash table, and holds a list of all
304 * flowsets and scheduler instances.
305 * XXX sch must be at the beginning, see schk_hash().
309 struct dn_alg *fp; /* Pointer to scheduler functions */
310 struct dn_link link; /* The link, embedded */
311 struct dn_profile *profile; /* delay profile, if any */
312 struct dn_id *cfg; /* extra config arguments */
314 SLIST_ENTRY(dn_schk) schk_next; /* hash chain for schedhash */
316 struct dn_fsk_head fsk_list; /* all fsk linked to me */
317 struct dn_fsk *fs; /* Flowset for !MULTIQUEUE */
319 /* bucket index used by the drain routine to drain the scheduler
320 * instance for this flowset.
324 /* Hash table of all instances (through sch.sched_mask)
325 * or single instance if no mask. Always valid.
332 * Scheduler instance.
333 * Contains variables and all queues relative to a this instance.
334 * This struct is created a runtime.
337 struct dn_flow ni; /* oid, flowid and stats */
338 SLIST_ENTRY(dn_sch_inst) si_next; /* hash chain for siht */
339 struct delay_line dline;
340 struct dn_schk *sched; /* the template */
341 int kflags; /* DN_ACTIVE */
343 int64_t credit; /* bits I can transmit (more or less). */
344 uint64_t sched_time; /* time link was scheduled in ready_heap */
345 uint64_t idle_time; /* start of scheduler instance idle time */
347 /* q_count is the number of queues that this instance is using.
348 * The counter is incremented or decremented when
349 * a reference from the queue is created or deleted.
350 * It is used to make sure that a scheduler instance can be safely
351 * deleted by the drain routine.
358 /* kernel-side flags. Linux has DN_DELETE in fcntl.h
361 /* 1 and 2 are reserved for the SCAN flags */
362 DN_DESTROY = 0x0004, /* destroy */
363 DN_DELETE_FS = 0x0008, /* destroy flowset */
365 DN_ACTIVE = 0x0020, /* object is in evheap */
366 DN_F_DLINE = 0x0040, /* object is a delay line */
367 DN_DEL_SAFE = 0x0080, /* delete a queue only if no longer needed
369 DN_QHT_IS_Q = 0x0100, /* in flowset, qht is a single queue */
372 extern struct dn_parms dn_cfg;
373 //VNET_DECLARE(struct dn_parms, _base_dn_cfg);
374 //#define dn_cfg VNET(_base_dn_cfg)
376 int dummynet_io(struct mbuf **, int , struct ip_fw_args *);
377 void dummynet_task(void *context, int pending);
378 void dn_reschedule(void);
380 struct dn_queue *ipdn_q_find(struct dn_fsk *, struct ipfw_flow_id *);
381 struct dn_sch_inst *ipdn_si_find(struct dn_schk *, struct ipfw_flow_id *);
384 * copy_range is a template for requests for ranges of pipes/queues/scheds.
385 * The number of ranges is variable and can be derived by o.len.
386 * As a default, we use a small number of entries so that the struct
387 * fits easily on the stack and is sufficient for most common requests.
389 #define DEFAULT_RANGES 5
392 uint32_t r[ 2 * DEFAULT_RANGES ];
400 struct copy_range *extra; /* extra filtering */
404 int ip_dummynet_compat(struct sockopt *sopt);
405 int dummynet_get(struct sockopt *sopt, void **compat);
406 int dn_c_copy_q (void *_ni, void *arg);
407 int dn_c_copy_pipe(struct dn_schk *s, struct copy_args *a, int nq);
408 int dn_c_copy_fs(struct dn_fsk *f, struct copy_args *a, int nq);
409 int dn_compat_copy_queue(struct copy_args *a, void *_o);
410 int dn_compat_copy_pipe(struct copy_args *a, void *_o);
411 int copy_data_helper_compat(void *_o, void *_arg);
412 int dn_compat_calc_size(void);
413 int do_config(void *p, int l);
415 /* function to drain idle object */
416 void dn_drain_scheduler(void);
417 void dn_drain_queue(void);
419 #endif /* _IP_DN_PRIVATE_H */