1/* 2 * Copyright (c) 2011 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/* $OpenBSD: altq_rmclass.h,v 1.10 2007/06/17 19:58:58 jasper Exp $ */ 30/* $KAME: altq_rmclass.h,v 1.6 2000/12/09 09:22:44 kjc Exp $ */ 31 32/* 33 * Copyright (c) 1991-1997 Regents of the University of California. 34 * All rights reserved. 35 * 36 * Redistribution and use in source and binary forms, with or without 37 * modification, are permitted provided that the following conditions 38 * are met: 39 * 1. Redistributions of source code must retain the above copyright 40 * notice, this list of conditions and the following disclaimer. 41 * 2. Redistributions in binary form must reproduce the above copyright 42 * notice, this list of conditions and the following disclaimer in the 43 * documentation and/or other materials provided with the distribution. 44 * 3. All advertising materials mentioning features or use of this software 45 * must display the following acknowledgement: 46 * This product includes software developed by the Network Research 47 * Group at Lawrence Berkeley Laboratory. 48 * 4. Neither the name of the University nor of the Laboratory may be used 49 * to endorse or promote products derived from this software without 50 * specific prior written permission. 51 * 52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 55 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 62 * SUCH DAMAGE. 63 */ 64 65#ifndef _NET_PKTSCHED_PKTSCHED_RMCLASS_H_ 66#define _NET_PKTSCHED_PKTSCHED_RMCLASS_H_ 67 68#ifdef PRIVATE 69#include <net/classq/classq.h> 70#include <net/pktsched/pktsched.h> 71 72#ifdef __cplusplus 73extern "C" { 74#endif 75 76#define RM_MAXPRIO 8 /* Max priority */ 77 78/* flags for rmc_init and rmc_newclass */ 79/* class flags */ 80#define RMCF_RED 0x0001 /* use RED */ 81#define RMCF_ECN 0x0002 /* use ECN with RED/BLUE/SFB */ 82#define RMCF_RIO 0x0004 /* use RIO */ 83#define RMCF_FLOWVALVE 0x0008 /* use flowvalve (aka penalty-box) */ 84#define RMCF_CLEARDSCP 0x0010 /* clear diffserv codepoint */ 85 86/* flags for rmc_init */ 87#define RMCF_WRR 0x0100 88#define RMCF_EFFICIENT 0x0200 89 90#define RMCF_BLUE 0x10000 /* use BLUE */ 91#define RMCF_SFB 0x20000 /* use SFB */ 92#define RMCF_FLOWCTL 0x40000 /* enable flow control advisories */ 93#ifdef BSD_KERNEL_PRIVATE 94#define RMCF_LAZY 0x10000000 /* on-demand resource allocation */ 95 96typedef struct rm_ifdat rm_ifdat_t; 97typedef struct rm_class rm_class_t; 98 99struct red; 100struct rio; 101struct blue; 102struct sfb; 103 104/* 105 * Macros for dealing with time values. We assume all times are 106 * 'timevals'. `microuptime' is used to get the best available clock 107 * resolution. If `microuptime' *doesn't* return a value that's about 108 * ten times smaller than the average packet time on the fastest 109 * link that will use these routines, a slightly different clock 110 * scheme than this one should be used. 111 * (Bias due to truncation error in this scheme will overestimate utilization 112 * and discriminate against high bandwidth classes. To remove this bias an 113 * integrator needs to be added. The simplest integrator uses a history of 114 * 10 * avg.packet.time / min.tick.time packet completion entries. This is 115 * straight forward to add but we don't want to pay the extra memory 116 * traffic to maintain it if it's not necessary (occasionally a vendor 117 * accidentally builds a workstation with a decent clock - e.g., Sun & HP).) 118 */ 119 120#define RM_GETTIME(now) microuptime(&now) 121 122#define TV_LT(a, b) (((a)->tv_sec < (b)->tv_sec) || \ 123 (((a)->tv_usec < (b)->tv_usec) && ((a)->tv_sec <= (b)->tv_sec))) 124 125#define TV_DELTA(a, b, delta) { \ 126 int xxs; \ 127 \ 128 delta = (a)->tv_usec - (b)->tv_usec; \ 129 if ((xxs = (a)->tv_sec - (b)->tv_sec)) { \ 130 switch (xxs) { \ 131 default: \ 132 /* \ 133 * if (xxs < 0) \ 134 * printf("rm_class: bogus time values\n"); \ 135 */ \ 136 delta = 0; \ 137 /* fall through */ \ 138 case 2: \ 139 delta += 1000000; \ 140 /* fall through */ \ 141 case 1: \ 142 delta += 1000000; \ 143 break; \ 144 } \ 145 } \ 146} 147 148#define TV_ADD_DELTA(a, delta, res) { \ 149 int xxus = (a)->tv_usec + (delta); \ 150 \ 151 (res)->tv_sec = (a)->tv_sec; \ 152 while (xxus >= 1000000) { \ 153 ++((res)->tv_sec); \ 154 xxus -= 1000000; \ 155 } \ 156 (res)->tv_usec = xxus; \ 157} 158 159#define RM_TIMEOUT 2 /* 1 Clock tick. */ 160 161#if 1 162#define RM_MAXQUEUED 1 /* this isn't used in ALTQ/CBQ */ 163#else 164#define RM_MAXQUEUED 16 /* Max number of packets downstream of CBQ */ 165#endif 166#define RM_MAXQUEUE 64 /* Max queue length */ 167#define RM_FILTER_GAIN 5 /* log2 of gain, e.g., 5 => 31/32 */ 168#define RM_POWER (1 << RM_FILTER_GAIN) 169#define RM_MAXDEPTH 32 170#define RM_NS_PER_SEC (1000000000) 171 172typedef struct _rm_class_stats_ { 173 u_int32_t handle; 174 u_int32_t depth; 175 176 struct pktcntr xmit_cnt; /* packets sent in this class */ 177 struct pktcntr drop_cnt; /* dropped packets */ 178 u_int32_t over; /* # times went over limit */ 179 u_int32_t borrows; /* # times tried to borrow */ 180 u_int32_t overactions; /* # times invoked overlimit action */ 181 u_int32_t delays; /* # times invoked delay actions */ 182} rm_class_stats_t; 183 184/* 185 * CBQ Class state structure 186 */ 187struct rm_class { 188 class_queue_t q_; /* Queue of packets */ 189 rm_ifdat_t *ifdat_; 190 int pri_; /* Class priority. */ 191 int depth_; /* Class depth */ 192 u_int32_t ns_per_byte_; /* NanoSeconds per byte. */ 193 u_int32_t maxrate_; /* Bytes per second for this class. */ 194 u_int32_t allotment_; /* Fraction of link bandwidth. */ 195 u_int32_t w_allotment_; /* Weighted allotment for WRR */ 196 int bytes_alloc_; /* Allocation for round of WRR */ 197 198 int avgidle_; 199 int maxidle_; 200 int minidle_; 201 int offtime_; 202 int sleeping_; /* != 0 if delaying */ 203 u_int32_t qthresh_; /* Threshold for formal link sharing */ 204 int leaf_; /* Note whether leaf class or not */ 205 206 rm_class_t *children_; /* Children of this class */ 207 rm_class_t *next_; /* Next pointer, used if child */ 208 209 rm_class_t *peer_; /* Peer class */ 210 rm_class_t *borrow_; /* Borrow class */ 211 rm_class_t *parent_; /* Parent class */ 212 213 void (*overlimit)(struct rm_class *, struct rm_class *); 214 void (*drop)(struct rm_class *); /* Class drop action. */ 215 216 union { 217 void *ptr; 218 struct red *red; /* RED state */ 219 struct rio *rio; /* RIO state */ 220 struct blue *blue; /* BLUE state */ 221 struct sfb *sfb; /* SFB state */ 222 } qalg_; 223 int flags_; 224 u_int32_t qflags_; 225 226 int last_pkttime_; /* saved pkt_time */ 227 struct timeval undertime_; /* time can next send */ 228 struct timeval last_; /* time last packet sent */ 229 struct timeval overtime_; 230 struct callout callout_; /* for timeout() calls */ 231 232 rm_class_stats_t stats_; /* Class Statistics */ 233}; 234 235#define red_ qalg_.red 236#define rio_ qalg_.rio 237#define blue_ qalg_.blue 238#define sfb_ qalg_.sfb 239 240/* 241 * CBQ Interface state 242 */ 243struct rm_ifdat { 244 int queued_; /* # pkts queued downstream */ 245 int efficient_; /* Link Efficency bit */ 246 int wrr_; /* Enable Weighted Round-Robin */ 247 u_long ns_per_byte_; /* Link byte speed. */ 248 int maxqueued_; /* Max packets to queue */ 249 int maxpkt_; /* Max packet size. */ 250 int qi_; /* In/out pointers for downstream */ 251 int qo_; /* packets */ 252 253 /* 254 * Active class state and WRR state. 255 */ 256 rm_class_t *active_[RM_MAXPRIO]; /* Active cl's in each pri */ 257 int na_[RM_MAXPRIO]; /* # of active cl's in a pri */ 258 int num_[RM_MAXPRIO]; /* # of cl's per pri */ 259 int alloc_[RM_MAXPRIO]; /* Byte Allocation */ 260 u_long M_[RM_MAXPRIO]; /* WRR weights. */ 261 262 /* 263 * Network Interface/Solaris Queue state pointer. 264 */ 265 struct ifclassq *ifq_; 266 rm_class_t *default_; /* Default Pkt class, BE */ 267 rm_class_t *root_; /* Root Link class. */ 268 rm_class_t *ctl_; /* Control Traffic class. */ 269 void (*restart)(struct ifclassq *); /* Restart routine. */ 270 271 /* 272 * Current packet downstream packet state and dynamic state. 273 */ 274 rm_class_t *borrowed_[RM_MAXQUEUED]; /* Class borrowed last */ 275 rm_class_t *class_[RM_MAXQUEUED]; /* class sending */ 276 int curlen_[RM_MAXQUEUED]; /* Current pktlen */ 277 struct timeval now_[RM_MAXQUEUED]; /* Current packet time */ 278 int is_overlimit_[RM_MAXQUEUED]; /* Current packet time */ 279 280 int cutoff_; /* Cut-off depth for borrowing */ 281 282 struct timeval ifnow_; /* expected xmit completion time */ 283#if 1 /* ALTQ4PPP */ 284 int maxiftime_; /* max delay inside interface */ 285#endif 286 rm_class_t *pollcache_; /* cached rm_class by poll operation */ 287}; 288 289#define RMC_IS_A_PARENT_CLASS(cl) ((cl)->children_ != NULL) 290 291extern void rmclass_init(void); 292extern rm_class_t *rmc_newclass(int, struct rm_ifdat *, u_int32_t, 293 void (*)(struct rm_class *, struct rm_class *), u_int32_t, 294 u_int32_t, struct rm_class *, struct rm_class *, 295 u_int32_t, int, u_int32_t, int, int); 296extern void rmc_delete_class(struct rm_ifdat *, struct rm_class *); 297extern int rmc_modclass(struct rm_class *, u_int32_t, int, u_int32_t, 298 int, u_int32_t, int); 299extern int rmc_init(struct ifclassq *, struct rm_ifdat *, u_int32_t, 300 void (*)(struct ifclassq *), u_int32_t, int, int, u_int32_t, 301 int, u_int32_t, int); 302extern int rmc_queue_packet(struct rm_class *, struct mbuf *, struct pf_mtag *); 303extern struct mbuf *rmc_dequeue_next(struct rm_ifdat *, cqdq_op_t); 304extern void rmc_update_class_util(struct rm_ifdat *); 305extern void rmc_delay_action(struct rm_class *, struct rm_class *); 306extern void rmc_drop(struct rm_class *, u_int32_t, u_int32_t *, u_int32_t *); 307extern void rmc_dropall(struct rm_class *); 308extern int rmc_get_weight(struct rm_ifdat *, int); 309extern void rmc_updateq(struct rm_class *, cqev_t); 310 311#endif /* BSD_KERNEL_PRIVATE */ 312 313#ifdef __cplusplus 314} 315#endif 316#endif /* PRIVATE */ 317#endif /* _NET_PKTSCHED_PKTSCHED_RMCLASS_H_ */ 318