[apple/xnu.git] / bsd / netinet / tcp_cc.c

/*
 * Copyright (c) 2013-2017 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@
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/syslog.h>
#include <sys/protosw.h>
#include <sys/socketvar.h>
#include <sys/kern_control.h>
#include <sys/domain.h>

#include <netinet/in.h>
#include <netinet/tcp.h>
#include <netinet/tcp_var.h>
#include <netinet/tcp_cc.h>
#include <mach/sdt.h>
#include <libkern/OSAtomic.h>

struct tcp_cc_debug_state {
	u_int64_t ccd_tsns;
	char ccd_srcaddr[INET6_ADDRSTRLEN];
	uint16_t ccd_srcport;
	char ccd_destaddr[INET6_ADDRSTRLEN];
	uint16_t ccd_destport;
	uint32_t ccd_snd_cwnd;
	uint32_t ccd_snd_wnd;
	uint32_t ccd_snd_ssthresh;
	uint32_t ccd_pipeack;
	uint32_t ccd_rttcur;
	uint32_t ccd_rxtcur;
	uint32_t ccd_srtt;
	uint32_t ccd_event;
	uint32_t ccd_sndcc;
	uint32_t ccd_sndhiwat;
	uint32_t ccd_bytes_acked;
	u_int8_t ccd_cc_index;
	u_int8_t ccd_unused_1__;
	u_int16_t ccd_unused_2__;
	union {
		struct {
			uint32_t ccd_last_max;
			uint32_t ccd_tcp_win;
			uint32_t ccd_target_win;
			uint32_t ccd_avg_lastmax;
			uint32_t ccd_mean_deviation;
		} cubic_state;
		struct {
			u_int32_t led_base_rtt;
		} ledbat_state;
	} u;
};

SYSCTL_SKMEM_TCP_INT(OID_AUTO, cc_debug, CTLFLAG_RW | CTLFLAG_LOCKED,
	int, tcp_cc_debug, 0, "Enable debug data collection");

extern struct tcp_cc_algo tcp_cc_newreno;
SYSCTL_INT(_net_inet_tcp, OID_AUTO, newreno_sockets,
	CTLFLAG_RD | CTLFLAG_LOCKED, &tcp_cc_newreno.num_sockets,
	0, "Number of sockets using newreno");

extern struct tcp_cc_algo tcp_cc_ledbat;
SYSCTL_INT(_net_inet_tcp, OID_AUTO, background_sockets,
	CTLFLAG_RD | CTLFLAG_LOCKED, &tcp_cc_ledbat.num_sockets,
	0, "Number of sockets using background transport");

extern struct tcp_cc_algo tcp_cc_cubic;
SYSCTL_INT(_net_inet_tcp, OID_AUTO, cubic_sockets,
	CTLFLAG_RD | CTLFLAG_LOCKED,&tcp_cc_cubic.num_sockets, 
	0, "Number of sockets using cubic");

SYSCTL_SKMEM_TCP_INT(OID_AUTO, use_newreno,
	CTLFLAG_RW | CTLFLAG_LOCKED, int, tcp_use_newreno, 0,
	"Use TCP NewReno by default");

static int tcp_check_cwnd_nonvalidated = 1;
#if (DEBUG || DEVELOPMENT)
SYSCTL_INT(_net_inet_tcp, OID_AUTO, cwnd_nonvalidated,
    CTLFLAG_RW | CTLFLAG_LOCKED, &tcp_check_cwnd_nonvalidated, 0,
    "Check if congestion window is non-validated");
#endif /* (DEBUG || DEVELOPMENT) */

 #define SET_SNDSB_IDEAL_SIZE(sndsb, size) \
	sndsb->sb_idealsize = min(max(tcp_sendspace, tp->snd_ssthresh), \
	tcp_autosndbuf_max);

/* Array containing pointers to currently implemented TCP CC algorithms */
struct tcp_cc_algo* tcp_cc_algo_list[TCP_CC_ALGO_COUNT];
struct zone *tcp_cc_zone;

/* Information for colelcting TCP debug information using control socket */
#define TCP_CCDEBUG_CONTROL_NAME "com.apple.network.tcp_ccdebug"
#define TCP_CCDBG_NOUNIT 0xffffffff
static kern_ctl_ref tcp_ccdbg_ctlref = NULL;
volatile UInt32 tcp_ccdbg_unit = TCP_CCDBG_NOUNIT;

void tcp_cc_init(void);
static void tcp_cc_control_register(void);
static errno_t tcp_ccdbg_control_connect(kern_ctl_ref kctl,
	struct sockaddr_ctl *sac, void **uinfo);
static errno_t tcp_ccdbg_control_disconnect(kern_ctl_ref kctl,
	u_int32_t unit, void *uinfo);
static struct tcp_cc_algo tcp_cc_algo_none;
/*
 * Initialize TCP congestion control algorithms.
 */
 
void
tcp_cc_init(void)
{
	bzero(&tcp_cc_algo_list, sizeof(tcp_cc_algo_list));
	bzero(&tcp_cc_algo_none, sizeof(tcp_cc_algo_none));

	tcp_cc_algo_list[TCP_CC_ALGO_NONE] = &tcp_cc_algo_none;
	tcp_cc_algo_list[TCP_CC_ALGO_NEWRENO_INDEX] = &tcp_cc_newreno;
	tcp_cc_algo_list[TCP_CC_ALGO_BACKGROUND_INDEX] = &tcp_cc_ledbat;
	tcp_cc_algo_list[TCP_CC_ALGO_CUBIC_INDEX] = &tcp_cc_cubic;

	tcp_cc_control_register();
}

static void
tcp_cc_control_register(void)
{
	struct kern_ctl_reg ccdbg_control;
	errno_t err;

	bzero(&ccdbg_control, sizeof(ccdbg_control));
	strlcpy(ccdbg_control.ctl_name, TCP_CCDEBUG_CONTROL_NAME,
	    sizeof(ccdbg_control.ctl_name));
	ccdbg_control.ctl_connect = tcp_ccdbg_control_connect;
	ccdbg_control.ctl_disconnect = tcp_ccdbg_control_disconnect;
	ccdbg_control.ctl_flags |= CTL_FLAG_PRIVILEGED;
	ccdbg_control.ctl_flags |= CTL_FLAG_REG_SOCK_STREAM;

	err = ctl_register(&ccdbg_control, &tcp_ccdbg_ctlref);
	if (err != 0) {
		log(LOG_ERR, "failed to register tcp_cc debug control");
	}
}

/* Allow only one socket to connect at any time for debugging */
static errno_t
tcp_ccdbg_control_connect(kern_ctl_ref kctl, struct sockaddr_ctl *sac,
	void **uinfo)
{
#pragma unused(kctl)
#pragma unused(uinfo)

	UInt32 old_value = TCP_CCDBG_NOUNIT;
	UInt32 new_value = sac->sc_unit;

	if (tcp_ccdbg_unit != old_value)
		return (EALREADY);

	if (OSCompareAndSwap(old_value, new_value, &tcp_ccdbg_unit))
		return (0);
	else
		return (EALREADY);
}

static errno_t
tcp_ccdbg_control_disconnect(kern_ctl_ref kctl, u_int32_t unit, void *uinfo)
{
#pragma unused(kctl, unit, uinfo)

	if (unit == tcp_ccdbg_unit) {
		UInt32 old_value = tcp_ccdbg_unit;
		UInt32 new_value = TCP_CCDBG_NOUNIT;
		if (tcp_ccdbg_unit == new_value)
			return (0);

		if (!OSCompareAndSwap(old_value, new_value,
			&tcp_ccdbg_unit))
			log(LOG_DEBUG, 
			    "failed to disconnect tcp_cc debug control");
	}
	return (0);
}

inline void
tcp_ccdbg_trace(struct tcpcb *tp, struct tcphdr *th, int32_t event)
{
#if !CONFIG_DTRACE
#pragma unused(th)
#endif /* !CONFIG_DTRACE */
	struct inpcb *inp = tp->t_inpcb;

	if (tcp_cc_debug && tcp_ccdbg_unit > 0) {
		struct tcp_cc_debug_state dbg_state;
		struct timespec tv;

		bzero(&dbg_state, sizeof(dbg_state));
		
		nanotime(&tv);
		/* Take time in seconds */
		dbg_state.ccd_tsns = (tv.tv_sec * 1000000000) + tv.tv_nsec;
		inet_ntop(SOCK_DOM(inp->inp_socket), 
		    ((SOCK_DOM(inp->inp_socket) == PF_INET) ?
		    (void *)&inp->inp_laddr.s_addr :
		    (void *)&inp->in6p_laddr), dbg_state.ccd_srcaddr,
		    sizeof(dbg_state.ccd_srcaddr));
		dbg_state.ccd_srcport = ntohs(inp->inp_lport);
		inet_ntop(SOCK_DOM(inp->inp_socket),
		    ((SOCK_DOM(inp->inp_socket) == PF_INET) ?
		    (void *)&inp->inp_faddr.s_addr :
		    (void *)&inp->in6p_faddr), dbg_state.ccd_destaddr,
		    sizeof(dbg_state.ccd_destaddr));
		dbg_state.ccd_destport = ntohs(inp->inp_fport);

		dbg_state.ccd_snd_cwnd = tp->snd_cwnd;
		dbg_state.ccd_snd_wnd = tp->snd_wnd;
		dbg_state.ccd_snd_ssthresh = tp->snd_ssthresh;
		dbg_state.ccd_pipeack = tp->t_pipeack;
		dbg_state.ccd_rttcur = tp->t_rttcur;
		dbg_state.ccd_rxtcur = tp->t_rxtcur;
		dbg_state.ccd_srtt = tp->t_srtt >> TCP_RTT_SHIFT;
		dbg_state.ccd_event = event;
		dbg_state.ccd_sndcc = inp->inp_socket->so_snd.sb_cc;
		dbg_state.ccd_sndhiwat = inp->inp_socket->so_snd.sb_hiwat;
		dbg_state.ccd_bytes_acked = tp->t_bytes_acked;
		dbg_state.ccd_cc_index = tp->tcp_cc_index;
		switch (tp->tcp_cc_index) {
		    case TCP_CC_ALGO_CUBIC_INDEX:
			dbg_state.u.cubic_state.ccd_last_max =
			    tp->t_ccstate->cub_last_max;
			dbg_state.u.cubic_state.ccd_tcp_win =
			    tp->t_ccstate->cub_tcp_win;
			dbg_state.u.cubic_state.ccd_target_win =
			    tp->t_ccstate->cub_target_win;
			dbg_state.u.cubic_state.ccd_avg_lastmax =
			    tp->t_ccstate->cub_avg_lastmax;
			dbg_state.u.cubic_state.ccd_mean_deviation =
			    tp->t_ccstate->cub_mean_dev;
			break;
		    case TCP_CC_ALGO_BACKGROUND_INDEX:
			dbg_state.u.ledbat_state.led_base_rtt =
			    get_base_rtt(tp);
			break;
		    default:
			break;
		}

		ctl_enqueuedata(tcp_ccdbg_ctlref, tcp_ccdbg_unit,
			&dbg_state, sizeof(dbg_state), 0);
	}
	DTRACE_TCP5(cc, void, NULL, struct inpcb *, inp,
		struct tcpcb *, tp, struct tcphdr *, th, int32_t, event);
}

void tcp_cc_resize_sndbuf(struct tcpcb *tp)
{
	struct sockbuf *sb;
	/*
	 * If the send socket buffer size is bigger than ssthresh,
	 * it is time to trim it because we do not want to hold
	 * too many mbufs in the socket buffer
	 */
	sb = &tp->t_inpcb->inp_socket->so_snd;
	if (sb->sb_hiwat > tp->snd_ssthresh &&
		(sb->sb_flags & SB_AUTOSIZE)) {
		if (sb->sb_idealsize > tp->snd_ssthresh) {
			SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
		}
		sb->sb_flags |= SB_TRIM;
	}
}

void tcp_bad_rexmt_fix_sndbuf(struct tcpcb *tp)
{
	struct sockbuf *sb;
	sb = &tp->t_inpcb->inp_socket->so_snd;
	if ((sb->sb_flags & (SB_TRIM|SB_AUTOSIZE)) == (SB_TRIM|SB_AUTOSIZE)) {
		/*
		 * If there was a retransmission that was not necessary
		 * then the size of socket buffer can be restored to
		 * what it was before
		 */
		SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
		if (sb->sb_hiwat <= sb->sb_idealsize) {
			sbreserve(sb, sb->sb_idealsize);
			sb->sb_flags &= ~SB_TRIM;
		}
	}
}

/*
 * Calculate initial cwnd according to RFC3390.
 *
 * Keep the old ss_fltsz sysctl for ABI compabitility issues.
 * but it will be overriden if tcp_do_rfc3390 sysctl when it is set.
 */
void
tcp_cc_cwnd_init_or_reset(struct tcpcb *tp)
{
	if (tp->t_flags & TF_LOCAL) {
		tp->snd_cwnd = tp->t_maxseg * ss_fltsz_local;
	} else {
		/* initial congestion window according to RFC 3390 */
		if (tcp_do_rfc3390)
			tp->snd_cwnd = min(4 * tp->t_maxseg,
				max(2 * tp->t_maxseg, TCP_CC_CWND_INIT_BYTES));
		else
			tp->snd_cwnd = tp->t_maxseg * ss_fltsz;
	}
}

/*
 * Indicate whether this ack should be delayed.
 * Here is the explanation for different settings of tcp_delack_enabled:
 *  - when set to 1, the bhavior is same as when set to 2. We kept this 
 *    for binary compatibility.
 *  - when set to 2, will "ack every other packet"
 *      - if our last ack wasn't a 0-sized window.
 *      - if the peer hasn't sent us a TH_PUSH data packet (radar 3649245). 
 *              If TH_PUSH is set, take this as a clue that we need to ACK 
 *              with no delay. This helps higher level protocols who 
 *              won't send us more data even if the window is open 
 *              because their last "segment" hasn't been ACKed
 *  - when set to 3,  will do "streaming detection" 
 *      - if we receive more than "maxseg_unacked" full packets 
 *        in the last 100ms
 *      - if the connection is not in slow-start or idle or 
 *        loss/recovery states
 *      - if those criteria aren't met, it will ack every other packet.
 */
int
tcp_cc_delay_ack(struct tcpcb *tp, struct tcphdr *th)
{
	switch (tcp_delack_enabled) {
	    case 1:
	    case 2:
		if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
		    (th->th_flags & TH_PUSH) == 0 &&
		    (tp->t_unacksegs == 1))
			return(1);
		break;  
	    case 3:
		if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
		    (th->th_flags & TH_PUSH) == 0 &&
		    ((tp->t_unacksegs == 1) ||
		    ((tp->t_flags & TF_STRETCHACK) != 0 &&
			tp->t_unacksegs < (maxseg_unacked))))
			return(1);
		break;
	}
	return(0);
}

void
tcp_cc_allocate_state(struct tcpcb *tp)
{
	if (tp->tcp_cc_index == TCP_CC_ALGO_CUBIC_INDEX &&
		tp->t_ccstate == NULL) {
		tp->t_ccstate = (struct tcp_ccstate *)zalloc(tcp_cc_zone);

		/*
		 * If we could not allocate memory for congestion control
		 * state, revert to using TCP NewReno as it does not
		 * require any state
		 */
		if (tp->t_ccstate == NULL)
			tp->tcp_cc_index = TCP_CC_ALGO_NEWRENO_INDEX;
		else
			bzero(tp->t_ccstate, sizeof(*tp->t_ccstate));
	}
}

/*
 * If stretch ack was disabled automatically on long standing connections, 
 * re-evaluate the situation after 15 minutes to enable it.
 */
#define	TCP_STRETCHACK_DISABLE_WIN	(15 * 60 * TCP_RETRANSHZ)
void
tcp_cc_after_idle_stretchack(struct tcpcb *tp)
{
	int32_t tdiff;

	if (!(tp->t_flagsext & TF_DISABLE_STRETCHACK))
		return;

	tdiff = timer_diff(tcp_now, 0, tp->rcv_nostrack_ts, 0);
	if (tdiff < 0)
		tdiff = -tdiff;

	if (tdiff > TCP_STRETCHACK_DISABLE_WIN) {
		tp->t_flagsext &= ~TF_DISABLE_STRETCHACK;
		tp->t_stretchack_delayed = 0;

		tcp_reset_stretch_ack(tp);
	}
}

/*
 * Detect if the congestion window is non-vlidated according to
 * draft-ietf-tcpm-newcwv-07
 */

inline uint32_t
tcp_cc_is_cwnd_nonvalidated(struct tcpcb *tp)
{
	struct socket *so = tp->t_inpcb->inp_socket;
	if (tp->t_pipeack == 0 || tcp_check_cwnd_nonvalidated == 0) {
		tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
		return (0);
	}

	/*
	 * The congestion window is validated if the number of bytes acked
	 * is more than half of the current window or if there is more
	 * data to send in the send socket buffer
	 */
	if (tp->t_pipeack >= (tp->snd_cwnd >> 1) ||
	    (so != NULL && so->so_snd.sb_cc > tp->snd_cwnd))
		tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
	else
		tp->t_flagsext |= TF_CWND_NONVALIDATED;
	return (tp->t_flagsext & TF_CWND_NONVALIDATED);
}

/*
 * Adjust congestion window in response to congestion in non-validated
 * phase.
 */
inline void
tcp_cc_adjust_nonvalidated_cwnd(struct tcpcb *tp)
{
	tp->t_pipeack = tcp_get_max_pipeack(tp);
	tcp_clear_pipeack_state(tp);
	tp->snd_cwnd = (max(tp->t_pipeack, tp->t_lossflightsize) >> 1);
	tp->snd_cwnd = max(tp->snd_cwnd, TCP_CC_CWND_INIT_BYTES);
	tp->snd_cwnd += tp->t_maxseg * tcprexmtthresh;
	tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
}

/*
 * Return maximum of all the pipeack samples. Since the number of samples
 * TCP_PIPEACK_SAMPLE_COUNT is 3 at this time, it will be simpler to do
 * a comparision. We should change ths if the number of samples increases.
 */
inline u_int32_t
tcp_get_max_pipeack(struct tcpcb *tp)
{
	u_int32_t max_pipeack = 0;
	max_pipeack = (tp->t_pipeack_sample[0] > tp->t_pipeack_sample[1]) ?
	    tp->t_pipeack_sample[0] : tp->t_pipeack_sample[1];
	max_pipeack = (tp->t_pipeack_sample[2] > max_pipeack) ?
	    tp->t_pipeack_sample[2] : max_pipeack;

	return (max_pipeack);
}

inline void
tcp_clear_pipeack_state(struct tcpcb *tp)
{
	bzero(tp->t_pipeack_sample, sizeof(tp->t_pipeack_sample));
	tp->t_pipeack_ind = 0;
	tp->t_lossflightsize = 0;
}
Commit	Line	Data
fe8ab488	1	/*
5ba3f43e	2	* Copyright (c) 2013-2017 Apple Inc. All rights reserved.
fe8ab488 A	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/param.h>
	30	#include <sys/systm.h>
	31	#include <sys/kernel.h>
	32	#include <sys/syslog.h>
	33	#include <sys/protosw.h>
	34	#include <sys/socketvar.h>
	35	#include <sys/kern_control.h>
	36	#include <sys/domain.h>
	37
	38	#include <netinet/in.h>
	39	#include <netinet/tcp.h>
	40	#include <netinet/tcp_var.h>
	41	#include <netinet/tcp_cc.h>
	42	#include <mach/sdt.h>
	43	#include <libkern/OSAtomic.h>
	44
	45	struct tcp_cc_debug_state {
	46	u_int64_t ccd_tsns;
	47	char ccd_srcaddr[INET6_ADDRSTRLEN];
	48	uint16_t ccd_srcport;
	49	char ccd_destaddr[INET6_ADDRSTRLEN];
	50	uint16_t ccd_destport;
	51	uint32_t ccd_snd_cwnd;
	52	uint32_t ccd_snd_wnd;
	53	uint32_t ccd_snd_ssthresh;
3e170ce0	54	uint32_t ccd_pipeack;
fe8ab488 A	55	uint32_t ccd_rttcur;
	56	uint32_t ccd_rxtcur;
	57	uint32_t ccd_srtt;
	58	uint32_t ccd_event;
	59	uint32_t ccd_sndcc;
	60	uint32_t ccd_sndhiwat;
	61	uint32_t ccd_bytes_acked;
ecc0ceb4 A	62	u_int8_t ccd_cc_index;
	63	u_int8_t ccd_unused_1__;
	64	u_int16_t ccd_unused_2__;
fe8ab488 A	65	union {
	66	struct {
	67	uint32_t ccd_last_max;
	68	uint32_t ccd_tcp_win;
	69	uint32_t ccd_target_win;
	70	uint32_t ccd_avg_lastmax;
	71	uint32_t ccd_mean_deviation;
	72	} cubic_state;
ecc0ceb4 A	73	struct {
	74	u_int32_t led_base_rtt;
	75	} ledbat_state;
fe8ab488 A	76	} u;
	77	};
	78
5ba3f43e A	79	SYSCTL_SKMEM_TCP_INT(OID_AUTO, cc_debug, CTLFLAG_RW \| CTLFLAG_LOCKED,
5ba3f43e A	80	int, tcp_cc_debug, 0, "Enable debug data collection");
fe8ab488 A	81
	82	extern struct tcp_cc_algo tcp_cc_newreno;
	83	SYSCTL_INT(_net_inet_tcp, OID_AUTO, newreno_sockets,
	84	CTLFLAG_RD \| CTLFLAG_LOCKED, &tcp_cc_newreno.num_sockets,
	85	0, "Number of sockets using newreno");
	86
	87	extern struct tcp_cc_algo tcp_cc_ledbat;
	88	SYSCTL_INT(_net_inet_tcp, OID_AUTO, background_sockets,
	89	CTLFLAG_RD \| CTLFLAG_LOCKED, &tcp_cc_ledbat.num_sockets,
	90	0, "Number of sockets using background transport");
	91
	92	extern struct tcp_cc_algo tcp_cc_cubic;
	93	SYSCTL_INT(_net_inet_tcp, OID_AUTO, cubic_sockets,
	94	CTLFLAG_RD \| CTLFLAG_LOCKED,&tcp_cc_cubic.num_sockets,
	95	0, "Number of sockets using cubic");
	96
5ba3f43e A	97	SYSCTL_SKMEM_TCP_INT(OID_AUTO, use_newreno,
5ba3f43e A	98	CTLFLAG_RW \| CTLFLAG_LOCKED, int, tcp_use_newreno, 0,
fe8ab488 A	99	"Use TCP NewReno by default");
fe8ab488 A	100
3e170ce0 A	101	static int tcp_check_cwnd_nonvalidated = 1;
	102	#if (DEBUG \|\| DEVELOPMENT)
	103	SYSCTL_INT(_net_inet_tcp, OID_AUTO, cwnd_nonvalidated,
	104	CTLFLAG_RW \| CTLFLAG_LOCKED, &tcp_check_cwnd_nonvalidated, 0,
	105	"Check if congestion window is non-validated");
	106	#endif /* (DEBUG \|\| DEVELOPMENT) */
	107
fe8ab488 A	108	#define SET_SNDSB_IDEAL_SIZE(sndsb, size) \
	109	sndsb->sb_idealsize = min(max(tcp_sendspace, tp->snd_ssthresh), \
	110	tcp_autosndbuf_max);
	111
	112	/* Array containing pointers to currently implemented TCP CC algorithms */
	113	struct tcp_cc_algo* tcp_cc_algo_list[TCP_CC_ALGO_COUNT];
	114	struct zone *tcp_cc_zone;
	115
	116	/* Information for colelcting TCP debug information using control socket */
	117	#define TCP_CCDEBUG_CONTROL_NAME "com.apple.network.tcp_ccdebug"
	118	#define TCP_CCDBG_NOUNIT 0xffffffff
	119	static kern_ctl_ref tcp_ccdbg_ctlref = NULL;
	120	volatile UInt32 tcp_ccdbg_unit = TCP_CCDBG_NOUNIT;
	121
	122	void tcp_cc_init(void);
	123	static void tcp_cc_control_register(void);
	124	static errno_t tcp_ccdbg_control_connect(kern_ctl_ref kctl,
	125	struct sockaddr_ctl sac, void *uinfo);
	126	static errno_t tcp_ccdbg_control_disconnect(kern_ctl_ref kctl,
	127	u_int32_t unit, void *uinfo);
	128	static struct tcp_cc_algo tcp_cc_algo_none;
	129	/*
	130	* Initialize TCP congestion control algorithms.
	131	*/
	132
	133	void
	134	tcp_cc_init(void)
	135	{
	136	bzero(&tcp_cc_algo_list, sizeof(tcp_cc_algo_list));
	137	bzero(&tcp_cc_algo_none, sizeof(tcp_cc_algo_none));
	138
	139	tcp_cc_algo_list[TCP_CC_ALGO_NONE] = &tcp_cc_algo_none;
	140	tcp_cc_algo_list[TCP_CC_ALGO_NEWRENO_INDEX] = &tcp_cc_newreno;
	141	tcp_cc_algo_list[TCP_CC_ALGO_BACKGROUND_INDEX] = &tcp_cc_ledbat;
	142	tcp_cc_algo_list[TCP_CC_ALGO_CUBIC_INDEX] = &tcp_cc_cubic;
	143
	144	tcp_cc_control_register();
	145	}
	146
	147	static void
	148	tcp_cc_control_register(void)
	149	{
	150	struct kern_ctl_reg ccdbg_control;
	151	errno_t err;
	152
	153	bzero(&ccdbg_control, sizeof(ccdbg_control));
	154	strlcpy(ccdbg_control.ctl_name, TCP_CCDEBUG_CONTROL_NAME,
	155	sizeof(ccdbg_control.ctl_name));
	156	ccdbg_control.ctl_connect = tcp_ccdbg_control_connect;
	157	ccdbg_control.ctl_disconnect = tcp_ccdbg_control_disconnect;
	158	ccdbg_control.ctl_flags \|= CTL_FLAG_PRIVILEGED;
	159	ccdbg_control.ctl_flags \|= CTL_FLAG_REG_SOCK_STREAM;
	160
	161	err = ctl_register(&ccdbg_control, &tcp_ccdbg_ctlref);
	162	if (err != 0) {
	163	log(LOG_ERR, "failed to register tcp_cc debug control");
	164	}
	165	}
	166
	167	/* Allow only one socket to connect at any time for debugging */
	168	static errno_t
	169	tcp_ccdbg_control_connect(kern_ctl_ref kctl, struct sockaddr_ctl *sac,
	170	void **uinfo)
	171	{
172	#pragma unused(kctl)
173	#pragma unused(uinfo)
174
175	UInt32 old_value = TCP_CCDBG_NOUNIT;
176	UInt32 new_value = sac->sc_unit;
177
178	if (tcp_ccdbg_unit != old_value)
179	return (EALREADY);
180
181	if (OSCompareAndSwap(old_value, new_value, &tcp_ccdbg_unit))
182	return (0);
183	else
184	return (EALREADY);
185	}
186
187	static errno_t
188	tcp_ccdbg_control_disconnect(kern_ctl_ref kctl, u_int32_t unit, void *uinfo)
189	{
190	#pragma unused(kctl, unit, uinfo)
191
192	if (unit == tcp_ccdbg_unit) {
193	UInt32 old_value = tcp_ccdbg_unit;
194	UInt32 new_value = TCP_CCDBG_NOUNIT;
195	if (tcp_ccdbg_unit == new_value)
196	return (0);
197
198	if (!OSCompareAndSwap(old_value, new_value,
199	&tcp_ccdbg_unit))
200	log(LOG_DEBUG,
201	"failed to disconnect tcp_cc debug control");
202	}
203	return (0);
204	}
205
206	inline void
207	tcp_ccdbg_trace(struct tcpcb tp, struct tcphdr th, int32_t event)
208	{
209	#if !CONFIG_DTRACE
210	#pragma unused(th)
211	#endif /* !CONFIG_DTRACE */
212	struct inpcb *inp = tp->t_inpcb;
213
214	if (tcp_cc_debug && tcp_ccdbg_unit > 0) {
215	struct tcp_cc_debug_state dbg_state;
216	struct timespec tv;
217
218	bzero(&dbg_state, sizeof(dbg_state));
219
220	nanotime(&tv);
221	/* Take time in seconds */
222	dbg_state.ccd_tsns = (tv.tv_sec * 1000000000) + tv.tv_nsec;
223	inet_ntop(SOCK_DOM(inp->inp_socket),
224	((SOCK_DOM(inp->inp_socket) == PF_INET) ?
225	(void *)&inp->inp_laddr.s_addr :
226	(void *)&inp->in6p_laddr), dbg_state.ccd_srcaddr,
227	sizeof(dbg_state.ccd_srcaddr));
228	dbg_state.ccd_srcport = ntohs(inp->inp_lport);
229	inet_ntop(SOCK_DOM(inp->inp_socket),
230	((SOCK_DOM(inp->inp_socket) == PF_INET) ?
231	(void *)&inp->inp_faddr.s_addr :
232	(void *)&inp->in6p_faddr), dbg_state.ccd_destaddr,
233	sizeof(dbg_state.ccd_destaddr));
234	dbg_state.ccd_destport = ntohs(inp->inp_fport);
235
236	dbg_state.ccd_snd_cwnd = tp->snd_cwnd;
237	dbg_state.ccd_snd_wnd = tp->snd_wnd;
238	dbg_state.ccd_snd_ssthresh = tp->snd_ssthresh;
3e170ce0	239	dbg_state.ccd_pipeack = tp->t_pipeack;
fe8ab488 A	240	dbg_state.ccd_rttcur = tp->t_rttcur;
	241	dbg_state.ccd_rxtcur = tp->t_rxtcur;
	242	dbg_state.ccd_srtt = tp->t_srtt >> TCP_RTT_SHIFT;
	243	dbg_state.ccd_event = event;
	244	dbg_state.ccd_sndcc = inp->inp_socket->so_snd.sb_cc;
	245	dbg_state.ccd_sndhiwat = inp->inp_socket->so_snd.sb_hiwat;
	246	dbg_state.ccd_bytes_acked = tp->t_bytes_acked;
ecc0ceb4	247	dbg_state.ccd_cc_index = tp->tcp_cc_index;
fe8ab488 A	248	switch (tp->tcp_cc_index) {
	249	case TCP_CC_ALGO_CUBIC_INDEX:
	250	dbg_state.u.cubic_state.ccd_last_max =
	251	tp->t_ccstate->cub_last_max;
	252	dbg_state.u.cubic_state.ccd_tcp_win =
	253	tp->t_ccstate->cub_tcp_win;
	254	dbg_state.u.cubic_state.ccd_target_win =
	255	tp->t_ccstate->cub_target_win;
	256	dbg_state.u.cubic_state.ccd_avg_lastmax =
	257	tp->t_ccstate->cub_avg_lastmax;
	258	dbg_state.u.cubic_state.ccd_mean_deviation =
	259	tp->t_ccstate->cub_mean_dev;
	260	break;
ecc0ceb4 A	261	case TCP_CC_ALGO_BACKGROUND_INDEX:
	262	dbg_state.u.ledbat_state.led_base_rtt =
	263	get_base_rtt(tp);
	264	break;
fe8ab488 A	265	default:
	266	break;
	267	}
	268
	269	ctl_enqueuedata(tcp_ccdbg_ctlref, tcp_ccdbg_unit,
	270	&dbg_state, sizeof(dbg_state), 0);
	271	}
	272	DTRACE_TCP5(cc, void, NULL, struct inpcb *, inp,
	273	struct tcpcb , tp, struct tcphdr , th, int32_t, event);
	274	}
	275
	276	void tcp_cc_resize_sndbuf(struct tcpcb *tp)
	277	{
	278	struct sockbuf *sb;
	279	/*
	280	* If the send socket buffer size is bigger than ssthresh,
	281	* it is time to trim it because we do not want to hold
	282	* too many mbufs in the socket buffer
	283	*/
	284	sb = &tp->t_inpcb->inp_socket->so_snd;
	285	if (sb->sb_hiwat > tp->snd_ssthresh &&
	286	(sb->sb_flags & SB_AUTOSIZE)) {
	287	if (sb->sb_idealsize > tp->snd_ssthresh) {
	288	SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
	289	}
	290	sb->sb_flags \|= SB_TRIM;
	291	}
	292	}
	293
	294	void tcp_bad_rexmt_fix_sndbuf(struct tcpcb *tp)
	295	{
	296	struct sockbuf *sb;
	297	sb = &tp->t_inpcb->inp_socket->so_snd;
	298	if ((sb->sb_flags & (SB_TRIM\|SB_AUTOSIZE)) == (SB_TRIM\|SB_AUTOSIZE)) {
	299	/*
5ba3f43e	300	* If there was a retransmission that was not necessary
fe8ab488 A	301	* then the size of socket buffer can be restored to
	302	* what it was before
	303	*/
	304	SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
	305	if (sb->sb_hiwat <= sb->sb_idealsize) {
	306	sbreserve(sb, sb->sb_idealsize);
	307	sb->sb_flags &= ~SB_TRIM;
	308	}
	309	}
	310	}
	311
	312	/*
	313	* Calculate initial cwnd according to RFC3390.
	314	*
	315	* Keep the old ss_fltsz sysctl for ABI compabitility issues.
	316	* but it will be overriden if tcp_do_rfc3390 sysctl when it is set.
	317	*/
	318	void
	319	tcp_cc_cwnd_init_or_reset(struct tcpcb *tp)
	320	{
	321	if (tp->t_flags & TF_LOCAL) {
	322	tp->snd_cwnd = tp->t_maxseg * ss_fltsz_local;
	323	} else {
	324	/* initial congestion window according to RFC 3390 */
	325	if (tcp_do_rfc3390)
	326	tp->snd_cwnd = min(4 * tp->t_maxseg,
	327	max(2 * tp->t_maxseg, TCP_CC_CWND_INIT_BYTES));
	328	else
	329	tp->snd_cwnd = tp->t_maxseg * ss_fltsz;
	330	}
	331	}
	332
	333	/*
	334	* Indicate whether this ack should be delayed.
	335	* Here is the explanation for different settings of tcp_delack_enabled:
	336	* - when set to 1, the bhavior is same as when set to 2. We kept this
	337	* for binary compatibility.
	338	* - when set to 2, will "ack every other packet"
	339	* - if our last ack wasn't a 0-sized window.
	340	* - if the peer hasn't sent us a TH_PUSH data packet (radar 3649245).
	341	* If TH_PUSH is set, take this as a clue that we need to ACK
	342	* with no delay. This helps higher level protocols who
	343	* won't send us more data even if the window is open
	344	* because their last "segment" hasn't been ACKed
	345	* - when set to 3, will do "streaming detection"
	346	* - if we receive more than "maxseg_unacked" full packets
	347	* in the last 100ms
	348	* - if the connection is not in slow-start or idle or
	349	* loss/recovery states
	350	* - if those criteria aren't met, it will ack every other packet.
	351	*/
	352	int
	353	tcp_cc_delay_ack(struct tcpcb tp, struct tcphdr th)
	354	{
fe8ab488 A	355	switch (tcp_delack_enabled) {
	356	case 1:
	357	case 2:
	358	if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
	359	(th->th_flags & TH_PUSH) == 0 &&
	360	(tp->t_unacksegs == 1))
	361	return(1);
	362	break;
	363	case 3:
	364	if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
	365	(th->th_flags & TH_PUSH) == 0 &&
	366	((tp->t_unacksegs == 1) \|\|
	367	((tp->t_flags & TF_STRETCHACK) != 0 &&
	368	tp->t_unacksegs < (maxseg_unacked))))
	369	return(1);
	370	break;
	371	}
	372	return(0);
	373	}
	374
	375	void
	376	tcp_cc_allocate_state(struct tcpcb *tp)
	377	{
	378	if (tp->tcp_cc_index == TCP_CC_ALGO_CUBIC_INDEX &&
	379	tp->t_ccstate == NULL) {
	380	tp->t_ccstate = (struct tcp_ccstate *)zalloc(tcp_cc_zone);
	381
	382	/*
	383	* If we could not allocate memory for congestion control
	384	* state, revert to using TCP NewReno as it does not
	385	* require any state
	386	*/
	387	if (tp->t_ccstate == NULL)
	388	tp->tcp_cc_index = TCP_CC_ALGO_NEWRENO_INDEX;
	389	else
	390	bzero(tp->t_ccstate, sizeof(*tp->t_ccstate));
	391	}
	392	}
	393
	394	/*
	395	* If stretch ack was disabled automatically on long standing connections,
	396	* re-evaluate the situation after 15 minutes to enable it.
	397	*/
	398	#define TCP_STRETCHACK_DISABLE_WIN (15 * 60 * TCP_RETRANSHZ)
	399	void
	400	tcp_cc_after_idle_stretchack(struct tcpcb *tp)
	401	{
	402	int32_t tdiff;
	403
	404	if (!(tp->t_flagsext & TF_DISABLE_STRETCHACK))
	405	return;
	406
	407	tdiff = timer_diff(tcp_now, 0, tp->rcv_nostrack_ts, 0);
	408	if (tdiff < 0)
	409	tdiff = -tdiff;
	410
	411	if (tdiff > TCP_STRETCHACK_DISABLE_WIN) {
	412	tp->t_flagsext &= ~TF_DISABLE_STRETCHACK;
	413	tp->t_stretchack_delayed = 0;
	414
	415	tcp_reset_stretch_ack(tp);
	416	}
	417	}
3e170ce0 A	418
	419	/*
	420	* Detect if the congestion window is non-vlidated according to
	421	* draft-ietf-tcpm-newcwv-07
	422	*/
	423
	424	inline uint32_t
	425	tcp_cc_is_cwnd_nonvalidated(struct tcpcb *tp)
	426	{
5ba3f43e	427	struct socket *so = tp->t_inpcb->inp_socket;
3e170ce0 A	428	if (tp->t_pipeack == 0 \|\| tcp_check_cwnd_nonvalidated == 0) {
	429	tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
	430	return (0);
	431	}
5ba3f43e A	432
	433	/*
	434	* The congestion window is validated if the number of bytes acked
	435	* is more than half of the current window or if there is more
	436	* data to send in the send socket buffer
	437	*/
	438	if (tp->t_pipeack >= (tp->snd_cwnd >> 1) \|\|
	439	(so != NULL && so->so_snd.sb_cc > tp->snd_cwnd))
3e170ce0 A	440	tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
	441	else
	442	tp->t_flagsext \|= TF_CWND_NONVALIDATED;
	443	return (tp->t_flagsext & TF_CWND_NONVALIDATED);
	444	}
	445
	446	/*
	447	* Adjust congestion window in response to congestion in non-validated
	448	* phase.
	449	*/
	450	inline void
	451	tcp_cc_adjust_nonvalidated_cwnd(struct tcpcb *tp)
	452	{
	453	tp->t_pipeack = tcp_get_max_pipeack(tp);
	454	tcp_clear_pipeack_state(tp);
	455	tp->snd_cwnd = (max(tp->t_pipeack, tp->t_lossflightsize) >> 1);
	456	tp->snd_cwnd = max(tp->snd_cwnd, TCP_CC_CWND_INIT_BYTES);
	457	tp->snd_cwnd += tp->t_maxseg * tcprexmtthresh;
	458	tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
	459	}
	460
	461	/*
	462	* Return maximum of all the pipeack samples. Since the number of samples
	463	* TCP_PIPEACK_SAMPLE_COUNT is 3 at this time, it will be simpler to do
	464	* a comparision. We should change ths if the number of samples increases.
	465	*/
	466	inline u_int32_t
	467	tcp_get_max_pipeack(struct tcpcb *tp)
	468	{
	469	u_int32_t max_pipeack = 0;
	470	max_pipeack = (tp->t_pipeack_sample[0] > tp->t_pipeack_sample[1]) ?
	471	tp->t_pipeack_sample[0] : tp->t_pipeack_sample[1];
	472	max_pipeack = (tp->t_pipeack_sample[2] > max_pipeack) ?
	473	tp->t_pipeack_sample[2] : max_pipeack;
	474
	475	return (max_pipeack);
	476	}
	477
	478	inline void
	479	tcp_clear_pipeack_state(struct tcpcb *tp)
	480	{
	481	bzero(tp->t_pipeack_sample, sizeof(tp->t_pipeack_sample));
	482	tp->t_pipeack_ind = 0;
	483	tp->t_lossflightsize = 0;
	484	}