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: stable/10/sys/netpfil/ipfw/ip_dn_private.h 325731 2017-11-12 01:28:20Z truckman $
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 #ifdef NEW_AQM
85 SLIST_HEAD(dn_aqm_head, dn_aqm); /* for new AQMs */
86 #endif
87
88 struct mq { /* a basic queue of packets*/
89 struct mbuf *head, *tail;
90 };
91
92 static inline void
set_oid(struct dn_id * o,int type,int len)93 set_oid(struct dn_id *o, int type, int len)
94 {
95 o->type = type;
96 o->len = len;
97 o->subtype = 0;
98 };
99
100 /*
101 * configuration and global data for a dummynet instance
102 *
103 * When a configuration is modified from userland, 'id' is incremented
104 * so we can use the value to check for stale pointers.
105 */
106 struct dn_parms {
107 uint32_t id; /* configuration version */
108
109 /* defaults (sysctl-accessible) */
110 int red_lookup_depth;
111 int red_avg_pkt_size;
112 int red_max_pkt_size;
113 int hash_size;
114 int max_hash_size;
115 long byte_limit; /* max queue sizes */
116 long slot_limit;
117
118 int io_fast;
119 int debug;
120
121 /* timekeeping */
122 struct timeval prev_t; /* last time dummynet_tick ran */
123 struct dn_heap evheap; /* scheduled events */
124
125 /* counters of objects -- used for reporting space */
126 int schk_count;
127 int si_count;
128 int fsk_count;
129 int queue_count;
130
131 /* ticks and other stuff */
132 uint64_t curr_time;
133 /* flowsets and schedulers are in hash tables, with 'hash_size'
134 * buckets. fshash is looked up at every packet arrival
135 * so better be generous if we expect many entries.
136 */
137 struct dn_ht *fshash;
138 struct dn_ht *schedhash;
139 /* list of flowsets without a scheduler -- use sch_chain */
140 struct dn_fsk_head fsu; /* list of unlinked flowsets */
141 struct dn_alg_head schedlist; /* list of algorithms */
142 #ifdef NEW_AQM
143 struct dn_aqm_head aqmlist; /* list of AQMs */
144 #endif
145
146 /* Store the fs/sch to scan when draining. The value is the
147 * bucket number of the hash table. Expire can be disabled
148 * with net.inet.ip.dummynet.expire=0, or it happens every
149 * expire ticks.
150 **/
151 int drain_fs;
152 int drain_sch;
153 uint32_t expire;
154 uint32_t expire_cycle; /* tick count */
155
156 int init_done;
157
158 /* if the upper half is busy doing something long,
159 * can set the busy flag and we will enqueue packets in
160 * a queue for later processing.
161 */
162 int busy;
163 struct mq pending;
164
165 #ifdef _KERNEL
166 /*
167 * This file is normally used in the kernel, unless we do
168 * some userland tests, in which case we do not need a mtx.
169 * uh_mtx arbitrates between system calls and also
170 * protects fshash, schedhash and fsunlinked.
171 * These structures are readonly for the lower half.
172 * bh_mtx protects all other structures which may be
173 * modified upon packet arrivals
174 */
175 #if defined( __linux__ ) || defined( _WIN32 )
176 spinlock_t uh_mtx;
177 spinlock_t bh_mtx;
178 #else
179 struct mtx uh_mtx;
180 struct mtx bh_mtx;
181 #endif
182
183 #endif /* _KERNEL */
184 };
185
186 /*
187 * Delay line, contains all packets on output from a link.
188 * Every scheduler instance has one.
189 */
190 struct delay_line {
191 struct dn_id oid;
192 struct dn_sch_inst *si;
193 struct mq mq;
194 };
195
196 /*
197 * The kernel side of a flowset. It is linked in a hash table
198 * of flowsets, and in a list of children of their parent scheduler.
199 * qht is either the queue or (if HAVE_MASK) a hash table queues.
200 * Note that the mask to use is the (flow_mask|sched_mask), which
201 * changes as we attach/detach schedulers. So we store it here.
202 *
203 * XXX If we want to add scheduler-specific parameters, we need to
204 * put them in external storage because the scheduler may not be
205 * available when the fsk is created.
206 */
207 struct dn_fsk { /* kernel side of a flowset */
208 struct dn_fs fs;
209 SLIST_ENTRY(dn_fsk) fsk_next; /* hash chain for fshash */
210
211 struct ipfw_flow_id fsk_mask;
212
213 /* qht is a hash table of queues, or just a single queue
214 * a bit in fs.flags tells us which one
215 */
216 struct dn_ht *qht;
217 struct dn_schk *sched; /* Sched we are linked to */
218 SLIST_ENTRY(dn_fsk) sch_chain; /* list of fsk attached to sched */
219
220 /* bucket index used by drain routine to drain queues for this
221 * flowset
222 */
223 int drain_bucket;
224 /* Parameter realted to RED / GRED */
225 /* original values are in dn_fs*/
226 int w_q ; /* queue weight (scaled) */
227 int max_th ; /* maximum threshold for queue (scaled) */
228 int min_th ; /* minimum threshold for queue (scaled) */
229 int max_p ; /* maximum value for p_b (scaled) */
230
231 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */
232 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */
233 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */
234 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */
235 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */
236 u_int lookup_depth ; /* depth of lookup table */
237 int lookup_step ; /* granularity inside the lookup table */
238 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
239 int avg_pkt_size ; /* medium packet size */
240 int max_pkt_size ; /* max packet size */
241 #ifdef NEW_AQM
242 struct dn_aqm *aqmfp; /* Pointer to AQM functions */
243 void *aqmcfg; /* configuration parameters for AQM */
244 #endif
245 };
246
247 /*
248 * A queue is created as a child of a flowset unless it belongs to
249 * a !MULTIQUEUE scheduler. It is normally in a hash table in the
250 * flowset. fs always points to the parent flowset.
251 * si normally points to the sch_inst, unless the flowset has been
252 * detached from the scheduler -- in this case si == NULL and we
253 * should not enqueue.
254 */
255 struct dn_queue {
256 struct dn_flow ni; /* oid, flow_id, stats */
257 struct mq mq; /* packets queue */
258 struct dn_sch_inst *_si; /* owner scheduler instance */
259 SLIST_ENTRY(dn_queue) q_next; /* hash chain list for qht */
260 struct dn_fsk *fs; /* parent flowset. */
261
262 /* RED parameters */
263 int avg; /* average queue length est. (scaled) */
264 int count; /* arrivals since last RED drop */
265 int random; /* random value (scaled) */
266 uint64_t q_time; /* start of queue idle time */
267 #ifdef NEW_AQM
268 void *aqm_status; /* per-queue status variables*/
269 #endif
270
271 };
272
273 /*
274 * The kernel side of a scheduler. Contains the userland config,
275 * a link, pointer to extra config arguments from command line,
276 * kernel flags, and a pointer to the scheduler methods.
277 * It is stored in a hash table, and holds a list of all
278 * flowsets and scheduler instances.
279 * XXX sch must be at the beginning, see schk_hash().
280 */
281 struct dn_schk {
282 struct dn_sch sch;
283 struct dn_alg *fp; /* Pointer to scheduler functions */
284 struct dn_link link; /* The link, embedded */
285 struct dn_profile *profile; /* delay profile, if any */
286 struct dn_id *cfg; /* extra config arguments */
287
288 SLIST_ENTRY(dn_schk) schk_next; /* hash chain for schedhash */
289
290 struct dn_fsk_head fsk_list; /* all fsk linked to me */
291 struct dn_fsk *fs; /* Flowset for !MULTIQUEUE */
292
293 /* bucket index used by the drain routine to drain the scheduler
294 * instance for this flowset.
295 */
296 int drain_bucket;
297
298 /* Hash table of all instances (through sch.sched_mask)
299 * or single instance if no mask. Always valid.
300 */
301 struct dn_ht *siht;
302 };
303
304
305 /*
306 * Scheduler instance.
307 * Contains variables and all queues relative to a this instance.
308 * This struct is created a runtime.
309 */
310 struct dn_sch_inst {
311 struct dn_flow ni; /* oid, flowid and stats */
312 SLIST_ENTRY(dn_sch_inst) si_next; /* hash chain for siht */
313 struct delay_line dline;
314 struct dn_schk *sched; /* the template */
315 int kflags; /* DN_ACTIVE */
316
317 int64_t credit; /* bits I can transmit (more or less). */
318 uint64_t sched_time; /* time link was scheduled in ready_heap */
319 uint64_t idle_time; /* start of scheduler instance idle time */
320
321 /* q_count is the number of queues that this instance is using.
322 * The counter is incremented or decremented when
323 * a reference from the queue is created or deleted.
324 * It is used to make sure that a scheduler instance can be safely
325 * deleted by the drain routine. See notes below.
326 */
327 int q_count;
328
329 };
330
331 /*
332 * NOTE about object drain.
333 * The system will automatically (XXX check when) drain queues and
334 * scheduler instances when they are idle.
335 * A queue is idle when it has no packets; an instance is idle when
336 * it is not in the evheap heap, and the corresponding delay line is empty.
337 * A queue can be safely deleted when it is idle because of the scheduler
338 * function xxx_free_queue() will remove any references to it.
339 * An instance can be only deleted when no queues reference it. To be sure
340 * of that, a counter (q_count) stores the number of queues that are pointing
341 * to the instance.
342 *
343 * XXX
344 * Order of scan:
345 * - take all flowset in a bucket for the flowset hash table
346 * - take all queues in a bucket for the flowset
347 * - increment the queue bucket
348 * - scan next flowset bucket
349 * Nothing is done if a bucket contains no entries.
350 *
351 * The same schema is used for sceduler instances
352 */
353
354
355 /* kernel-side flags. Linux has DN_DELETE in fcntl.h
356 */
357 enum {
358 /* 1 and 2 are reserved for the SCAN flags */
359 DN_DESTROY = 0x0004, /* destroy */
360 DN_DELETE_FS = 0x0008, /* destroy flowset */
361 DN_DETACH = 0x0010,
362 DN_ACTIVE = 0x0020, /* object is in evheap */
363 DN_F_DLINE = 0x0040, /* object is a delay line */
364 DN_DEL_SAFE = 0x0080, /* delete a queue only if no longer needed
365 * by scheduler */
366 DN_QHT_IS_Q = 0x0100, /* in flowset, qht is a single queue */
367 };
368
369 /*
370 * Packets processed by dummynet have an mbuf tag associated with
371 * them that carries their dummynet state.
372 * Outside dummynet, only the 'rule' field is relevant, and it must
373 * be at the beginning of the structure.
374 */
375 struct dn_pkt_tag {
376 struct ipfw_rule_ref rule; /* matching rule */
377
378 /* second part, dummynet specific */
379 int dn_dir; /* action when packet comes out.*/
380 /* see ip_fw_private.h */
381 uint64_t output_time; /* when the pkt is due for delivery*/
382 struct ifnet *ifp; /* interface, for ip_output */
383 struct _ip6dn_args ip6opt; /* XXX ipv6 options */
384 uint16_t iphdr_off; /* IP header offset for mtodo() */
385 };
386
387 extern struct dn_parms dn_cfg;
388 //VNET_DECLARE(struct dn_parms, _base_dn_cfg);
389 //#define dn_cfg VNET(_base_dn_cfg)
390
391 int dummynet_io(struct mbuf **, int , struct ip_fw_args *);
392 void dummynet_task(void *context, int pending);
393 void dn_reschedule(void);
394 struct dn_pkt_tag * dn_tag_get(struct mbuf *m);
395
396 struct dn_queue *ipdn_q_find(struct dn_fsk *, struct dn_sch_inst *,
397 struct ipfw_flow_id *);
398 struct dn_sch_inst *ipdn_si_find(struct dn_schk *, struct ipfw_flow_id *);
399
400 /*
401 * copy_range is a template for requests for ranges of pipes/queues/scheds.
402 * The number of ranges is variable and can be derived by o.len.
403 * As a default, we use a small number of entries so that the struct
404 * fits easily on the stack and is sufficient for most common requests.
405 */
406 #define DEFAULT_RANGES 5
407 struct copy_range {
408 struct dn_id o;
409 uint32_t r[ 2 * DEFAULT_RANGES ];
410 };
411
412 struct copy_args {
413 char **start;
414 char *end;
415 int flags;
416 int type;
417 struct copy_range *extra; /* extra filtering */
418 };
419
420 struct sockopt;
421 int ip_dummynet_compat(struct sockopt *sopt);
422 int dummynet_get(struct sockopt *sopt, void **compat);
423 int dn_c_copy_q (void *_ni, void *arg);
424 int dn_c_copy_pipe(struct dn_schk *s, struct copy_args *a, int nq);
425 int dn_c_copy_fs(struct dn_fsk *f, struct copy_args *a, int nq);
426 int dn_compat_copy_queue(struct copy_args *a, void *_o);
427 int dn_compat_copy_pipe(struct copy_args *a, void *_o);
428 int copy_data_helper_compat(void *_o, void *_arg);
429 int dn_compat_calc_size(void);
430 int do_config(void *p, int l);
431
432 /* function to drain idle object */
433 void dn_drain_scheduler(void);
434 void dn_drain_queue(void);
435
436 #ifdef NEW_AQM
437 int ecn_mark(struct mbuf* m);
438
439 /* moved from ip_dn_io.c to here to be available for AQMs modules*/
440 static inline void
mq_append(struct mq * q,struct mbuf * m)441 mq_append(struct mq *q, struct mbuf *m)
442 {
443 if (q->head == NULL)
444 q->head = m;
445 else
446 q->tail->m_nextpkt = m;
447 q->tail = m;
448 m->m_nextpkt = NULL;
449 }
450 #endif /* NEW_AQM */
451
452 #endif /* _IP_DN_PRIVATE_H */
453