This is xnu-12377.1.9. See this file in:
/*
* Copyright (c) 2016-2021 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. The rights granted to you under the License
* may not be used to create, or enable the creation or redistribution of,
* unlawful or unlicensed copies of an Apple operating system, or to
* circumvent, violate, or enable the circumvention or violation of, any
* terms of an Apple operating system software license agreement.
*
* Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
*/
/*
* The migration of flow queue between the different states is summarised in
* the below state diagram. (RFC 8290)
*
* +-----------------+ +------------------+
* | | Empty | |
* | Empty |<---------------+ Old +----+
* | | | | |
* +-------+---------+ +------------------+ |
* | ^ ^ |Credits
* |Arrival | | |Exhausted
* v | | |
* +-----------------+ | | |
* | | Empty or | | |
* | New +-------------------+ +-------+
* | | Credits Exhausted
* +-----------------+
*
* In this implementation of FQ-CODEL, flow queue is a dynamically allocated
* object. An active flow queue goes through the above cycle of state
* transitions very often. To avoid the cost of frequent flow queue object
* allocation/free, this implementation retains the flow queue object in
* [Empty] state on an Empty flow queue list with an active reference in flow
* queue hash table. The flow queue objects on the Empty flow queue list have
* an associated age and are purged accordingly.
*/
#include <sys/cdefs.h>
#include <sys/param.h>
#include <sys/mbuf.h>
#include <sys/socket.h>
#include <sys/sockio.h>
#include <sys/systm.h>
#include <sys/syslog.h>
#include <sys/proc.h>
#include <sys/errno.h>
#include <sys/kernel.h>
#include <sys/kauth.h>
#include <sys/sdt.h>
#include <kern/zalloc.h>
#include <netinet/in.h>
#include <net/classq/classq.h>
#include <net/classq/if_classq.h>
#include <net/pktsched/pktsched.h>
#include <net/pktsched/pktsched_fq_codel.h>
#include <net/classq/classq_fq_codel.h>
#include <net/droptap.h>
#include <netinet/tcp_var.h>
#define FQ_ZONE_MAX (32 * 1024) /* across all interfaces */
#define DTYPE_NODROP 0 /* no drop */
#define DTYPE_FORCED 1 /* a "forced" drop */
#define DTYPE_EARLY 2 /* an "unforced" (early) drop */
static uint32_t pkt_compressor = 1;
static uint64_t l4s_ce_threshold = 0; /* in usec */
static uint32_t l4s_local_ce_report = 0;
static uint64_t pkt_pacing_leeway = 0; /* in usec */
static uint64_t max_pkt_pacing_interval = 3 * NSEC_PER_SEC;
static uint64_t l4s_min_delay_threshold = 20 * NSEC_PER_MSEC; /* 20 ms */
#if (DEBUG || DEVELOPMENT)
SYSCTL_NODE(_net_classq, OID_AUTO, flow_q, CTLFLAG_RW | CTLFLAG_LOCKED,
0, "FQ-CODEL parameters");
SYSCTL_UINT(_net_classq_flow_q, OID_AUTO, pkt_compressor,
CTLFLAG_RW | CTLFLAG_LOCKED, &pkt_compressor, 0, "enable pkt compression");
SYSCTL_QUAD(_net_classq, OID_AUTO, l4s_ce_threshold,
CTLFLAG_RW | CTLFLAG_LOCKED, &l4s_ce_threshold,
"L4S CE threshold");
SYSCTL_UINT(_net_classq_flow_q, OID_AUTO, l4s_local_ce_report,
CTLFLAG_RW | CTLFLAG_LOCKED, &l4s_local_ce_report, 0,
"enable L4S local CE report");
SYSCTL_QUAD(_net_classq_flow_q, OID_AUTO, pkt_pacing_leeway,
CTLFLAG_RW | CTLFLAG_LOCKED, &pkt_pacing_leeway, "packet pacing leeway");
SYSCTL_QUAD(_net_classq_flow_q, OID_AUTO, max_pkt_pacing_interval,
CTLFLAG_RW | CTLFLAG_LOCKED, &max_pkt_pacing_interval, "max packet pacing interval");
SYSCTL_QUAD(_net_classq_flow_q, OID_AUTO, l4s_min_delay_threshold,
CTLFLAG_RW | CTLFLAG_LOCKED, &l4s_min_delay_threshold, "l4s min delay threshold");
#endif /* (DEBUG || DEVELOPMENT) */
void
fq_codel_init(void)
{
static_assert(AQM_KTRACE_AON_FLOW_HIGH_DELAY == 0x8300004);
static_assert(AQM_KTRACE_AON_THROTTLE == 0x8300008);
static_assert(AQM_KTRACE_AON_FLOW_OVERWHELMING == 0x830000c);
static_assert(AQM_KTRACE_AON_FLOW_DQ_STALL == 0x8300010);
static_assert(AQM_KTRACE_STATS_FLOW_ENQUEUE == 0x8310004);
static_assert(AQM_KTRACE_STATS_FLOW_DEQUEUE == 0x8310008);
static_assert(AQM_KTRACE_STATS_FLOW_CTL == 0x831000c);
static_assert(AQM_KTRACE_STATS_FLOW_ALLOC == 0x8310010);
static_assert(AQM_KTRACE_STATS_FLOW_DESTROY == 0x8310014);
static_assert(AQM_KTRACE_STATS_FLOW_REPORT_CE == 0x8310018);
static_assert(AQM_KTRACE_STATS_GET_QLEN == 0x831001c);
static_assert(AQM_KTRACE_TX_NOT_READY == 0x8310020);
static_assert(AQM_KTRACE_TX_PACEMAKER == 0x8310024);
static_assert(AQM_KTRACE_PKT_DROP == 0x8310028);
static_assert(AQM_KTRACE_OK_TO_DROP == 0x831002c);
static_assert(AQM_KTRACE_CONGESTION_INC == 0x8310030);
static_assert(AQM_KTRACE_CONGESTION_NOTIFIED == 0x8310034);
}
fq_t *
fq_alloc(classq_pkt_type_t ptype)
{
fq_t *fq = NULL;
fq = kalloc_type(fq_t, Z_WAITOK_ZERO);
if (ptype == QP_MBUF) {
MBUFQ_INIT(&fq->fq_mbufq);
}
#if SKYWALK
else {
VERIFY(ptype == QP_PACKET);
KPKTQ_INIT(&fq->fq_kpktq);
}
#endif /* SKYWALK */
CLASSQ_PKT_INIT(&fq->fq_dq_head);
CLASSQ_PKT_INIT(&fq->fq_dq_tail);
fq->fq_in_dqlist = false;
return fq;
}
void
fq_destroy(fq_t *fq, classq_pkt_type_t ptype)
{
VERIFY(!fq->fq_in_dqlist);
VERIFY(fq_empty(fq, ptype));
VERIFY(!(fq->fq_flags & (FQF_NEW_FLOW | FQF_OLD_FLOW |
FQF_EMPTY_FLOW)));
VERIFY(fq->fq_bytes == 0);
kfree_type(fq_t, fq);
}
static inline void
fq_detect_dequeue_stall(fq_if_t *fqs, fq_t *flowq, fq_if_classq_t *fq_cl,
u_int64_t *now)
{
u_int64_t maxgetqtime, update_interval;
if (FQ_IS_DELAY_HIGH(flowq) || flowq->fq_getqtime == 0 ||
fq_empty(flowq, fqs->fqs_ptype) ||
flowq->fq_bytes < FQ_MIN_FC_THRESHOLD_BYTES) {
return;
}
update_interval = FQ_UPDATE_INTERVAL(flowq);
maxgetqtime = flowq->fq_getqtime + update_interval;
if ((*now) > maxgetqtime) {
/*
* there was no dequeue in an update interval worth of
* time. It means that the queue is stalled.
*/
FQ_SET_DELAY_HIGH(flowq);
fq_cl->fcl_stat.fcl_dequeue_stall++;
os_log_error(OS_LOG_DEFAULT, "%s:num: %d, "
"scidx: %d, flow: 0x%x, iface: %s grp: %hhu", __func__,
fq_cl->fcl_stat.fcl_dequeue_stall, flowq->fq_sc_index,
flowq->fq_flowhash, if_name(fqs->fqs_ifq->ifcq_ifp),
FQ_GROUP(flowq)->fqg_index);
KDBG(AQM_KTRACE_AON_FLOW_DQ_STALL, flowq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(flowq), flowq->fq_bytes,
(*now) - flowq->fq_getqtime);
}
}
void
fq_head_drop(fq_if_t *fqs, fq_t *fq)
{
pktsched_pkt_t pkt;
volatile uint32_t *__single pkt_flags;
uint64_t *__single pkt_timestamp;
struct ifclassq *ifq = fqs->fqs_ifq;
_PKTSCHED_PKT_INIT(&pkt);
fq_getq_flow_internal(fqs, fq, &pkt);
if (pkt.pktsched_pkt_mbuf == NULL) {
return;
}
pktsched_get_pkt_vars(&pkt, &pkt_flags, &pkt_timestamp, NULL, NULL,
NULL, NULL, NULL);
*pkt_timestamp = 0;
switch (pkt.pktsched_ptype) {
case QP_MBUF:
*pkt_flags &= ~PKTF_PRIV_GUARDED;
break;
#if SKYWALK
case QP_PACKET:
/* sanity check */
ASSERT((*pkt_flags & ~PKT_F_COMMON_MASK) == 0);
break;
#endif /* SKYWALK */
default:
VERIFY(0);
/* NOTREACHED */
__builtin_unreachable();
}
IFCQ_DROP_ADD(ifq, 1, pktsched_get_pkt_len(&pkt));
IFCQ_CONVERT_LOCK(ifq);
pktsched_free_pkt(&pkt);
}
static int
fq_compressor(fq_if_t *fqs, fq_t *fq, fq_if_classq_t *fq_cl,
pktsched_pkt_t *pkt)
{
classq_pkt_type_t ptype = fqs->fqs_ptype;
uint32_t comp_gencnt = 0;
uint64_t *__single pkt_timestamp;
uint64_t old_timestamp = 0;
uint32_t old_pktlen = 0;
struct ifclassq *ifq = fqs->fqs_ifq;
if (__improbable(pkt_compressor == 0)) {
return 0;
}
pktsched_get_pkt_vars(pkt, NULL, &pkt_timestamp, NULL, NULL, NULL,
&comp_gencnt, NULL);
if (comp_gencnt == 0) {
return 0;
}
fq_cl->fcl_stat.fcl_pkts_compressible++;
if (fq_empty(fq, fqs->fqs_ptype)) {
return 0;
}
if (ptype == QP_MBUF) {
struct mbuf *m = MBUFQ_LAST(&fq->fq_mbufq);
if (comp_gencnt != m->m_pkthdr.comp_gencnt) {
return 0;
}
/* If we got until here, we should merge/replace the segment */
MBUFQ_REMOVE(&fq->fq_mbufq, m);
old_pktlen = m_pktlen(m);
old_timestamp = m->m_pkthdr.pkt_timestamp;
IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
if (__improbable(droptap_verbose > 0)) {
droptap_output_mbuf(m, DROP_REASON_AQM_COMPRESSED, NULL, 0, 0,
fqs->fqs_ifq->ifcq_ifp);
}
m_freem(m);
}
#if SKYWALK
else {
struct __kern_packet *kpkt = KPKTQ_LAST(&fq->fq_kpktq);
if (comp_gencnt != kpkt->pkt_comp_gencnt) {
return 0;
}
/* If we got until here, we should merge/replace the segment */
KPKTQ_REMOVE(&fq->fq_kpktq, kpkt);
old_pktlen = kpkt->pkt_length;
old_timestamp = kpkt->pkt_timestamp;
IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
if (__improbable(droptap_verbose > 0)) {
droptap_output_packet(SK_PKT2PH(kpkt), DROP_REASON_AQM_COMPRESSED, NULL, 0, 0,
fqs->fqs_ifq->ifcq_ifp, 0, NULL, -1, NULL, 0, 0);
}
struct kern_pbufpool *pp =
__DECONST(struct kern_pbufpool *, ((struct __kern_quantum *)kpkt)->qum_pp);
pp_free_packet(pp, (uint64_t)kpkt);
}
#endif /* SKYWALK */
fq->fq_bytes -= old_pktlen;
fq_cl->fcl_stat.fcl_byte_cnt -= old_pktlen;
fq_cl->fcl_stat.fcl_pkt_cnt--;
IFCQ_DEC_LEN(ifq);
IFCQ_DEC_BYTES(ifq, old_pktlen);
FQ_GRP_DEC_LEN(fq);
FQ_GRP_DEC_BYTES(fq, old_pktlen);
*pkt_timestamp = old_timestamp;
return CLASSQEQ_COMPRESSED;
}
int
fq_codel_enq_legacy(void *fqs_p, fq_if_group_t *fq_grp, pktsched_pkt_t *pkt,
fq_if_classq_t *fq_cl)
{
fq_if_t *fqs = (fq_if_t *)fqs_p;
int droptype = DTYPE_NODROP, fc_adv = 0, ret = CLASSQEQ_SUCCESS;
u_int64_t now;
fq_t *fq = NULL;
uint64_t *__single pkt_timestamp;
volatile uint32_t *__single pkt_flags;
uint32_t pkt_flowid, cnt;
uint8_t pkt_proto, pkt_flowsrc;
fq_tfc_type_t tfc_type = FQ_TFC_C;
cnt = pkt->pktsched_pcnt;
pktsched_get_pkt_vars(pkt, &pkt_flags, &pkt_timestamp, &pkt_flowid,
&pkt_flowsrc, &pkt_proto, NULL, NULL);
/*
* XXX Not walking the chain to set this flag on every packet.
* This flag is only used for debugging. Nothing is affected if it's
* not set.
*/
switch (pkt->pktsched_ptype) {
case QP_MBUF:
/* See comments in <rdar://problem/14040693> */
VERIFY(!(*pkt_flags & PKTF_PRIV_GUARDED));
*pkt_flags |= PKTF_PRIV_GUARDED;
break;
#if SKYWALK
case QP_PACKET:
/* sanity check */
ASSERT((*pkt_flags & ~PKT_F_COMMON_MASK) == 0);
break;
#endif /* SKYWALK */
default:
VERIFY(0);
/* NOTREACHED */
__builtin_unreachable();
}
if (fq_codel_enable_l4s) {
tfc_type = pktsched_is_pkt_l4s(pkt) ? FQ_TFC_L4S : FQ_TFC_C;
}
/*
* Timestamps for every packet must be set prior to entering this path.
*/
now = *pkt_timestamp;
ASSERT(now > 0);
/* find the flowq for this packet */
fq = fq_if_hash_pkt(fqs, fq_grp, pkt_flowid, pktsched_get_pkt_svc(pkt),
now, pkt_proto, pkt_flowsrc, tfc_type, true);
if (__improbable(fq == NULL)) {
DTRACE_IP1(memfail__drop, fq_if_t *, fqs);
/* drop the packet if we could not allocate a flow queue */
fq_cl->fcl_stat.fcl_drop_memfailure += cnt;
return CLASSQEQ_DROP;
}
VERIFY(fq->fq_group == fq_grp);
VERIFY(fqs->fqs_ptype == pkt->pktsched_ptype);
KDBG(AQM_KTRACE_STATS_FLOW_ENQUEUE, fq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(fq),
fq->fq_bytes, pktsched_get_pkt_len(pkt));
fq_detect_dequeue_stall(fqs, fq, fq_cl, &now);
/*
* Skip the dropping part if it's L4S. Flow control or ECN marking decision
* will be made at dequeue time.
*/
if (fq_codel_enable_l4s && tfc_type == FQ_TFC_L4S) {
fq_cl->fcl_stat.fcl_l4s_pkts += cnt;
droptype = DTYPE_NODROP;
}
if (__improbable(FQ_IS_DELAY_HIGH(fq) || FQ_IS_OVERWHELMING(fq))) {
if ((fq->fq_flags & FQF_FLOWCTL_CAPABLE) &&
(*pkt_flags & PKTF_FLOW_ADV)) {
fc_adv = 1;
/*
* If the flow is suspended or it is not
* TCP/QUIC, drop the chain.
*/
if ((pkt_proto != IPPROTO_TCP) &&
(pkt_proto != IPPROTO_QUIC)) {
droptype = DTYPE_EARLY;
fq_cl->fcl_stat.fcl_drop_early += cnt;
IFCQ_DROP_ADD(fqs->fqs_ifq, cnt, pktsched_get_pkt_len(pkt));
}
DTRACE_IP6(flow__adv, fq_if_t *, fqs,
fq_if_classq_t *, fq_cl, fq_t *, fq,
int, droptype, pktsched_pkt_t *, pkt,
uint32_t, cnt);
} else {
/*
* Need to drop packets to make room for the new
* ones. Try to drop from the head of the queue
* instead of the latest packets.
*/
if (!fq_empty(fq, fqs->fqs_ptype)) {
uint32_t i;
for (i = 0; i < cnt; i++) {
fq_head_drop(fqs, fq);
}
droptype = DTYPE_NODROP;
} else {
droptype = DTYPE_EARLY;
}
fq_cl->fcl_stat.fcl_drop_early += cnt;
DTRACE_IP6(no__flow__adv, fq_if_t *, fqs,
fq_if_classq_t *, fq_cl, fq_t *, fq,
int, droptype, pktsched_pkt_t *, pkt,
uint32_t, cnt);
}
}
/* Set the return code correctly */
if (__improbable(fc_adv == 1 && droptype != DTYPE_FORCED)) {
if (fq_if_add_fcentry(fqs, pkt, pkt_flowsrc, fq, fq_cl)) {
fq->fq_flags |= FQF_FLOWCTL_ON;
/* deliver flow control advisory error */
if (droptype == DTYPE_NODROP) {
ret = CLASSQEQ_SUCCESS_FC;
} else {
/* dropped due to flow control */
ret = CLASSQEQ_DROP_FC;
}
} else {
/*
* if we could not flow control the flow, it is
* better to drop
*/
droptype = DTYPE_FORCED;
ret = CLASSQEQ_DROP_FC;
fq_cl->fcl_stat.fcl_flow_control_fail++;
}
DTRACE_IP3(fc__ret, fq_if_t *, fqs, int, droptype, int, ret);
}
/*
* If the queue length hits the queue limit, drop a chain with the
* same number of packets from the front of the queue for a flow with
* maximum number of bytes. This will penalize heavy and unresponsive
* flows. It will also avoid a tail drop.
*/
if (__improbable(droptype == DTYPE_NODROP &&
fq_if_at_drop_limit(fqs))) {
uint32_t i;
if (fqs->fqs_large_flow == fq) {
/*
* Drop from the head of the current fq. Since a
* new packet will be added to the tail, it is ok
* to leave fq in place.
*/
DTRACE_IP5(large__flow, fq_if_t *, fqs,
fq_if_classq_t *, fq_cl, fq_t *, fq,
pktsched_pkt_t *, pkt, uint32_t, cnt);
for (i = 0; i < cnt; i++) {
fq_head_drop(fqs, fq);
}
fq_cl->fcl_stat.fcl_drop_overflow += cnt;
/*
* TCP and QUIC will react to the loss of those head dropped pkts
* and adjust send rate.
*/
if ((fq->fq_flags & FQF_FLOWCTL_CAPABLE) &&
(*pkt_flags & PKTF_FLOW_ADV) &&
(pkt_proto != IPPROTO_TCP) &&
(pkt_proto != IPPROTO_QUIC)) {
if (fq_if_add_fcentry(fqs, pkt, pkt_flowsrc, fq, fq_cl)) {
fq->fq_flags |= FQF_FLOWCTL_ON;
FQ_SET_OVERWHELMING(fq);
fq_cl->fcl_stat.fcl_overwhelming++;
/* deliver flow control advisory error */
ret = CLASSQEQ_SUCCESS_FC;
}
}
} else {
if (fqs->fqs_large_flow == NULL) {
droptype = DTYPE_FORCED;
fq_cl->fcl_stat.fcl_drop_overflow += cnt;
ret = CLASSQEQ_DROP;
DTRACE_IP5(no__large__flow, fq_if_t *, fqs,
fq_if_classq_t *, fq_cl, fq_t *, fq,
pktsched_pkt_t *, pkt, uint32_t, cnt);
/*
* if this fq was freshly created and there
* is nothing to enqueue, move it to empty list
*/
if (fq_empty(fq, fqs->fqs_ptype) &&
!(fq->fq_flags & (FQF_NEW_FLOW |
FQF_OLD_FLOW))) {
fq_if_move_to_empty_flow(fqs, fq_cl,
fq, now);
fq = NULL;
}
} else {
DTRACE_IP5(different__large__flow,
fq_if_t *, fqs, fq_if_classq_t *, fq_cl,
fq_t *, fq, pktsched_pkt_t *, pkt,
uint32_t, cnt);
for (i = 0; i < cnt; i++) {
fq_if_drop_packet(fqs, now);
}
}
}
}
fq_cl->fcl_flags &= ~FCL_PACED;
if (__probable(droptype == DTYPE_NODROP)) {
uint32_t chain_len = pktsched_get_pkt_len(pkt);
int ret_compress = 0;
/*
* We do not compress if we are enqueuing a chain.
* Traversing the chain to look for acks would defeat the
* purpose of batch enqueueing.
*/
if (cnt == 1) {
ret_compress = fq_compressor(fqs, fq, fq_cl, pkt);
if (ret_compress == CLASSQEQ_COMPRESSED) {
fq_cl->fcl_stat.fcl_pkts_compressed++;
}
}
DTRACE_IP5(fq_enqueue, fq_if_t *, fqs, fq_if_classq_t *, fq_cl,
fq_t *, fq, pktsched_pkt_t *, pkt, uint32_t, cnt);
fq_enqueue(fq, pkt->pktsched_pkt, pkt->pktsched_tail, cnt,
pkt->pktsched_ptype);
fq->fq_bytes += chain_len;
fq_cl->fcl_stat.fcl_byte_cnt += chain_len;
fq_cl->fcl_stat.fcl_pkt_cnt += cnt;
/*
* check if this queue will qualify to be the next
* victim queue
*/
fq_if_is_flow_heavy(fqs, fq);
} else {
DTRACE_IP3(fq_drop, fq_if_t *, fqs, int, droptype, int, ret);
return (ret != CLASSQEQ_SUCCESS) ? ret : CLASSQEQ_DROP;
}
/*
* If the queue is not currently active, add it to the end of new
* flows list for that service class.
*/
if ((fq->fq_flags & (FQF_NEW_FLOW | FQF_OLD_FLOW)) == 0) {
VERIFY(STAILQ_NEXT(fq, fq_actlink) == NULL);
STAILQ_INSERT_TAIL(&fq_cl->fcl_new_flows, fq, fq_actlink);
fq->fq_flags |= FQF_NEW_FLOW;
fq_cl->fcl_stat.fcl_newflows_cnt++;
fq->fq_deficit = fq_cl->fcl_quantum;
}
return ret;
}
void
fq_getq_flow_internal(fq_if_t *fqs, fq_t *fq, pktsched_pkt_t *pkt)
{
classq_pkt_t p = CLASSQ_PKT_INITIALIZER(p);
uint32_t plen;
fq_if_classq_t *fq_cl;
struct ifclassq *ifq = fqs->fqs_ifq;
fq_dequeue(fq, &p, fqs->fqs_ptype);
if (p.cp_ptype == QP_INVALID) {
VERIFY(p.cp_mbuf == NULL);
return;
}
fq->fq_next_tx_time = FQ_INVALID_TX_TS;
pktsched_pkt_encap(pkt, &p);
plen = pktsched_get_pkt_len(pkt);
VERIFY(fq->fq_bytes >= plen);
fq->fq_bytes -= plen;
fq_cl = &FQ_CLASSQ(fq);
fq_cl->fcl_stat.fcl_byte_cnt -= plen;
fq_cl->fcl_stat.fcl_pkt_cnt--;
fq_cl->fcl_flags &= ~FCL_PACED;
IFCQ_DEC_LEN(ifq);
IFCQ_DEC_BYTES(ifq, plen);
FQ_GRP_DEC_LEN(fq);
FQ_GRP_DEC_BYTES(fq, plen);
/* Reset getqtime so that we don't count idle times */
if (fq_empty(fq, fqs->fqs_ptype)) {
fq->fq_getqtime = 0;
}
}
/*
* fq_get_next_tx_time returns FQ_INVALID_TX_TS when there is no tx time in fq
*/
static uint64_t
fq_get_next_tx_time(fq_if_t *fqs, fq_t *fq)
{
uint64_t tx_time = FQ_INVALID_TX_TS;
/*
* Check the cached value in fq
*/
if (fq->fq_next_tx_time != FQ_INVALID_TX_TS) {
return fq->fq_next_tx_time;
}
switch (fqs->fqs_ptype) {
case QP_MBUF: {
struct mbuf *m;
if ((m = MBUFQ_FIRST(&fq->fq_mbufq)) != NULL) {
struct m_tag *tag;
tag = m_tag_locate(m, KERNEL_MODULE_TAG_ID,
KERNEL_TAG_TYPE_AQM);
if (tag != NULL) {
tx_time = *(uint64_t *)tag->m_tag_data;
}
}
break;
}
case QP_PACKET: {
struct __kern_packet *p = KPKTQ_FIRST(&fq->fq_kpktq);
if (__probable(p != NULL)) {
tx_time = __packet_get_tx_timestamp(SK_PKT2PH(p));
}
break;
}
default:
VERIFY(0);
/* NOTREACHED */
__builtin_unreachable();
}
/*
* Cache the tx time in fq. The cache will be clear after dequeue or drop
* from the fq.
*/
fq->fq_next_tx_time = tx_time;
return tx_time;
}
/*
* fq_tx_time_ready returns true if the fq is empty so that it doesn't
* affect caller logics that handles empty flow.
*/
boolean_t
fq_tx_time_ready(fq_if_t *fqs, fq_t *fq, uint64_t now, uint64_t *ready_time)
{
uint64_t pkt_tx_time;
fq_if_classq_t *fq_cl = &FQ_CLASSQ(fq);
if (!fq_codel_enable_pacing) {
return TRUE;
}
pkt_tx_time = fq_get_next_tx_time(fqs, fq);
if (ready_time != NULL) {
*ready_time = pkt_tx_time;
}
if (pkt_tx_time <= now + pkt_pacing_leeway ||
pkt_tx_time == FQ_INVALID_TX_TS) {
return TRUE;
}
/*
* Ignore the tx time if it's scheduled too far in the future
*/
if (pkt_tx_time > max_pkt_pacing_interval + now) {
fq_cl->fcl_stat.fcl_ignore_tx_time++;
return TRUE;
}
ASSERT(pkt_tx_time != FQ_INVALID_TX_TS);
KDBG(AQM_KTRACE_TX_NOT_READY, fq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(fq), now, pkt_tx_time);
return FALSE;
}
void
fq_codel_dq_legacy(void *fqs_p, void *fq_p, pktsched_pkt_t *pkt, uint64_t now)
{
fq_if_t *fqs = (fq_if_t *)fqs_p;
fq_t *fq = (fq_t *)fq_p;
fq_if_classq_t *fq_cl = &FQ_CLASSQ(fq);
int64_t qdelay = 0;
volatile uint32_t *__single pkt_flags;
uint64_t *__single pkt_timestamp, pkt_tx_time = 0, pacing_delay = 0;
uint64_t fq_min_delay_threshold = FQ_TARGET_DELAY(fq);
uint8_t pkt_flowsrc;
boolean_t l4s_pkt;
fq_getq_flow_internal(fqs, fq, pkt);
if (pkt->pktsched_ptype == QP_INVALID) {
VERIFY(pkt->pktsched_pkt_mbuf == NULL);
return;
}
pktsched_get_pkt_vars(pkt, &pkt_flags, &pkt_timestamp, NULL, &pkt_flowsrc,
NULL, NULL, &pkt_tx_time);
l4s_pkt = pktsched_is_pkt_l4s(pkt);
if (fq_codel_enable_pacing && fq_codel_enable_l4s) {
if (pkt_tx_time > *pkt_timestamp) {
pacing_delay = pkt_tx_time - *pkt_timestamp;
fq_cl->fcl_stat.fcl_paced_pkts++;
DTRACE_SKYWALK3(aqm__pacing__delta, uint64_t, now - pkt_tx_time,
fq_if_t *, fqs, fq_t *, fq);
}
#if (DEVELOPMENT || DEBUG)
else if (pkt_tx_time != 0) {
DTRACE_SKYWALK5(aqm__miss__pacing__delay, uint64_t, *pkt_timestamp,
uint64_t, pkt_tx_time, uint64_t, now, fq_if_t *,
fqs, fq_t *, fq);
}
#endif // (DEVELOPMENT || DEBUG)
}
/* this will compute qdelay in nanoseconds */
if (now > *pkt_timestamp) {
qdelay = now - *pkt_timestamp;
}
/* Update min/max/avg qdelay for the respective class */
if (fq_cl->fcl_stat.fcl_min_qdelay == 0 ||
(qdelay > 0 && (u_int64_t)qdelay < fq_cl->fcl_stat.fcl_min_qdelay)) {
fq_cl->fcl_stat.fcl_min_qdelay = qdelay;
}
if (fq_cl->fcl_stat.fcl_max_qdelay == 0 ||
(qdelay > 0 && (u_int64_t)qdelay > fq_cl->fcl_stat.fcl_max_qdelay)) {
fq_cl->fcl_stat.fcl_max_qdelay = qdelay;
}
uint64_t num_dequeues = fq_cl->fcl_stat.fcl_dequeue;
if (num_dequeues == 0) {
fq_cl->fcl_stat.fcl_avg_qdelay = qdelay;
} else if (qdelay > 0) {
uint64_t res = 0;
if (os_add_overflow(num_dequeues, 1, &res)) {
/* Reset the dequeue num and dequeue bytes */
fq_cl->fcl_stat.fcl_dequeue = num_dequeues = 0;
fq_cl->fcl_stat.fcl_dequeue_bytes = 0;
fq_cl->fcl_stat.fcl_avg_qdelay = qdelay;
os_log_info(OS_LOG_DEFAULT, "%s: dequeue num overflow, "
"flow: 0x%x, iface: %s", __func__, fq->fq_flowhash,
if_name(fqs->fqs_ifq->ifcq_ifp));
} else {
uint64_t product = 0;
if (os_mul_overflow(fq_cl->fcl_stat.fcl_avg_qdelay,
num_dequeues, &product) || os_add_overflow(product, qdelay, &res)) {
fq_cl->fcl_stat.fcl_avg_qdelay = qdelay;
} else {
fq_cl->fcl_stat.fcl_avg_qdelay = res /
(num_dequeues + 1);
}
}
}
fq->fq_pkts_since_last_report++;
if (fq_codel_enable_l4s && l4s_pkt) {
/*
* A safe guard to make sure that L4S is not going to build a huge
* queue if we encounter unexpected problems (for eg., if ACKs don't
* arrive in timely manner due to congestion in reverse path).
*/
fq_min_delay_threshold = l4s_min_delay_threshold;
if ((l4s_ce_threshold != 0 && qdelay > l4s_ce_threshold + pacing_delay) ||
(l4s_ce_threshold == 0 && qdelay > FQ_TARGET_DELAY(fq) + pacing_delay)) {
DTRACE_SKYWALK4(aqm__mark__ce, uint64_t, qdelay, uint64_t, pacing_delay,
fq_if_t *, fqs, fq_t *, fq);
KDBG(AQM_KTRACE_STATS_FLOW_REPORT_CE, fq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(fq), qdelay, pacing_delay);
/*
* The packet buffer that pktsched_mark_ecn writes to can be pageable.
* Since it is not safe to write to pageable memory while preemption
* is disabled, convert the spin lock into mutex.
*/
IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
if (__improbable(l4s_local_ce_report != 0) &&
(*pkt_flags & PKTF_FLOW_ADV) != 0 &&
fq_if_report_congestion(fqs, pkt, 0, 1, fq->fq_pkts_since_last_report)) {
fq->fq_pkts_since_last_report = 0;
fq_cl->fcl_stat.fcl_ce_reported++;
} else if (pktsched_mark_ecn(pkt) == 0) {
fq_cl->fcl_stat.fcl_ce_marked++;
} else {
fq_cl->fcl_stat.fcl_ce_mark_failures++;
}
}
}
ASSERT(pacing_delay <= INT64_MAX);
qdelay = MAX(0, qdelay - (int64_t)pacing_delay);
if (fq->fq_min_qdelay == 0 ||
(u_int64_t)qdelay < fq->fq_min_qdelay) {
fq->fq_min_qdelay = qdelay;
}
if (now >= fq->fq_updatetime) {
if (fq->fq_min_qdelay > fq_min_delay_threshold) {
if (!FQ_IS_DELAY_HIGH(fq)) {
FQ_SET_DELAY_HIGH(fq);
}
} else {
FQ_CLEAR_DELAY_HIGH(fq);
}
/* Reset measured queue delay and update time */
fq->fq_updatetime = now + FQ_UPDATE_INTERVAL(fq);
fq->fq_min_qdelay = 0;
}
if (fqs->fqs_large_flow != fq || !fq_if_almost_at_drop_limit(fqs)) {
FQ_CLEAR_OVERWHELMING(fq);
}
if (!FQ_IS_DELAY_HIGH(fq) || fq_empty(fq, fqs->fqs_ptype)) {
FQ_CLEAR_DELAY_HIGH(fq);
}
if ((fq->fq_flags & FQF_FLOWCTL_ON) &&
!FQ_IS_DELAY_HIGH(fq) && !FQ_IS_OVERWHELMING(fq)) {
fq_if_flow_feedback(fqs, fq, fq_cl);
}
if (fq_empty(fq, fqs->fqs_ptype)) {
/* Reset getqtime so that we don't count idle times */
fq->fq_getqtime = 0;
} else {
fq->fq_getqtime = now;
}
fq_if_is_flow_heavy(fqs, fq);
*pkt_timestamp = 0;
switch (pkt->pktsched_ptype) {
case QP_MBUF:
*pkt_flags &= ~PKTF_PRIV_GUARDED;
break;
#if SKYWALK
case QP_PACKET:
/* sanity check */
ASSERT((*pkt_flags & ~PKT_F_COMMON_MASK) == 0);
break;
#endif /* SKYWALK */
default:
VERIFY(0);
/* NOTREACHED */
__builtin_unreachable();
}
}
int
fq_codel_enq(void *fqs_p, fq_if_group_t *fq_grp, pktsched_pkt_t *pkt,
fq_if_classq_t *fq_cl)
{
fq_if_t *fqs = (fq_if_t *)fqs_p;
int droptype = DTYPE_NODROP, ret = CLASSQEQ_SUCCESS;
u_int64_t now;
fq_t *fq = NULL;
uint64_t *__single pkt_timestamp;
volatile uint32_t *__single pkt_flags;
uint32_t pkt_flowid, cnt;
uint8_t pkt_proto, pkt_flowsrc;
fq_tfc_type_t tfc_type = FQ_TFC_C;
cnt = pkt->pktsched_pcnt;
pktsched_get_pkt_vars(pkt, &pkt_flags, &pkt_timestamp, &pkt_flowid,
&pkt_flowsrc, &pkt_proto, NULL, NULL);
/*
* XXX Not walking the chain to set this flag on every packet.
* This flag is only used for debugging. Nothing is affected if it's
* not set.
*/
switch (pkt->pktsched_ptype) {
case QP_MBUF:
/* See comments in <rdar://problem/14040693> */
VERIFY(!(*pkt_flags & PKTF_PRIV_GUARDED));
break;
#if SKYWALK
case QP_PACKET:
/* sanity check */
ASSERT((*pkt_flags & ~PKT_F_COMMON_MASK) == 0);
break;
#endif /* SKYWALK */
default:
VERIFY(0);
/* NOTREACHED */
__builtin_unreachable();
}
if (fq_codel_enable_l4s) {
tfc_type = pktsched_is_pkt_l4s(pkt) ? FQ_TFC_L4S : FQ_TFC_C;
}
/*
* Timestamps for every packet must be set prior to entering this path.
*/
now = *pkt_timestamp;
ASSERT(now > 0);
/* find the flowq for this packet */
fq = fq_if_hash_pkt(fqs, fq_grp, pkt_flowid, pktsched_get_pkt_svc(pkt),
now, pkt_proto, pkt_flowsrc, tfc_type, true);
if (__improbable(fq == NULL)) {
DTRACE_IP1(memfail__drop, fq_if_t *, fqs);
/* drop the packet if we could not allocate a flow queue */
fq_cl->fcl_stat.fcl_drop_memfailure += cnt;
return CLASSQEQ_DROP;
}
VERIFY(fq->fq_group == fq_grp);
VERIFY(fqs->fqs_ptype == pkt->pktsched_ptype);
KDBG(AQM_KTRACE_STATS_FLOW_ENQUEUE, fq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(fq),
fq->fq_bytes, pktsched_get_pkt_len(pkt));
/*
* Skip the dropping part if it's L4S. Flow control or ECN marking decision
* will be made at dequeue time.
*/
if (fq_codel_enable_l4s && tfc_type == FQ_TFC_L4S) {
fq_cl->fcl_stat.fcl_l4s_pkts += cnt;
droptype = DTYPE_NODROP;
}
/*
* If the queue length hits the queue limit, drop a chain with the
* same number of packets from the front of the queue for a flow with
* maximum number of bytes. This will penalize heavy and unresponsive
* flows. It will also avoid a tail drop.
*/
if (__improbable(droptype == DTYPE_NODROP &&
fq_if_at_drop_limit(fqs))) {
uint32_t i;
if (fqs->fqs_large_flow == fq) {
/*
* Drop from the head of the current fq. Since a
* new packet will be added to the tail, it is ok
* to leave fq in place.
*/
DTRACE_IP5(large__flow, fq_if_t *, fqs,
fq_if_classq_t *, fq_cl, fq_t *, fq,
pktsched_pkt_t *, pkt, uint32_t, cnt);
for (i = 0; i < cnt; i++) {
fq_head_drop(fqs, fq);
}
fq_cl->fcl_stat.fcl_drop_overflow += cnt;
/*
* For UDP, flow control it here so that we won't waste too much
* CPU dropping packets.
*/
if ((fq->fq_flags & FQF_FLOWCTL_CAPABLE) &&
(*pkt_flags & PKTF_FLOW_ADV) &&
(pkt_proto != IPPROTO_TCP) &&
(pkt_proto != IPPROTO_QUIC)) {
if (fq_if_add_fcentry(fqs, pkt, pkt_flowsrc, fq, fq_cl)) {
fq->fq_flags |= FQF_FLOWCTL_ON;
FQ_SET_OVERWHELMING(fq);
fq_cl->fcl_stat.fcl_overwhelming++;
/* deliver flow control advisory error */
ret = CLASSQEQ_SUCCESS_FC;
}
}
} else {
if (fqs->fqs_large_flow == NULL) {
droptype = DTYPE_FORCED;
fq_cl->fcl_stat.fcl_drop_overflow += cnt;
ret = CLASSQEQ_DROP;
DTRACE_IP5(no__large__flow, fq_if_t *, fqs,
fq_if_classq_t *, fq_cl, fq_t *, fq,
pktsched_pkt_t *, pkt, uint32_t, cnt);
/*
* if this fq was freshly created and there
* is nothing to enqueue, move it to empty list
*/
if (fq_empty(fq, fqs->fqs_ptype) &&
!(fq->fq_flags & (FQF_NEW_FLOW |
FQF_OLD_FLOW))) {
fq_if_move_to_empty_flow(fqs, fq_cl,
fq, now);
fq = NULL;
}
} else {
DTRACE_IP5(different__large__flow,
fq_if_t *, fqs, fq_if_classq_t *, fq_cl,
fq_t *, fq, pktsched_pkt_t *, pkt,
uint32_t, cnt);
for (i = 0; i < cnt; i++) {
fq_if_drop_packet(fqs, now);
}
}
}
}
fq_cl->fcl_flags &= ~FCL_PACED;
if (__probable(droptype == DTYPE_NODROP)) {
uint32_t chain_len = pktsched_get_pkt_len(pkt);
int ret_compress = 0;
/*
* We do not compress if we are enqueuing a chain.
* Traversing the chain to look for acks would defeat the
* purpose of batch enqueueing.
*/
if (cnt == 1) {
ret_compress = fq_compressor(fqs, fq, fq_cl, pkt);
if (ret_compress == CLASSQEQ_COMPRESSED) {
fq_cl->fcl_stat.fcl_pkts_compressed++;
}
}
DTRACE_IP5(fq_enqueue, fq_if_t *, fqs, fq_if_classq_t *, fq_cl,
fq_t *, fq, pktsched_pkt_t *, pkt, uint32_t, cnt);
fq_enqueue(fq, pkt->pktsched_pkt, pkt->pktsched_tail, cnt,
pkt->pktsched_ptype);
fq->fq_bytes += chain_len;
fq_cl->fcl_stat.fcl_byte_cnt += chain_len;
fq_cl->fcl_stat.fcl_pkt_cnt += cnt;
/*
* check if this queue will qualify to be the next
* victim queue
*/
fq_if_is_flow_heavy(fqs, fq);
if (FQ_CONGESTION_FEEDBACK_CAPABLE(fq) && fq->fq_flowsrc == FLOWSRC_INPCB &&
fq->fq_congestion_cnt > fq->fq_last_congestion_cnt) {
KDBG(AQM_KTRACE_CONGESTION_NOTIFIED,
fq->fq_flowhash, AQM_KTRACE_FQ_GRP_SC_IDX(fq),
fq->fq_bytes, fq->fq_congestion_cnt);
fq_cl->fcl_stat.fcl_congestion_feedback++;
ret = CLASSQEQ_CONGESTED;
}
} else {
DTRACE_IP3(fq_drop, fq_if_t *, fqs, int, droptype, int, ret);
return (ret != CLASSQEQ_SUCCESS) ? ret : CLASSQEQ_DROP;
}
/*
* If the queue is not currently active, add it to the end of new
* flows list for that service class.
*/
if ((fq->fq_flags & (FQF_NEW_FLOW | FQF_OLD_FLOW)) == 0) {
VERIFY(STAILQ_NEXT(fq, fq_actlink) == NULL);
STAILQ_INSERT_TAIL(&fq_cl->fcl_new_flows, fq, fq_actlink);
fq->fq_flags |= FQF_NEW_FLOW;
fq_cl->fcl_stat.fcl_newflows_cnt++;
fq->fq_deficit = fq_cl->fcl_quantum;
}
fq->fq_last_congestion_cnt = fq->fq_congestion_cnt;
return ret;
}
static boolean_t
codel_ok_to_drop(pktsched_pkt_t *pkt, fq_t *fq,
struct codel_status *codel_status, uint64_t now)
{
uint64_t *__single pkt_enq_time, sojourn_time;
boolean_t ok_to_drop = false;
if (pkt->pktsched_pcnt == 0) {
codel_status->first_above_time = 0;
return false;
}
pktsched_get_pkt_vars(pkt, NULL, &pkt_enq_time, NULL, NULL, NULL, NULL, NULL);
sojourn_time = 0;
// TODO: handle pacing
VERIFY(now >= *pkt_enq_time);
if (__probable(now > *pkt_enq_time)) {
sojourn_time = now - *pkt_enq_time;
}
if (sojourn_time <= FQ_TARGET_DELAY(fq)) {
codel_status->first_above_time = 0;
goto end;
}
if (codel_status->first_above_time == 0) {
codel_status->first_above_time = now += FQ_UPDATE_INTERVAL(fq);
} else if (now >= codel_status->first_above_time) {
ok_to_drop = true;
KDBG(AQM_KTRACE_OK_TO_DROP, fq->fq_flowhash, sojourn_time,
*pkt_enq_time, now);
}
end:
/* we shouldn't need to access pkt_enq_time again, clear it now */
*pkt_enq_time = 0;
return ok_to_drop;
}
static float
fast_inv_sqrt(float number)
{
union {
float f;
uint32_t i;
} conv = { .f = number };
conv.i = 0x5f3759df - (conv.i >> 1);
conv.f *= 1.5F - (number * 0.5F * conv.f * conv.f);
return conv.f;
}
static uint64_t
codel_control_law(float inv_sqrt, uint64_t t, uint64_t interval)
{
/* Drop becomes more frequeut as drop count increases */
uint64_t val = (uint64_t)(inv_sqrt * interval);
uint64_t result = t + val;
VERIFY(val > 0 && val <= interval);
return result;
}
static void
fq_drop_pkt(struct ifclassq *ifcq, struct ifnet *ifp, pktsched_pkt_t *pkt)
{
IFCQ_DROP_ADD(ifcq, 1, pktsched_get_pkt_len(pkt));
if (__improbable(droptap_verbose > 0)) {
pktsched_drop_pkt(pkt, ifp, DROP_REASON_AQM_HIGH_DELAY,
__func__, __LINE__, 0);
} else {
pktsched_free_pkt(pkt);
}
}
void
fq_codel_dq(void *fqs_p, void *fq_p, pktsched_pkt_t *pkt, uint64_t now)
{
fq_if_t *fqs = (fq_if_t *)fqs_p;
fq_t *fq = (fq_t *)fq_p;
fq_if_classq_t *fq_cl = &FQ_CLASSQ(fq);
struct ifnet *ifp = fqs->fqs_ifq->ifcq_ifp;
struct codel_status *status = &fq->codel_status;
struct ifclassq *ifcq = fqs->fqs_ifq;
volatile uint32_t *__single pkt_flags;
uint64_t *__single pkt_timestamp, pkt_tx_time = 0, pacing_delay = 0, pkt_enq_time = 0;
int64_t qdelay = 0;
boolean_t l4s_pkt;
boolean_t ok_to_drop = false;
uint32_t delta = 0;
fq_getq_flow_internal(fqs, fq, pkt);
if (pkt->pktsched_ptype == QP_INVALID) {
VERIFY(pkt->pktsched_pkt_mbuf == NULL);
return;
}
pktsched_get_pkt_vars(pkt, &pkt_flags, &pkt_timestamp, NULL, NULL,
NULL, NULL, &pkt_tx_time);
l4s_pkt = pktsched_is_pkt_l4s(pkt);
pkt_enq_time = *pkt_timestamp;
if (fq_codel_enable_pacing && fq_codel_enable_l4s) {
if (pkt_tx_time > pkt_enq_time) {
pacing_delay = pkt_tx_time - pkt_enq_time;
fq_cl->fcl_stat.fcl_paced_pkts++;
DTRACE_SKYWALK3(aqm__pacing__delta, uint64_t, now - pkt_tx_time,
fq_if_t *, fqs, fq_t *, fq);
}
#if (DEVELOPMENT || DEBUG)
else if (pkt_tx_time != 0) {
DTRACE_SKYWALK5(aqm__miss__pacing__delay, uint64_t, pkt_enq_time,
uint64_t, pkt_tx_time, uint64_t, now, fq_if_t *,
fqs, fq_t *, fq);
}
#endif // (DEVELOPMENT || DEBUG)
}
if (fq_codel_enable_l4s && l4s_pkt) {
/* this will compute qdelay in nanoseconds */
if (now > pkt_enq_time) {
qdelay = now - pkt_enq_time;
}
fq->fq_pkts_since_last_report++;
if ((l4s_ce_threshold != 0 && qdelay > l4s_ce_threshold + pacing_delay) ||
(l4s_ce_threshold == 0 && qdelay > FQ_TARGET_DELAY(fq) + pacing_delay)) {
DTRACE_SKYWALK4(aqm__mark__ce, uint64_t, qdelay, uint64_t, pacing_delay,
fq_if_t *, fqs, fq_t *, fq);
KDBG(AQM_KTRACE_STATS_FLOW_REPORT_CE, fq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(fq), qdelay, pacing_delay);
/*
* The packet buffer that pktsched_mark_ecn writes to can be pageable.
* Since it is not safe to write to pageable memory while preemption
* is disabled, convert the spin lock into mutex.
*/
IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
if (__improbable(l4s_local_ce_report != 0) &&
(*pkt_flags & PKTF_FLOW_ADV) != 0 &&
fq_if_report_congestion(fqs, pkt, 0, 1, fq->fq_pkts_since_last_report)) {
fq->fq_pkts_since_last_report = 0;
fq_cl->fcl_stat.fcl_ce_reported++;
} else if (pktsched_mark_ecn(pkt) == 0) {
fq_cl->fcl_stat.fcl_ce_marked++;
} else {
fq_cl->fcl_stat.fcl_ce_mark_failures++;
}
}
*pkt_timestamp = 0;
} else {
ok_to_drop = codel_ok_to_drop(pkt, fq, status, now);
if (status->dropping) {
if (!ok_to_drop) {
status->dropping = false;
}
/*
* Time for the next drop. Drop current packet and dequeue
* next. If the dequeue doesn't take us out of dropping
* state, schedule the next drop. A large backlog might
* result in drop rates so high that the next drop should
* happen now, hence the 'while' loop.
*/
while (now >= status->drop_next && status->dropping) {
status->count++;
IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
KDBG(AQM_KTRACE_CONGESTION_INC, fq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(fq), fq->fq_bytes, 0);
if (FQ_CONGESTION_FEEDBACK_CAPABLE(fq) && (*pkt_flags & PKTF_FLOW_ADV)) {
fq->fq_congestion_cnt++;
/* Like in the case of ECN, return now and dequeue again. */
if (fq->fq_flowsrc == FLOWSRC_CHANNEL) {
fq_if_report_congestion(fqs, pkt, 1, 0, fq->fq_pkts_since_last_report);
fq_cl->fcl_stat.fcl_congestion_feedback++;
}
goto end;
/*
* If congestion feedback is not supported,
* try ECN first, if fail, drop the packet.
*/
} else if (FQ_IS_ECN_CAPABLE(fq) && pktsched_mark_ecn(pkt) == 0) {
fq_cl->fcl_stat.fcl_ce_marked++;
status->drop_next =
codel_control_law(fast_inv_sqrt(status->count), status->drop_next, FQ_UPDATE_INTERVAL(fq));
KDBG(AQM_KTRACE_PKT_DROP, fq->fq_flowhash,
status->count, status->drop_next, now);
/*
* Since we are not dropping, return now and let the
* caller dequeue again
*/
goto end;
} else {
/* Disable ECN marking for this flow if marking fails once */
FQ_CLEAR_ECN_CAPABLE(fq);
fq_drop_pkt(ifcq, ifp, pkt);
fq_cl->fcl_stat.fcl_ce_mark_failures++;
fq_cl->fcl_stat.fcl_high_delay_drop++;
fq_getq_flow_internal(fqs, fq, pkt);
if (!codel_ok_to_drop(pkt, fq, status, now)) {
/* exit dropping state when queuing delay falls below threshold */
status->dropping = false;
} else {
status->drop_next =
codel_control_law(fast_inv_sqrt(status->count), status->drop_next, FQ_UPDATE_INTERVAL(fq));
}
}
KDBG(AQM_KTRACE_PKT_DROP, fq->fq_flowhash,
status->count, status->drop_next, now);
}
/*
* If we get here, we're not in drop state. The 'ok_to_drop'
* return from dodequeue means that the sojourn time has been
* above 'TARGET' for 'INTERVAL', so enter drop state.
*/
} else if (ok_to_drop) {
IFCQ_CONVERT_LOCK(fqs->fqs_ifq);
KDBG(AQM_KTRACE_CONGESTION_INC, fq->fq_flowhash,
AQM_KTRACE_FQ_GRP_SC_IDX(fq), fq->fq_bytes, 0);
if (FQ_CONGESTION_FEEDBACK_CAPABLE(fq) && (*pkt_flags & PKTF_FLOW_ADV)) {
fq->fq_congestion_cnt++;
if (fq->fq_flowsrc == FLOWSRC_CHANNEL) {
fq_if_report_congestion(fqs, pkt, 1, 0, fq->fq_pkts_since_last_report);
fq_cl->fcl_stat.fcl_congestion_feedback++;
}
} else if (FQ_IS_ECN_CAPABLE(fq) && pktsched_mark_ecn(pkt) == 0) {
fq_cl->fcl_stat.fcl_ce_marked++;
} else {
FQ_CLEAR_ECN_CAPABLE(fq);
fq_drop_pkt(ifcq, ifp, pkt);
fq_cl->fcl_stat.fcl_ce_mark_failures++;
fq_cl->fcl_stat.fcl_high_delay_drop++;
fq_getq_flow_internal(fqs, fq, pkt);
ok_to_drop = codel_ok_to_drop(pkt, fq, status, now);
}
status->dropping = true;
/*
* If min went above TARGET close to when it last went
* below, assume that the drop rate that controlled the
* queue on the last cycle is a good starting point to
* control it now. ('drop_next' will be at most 'INTERVAL'
* later than the time of the last drop, so 'now - drop_next'
* is a good approximation of the time from the last drop
* until now.)
*/
delta = status->count - status->lastcnt;
if (delta > 0 && now - status->drop_next <= 16 * FQ_UPDATE_INTERVAL(fq)) {
status->count = MAX(status->count - 1, 1);
} else {
status->count = 1;
}
status->drop_next =
codel_control_law(fast_inv_sqrt(status->count), now, FQ_UPDATE_INTERVAL(fq));
status->lastcnt = status->count;
KDBG(AQM_KTRACE_PKT_DROP, fq->fq_flowhash,
status->count, status->drop_next, now);
}
}
end:
if (fqs->fqs_large_flow != fq || !fq_if_almost_at_drop_limit(fqs) ||
fq_empty(fq, fqs->fqs_ptype)) {
FQ_CLEAR_OVERWHELMING(fq);
}
if ((fq->fq_flags & FQF_FLOWCTL_ON) && !FQ_IS_OVERWHELMING(fq)) {
fq_if_flow_feedback(fqs, fq, fq_cl);
}
if (fq_empty(fq, fqs->fqs_ptype)) {
/* Reset getqtime so that we don't count idle times */
fq->fq_getqtime = 0;
fq->codel_status.dropping = false;
} else {
fq->fq_getqtime = now;
}
fq_if_is_flow_heavy(fqs, fq);
}