1 | /* |
2 | * Copyright (c) 2016-2021 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 | #ifndef _NET_CLASSQ_CLASSQ_FQ_CODEL_H |
30 | #define _NET_CLASSQ_CLASSQ_FQ_CODEL_H |
31 | #ifdef PRIVATE |
32 | #ifdef BSD_KERNEL_PRIVATE |
33 | #include <stdbool.h> |
34 | #include <sys/time.h> |
35 | #include <net/flowadv.h> |
36 | #include <net/classq/if_classq.h> |
37 | #if SKYWALK |
38 | #include <skywalk/os_skywalk_private.h> |
39 | #endif /* SKYWALK */ |
40 | |
41 | #ifdef __cplusplus |
42 | extern "C" { |
43 | #endif |
44 | |
45 | #define AQM_KTRACE_AON_FLOW_HIGH_DELAY AQMDBG_CODE(DBG_AQM_ALWAYSON, 0x001) |
46 | #define AQM_KTRACE_AON_THROTTLE AQMDBG_CODE(DBG_AQM_ALWAYSON, 0x002) |
47 | #define AQM_KTRACE_AON_FLOW_OVERWHELMING AQMDBG_CODE(DBG_AQM_ALWAYSON, 0x003) |
48 | #define AQM_KTRACE_AON_FLOW_DQ_STALL AQMDBG_CODE(DBG_AQM_ALWAYSON, 0x004) |
49 | |
50 | #define AQM_KTRACE_STATS_FLOW_ENQUEUE AQMDBG_CODE(DBG_AQM_STATS, 0x001) |
51 | #define AQM_KTRACE_STATS_FLOW_DEQUEUE AQMDBG_CODE(DBG_AQM_STATS, 0x002) |
52 | #define AQM_KTRACE_STATS_FLOW_CTL AQMDBG_CODE(DBG_AQM_STATS, 0x003) |
53 | #define AQM_KTRACE_STATS_FLOW_ALLOC AQMDBG_CODE(DBG_AQM_STATS, 0x004) |
54 | #define AQM_KTRACE_STATS_FLOW_DESTROY AQMDBG_CODE(DBG_AQM_STATS, 0x005) |
55 | #define AQM_KTRACE_STATS_FLOW_REPORT_CE AQMDBG_CODE(DBG_AQM_STATS, 0x006) |
56 | #define AQM_KTRACE_STATS_GET_QLEN AQMDBG_CODE(DBG_AQM_STATS, 0x007) |
57 | #define AQM_KTRACE_TX_NOT_READY AQMDBG_CODE(DBG_AQM_STATS, 0x008) |
58 | #define AQM_KTRACE_TX_PACEMAKER AQMDBG_CODE(DBG_AQM_STATS, 0x009) |
59 | |
60 | #define AQM_KTRACE_FQ_GRP_SC_IDX(_fq_) \ |
61 | ((_fq_)->fq_group->fqg_index << 4 | (_fq_)->fq_sc_index) |
62 | |
63 | #define FQ_MIN_FC_THRESHOLD_BYTES 7500 |
64 | #define FQ_IS_DELAY_HIGH(_fq_) ((_fq_)->fq_flags & FQF_DELAY_HIGH) |
65 | #define FQ_SET_DELAY_HIGH(_fq_) do { \ |
66 | if (!FQ_IS_DELAY_HIGH(_fq_)) { \ |
67 | KDBG(AQM_KTRACE_AON_FLOW_HIGH_DELAY | DBG_FUNC_START, \ |
68 | (_fq_)->fq_flowhash, AQM_KTRACE_FQ_GRP_SC_IDX((_fq_)), \ |
69 | (_fq_)->fq_bytes, (_fq_)->fq_min_qdelay); \ |
70 | } \ |
71 | (_fq_)->fq_flags |= FQF_DELAY_HIGH; \ |
72 | } while (0) |
73 | #define FQ_CLEAR_DELAY_HIGH(_fq_) do { \ |
74 | if (FQ_IS_DELAY_HIGH(_fq_)) { \ |
75 | KDBG(AQM_KTRACE_AON_FLOW_HIGH_DELAY | DBG_FUNC_END, \ |
76 | (_fq_)->fq_flowhash, AQM_KTRACE_FQ_GRP_SC_IDX((_fq_)), \ |
77 | (_fq_)->fq_bytes, (_fq_)->fq_min_qdelay); \ |
78 | } \ |
79 | (_fq_)->fq_flags &= ~FQF_DELAY_HIGH; \ |
80 | } while (0) |
81 | |
82 | #define FQ_IS_OVERWHELMING(_fq_) ((_fq_)->fq_flags & FQF_OVERWHELMING) |
83 | #define FQ_SET_OVERWHELMING(_fq_) do { \ |
84 | if (!FQ_IS_OVERWHELMING(_fq_)) { \ |
85 | KDBG(AQM_KTRACE_AON_FLOW_OVERWHELMING | DBG_FUNC_START, \ |
86 | (_fq_)->fq_flowhash, AQM_KTRACE_FQ_GRP_SC_IDX((_fq_)), \ |
87 | (_fq_)->fq_bytes, (_fq_)->fq_min_qdelay); \ |
88 | } \ |
89 | (_fq_)->fq_flags |= FQF_OVERWHELMING; \ |
90 | } while (0) |
91 | #define FQ_CLEAR_OVERWHELMING(_fq_) do { \ |
92 | if (FQ_IS_OVERWHELMING(_fq_)) { \ |
93 | KDBG(AQM_KTRACE_AON_FLOW_OVERWHELMING | DBG_FUNC_END, \ |
94 | (_fq_)->fq_flowhash, AQM_KTRACE_FQ_GRP_SC_IDX((_fq_)), \ |
95 | (_fq_)->fq_bytes, (_fq_)->fq_min_qdelay); \ |
96 | } \ |
97 | (_fq_)->fq_flags &= ~FQF_OVERWHELMING; \ |
98 | } while (0) |
99 | |
100 | /* |
101 | * time (in ns) the flow queue can stay in empty state. |
102 | */ |
103 | #define FQ_EMPTY_PURGE_DELAY (3ULL * 1000 * 1000 * 1000) |
104 | |
105 | /* |
106 | * maximum number of flow queues which can be purged during a dequeue. |
107 | */ |
108 | #define FQ_EMPTY_PURGE_MAX 4 |
109 | |
110 | #define FQ_INVALID_TX_TS UINT64_MAX |
111 | |
112 | struct flowq { |
113 | #pragma pack(push,1) |
114 | union { |
115 | MBUFQ_HEAD(mbufq_head) __mbufq; /* mbuf packet queue */ |
116 | #if SKYWALK |
117 | KPKTQ_HEAD(kpktq_head) __kpktq; /* skywalk packet queue */ |
118 | #endif /* SKYWALK */ |
119 | } __fq_pktq_u; |
120 | #pragma pack(pop) |
121 | uint32_t fq_flowhash; /* Flow hash */ |
122 | uint32_t fq_bytes; /* Number of bytes in the queue */ |
123 | int32_t fq_deficit; /* Deficit for scheduling */ |
124 | fq_if_group_t *fq_group; /* Back pointer to the group */ |
125 | #define FQF_FLOWCTL_CAPABLE 0x01 /* Use flow control instead of drop */ |
126 | #define FQF_DELAY_HIGH 0x02 /* Min delay is greater than target */ |
127 | #define FQF_NEW_FLOW 0x04 /* Currently on new flows queue */ |
128 | #define FQF_OLD_FLOW 0x08 /* Currently on old flows queue */ |
129 | #define FQF_FLOWCTL_ON 0x10 /* Currently flow controlled */ |
130 | #define FQF_EMPTY_FLOW 0x20 /* Currently on empty flows queue */ |
131 | #define FQF_OVERWHELMING 0x40 /* The largest flow when AQM hits queue limit */ |
132 | #define FQF_FRESH_FLOW 0x80 /* The flow queue has just been allocated */ |
133 | uint8_t fq_flags; /* flags */ |
134 | uint8_t fq_sc_index; /* service_class index */ |
135 | bool fq_in_dqlist; |
136 | fq_tfc_type_t fq_tfc_type; |
137 | uint8_t __fq_pad_uint8[4]; |
138 | uint64_t fq_min_qdelay; /* min queue delay for Codel */ |
139 | uint64_t fq_getqtime; /* last dequeue time */ |
140 | /* total pkt count since last congestion event report */ |
141 | uint32_t fq_pkts_since_last_report; |
142 | /* the next time that a paced packet is ready to go*/ |
143 | uint64_t fq_next_tx_time; |
144 | union { |
145 | uint64_t fq_updatetime; /* next update interval */ |
146 | /* empty list purge time (in nanoseconds) */ |
147 | uint64_t fq_empty_purge_time; |
148 | }; |
149 | SLIST_ENTRY(flowq) fq_hashlink; /* for flow queue hash table */ |
150 | /* |
151 | * flow queue will only be on either one of the lists. |
152 | */ |
153 | union { |
154 | STAILQ_ENTRY(flowq) fq_actlink; /* for new/old flow queues */ |
155 | /* entry on empty flow queue list */ |
156 | TAILQ_ENTRY(flowq) fq_empty_link; |
157 | }; |
158 | /* entry on dequeue flow list */ |
159 | STAILQ_ENTRY(flowq) fq_dqlink; |
160 | /* temporary packet queue for dequeued packets */ |
161 | classq_pkt_t fq_dq_head; |
162 | classq_pkt_t fq_dq_tail; |
163 | }; |
164 | |
165 | typedef struct flowq fq_t; |
166 | |
167 | #define FQF_FLOW_STATE_MASK (FQF_DELAY_HIGH | FQF_NEW_FLOW | \ |
168 | FQF_OLD_FLOW | FQF_FLOWCTL_ON | FQF_EMPTY_FLOW) |
169 | |
170 | #define fq_mbufq __fq_pktq_u.__mbufq |
171 | #if SKYWALK |
172 | #define fq_kpktq __fq_pktq_u.__kpktq |
173 | #endif /* SKYWALK */ |
174 | |
175 | #if SKYWALK |
176 | #define fq_empty(_q, _ptype) (((_ptype) == QP_MBUF) ? \ |
177 | MBUFQ_EMPTY(&(_q)->fq_mbufq) : KPKTQ_EMPTY(&(_q)->fq_kpktq)) |
178 | #else /* !SKYWALK */ |
179 | #define fq_empty(_q, _ptype) MBUFQ_EMPTY(&(_q)->fq_mbufq) |
180 | #endif /* !SKYWALK */ |
181 | |
182 | #if SKYWALK |
183 | #define fq_enqueue(_q, _h, _t, _c, _ptype) do { \ |
184 | switch (_ptype) { \ |
185 | case QP_MBUF: \ |
186 | ASSERT((_h).cp_ptype == QP_MBUF); \ |
187 | ASSERT((_t).cp_ptype == QP_MBUF); \ |
188 | MBUFQ_ENQUEUE_MULTI(&(_q)->fq_mbufq, (_h).cp_mbuf, \ |
189 | (_t).cp_mbuf); \ |
190 | MBUFQ_ADD_CRUMB_MULTI(&(_q)->fq_mbufq, (_h).cp_mbuf, \ |
191 | (_t).cp_mbuf, PKT_CRUMB_FQ_ENQUEUE); \ |
192 | break; \ |
193 | case QP_PACKET: \ |
194 | ASSERT((_h).cp_ptype == QP_PACKET); \ |
195 | ASSERT((_t).cp_ptype == QP_PACKET); \ |
196 | KPKTQ_ENQUEUE_MULTI(&(_q)->fq_kpktq, (_h).cp_kpkt, \ |
197 | (_t).cp_kpkt, (_c)); \ |
198 | break; \ |
199 | default: \ |
200 | VERIFY(0); \ |
201 | __builtin_unreachable(); \ |
202 | break; \ |
203 | } \ |
204 | } while (0) |
205 | #else /* !SKYWALK */ |
206 | #define fq_enqueue(_q, _h, _t, _c, _ptype) { \ |
207 | MBUFQ_ENQUEUE_MULTI(&(_q)->fq_mbufq, (_h).cp_mbuf, (_t).cp_mbuf); \ |
208 | MBUFQ_ADD_CRUMB_MULTI(&(_q)->fq_mbufq, (_h).cp_mbuf, \ |
209 | (_t).cp_mbuf, PKT_CRUMB_FQ_ENQUEUE); \ |
210 | } while (0) |
211 | #endif /* !SKYWALK */ |
212 | |
213 | #if SKYWALK |
214 | #define fq_dequeue(_q, _p, _ptype) do { \ |
215 | switch (_ptype) { \ |
216 | case QP_MBUF: { \ |
217 | MBUFQ_DEQUEUE(&(_q)->fq_mbufq, (_p)->cp_mbuf); \ |
218 | if (__probable((_p)->cp_mbuf != NULL)) { \ |
219 | CLASSQ_PKT_INIT_MBUF((_p), (_p)->cp_mbuf); \ |
220 | m_add_crumb((_p)->cp_mbuf, \ |
221 | PKT_CRUMB_FQ_DEQUEUE); \ |
222 | } \ |
223 | break; \ |
224 | } \ |
225 | case QP_PACKET: { \ |
226 | KPKTQ_DEQUEUE(&(_q)->fq_kpktq, (_p)->cp_kpkt); \ |
227 | if (__probable((_p)->cp_kpkt != NULL)) { \ |
228 | CLASSQ_PKT_INIT_PACKET((_p), (_p)->cp_kpkt); \ |
229 | } \ |
230 | break; \ |
231 | } \ |
232 | default: \ |
233 | VERIFY(0); \ |
234 | __builtin_unreachable(); \ |
235 | break; \ |
236 | } \ |
237 | } while (0) |
238 | #else /* !SKYWALK */ |
239 | #define fq_dequeue(_q, _p, _ptype) do { \ |
240 | MBUFQ_DEQUEUE(&(_q)->fq_mbufq, (_p)->cp_mbuf); \ |
241 | if (__probable((_p)->cp_mbuf != NULL)) { \ |
242 | CLASSQ_PKT_INIT_MBUF((_p), (_p)->cp_mbuf); \ |
243 | m_add_crumb((_p)->cp_mbuf, PKT_CRUMB_FQ_DEQUEUE); \ |
244 | } \ |
245 | } while (0) |
246 | #endif /* !SKYWALK */ |
247 | |
248 | struct fq_codel_sched_data; |
249 | struct fq_if_classq; |
250 | |
251 | /* Function definitions */ |
252 | extern void fq_codel_init(void); |
253 | extern fq_t *fq_alloc(classq_pkt_type_t); |
254 | extern void fq_destroy(fq_t *, classq_pkt_type_t); |
255 | extern int fq_addq(struct fq_codel_sched_data *, fq_if_group_t *, |
256 | pktsched_pkt_t *, struct fq_if_classq *); |
257 | extern void fq_getq_flow(struct fq_codel_sched_data *, fq_t *, |
258 | pktsched_pkt_t *, uint64_t now); |
259 | extern void fq_codel_dequeue(fq_if_t *fqs, fq_t *fq, |
260 | pktsched_pkt_t *pkt, uint64_t now); |
261 | extern void fq_getq_flow_internal(struct fq_codel_sched_data *, |
262 | fq_t *, pktsched_pkt_t *); |
263 | extern void fq_head_drop(struct fq_codel_sched_data *, fq_t *); |
264 | extern boolean_t fq_tx_time_ready(fq_if_t *fqs, fq_t *fq, uint64_t now, |
265 | uint64_t *ready_time); |
266 | |
267 | #ifdef __cplusplus |
268 | } |
269 | #endif |
270 | #endif /* BSD_KERNEL_PRIVATE */ |
271 | #endif /* PRIVATE */ |
272 | #endif /* _NET_CLASSQ_CLASSQ_FQ_CODEL_H */ |
273 | |