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_PKTSCHED_FQ_CODEL_H_ 30 #define _NET_PKTSCHED_FQ_CODEL_H_ 31 32 #ifdef PRIVATE 33 #include <sys/types.h> 34 #include <sys/param.h> 35 36 #ifdef BSD_KERNEL_PRIVATE 37 #include <net/flowadv.h> 38 #include <net/pktsched/pktsched.h> 39 #endif /* BSD_KERNEL_PRIVATE */ 40 41 #ifdef __cplusplus 42 extern "C" { 43 #endif 44 45 #ifdef BSD_KERNEL_PRIVATE 46 struct fcl_stat { 47 u_int32_t fcl_flow_control; 48 u_int32_t fcl_flow_feedback; 49 u_int32_t fcl_dequeue_stall; 50 u_int32_t fcl_flow_control_fail; 51 u_int64_t fcl_drop_overflow; 52 u_int64_t fcl_drop_early; 53 u_int32_t fcl_drop_memfailure; 54 u_int32_t fcl_flows_cnt; 55 u_int32_t fcl_newflows_cnt; 56 u_int32_t fcl_oldflows_cnt; 57 u_int64_t fcl_pkt_cnt; 58 u_int64_t fcl_dequeue; 59 u_int64_t fcl_dequeue_bytes; 60 u_int64_t fcl_byte_cnt; 61 u_int32_t fcl_throttle_on; 62 u_int32_t fcl_throttle_off; 63 u_int32_t fcl_throttle_drops; 64 u_int32_t fcl_dup_rexmts; 65 u_int32_t fcl_pkts_compressible; 66 u_int32_t fcl_pkts_compressed; 67 uint64_t fcl_min_qdelay; 68 uint64_t fcl_max_qdelay; 69 uint64_t fcl_avg_qdelay; 70 uint32_t fcl_overwhelming; 71 }; 72 73 /* 74 * Use the top most 8 bits of flow id as the tag for set associative 75 * hashing 76 */ 77 78 #define FQ_IF_HASH_TAG_SIZE 8 79 #define FQ_IF_HASH_TAG_SHIFT 24 80 #define FQ_IF_HASH_TAG_MASK 0xFF 81 #define FQ_IF_HASH_TABLE_SIZE (1 << FQ_IF_HASH_TAG_SIZE) 82 83 /* Set the quantum to be one MTU */ 84 #define FQ_IF_DEFAULT_QUANTUM 1500 85 86 /* Max number of service classes currently supported */ 87 #define FQ_IF_MAX_CLASSES 10 88 _Static_assert(FQ_IF_MAX_CLASSES < 127, 89 "maximum number of classes needs to fit in a single byte"); 90 91 #define FQ_IF_LARGE_FLOW_BYTE_LIMIT 15000 92 93 struct flowq; 94 typedef u_int32_t pktsched_bitmap_t; 95 struct if_ifclassq_stats; 96 97 enum fq_if_state { 98 FQ_IF_ER = 0, /* eligible, ready */ 99 FQ_IF_IR = 1, /* ineligible, ready */ 100 FQ_IF_EB = 2, /* eligible blocked */ 101 FQ_IF_IB = 3, /* ineligible, blocked */ 102 FQ_IF_MAX_STATE 103 }; 104 105 /* 106 * This priority index is used for QFQ state bitmaps, lower index gets 107 * higher priority 108 */ 109 #define FQ_IF_BK_SYS_INDEX 9 110 #define FQ_IF_BK_INDEX 8 111 #define FQ_IF_BE_INDEX 7 112 #define FQ_IF_RD_INDEX 6 113 #define FQ_IF_OAM_INDEX 5 114 #define FQ_IF_AV_INDEX 4 115 #define FQ_IF_RV_INDEX 3 116 #define FQ_IF_VI_INDEX 2 117 #define FQ_IF_SIG_INDEX 2 118 #define FQ_IF_VO_INDEX 1 119 #define FQ_IF_CTL_INDEX 0 120 121 typedef SLIST_HEAD(, flowq) flowq_list_t; 122 typedef STAILQ_HEAD(, flowq) flowq_stailq_t; 123 typedef struct fq_if_classq { 124 uint32_t fcl_pri; /* class priority, lower the better */ 125 uint32_t fcl_service_class; /* service class */ 126 uint32_t fcl_quantum; /* quantum in bytes */ 127 uint32_t fcl_drr_max; /* max flows per class for DRR */ 128 int64_t fcl_budget; /* budget for this classq */ 129 flowq_stailq_t fcl_new_flows; /* List of new flows */ 130 flowq_stailq_t fcl_old_flows; /* List of old flows */ 131 struct fcl_stat fcl_stat; 132 } fq_if_classq_t; 133 134 typedef struct fq_codel_sched_data { 135 struct ifclassq *fqs_ifq; /* back pointer to ifclassq */ 136 u_int64_t fqs_target_qdelay; /* Target queue delay (ns) */ 137 u_int64_t fqs_update_interval; /* update interval (ns) */ 138 flowq_list_t fqs_flows[FQ_IF_HASH_TABLE_SIZE]; /* flows table */ 139 pktsched_bitmap_t fqs_bitmaps[FQ_IF_MAX_STATE]; 140 u_int32_t fqs_pkt_droplimit; /* drop limit */ 141 u_int8_t fqs_throttle; /* throttle on or off */ 142 u_int8_t fqs_flags; /* flags */ 143 #define FQS_DRIVER_MANAGED 0x1 144 fq_if_classq_t fqs_classq[FQ_IF_MAX_CLASSES]; /* class queues */ 145 struct flowadv_fclist fqs_fclist; /* flow control state */ 146 struct flowq *fqs_large_flow; /* flow has highest number of bytes */ 147 classq_pkt_type_t fqs_ptype; 148 } fq_if_t; 149 150 #endif /* BSD_KERNEL_PRIVATE */ 151 152 struct fq_codel_flowstats { 153 u_int32_t fqst_min_qdelay; 154 #define FQ_FLOWSTATS_OLD_FLOW 0x1 155 #define FQ_FLOWSTATS_NEW_FLOW 0x2 156 #define FQ_FLOWSTATS_LARGE_FLOW 0x4 157 #define FQ_FLOWSTATS_DELAY_HIGH 0x8 158 #define FQ_FLOWSTATS_FLOWCTL_ON 0x10 159 u_int32_t fqst_flags; 160 u_int32_t fqst_bytes; 161 u_int32_t fqst_flowhash; 162 }; 163 164 #define FQ_IF_MAX_FLOWSTATS 20 165 166 struct fq_codel_classstats { 167 u_int32_t fcls_pri; 168 u_int32_t fcls_service_class; 169 u_int32_t fcls_quantum; 170 u_int32_t fcls_drr_max; 171 int64_t fcls_budget; 172 u_int64_t fcls_target_qdelay; 173 u_int64_t fcls_update_interval; 174 u_int32_t fcls_flow_control; 175 u_int32_t fcls_flow_feedback; 176 u_int32_t fcls_dequeue_stall; 177 u_int32_t fcls_flow_control_fail; 178 u_int64_t fcls_drop_overflow; 179 u_int64_t fcls_drop_early; 180 u_int32_t fcls_drop_memfailure; 181 u_int32_t fcls_flows_cnt; 182 u_int32_t fcls_newflows_cnt; 183 u_int32_t fcls_oldflows_cnt; 184 u_int64_t fcls_pkt_cnt; 185 u_int64_t fcls_dequeue; 186 u_int64_t fcls_dequeue_bytes; 187 u_int64_t fcls_byte_cnt; 188 u_int32_t fcls_throttle_on; 189 u_int32_t fcls_throttle_off; 190 u_int32_t fcls_throttle_drops; 191 u_int32_t fcls_dup_rexmts; 192 u_int32_t fcls_flowstats_cnt; 193 struct fq_codel_flowstats fcls_flowstats[FQ_IF_MAX_FLOWSTATS]; 194 u_int32_t fcls_pkts_compressible; 195 u_int32_t fcls_pkts_compressed; 196 uint64_t fcls_min_qdelay; 197 uint64_t fcls_max_qdelay; 198 uint64_t fcls_avg_qdelay; 199 uint32_t fcls_overwhelming; 200 }; 201 202 #ifdef BSD_KERNEL_PRIVATE 203 204 extern void fq_codel_scheduler_init(void); 205 extern int fq_if_enqueue_classq(struct ifclassq *ifq, classq_pkt_t *h, 206 classq_pkt_t *t, uint32_t cnt, uint32_t bytes, boolean_t *pdrop); 207 extern void fq_if_dequeue_classq(struct ifclassq *ifq, classq_pkt_t *pkt); 208 extern void fq_if_dequeue_sc_classq(struct ifclassq *ifq, mbuf_svc_class_t svc, 209 classq_pkt_t *pkt); 210 extern int fq_if_dequeue_classq_multi(struct ifclassq *ifq, u_int32_t maxpktcnt, 211 u_int32_t maxbytecnt, classq_pkt_t *first_packet, classq_pkt_t *last_packet, 212 u_int32_t *retpktcnt, u_int32_t *retbytecnt); 213 extern int fq_if_dequeue_sc_classq_multi(struct ifclassq *ifq, 214 mbuf_svc_class_t svc, u_int32_t maxpktcnt, u_int32_t maxbytecnt, 215 classq_pkt_t *first_packet, classq_pkt_t *last_packet, u_int32_t *retpktcnt, 216 u_int32_t *retbytecnt); 217 extern int fq_if_request_classq(struct ifclassq *ifq, cqrq_t rq, void *arg); 218 extern struct flowq *fq_if_hash_pkt(fq_if_t *, u_int32_t, mbuf_svc_class_t, 219 u_int64_t, boolean_t, classq_pkt_type_t); 220 extern boolean_t fq_if_at_drop_limit(fq_if_t *); 221 extern void fq_if_drop_packet(fq_if_t *); 222 extern boolean_t fq_if_almost_at_drop_limit(fq_if_t *fqs); 223 extern void fq_if_is_flow_heavy(fq_if_t *, struct flowq *); 224 extern boolean_t fq_if_add_fcentry(fq_if_t *, pktsched_pkt_t *, uint8_t, 225 struct flowq *, fq_if_classq_t *); 226 extern void fq_if_flow_feedback(fq_if_t *, struct flowq *, fq_if_classq_t *); 227 extern int fq_if_setup_ifclassq(struct ifclassq *ifq, u_int32_t flags, 228 classq_pkt_type_t ptype); 229 extern void fq_if_teardown_ifclassq(struct ifclassq *ifq); 230 extern int fq_if_getqstats_ifclassq(struct ifclassq *ifq, u_int32_t qid, 231 struct if_ifclassq_stats *ifqs); 232 extern void fq_if_destroy_flow(fq_if_t *, fq_if_classq_t *, 233 struct flowq *, bool); 234 235 236 #endif /* BSD_KERNEL_PRIVATE */ 237 238 #ifdef __cplusplus 239 } 240 #endif 241 242 #endif /* PRIVATE */ 243 #endif /* _NET_PKTSCHED_PKTSCHED_FQ_CODEL_H_ */ 244