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 |
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 */ |
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 | |
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 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 | */ |
235 | struct 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 | */ |
249 | struct 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 | |
271 | struct if_ifclassq_stats; |
272 | |
273 | extern void qfq_init(void); |
274 | extern struct qfq_if *qfq_alloc(struct ifnet *, int); |
275 | extern int qfq_destroy(struct qfq_if *); |
276 | extern void qfq_purge(struct qfq_if *); |
277 | extern void qfq_event(struct qfq_if *, cqev_t); |
278 | extern 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); |
280 | extern int qfq_remove_queue(struct qfq_if *, u_int32_t); |
281 | extern int qfq_get_class_stats(struct qfq_if *, u_int32_t, |
282 | struct qfq_classstats *); |
283 | extern int qfq_enqueue(struct qfq_if *, struct qfq_class *, pktsched_pkt_t *, |
284 | struct pf_mtag *); |
285 | extern void qfq_dequeue(struct qfq_if *, pktsched_pkt_t *); |
286 | extern int qfq_setup_ifclassq(struct ifclassq *, u_int32_t, classq_pkt_type_t); |
287 | extern int qfq_teardown_ifclassq(struct ifclassq *ifq); |
288 | extern 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 | |