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/* $NetBSD: altq_hfsc.h,v 1.8 2006/10/12 19:59:08 peter Exp $ */ 30/* $KAME: altq_hfsc.h,v 1.12 2003/12/05 05:40:46 kjc Exp $ */ 31 32/* 33 * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved. 34 * 35 * Permission to use, copy, modify, and distribute this software and 36 * its documentation is hereby granted (including for commercial or 37 * for-profit use), provided that both the copyright notice and this 38 * permission notice appear in all copies of the software, derivative 39 * works, or modified versions, and any portions thereof. 40 * 41 * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF 42 * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS 43 * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED 44 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 45 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 46 * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE 47 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 48 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 49 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 50 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 51 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 52 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 53 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 54 * DAMAGE. 55 * 56 * Carnegie Mellon encourages (but does not require) users of this 57 * software to return any improvements or extensions that they make, 58 * and to grant Carnegie Mellon the rights to redistribute these 59 * changes without encumbrance. 60 */ 61#ifndef _NET_PKTSCHED_PKTSCHED_HFSC_H_ 62#define _NET_PKTSCHED_PKTSCHED_HFSC_H_ 63 64#ifdef PRIVATE 65#include <net/pktsched/pktsched.h> 66#include <net/classq/classq.h> 67#include <net/classq/classq_red.h> 68#include <net/classq/classq_rio.h> 69#include <net/classq/classq_blue.h> 70#include <net/classq/classq_sfb.h> 71 72#ifdef __cplusplus 73extern "C" { 74#endif 75 76struct service_curve { 77 u_int32_t fl; /* service curve flags */ 78 u_int64_t m1; /* slope of the first segment in bits/sec */ 79 u_int32_t d; /* the x-projection of the first segment in msec */ 80 u_int64_t m2; /* slope of the second segment in bits/sec */ 81}; 82 83/* valid values for service curve flags */ 84#define HFSCF_M1_PCT 0x1 /* m1 is in percentage */ 85#define HFSCF_M2_PCT 0x10 /* m2 is in percentage */ 86 87#define HFSCF_USERFLAGS (HFSCF_M1_PCT | HFSCF_M2_PCT) 88 89/* special class handles */ 90#define HFSC_NULLCLASS_HANDLE 0 91#define HFSC_MAX_CLASSES 64 92 93/* hfsc class flags */ 94#define HFCF_RED 0x0001 /* use RED */ 95#define HFCF_ECN 0x0002 /* use ECN with RED/BLUE/SFB */ 96#define HFCF_RIO 0x0004 /* use RIO */ 97#define HFCF_CLEARDSCP 0x0010 /* clear diffserv codepoint */ 98#define HFCF_BLUE 0x0100 /* use BLUE */ 99#define HFCF_SFB 0x0200 /* use SFB */ 100#define HFCF_FLOWCTL 0x0400 /* enable flow control advisories */ 101#define HFCF_DEFAULTCLASS 0x1000 /* default class */ 102#ifdef BSD_KERNEL_PRIVATE 103#define HFCF_RSC 0x10000 /* has realtime sc */ 104#define HFCF_FSC 0x20000 /* has linkshare sc */ 105#define HFCF_USC 0x40000 /* has upperlimit sc */ 106#define HFCF_LAZY 0x10000000 /* on-demand resource allocation */ 107#endif /* BSD_KERNEL_PRIVATE */ 108 109#define HFCF_USERFLAGS \ 110 (HFCF_RED | HFCF_ECN | HFCF_RIO | HFCF_CLEARDSCP | HFCF_BLUE | \ 111 HFCF_SFB | HFCF_FLOWCTL | HFCF_DEFAULTCLASS) 112 113#ifdef BSD_KERNEL_PRIVATE 114#define HFCF_BITS \ 115 "\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT" \ 116 "\21RSC\22FSC\23USC\35LAZY" 117#else 118#define HFCF_BITS \ 119 "\020\1RED\2ECN\3RIO\5CLEARDSCP\11BLUE\12SFB\13FLOWCTL\15DEFAULT" 120#endif /* !BSD_KERNEL_PRIVATE */ 121 122/* service curve types */ 123#define HFSC_REALTIMESC 1 124#define HFSC_LINKSHARINGSC 2 125#define HFSC_UPPERLIMITSC 4 126#define HFSC_DEFAULTSC (HFSC_REALTIMESC|HFSC_LINKSHARINGSC) 127 128struct hfsc_classstats { 129 u_int32_t class_id; 130 u_int32_t class_handle; 131 struct service_curve rsc; 132 struct service_curve fsc; 133 struct service_curve usc; /* upper limit service curve */ 134 135 u_int64_t total; /* total work in bytes */ 136 u_int64_t cumul; /* cumulative work in bytes */ 137 /* done by real-time criteria */ 138 u_int64_t d; /* deadline */ 139 u_int64_t e; /* eligible time */ 140 u_int64_t vt; /* virtual time */ 141 u_int64_t f; /* fit time for upper-limit */ 142 143 /* info helpful for debugging */ 144 u_int64_t initvt; /* init virtual time */ 145 u_int64_t vtoff; /* cl_vt_ipoff */ 146 u_int64_t cvtmax; /* cl_maxvt */ 147 u_int64_t myf; /* cl_myf */ 148 u_int64_t cfmin; /* cl_mincf */ 149 u_int64_t cvtmin; /* cl_mincvt */ 150 u_int64_t myfadj; /* cl_myfadj */ 151 u_int64_t vtadj; /* cl_vtadj */ 152 u_int64_t cur_time; 153 u_int32_t machclk_freq; 154 155 u_int32_t qlength; 156 u_int32_t qlimit; 157 struct pktcntr xmit_cnt; 158 struct pktcntr drop_cnt; 159 u_int32_t period; 160 161 u_int32_t vtperiod; /* vt period sequence no */ 162 u_int32_t parentperiod; /* parent's vt period seqno */ 163 int nactive; /* number of active children */ 164 165 /* RED, RIO, BLUE, SFB related info */ 166 classq_type_t qtype; 167 union { 168 /* RIO has 3 red stats */ 169 struct red_stats red[RIO_NDROPPREC]; 170 struct blue_stats blue; 171 struct sfb_stats sfb; 172 }; 173 classq_state_t qstate; 174}; 175 176#ifdef BSD_KERNEL_PRIVATE 177#include <sys/queue.h> 178/* 179 * kernel internal service curve representation 180 * coordinates are given by 64 bit unsigned integers. 181 * x-axis: unit is clock count. for the intel x86 architecture, 182 * the raw Pentium TSC (Timestamp Counter) value is used. 183 * virtual time is also calculated in this time scale. 184 * y-axis: unit is byte. 185 * 186 * the service curve parameters are converted to the internal 187 * representation. 188 * the slope values are scaled to avoid overflow. 189 * the inverse slope values as well as the y-projection of the 1st 190 * segment are kept in order to to avoid 64-bit divide operations 191 * that are expensive on 32-bit architectures. 192 * 193 * note: Intel Pentium TSC never wraps around in several thousands of years. 194 * x-axis doesn't wrap around for 1089 years with 1GHz clock. 195 * y-axis doesn't wrap around for 4358 years with 1Gbps bandwidth. 196 */ 197 198/* kernel internal representation of a service curve */ 199struct internal_sc { 200 u_int64_t sm1; /* scaled slope of the 1st segment */ 201 u_int64_t ism1; /* scaled inverse-slope of the 1st segment */ 202 u_int64_t dx; /* the x-projection of the 1st segment */ 203 u_int64_t dy; /* the y-projection of the 1st segment */ 204 u_int64_t sm2; /* scaled slope of the 2nd segment */ 205 u_int64_t ism2; /* scaled inverse-slope of the 2nd segment */ 206}; 207 208/* runtime service curve */ 209struct runtime_sc { 210 u_int64_t x; /* current starting position on x-axis */ 211 u_int64_t y; /* current starting position on x-axis */ 212 u_int64_t sm1; /* scaled slope of the 1st segment */ 213 u_int64_t ism1; /* scaled inverse-slope of the 1st segment */ 214 u_int64_t dx; /* the x-projection of the 1st segment */ 215 u_int64_t dy; /* the y-projection of the 1st segment */ 216 u_int64_t sm2; /* scaled slope of the 2nd segment */ 217 u_int64_t ism2; /* scaled inverse-slope of the 2nd segment */ 218}; 219 220/* for TAILQ based ellist and actlist implementation */ 221struct hfsc_class; 222typedef TAILQ_HEAD(_eligible, hfsc_class) ellist_t; 223typedef TAILQ_ENTRY(hfsc_class) elentry_t; 224typedef TAILQ_HEAD(_active, hfsc_class) actlist_t; 225typedef TAILQ_ENTRY(hfsc_class) actentry_t; 226#define ellist_first(s) TAILQ_FIRST(s) 227#define actlist_first(s) TAILQ_FIRST(s) 228#define actlist_last(s) TAILQ_LAST(s, _active) 229 230struct hfsc_class { 231 u_int32_t cl_id; /* class id (just for debug) */ 232 u_int32_t cl_handle; /* class handle */ 233 struct hfsc_if *cl_hif; /* back pointer to struct hfsc_if */ 234 u_int32_t cl_flags; /* misc flags */ 235 236 struct hfsc_class *cl_parent; /* parent class */ 237 struct hfsc_class *cl_siblings; /* sibling classes */ 238 struct hfsc_class *cl_children; /* child classes */ 239 240 class_queue_t cl_q; /* class queue structure */ 241 u_int32_t cl_qflags; /* class queue flags */ 242 union { 243 void *ptr; 244 struct red *red; /* RED state */ 245 struct rio *rio; /* RIO state */ 246 struct blue *blue; /* BLUE state */ 247 struct sfb *sfb; /* SFB state */ 248 } cl_qalg; 249 250 u_int64_t cl_total; /* total work in bytes */ 251 u_int64_t cl_cumul; /* cumulative work in bytes */ 252 /* done by real-time criteria */ 253 u_int64_t cl_d; /* deadline */ 254 u_int64_t cl_e; /* eligible time */ 255 u_int64_t cl_vt; /* virtual time */ 256 u_int64_t cl_f; /* time when this class will fit for */ 257 /* link-sharing, max(myf, cfmin) */ 258 u_int64_t cl_myf; /* my fit-time (as calculated from */ 259 /* this class's own upperlimit */ 260 /* curve) */ 261 u_int64_t cl_myfadj; /* my fit-time adjustment */ 262 /* (to cancel history dependence) */ 263 u_int64_t cl_cfmin; /* earliest children's fit-time (used */ 264 /* with cl_myf to obtain cl_f) */ 265 u_int64_t cl_cvtmin; /* minimal virtual time among the */ 266 /* children fit for link-sharing */ 267 /* (monotonic within a period) */ 268 u_int64_t cl_vtadj; /* intra-period cumulative vt */ 269 /* adjustment */ 270 u_int64_t cl_vtoff; /* inter-period cumulative vt offset */ 271 u_int64_t cl_cvtmax; /* max child's vt in the last period */ 272 273 u_int64_t cl_initvt; /* init virtual time (for debugging) */ 274 275 struct service_curve cl_rsc0; /* external real-time service curve */ 276 struct service_curve cl_fsc0; /* external fair service curve */ 277 struct service_curve cl_usc0; /* external uppperlimit service curve */ 278 struct internal_sc cl_rsc; /* internal real-time service curve */ 279 struct internal_sc cl_fsc; /* internal fair service curve */ 280 struct internal_sc cl_usc; /* internal upperlimit service curve */ 281 struct runtime_sc cl_deadline; /* deadline curve */ 282 struct runtime_sc cl_eligible; /* eligible curve */ 283 struct runtime_sc cl_virtual; /* virtual curve */ 284 struct runtime_sc cl_ulimit; /* upperlimit curve */ 285 286 u_int32_t cl_vtperiod; /* vt period sequence no */ 287 u_int32_t cl_parentperiod; /* parent's vt period seqno */ 288 u_int32_t cl_nactive; /* number of active children */ 289 actlist_t cl_actc; /* active children list */ 290 291 actentry_t cl_actlist; /* active children list entry */ 292 elentry_t cl_ellist; /* eligible list entry */ 293 294 struct { 295 struct pktcntr xmit_cnt; 296 struct pktcntr drop_cnt; 297 u_int32_t period; 298 } cl_stats; 299}; 300 301#define cl_red cl_qalg.red 302#define cl_rio cl_qalg.rio 303#define cl_blue cl_qalg.blue 304#define cl_sfb cl_qalg.sfb 305 306/* hfsc_if flags */ 307#define HFSCIFF_ALTQ 0x1 /* configured via PF/ALTQ */ 308 309/* 310 * hfsc interface state 311 */ 312struct hfsc_if { 313 struct ifclassq *hif_ifq; /* backpointer to ifclassq */ 314 struct hfsc_class *hif_rootclass; /* root class */ 315 struct hfsc_class *hif_defaultclass; /* default class */ 316 struct hfsc_class **hif_class_tbl; 317 struct hfsc_class *hif_pollcache; /* cache for poll operation */ 318 319 u_int32_t hif_flags; /* flags */ 320 u_int32_t hif_maxclasses; /* max # of classes in table */ 321 u_int32_t hif_classes; /* # of classes in the tree */ 322 u_int32_t hif_packets; /* # of packets in the tree */ 323 u_int32_t hif_classid; /* class id sequence number */ 324 u_int64_t hif_eff_rate; /* last known effective rate */ 325 326 ellist_t hif_eligible; /* eligible list */ 327}; 328 329#define HFSCIF_IFP(_hif) ((_hif)->hif_ifq->ifcq_ifp) 330 331extern void hfsc_init(void); 332extern struct hfsc_if *hfsc_alloc(struct ifnet *, int, boolean_t); 333extern int hfsc_destroy(struct hfsc_if *); 334extern void hfsc_purge(struct hfsc_if *); 335extern void hfsc_event(struct hfsc_if *, cqev_t); 336extern int hfsc_add_queue(struct hfsc_if *, struct service_curve *, 337 struct service_curve *, struct service_curve *, u_int32_t, int, 338 u_int32_t, u_int32_t, struct hfsc_class **); 339extern int hfsc_remove_queue(struct hfsc_if *, u_int32_t); 340extern int hfsc_get_class_stats(struct hfsc_if *, u_int32_t, 341 struct hfsc_classstats *); 342extern int hfsc_enqueue(struct hfsc_if *, struct hfsc_class *, 343 struct mbuf *, struct pf_mtag *); 344extern struct mbuf *hfsc_dequeue(struct hfsc_if *, cqdq_op_t); 345extern int hfsc_setup_ifclassq(struct ifclassq *, u_int32_t); 346extern int hfsc_teardown_ifclassq(struct ifclassq *); 347extern int hfsc_getqstats_ifclassq(struct ifclassq *, u_int32_t, 348 struct if_ifclassq_stats *); 349#endif /* BSD_KERNEL_PRIVATE */ 350 351#ifdef __cplusplus 352} 353#endif 354#endif /* PRIVATE */ 355#endif /* _NET_PKTSCHED_PKTSCHED_HFSC_H_ */ 356