[apple/xnu.git] / bsd / net / pktsched / pktsched_qfq.h

/*
 * Copyright (c) 2011-2012 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

/*
 * Copyright (c) 2010 Fabio Checconi, Luigi Rizzo, Paolo Valente
 * All rights reserved
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef _NET_PKTSCHED_PKTSCHED_QFQ_H_
#define	_NET_PKTSCHED_PKTSCHED_QFQ_H_

#ifdef PRIVATE
#include <net/pktsched/pktsched.h>
#include <net/classq/classq.h>
#include <net/classq/classq_red.h>
#include <net/classq/classq_rio.h>
#include <net/classq/classq_blue.h>
#include <net/classq/classq_sfb.h>

#ifdef __cplusplus
extern "C" {
#endif

/* qfq class flags */
#define	QFCF_RED		0x0001	/* use RED */
#define	QFCF_ECN		0x0002  /* use ECN with RED/BLUE/SFB */
#define	QFCF_RIO		0x0004  /* use RIO */
#define	QFCF_CLEARDSCP		0x0010  /* clear diffserv codepoint */
#define	QFCF_BLUE		0x0100	/* use BLUE */
#define	QFCF_SFB		0x0200	/* use SFB */
#define	QFCF_FLOWCTL		0x0400	/* enable flow control advisories */
#define	QFCF_DEFAULTCLASS	0x1000	/* default class */
#define	QFCF_DELAYBASED		0x2000	/* queue sizing is delay based */
#ifdef BSD_KERNEL_PRIVATE
#define	QFCF_LAZY		0x10000000 /* on-demand resource allocation */
#endif /* BSD_KERNEL_PRIVATE */

#define	QFCF_USERFLAGS							\
	(QFCF_RED | QFCF_ECN | QFCF_RIO | QFCF_CLEARDSCP | QFCF_BLUE |	\
	QFCF_SFB | QFCF_FLOWCTL | QFCF_DEFAULTCLASS)

#ifdef BSD_KERNEL_PRIVATE
#define	QFCF_BITS \
	"\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT" \
	"\35LAZY"
#else
#define	QFCF_BITS \
	"\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT"
#endif /* !BSD_KERNEL_PRIVATE */

#define	QFQ_MAX_CLASSES		32
#define	QFQ_MAX_WSHIFT		16	/* log2(max_weight) */
#define	QFQ_MAX_WEIGHT		(1 << QFQ_MAX_WSHIFT)

struct qfq_classstats {
	u_int32_t		class_handle;
	u_int32_t		index;
	u_int32_t		weight;
	u_int32_t		lmax;

	u_int32_t		qlength;
	u_int32_t		qlimit;
	u_int32_t		period;
	struct pktcntr		xmitcnt;  /* transmitted packet counter */
	struct pktcntr		dropcnt;  /* dropped packet counter */

	/* RED, RIO, BLUE, SFB related info */
	classq_type_t		qtype;
	union {
		/* RIO has 3 red stats */
		struct red_stats	red[RIO_NDROPPREC];
		struct blue_stats	blue;
		struct sfb_stats	sfb;
	};
	classq_state_t		qstate;
};

#ifdef BSD_KERNEL_PRIVATE
#define	QFQ_DEBUG	1	/* enable extra debugging */

/*
 * Virtual time computations.
 *
 * S, F and V are all computed in fixed point arithmetic with
 * FRAC_BITS decimal bits.
 *
 * QFQ_MAX_INDEX is the maximum index allowed for a group. We need
 * one bit per index.
 *
 * QFQ_MAX_WSHIFT is the maximum power of two supported as a weight.
 * The layout of the bits is as below:
 *
 *                 [ MTU_SHIFT ][      FRAC_BITS    ]
 *                 [ MAX_INDEX    ][ MIN_SLOT_SHIFT ]
 *				 ^.__grp->index = 0
 *				 *.__grp->slot_shift
 *
 * where MIN_SLOT_SHIFT is derived by difference from the others.
 *
 * The max group index corresponds to Lmax/w_min, where
 *	Lmax=1<<MTU_SHIFT, w_min = 1 .
 * From this, and knowing how many groups (MAX_INDEX) we want,
 * we can derive the shift corresponding to each group.
 *
 * Because we often need to compute
 *	F = S + len/w_i  and V = V + len/wsum
 * instead of storing w_i store the value
 *	inv_w = (1<<FRAC_BITS)/w_i
 * so we can do F = S + len * inv_w * wsum.
 * We use W_TOT in the formulas so we can easily move between
 * static and adaptive weight sum.
 *
 * The per-scheduler-instance data contain all the data structures
 * for the scheduler: bitmaps and bucket lists.
 */

/*
 * Shifts used for class<->group mapping.  Class weights are in the
 * range [1, QFQ_MAX_WEIGHT], we need to map each class i to the
 * group with the smallest index that can support the L_i / r_i
 * configured for the class.
 *
 * grp->qfg_index is the index of the group; and grp->qfg_slot_shift
 * is the shift for the corresponding (scaled) sigma_i.
 *
 * When computing the group index, we do (len<<FP_SHIFT)/weight,
 * then compute an FLS (which is like a log2()), and if the result
 * is below the MAX_INDEX region we use 0 (which is the same as
 * using a larger len).
 */
#define	QFQ_MAX_INDEX		19
#define	QFQ_MAX_WSUM		(2 * QFQ_MAX_WEIGHT)

#define	QFQ_FRAC_BITS		30	/* fixed point arithmetic */
#define	QFQ_ONE_FP		(1UL << QFQ_FRAC_BITS)
#define	QFQ_IWSUM		(QFQ_ONE_FP / QFQ_MAX_WSUM)

#define	QFQ_MTU_SHIFT		11	/* log2(max_len) */
#define	QFQ_MIN_SLOT_SHIFT	(QFQ_FRAC_BITS + QFQ_MTU_SHIFT - QFQ_MAX_INDEX)

/*
 * Possible group states, also indexes for the bitmaps array in
 * struct qfq_if. We rely on ER, IR, EB, IB being numbered 0..3
 */
enum qfq_state {
	ER = 0,				/* eligible, ready */
	IR = 1,				/* ineligible, ready */
	EB = 2,				/* eligible, backlogged */
	IB = 3,				/* ineligible, backlogged */
	QFQ_MAX_STATE
};

struct qfq_group;

struct qfq_class {
	u_int32_t	cl_handle;	/* class handle */
	class_queue_t	cl_q;		/* class queue structure */
	u_int32_t	cl_qflags;	/* class queue flags */
	union {
		void		*ptr;
		struct red	*red;	/* RED state */
		struct rio	*rio;	/* RIO state */
		struct blue	*blue;	/* BLUE state */
		struct sfb	*sfb;	/* SFB state */
	} cl_qalg;
	struct qfq_if	*cl_qif;	/* back pointer to qif */
	u_int32_t	cl_flags;	/* class flags */

	u_int64_t	cl_S, cl_F;	/* flow timestamps (exact) */
	struct qfq_class *cl_next;	/* link for the slot list */
	/*
	 * Group we belong to.  In principle we would need the index,
	 * which is log_2(lmax/weight), but we never reference it
	 * directly, only the group.
	 */
	struct qfq_group *cl_grp;
	u_int32_t	cl_inv_w;	/* QFQ_ONE_FP/weight */
	u_int32_t	cl_lmax;	/* max packet size for this flow */

	/* statistics */
	u_int32_t	cl_period;	/* backlog period */
	struct pktcntr  cl_xmitcnt;	/* transmitted packet counter */
	struct pktcntr  cl_dropcnt;	/* dropped packet counter */
};

#define	cl_red	cl_qalg.red
#define	cl_rio	cl_qalg.rio
#define	cl_blue	cl_qalg.blue
#define	cl_sfb	cl_qalg.sfb

/*
 * Group descriptor, see the paper for details.
 * Basically this contains the bucket lists.
 */
struct qfq_group {
	u_int64_t	qfg_S, qfg_F;	/* group timestamps (approx) */
	u_int8_t	qfg_slot_shift;	/* slot shift */
	u_int8_t	qfg_index;	/* group index */
	u_int8_t	qfg_front;	/* index of the front slot */
	pktsched_bitmap_t qfg_full_slots; /* non-empty slots */

	/* array of lists of active classes */
	struct qfq_class **qfg_slots;
};

/* qfq_if flags */
#define	QFQIFF_ALTQ		0x1	/* configured via PF/ALTQ */

/*
 * qfq interface state
 */
struct qfq_if {
	struct ifclassq		*qif_ifq;	/* backpointer to ifclassq */
	u_int32_t		qif_flags;	/* flags */
	u_int32_t		qif_throttle;	/* throttling level */
	u_int8_t		qif_classes;	/* # of classes in table */
	u_int8_t		qif_maxclasses;	/* max # of classes in table */
	u_int8_t		qif_maxslots;	/* max # of slots */
	struct qfq_class	*qif_default;	/* default class */
	struct qfq_class	**qif_class_tbl;

	u_int64_t		qif_V;		/* precise virtual time */
	u_int32_t		qif_wsum;	/* weight sum */
#if QFQ_DEBUG
	u_int32_t		qif_i_wsum;	/* QFQ_ONE_FP/w_sum */
	u_int32_t		qif_queued;	/* debugging */
	u_int32_t		qif_emptygrp;	/* debugging */
#endif /* QFQ_DEBUG */
	pktsched_bitmap_t	qif_bitmaps[QFQ_MAX_STATE]; /* group bitmaps */
	struct qfq_group	**qif_groups;	/* the groups */
};

#define	QFQIF_IFP(_qif)	((_qif)->qif_ifq->ifcq_ifp)

struct if_ifclassq_stats;

extern void qfq_init(void);
extern struct qfq_if *qfq_alloc(struct ifnet *, int, boolean_t);
extern int qfq_destroy(struct qfq_if *);
extern void qfq_purge(struct qfq_if *);
extern void qfq_event(struct qfq_if *, cqev_t);
extern int qfq_add_queue(struct qfq_if *, u_int32_t, u_int32_t, u_int32_t,
    u_int32_t, u_int32_t, struct qfq_class **);
extern int qfq_remove_queue(struct qfq_if *, u_int32_t);
extern int qfq_get_class_stats(struct qfq_if *, u_int32_t,
    struct qfq_classstats *);
extern int qfq_enqueue(struct qfq_if *, struct qfq_class *, struct mbuf *,
    struct pf_mtag *);
extern struct mbuf *qfq_dequeue(struct qfq_if *, cqdq_op_t);
extern int qfq_setup_ifclassq(struct ifclassq *, u_int32_t);
extern int qfq_teardown_ifclassq(struct ifclassq *ifq);
extern int qfq_getqstats_ifclassq(struct ifclassq *, u_int32_t,
    struct if_ifclassq_stats *);
#endif /* BSD_KERNEL_PRIVATE */
#ifdef __cplusplus
}
#endif
#endif /* PRIVATE */
#endif /* _NET_PKTSCHED_PKTSCHED_QFQ_H_ */
Commit	Line	Data
316670eb A	1	/*
	2	* Copyright (c) 2011-2012 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28
	29	/*
	30	* Copyright (c) 2010 Fabio Checconi, Luigi Rizzo, Paolo Valente
	31	* All rights reserved
	32	*
	33	* Redistribution and use in source and binary forms, with or without
	34	* modification, are permitted provided that the following conditions
	35	* are met:
	36	* 1. Redistributions of source code must retain the above copyright
	37	* notice, this list of conditions and the following disclaimer.
	38	* 2. Redistributions in binary form must reproduce the above copyright
	39	* notice, this list of conditions and the following disclaimer in the
	40	* documentation and/or other materials provided with the distribution.
	41	*
	42	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	43	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	44	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	45	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	46	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	47	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	48	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	49	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	50	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	51	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	52	* SUCH DAMAGE.
	53	*/
	54
	55	#ifndef _NET_PKTSCHED_PKTSCHED_QFQ_H_
	56	#define _NET_PKTSCHED_PKTSCHED_QFQ_H_
	57
	58	#ifdef PRIVATE
	59	#include <net/pktsched/pktsched.h>
	60	#include <net/classq/classq.h>
	61	#include <net/classq/classq_red.h>
	62	#include <net/classq/classq_rio.h>
	63	#include <net/classq/classq_blue.h>
	64	#include <net/classq/classq_sfb.h>
65
66	#ifdef __cplusplus
67	extern "C" {
68	#endif
69
70	/* qfq class flags */
71	#define QFCF_RED 0x0001 /* use RED */
72	#define QFCF_ECN 0x0002 /* use ECN with RED/BLUE/SFB */
73	#define QFCF_RIO 0x0004 /* use RIO */
74	#define QFCF_CLEARDSCP 0x0010 /* clear diffserv codepoint */
75	#define QFCF_BLUE 0x0100 /* use BLUE */
76	#define QFCF_SFB 0x0200 /* use SFB */
77	#define QFCF_FLOWCTL 0x0400 /* enable flow control advisories */
78	#define QFCF_DEFAULTCLASS 0x1000 /* default class */
fe8ab488	79	#define QFCF_DELAYBASED 0x2000 /* queue sizing is delay based */
316670eb A	80	#ifdef BSD_KERNEL_PRIVATE
	81	#define QFCF_LAZY 0x10000000 /* on-demand resource allocation */
	82	#endif /* BSD_KERNEL_PRIVATE */
	83
	84	#define QFCF_USERFLAGS \
	85	(QFCF_RED \| QFCF_ECN \| QFCF_RIO \| QFCF_CLEARDSCP \| QFCF_BLUE \| \
	86	QFCF_SFB \| QFCF_FLOWCTL \| QFCF_DEFAULTCLASS)
	87
	88	#ifdef BSD_KERNEL_PRIVATE
	89	#define QFCF_BITS \
	90	"\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT" \
	91	"\35LAZY"
	92	#else
	93	#define QFCF_BITS \
	94	"\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT"
	95	#endif /* !BSD_KERNEL_PRIVATE */
	96
	97	#define QFQ_MAX_CLASSES 32
	98	#define QFQ_MAX_WSHIFT 16 /* log2(max_weight) */
	99	#define QFQ_MAX_WEIGHT (1 << QFQ_MAX_WSHIFT)
	100
	101	struct qfq_classstats {
	102	u_int32_t class_handle;
	103	u_int32_t index;
	104	u_int32_t weight;
	105	u_int32_t lmax;
	106
	107	u_int32_t qlength;
	108	u_int32_t qlimit;
	109	u_int32_t period;
	110	struct pktcntr xmitcnt; /* transmitted packet counter */
	111	struct pktcntr dropcnt; /* dropped packet counter */
	112
	113	/* RED, RIO, BLUE, SFB related info */
	114	classq_type_t qtype;
	115	union {
	116	/* RIO has 3 red stats */
	117	struct red_stats red[RIO_NDROPPREC];
	118	struct blue_stats blue;
	119	struct sfb_stats sfb;
	120	};
	121	classq_state_t qstate;
	122	};
	123
	124	#ifdef BSD_KERNEL_PRIVATE
	125	#define QFQ_DEBUG 1 /* enable extra debugging */
	126
	127	/*
	128	* Virtual time computations.
	129	*
	130	* S, F and V are all computed in fixed point arithmetic with
	131	* FRAC_BITS decimal bits.
	132	*
	133	* QFQ_MAX_INDEX is the maximum index allowed for a group. We need
	134	* one bit per index.
	135	*
	136	* QFQ_MAX_WSHIFT is the maximum power of two supported as a weight.
	137	* The layout of the bits is as below:
	138	*
	139	* [ MTU_SHIFT ][ FRAC_BITS ]
	140	* [ MAX_INDEX ][ MIN_SLOT_SHIFT ]
	141	* ^.__grp->index = 0
	142	* *.__grp->slot_shift
	143	*
144	* where MIN_SLOT_SHIFT is derived by difference from the others.
145	*
146	* The max group index corresponds to Lmax/w_min, where
147	* Lmax=1<<MTU_SHIFT, w_min = 1 .
148	* From this, and knowing how many groups (MAX_INDEX) we want,
149	* we can derive the shift corresponding to each group.
150	*
151	* Because we often need to compute
152	* F = S + len/w_i and V = V + len/wsum
153	* instead of storing w_i store the value
154	* inv_w = (1<<FRAC_BITS)/w_i
155	* so we can do F = S + len * inv_w * wsum.
156	* We use W_TOT in the formulas so we can easily move between
157	* static and adaptive weight sum.
158	*
159	* The per-scheduler-instance data contain all the data structures
160	* for the scheduler: bitmaps and bucket lists.
161	*/
162
163	/*
164	* Shifts used for class<->group mapping. Class weights are in the
165	* range [1, QFQ_MAX_WEIGHT], we need to map each class i to the
166	* group with the smallest index that can support the L_i / r_i
167	* configured for the class.
168	*
169	* grp->qfg_index is the index of the group; and grp->qfg_slot_shift
170	* is the shift for the corresponding (scaled) sigma_i.
171	*
172	* When computing the group index, we do (len<<FP_SHIFT)/weight,
173	* then compute an FLS (which is like a log2()), and if the result
174	* is below the MAX_INDEX region we use 0 (which is the same as
175	* using a larger len).
176	*/
177	#define QFQ_MAX_INDEX 19
178	#define QFQ_MAX_WSUM (2 * QFQ_MAX_WEIGHT)
179
180	#define QFQ_FRAC_BITS 30 /* fixed point arithmetic */
181	#define QFQ_ONE_FP (1UL << QFQ_FRAC_BITS)
182	#define QFQ_IWSUM (QFQ_ONE_FP / QFQ_MAX_WSUM)
183
184	#define QFQ_MTU_SHIFT 11 /* log2(max_len) */
185	#define QFQ_MIN_SLOT_SHIFT (QFQ_FRAC_BITS + QFQ_MTU_SHIFT - QFQ_MAX_INDEX)
186
187	/*
188	* Possible group states, also indexes for the bitmaps array in
189	* struct qfq_if. We rely on ER, IR, EB, IB being numbered 0..3
190	*/
191	enum qfq_state {
192	ER = 0, /* eligible, ready */
193	IR = 1, /* ineligible, ready */
194	EB = 2, /* eligible, backlogged */
195	IB = 3, /* ineligible, backlogged */
196	QFQ_MAX_STATE
197	};
198
199	struct qfq_group;
200
201	struct qfq_class {
202	u_int32_t cl_handle; /* class handle */
203	class_queue_t cl_q; /* class queue structure */
204	u_int32_t cl_qflags; /* class queue flags */
205	union {
206	void *ptr;
207	struct red red; / RED state */
208	struct rio rio; / RIO state */
209	struct blue blue; / BLUE state */
210	struct sfb sfb; / SFB state */
211	} cl_qalg;
212	struct qfq_if cl_qif; / back pointer to qif */
213	u_int32_t cl_flags; /* class flags */
214
215	u_int64_t cl_S, cl_F; /* flow timestamps (exact) */
216	struct qfq_class cl_next; / link for the slot list */
217	/*
218	* Group we belong to. In principle we would need the index,
219	* which is log_2(lmax/weight), but we never reference it
220	* directly, only the group.
221	*/
222	struct qfq_group *cl_grp;
223	u_int32_t cl_inv_w; /* QFQ_ONE_FP/weight */
224	u_int32_t cl_lmax; /* max packet size for this flow */
225
226	/* statistics */
227	u_int32_t cl_period; /* backlog period */
228	struct pktcntr cl_xmitcnt; /* transmitted packet counter */
229	struct pktcntr cl_dropcnt; /* dropped packet counter */
230	};
231
232	#define cl_red cl_qalg.red
233	#define cl_rio cl_qalg.rio
234	#define cl_blue cl_qalg.blue
235	#define cl_sfb cl_qalg.sfb
236
237	/*
238	* Group descriptor, see the paper for details.
239	* Basically this contains the bucket lists.
240	*/
241	struct qfq_group {
242	u_int64_t qfg_S, qfg_F; /* group timestamps (approx) */
243	u_int8_t qfg_slot_shift; /* slot shift */
244	u_int8_t qfg_index; /* group index */
245	u_int8_t qfg_front; /* index of the front slot */
246	pktsched_bitmap_t qfg_full_slots; /* non-empty slots */
247
248	/* array of lists of active classes */
249	struct qfq_class **qfg_slots;
250	};
251
252	/* qfq_if flags */
253	#define QFQIFF_ALTQ 0x1 /* configured via PF/ALTQ */
254
255	/*
256	* qfq interface state
257	*/
258	struct qfq_if {
259	struct ifclassq qif_ifq; / backpointer to ifclassq */
260	u_int32_t qif_flags; /* flags */
261	u_int32_t qif_throttle; /* throttling level */
262	u_int8_t qif_classes; /* # of classes in table */
263	u_int8_t qif_maxclasses; /* max # of classes in table */
264	u_int8_t qif_maxslots; /* max # of slots */
265	struct qfq_class qif_default; / default class */
266	struct qfq_class **qif_class_tbl;
267
268	u_int64_t qif_V; /* precise virtual time */
269	u_int32_t qif_wsum; /* weight sum */
270	#if QFQ_DEBUG
271	u_int32_t qif_i_wsum; /* QFQ_ONE_FP/w_sum */
272	u_int32_t qif_queued; /* debugging */
273	u_int32_t qif_emptygrp; /* debugging */
274	#endif /* QFQ_DEBUG */
275	pktsched_bitmap_t qif_bitmaps[QFQ_MAX_STATE]; /* group bitmaps */
276	struct qfq_group *qif_groups; / the groups */
277	};
278
279	#define QFQIF_IFP(_qif) ((_qif)->qif_ifq->ifcq_ifp)
280
281	struct if_ifclassq_stats;
282
283	extern void qfq_init(void);
284	extern struct qfq_if qfq_alloc(struct ifnet , int, boolean_t);
285	extern int qfq_destroy(struct qfq_if *);
286	extern void qfq_purge(struct qfq_if *);
287	extern void qfq_event(struct qfq_if *, cqev_t);
288	extern int qfq_add_queue(struct qfq_if *, u_int32_t, u_int32_t, u_int32_t,
289	u_int32_t, u_int32_t, struct qfq_class **);
290	extern int qfq_remove_queue(struct qfq_if *, u_int32_t);
291	extern int qfq_get_class_stats(struct qfq_if *, u_int32_t,
292	struct qfq_classstats *);
293	extern int qfq_enqueue(struct qfq_if , struct qfq_class , struct mbuf *,
294	struct pf_mtag *);
295	extern struct mbuf qfq_dequeue(struct qfq_if , cqdq_op_t);
296	extern int qfq_setup_ifclassq(struct ifclassq *, u_int32_t);
297	extern int qfq_teardown_ifclassq(struct ifclassq *ifq);
298	extern int qfq_getqstats_ifclassq(struct ifclassq *, u_int32_t,
299	struct if_ifclassq_stats *);
300	#endif /* BSD_KERNEL_PRIVATE */
301	#ifdef __cplusplus
302	}
303	#endif
304	#endif /* PRIVATE */
305	#endif /* _NET_PKTSCHED_PKTSCHED_QFQ_H_ */