1/* 2 * Copyright (c) 2011-2013 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#include <sys/cdefs.h> 30#include <sys/param.h> 31#include <sys/mbuf.h> 32#include <sys/socket.h> 33#include <sys/sockio.h> 34#include <sys/systm.h> 35#include <sys/sysctl.h> 36#include <sys/syslog.h> 37#include <sys/proc.h> 38#include <sys/errno.h> 39#include <sys/kernel.h> 40#include <sys/kauth.h> 41 42#include <kern/zalloc.h> 43 44#include <net/if.h> 45#include <net/if_var.h> 46#include <net/if_types.h> 47#include <net/dlil.h> 48#include <net/flowadv.h> 49 50#include <netinet/in.h> 51#include <netinet/in_systm.h> 52#include <netinet/ip.h> 53#if INET6 54#include <netinet/ip6.h> 55#endif 56 57#include <net/classq/classq_sfb.h> 58#include <net/flowhash.h> 59#include <net/net_osdep.h> 60#include <dev/random/randomdev.h> 61 62/* 63 * Stochastic Fair Blue 64 * 65 * Wu-chang Feng, Dilip D. Kandlur, Debanjan Saha, Kang G. Shin 66 * http://www.thefengs.com/wuchang/blue/CSE-TR-387-99.pdf 67 * 68 * Based on the NS code with the following parameters: 69 * 70 * bytes: false 71 * decrement: 0.001 72 * increment: 0.005 73 * hold-time: 10ms-50ms (randomized) 74 * algorithm: 0 75 * pbox: 1 76 * pbox-time: 50-100ms (randomized) 77 * hinterval: 11-23 (randomized) 78 * 79 * This implementation uses L = 2 and N = 32 for 2 sets of: 80 * 81 * B[L][N]: L x N array of bins (L levels, N bins per level) 82 * 83 * Each set effectively creates 32^2 virtual buckets (bin combinations) 84 * while using only O(32*2) states. 85 * 86 * Given a 32-bit hash value, we divide it such that octets [0,1,2,3] are 87 * used as index for the bins across the 2 levels, where level 1 uses [0,2] 88 * and level 2 uses [1,3]. The 2 values per level correspond to the indices 89 * for the current and warm-up sets (section 4.4. in the SFB paper regarding 90 * Moving Hash Functions explains the purposes of these 2 sets.) 91 */ 92 93/* 94 * Use Murmur3A_x86_32 for hash function. It seems to perform consistently 95 * across platforms for 1-word key (32-bit flowhash value). See flowhash.h 96 * for other alternatives. We only need 16-bit hash output. 97 */ 98#define SFB_HASH net_flowhash_mh3_x86_32 99#define SFB_HASHMASK HASHMASK(16) 100 101#define SFB_BINMASK(_x) \ 102 ((_x) & HASHMASK(SFB_BINS_SHIFT)) 103 104#define SFB_BINST(_sp, _l, _n, _c) \ 105 (&(*(_sp)->sfb_bins)[_c].stats[_l][_n]) 106 107#define SFB_BINFT(_sp, _l, _n, _c) \ 108 (&(*(_sp)->sfb_bins)[_c].freezetime[_l][_n]) 109 110#define SFB_FC_LIST(_sp, _n) \ 111 (&(*(_sp)->sfb_fc_lists)[_n]) 112 113/* 114 * The holdtime parameter determines the minimum time interval between 115 * two successive updates of the marking probability. In the event the 116 * uplink speed is not known, a default value is chosen and is randomized 117 * to be within the following range. 118 */ 119#define HOLDTIME_BASE (100ULL * 1000 * 1000) /* 100ms */ 120#define HOLDTIME_MIN (10ULL * 1000 * 1000) /* 10ms */ 121#define HOLDTIME_MAX (100ULL * 1000 * 1000) /* 100ms */ 122 123/* 124 * The pboxtime parameter determines the bandwidth allocated for rogue 125 * flows, i.e. the rate limiting bandwidth. In the event the uplink speed 126 * is not known, a default value is chosen and is randomized to be within 127 * the following range. 128 */ 129#define PBOXTIME_BASE (300ULL * 1000 * 1000) /* 300ms */ 130#define PBOXTIME_MIN (30ULL * 1000 * 1000) /* 30ms */ 131#define PBOXTIME_MAX (300ULL * 1000 * 1000) /* 300ms */ 132 133/* 134 * Target queueing delay is the amount of extra delay that can be added 135 * to accommodate variations in the link bandwidth. The queue should be 136 * large enough to induce this much delay and nothing more than that. 137 */ 138#define TARGET_QDELAY_BASE (10ULL * 1000 * 1000) /* 10ms */ 139#define TARGET_QDELAY_MIN (10ULL * 1000) /* 10us */ 140#define TARGET_QDELAY_MAX (20ULL * 1000 * 1000 * 1000) /* 20s */ 141 142/* 143 * Update interval for checking the extra delay added by the queue. This 144 * should be 90-95 percentile of RTT experienced by any TCP connection 145 * so that it will take care of the burst traffic. 146 */ 147#define UPDATE_INTERVAL_BASE (100ULL * 1000 * 1000) /* 100ms */ 148#define UPDATE_INTERVAL_MIN (100ULL * 1000 * 1000) /* 100ms */ 149#define UPDATE_INTERVAL_MAX (10ULL * 1000 * 1000 * 1000) /* 10s */ 150 151#define SFB_RANDOM(sp, tmin, tmax) ((sfb_random(sp) % (tmax)) + (tmin)) 152 153#define SFB_PKT_PBOX 0x1 /* in penalty box */ 154 155/* The following mantissa values are in SFB_FP_SHIFT Q format */ 156#define SFB_MAX_PMARK (1 << SFB_FP_SHIFT) /* Q14 representation of 1.00 */ 157 158/* 159 * These are d1 (increment) and d2 (decrement) parameters, used to determine 160 * the amount by which the marking probability is incremented when the queue 161 * overflows, or is decremented when the link is idle. d1 is set higher than 162 * d2, because link underutilization can occur when congestion management is 163 * either too conservative or too aggressive, but packet loss occurs only 164 * when congestion management is too conservative. By weighing heavily 165 * against packet loss, it can quickly reach to a substantial increase in 166 * traffic load. 167 */ 168#define SFB_INCREMENT 82 /* Q14 representation of 0.005 */ 169#define SFB_DECREMENT 16 /* Q14 representation of 0.001 */ 170 171#define SFB_PMARK_TH 16056 /* Q14 representation of 0.98 */ 172#define SFB_PMARK_WARM 3276 /* Q14 representation of 0.2 */ 173 174#define SFB_PMARK_INC(_bin) do { \ 175 (_bin)->pmark += sfb_increment; \ 176 if ((_bin)->pmark > SFB_MAX_PMARK) \ 177 (_bin)->pmark = SFB_MAX_PMARK; \ 178} while (0) 179 180#define SFB_PMARK_DEC(_bin) do { \ 181 if ((_bin)->pmark > 0) { \ 182 (_bin)->pmark -= sfb_decrement; \ 183 if ((_bin)->pmark < 0) \ 184 (_bin)->pmark = 0; \ 185 } \ 186} while (0) 187 188/* Minimum nuber of bytes in queue to get flow controlled */ 189#define SFB_MIN_FC_THRESHOLD_BYTES 7500 190 191#define SFB_SET_DELAY_HIGH(_sp_, _q_) do { \ 192 (_sp_)->sfb_flags |= SFBF_DELAYHIGH; \ 193 (_sp_)->sfb_fc_threshold = max(SFB_MIN_FC_THRESHOLD_BYTES, \ 194 (qsize((_q_)) >> 3)); \ 195} while (0) 196 197#define SFB_QUEUE_DELAYBASED(_sp_) ((_sp_)->sfb_flags & SFBF_DELAYBASED) 198#define SFB_IS_DELAYHIGH(_sp_) ((_sp_)->sfb_flags & SFBF_DELAYHIGH) 199#define SFB_QUEUE_DELAYBASED_MAXSIZE 2048 /* max pkts */ 200 201#define HINTERVAL_MIN (10) /* 10 seconds */ 202#define HINTERVAL_MAX (20) /* 20 seconds */ 203#define SFB_HINTERVAL(sp) ((sfb_random(sp) % HINTERVAL_MAX) + HINTERVAL_MIN) 204 205#define DEQUEUE_DECAY 7 /* ilog2 of EWMA decay rate, (128) */ 206#define DEQUEUE_SPIKE(_new, _old) \ 207 ((u_int64_t)ABS((int64_t)(_new) - (int64_t)(_old)) > ((_old) << 11)) 208 209#define ABS(v) (((v) > 0) ? (v) : -(v)) 210 211#define SFB_ZONE_MAX 32 /* maximum elements in zone */ 212#define SFB_ZONE_NAME "classq_sfb" /* zone name */ 213 214#define SFB_BINS_ZONE_MAX 32 /* maximum elements in zone */ 215#define SFB_BINS_ZONE_NAME "classq_sfb_bins" /* zone name */ 216 217#define SFB_FCL_ZONE_MAX 32 /* maximum elements in zone */ 218#define SFB_FCL_ZONE_NAME "classq_sfb_fcl" /* zone name */ 219 220/* Place the flow control entries in current bin on level 0 */ 221#define SFB_FC_LEVEL 0 222 223/* Store SFB hash and flags in the module private scratch space */ 224#define pkt_sfb_hash8 pkt_mpriv.__mpriv_u.__mpriv32[0].__mpriv32_u.__val8 225#define pkt_sfb_hash16 pkt_mpriv.__mpriv_u.__mpriv32[0].__mpriv32_u.__val16 226#define pkt_sfb_hash32 pkt_mpriv.__mpriv_u.__mpriv32[0].__mpriv32_u.__val32 227#define pkt_sfb_flags pkt_mpriv.__mpriv_u.__mpriv32[1].__mpriv32_u.__val32 228 229static unsigned int sfb_size; /* size of zone element */ 230static struct zone *sfb_zone; /* zone for sfb */ 231 232static unsigned int sfb_bins_size; /* size of zone element */ 233static struct zone *sfb_bins_zone; /* zone for sfb_bins */ 234 235static unsigned int sfb_fcl_size; /* size of zone element */ 236static struct zone *sfb_fcl_zone; /* zone for sfb_fc_lists */ 237 238/* internal function prototypes */ 239static u_int32_t sfb_random(struct sfb *); 240static struct mbuf *sfb_getq_flow(struct sfb *, class_queue_t *, u_int32_t, 241 boolean_t); 242static void sfb_resetq(struct sfb *, cqev_t); 243static void sfb_calc_holdtime(struct sfb *, u_int64_t); 244static void sfb_calc_pboxtime(struct sfb *, u_int64_t); 245static void sfb_calc_hinterval(struct sfb *, u_int64_t *); 246static void sfb_calc_target_qdelay(struct sfb *, u_int64_t); 247static void sfb_calc_update_interval(struct sfb *, u_int64_t); 248static void sfb_swap_bins(struct sfb *, u_int32_t); 249static inline int sfb_pcheck(struct sfb *, struct pkthdr *); 250static int sfb_penalize(struct sfb *, struct pkthdr *, struct timespec *); 251static void sfb_adjust_bin(struct sfb *, struct sfbbinstats *, 252 struct timespec *, struct timespec *, boolean_t); 253static void sfb_decrement_bin(struct sfb *, struct sfbbinstats *, 254 struct timespec *, struct timespec *); 255static void sfb_increment_bin(struct sfb *, struct sfbbinstats *, 256 struct timespec *, struct timespec *); 257static inline void sfb_dq_update_bins(struct sfb *, struct pkthdr *, 258 struct timespec *, u_int32_t qsize); 259static inline void sfb_eq_update_bins(struct sfb *, struct pkthdr *); 260static int sfb_drop_early(struct sfb *, struct pkthdr *, u_int16_t *, 261 struct timespec *); 262static boolean_t sfb_bin_addfcentry(struct sfb *, struct pkthdr *); 263static void sfb_fclist_append(struct sfb *, struct sfb_fcl *); 264static void sfb_fclists_clean(struct sfb *sp); 265static int sfb_bin_mark_or_drop(struct sfb *sp, struct sfbbinstats *bin); 266static void sfb_detect_dequeue_stall(struct sfb *sp, class_queue_t *, 267 struct timespec *); 268 269SYSCTL_NODE(_net_classq, OID_AUTO, sfb, CTLFLAG_RW|CTLFLAG_LOCKED, 0, "SFB"); 270 271static u_int64_t sfb_holdtime = 0; /* 0 indicates "automatic" */ 272SYSCTL_QUAD(_net_classq_sfb, OID_AUTO, holdtime, CTLFLAG_RW|CTLFLAG_LOCKED, 273 &sfb_holdtime, "SFB freeze time in nanoseconds"); 274 275static u_int64_t sfb_pboxtime = 0; /* 0 indicates "automatic" */ 276SYSCTL_QUAD(_net_classq_sfb, OID_AUTO, pboxtime, CTLFLAG_RW|CTLFLAG_LOCKED, 277 &sfb_pboxtime, "SFB penalty box time in nanoseconds"); 278 279static u_int64_t sfb_hinterval; 280SYSCTL_QUAD(_net_classq_sfb, OID_AUTO, hinterval, CTLFLAG_RW|CTLFLAG_LOCKED, 281 &sfb_hinterval, "SFB hash interval in nanoseconds"); 282 283static u_int64_t sfb_target_qdelay; 284SYSCTL_QUAD(_net_classq_sfb, OID_AUTO, target_qdelay, CTLFLAG_RW|CTLFLAG_LOCKED, 285 &sfb_target_qdelay, "SFB target queue delay in milliseconds"); 286 287static u_int64_t sfb_update_interval; 288SYSCTL_QUAD(_net_classq_sfb, OID_AUTO, update_interval, 289 CTLFLAG_RW|CTLFLAG_LOCKED, &sfb_update_interval, "SFB update interval"); 290 291static u_int32_t sfb_increment = SFB_INCREMENT; 292SYSCTL_UINT(_net_classq_sfb, OID_AUTO, increment, CTLFLAG_RW|CTLFLAG_LOCKED, 293 &sfb_increment, SFB_INCREMENT, "SFB increment [d1]"); 294 295static u_int32_t sfb_decrement = SFB_DECREMENT; 296SYSCTL_UINT(_net_classq_sfb, OID_AUTO, decrement, CTLFLAG_RW|CTLFLAG_LOCKED, 297 &sfb_decrement, SFB_DECREMENT, "SFB decrement [d2]"); 298 299static u_int32_t sfb_allocation = 0; /* 0 means "automatic" */ 300SYSCTL_UINT(_net_classq_sfb, OID_AUTO, allocation, CTLFLAG_RW|CTLFLAG_LOCKED, 301 &sfb_allocation, 0, "SFB bin allocation"); 302 303static u_int32_t sfb_ratelimit = 0; 304SYSCTL_UINT(_net_classq_sfb, OID_AUTO, ratelimit, CTLFLAG_RW|CTLFLAG_LOCKED, 305 &sfb_ratelimit, 0, "SFB rate limit"); 306 307#define KBPS (1ULL * 1000) /* 1 Kbits per second */ 308#define MBPS (1ULL * 1000 * 1000) /* 1 Mbits per second */ 309#define GBPS (MBPS * 1000) /* 1 Gbits per second */ 310 311struct sfb_time_tbl { 312 u_int64_t speed; /* uplink speed */ 313 u_int64_t holdtime; /* hold time */ 314 u_int64_t pboxtime; /* penalty box time */ 315}; 316 317static struct sfb_time_tbl sfb_ttbl[] = { 318 { 1 * MBPS, HOLDTIME_BASE * 1000, PBOXTIME_BASE * 1000 }, 319 { 10 * MBPS, HOLDTIME_BASE * 100, PBOXTIME_BASE * 100 }, 320 { 100 * MBPS, HOLDTIME_BASE * 10, PBOXTIME_BASE * 10 }, 321 { 1 * GBPS, HOLDTIME_BASE, PBOXTIME_BASE }, 322 { 10 * GBPS, HOLDTIME_BASE / 10, PBOXTIME_BASE / 10 }, 323 { 100 * GBPS, HOLDTIME_BASE / 100, PBOXTIME_BASE / 100 }, 324 { 0, 0, 0 } 325}; 326 327void 328sfb_init(void) 329{ 330 _CASSERT(SFBF_ECN4 == CLASSQF_ECN4); 331 _CASSERT(SFBF_ECN6 == CLASSQF_ECN6); 332 333 sfb_size = sizeof (struct sfb); 334 sfb_zone = zinit(sfb_size, SFB_ZONE_MAX * sfb_size, 335 0, SFB_ZONE_NAME); 336 if (sfb_zone == NULL) { 337 panic("%s: failed allocating %s", __func__, SFB_ZONE_NAME); 338 /* NOTREACHED */ 339 } 340 zone_change(sfb_zone, Z_EXPAND, TRUE); 341 zone_change(sfb_zone, Z_CALLERACCT, TRUE); 342 343 sfb_bins_size = sizeof (*((struct sfb *)0)->sfb_bins); 344 sfb_bins_zone = zinit(sfb_bins_size, SFB_BINS_ZONE_MAX * sfb_bins_size, 345 0, SFB_BINS_ZONE_NAME); 346 if (sfb_bins_zone == NULL) { 347 panic("%s: failed allocating %s", __func__, SFB_BINS_ZONE_NAME); 348 /* NOTREACHED */ 349 } 350 zone_change(sfb_bins_zone, Z_EXPAND, TRUE); 351 zone_change(sfb_bins_zone, Z_CALLERACCT, TRUE); 352 353 sfb_fcl_size = sizeof (*((struct sfb *)0)->sfb_fc_lists); 354 sfb_fcl_zone = zinit(sfb_fcl_size, SFB_FCL_ZONE_MAX * sfb_fcl_size, 355 0, SFB_FCL_ZONE_NAME); 356 if (sfb_fcl_zone == NULL) { 357 panic("%s: failed allocating %s", __func__, SFB_FCL_ZONE_NAME); 358 /* NOTREACHED */ 359 } 360 zone_change(sfb_fcl_zone, Z_EXPAND, TRUE); 361 zone_change(sfb_fcl_zone, Z_CALLERACCT, TRUE); 362} 363 364static u_int32_t 365sfb_random(struct sfb *sp) 366{ 367 IFCQ_CONVERT_LOCK(&sp->sfb_ifp->if_snd); 368 return (RandomULong()); 369} 370 371static void 372sfb_calc_holdtime(struct sfb *sp, u_int64_t outbw) 373{ 374 u_int64_t holdtime; 375 376 if (sfb_holdtime != 0) { 377 holdtime = sfb_holdtime; 378 } else if (outbw == 0) { 379 holdtime = SFB_RANDOM(sp, HOLDTIME_MIN, HOLDTIME_MAX); 380 } else { 381 unsigned int n, i; 382 383 n = sfb_ttbl[0].holdtime; 384 for (i = 0; sfb_ttbl[i].speed != 0; i++) { 385 if (outbw < sfb_ttbl[i].speed) 386 break; 387 n = sfb_ttbl[i].holdtime; 388 } 389 holdtime = n; 390 } 391 net_nsectimer(&holdtime, &sp->sfb_holdtime); 392} 393 394static void 395sfb_calc_pboxtime(struct sfb *sp, u_int64_t outbw) 396{ 397 u_int64_t pboxtime; 398 399 if (sfb_pboxtime != 0) { 400 pboxtime = sfb_pboxtime; 401 } else if (outbw == 0) { 402 pboxtime = SFB_RANDOM(sp, PBOXTIME_MIN, PBOXTIME_MAX); 403 } else { 404 unsigned int n, i; 405 406 n = sfb_ttbl[0].pboxtime; 407 for (i = 0; sfb_ttbl[i].speed != 0; i++) { 408 if (outbw < sfb_ttbl[i].speed) 409 break; 410 n = sfb_ttbl[i].pboxtime; 411 } 412 pboxtime = n; 413 } 414 net_nsectimer(&pboxtime, &sp->sfb_pboxtime); 415 net_timerclear(&sp->sfb_pboxfreeze); 416} 417 418static void 419sfb_calc_hinterval(struct sfb *sp, u_int64_t *t) 420{ 421 u_int64_t hinterval; 422 struct timespec now; 423 424 if (t != NULL) { 425 /* 426 * TODO adi@apple.com: use dq_avg to derive hinterval. 427 */ 428 hinterval = *t; 429 } 430 431 if (sfb_hinterval != 0) 432 hinterval = sfb_hinterval; 433 else if (t == NULL || hinterval == 0) 434 hinterval = ((u_int64_t)SFB_HINTERVAL(sp) * NSEC_PER_SEC); 435 436 net_nsectimer(&hinterval, &sp->sfb_hinterval); 437 438 nanouptime(&now); 439 net_timeradd(&now, &sp->sfb_hinterval, &sp->sfb_nextreset); 440} 441 442static void 443sfb_calc_target_qdelay(struct sfb *sp, u_int64_t out_bw) 444{ 445#pragma unused(out_bw) 446 u_int64_t target_qdelay = 0; 447 struct ifnet *ifp = sp->sfb_ifp; 448 449 target_qdelay = IFCQ_TARGET_QDELAY(&ifp->if_snd); 450 451 if (sfb_target_qdelay != 0) 452 target_qdelay = sfb_target_qdelay; 453 454 /* 455 * If we do not know the effective bandwidth, use the default 456 * target queue delay. 457 */ 458 if (target_qdelay == 0) 459 target_qdelay = IFQ_TARGET_DELAY; 460 461 sp->sfb_target_qdelay = target_qdelay; 462} 463 464static void 465sfb_calc_update_interval(struct sfb *sp, u_int64_t out_bw) 466{ 467#pragma unused(out_bw) 468 u_int64_t update_interval = 0; 469 470 /* If the system-level override is set, use it */ 471 if (sfb_update_interval != 0) 472 update_interval = sfb_update_interval; 473 /* 474 * If we do not know the effective bandwidth, use the default 475 * update interval. 476 */ 477 if (update_interval == 0) 478 update_interval = IFQ_UPDATE_INTERVAL; 479 480 net_nsectimer(&update_interval, &sp->sfb_update_interval); 481} 482 483/* 484 * sfb support routines 485 */ 486struct sfb * 487sfb_alloc(struct ifnet *ifp, u_int32_t qid, u_int32_t qlim, u_int32_t flags) 488{ 489 struct sfb *sp; 490 int i; 491 492 VERIFY(ifp != NULL && qlim > 0); 493 494 sp = zalloc(sfb_zone); 495 if (sp == NULL) { 496 log(LOG_ERR, "%s: SFB unable to allocate\n", if_name(ifp)); 497 return (NULL); 498 } 499 bzero(sp, sfb_size); 500 501 if ((sp->sfb_bins = zalloc(sfb_bins_zone)) == NULL) { 502 log(LOG_ERR, "%s: SFB unable to allocate bins\n", if_name(ifp)); 503 sfb_destroy(sp); 504 return (NULL); 505 } 506 bzero(sp->sfb_bins, sfb_bins_size); 507 508 if ((sp->sfb_fc_lists = zalloc(sfb_fcl_zone)) == NULL) { 509 log(LOG_ERR, "%s: SFB unable to allocate flow control lists\n", 510 if_name(ifp)); 511 sfb_destroy(sp); 512 return(NULL); 513 } 514 bzero(sp->sfb_fc_lists, sfb_fcl_size); 515 516 for (i = 0; i < SFB_BINS; ++i) 517 STAILQ_INIT(&SFB_FC_LIST(sp, i)->fclist); 518 519 sp->sfb_ifp = ifp; 520 sp->sfb_qlim = qlim; 521 sp->sfb_qid = qid; 522 sp->sfb_flags = (flags & SFBF_USERFLAGS); 523#if !PF_ECN 524 if (sp->sfb_flags & SFBF_ECN) { 525 sp->sfb_flags &= ~SFBF_ECN; 526 log(LOG_ERR, "%s: SFB qid=%d, ECN not available; ignoring " 527 "SFBF_ECN flag!\n", if_name(ifp), sp->sfb_qid); 528 } 529#endif /* !PF_ECN */ 530 531 sfb_resetq(sp, -1); 532 533 return (sp); 534} 535 536static void 537sfb_fclist_append(struct sfb *sp, struct sfb_fcl *fcl) 538{ 539 IFCQ_CONVERT_LOCK(&sp->sfb_ifp->if_snd); 540 541 VERIFY(STAILQ_EMPTY(&fcl->fclist) || fcl->cnt > 0); 542 sp->sfb_stats.flow_feedback += fcl->cnt; 543 fcl->cnt = 0; 544 545 flowadv_add(&fcl->fclist); 546 VERIFY(fcl->cnt == 0 && STAILQ_EMPTY(&fcl->fclist)); 547} 548 549static void 550sfb_fclists_clean(struct sfb *sp) 551{ 552 int i; 553 554 /* Move all the flow control entries to the flowadv list */ 555 for (i = 0; i < SFB_BINS; ++i) { 556 struct sfb_fcl *fcl = SFB_FC_LIST(sp, i); 557 if (!STAILQ_EMPTY(&fcl->fclist)) 558 sfb_fclist_append(sp, fcl); 559 } 560} 561 562void 563sfb_destroy(struct sfb *sp) 564{ 565 sfb_fclists_clean(sp); 566 if (sp->sfb_bins != NULL) { 567 zfree(sfb_bins_zone, sp->sfb_bins); 568 sp->sfb_bins = NULL; 569 } 570 if (sp->sfb_fc_lists != NULL) { 571 zfree(sfb_fcl_zone, sp->sfb_fc_lists); 572 sp->sfb_fc_lists = NULL; 573 } 574 zfree(sfb_zone, sp); 575} 576 577static void 578sfb_resetq(struct sfb *sp, cqev_t ev) 579{ 580 struct ifnet *ifp = sp->sfb_ifp; 581 u_int64_t eff_rate; 582 583 VERIFY(ifp != NULL); 584 585 if (ev != CLASSQ_EV_LINK_DOWN) { 586 (*sp->sfb_bins)[0].fudge = sfb_random(sp); 587 (*sp->sfb_bins)[1].fudge = sfb_random(sp); 588 sp->sfb_allocation = ((sfb_allocation == 0) ? 589 (sp->sfb_qlim / 3) : sfb_allocation); 590 sp->sfb_drop_thresh = sp->sfb_allocation + 591 (sp->sfb_allocation >> 1); 592 } 593 594 sp->sfb_clearpkts = 0; 595 sp->sfb_current = 0; 596 597 eff_rate = ifnet_output_linkrate(ifp); 598 sp->sfb_eff_rate = eff_rate; 599 600 sfb_calc_holdtime(sp, eff_rate); 601 sfb_calc_pboxtime(sp, eff_rate); 602 sfb_calc_hinterval(sp, NULL); 603 sfb_calc_target_qdelay(sp, eff_rate); 604 sfb_calc_update_interval(sp, eff_rate); 605 606 if (ev == CLASSQ_EV_LINK_DOWN || 607 ev == CLASSQ_EV_LINK_UP) 608 sfb_fclists_clean(sp); 609 610 bzero(sp->sfb_bins, sizeof (*sp->sfb_bins)); 611 bzero(&sp->sfb_stats, sizeof (sp->sfb_stats)); 612 613 if (ev == CLASSQ_EV_LINK_DOWN || !classq_verbose) 614 return; 615 616 log(LOG_DEBUG, "%s: SFB qid=%d, holdtime=%llu nsec, " 617 "pboxtime=%llu nsec, allocation=%d, drop_thresh=%d, " 618 "hinterval=%d sec, sfb_bins=%d bytes, eff_rate=%llu bps" 619 "target_qdelay= %llu nsec " 620 "update_interval=%llu sec %llu nsec flags=0x%x\n", 621 if_name(ifp), sp->sfb_qid, (u_int64_t)sp->sfb_holdtime.tv_nsec, 622 (u_int64_t)sp->sfb_pboxtime.tv_nsec, 623 (u_int32_t)sp->sfb_allocation, (u_int32_t)sp->sfb_drop_thresh, 624 (int)sp->sfb_hinterval.tv_sec, (int)sizeof (*sp->sfb_bins), 625 eff_rate, (u_int64_t)sp->sfb_target_qdelay, 626 (u_int64_t)sp->sfb_update_interval.tv_sec, 627 (u_int64_t)sp->sfb_update_interval.tv_nsec, sp->sfb_flags); 628} 629 630void 631sfb_getstats(struct sfb *sp, struct sfb_stats *sps) 632{ 633 sps->allocation = sp->sfb_allocation; 634 sps->dropthresh = sp->sfb_drop_thresh; 635 sps->clearpkts = sp->sfb_clearpkts; 636 sps->current = sp->sfb_current; 637 sps->target_qdelay = sp->sfb_target_qdelay; 638 sps->min_estdelay = sp->sfb_min_qdelay; 639 sps->delay_fcthreshold = sp->sfb_fc_threshold; 640 sps->flags = sp->sfb_flags; 641 642 net_timernsec(&sp->sfb_holdtime, &sp->sfb_stats.hold_time); 643 net_timernsec(&sp->sfb_pboxtime, &sp->sfb_stats.pbox_time); 644 net_timernsec(&sp->sfb_hinterval, &sp->sfb_stats.rehash_intval); 645 net_timernsec(&sp->sfb_update_interval, &sps->update_interval); 646 *(&(sps->sfbstats)) = *(&(sp->sfb_stats)); 647 648 _CASSERT(sizeof ((*sp->sfb_bins)[0].stats) == 649 sizeof (sps->binstats[0].stats)); 650 651 bcopy(&(*sp->sfb_bins)[0].stats, &sps->binstats[0].stats, 652 sizeof (sps->binstats[0].stats)); 653 bcopy(&(*sp->sfb_bins)[1].stats, &sps->binstats[1].stats, 654 sizeof (sps->binstats[1].stats)); 655} 656 657static void 658sfb_swap_bins(struct sfb *sp, u_int32_t len) 659{ 660 int i, j, s; 661 662 if (sp->sfb_flags & SFBF_SUSPENDED) 663 return; 664 665 s = sp->sfb_current; 666 VERIFY((s + (s ^ 1)) == 1); 667 668 (*sp->sfb_bins)[s].fudge = sfb_random(sp); /* recompute perturbation */ 669 sp->sfb_clearpkts = len; 670 sp->sfb_stats.num_rehash++; 671 672 s = (sp->sfb_current ^= 1); /* flip the bit (swap current) */ 673 674 if (classq_verbose) { 675 log(LOG_DEBUG, "%s: SFB qid=%d, set %d is now current, " 676 "qlen=%d\n", if_name(sp->sfb_ifp), sp->sfb_qid, s, len); 677 } 678 679 /* clear freezetime for all current bins */ 680 bzero(&(*sp->sfb_bins)[s].freezetime, 681 sizeof ((*sp->sfb_bins)[s].freezetime)); 682 683 /* clear/adjust bin statistics and flow control lists */ 684 for (i = 0; i < SFB_BINS; i++) { 685 struct sfb_fcl *fcl = SFB_FC_LIST(sp, i); 686 687 if (!STAILQ_EMPTY(&fcl->fclist)) 688 sfb_fclist_append(sp, fcl); 689 690 for (j = 0; j < SFB_LEVELS; j++) { 691 struct sfbbinstats *cbin, *wbin; 692 693 cbin = SFB_BINST(sp, j, i, s); /* current */ 694 wbin = SFB_BINST(sp, j, i, s ^ 1); /* warm-up */ 695 696 cbin->pkts = 0; 697 cbin->bytes = 0; 698 if (cbin->pmark > SFB_MAX_PMARK) 699 cbin->pmark = SFB_MAX_PMARK; 700 if (cbin->pmark < 0) 701 cbin->pmark = 0; 702 703 /* 704 * Keep pmark from before to identify 705 * non-responsives immediately. 706 */ 707 if (wbin->pmark > SFB_PMARK_WARM) 708 wbin->pmark = SFB_PMARK_WARM; 709 } 710 } 711} 712 713static inline int 714sfb_pcheck(struct sfb *sp, struct pkthdr *pkt) 715{ 716#if SFB_LEVELS != 2 717 int i, n; 718#endif /* SFB_LEVELS != 2 */ 719 int s; 720 721 s = sp->sfb_current; 722 VERIFY((s + (s ^ 1)) == 1); 723 724 /* 725 * For current bins, returns 1 if all pmark >= SFB_PMARK_TH, 726 * 0 otherwise; optimize for SFB_LEVELS=2. 727 */ 728#if SFB_LEVELS == 2 729 /* 730 * Level 0: bin index at [0] for set 0; [2] for set 1 731 * Level 1: bin index at [1] for set 0; [3] for set 1 732 */ 733 if (SFB_BINST(sp, 0, SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1)]), 734 s)->pmark < SFB_PMARK_TH || 735 SFB_BINST(sp, 1, SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1) + 1]), 736 s)->pmark < SFB_PMARK_TH) 737 return (0); 738#else /* SFB_LEVELS != 2 */ 739 for (i = 0; i < SFB_LEVELS; i++) { 740 if (s == 0) /* set 0, bin index [0,1] */ 741 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i]); 742 else /* set 1, bin index [2,3] */ 743 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i + 2]); 744 745 if (SFB_BINST(sp, i, n, s)->pmark < SFB_PMARK_TH) 746 return (0); 747 } 748#endif /* SFB_LEVELS != 2 */ 749 return (1); 750} 751 752static int 753sfb_penalize(struct sfb *sp, struct pkthdr *pkt, struct timespec *now) 754{ 755 struct timespec delta = { 0, 0 }; 756 757 /* If minimum pmark of current bins is < SFB_PMARK_TH, we're done */ 758 if (!sfb_ratelimit || !sfb_pcheck(sp, pkt)) 759 return (0); 760 761 net_timersub(now, &sp->sfb_pboxfreeze, &delta); 762 if (net_timercmp(&delta, &sp->sfb_pboxtime, <)) { 763#if SFB_LEVELS != 2 764 int i; 765#endif /* SFB_LEVELS != 2 */ 766 struct sfbbinstats *bin; 767 int n, w; 768 769 w = sp->sfb_current ^ 1; 770 VERIFY((w + (w ^ 1)) == 1); 771 772 /* 773 * Update warm-up bins; optimize for SFB_LEVELS=2 774 */ 775#if SFB_LEVELS == 2 776 /* Level 0: bin index at [0] for set 0; [2] for set 1 */ 777 n = SFB_BINMASK(pkt->pkt_sfb_hash8[(w << 1)]); 778 bin = SFB_BINST(sp, 0, n, w); 779 if (bin->pkts >= sp->sfb_allocation) 780 sfb_increment_bin(sp, bin, SFB_BINFT(sp, 0, n, w), now); 781 782 /* Level 0: bin index at [1] for set 0; [3] for set 1 */ 783 n = SFB_BINMASK(pkt->pkt_sfb_hash8[(w << 1) + 1]); 784 bin = SFB_BINST(sp, 1, n, w); 785 if (bin->pkts >= sp->sfb_allocation) 786 sfb_increment_bin(sp, bin, SFB_BINFT(sp, 1, n, w), now); 787#else /* SFB_LEVELS != 2 */ 788 for (i = 0; i < SFB_LEVELS; i++) { 789 if (w == 0) /* set 0, bin index [0,1] */ 790 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i]); 791 else /* set 1, bin index [2,3] */ 792 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i + 2]); 793 794 bin = SFB_BINST(sp, i, n, w); 795 if (bin->pkts >= sp->sfb_allocation) { 796 sfb_increment_bin(sp, bin, 797 SFB_BINFT(sp, i, n, w), now); 798 } 799 } 800#endif /* SFB_LEVELS != 2 */ 801 return (1); 802 } 803 804 /* non-conformant or else misclassified flow; queue it anyway */ 805 pkt->pkt_sfb_flags |= SFB_PKT_PBOX; 806 *(&sp->sfb_pboxfreeze) = *now; 807 808 return (0); 809} 810 811static void 812sfb_adjust_bin(struct sfb *sp, struct sfbbinstats *bin, struct timespec *ft, 813 struct timespec *now, boolean_t inc) 814{ 815 struct timespec delta; 816 817 net_timersub(now, ft, &delta); 818 if (net_timercmp(&delta, &sp->sfb_holdtime, <)) { 819 if (classq_verbose > 1) { 820 log(LOG_DEBUG, "%s: SFB qid=%d, %s update frozen " 821 "(delta=%llu nsec)\n", if_name(sp->sfb_ifp), 822 sp->sfb_qid, inc ? "increment" : "decrement", 823 (u_int64_t)delta.tv_nsec); 824 } 825 return; 826 } 827 828 /* increment/decrement marking probability */ 829 *ft = *now; 830 if (inc) 831 SFB_PMARK_INC(bin); 832 else 833 SFB_PMARK_DEC(bin); 834} 835 836static void 837sfb_decrement_bin(struct sfb *sp, struct sfbbinstats *bin, struct timespec *ft, 838 struct timespec *now) 839{ 840 return (sfb_adjust_bin(sp, bin, ft, now, FALSE)); 841} 842 843static void 844sfb_increment_bin(struct sfb *sp, struct sfbbinstats *bin, struct timespec *ft, 845 struct timespec *now) 846{ 847 return (sfb_adjust_bin(sp, bin, ft, now, TRUE)); 848} 849 850static inline void 851sfb_dq_update_bins(struct sfb *sp, struct pkthdr *pkt, 852 struct timespec *now, u_int32_t qsize) 853{ 854#if SFB_LEVELS != 2 || SFB_FC_LEVEL != 0 855 int i; 856#endif /* SFB_LEVELS != 2 || SFB_FC_LEVEL != 0 */ 857 struct sfbbinstats *bin; 858 int s, n; 859 struct sfb_fcl *fcl = NULL; 860 861 s = sp->sfb_current; 862 VERIFY((s + (s ^ 1)) == 1); 863 864 /* 865 * Update current bins; optimize for SFB_LEVELS=2 and SFB_FC_LEVEL=0 866 */ 867#if SFB_LEVELS == 2 && SFB_FC_LEVEL == 0 868 /* Level 0: bin index at [0] for set 0; [2] for set 1 */ 869 n = SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1)]); 870 bin = SFB_BINST(sp, 0, n, s); 871 872 VERIFY(bin->pkts > 0 && bin->bytes >= (u_int32_t)pkt->len); 873 bin->pkts--; 874 bin->bytes -= pkt->len; 875 876 if (bin->pkts == 0) 877 sfb_decrement_bin(sp, bin, SFB_BINFT(sp, 0, n, s), now); 878 879 /* Deliver flow control feedback to the sockets */ 880 if (SFB_QUEUE_DELAYBASED(sp)) { 881 if (!(SFB_IS_DELAYHIGH(sp)) || 882 bin->bytes <= sp->sfb_fc_threshold || 883 bin->pkts == 0 || qsize == 0) 884 fcl = SFB_FC_LIST(sp, n); 885 } else if (bin->pkts <= (sp->sfb_allocation >> 2)) { 886 fcl = SFB_FC_LIST(sp, n); 887 } 888 889 if (fcl != NULL && !STAILQ_EMPTY(&fcl->fclist)) 890 sfb_fclist_append(sp, fcl); 891 fcl = NULL; 892 893 /* Level 1: bin index at [1] for set 0; [3] for set 1 */ 894 n = SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1) + 1]); 895 bin = SFB_BINST(sp, 1, n, s); 896 897 VERIFY(bin->pkts > 0 && bin->bytes >= (u_int64_t)pkt->len); 898 bin->pkts--; 899 bin->bytes -= pkt->len; 900 if (bin->pkts == 0) 901 sfb_decrement_bin(sp, bin, SFB_BINFT(sp, 1, n, s), now); 902#else /* SFB_LEVELS != 2 || SFB_FC_LEVEL != 0 */ 903 for (i = 0; i < SFB_LEVELS; i++) { 904 if (s == 0) /* set 0, bin index [0,1] */ 905 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i]); 906 else /* set 1, bin index [2,3] */ 907 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i + 2]); 908 909 bin = SFB_BINST(sp, i, n, s); 910 911 VERIFY(bin->pkts > 0 && bin->bytes >= pkt->len); 912 bin->pkts--; 913 bin->bytes -= pkt->len; 914 if (bin->pkts == 0) 915 sfb_decrement_bin(sp, bin, 916 SFB_BINFT(sp, i, n, s), now); 917 if (i != SFB_FC_LEVEL) 918 continue; 919 if (SFB_QUEUE_DELAYBASED(sp)) { 920 if (!(SFB_IS_DELAYHIGH(sp)) || 921 bin->bytes <= sp->sfb_fc_threshold) 922 fcl = SFB_FC_LIST(sp, n); 923 } else if (bin->pkts <= (sp->sfb_allocation >> 2)) { 924 fcl = SFB_FC_LIST(sp, n); 925 } 926 if (fcl != NULL && !STAILQ_EMPTY(&fcl->fclist)) 927 sfb_fclist_append(sp, fcl); 928 fcl = NULL; 929 } 930#endif /* SFB_LEVELS != 2 || SFB_FC_LEVEL != 0 */ 931} 932 933static inline void 934sfb_eq_update_bins(struct sfb *sp, struct pkthdr *pkt) 935{ 936#if SFB_LEVELS != 2 937 int i, n; 938#endif /* SFB_LEVELS != 2 */ 939 int s; 940 struct sfbbinstats *bin; 941 s = sp->sfb_current; 942 VERIFY((s + (s ^ 1)) == 1); 943 944 /* 945 * Update current bins; optimize for SFB_LEVELS=2 946 */ 947#if SFB_LEVELS == 2 948 /* Level 0: bin index at [0] for set 0; [2] for set 1 */ 949 bin = SFB_BINST(sp, 0, 950 SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1)]), s); 951 bin->pkts++; 952 bin->bytes += pkt->len; 953 954 /* Level 1: bin index at [1] for set 0; [3] for set 1 */ 955 bin = SFB_BINST(sp, 1, 956 SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1) + 1]), s); 957 bin->pkts++; 958 bin->bytes += pkt->len; 959 960#else /* SFB_LEVELS != 2 */ 961 for (i = 0; i < SFB_LEVELS; i++) { 962 if (s == 0) /* set 0, bin index [0,1] */ 963 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i]); 964 else /* set 1, bin index [2,3] */ 965 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i + 2]); 966 967 bin = SFB_BINST(sp, i, n, s); 968 bin->pkts++; 969 bin->bytes += pkt->len; 970 } 971#endif /* SFB_LEVELS != 2 */ 972} 973 974static boolean_t 975sfb_bin_addfcentry(struct sfb *sp, struct pkthdr *pkt) 976{ 977 struct flowadv_fcentry *fce; 978 u_int32_t flowsrc, flowid; 979 struct sfb_fcl *fcl; 980 int s; 981 982 s = sp->sfb_current; 983 VERIFY((s + (s ^ 1)) == 1); 984 985 flowsrc = pkt->pkt_flowsrc; 986 flowid = pkt->pkt_flowid; 987 988 if (flowid == 0) { 989 sp->sfb_stats.null_flowid++; 990 return (FALSE); 991 } 992 993 /* 994 * Use value at index 0 for set 0 and 995 * value at index 2 for set 1 996 */ 997 fcl = SFB_FC_LIST(sp, SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1)])); 998 STAILQ_FOREACH(fce, &fcl->fclist, fce_link) { 999 if (fce->fce_flowsrc == flowsrc && 1000 fce->fce_flowid == flowid) { 1001 /* Already on flow control list; just return */ 1002 return (TRUE); 1003 } 1004 } 1005 1006 IFCQ_CONVERT_LOCK(&sp->sfb_ifp->if_snd); 1007 fce = flowadv_alloc_entry(M_WAITOK); 1008 if (fce != NULL) { 1009 fce->fce_flowsrc = flowsrc; 1010 fce->fce_flowid = flowid; 1011 STAILQ_INSERT_TAIL(&fcl->fclist, fce, fce_link); 1012 fcl->cnt++; 1013 sp->sfb_stats.flow_controlled++; 1014 } 1015 1016 return (fce != NULL); 1017} 1018 1019/* 1020 * check if this flow needs to be flow-controlled or if this 1021 * packet needs to be dropped. 1022 */ 1023static int 1024sfb_bin_mark_or_drop(struct sfb *sp, struct sfbbinstats *bin) 1025{ 1026 int ret = 0; 1027 if (SFB_QUEUE_DELAYBASED(sp)) { 1028 /* 1029 * Mark or drop if this bin has more 1030 * bytes than the flowcontrol threshold. 1031 */ 1032 if (SFB_IS_DELAYHIGH(sp) && 1033 bin->bytes >= (sp->sfb_fc_threshold << 1)) 1034 ret = 1; 1035 } else { 1036 if (bin->pkts >= sp->sfb_allocation && 1037 bin->pkts >= sp->sfb_drop_thresh) 1038 ret = 1; /* drop or mark */ 1039 } 1040 return (ret); 1041} 1042 1043/* 1044 * early-drop probability is kept in pmark of each bin of the flow 1045 */ 1046static int 1047sfb_drop_early(struct sfb *sp, struct pkthdr *pkt, u_int16_t *pmin, 1048 struct timespec *now) 1049{ 1050#if SFB_LEVELS != 2 1051 int i; 1052#endif /* SFB_LEVELS != 2 */ 1053 struct sfbbinstats *bin; 1054 int s, n, ret = 0; 1055 1056 s = sp->sfb_current; 1057 VERIFY((s + (s ^ 1)) == 1); 1058 1059 *pmin = (u_int16_t)-1; 1060 1061 /* 1062 * Update current bins; optimize for SFB_LEVELS=2 1063 */ 1064#if SFB_LEVELS == 2 1065 /* Level 0: bin index at [0] for set 0; [2] for set 1 */ 1066 n = SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1)]); 1067 bin = SFB_BINST(sp, 0, n, s); 1068 if (*pmin > (u_int16_t)bin->pmark) 1069 *pmin = (u_int16_t)bin->pmark; 1070 1071 1072 /* Update SFB probability */ 1073 if (bin->pkts >= sp->sfb_allocation) 1074 sfb_increment_bin(sp, bin, SFB_BINFT(sp, 0, n, s), now); 1075 1076 ret = sfb_bin_mark_or_drop(sp, bin); 1077 1078 /* Level 1: bin index at [1] for set 0; [3] for set 1 */ 1079 n = SFB_BINMASK(pkt->pkt_sfb_hash8[(s << 1) + 1]); 1080 bin = SFB_BINST(sp, 1, n, s); 1081 if (*pmin > (u_int16_t)bin->pmark) 1082 *pmin = (u_int16_t)bin->pmark; 1083 1084 if (bin->pkts >= sp->sfb_allocation) 1085 sfb_increment_bin(sp, bin, SFB_BINFT(sp, 1, n, s), now); 1086#else /* SFB_LEVELS != 2 */ 1087 for (i = 0; i < SFB_LEVELS; i++) { 1088 if (s == 0) /* set 0, bin index [0,1] */ 1089 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i]); 1090 else /* set 1, bin index [2,3] */ 1091 n = SFB_BINMASK(pkt->pkt_sfb_hash8[i + 2]); 1092 1093 bin = SFB_BINST(sp, i, n, s); 1094 if (*pmin > (u_int16_t)bin->pmark) 1095 *pmin = (u_int16_t)bin->pmark; 1096 1097 if (bin->pkts >= sp->sfb_allocation) 1098 sfb_increment_bin(sp, bin, 1099 SFB_BINFT(sp, i, n, s), now); 1100 if (i == SFB_FC_LEVEL) 1101 ret = sfb_bin_mark_or_drop(sp, bin); 1102 } 1103#endif /* SFB_LEVELS != 2 */ 1104 1105 if (sp->sfb_flags & SFBF_SUSPENDED) 1106 ret = 1; /* drop or mark */ 1107 1108 return (ret); 1109} 1110 1111void 1112sfb_detect_dequeue_stall(struct sfb *sp, class_queue_t *q, 1113 struct timespec *now) 1114{ 1115 struct timespec max_getqtime; 1116 1117 if (!SFB_QUEUE_DELAYBASED(sp) || SFB_IS_DELAYHIGH(sp) || 1118 qsize(q) <= SFB_MIN_FC_THRESHOLD_BYTES || 1119 !net_timerisset(&sp->sfb_getqtime)) 1120 return; 1121 1122 net_timeradd(&sp->sfb_getqtime, &sp->sfb_update_interval, 1123 &max_getqtime); 1124 if (net_timercmp(now, &max_getqtime, >)) { 1125 /* 1126 * No packets have been dequeued in an update interval 1127 * worth of time. It means that the queue is stalled 1128 */ 1129 SFB_SET_DELAY_HIGH(sp, q); 1130 sp->sfb_stats.dequeue_stall++; 1131 } 1132} 1133 1134#define DTYPE_NODROP 0 /* no drop */ 1135#define DTYPE_FORCED 1 /* a "forced" drop */ 1136#define DTYPE_EARLY 2 /* an "unforced" (early) drop */ 1137 1138int 1139sfb_addq(struct sfb *sp, class_queue_t *q, struct mbuf *m, struct pf_mtag *t) 1140{ 1141#if !PF_ECN 1142#pragma unused(t) 1143#endif /* !PF_ECN */ 1144 struct pkthdr *pkt = &m->m_pkthdr; 1145 struct timespec now; 1146 int droptype, s; 1147 u_int16_t pmin; 1148 int fc_adv = 0; 1149 int ret = CLASSQEQ_SUCCESS; 1150 1151 nanouptime(&now); 1152 1153 s = sp->sfb_current; 1154 VERIFY((s + (s ^ 1)) == 1); 1155 1156 /* See comments in <rdar://problem/14040693> */ 1157 VERIFY(!(pkt->pkt_flags & PKTF_PRIV_GUARDED)); 1158 pkt->pkt_flags |= PKTF_PRIV_GUARDED; 1159 1160 /* time to swap the bins? */ 1161 if (net_timercmp(&now, &sp->sfb_nextreset, >=)) { 1162 net_timeradd(&now, &sp->sfb_hinterval, &sp->sfb_nextreset); 1163 sfb_swap_bins(sp, qlen(q)); 1164 s = sp->sfb_current; 1165 VERIFY((s + (s ^ 1)) == 1); 1166 } 1167 1168 if (!net_timerisset(&sp->sfb_update_time)) { 1169 net_timeradd(&now, &sp->sfb_update_interval, 1170 &sp->sfb_update_time); 1171 } 1172 1173 pkt->pkt_sfb_flags = 0; 1174 pkt->pkt_sfb_hash16[s] = 1175 (SFB_HASH(&pkt->pkt_flowid, sizeof (pkt->pkt_flowid), 1176 (*sp->sfb_bins)[s].fudge) & SFB_HASHMASK); 1177 pkt->pkt_sfb_hash16[s ^ 1] = 1178 (SFB_HASH(&pkt->pkt_flowid, sizeof (pkt->pkt_flowid), 1179 (*sp->sfb_bins)[s ^ 1].fudge) & SFB_HASHMASK); 1180 1181 /* check if the queue has been stalled */ 1182 sfb_detect_dequeue_stall(sp, q, &now); 1183 1184 /* see if we drop early */ 1185 droptype = DTYPE_NODROP; 1186 if (sfb_drop_early(sp, pkt, &pmin, &now)) { 1187 /* flow control, mark or drop by sfb */ 1188 if ((sp->sfb_flags & SFBF_FLOWCTL) && 1189 (pkt->pkt_flags & PKTF_FLOW_ADV)) { 1190 fc_adv = 1; 1191 /* drop all during suspension or for non-TCP */ 1192 if ((sp->sfb_flags & SFBF_SUSPENDED) || 1193 pkt->pkt_proto != IPPROTO_TCP) { 1194 droptype = DTYPE_EARLY; 1195 sp->sfb_stats.drop_early++; 1196 } 1197 } 1198#if PF_ECN 1199 else if ((sp->sfb_flags & SFBF_ECN) && 1200 (pkt->pkt_proto == IPPROTO_TCP) && /* only for TCP */ 1201 ((sfb_random(sp) & SFB_MAX_PMARK) <= pmin) && 1202 mark_ecn(m, t, sp->sfb_flags) && 1203 !(sp->sfb_flags & SFBF_SUSPENDED)) { 1204 /* successfully marked; do not drop. */ 1205 sp->sfb_stats.marked_packets++; 1206 } 1207#endif /* PF_ECN */ 1208 else { 1209 /* unforced drop by sfb */ 1210 droptype = DTYPE_EARLY; 1211 sp->sfb_stats.drop_early++; 1212 } 1213 } 1214 1215 /* non-responsive flow penalty? */ 1216 if (droptype == DTYPE_NODROP && sfb_penalize(sp, pkt, &now)) { 1217 droptype = DTYPE_FORCED; 1218 sp->sfb_stats.drop_pbox++; 1219 } 1220 1221 /* 1222 * if max queue size is static, make it a forced drop 1223 * when the queue length hits the queue limit 1224 */ 1225 if (!(SFB_QUEUE_DELAYBASED(sp)) && 1226 droptype == DTYPE_NODROP && qlen(q) >= qlimit(q)) { 1227 droptype = DTYPE_FORCED; 1228 sp->sfb_stats.drop_queue++; 1229 } 1230 1231 /* 1232 * delay based queues have a larger maximum size to 1233 * allow for bursts 1234 */ 1235 if (SFB_QUEUE_DELAYBASED(sp) && 1236 droptype == DTYPE_NODROP && 1237 qlen(q) >= SFB_QUEUE_DELAYBASED_MAXSIZE) { 1238 droptype = DTYPE_FORCED; 1239 sp->sfb_stats.drop_queue++; 1240 } 1241 1242 if (fc_adv == 1 && droptype != DTYPE_FORCED && 1243 sfb_bin_addfcentry(sp, pkt)) { 1244 /* deliver flow control advisory error */ 1245 if (droptype == DTYPE_NODROP) { 1246 ret = CLASSQEQ_SUCCESS_FC; 1247 VERIFY(!(sp->sfb_flags & SFBF_SUSPENDED)); 1248 } else if (sp->sfb_flags & SFBF_SUSPENDED) { 1249 /* dropped due to suspension */ 1250 ret = CLASSQEQ_DROPPED_SP; 1251 } else { 1252 /* dropped due to flow-control */ 1253 ret = CLASSQEQ_DROPPED_FC; 1254 } 1255 } 1256 /* if successful enqueue this packet, else drop it */ 1257 if (droptype == DTYPE_NODROP) { 1258 net_timernsec(&now, &pkt->pkt_enqueue_ts); 1259 _addq(q, m); 1260 } else { 1261 IFCQ_CONVERT_LOCK(&sp->sfb_ifp->if_snd); 1262 m_freem(m); 1263 return ((ret != CLASSQEQ_SUCCESS) ? ret : CLASSQEQ_DROPPED); 1264 } 1265 1266 if (!(pkt->pkt_sfb_flags & SFB_PKT_PBOX)) 1267 sfb_eq_update_bins(sp, pkt); 1268 else 1269 sp->sfb_stats.pbox_packets++; 1270 1271 /* successfully queued */ 1272 return (ret); 1273} 1274 1275static struct mbuf * 1276sfb_getq_flow(struct sfb *sp, class_queue_t *q, u_int32_t flow, boolean_t purge) 1277{ 1278 struct timespec now; 1279 struct mbuf *m; 1280 struct pkthdr *pkt; 1281 1282 if (!purge && (sp->sfb_flags & SFBF_SUSPENDED)) 1283 return (NULL); 1284 1285 nanouptime(&now); 1286 1287 /* flow of 0 means head of queue */ 1288 if ((m = ((flow == 0) ? _getq(q) : _getq_flow(q, flow))) == NULL) { 1289 if (!purge) 1290 net_timerclear(&sp->sfb_getqtime); 1291 return (NULL); 1292 } 1293 1294 VERIFY(m->m_flags & M_PKTHDR); 1295 1296 pkt = &m->m_pkthdr; 1297 VERIFY(pkt->pkt_flags & PKTF_PRIV_GUARDED); 1298 1299 if (!purge) { 1300 /* calculate EWMA of dequeues */ 1301 if (net_timerisset(&sp->sfb_getqtime)) { 1302 struct timespec delta; 1303 u_int64_t avg, new; 1304 net_timersub(&now, &sp->sfb_getqtime, &delta); 1305 net_timernsec(&delta, &new); 1306 avg = sp->sfb_stats.dequeue_avg; 1307 if (avg > 0) { 1308 int decay = DEQUEUE_DECAY; 1309 /* 1310 * If the time since last dequeue is 1311 * significantly greater than the current 1312 * average, weigh the average more against 1313 * the old value. 1314 */ 1315 if (DEQUEUE_SPIKE(new, avg)) 1316 decay += 5; 1317 avg = (((avg << decay) - avg) + new) >> decay; 1318 } else { 1319 avg = new; 1320 } 1321 sp->sfb_stats.dequeue_avg = avg; 1322 } 1323 *(&sp->sfb_getqtime) = *(&now); 1324 } 1325 1326 if (!purge && SFB_QUEUE_DELAYBASED(sp)) { 1327 u_int64_t dequeue_ns, queue_delay = 0; 1328 net_timernsec(&now, &dequeue_ns); 1329 if (dequeue_ns > pkt->pkt_enqueue_ts) 1330 queue_delay = dequeue_ns - pkt->pkt_enqueue_ts; 1331 1332 if (sp->sfb_min_qdelay == 0 || 1333 (queue_delay > 0 && queue_delay < sp->sfb_min_qdelay)) 1334 sp->sfb_min_qdelay = queue_delay; 1335 if (net_timercmp(&now, &sp->sfb_update_time, >=)) { 1336 if (sp->sfb_min_qdelay > sp->sfb_target_qdelay) { 1337 if (!SFB_IS_DELAYHIGH(sp)) 1338 SFB_SET_DELAY_HIGH(sp, q); 1339 } else { 1340 sp->sfb_flags &= ~(SFBF_DELAYHIGH); 1341 sp->sfb_fc_threshold = 0; 1342 1343 } 1344 net_timeradd(&now, &sp->sfb_update_interval, 1345 &sp->sfb_update_time); 1346 sp->sfb_min_qdelay = 0; 1347 } 1348 } 1349 1350 /* 1351 * Clearpkts are the ones which were in the queue when the hash 1352 * function was perturbed. Since the perturbation value (fudge), 1353 * and thus bin information for these packets is not known, we do 1354 * not change accounting information while dequeuing these packets. 1355 * It is important not to set the hash interval too small due to 1356 * this reason. A rule of thumb is to set it to K*D, where D is 1357 * the time taken to drain queue. 1358 */ 1359 if (pkt->pkt_sfb_flags & SFB_PKT_PBOX) { 1360 pkt->pkt_sfb_flags &= ~SFB_PKT_PBOX; 1361 if (sp->sfb_clearpkts > 0) 1362 sp->sfb_clearpkts--; 1363 } else if (sp->sfb_clearpkts > 0) { 1364 sp->sfb_clearpkts--; 1365 } else { 1366 sfb_dq_update_bins(sp, pkt, &now, qsize(q)); 1367 } 1368 1369 /* See comments in <rdar://problem/14040693> */ 1370 pkt->pkt_flags &= ~PKTF_PRIV_GUARDED; 1371 1372 /* 1373 * If the queue becomes empty before the update interval, reset 1374 * the flow control threshold 1375 */ 1376 if (qsize(q) == 0) { 1377 sp->sfb_flags &= ~SFBF_DELAYHIGH; 1378 sp->sfb_min_qdelay = 0; 1379 sp->sfb_fc_threshold = 0; 1380 net_timerclear(&sp->sfb_update_time); 1381 } 1382 1383 return (m); 1384} 1385 1386struct mbuf * 1387sfb_getq(struct sfb *sp, class_queue_t *q) 1388{ 1389 return (sfb_getq_flow(sp, q, 0, FALSE)); 1390} 1391 1392void 1393sfb_purgeq(struct sfb *sp, class_queue_t *q, u_int32_t flow, u_int32_t *packets, 1394 u_int32_t *bytes) 1395{ 1396 u_int32_t cnt = 0, len = 0; 1397 struct mbuf *m; 1398 1399 IFCQ_CONVERT_LOCK(&sp->sfb_ifp->if_snd); 1400 1401 while ((m = sfb_getq_flow(sp, q, flow, TRUE)) != NULL) { 1402 cnt++; 1403 len += m_pktlen(m); 1404 m_freem(m); 1405 } 1406 1407 if (packets != NULL) 1408 *packets = cnt; 1409 if (bytes != NULL) 1410 *bytes = len; 1411} 1412 1413void 1414sfb_updateq(struct sfb *sp, cqev_t ev) 1415{ 1416 struct ifnet *ifp = sp->sfb_ifp; 1417 1418 VERIFY(ifp != NULL); 1419 1420 switch (ev) { 1421 case CLASSQ_EV_LINK_BANDWIDTH: { 1422 u_int64_t eff_rate = ifnet_output_linkrate(ifp); 1423 1424 /* update parameters only if rate has changed */ 1425 if (eff_rate == sp->sfb_eff_rate) 1426 break; 1427 1428 if (classq_verbose) { 1429 log(LOG_DEBUG, "%s: SFB qid=%d, adapting to new " 1430 "eff_rate=%llu bps\n", if_name(ifp), sp->sfb_qid, 1431 eff_rate); 1432 } 1433 sfb_calc_holdtime(sp, eff_rate); 1434 sfb_calc_pboxtime(sp, eff_rate); 1435 sfb_calc_target_qdelay(sp, eff_rate); 1436 sfb_calc_update_interval(sp, eff_rate); 1437 break; 1438 } 1439 1440 case CLASSQ_EV_LINK_UP: 1441 case CLASSQ_EV_LINK_DOWN: 1442 if (classq_verbose) { 1443 log(LOG_DEBUG, "%s: SFB qid=%d, resetting due to " 1444 "link %s\n", if_name(ifp), sp->sfb_qid, 1445 (ev == CLASSQ_EV_LINK_UP) ? "UP" : "DOWN"); 1446 } 1447 sfb_resetq(sp, ev); 1448 break; 1449 1450 case CLASSQ_EV_LINK_LATENCY: 1451 case CLASSQ_EV_LINK_MTU: 1452 default: 1453 break; 1454 } 1455} 1456 1457int 1458sfb_suspendq(struct sfb *sp, class_queue_t *q, boolean_t on) 1459{ 1460#pragma unused(q) 1461 struct ifnet *ifp = sp->sfb_ifp; 1462 1463 VERIFY(ifp != NULL); 1464 1465 if ((on && (sp->sfb_flags & SFBF_SUSPENDED)) || 1466 (!on && !(sp->sfb_flags & SFBF_SUSPENDED))) 1467 return (0); 1468 1469 if (!(sp->sfb_flags & SFBF_FLOWCTL)) { 1470 log(LOG_ERR, "%s: SFB qid=%d, unable to %s queue since " 1471 "flow-control is not enabled", if_name(ifp), sp->sfb_qid, 1472 (on ? "suspend" : "resume")); 1473 return (ENOTSUP); 1474 } 1475 1476 if (classq_verbose) { 1477 log(LOG_DEBUG, "%s: SFB qid=%d, setting state to %s", 1478 if_name(ifp), sp->sfb_qid, (on ? "SUSPENDED" : "RUNNING")); 1479 } 1480 1481 if (on) { 1482 sp->sfb_flags |= SFBF_SUSPENDED; 1483 } else { 1484 sp->sfb_flags &= ~SFBF_SUSPENDED; 1485 sfb_swap_bins(sp, qlen(q)); 1486 } 1487 1488 return (0); 1489} 1490