[mirror_ubuntu-bionic-kernel.git] / net / ipv4 / tcp_nv.c

/*
 * TCP NV: TCP with Congestion Avoidance
 *
 * TCP-NV is a successor of TCP-Vegas that has been developed to
 * deal with the issues that occur in modern networks.
 * Like TCP-Vegas, TCP-NV supports true congestion avoidance,
 * the ability to detect congestion before packet losses occur.
 * When congestion (queue buildup) starts to occur, TCP-NV
 * predicts what the cwnd size should be for the current
 * throughput and it reduces the cwnd proportionally to
 * the difference between the current cwnd and the predicted cwnd.
 *
 * NV is only recommeneded for traffic within a data center, and when
 * all the flows are NV (at least those within the data center). This
 * is due to the inherent unfairness between flows using losses to
 * detect congestion (congestion control) and those that use queue
 * buildup to detect congestion (congestion avoidance).
 *
 * Note: High NIC coalescence values may lower the performance of NV
 * due to the increased noise in RTT values. In particular, we have
 * seen issues with rx-frames values greater than 8.
 *
 * TODO:
 * 1) Add mechanism to deal with reverse congestion.
 */

#include <linux/mm.h>
#include <linux/module.h>
#include <linux/math64.h>
#include <net/tcp.h>
#include <linux/inet_diag.h>

/* TCP NV parameters
 *
 * nv_pad		Max number of queued packets allowed in network
 * nv_pad_buffer	Do not grow cwnd if this closed to nv_pad
 * nv_reset_period	How often (in) seconds)to reset min_rtt
 * nv_min_cwnd		Don't decrease cwnd below this if there are no losses
 * nv_cong_dec_mult	Decrease cwnd by X% (30%) of congestion when detected
 * nv_ssthresh_factor	On congestion set ssthresh to this * <desired cwnd> / 8
 * nv_rtt_factor	RTT averaging factor
 * nv_loss_dec_factor	Decrease cwnd by this (50%) when losses occur
 * nv_dec_eval_min_calls	Wait this many RTT measurements before dec cwnd
 * nv_inc_eval_min_calls	Wait this many RTT measurements before inc cwnd
 * nv_ssthresh_eval_min_calls	Wait this many RTT measurements before stopping
 *				slow-start due to congestion
 * nv_stop_rtt_cnt	Only grow cwnd for this many RTTs after non-congestion
 * nv_rtt_min_cnt	Wait these many RTTs before making congesion decision
 * nv_cwnd_growth_rate_neg
 * nv_cwnd_growth_rate_pos
 *	How quickly to double growth rate (not rate) of cwnd when not
 *	congested. One value (nv_cwnd_growth_rate_neg) for when
 *	rate < 1 pkt/RTT (after losses). The other (nv_cwnd_growth_rate_pos)
 *	otherwise.
 */

static int nv_pad __read_mostly = 10;
static int nv_pad_buffer __read_mostly = 2;
static int nv_reset_period __read_mostly = 5; /* in seconds */
static int nv_min_cwnd __read_mostly = 2;
static int nv_cong_dec_mult __read_mostly = 30 * 128 / 100; /* = 30% */
static int nv_ssthresh_factor __read_mostly = 8; /* = 1 */
static int nv_rtt_factor __read_mostly = 128; /* = 1/2*old + 1/2*new */
static int nv_loss_dec_factor __read_mostly = 512; /* => 50% */
static int nv_cwnd_growth_rate_neg __read_mostly = 8;
static int nv_cwnd_growth_rate_pos __read_mostly; /* 0 => fixed like Reno */
static int nv_dec_eval_min_calls __read_mostly = 60;
static int nv_inc_eval_min_calls __read_mostly = 20;
static int nv_ssthresh_eval_min_calls __read_mostly = 30;
static int nv_stop_rtt_cnt __read_mostly = 10;
static int nv_rtt_min_cnt __read_mostly = 2;

module_param(nv_pad, int, 0644);
MODULE_PARM_DESC(nv_pad, "max queued packets allowed in network");
module_param(nv_reset_period, int, 0644);
MODULE_PARM_DESC(nv_reset_period, "nv_min_rtt reset period (secs)");
module_param(nv_min_cwnd, int, 0644);
MODULE_PARM_DESC(nv_min_cwnd, "NV will not decrease cwnd below this value"
		 " without losses");

/* TCP NV Parameters */
struct tcpnv {
	unsigned long nv_min_rtt_reset_jiffies;  /* when to switch to
						  * nv_min_rtt_new */
	s8  cwnd_growth_factor;	/* Current cwnd growth factor,
				 * < 0 => less than 1 packet/RTT */
	u8  available8;
	u16 available16;
	u8  nv_allow_cwnd_growth:1, /* whether cwnd can grow */
		nv_reset:1,	    /* whether to reset values */
		nv_catchup:1;	    /* whether we are growing because
				     * of temporary cwnd decrease */
	u8  nv_eval_call_cnt;	/* call count since last eval */
	u8  nv_min_cwnd;	/* nv won't make a ca decision if cwnd is
				 * smaller than this. It may grow to handle
				 * TSO, LRO and interrupt coalescence because
				 * with these a small cwnd cannot saturate
				 * the link. Note that this is different from
				 * the file local nv_min_cwnd */
	u8  nv_rtt_cnt;		/* RTTs without making ca decision */;
	u32 nv_last_rtt;	/* last rtt */
	u32 nv_min_rtt;		/* active min rtt. Used to determine slope */
	u32 nv_min_rtt_new;	/* min rtt for future use */
	u32 nv_rtt_max_rate;	/* max rate seen during current RTT */
	u32 nv_rtt_start_seq;	/* current RTT ends when packet arrives
				 * acking beyond nv_rtt_start_seq */
	u32 nv_last_snd_una;	/* Previous value of tp->snd_una. It is
				 * used to determine bytes acked since last
				 * call to bictcp_acked */
	u32 nv_no_cong_cnt;	/* Consecutive no congestion decisions */
};

#define NV_INIT_RTT	  U32_MAX
#define NV_MIN_CWND	  4
#define NV_MIN_CWND_GROW  2
#define NV_TSO_CWND_BOUND 80

static inline void tcpnv_reset(struct tcpnv *ca, struct sock *sk)
{
	struct tcp_sock *tp = tcp_sk(sk);

	ca->nv_reset = 0;
	ca->nv_no_cong_cnt = 0;
	ca->nv_rtt_cnt = 0;
	ca->nv_last_rtt = 0;
	ca->nv_rtt_max_rate = 0;
	ca->nv_rtt_start_seq = tp->snd_una;
	ca->nv_eval_call_cnt = 0;
	ca->nv_last_snd_una = tp->snd_una;
}

static void tcpnv_init(struct sock *sk)
{
	struct tcpnv *ca = inet_csk_ca(sk);

	tcpnv_reset(ca, sk);

	ca->nv_allow_cwnd_growth = 1;
	ca->nv_min_rtt_reset_jiffies = jiffies + 2 * HZ;
	ca->nv_min_rtt = NV_INIT_RTT;
	ca->nv_min_rtt_new = NV_INIT_RTT;
	ca->nv_min_cwnd = NV_MIN_CWND;
	ca->nv_catchup = 0;
	ca->cwnd_growth_factor = 0;
}

static void tcpnv_cong_avoid(struct sock *sk, u32 ack, u32 acked)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct tcpnv *ca = inet_csk_ca(sk);
	u32 cnt;

	if (!tcp_is_cwnd_limited(sk))
		return;

	/* Only grow cwnd if NV has not detected congestion */
	if (!ca->nv_allow_cwnd_growth)
		return;

	if (tcp_in_slow_start(tp)) {
		acked = tcp_slow_start(tp, acked);
		if (!acked)
			return;
	}

	if (ca->cwnd_growth_factor < 0) {
		cnt = tp->snd_cwnd << -ca->cwnd_growth_factor;
		tcp_cong_avoid_ai(tp, cnt, acked);
	} else {
		cnt = max(4U, tp->snd_cwnd >> ca->cwnd_growth_factor);
		tcp_cong_avoid_ai(tp, cnt, acked);
	}
}

static u32 tcpnv_recalc_ssthresh(struct sock *sk)
{
	const struct tcp_sock *tp = tcp_sk(sk);

	return max((tp->snd_cwnd * nv_loss_dec_factor) >> 10, 2U);
}

static void tcpnv_state(struct sock *sk, u8 new_state)
{
	struct tcpnv *ca = inet_csk_ca(sk);

	if (new_state == TCP_CA_Open && ca->nv_reset) {
		tcpnv_reset(ca, sk);
	} else if (new_state == TCP_CA_Loss || new_state == TCP_CA_CWR ||
		new_state == TCP_CA_Recovery) {
		ca->nv_reset = 1;
		ca->nv_allow_cwnd_growth = 0;
		if (new_state == TCP_CA_Loss) {
			/* Reset cwnd growth factor to Reno value */
			if (ca->cwnd_growth_factor > 0)
				ca->cwnd_growth_factor = 0;
			/* Decrease growth rate if allowed */
			if (nv_cwnd_growth_rate_neg > 0 &&
			    ca->cwnd_growth_factor > -8)
				ca->cwnd_growth_factor--;
		}
	}
}

/* Do congestion avoidance calculations for TCP-NV
 */
static void tcpnv_acked(struct sock *sk, const struct ack_sample *sample)
{
	const struct inet_connection_sock *icsk = inet_csk(sk);
	struct tcp_sock *tp = tcp_sk(sk);
	struct tcpnv *ca = inet_csk_ca(sk);
	unsigned long now = jiffies;
	s64 rate64 = 0;
	u32 rate, max_win, cwnd_by_slope;
	u32 avg_rtt;
	u32 bytes_acked = 0;

	/* Some calls are for duplicates without timetamps */
	if (sample->rtt_us < 0)
		return;

	/* If not in TCP_CA_Open or TCP_CA_Disorder states, skip. */
	if (icsk->icsk_ca_state != TCP_CA_Open &&
	    icsk->icsk_ca_state != TCP_CA_Disorder)
		return;

	/* Stop cwnd growth if we were in catch up mode */
	if (ca->nv_catchup && tp->snd_cwnd >= nv_min_cwnd) {
		ca->nv_catchup = 0;
		ca->nv_allow_cwnd_growth = 0;
	}

	bytes_acked = tp->snd_una - ca->nv_last_snd_una;
	ca->nv_last_snd_una = tp->snd_una;

	if (sample->in_flight == 0)
		return;

	/* Calculate moving average of RTT */
	if (nv_rtt_factor > 0) {
		if (ca->nv_last_rtt > 0) {
			avg_rtt = (((u64)sample->rtt_us) * nv_rtt_factor +
				   ((u64)ca->nv_last_rtt)
				   * (256 - nv_rtt_factor)) >> 8;
		} else {
			avg_rtt = sample->rtt_us;
			ca->nv_min_rtt = avg_rtt << 1;
		}
		ca->nv_last_rtt = avg_rtt;
	} else {
		avg_rtt = sample->rtt_us;
	}

	/* rate in 100's bits per second */
	rate64 = ((u64)sample->in_flight) * 8000000;
	rate = (u32)div64_u64(rate64, (u64)(avg_rtt * 100));

	/* Remember the maximum rate seen during this RTT
	 * Note: It may be more than one RTT. This function should be
	 *       called at least nv_dec_eval_min_calls times.
	 */
	if (ca->nv_rtt_max_rate < rate)
		ca->nv_rtt_max_rate = rate;

	/* We have valid information, increment counter */
	if (ca->nv_eval_call_cnt < 255)
		ca->nv_eval_call_cnt++;

	/* update min rtt if necessary */
	if (avg_rtt < ca->nv_min_rtt)
		ca->nv_min_rtt = avg_rtt;

	/* update future min_rtt if necessary */
	if (avg_rtt < ca->nv_min_rtt_new)
		ca->nv_min_rtt_new = avg_rtt;

	/* nv_min_rtt is updated with the minimum (possibley averaged) rtt
	 * seen in the last sysctl_tcp_nv_reset_period seconds (i.e. a
	 * warm reset). This new nv_min_rtt will be continued to be updated
	 * and be used for another sysctl_tcp_nv_reset_period seconds,
	 * when it will be updated again.
	 * In practice we introduce some randomness, so the actual period used
	 * is chosen randomly from the range:
	 *   [sysctl_tcp_nv_reset_period*3/4, sysctl_tcp_nv_reset_period*5/4)
	 */
	if (time_after_eq(now, ca->nv_min_rtt_reset_jiffies)) {
		unsigned char rand;

		ca->nv_min_rtt = ca->nv_min_rtt_new;
		ca->nv_min_rtt_new = NV_INIT_RTT;
		get_random_bytes(&rand, 1);
		ca->nv_min_rtt_reset_jiffies =
			now + ((nv_reset_period * (384 + rand) * HZ) >> 9);
		/* Every so often we decrease ca->nv_min_cwnd in case previous
		 *  value is no longer accurate.
		 */
		ca->nv_min_cwnd = max(ca->nv_min_cwnd / 2, NV_MIN_CWND);
	}

	/* Once per RTT check if we need to do congestion avoidance */
	if (before(ca->nv_rtt_start_seq, tp->snd_una)) {
		ca->nv_rtt_start_seq = tp->snd_nxt;
		if (ca->nv_rtt_cnt < 0xff)
			/* Increase counter for RTTs without CA decision */
			ca->nv_rtt_cnt++;

		/* If this function is only called once within an RTT
		 * the cwnd is probably too small (in some cases due to
		 * tso, lro or interrupt coalescence), so we increase
		 * ca->nv_min_cwnd.
		 */
		if (ca->nv_eval_call_cnt == 1 &&
		    bytes_acked >= (ca->nv_min_cwnd - 1) * tp->mss_cache &&
		    ca->nv_min_cwnd < (NV_TSO_CWND_BOUND + 1)) {
			ca->nv_min_cwnd = min(ca->nv_min_cwnd
					      + NV_MIN_CWND_GROW,
					      NV_TSO_CWND_BOUND + 1);
			ca->nv_rtt_start_seq = tp->snd_nxt +
				ca->nv_min_cwnd * tp->mss_cache;
			ca->nv_eval_call_cnt = 0;
			ca->nv_allow_cwnd_growth = 1;
			return;
		}

		/* Find the ideal cwnd for current rate from slope
		 * slope = 80000.0 * mss / nv_min_rtt
		 * cwnd_by_slope = nv_rtt_max_rate / slope
		 */
		cwnd_by_slope = (u32)
			div64_u64(((u64)ca->nv_rtt_max_rate) * ca->nv_min_rtt,
				  (u64)(80000 * tp->mss_cache));
		max_win = cwnd_by_slope + nv_pad;

		/* If cwnd > max_win, decrease cwnd
		 * if cwnd < max_win, grow cwnd
		 * else leave the same
		 */
		if (tp->snd_cwnd > max_win) {
			/* there is congestion, check that it is ok
			 * to make a CA decision
			 * 1. We should have at least nv_dec_eval_min_calls
			 *    data points before making a CA  decision
			 * 2. We only make a congesion decision after
			 *    nv_rtt_min_cnt RTTs
			 */
			if (ca->nv_rtt_cnt < nv_rtt_min_cnt) {
				return;
			} else if (tp->snd_ssthresh == TCP_INFINITE_SSTHRESH) {
				if (ca->nv_eval_call_cnt <
				    nv_ssthresh_eval_min_calls)
					return;
				/* otherwise we will decrease cwnd */
			} else if (ca->nv_eval_call_cnt <
				   nv_dec_eval_min_calls) {
				if (ca->nv_allow_cwnd_growth &&
				    ca->nv_rtt_cnt > nv_stop_rtt_cnt)
					ca->nv_allow_cwnd_growth = 0;
				return;
			}

			/* We have enough data to determine we are congested */
			ca->nv_allow_cwnd_growth = 0;
			tp->snd_ssthresh =
				(nv_ssthresh_factor * max_win) >> 3;
			if (tp->snd_cwnd - max_win > 2) {
				/* gap > 2, we do exponential cwnd decrease */
				int dec;

				dec = max(2U, ((tp->snd_cwnd - max_win) *
					       nv_cong_dec_mult) >> 7);
				tp->snd_cwnd -= dec;
			} else if (nv_cong_dec_mult > 0) {
				tp->snd_cwnd = max_win;
			}
			if (ca->cwnd_growth_factor > 0)
				ca->cwnd_growth_factor = 0;
			ca->nv_no_cong_cnt = 0;
		} else if (tp->snd_cwnd <= max_win - nv_pad_buffer) {
			/* There is no congestion, grow cwnd if allowed*/
			if (ca->nv_eval_call_cnt < nv_inc_eval_min_calls)
				return;

			ca->nv_allow_cwnd_growth = 1;
			ca->nv_no_cong_cnt++;
			if (ca->cwnd_growth_factor < 0 &&
			    nv_cwnd_growth_rate_neg > 0 &&
			    ca->nv_no_cong_cnt > nv_cwnd_growth_rate_neg) {
				ca->cwnd_growth_factor++;
				ca->nv_no_cong_cnt = 0;
			} else if (ca->cwnd_growth_factor >= 0 &&
				   nv_cwnd_growth_rate_pos > 0 &&
				   ca->nv_no_cong_cnt >
				   nv_cwnd_growth_rate_pos) {
				ca->cwnd_growth_factor++;
				ca->nv_no_cong_cnt = 0;
			}
		} else {
			/* cwnd is in-between, so do nothing */
			return;
		}

		/* update state */
		ca->nv_eval_call_cnt = 0;
		ca->nv_rtt_cnt = 0;
		ca->nv_rtt_max_rate = 0;

		/* Don't want to make cwnd < nv_min_cwnd
		 * (it wasn't before, if it is now is because nv
		 *  decreased it).
		 */
		if (tp->snd_cwnd < nv_min_cwnd)
			tp->snd_cwnd = nv_min_cwnd;
	}
}

/* Extract info for Tcp socket info provided via netlink */
static size_t tcpnv_get_info(struct sock *sk, u32 ext, int *attr,
			     union tcp_cc_info *info)
{
	const struct tcpnv *ca = inet_csk_ca(sk);

	if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
		info->vegas.tcpv_enabled = 1;
		info->vegas.tcpv_rttcnt = ca->nv_rtt_cnt;
		info->vegas.tcpv_rtt = ca->nv_last_rtt;
		info->vegas.tcpv_minrtt = ca->nv_min_rtt;

		*attr = INET_DIAG_VEGASINFO;
		return sizeof(struct tcpvegas_info);
	}
	return 0;
}

static struct tcp_congestion_ops tcpnv __read_mostly = {
	.init		= tcpnv_init,
	.ssthresh	= tcpnv_recalc_ssthresh,
	.cong_avoid	= tcpnv_cong_avoid,
	.set_state	= tcpnv_state,
	.undo_cwnd	= tcp_reno_undo_cwnd,
	.pkts_acked     = tcpnv_acked,
	.get_info	= tcpnv_get_info,

	.owner		= THIS_MODULE,
	.name		= "nv",
};

static int __init tcpnv_register(void)
{
	BUILD_BUG_ON(sizeof(struct tcpnv) > ICSK_CA_PRIV_SIZE);

	return tcp_register_congestion_control(&tcpnv);
}

static void __exit tcpnv_unregister(void)
{
	tcp_unregister_congestion_control(&tcpnv);
}

module_init(tcpnv_register);
module_exit(tcpnv_unregister);

MODULE_AUTHOR("Lawrence Brakmo");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("TCP NV");
MODULE_VERSION("1.0");
Commit	Line	Data
699fafaf LB	1	/*
	2	* TCP NV: TCP with Congestion Avoidance
	3	*
	4	* TCP-NV is a successor of TCP-Vegas that has been developed to
	5	* deal with the issues that occur in modern networks.
	6	* Like TCP-Vegas, TCP-NV supports true congestion avoidance,
	7	* the ability to detect congestion before packet losses occur.
	8	* When congestion (queue buildup) starts to occur, TCP-NV
	9	* predicts what the cwnd size should be for the current
	10	* throughput and it reduces the cwnd proportionally to
	11	* the difference between the current cwnd and the predicted cwnd.
	12	*
	13	* NV is only recommeneded for traffic within a data center, and when
	14	* all the flows are NV (at least those within the data center). This
	15	* is due to the inherent unfairness between flows using losses to
	16	* detect congestion (congestion control) and those that use queue
	17	* buildup to detect congestion (congestion avoidance).
	18	*
	19	* Note: High NIC coalescence values may lower the performance of NV
	20	* due to the increased noise in RTT values. In particular, we have
	21	* seen issues with rx-frames values greater than 8.
	22	*
	23	* TODO:
	24	* 1) Add mechanism to deal with reverse congestion.
	25	*/
	26
	27	#include <linux/mm.h>
	28	#include <linux/module.h>
	29	#include <linux/math64.h>
	30	#include <net/tcp.h>
	31	#include <linux/inet_diag.h>
	32
	33	/* TCP NV parameters
	34	*
	35	* nv_pad Max number of queued packets allowed in network
	36	* nv_pad_buffer Do not grow cwnd if this closed to nv_pad
	37	* nv_reset_period How often (in) seconds)to reset min_rtt
	38	* nv_min_cwnd Don't decrease cwnd below this if there are no losses
	39	* nv_cong_dec_mult Decrease cwnd by X% (30%) of congestion when detected
	40	* nv_ssthresh_factor On congestion set ssthresh to this * <desired cwnd> / 8
	41	* nv_rtt_factor RTT averaging factor
	42	* nv_loss_dec_factor Decrease cwnd by this (50%) when losses occur
	43	* nv_dec_eval_min_calls Wait this many RTT measurements before dec cwnd
	44	* nv_inc_eval_min_calls Wait this many RTT measurements before inc cwnd
	45	* nv_ssthresh_eval_min_calls Wait this many RTT measurements before stopping
	46	* slow-start due to congestion
	47	* nv_stop_rtt_cnt Only grow cwnd for this many RTTs after non-congestion
	48	* nv_rtt_min_cnt Wait these many RTTs before making congesion decision
	49	* nv_cwnd_growth_rate_neg
	50	* nv_cwnd_growth_rate_pos
	51	* How quickly to double growth rate (not rate) of cwnd when not
	52	* congested. One value (nv_cwnd_growth_rate_neg) for when
	53	* rate < 1 pkt/RTT (after losses). The other (nv_cwnd_growth_rate_pos)
	54	* otherwise.
	55	*/
	56
	57	static int nv_pad __read_mostly = 10;
	58	static int nv_pad_buffer __read_mostly = 2;
	59	static int nv_reset_period __read_mostly = 5; /* in seconds */
	60	static int nv_min_cwnd __read_mostly = 2;
	61	static int nv_cong_dec_mult __read_mostly = 30 * 128 / 100; /* = 30% */
	62	static int nv_ssthresh_factor __read_mostly = 8; /* = 1 */
	63	static int nv_rtt_factor __read_mostly = 128; /* = 1/2old + 1/2new */
	64	static int nv_loss_dec_factor __read_mostly = 512; /* => 50% */
65	static int nv_cwnd_growth_rate_neg __read_mostly = 8;
66	static int nv_cwnd_growth_rate_pos __read_mostly; /* 0 => fixed like Reno */
67	static int nv_dec_eval_min_calls __read_mostly = 60;
68	static int nv_inc_eval_min_calls __read_mostly = 20;
69	static int nv_ssthresh_eval_min_calls __read_mostly = 30;
70	static int nv_stop_rtt_cnt __read_mostly = 10;
71	static int nv_rtt_min_cnt __read_mostly = 2;
72
73	module_param(nv_pad, int, 0644);
74	MODULE_PARM_DESC(nv_pad, "max queued packets allowed in network");
75	module_param(nv_reset_period, int, 0644);
76	MODULE_PARM_DESC(nv_reset_period, "nv_min_rtt reset period (secs)");
77	module_param(nv_min_cwnd, int, 0644);
78	MODULE_PARM_DESC(nv_min_cwnd, "NV will not decrease cwnd below this value"
79	" without losses");
80
81	/* TCP NV Parameters */
82	struct tcpnv {
83	unsigned long nv_min_rtt_reset_jiffies; /* when to switch to
84	* nv_min_rtt_new */
85	s8 cwnd_growth_factor; /* Current cwnd growth factor,
86	* < 0 => less than 1 packet/RTT */
87	u8 available8;
88	u16 available16;
699fafaf LB	89	u8 nv_allow_cwnd_growth:1, /* whether cwnd can grow */
	90	nv_reset:1, /* whether to reset values */
	91	nv_catchup:1; /* whether we are growing because
	92	* of temporary cwnd decrease */
	93	u8 nv_eval_call_cnt; /* call count since last eval */
	94	u8 nv_min_cwnd; /* nv won't make a ca decision if cwnd is
	95	* smaller than this. It may grow to handle
	96	* TSO, LRO and interrupt coalescence because
	97	* with these a small cwnd cannot saturate
	98	* the link. Note that this is different from
	99	* the file local nv_min_cwnd */
	100	u8 nv_rtt_cnt; /* RTTs without making ca decision */;
	101	u32 nv_last_rtt; /* last rtt */
	102	u32 nv_min_rtt; /* active min rtt. Used to determine slope */
	103	u32 nv_min_rtt_new; /* min rtt for future use */
	104	u32 nv_rtt_max_rate; /* max rate seen during current RTT */
	105	u32 nv_rtt_start_seq; /* current RTT ends when packet arrives
	106	* acking beyond nv_rtt_start_seq */
	107	u32 nv_last_snd_una; /* Previous value of tp->snd_una. It is
	108	* used to determine bytes acked since last
	109	* call to bictcp_acked */
	110	u32 nv_no_cong_cnt; /* Consecutive no congestion decisions */
	111	};
	112
	113	#define NV_INIT_RTT U32_MAX
	114	#define NV_MIN_CWND 4
	115	#define NV_MIN_CWND_GROW 2
	116	#define NV_TSO_CWND_BOUND 80
	117
	118	static inline void tcpnv_reset(struct tcpnv ca, struct sock sk)
	119	{
	120	struct tcp_sock *tp = tcp_sk(sk);
	121
	122	ca->nv_reset = 0;
699fafaf LB	123	ca->nv_no_cong_cnt = 0;
	124	ca->nv_rtt_cnt = 0;
	125	ca->nv_last_rtt = 0;
	126	ca->nv_rtt_max_rate = 0;
	127	ca->nv_rtt_start_seq = tp->snd_una;
	128	ca->nv_eval_call_cnt = 0;
	129	ca->nv_last_snd_una = tp->snd_una;
	130	}
	131
	132	static void tcpnv_init(struct sock *sk)
	133	{
	134	struct tcpnv *ca = inet_csk_ca(sk);
	135
	136	tcpnv_reset(ca, sk);
	137
	138	ca->nv_allow_cwnd_growth = 1;
	139	ca->nv_min_rtt_reset_jiffies = jiffies + 2 * HZ;
	140	ca->nv_min_rtt = NV_INIT_RTT;
	141	ca->nv_min_rtt_new = NV_INIT_RTT;
	142	ca->nv_min_cwnd = NV_MIN_CWND;
	143	ca->nv_catchup = 0;
	144	ca->cwnd_growth_factor = 0;
	145	}
	146
	147	static void tcpnv_cong_avoid(struct sock *sk, u32 ack, u32 acked)
	148	{
	149	struct tcp_sock *tp = tcp_sk(sk);
	150	struct tcpnv *ca = inet_csk_ca(sk);
	151	u32 cnt;
	152
	153	if (!tcp_is_cwnd_limited(sk))
	154	return;
	155
	156	/* Only grow cwnd if NV has not detected congestion */
	157	if (!ca->nv_allow_cwnd_growth)
	158	return;
	159
	160	if (tcp_in_slow_start(tp)) {
	161	acked = tcp_slow_start(tp, acked);
	162	if (!acked)
	163	return;
	164	}
	165
	166	if (ca->cwnd_growth_factor < 0) {
	167	cnt = tp->snd_cwnd << -ca->cwnd_growth_factor;
	168	tcp_cong_avoid_ai(tp, cnt, acked);
	169	} else {
	170	cnt = max(4U, tp->snd_cwnd >> ca->cwnd_growth_factor);
	171	tcp_cong_avoid_ai(tp, cnt, acked);
	172	}
	173	}
	174
	175	static u32 tcpnv_recalc_ssthresh(struct sock *sk)
	176	{
	177	const struct tcp_sock *tp = tcp_sk(sk);
699fafaf	178
699fafaf LB	179	return max((tp->snd_cwnd * nv_loss_dec_factor) >> 10, 2U);
	180	}
	181
699fafaf LB	182	static void tcpnv_state(struct sock *sk, u8 new_state)
	183	{
	184	struct tcpnv *ca = inet_csk_ca(sk);
	185
	186	if (new_state == TCP_CA_Open && ca->nv_reset) {
	187	tcpnv_reset(ca, sk);
	188	} else if (new_state == TCP_CA_Loss \|\| new_state == TCP_CA_CWR \|\|
	189	new_state == TCP_CA_Recovery) {
	190	ca->nv_reset = 1;
	191	ca->nv_allow_cwnd_growth = 0;
	192	if (new_state == TCP_CA_Loss) {
	193	/* Reset cwnd growth factor to Reno value */
	194	if (ca->cwnd_growth_factor > 0)
	195	ca->cwnd_growth_factor = 0;
	196	/* Decrease growth rate if allowed */
	197	if (nv_cwnd_growth_rate_neg > 0 &&
	198	ca->cwnd_growth_factor > -8)
	199	ca->cwnd_growth_factor--;
	200	}
	201	}
	202	}
	203
	204	/* Do congestion avoidance calculations for TCP-NV
	205	*/
	206	static void tcpnv_acked(struct sock sk, const struct ack_sample sample)
	207	{
	208	const struct inet_connection_sock *icsk = inet_csk(sk);
	209	struct tcp_sock *tp = tcp_sk(sk);
	210	struct tcpnv *ca = inet_csk_ca(sk);
	211	unsigned long now = jiffies;
	212	s64 rate64 = 0;
	213	u32 rate, max_win, cwnd_by_slope;
	214	u32 avg_rtt;
	215	u32 bytes_acked = 0;
	216
	217	/* Some calls are for duplicates without timetamps */
	218	if (sample->rtt_us < 0)
	219	return;
	220
	221	/* If not in TCP_CA_Open or TCP_CA_Disorder states, skip. */
	222	if (icsk->icsk_ca_state != TCP_CA_Open &&
	223	icsk->icsk_ca_state != TCP_CA_Disorder)
	224	return;
	225
	226	/* Stop cwnd growth if we were in catch up mode */
	227	if (ca->nv_catchup && tp->snd_cwnd >= nv_min_cwnd) {
	228	ca->nv_catchup = 0;
	229	ca->nv_allow_cwnd_growth = 0;
	230	}
	231
	232	bytes_acked = tp->snd_una - ca->nv_last_snd_una;
	233	ca->nv_last_snd_una = tp->snd_una;
	234
	235	if (sample->in_flight == 0)
	236	return;
	237
	238	/* Calculate moving average of RTT */
	239	if (nv_rtt_factor > 0) {
	240	if (ca->nv_last_rtt > 0) {
	241	avg_rtt = (((u64)sample->rtt_us) * nv_rtt_factor +
	242	((u64)ca->nv_last_rtt)
	243	* (256 - nv_rtt_factor)) >> 8;
	244	} else {
	245	avg_rtt = sample->rtt_us;
246	ca->nv_min_rtt = avg_rtt << 1;
247	}
248	ca->nv_last_rtt = avg_rtt;
249	} else {
250	avg_rtt = sample->rtt_us;
251	}
252
253	/* rate in 100's bits per second */
254	rate64 = ((u64)sample->in_flight) * 8000000;
255	rate = (u32)div64_u64(rate64, (u64)(avg_rtt * 100));
256
257	/* Remember the maximum rate seen during this RTT
258	* Note: It may be more than one RTT. This function should be
259	* called at least nv_dec_eval_min_calls times.
260	*/
261	if (ca->nv_rtt_max_rate < rate)
262	ca->nv_rtt_max_rate = rate;
263
264	/* We have valid information, increment counter */
265	if (ca->nv_eval_call_cnt < 255)
266	ca->nv_eval_call_cnt++;
267
268	/* update min rtt if necessary */
269	if (avg_rtt < ca->nv_min_rtt)
270	ca->nv_min_rtt = avg_rtt;
271
272	/* update future min_rtt if necessary */
273	if (avg_rtt < ca->nv_min_rtt_new)
274	ca->nv_min_rtt_new = avg_rtt;
275
276	/* nv_min_rtt is updated with the minimum (possibley averaged) rtt
277	* seen in the last sysctl_tcp_nv_reset_period seconds (i.e. a
278	* warm reset). This new nv_min_rtt will be continued to be updated
279	* and be used for another sysctl_tcp_nv_reset_period seconds,
280	* when it will be updated again.
281	* In practice we introduce some randomness, so the actual period used
282	* is chosen randomly from the range:
283	* [sysctl_tcp_nv_reset_period3/4, sysctl_tcp_nv_reset_period5/4)
284	*/
285	if (time_after_eq(now, ca->nv_min_rtt_reset_jiffies)) {
286	unsigned char rand;
287
288	ca->nv_min_rtt = ca->nv_min_rtt_new;
289	ca->nv_min_rtt_new = NV_INIT_RTT;
290	get_random_bytes(&rand, 1);
291	ca->nv_min_rtt_reset_jiffies =
292	now + ((nv_reset_period * (384 + rand) * HZ) >> 9);
293	/* Every so often we decrease ca->nv_min_cwnd in case previous
294	* value is no longer accurate.
295	*/
296	ca->nv_min_cwnd = max(ca->nv_min_cwnd / 2, NV_MIN_CWND);
297	}
298
299	/* Once per RTT check if we need to do congestion avoidance */
300	if (before(ca->nv_rtt_start_seq, tp->snd_una)) {
301	ca->nv_rtt_start_seq = tp->snd_nxt;
302	if (ca->nv_rtt_cnt < 0xff)
303	/* Increase counter for RTTs without CA decision */
304	ca->nv_rtt_cnt++;
305
306	/* If this function is only called once within an RTT
307	* the cwnd is probably too small (in some cases due to
308	* tso, lro or interrupt coalescence), so we increase
309	* ca->nv_min_cwnd.
310	*/
311	if (ca->nv_eval_call_cnt == 1 &&
312	bytes_acked >= (ca->nv_min_cwnd - 1) * tp->mss_cache &&
313	ca->nv_min_cwnd < (NV_TSO_CWND_BOUND + 1)) {
314	ca->nv_min_cwnd = min(ca->nv_min_cwnd
315	+ NV_MIN_CWND_GROW,
316	NV_TSO_CWND_BOUND + 1);
317	ca->nv_rtt_start_seq = tp->snd_nxt +
318	ca->nv_min_cwnd * tp->mss_cache;
319	ca->nv_eval_call_cnt = 0;
320	ca->nv_allow_cwnd_growth = 1;
321	return;
322	}
323
324	/* Find the ideal cwnd for current rate from slope
325	* slope = 80000.0 * mss / nv_min_rtt
326	* cwnd_by_slope = nv_rtt_max_rate / slope
327	*/
328	cwnd_by_slope = (u32)
329	div64_u64(((u64)ca->nv_rtt_max_rate) * ca->nv_min_rtt,
330	(u64)(80000 * tp->mss_cache));
331	max_win = cwnd_by_slope + nv_pad;
332
333	/* If cwnd > max_win, decrease cwnd
334	* if cwnd < max_win, grow cwnd
335	* else leave the same
336	*/
337	if (tp->snd_cwnd > max_win) {
338	/* there is congestion, check that it is ok
339	* to make a CA decision
340	* 1. We should have at least nv_dec_eval_min_calls
341	* data points before making a CA decision
342	* 2. We only make a congesion decision after
343	* nv_rtt_min_cnt RTTs
344	*/
345	if (ca->nv_rtt_cnt < nv_rtt_min_cnt) {
346	return;
347	} else if (tp->snd_ssthresh == TCP_INFINITE_SSTHRESH) {
348	if (ca->nv_eval_call_cnt <
349	nv_ssthresh_eval_min_calls)
350	return;
351	/* otherwise we will decrease cwnd */
352	} else if (ca->nv_eval_call_cnt <
353	nv_dec_eval_min_calls) {
354	if (ca->nv_allow_cwnd_growth &&
355	ca->nv_rtt_cnt > nv_stop_rtt_cnt)
356	ca->nv_allow_cwnd_growth = 0;
357	return;
358	}
359
360	/* We have enough data to determine we are congested */
361	ca->nv_allow_cwnd_growth = 0;
362	tp->snd_ssthresh =
363	(nv_ssthresh_factor * max_win) >> 3;
364	if (tp->snd_cwnd - max_win > 2) {
365	/* gap > 2, we do exponential cwnd decrease */
366	int dec;
367
368	dec = max(2U, ((tp->snd_cwnd - max_win) *
369	nv_cong_dec_mult) >> 7);
370	tp->snd_cwnd -= dec;
371	} else if (nv_cong_dec_mult > 0) {
372	tp->snd_cwnd = max_win;
373	}
374	if (ca->cwnd_growth_factor > 0)
375	ca->cwnd_growth_factor = 0;
376	ca->nv_no_cong_cnt = 0;
377	} else if (tp->snd_cwnd <= max_win - nv_pad_buffer) {
378	/* There is no congestion, grow cwnd if allowed*/
379	if (ca->nv_eval_call_cnt < nv_inc_eval_min_calls)
380	return;
381
382	ca->nv_allow_cwnd_growth = 1;
383	ca->nv_no_cong_cnt++;
384	if (ca->cwnd_growth_factor < 0 &&
385	nv_cwnd_growth_rate_neg > 0 &&
386	ca->nv_no_cong_cnt > nv_cwnd_growth_rate_neg) {
387	ca->cwnd_growth_factor++;
388	ca->nv_no_cong_cnt = 0;
389	} else if (ca->cwnd_growth_factor >= 0 &&
390	nv_cwnd_growth_rate_pos > 0 &&
391	ca->nv_no_cong_cnt >
392	nv_cwnd_growth_rate_pos) {
393	ca->cwnd_growth_factor++;
394	ca->nv_no_cong_cnt = 0;
395	}
396	} else {
397	/* cwnd is in-between, so do nothing */
398	return;
399	}
400
401	/* update state */
402	ca->nv_eval_call_cnt = 0;
403	ca->nv_rtt_cnt = 0;
404	ca->nv_rtt_max_rate = 0;
405
406	/* Don't want to make cwnd < nv_min_cwnd
407	* (it wasn't before, if it is now is because nv
408	* decreased it).
409	*/
410	if (tp->snd_cwnd < nv_min_cwnd)
411	tp->snd_cwnd = nv_min_cwnd;
412	}
413	}
414
415	/* Extract info for Tcp socket info provided via netlink */
c718c6d6	416	static size_t tcpnv_get_info(struct sock sk, u32 ext, int attr,
c718c6d6	417	union tcp_cc_info *info)
699fafaf LB	418	{
	419	const struct tcpnv *ca = inet_csk_ca(sk);
	420
	421	if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
	422	info->vegas.tcpv_enabled = 1;
	423	info->vegas.tcpv_rttcnt = ca->nv_rtt_cnt;
	424	info->vegas.tcpv_rtt = ca->nv_last_rtt;
	425	info->vegas.tcpv_minrtt = ca->nv_min_rtt;
	426
	427	*attr = INET_DIAG_VEGASINFO;
	428	return sizeof(struct tcpvegas_info);
	429	}
	430	return 0;
	431	}
699fafaf LB	432
	433	static struct tcp_congestion_ops tcpnv __read_mostly = {
	434	.init = tcpnv_init,
	435	.ssthresh = tcpnv_recalc_ssthresh,
	436	.cong_avoid = tcpnv_cong_avoid,
	437	.set_state = tcpnv_state,
f1722a1b	438	.undo_cwnd = tcp_reno_undo_cwnd,
699fafaf LB	439	.pkts_acked = tcpnv_acked,
	440	.get_info = tcpnv_get_info,
	441
	442	.owner = THIS_MODULE,
	443	.name = "nv",
	444	};
	445
	446	static int __init tcpnv_register(void)
	447	{
	448	BUILD_BUG_ON(sizeof(struct tcpnv) > ICSK_CA_PRIV_SIZE);
	449
	450	return tcp_register_congestion_control(&tcpnv);
	451	}
	452
	453	static void __exit tcpnv_unregister(void)
	454	{
	455	tcp_unregister_congestion_control(&tcpnv);
	456	}
	457
	458	module_init(tcpnv_register);
	459	module_exit(tcpnv_unregister);
	460
	461	MODULE_AUTHOR("Lawrence Brakmo");
	462	MODULE_LICENSE("GPL");
	463	MODULE_DESCRIPTION("TCP NV");
	464	MODULE_VERSION("1.0");