13b3a8eb9SGleb Smirnoff /*-
24d846d26SWarner Losh * SPDX-License-Identifier: BSD-2-Clause
3fe267a55SPedro F. Giffuni *
43b3a8eb9SGleb Smirnoff * Copyright (c) 2010 Luigi Rizzo, Riccardo Panicucci, Universita` di Pisa
53b3a8eb9SGleb Smirnoff * All rights reserved
63b3a8eb9SGleb Smirnoff *
73b3a8eb9SGleb Smirnoff * Redistribution and use in source and binary forms, with or without
83b3a8eb9SGleb Smirnoff * modification, are permitted provided that the following conditions
93b3a8eb9SGleb Smirnoff * are met:
103b3a8eb9SGleb Smirnoff * 1. Redistributions of source code must retain the above copyright
113b3a8eb9SGleb Smirnoff * notice, this list of conditions and the following disclaimer.
123b3a8eb9SGleb Smirnoff * 2. Redistributions in binary form must reproduce the above copyright
133b3a8eb9SGleb Smirnoff * notice, this list of conditions and the following disclaimer in the
143b3a8eb9SGleb Smirnoff * documentation and/or other materials provided with the distribution.
153b3a8eb9SGleb Smirnoff *
163b3a8eb9SGleb Smirnoff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
173b3a8eb9SGleb Smirnoff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
183b3a8eb9SGleb Smirnoff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
193b3a8eb9SGleb Smirnoff * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
203b3a8eb9SGleb Smirnoff * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
213b3a8eb9SGleb Smirnoff * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
223b3a8eb9SGleb Smirnoff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
233b3a8eb9SGleb Smirnoff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
243b3a8eb9SGleb Smirnoff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
253b3a8eb9SGleb Smirnoff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
263b3a8eb9SGleb Smirnoff * SUCH DAMAGE.
273b3a8eb9SGleb Smirnoff */
283b3a8eb9SGleb Smirnoff
293b3a8eb9SGleb Smirnoff /*
303b3a8eb9SGleb Smirnoff * internal dummynet APIs.
313b3a8eb9SGleb Smirnoff */
323b3a8eb9SGleb Smirnoff
333b3a8eb9SGleb Smirnoff #ifndef _IP_DN_PRIVATE_H
343b3a8eb9SGleb Smirnoff #define _IP_DN_PRIVATE_H
353b3a8eb9SGleb Smirnoff
363b3a8eb9SGleb Smirnoff /* debugging support
373b3a8eb9SGleb Smirnoff * use ND() to remove debugging, D() to print a line,
383b3a8eb9SGleb Smirnoff * DX(level, ...) to print above a certain level
393b3a8eb9SGleb Smirnoff * If you redefine D() you are expected to redefine all.
403b3a8eb9SGleb Smirnoff */
413b3a8eb9SGleb Smirnoff #ifndef D
423b3a8eb9SGleb Smirnoff #define ND(fmt, ...) do {} while (0)
433b3a8eb9SGleb Smirnoff #define D1(fmt, ...) do {} while (0)
443b3a8eb9SGleb Smirnoff #define D(fmt, ...) printf("%-10s " fmt "\n", \
453b3a8eb9SGleb Smirnoff __FUNCTION__, ## __VA_ARGS__)
463b3a8eb9SGleb Smirnoff #define DX(lev, fmt, ...) do { \
47fe3bcfbdSTom Jones if (V_dn_cfg.debug > lev) D(fmt, ## __VA_ARGS__); } while (0)
483b3a8eb9SGleb Smirnoff #endif
493b3a8eb9SGleb Smirnoff
503b3a8eb9SGleb Smirnoff MALLOC_DECLARE(M_DUMMYNET);
513b3a8eb9SGleb Smirnoff
523b3a8eb9SGleb Smirnoff #ifndef __linux__
533b3a8eb9SGleb Smirnoff #define div64(a, b) ((int64_t)(a) / (int64_t)(b))
543b3a8eb9SGleb Smirnoff #endif
553b3a8eb9SGleb Smirnoff
563b3a8eb9SGleb Smirnoff #define DN_LOCK_INIT() do { \
57fe3bcfbdSTom Jones mtx_init(&V_dn_cfg.uh_mtx, "dn_uh", NULL, MTX_DEF); \
58fe3bcfbdSTom Jones mtx_init(&V_dn_cfg.bh_mtx, "dn_bh", NULL, MTX_DEF); \
593b3a8eb9SGleb Smirnoff } while (0)
603b3a8eb9SGleb Smirnoff #define DN_LOCK_DESTROY() do { \
61fe3bcfbdSTom Jones mtx_destroy(&V_dn_cfg.uh_mtx); \
62fe3bcfbdSTom Jones mtx_destroy(&V_dn_cfg.bh_mtx); \
633b3a8eb9SGleb Smirnoff } while (0)
643b3a8eb9SGleb Smirnoff #if 0 /* not used yet */
65fe3bcfbdSTom Jones #define DN_UH_RLOCK() mtx_lock(&V_dn_cfg.uh_mtx)
66fe3bcfbdSTom Jones #define DN_UH_RUNLOCK() mtx_unlock(&V_dn_cfg.uh_mtx)
67fe3bcfbdSTom Jones #define DN_UH_WLOCK() mtx_lock(&V_dn_cfg.uh_mtx)
68fe3bcfbdSTom Jones #define DN_UH_WUNLOCK() mtx_unlock(&V_dn_cfg.uh_mtx)
69fe3bcfbdSTom Jones #define DN_UH_LOCK_ASSERT() mtx_assert(&V_dn_cfg.uh_mtx, MA_OWNED)
703b3a8eb9SGleb Smirnoff #endif
713b3a8eb9SGleb Smirnoff
72fe3bcfbdSTom Jones #define DN_BH_RLOCK() mtx_lock(&V_dn_cfg.uh_mtx)
73fe3bcfbdSTom Jones #define DN_BH_RUNLOCK() mtx_unlock(&V_dn_cfg.uh_mtx)
74fe3bcfbdSTom Jones #define DN_BH_WLOCK() mtx_lock(&V_dn_cfg.uh_mtx)
75fe3bcfbdSTom Jones #define DN_BH_WUNLOCK() mtx_unlock(&V_dn_cfg.uh_mtx)
76fe3bcfbdSTom Jones #define DN_BH_LOCK_ASSERT() mtx_assert(&V_dn_cfg.uh_mtx, MA_OWNED)
773b3a8eb9SGleb Smirnoff
783b3a8eb9SGleb Smirnoff SLIST_HEAD(dn_fsk_head, dn_fsk);
7991336b40SDon Lewis
803b3a8eb9SGleb Smirnoff struct mq { /* a basic queue of packets*/
813b3a8eb9SGleb Smirnoff struct mbuf *head, *tail;
8241d10f90SLuigi Rizzo int count;
833b3a8eb9SGleb Smirnoff };
843b3a8eb9SGleb Smirnoff
853b3a8eb9SGleb Smirnoff static inline void
set_oid(struct dn_id * o,int type,int len)863b3a8eb9SGleb Smirnoff set_oid(struct dn_id *o, int type, int len)
873b3a8eb9SGleb Smirnoff {
883b3a8eb9SGleb Smirnoff o->type = type;
893b3a8eb9SGleb Smirnoff o->len = len;
903b3a8eb9SGleb Smirnoff o->subtype = 0;
91352bc63dSLuigi Rizzo }
923b3a8eb9SGleb Smirnoff
933b3a8eb9SGleb Smirnoff /*
94fe3bcfbdSTom Jones * configuration and data for a dummynet instance
953b3a8eb9SGleb Smirnoff *
963b3a8eb9SGleb Smirnoff * When a configuration is modified from userland, 'id' is incremented
973b3a8eb9SGleb Smirnoff * so we can use the value to check for stale pointers.
983b3a8eb9SGleb Smirnoff */
993b3a8eb9SGleb Smirnoff struct dn_parms {
1003b3a8eb9SGleb Smirnoff uint32_t id; /* configuration version */
1013b3a8eb9SGleb Smirnoff
1023b3a8eb9SGleb Smirnoff /* defaults (sysctl-accessible) */
1033b3a8eb9SGleb Smirnoff int red_lookup_depth;
1043b3a8eb9SGleb Smirnoff int red_avg_pkt_size;
1053b3a8eb9SGleb Smirnoff int red_max_pkt_size;
1063b3a8eb9SGleb Smirnoff int hash_size;
1073b3a8eb9SGleb Smirnoff int max_hash_size;
1083b3a8eb9SGleb Smirnoff long byte_limit; /* max queue sizes */
1093b3a8eb9SGleb Smirnoff long slot_limit;
1103b3a8eb9SGleb Smirnoff
1113b3a8eb9SGleb Smirnoff int io_fast;
1123b3a8eb9SGleb Smirnoff int debug;
1133b3a8eb9SGleb Smirnoff
1143b3a8eb9SGleb Smirnoff /* timekeeping */
1153b3a8eb9SGleb Smirnoff struct timeval prev_t; /* last time dummynet_tick ran */
1163b3a8eb9SGleb Smirnoff struct dn_heap evheap; /* scheduled events */
1173b3a8eb9SGleb Smirnoff
118320bed3cSKristof Provost long tick_last; /* Last tick duration (usec). */
119320bed3cSKristof Provost long tick_delta; /* Last vs standard tick diff (usec). */
120320bed3cSKristof Provost long tick_delta_sum; /* Accumulated tick difference (usec).*/
121320bed3cSKristof Provost long tick_adjustment; /* Tick adjustments done. */
122320bed3cSKristof Provost long tick_lost; /* Lost(coalesced) ticks number. */
123320bed3cSKristof Provost /* Adjusted vs non-adjusted curr_time difference (ticks). */
124320bed3cSKristof Provost long tick_diff;
125320bed3cSKristof Provost
1263b3a8eb9SGleb Smirnoff /* counters of objects -- used for reporting space */
1273b3a8eb9SGleb Smirnoff int schk_count;
1283b3a8eb9SGleb Smirnoff int si_count;
1293b3a8eb9SGleb Smirnoff int fsk_count;
1303b3a8eb9SGleb Smirnoff int queue_count;
1313b3a8eb9SGleb Smirnoff
132cd5671efSKristof Provost /* packet counters */
133cd5671efSKristof Provost unsigned long io_pkt;
134cd5671efSKristof Provost unsigned long io_pkt_fast;
135cd5671efSKristof Provost unsigned long io_pkt_drop;
136cd5671efSKristof Provost
1373b3a8eb9SGleb Smirnoff /* ticks and other stuff */
1383b3a8eb9SGleb Smirnoff uint64_t curr_time;
1393b3a8eb9SGleb Smirnoff /* flowsets and schedulers are in hash tables, with 'hash_size'
1403b3a8eb9SGleb Smirnoff * buckets. fshash is looked up at every packet arrival
1413b3a8eb9SGleb Smirnoff * so better be generous if we expect many entries.
1423b3a8eb9SGleb Smirnoff */
1433b3a8eb9SGleb Smirnoff struct dn_ht *fshash;
1443b3a8eb9SGleb Smirnoff struct dn_ht *schedhash;
1453b3a8eb9SGleb Smirnoff /* list of flowsets without a scheduler -- use sch_chain */
1463b3a8eb9SGleb Smirnoff struct dn_fsk_head fsu; /* list of unlinked flowsets */
1473b3a8eb9SGleb Smirnoff
1483b3a8eb9SGleb Smirnoff /* Store the fs/sch to scan when draining. The value is the
1493b3a8eb9SGleb Smirnoff * bucket number of the hash table. Expire can be disabled
1503b3a8eb9SGleb Smirnoff * with net.inet.ip.dummynet.expire=0, or it happens every
1513b3a8eb9SGleb Smirnoff * expire ticks.
1523b3a8eb9SGleb Smirnoff **/
1533b3a8eb9SGleb Smirnoff int drain_fs;
1543b3a8eb9SGleb Smirnoff int drain_sch;
1553b3a8eb9SGleb Smirnoff uint32_t expire;
1563b3a8eb9SGleb Smirnoff uint32_t expire_cycle; /* tick count */
1573b3a8eb9SGleb Smirnoff
1583b3a8eb9SGleb Smirnoff int init_done;
1593b3a8eb9SGleb Smirnoff
1603b3a8eb9SGleb Smirnoff #ifdef _KERNEL
1613b3a8eb9SGleb Smirnoff /*
1623b3a8eb9SGleb Smirnoff * This file is normally used in the kernel, unless we do
1633b3a8eb9SGleb Smirnoff * some userland tests, in which case we do not need a mtx.
1643b3a8eb9SGleb Smirnoff * uh_mtx arbitrates between system calls and also
1653b3a8eb9SGleb Smirnoff * protects fshash, schedhash and fsunlinked.
1663b3a8eb9SGleb Smirnoff * These structures are readonly for the lower half.
1673b3a8eb9SGleb Smirnoff * bh_mtx protects all other structures which may be
1683b3a8eb9SGleb Smirnoff * modified upon packet arrivals
1693b3a8eb9SGleb Smirnoff */
1703b3a8eb9SGleb Smirnoff #if defined( __linux__ ) || defined( _WIN32 )
1713b3a8eb9SGleb Smirnoff spinlock_t uh_mtx;
1723b3a8eb9SGleb Smirnoff spinlock_t bh_mtx;
1733b3a8eb9SGleb Smirnoff #else
1743b3a8eb9SGleb Smirnoff struct mtx uh_mtx;
1753b3a8eb9SGleb Smirnoff struct mtx bh_mtx;
1763b3a8eb9SGleb Smirnoff #endif
1773b3a8eb9SGleb Smirnoff
1783b3a8eb9SGleb Smirnoff #endif /* _KERNEL */
1793b3a8eb9SGleb Smirnoff };
1803b3a8eb9SGleb Smirnoff
1813b3a8eb9SGleb Smirnoff /*
1823b3a8eb9SGleb Smirnoff * Delay line, contains all packets on output from a link.
1833b3a8eb9SGleb Smirnoff * Every scheduler instance has one.
1843b3a8eb9SGleb Smirnoff */
1853b3a8eb9SGleb Smirnoff struct delay_line {
1863b3a8eb9SGleb Smirnoff struct dn_id oid;
1873b3a8eb9SGleb Smirnoff struct dn_sch_inst *si;
1883b3a8eb9SGleb Smirnoff struct mq mq;
1893b3a8eb9SGleb Smirnoff };
1903b3a8eb9SGleb Smirnoff
1913b3a8eb9SGleb Smirnoff /*
1923b3a8eb9SGleb Smirnoff * The kernel side of a flowset. It is linked in a hash table
1933b3a8eb9SGleb Smirnoff * of flowsets, and in a list of children of their parent scheduler.
1943b3a8eb9SGleb Smirnoff * qht is either the queue or (if HAVE_MASK) a hash table queues.
1953b3a8eb9SGleb Smirnoff * Note that the mask to use is the (flow_mask|sched_mask), which
1963b3a8eb9SGleb Smirnoff * changes as we attach/detach schedulers. So we store it here.
1973b3a8eb9SGleb Smirnoff *
1983b3a8eb9SGleb Smirnoff * XXX If we want to add scheduler-specific parameters, we need to
1993b3a8eb9SGleb Smirnoff * put them in external storage because the scheduler may not be
2003b3a8eb9SGleb Smirnoff * available when the fsk is created.
2013b3a8eb9SGleb Smirnoff */
2023b3a8eb9SGleb Smirnoff struct dn_fsk { /* kernel side of a flowset */
2033b3a8eb9SGleb Smirnoff struct dn_fs fs;
2043b3a8eb9SGleb Smirnoff SLIST_ENTRY(dn_fsk) fsk_next; /* hash chain for fshash */
2053b3a8eb9SGleb Smirnoff
2063b3a8eb9SGleb Smirnoff struct ipfw_flow_id fsk_mask;
2073b3a8eb9SGleb Smirnoff
2083b3a8eb9SGleb Smirnoff /* qht is a hash table of queues, or just a single queue
2093b3a8eb9SGleb Smirnoff * a bit in fs.flags tells us which one
2103b3a8eb9SGleb Smirnoff */
2113b3a8eb9SGleb Smirnoff struct dn_ht *qht;
2123b3a8eb9SGleb Smirnoff struct dn_schk *sched; /* Sched we are linked to */
2133b3a8eb9SGleb Smirnoff SLIST_ENTRY(dn_fsk) sch_chain; /* list of fsk attached to sched */
2143b3a8eb9SGleb Smirnoff
2153b3a8eb9SGleb Smirnoff /* bucket index used by drain routine to drain queues for this
2163b3a8eb9SGleb Smirnoff * flowset
2173b3a8eb9SGleb Smirnoff */
2183b3a8eb9SGleb Smirnoff int drain_bucket;
2193b3a8eb9SGleb Smirnoff /* Parameter realted to RED / GRED */
2203b3a8eb9SGleb Smirnoff /* original values are in dn_fs*/
2213b3a8eb9SGleb Smirnoff int w_q ; /* queue weight (scaled) */
2223b3a8eb9SGleb Smirnoff int max_th ; /* maximum threshold for queue (scaled) */
2233b3a8eb9SGleb Smirnoff int min_th ; /* minimum threshold for queue (scaled) */
2243b3a8eb9SGleb Smirnoff int max_p ; /* maximum value for p_b (scaled) */
2253b3a8eb9SGleb Smirnoff
2263b3a8eb9SGleb Smirnoff u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */
2273b3a8eb9SGleb Smirnoff u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */
2283b3a8eb9SGleb Smirnoff u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */
2293b3a8eb9SGleb Smirnoff u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */
2303b3a8eb9SGleb Smirnoff u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */
2313b3a8eb9SGleb Smirnoff u_int lookup_depth ; /* depth of lookup table */
2323b3a8eb9SGleb Smirnoff int lookup_step ; /* granularity inside the lookup table */
2333b3a8eb9SGleb Smirnoff int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
2343b3a8eb9SGleb Smirnoff int avg_pkt_size ; /* medium packet size */
2353b3a8eb9SGleb Smirnoff int max_pkt_size ; /* max packet size */
23691336b40SDon Lewis #ifdef NEW_AQM
23791336b40SDon Lewis struct dn_aqm *aqmfp; /* Pointer to AQM functions */
23891336b40SDon Lewis void *aqmcfg; /* configuration parameters for AQM */
23991336b40SDon Lewis #endif
2403b3a8eb9SGleb Smirnoff };
2413b3a8eb9SGleb Smirnoff
2423b3a8eb9SGleb Smirnoff /*
2433b3a8eb9SGleb Smirnoff * A queue is created as a child of a flowset unless it belongs to
2443b3a8eb9SGleb Smirnoff * a !MULTIQUEUE scheduler. It is normally in a hash table in the
2453b3a8eb9SGleb Smirnoff * flowset. fs always points to the parent flowset.
2463b3a8eb9SGleb Smirnoff * si normally points to the sch_inst, unless the flowset has been
2473b3a8eb9SGleb Smirnoff * detached from the scheduler -- in this case si == NULL and we
2483b3a8eb9SGleb Smirnoff * should not enqueue.
2493b3a8eb9SGleb Smirnoff */
2503b3a8eb9SGleb Smirnoff struct dn_queue {
2513b3a8eb9SGleb Smirnoff struct dn_flow ni; /* oid, flow_id, stats */
2523b3a8eb9SGleb Smirnoff struct mq mq; /* packets queue */
2533b3a8eb9SGleb Smirnoff struct dn_sch_inst *_si; /* owner scheduler instance */
2543b3a8eb9SGleb Smirnoff SLIST_ENTRY(dn_queue) q_next; /* hash chain list for qht */
2553b3a8eb9SGleb Smirnoff struct dn_fsk *fs; /* parent flowset. */
2563b3a8eb9SGleb Smirnoff
2573b3a8eb9SGleb Smirnoff /* RED parameters */
2583b3a8eb9SGleb Smirnoff int avg; /* average queue length est. (scaled) */
2593b3a8eb9SGleb Smirnoff int count; /* arrivals since last RED drop */
2603b3a8eb9SGleb Smirnoff int random; /* random value (scaled) */
2613b3a8eb9SGleb Smirnoff uint64_t q_time; /* start of queue idle time */
26291336b40SDon Lewis #ifdef NEW_AQM
26391336b40SDon Lewis void *aqm_status; /* per-queue status variables*/
26491336b40SDon Lewis #endif
2653b3a8eb9SGleb Smirnoff
2663b3a8eb9SGleb Smirnoff };
2673b3a8eb9SGleb Smirnoff
2683b3a8eb9SGleb Smirnoff /*
2693b3a8eb9SGleb Smirnoff * The kernel side of a scheduler. Contains the userland config,
2703b3a8eb9SGleb Smirnoff * a link, pointer to extra config arguments from command line,
2713b3a8eb9SGleb Smirnoff * kernel flags, and a pointer to the scheduler methods.
2723b3a8eb9SGleb Smirnoff * It is stored in a hash table, and holds a list of all
2733b3a8eb9SGleb Smirnoff * flowsets and scheduler instances.
2743b3a8eb9SGleb Smirnoff * XXX sch must be at the beginning, see schk_hash().
2753b3a8eb9SGleb Smirnoff */
2763b3a8eb9SGleb Smirnoff struct dn_schk {
2773b3a8eb9SGleb Smirnoff struct dn_sch sch;
2783b3a8eb9SGleb Smirnoff struct dn_alg *fp; /* Pointer to scheduler functions */
2793b3a8eb9SGleb Smirnoff struct dn_link link; /* The link, embedded */
2803b3a8eb9SGleb Smirnoff struct dn_profile *profile; /* delay profile, if any */
2813b3a8eb9SGleb Smirnoff struct dn_id *cfg; /* extra config arguments */
2823b3a8eb9SGleb Smirnoff
2833b3a8eb9SGleb Smirnoff SLIST_ENTRY(dn_schk) schk_next; /* hash chain for schedhash */
2843b3a8eb9SGleb Smirnoff
2853b3a8eb9SGleb Smirnoff struct dn_fsk_head fsk_list; /* all fsk linked to me */
2863b3a8eb9SGleb Smirnoff struct dn_fsk *fs; /* Flowset for !MULTIQUEUE */
2873b3a8eb9SGleb Smirnoff
2883b3a8eb9SGleb Smirnoff /* bucket index used by the drain routine to drain the scheduler
2893b3a8eb9SGleb Smirnoff * instance for this flowset.
2903b3a8eb9SGleb Smirnoff */
2913b3a8eb9SGleb Smirnoff int drain_bucket;
2923b3a8eb9SGleb Smirnoff
2933b3a8eb9SGleb Smirnoff /* Hash table of all instances (through sch.sched_mask)
2943b3a8eb9SGleb Smirnoff * or single instance if no mask. Always valid.
2953b3a8eb9SGleb Smirnoff */
2963b3a8eb9SGleb Smirnoff struct dn_ht *siht;
2973b3a8eb9SGleb Smirnoff };
2983b3a8eb9SGleb Smirnoff
2993b3a8eb9SGleb Smirnoff /*
3003b3a8eb9SGleb Smirnoff * Scheduler instance.
3013b3a8eb9SGleb Smirnoff * Contains variables and all queues relative to a this instance.
3023b3a8eb9SGleb Smirnoff * This struct is created a runtime.
3033b3a8eb9SGleb Smirnoff */
3043b3a8eb9SGleb Smirnoff struct dn_sch_inst {
3053b3a8eb9SGleb Smirnoff struct dn_flow ni; /* oid, flowid and stats */
3063b3a8eb9SGleb Smirnoff SLIST_ENTRY(dn_sch_inst) si_next; /* hash chain for siht */
3073b3a8eb9SGleb Smirnoff struct delay_line dline;
3083b3a8eb9SGleb Smirnoff struct dn_schk *sched; /* the template */
3093b3a8eb9SGleb Smirnoff int kflags; /* DN_ACTIVE */
3103b3a8eb9SGleb Smirnoff
3113b3a8eb9SGleb Smirnoff int64_t credit; /* bits I can transmit (more or less). */
3123b3a8eb9SGleb Smirnoff uint64_t sched_time; /* time link was scheduled in ready_heap */
3133b3a8eb9SGleb Smirnoff uint64_t idle_time; /* start of scheduler instance idle time */
3143b3a8eb9SGleb Smirnoff
3153b3a8eb9SGleb Smirnoff /* q_count is the number of queues that this instance is using.
3163b3a8eb9SGleb Smirnoff * The counter is incremented or decremented when
3173b3a8eb9SGleb Smirnoff * a reference from the queue is created or deleted.
3183b3a8eb9SGleb Smirnoff * It is used to make sure that a scheduler instance can be safely
3193b3a8eb9SGleb Smirnoff * deleted by the drain routine. See notes below.
3203b3a8eb9SGleb Smirnoff */
3213b3a8eb9SGleb Smirnoff int q_count;
3223b3a8eb9SGleb Smirnoff
3233b3a8eb9SGleb Smirnoff };
3243b3a8eb9SGleb Smirnoff
3253b3a8eb9SGleb Smirnoff /*
3263b3a8eb9SGleb Smirnoff * NOTE about object drain.
3273b3a8eb9SGleb Smirnoff * The system will automatically (XXX check when) drain queues and
3283b3a8eb9SGleb Smirnoff * scheduler instances when they are idle.
3293b3a8eb9SGleb Smirnoff * A queue is idle when it has no packets; an instance is idle when
3303b3a8eb9SGleb Smirnoff * it is not in the evheap heap, and the corresponding delay line is empty.
3313b3a8eb9SGleb Smirnoff * A queue can be safely deleted when it is idle because of the scheduler
3323b3a8eb9SGleb Smirnoff * function xxx_free_queue() will remove any references to it.
3333b3a8eb9SGleb Smirnoff * An instance can be only deleted when no queues reference it. To be sure
3343b3a8eb9SGleb Smirnoff * of that, a counter (q_count) stores the number of queues that are pointing
3353b3a8eb9SGleb Smirnoff * to the instance.
3363b3a8eb9SGleb Smirnoff *
3373b3a8eb9SGleb Smirnoff * XXX
3383b3a8eb9SGleb Smirnoff * Order of scan:
3393b3a8eb9SGleb Smirnoff * - take all flowset in a bucket for the flowset hash table
3403b3a8eb9SGleb Smirnoff * - take all queues in a bucket for the flowset
3413b3a8eb9SGleb Smirnoff * - increment the queue bucket
3423b3a8eb9SGleb Smirnoff * - scan next flowset bucket
3433b3a8eb9SGleb Smirnoff * Nothing is done if a bucket contains no entries.
3443b3a8eb9SGleb Smirnoff *
3453b3a8eb9SGleb Smirnoff * The same schema is used for sceduler instances
3463b3a8eb9SGleb Smirnoff */
3473b3a8eb9SGleb Smirnoff
3483b3a8eb9SGleb Smirnoff /* kernel-side flags. Linux has DN_DELETE in fcntl.h
3493b3a8eb9SGleb Smirnoff */
3503b3a8eb9SGleb Smirnoff enum {
3513b3a8eb9SGleb Smirnoff /* 1 and 2 are reserved for the SCAN flags */
3523b3a8eb9SGleb Smirnoff DN_DESTROY = 0x0004, /* destroy */
3533b3a8eb9SGleb Smirnoff DN_DELETE_FS = 0x0008, /* destroy flowset */
3543b3a8eb9SGleb Smirnoff DN_DETACH = 0x0010,
3553b3a8eb9SGleb Smirnoff DN_ACTIVE = 0x0020, /* object is in evheap */
3563b3a8eb9SGleb Smirnoff DN_F_DLINE = 0x0040, /* object is a delay line */
3573b3a8eb9SGleb Smirnoff DN_DEL_SAFE = 0x0080, /* delete a queue only if no longer needed
3583b3a8eb9SGleb Smirnoff * by scheduler */
3593b3a8eb9SGleb Smirnoff DN_QHT_IS_Q = 0x0100, /* in flowset, qht is a single queue */
3603b3a8eb9SGleb Smirnoff };
3613b3a8eb9SGleb Smirnoff
3624001fcbeSDon Lewis /*
3634001fcbeSDon Lewis * Packets processed by dummynet have an mbuf tag associated with
3644001fcbeSDon Lewis * them that carries their dummynet state.
3654001fcbeSDon Lewis * Outside dummynet, only the 'rule' field is relevant, and it must
3664001fcbeSDon Lewis * be at the beginning of the structure.
3674001fcbeSDon Lewis */
3684001fcbeSDon Lewis struct dn_pkt_tag {
3694001fcbeSDon Lewis struct ipfw_rule_ref rule; /* matching rule */
3704001fcbeSDon Lewis
3714001fcbeSDon Lewis /* second part, dummynet specific */
3724001fcbeSDon Lewis int dn_dir; /* action when packet comes out.*/
3734001fcbeSDon Lewis /* see ip_fw_private.h */
3744001fcbeSDon Lewis uint64_t output_time; /* when the pkt is due for delivery*/
37512c542cdSKristof Provost uint16_t if_index;
37612c542cdSKristof Provost uint16_t if_idxgen;
3774001fcbeSDon Lewis uint16_t iphdr_off; /* IP header offset for mtodo() */
3784001fcbeSDon Lewis };
3794001fcbeSDon Lewis
380dc0fa4f7SGleb Smirnoff /*
381dc0fa4f7SGleb Smirnoff * Possible values for dn_dir. XXXGL: this needs to be reviewed
382dc0fa4f7SGleb Smirnoff * and converted to same values ip_fw_args.flags use.
383dc0fa4f7SGleb Smirnoff */
384dc0fa4f7SGleb Smirnoff enum {
385dc0fa4f7SGleb Smirnoff DIR_OUT = 0,
386dc0fa4f7SGleb Smirnoff DIR_IN = 1,
387dc0fa4f7SGleb Smirnoff DIR_FWD = 2,
388dc0fa4f7SGleb Smirnoff DIR_DROP = 3,
389dc0fa4f7SGleb Smirnoff PROTO_LAYER2 = 0x4, /* set for layer 2 */
390dc0fa4f7SGleb Smirnoff PROTO_IPV4 = 0x08,
391dc0fa4f7SGleb Smirnoff PROTO_IPV6 = 0x10,
392dc0fa4f7SGleb Smirnoff PROTO_IFB = 0x0c, /* layer2 + ifbridge */
393dc0fa4f7SGleb Smirnoff };
394dc0fa4f7SGleb Smirnoff
39531cf66d7SRichard Scheffenegger /*
39631cf66d7SRichard Scheffenegger * States for the Packet Loss Rate Gilbert-Elliott
39731cf66d7SRichard Scheffenegger * channel model
39831cf66d7SRichard Scheffenegger */
39931cf66d7SRichard Scheffenegger enum {
40031cf66d7SRichard Scheffenegger PLR_STATE_G = 0,
40131cf66d7SRichard Scheffenegger PLR_STATE_B,
40231cf66d7SRichard Scheffenegger };
40331cf66d7SRichard Scheffenegger
404fe3bcfbdSTom Jones //extern struct dn_parms V_dn_cfg;
405fe3bcfbdSTom Jones VNET_DECLARE(struct dn_parms, dn_cfg);
406fe3bcfbdSTom Jones #define V_dn_cfg VNET(dn_cfg)
4073b3a8eb9SGleb Smirnoff
408dc0fa4f7SGleb Smirnoff int dummynet_io(struct mbuf **, struct ip_fw_args *);
4093f3e4f3cSKristof Provost void dummynet_sched_lock(void);
4103f3e4f3cSKristof Provost void dummynet_sched_unlock(void);
4113b3a8eb9SGleb Smirnoff void dummynet_task(void *context, int pending);
4123b3a8eb9SGleb Smirnoff void dn_reschedule(void);
4134001fcbeSDon Lewis struct dn_pkt_tag * dn_tag_get(struct mbuf *m);
4143b3a8eb9SGleb Smirnoff
4153b3a8eb9SGleb Smirnoff struct dn_queue *ipdn_q_find(struct dn_fsk *, struct dn_sch_inst *,
4163b3a8eb9SGleb Smirnoff struct ipfw_flow_id *);
4173b3a8eb9SGleb Smirnoff struct dn_sch_inst *ipdn_si_find(struct dn_schk *, struct ipfw_flow_id *);
4183b3a8eb9SGleb Smirnoff
4193b3a8eb9SGleb Smirnoff /*
4203b3a8eb9SGleb Smirnoff * copy_range is a template for requests for ranges of pipes/queues/scheds.
4213b3a8eb9SGleb Smirnoff * The number of ranges is variable and can be derived by o.len.
4223b3a8eb9SGleb Smirnoff * As a default, we use a small number of entries so that the struct
4233b3a8eb9SGleb Smirnoff * fits easily on the stack and is sufficient for most common requests.
4243b3a8eb9SGleb Smirnoff */
4253b3a8eb9SGleb Smirnoff #define DEFAULT_RANGES 5
4263b3a8eb9SGleb Smirnoff struct copy_range {
4273b3a8eb9SGleb Smirnoff struct dn_id o;
4283b3a8eb9SGleb Smirnoff uint32_t r[ 2 * DEFAULT_RANGES ];
4293b3a8eb9SGleb Smirnoff };
4303b3a8eb9SGleb Smirnoff
4313b3a8eb9SGleb Smirnoff struct copy_args {
4323b3a8eb9SGleb Smirnoff char **start;
4333b3a8eb9SGleb Smirnoff char *end;
4343b3a8eb9SGleb Smirnoff int flags;
4353b3a8eb9SGleb Smirnoff int type;
4363b3a8eb9SGleb Smirnoff struct copy_range *extra; /* extra filtering */
4373b3a8eb9SGleb Smirnoff };
4383b3a8eb9SGleb Smirnoff
4393b3a8eb9SGleb Smirnoff struct sockopt;
4403b3a8eb9SGleb Smirnoff int ip_dummynet_compat(struct sockopt *sopt);
4413b3a8eb9SGleb Smirnoff int dummynet_get(struct sockopt *sopt, void **compat);
4423b3a8eb9SGleb Smirnoff int dn_c_copy_q (void *_ni, void *arg);
4433b3a8eb9SGleb Smirnoff int dn_c_copy_pipe(struct dn_schk *s, struct copy_args *a, int nq);
4443b3a8eb9SGleb Smirnoff int dn_c_copy_fs(struct dn_fsk *f, struct copy_args *a, int nq);
4453b3a8eb9SGleb Smirnoff int dn_compat_copy_queue(struct copy_args *a, void *_o);
4463b3a8eb9SGleb Smirnoff int dn_compat_copy_pipe(struct copy_args *a, void *_o);
4473b3a8eb9SGleb Smirnoff int copy_data_helper_compat(void *_o, void *_arg);
4483b3a8eb9SGleb Smirnoff int dn_compat_calc_size(void);
4491c732c85SMark Johnston int do_config(void *p, size_t l);
4503b3a8eb9SGleb Smirnoff
4513b3a8eb9SGleb Smirnoff /* function to drain idle object */
4523b3a8eb9SGleb Smirnoff void dn_drain_scheduler(void);
4533b3a8eb9SGleb Smirnoff void dn_drain_queue(void);
4543b3a8eb9SGleb Smirnoff
45591336b40SDon Lewis #ifdef NEW_AQM
45691336b40SDon Lewis int ecn_mark(struct mbuf* m);
45791336b40SDon Lewis
45891336b40SDon Lewis /* moved from ip_dn_io.c to here to be available for AQMs modules*/
45991336b40SDon Lewis static inline void
mq_append(struct mq * q,struct mbuf * m)46091336b40SDon Lewis mq_append(struct mq *q, struct mbuf *m)
46191336b40SDon Lewis {
46291336b40SDon Lewis #ifdef USERSPACE
46391336b40SDon Lewis // buffers from netmap need to be copied
46491336b40SDon Lewis // XXX note that the routine is not expected to fail
46591336b40SDon Lewis ND("append %p to %p", m, q);
46691336b40SDon Lewis if (m->m_flags & M_STACK) {
46791336b40SDon Lewis struct mbuf *m_new;
46891336b40SDon Lewis void *p;
46991336b40SDon Lewis int l, ofs;
47091336b40SDon Lewis
47191336b40SDon Lewis ofs = m->m_data - m->__m_extbuf;
47291336b40SDon Lewis // XXX allocate
47391336b40SDon Lewis MGETHDR(m_new, M_NOWAIT, MT_DATA);
47491336b40SDon Lewis ND("*** WARNING, volatile buf %p ext %p %d dofs %d m_new %p",
47591336b40SDon Lewis m, m->__m_extbuf, m->__m_extlen, ofs, m_new);
47691336b40SDon Lewis p = m_new->__m_extbuf; /* new pointer */
47791336b40SDon Lewis l = m_new->__m_extlen; /* new len */
47891336b40SDon Lewis if (l <= m->__m_extlen) {
47991336b40SDon Lewis panic("extlen too large");
48091336b40SDon Lewis }
48191336b40SDon Lewis
48291336b40SDon Lewis *m_new = *m; // copy
48391336b40SDon Lewis m_new->m_flags &= ~M_STACK;
48491336b40SDon Lewis m_new->__m_extbuf = p; // point to new buffer
48591336b40SDon Lewis _pkt_copy(m->__m_extbuf, p, m->__m_extlen);
48691336b40SDon Lewis m_new->m_data = p + ofs;
48791336b40SDon Lewis m = m_new;
48891336b40SDon Lewis }
48991336b40SDon Lewis #endif /* USERSPACE */
49091336b40SDon Lewis if (q->head == NULL)
49191336b40SDon Lewis q->head = m;
49291336b40SDon Lewis else
49391336b40SDon Lewis q->tail->m_nextpkt = m;
49491336b40SDon Lewis q->count++;
49591336b40SDon Lewis q->tail = m;
49691336b40SDon Lewis m->m_nextpkt = NULL;
49791336b40SDon Lewis }
49891336b40SDon Lewis #endif /* NEW_AQM */
49991336b40SDon Lewis
5003b3a8eb9SGleb Smirnoff #endif /* _IP_DN_PRIVATE_H */
501