1/*
2 * Copyright (c) 2011-2016 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
67extern "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 */
79#define QFCF_DELAYBASED 0x2000 /* queue sizing is delay based */
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
101struct 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 */
191enum 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
199struct qfq_group;
200
201struct 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 sfb *sfb; /* SFB state */
208 } cl_qalg;
209 struct qfq_if *cl_qif; /* back pointer to qif */
210 u_int32_t cl_flags; /* class flags */
211
212 u_int64_t cl_S, cl_F; /* flow timestamps (exact) */
213 struct qfq_class *cl_next; /* link for the slot list */
214 /*
215 * Group we belong to. In principle we would need the index,
216 * which is log_2(lmax/weight), but we never reference it
217 * directly, only the group.
218 */
219 struct qfq_group *cl_grp;
220 u_int32_t cl_inv_w; /* QFQ_ONE_FP/weight */
221 u_int32_t cl_lmax; /* max packet size for this flow */
222
223 /* statistics */
224 u_int32_t cl_period; /* backlog period */
225 struct pktcntr cl_xmitcnt; /* transmitted packet counter */
226 struct pktcntr cl_dropcnt; /* dropped packet counter */
227};
228
229#define cl_sfb cl_qalg.sfb
230
231/*
232 * Group descriptor, see the paper for details.
233 * Basically this contains the bucket lists.
234 */
235struct qfq_group {
236 u_int64_t qfg_S, qfg_F; /* group timestamps (approx) */
237 u_int8_t qfg_slot_shift; /* slot shift */
238 u_int8_t qfg_index; /* group index */
239 u_int8_t qfg_front; /* index of the front slot */
240 pktsched_bitmap_t qfg_full_slots; /* non-empty slots */
241
242 /* array of lists of active classes */
243 struct qfq_class **qfg_slots;
244};
245
246/*
247 * qfq interface state
248 */
249struct qfq_if {
250 struct ifclassq *qif_ifq; /* backpointer to ifclassq */
251 u_int32_t qif_throttle; /* throttling level */
252 u_int8_t qif_classes; /* # of classes in table */
253 u_int8_t qif_maxclasses; /* max # of classes in table */
254 u_int8_t qif_maxslots; /* max # of slots */
255 struct qfq_class *qif_default; /* default class */
256 struct qfq_class **qif_class_tbl;
257
258 u_int64_t qif_V; /* precise virtual time */
259 u_int32_t qif_wsum; /* weight sum */
260#if QFQ_DEBUG
261 u_int32_t qif_i_wsum; /* QFQ_ONE_FP/w_sum */
262 u_int32_t qif_queued; /* debugging */
263 u_int32_t qif_emptygrp; /* debugging */
264#endif /* QFQ_DEBUG */
265 pktsched_bitmap_t qif_bitmaps[QFQ_MAX_STATE]; /* group bitmaps */
266 struct qfq_group **qif_groups; /* the groups */
267};
268
269#define QFQIF_IFP(_qif) ((_qif)->qif_ifq->ifcq_ifp)
270
271struct if_ifclassq_stats;
272
273extern void qfq_init(void);
274extern struct qfq_if *qfq_alloc(struct ifnet *, int);
275extern int qfq_destroy(struct qfq_if *);
276extern void qfq_purge(struct qfq_if *);
277extern void qfq_event(struct qfq_if *, cqev_t);
278extern int qfq_add_queue(struct qfq_if *, u_int32_t, u_int32_t, u_int32_t,
279 u_int32_t, u_int32_t, struct qfq_class **, classq_pkt_type_t);
280extern int qfq_remove_queue(struct qfq_if *, u_int32_t);
281extern int qfq_get_class_stats(struct qfq_if *, u_int32_t,
282 struct qfq_classstats *);
283extern int qfq_enqueue(struct qfq_if *, struct qfq_class *, pktsched_pkt_t *,
284 struct pf_mtag *);
285extern void qfq_dequeue(struct qfq_if *, pktsched_pkt_t *);
286extern int qfq_setup_ifclassq(struct ifclassq *, u_int32_t, classq_pkt_type_t);
287extern int qfq_teardown_ifclassq(struct ifclassq *ifq);
288extern int qfq_getqstats_ifclassq(struct ifclassq *, u_int32_t,
289 struct if_ifclassq_stats *);
290#endif /* BSD_KERNEL_PRIVATE */
291#ifdef __cplusplus
292}
293#endif
294#endif /* PRIVATE */
295#endif /* _NET_PKTSCHED_PKTSCHED_QFQ_H_ */
296