cc - zygaena/hammerhead

root / base / usr / src / uts / common / inet / cc
cc Plain Text 1511 lines 44.5 KB
This software was developed by Lawrence Stewart while studying at the Centre
for Advanced Internet Architectures, Swinburne University of Technology, made
possible in part by a grant from the Cisco University Research Program Fund
at Community Foundation Silicon Valley.

Portions of this software were developed at the Centre for Advanced
Internet Architectures, Swinburne University of Technology, Melbourne,
Australia by David Hayes under sponsorship from the FreeBSD Foundation.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
The congestion control framework, its header, and the CUBIC and NewReno
congestion control modules came from FreeBSD, and are therefore licensed
under the 2-Clause BSD License.
/*
 * Copyright (c) 2007-2008
 *	Swinburne University of Technology, Melbourne, Australia.
 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
 * Copyright (c) 2010 The FreeBSD Foundation
 * All rights reserved.
 * Copyright (c) 2017 by Delphix. All rights reserved.
 *
 * This software was developed at the Centre for Advanced Internet
 * Architectures, Swinburne University of Technology, by Lawrence Stewart and
 * James Healy, made possible in part by a grant from the Cisco University
 * Research Program Fund at Community Foundation Silicon Valley.
 *
 * Portions of this software were developed at the Centre for Advanced
 * Internet Architectures, Swinburne University of Technology, Melbourne,
 * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * This software was first released in 2007 by James Healy and Lawrence Stewart
 * whilst working on the NewTCP research project at Swinburne University of
 * Technology's Centre for Advanced Internet Architectures, Melbourne,
 * Australia, which was made possible in part by a grant from the Cisco
 * University Research Program Fund at Community Foundation Silicon Valley.
 * More details are available at:
 *   http://caia.swin.edu.au/urp/newtcp/
 */

#include <sys/param.h>
#include <sys/errno.h>
#include <sys/systm.h>
#include <sys/queue.h>
#include <inet/cc.h>
#include <inet/tcp.h>
#include <sys/sdt.h>

#define	CC_KMODDIR	"cc"

/*
 * List of available cc algorithms on the current system. Access is
 * synchronized using cc_list_lock.
 */
static STAILQ_HEAD(cc_head, cc_algo) cc_list = STAILQ_HEAD_INITIALIZER(cc_list);
static kmutex_t cc_list_lock;

static struct modlmisc cc_modlmisc = {
	&mod_miscops,
	"Pluggable Congestion Control Framework"
};

static struct modlinkage cc_modlinkage = {
	MODREV_1,
	&cc_modlmisc,
	NULL
};

/*
 * Initialise CC subsystem on system boot.
 */
int
_init(void)
{
	STAILQ_INIT(&cc_list);

	return (mod_install(&cc_modlinkage));
}

int
_fini(void)
{
	return (EBUSY);
}

int
_info(struct modinfo *modinfop)
{
	return (mod_info(&cc_modlinkage, modinfop));
}

int
cc_walk_algos(cc_walk_func_t *func, void *cd)
{
	struct cc_algo *algo;
	int ret = 0;

	mutex_enter(&cc_list_lock);
	STAILQ_FOREACH(algo, &cc_list, entries) {
		if ((ret = func(cd, algo)) != 0) {
			break;
		}
	}
	mutex_exit(&cc_list_lock);

	return (ret);
}

/*
 * Search for an algorithm of a given name, and return the corresponding set of
 * operations. If there is no algorithm with the given name present, then this
 * function returns NULL.
 *
 * Since this function is passed names from userland, it needs to be paranoid
 * about the string, in case it's missing a terminating NUL character.
 */
struct cc_algo *
cc_load_algo(const char *name)
{
	struct cc_algo *algo;
	boolean_t found = B_FALSE;

	if (strnlen(name, CC_ALGO_NAME_MAX) >= CC_ALGO_NAME_MAX) {
		return (NULL);
	}

	mutex_enter(&cc_list_lock);
	STAILQ_FOREACH(algo, &cc_list, entries) {
		if (strncmp(algo->name, name, CC_ALGO_NAME_MAX) == 0) {
			found = B_TRUE;
			break;
		}
	}
	mutex_exit(&cc_list_lock);

	return (found ? algo : NULL);
}

/*
 * Returns non-zero on success, 0 on failure.
 */
int
cc_deregister_algo(struct cc_algo *remove_cc)
{
	struct cc_algo *funcs, *tmpfuncs;
	int err = ENOENT;

	mutex_enter(&cc_list_lock);
	STAILQ_FOREACH_SAFE(funcs, &cc_list, entries, tmpfuncs) {
		if (funcs == remove_cc) {
			STAILQ_REMOVE(&cc_list, funcs, cc_algo, entries);
			err = 0;
			break;
		}
	}
	mutex_exit(&cc_list_lock);
	return (err);
}

/*
 * Returns 0 on success, non-zero on failure.
 */
int
cc_register_algo(struct cc_algo *add_cc)
{
	struct cc_algo *funcs;
	size_t nlen;
	int err = 0;

	nlen = strnlen(add_cc->name, CC_ALGO_NAME_MAX);
	if (nlen == 0 || nlen >= CC_ALGO_NAME_MAX) {
		return (EINVAL);
	}

	/*
	 * Iterate over list of registered CC algorithms and make sure
	 * we're not trying to add a duplicate.
	 */
	mutex_enter(&cc_list_lock);
	STAILQ_FOREACH(funcs, &cc_list, entries) {
		if (strncmp(funcs->name, add_cc->name, CC_ALGO_NAME_MAX) == 0)
			err = EEXIST;
	}

	if (err == 0)
		STAILQ_INSERT_TAIL(&cc_list, add_cc, entries);

	mutex_exit(&cc_list_lock);

	return (err);
}
/*
 * Copyright (c) 2008-2010 Lawrence Stewart <lstewart@freebsd.org>
 * Copyright (c) 2010 The FreeBSD Foundation
 * All rights reserved.
 * Copyright (c) 2017 by Delphix. All rights reserved.
 * Copyright 2019 Joyent, Inc.
 * Copyright 2020 RackTop Systems, Inc.
 *
 * This software was developed by Lawrence Stewart while studying at the Centre
 * for Advanced Internet Architectures, Swinburne University of Technology, made
 * possible in part by a grant from the Cisco University Research Program Fund
 * at Community Foundation Silicon Valley.
 *
 * Portions of this software were developed at the Centre for Advanced
 * Internet Architectures, Swinburne University of Technology, Melbourne,
 * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * An implementation of the CUBIC congestion control algorithm for FreeBSD,
 * based on the Internet Draft "draft-rhee-tcpm-cubic-02" by Rhee, Xu and Ha.
 * Originally released as part of the NewTCP research project at Swinburne
 * University of Technology's Centre for Advanced Internet Architectures,
 * Melbourne, Australia, which was made possible in part by a grant from the
 * Cisco University Research Program Fund at Community Foundation Silicon
 * Valley. More details are available at:
 *   http://caia.swin.edu.au/urp/newtcp/
 */

#include <sys/errno.h>
#include <sys/types.h>
#include <sys/kmem.h>
#include <sys/ddi.h>
#include <sys/sunddi.h>
#include <sys/modctl.h>
#include <sys/time.h>

#include <inet/tcp_impl.h>
#include <inet/cc.h>
#include <inet/cc/cc_cubic.h>
#include <inet/cc/cc_module.h>

static struct modlmisc cc_cubic_modlmisc = {
	&mod_miscops,
	"Cubic Congestion Control"
};

static struct modlinkage cc_cubic_modlinkage = {
	MODREV_1,
	&cc_cubic_modlmisc,
	NULL
};

/*
 * cubic uses the NewReno implementation of after_idle and uses NewReno's
 * ack_received callback during slow start.
 */
static struct cc_algo *newreno_cc_algo;

static void	cubic_ack_received(struct cc_var *ccv, uint16_t type);
static void	cubic_cb_destroy(struct cc_var *ccv);
static int	cubic_cb_init(struct cc_var *ccv);
static void	cubic_cong_signal(struct cc_var *ccv, uint32_t type);
static void	cubic_conn_init(struct cc_var *ccv);
static void	cubic_post_recovery(struct cc_var *ccv);
static void	cubic_record_rtt(struct cc_var *ccv);
static void	cubic_ssthresh_update(struct cc_var *ccv);
static void	cubic_after_idle(struct cc_var *ccv);

struct cubic {
	/* Cubic K in fixed point form with CUBIC_SHIFT worth of precision. */
	int64_t		K;
	/* Sum of RTT samples across an epoch in nanoseconds. */
	hrtime_t	sum_rtt_nsecs;
	/* cwnd at the most recent congestion event. */
	uint32_t	max_cwnd;
	/* cwnd at the previous congestion event. */
	uint32_t	prev_max_cwnd;
	/* Number of congestion events. */
	uint32_t	num_cong_events;
	/* Minimum observed rtt in nanoseconds. */
	hrtime_t	min_rtt_nsecs;
	/* Mean observed rtt between congestion epochs. */
	hrtime_t	mean_rtt_nsecs;
	/* ACKs since last congestion event. */
	int		epoch_ack_count;
	/* Time of last congestion event in nanoseconds. */
	hrtime_t	t_last_cong;
};

struct cc_algo cubic_cc_algo = {
	.name = "cubic",
	.ack_received = cubic_ack_received,
	.cb_destroy = cubic_cb_destroy,
	.cb_init = cubic_cb_init,
	.cong_signal = cubic_cong_signal,
	.conn_init = cubic_conn_init,
	.post_recovery = cubic_post_recovery,
	.after_idle = cubic_after_idle,
};

int
_init(void)
{
	int err;

	if ((newreno_cc_algo = cc_load_algo("newreno")) == NULL)
		return (EINVAL);

	if ((err = cc_register_algo(&cubic_cc_algo)) == 0) {
		if ((err = mod_install(&cc_cubic_modlinkage)) != 0)
			(void) cc_deregister_algo(&cubic_cc_algo);
	}

	return (err);
}

int
_fini(void)
{
	/* XXX Not unloadable for now */
	return (EBUSY);
}

int
_info(struct modinfo *modinfop)
{
	return (mod_info(&cc_cubic_modlinkage, modinfop));
}

static void
cubic_ack_received(struct cc_var *ccv, uint16_t type)
{
	struct cubic *cubic_data;
	uint32_t w_tf, w_cubic_next;
	hrtime_t nsecs_since_cong;

	cubic_data = ccv->cc_data;
	cubic_record_rtt(ccv);

	/*
	 * Regular ACK and we're not in cong/fast recovery and we're cwnd
	 * limited and we're either not doing ABC or are slow starting or are
	 * doing ABC and we've sent a cwnd's worth of bytes.
	 */
	if (type == CC_ACK && !IN_RECOVERY(ccv->flags) &&
	    (ccv->flags & CCF_CWND_LIMITED) && (!CC_ABC(ccv) ||
	    CCV(ccv, tcp_cwnd) <= CCV(ccv, tcp_cwnd_ssthresh) ||
	    (CC_ABC(ccv) && (ccv->flags & CCF_ABC_SENTAWND)))) {
		/* Use the logic in NewReno ack_received() for slow start. */
		if (CCV(ccv, tcp_cwnd) <= CCV(ccv, tcp_cwnd_ssthresh) ||
		    cubic_data->min_rtt_nsecs == TCPTV_SRTTBASE)
			newreno_cc_algo->ack_received(ccv, type);
		else {
			nsecs_since_cong = gethrtime() -
			    cubic_data->t_last_cong;

			/*
			 * The mean RTT is used to best reflect the equations in
			 * the I-D. Using min_rtt in the tf_cwnd calculation
			 * causes w_tf to grow much faster than it should if the
			 * RTT is dominated by network buffering rather than
			 * propagation delay.
			 */
			w_tf = tf_cwnd(nsecs_since_cong,
			    cubic_data->mean_rtt_nsecs, cubic_data->max_cwnd,
			    CCV(ccv, tcp_mss));

			w_cubic_next = cubic_cwnd(nsecs_since_cong +
			    cubic_data->mean_rtt_nsecs, cubic_data->max_cwnd,
			    CCV(ccv, tcp_mss), cubic_data->K);

			ccv->flags &= ~CCF_ABC_SENTAWND;

			if (w_cubic_next < w_tf) {
				/*
				 * TCP-friendly region, follow tf
				 * cwnd growth.
				 */
				if (CCV(ccv, tcp_cwnd) < w_tf)
					CCV(ccv, tcp_cwnd) = w_tf;
			} else if (CCV(ccv, tcp_cwnd) < w_cubic_next) {
				/*
				 * Concave or convex region, follow CUBIC
				 * cwnd growth.
				 */
				if (CC_ABC(ccv))
					CCV(ccv, tcp_cwnd) = MIN(w_cubic_next,
					    INT_MAX);
				else
					CCV(ccv, tcp_cwnd) += MAX(1,
					    ((MIN(w_cubic_next, INT_MAX) -
					    CCV(ccv, tcp_cwnd)) *
					    CCV(ccv, tcp_mss)) /
					    CCV(ccv, tcp_cwnd));
			}

			/*
			 * If we're not in slow start and we're probing for a
			 * new cwnd limit at the start of a connection
			 * (happens when hostcache has a relevant entry),
			 * keep updating our current estimate of the
			 * max_cwnd.
			 */
			if (cubic_data->num_cong_events == 0 &&
			    cubic_data->max_cwnd < CCV(ccv, tcp_cwnd)) {
				cubic_data->max_cwnd = CCV(ccv, tcp_cwnd);
				cubic_data->K = cubic_k(cubic_data->max_cwnd /
				    CCV(ccv, tcp_mss));
			}
		}
	}
}

/*
 * This is a Cubic specific implementation of after_idle.
 *   - Reset cwnd by calling New Reno implementation of after_idle.
 *   - Reset t_last_cong.
 */
static void
cubic_after_idle(struct cc_var *ccv)
{
	struct cubic *cubic_data;

	cubic_data = ccv->cc_data;

	cubic_data->max_cwnd = max(cubic_data->max_cwnd, CCV(ccv, tcp_cwnd));
	cubic_data->K = cubic_k(cubic_data->max_cwnd / CCV(ccv, tcp_mss));

	newreno_cc_algo->after_idle(ccv);
	cubic_data->t_last_cong = gethrtime();
}

static void
cubic_cb_destroy(struct cc_var *ccv)
{

	if (ccv->cc_data != NULL)
		kmem_free(ccv->cc_data, sizeof (struct cubic));
}

static int
cubic_cb_init(struct cc_var *ccv)
{
	struct cubic *cubic_data;

	cubic_data = kmem_zalloc(sizeof (struct cubic), KM_NOSLEEP);

	if (cubic_data == NULL)
		return (ENOMEM);

	/* Init some key variables with sensible defaults. */
	cubic_data->t_last_cong = gethrtime();
	cubic_data->min_rtt_nsecs = TCPTV_SRTTBASE;
	cubic_data->mean_rtt_nsecs = 1;

	ccv->cc_data = cubic_data;

	return (0);
}

/*
 * Perform any necessary tasks before we enter congestion recovery.
 */
static void
cubic_cong_signal(struct cc_var *ccv, uint32_t type)
{
	struct cubic *cubic_data;
	uint32_t cwin;
	uint32_t mss;

	cubic_data = ccv->cc_data;
	cwin = CCV(ccv, tcp_cwnd);
	mss = CCV(ccv, tcp_mss);

	switch (type) {
	case CC_NDUPACK:
		if (!IN_FASTRECOVERY(ccv->flags)) {
			if (!IN_CONGRECOVERY(ccv->flags)) {
				cubic_ssthresh_update(ccv);
				cubic_data->num_cong_events++;
				cubic_data->prev_max_cwnd =
				    cubic_data->max_cwnd;
				cubic_data->max_cwnd = cwin;
				CCV(ccv, tcp_cwnd) =
				    CCV(ccv, tcp_cwnd_ssthresh);
			}
			ENTER_RECOVERY(ccv->flags);
		}
		break;

	case CC_ECN:
		if (!IN_CONGRECOVERY(ccv->flags)) {
			cubic_ssthresh_update(ccv);
			cubic_data->num_cong_events++;
			cubic_data->prev_max_cwnd = cubic_data->max_cwnd;
			cubic_data->max_cwnd = cwin;
			cubic_data->t_last_cong = gethrtime();
			CCV(ccv, tcp_cwnd) = CCV(ccv, tcp_cwnd_ssthresh);
			ENTER_CONGRECOVERY(ccv->flags);
		}
		break;

	case CC_RTO:
		/*
		 * Grab the current time and record it so we know when the
		 * most recent congestion event was.
		 */
		cubic_data->num_cong_events++;
		cubic_data->t_last_cong = gethrtime();
		cubic_ssthresh_update(ccv);
		cubic_data->max_cwnd = cwin;
		CCV(ccv, tcp_cwnd) = mss;
		break;
	}
}

static void
cubic_conn_init(struct cc_var *ccv)
{
	struct cubic *cubic_data;

	cubic_data = ccv->cc_data;

	/*
	 * Ensure we have a sane initial value for max_cwnd recorded. Without
	 * this here bad things happen when entries from the TCP hostcache
	 * get used.
	 */
	cubic_data->max_cwnd = CCV(ccv, tcp_cwnd);
}

/*
 * Perform any necessary tasks before we exit congestion recovery.
 */
static void
cubic_post_recovery(struct cc_var *ccv)
{
	struct cubic *cubic_data;
	uint32_t mss, pipe;

	cubic_data = ccv->cc_data;

	/* Fast convergence heuristic. */
	if (cubic_data->max_cwnd < cubic_data->prev_max_cwnd) {
		cubic_data->max_cwnd = (cubic_data->max_cwnd * CUBIC_FC_FACTOR)
		    >> CUBIC_SHIFT;
	}

	/*
	 * There is a risk that if the cwnd becomes less than mss, and
	 * we do not get enough acks to drive it back up beyond mss,
	 * we will stop transmitting data altogether.
	 *
	 * The Cubic RFC defines values in terms of units of mss. Therefore
	 * we must make sure we have at least 1 mss to make progress
	 * since the algorthm is written that way.
	 */
	mss = CCV(ccv, tcp_mss);

	if (IN_FASTRECOVERY(ccv->flags)) {
		/*
		 * If inflight data is less than ssthresh, set cwnd
		 * conservatively to avoid a burst of data, as suggested in
		 * the NewReno RFC. Otherwise, use the CUBIC method.
		 */
		pipe = CCV(ccv, tcp_snxt) - CCV(ccv, tcp_suna);
		if (pipe < CCV(ccv, tcp_cwnd_ssthresh)) {
			/*
			 * Ensure that cwnd does not collapse to 1 MSS under
			 * adverse conditions. Implements RFC6582
			 */
			CCV(ccv, tcp_cwnd) = MAX(pipe, mss) + mss;
		} else {
			/* Update cwnd based on beta and adjusted max_cwnd. */
			CCV(ccv, tcp_cwnd) = max(mss, ((CUBIC_BETA *
			    cubic_data->max_cwnd) >> CUBIC_SHIFT));
		}
	} else {
		CCV(ccv, tcp_cwnd) = max(mss, CCV(ccv, tcp_cwnd));
	}

	cubic_data->t_last_cong = gethrtime();

	/* Calculate the average RTT between congestion epochs. */
	if (cubic_data->epoch_ack_count > 0 &&
	    cubic_data->sum_rtt_nsecs >= cubic_data->epoch_ack_count) {
		cubic_data->mean_rtt_nsecs =
		    (cubic_data->sum_rtt_nsecs / cubic_data->epoch_ack_count);
	}

	cubic_data->epoch_ack_count = 0;
	cubic_data->sum_rtt_nsecs = 0;
	cubic_data->K = cubic_k(cubic_data->max_cwnd / mss);
}

/*
 * Record the min RTT and sum samples for the epoch average RTT calculation.
 */
static void
cubic_record_rtt(struct cc_var *ccv)
{
	struct cubic *cubic_data;
	int t_srtt_nsecs;

	/* Ignore srtt until a min number of samples have been taken. */
	if (CCV(ccv, tcp_rtt_update) >= CUBIC_MIN_RTT_SAMPLES) {
		cubic_data = ccv->cc_data;
		/* tcp_rtt_sa is 8 * smoothed RTT in nanoseconds */
		t_srtt_nsecs = CCV(ccv, tcp_rtt_sa) >> 3;

		/*
		 * Record the current SRTT as our minrtt if it's the smallest
		 * we've seen or minrtt is currently equal to its initialized
		 * value.
		 *
		 * XXXLAS: Should there be some hysteresis for minrtt?
		 */
		if ((t_srtt_nsecs < cubic_data->min_rtt_nsecs ||
		    cubic_data->min_rtt_nsecs == TCPTV_SRTTBASE)) {
			cubic_data->min_rtt_nsecs = max(1, t_srtt_nsecs);

			/*
			 * If the connection is within its first congestion
			 * epoch, ensure we prime mean_rtt_nsecs with a
			 * reasonable value until the epoch average RTT is
			 * calculated in cubic_post_recovery().
			 */
			if (cubic_data->min_rtt_nsecs >
			    cubic_data->mean_rtt_nsecs)
				cubic_data->mean_rtt_nsecs =
				    cubic_data->min_rtt_nsecs;
		}

		/* Sum samples for epoch average RTT calculation. */
		cubic_data->sum_rtt_nsecs += t_srtt_nsecs;
		cubic_data->epoch_ack_count++;
	}
}

/*
 * Update the ssthresh in the event of congestion.
 */
static void
cubic_ssthresh_update(struct cc_var *ccv)
{
	struct cubic *cubic_data;

	cubic_data = ccv->cc_data;

	/*
	 * On the first congestion event, set ssthresh to cwnd * 0.5, on
	 * subsequent congestion events, set it to cwnd * beta.
	 */
	if (cubic_data->num_cong_events == 0)
		CCV(ccv, tcp_cwnd_ssthresh) = CCV(ccv, tcp_cwnd) >> 1;
	else
		CCV(ccv, tcp_cwnd_ssthresh) =
		    (CCV(ccv, tcp_cwnd) * CUBIC_BETA) >> CUBIC_SHIFT;
}
/*
 * Copyright (c) 2008-2010 Lawrence Stewart <lstewart@freebsd.org>
 * Copyright (c) 2010 The FreeBSD Foundation
 * All rights reserved.
 * Copyright (c) 2017 by Delphix. All rights reserved.
 * Copyright 2019 Joyent, Inc.
 * Copyright 2020 RackTop Systems, Inc.
 *
 * This software was developed by Lawrence Stewart while studying at the Centre
 * for Advanced Internet Architectures, Swinburne University of Technology, made
 * possible in part by a grant from the Cisco University Research Program Fund
 * at Community Foundation Silicon Valley.
 *
 * Portions of this software were developed at the Centre for Advanced
 * Internet Architectures, Swinburne University of Technology, Melbourne,
 * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * $FreeBSD$
 */

#ifndef _NETINET_CC_CUBIC_H_
#define	_NETINET_CC_CUBIC_H_

/* Number of bits of precision for fixed point math calcs. */
#define	CUBIC_SHIFT		8

#define	CUBIC_SHIFT_4		32

/* 0.5 << CUBIC_SHIFT. */
#define	RENO_BETA		128

/* ~0.8 << CUBIC_SHIFT. */
#define	CUBIC_BETA		204

/* ~0.2 << CUBIC_SHIFT. */
#define	ONE_SUB_CUBIC_BETA	51

/* 3 * ONE_SUB_CUBIC_BETA. */
#define	THREE_X_PT2		153

/* (2 << CUBIC_SHIFT) - ONE_SUB_CUBIC_BETA. */
#define	TWO_SUB_PT2		461

/* ~0.4 << CUBIC_SHIFT. */
#define	CUBIC_C_FACTOR		102

/* CUBIC fast convergence factor: ~0.9 << CUBIC_SHIFT. */
#define	CUBIC_FC_FACTOR		230

/* Don't trust s_rtt until this many rtt samples have been taken. */
#define	CUBIC_MIN_RTT_SAMPLES	8

/*
 * (2^21)^3 is long max. Dividing (2^63) by Cubic_C_factor
 * and taking cube-root yields 448845 as the effective useful limit
 */
#define	CUBED_ROOT_MAX_ULONG	448845

/* Userland only bits. */
#ifndef _KERNEL

extern int hz;

/*
 * Implementation based on the formulae found in the CUBIC Internet Draft
 * "draft-rhee-tcpm-cubic-02".
 *
 * Note BETA used in cc_cubic is equal to (1-beta) in the I-D
 */

static __inline float
theoretical_cubic_k(double wmax_pkts)
{
	double C;

	C = 0.4;

	return (pow((wmax_pkts * 0.2) / C, (1.0 / 3.0)) * pow(2, CUBIC_SHIFT));
}

static __inline uint32_t
theoretical_cubic_cwnd(int ticks_since_cong, uint32_t wmax, uint32_t smss)
{
	double C, wmax_pkts;

	C = 0.4;
	wmax_pkts = wmax / (double)smss;

	return (smss * (wmax_pkts +
	    (C * pow(ticks_since_cong / (double)hz -
	    theoretical_cubic_k(wmax_pkts) / pow(2, CUBIC_SHIFT), 3.0))));
}

static __inline uint32_t
theoretical_reno_cwnd(int ticks_since_cong, int rtt_ticks, uint32_t wmax,
    uint32_t smss)
{

	return ((wmax * 0.5) + ((ticks_since_cong / (float)rtt_ticks) * smss));
}

static __inline uint32_t
theoretical_tf_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax,
    uint32_t smss)
{

	return ((wmax * 0.8) + ((3 * 0.2) / (2 - 0.2) *
	    (ticks_since_cong / (float)rtt_ticks) * smss));
}

#endif /* !_KERNEL */

/*
 * Compute the CUBIC K value used in the cwnd calculation, using an
 * implementation of eqn 2 in the I-D. The method used
 * here is adapted from Apple Computer Technical Report #KT-32.
 */
static __inline int64_t
cubic_k(uint32_t wmax_pkts)
{
	int64_t s, K;
	uint16_t p;

	K = s = 0;
	p = 0;

	/* (wmax * beta)/C with CUBIC_SHIFT worth of precision. */
	s = ((wmax_pkts * ONE_SUB_CUBIC_BETA) << CUBIC_SHIFT) / CUBIC_C_FACTOR;

	/* Rebase s to be between 1 and 1/8 with a shift of CUBIC_SHIFT. */
	while (s >= 256) {
		s >>= 3;
		p++;
	}

	/*
	 * Some magic constants taken from the Apple TR with appropriate
	 * shifts: 275 == 1.072302 << CUBIC_SHIFT, 98 == 0.3812513 <<
	 * CUBIC_SHIFT, 120 == 0.46946116 << CUBIC_SHIFT.
	 */
	K = (((s * 275) >> CUBIC_SHIFT) + 98) -
	    (((s * s * 120) >> CUBIC_SHIFT) >> CUBIC_SHIFT);

	/* Multiply by 2^p to undo the rebasing of s from above. */
	return (K <<= p);
}

/*
 * Compute the new cwnd value using an implementation of eqn 1 from the I-D.
 * Thanks to Kip Macy for help debugging this function.
 *
 * XXXLAS: Characterise bounds for overflow.
 */
static __inline uint32_t
cubic_cwnd(hrtime_t nsecs_since_cong, uint32_t wmax, uint32_t smss, int64_t K)
{
	int64_t t, cwnd;

	/*
	 * Convert nsecs_since_cong to milliseconds, with CUBIC_SHIFT worth
	 * of precision.
	 */
	t = NSEC2MSEC(nsecs_since_cong << CUBIC_SHIFT);

	/*
	 * K is the time period in seconds that it will take to reach wmax. The
	 * value is kept in fixed point form with CUBIC_SHIFT worth of
	 * precision.
	 *
	 * For comparison with t, we convert K to milliseconds, and then convert
	 * the result back to seconds.
	 *
	 * cwnd = t - K, with CUBIC_SHIFT worth of precision.
	 */
	cwnd = (t - K * MILLISEC) / MILLISEC;

	if (cwnd > CUBED_ROOT_MAX_ULONG)
		return (INT_MAX);
	if (cwnd < -CUBED_ROOT_MAX_ULONG)
		return (0);

	/* cwnd = (t - K)^3, with CUBIC_SHIFT^3 worth of precision. */
	cwnd *= (cwnd * cwnd);

	/*
	 * C(t - K)^3 + wmax
	 * The down shift by CUBIC_SHIFT_4 is because cwnd has 4 lots of
	 * CUBIC_SHIFT included in the value. 3 from the cubing of cwnd above,
	 * and an extra from multiplying through by CUBIC_C_FACTOR.
	 */
	cwnd = ((cwnd * CUBIC_C_FACTOR * smss) >> CUBIC_SHIFT_4) + wmax;

	/*
	 * for negative cwnd, limiting to zero as lower bound
	 */
	return (max(0, cwnd));
}

/*
 * Compute an approximation of the "TCP friendly" cwnd some number of
 * nanoseconds after a congestion event that is designed to yield the same
 * average cwnd as NewReno while using CUBIC's beta of 0.8. RTT should be the
 * average RTT estimate for the path measured over the previous congestion
 * epoch and wmax is the value of cwnd at the last congestion event.
 */
static __inline uint32_t
tf_cwnd(hrtime_t nsecs_since_cong, hrtime_t rtt_nsecs, uint32_t wmax,
    uint32_t smss)
{

	/* Equation 4 of I-D. */
	return (((wmax * CUBIC_BETA) + (((THREE_X_PT2 * nsecs_since_cong *
	    smss) << CUBIC_SHIFT) / TWO_SUB_PT2 / rtt_nsecs)) >> CUBIC_SHIFT);
}

#endif /* _NETINET_CC_CUBIC_H_ */
/*
 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
 * All rights reserved.
 * Copyright (c) 2017 by Delphix. All rights reserved.
 *
 * This software was developed by Lawrence Stewart while studying at the Centre
 * for Advanced Internet Architectures, Swinburne University of Technology, made
 * possible in part by a grant from the Cisco University Research Program Fund
 * at Community Foundation Silicon Valley.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * $FreeBSD$
 */

/*
 * This software was first released in 2009 by Lawrence Stewart as part of the
 * NewTCP research project at Swinburne University of Technology's Centre for
 * Advanced Internet Architectures, Melbourne, Australia, which was made
 * possible in part by a grant from the Cisco University Research Program Fund
 * at Community Foundation Silicon Valley. More details are available at:
 *   http://caia.swin.edu.au/urp/newtcp/
 */

#ifndef _NETINET_CC_MODULE_H_
#define	_NETINET_CC_MODULE_H_

#define	CCV(ccv, what) (ccv)->ccvc.tcp->what
#define	CCSV(ccv, what) (ccv)->ccvc.tcp->tcp_tcps->what
#define	CCV_PROTO(ccv) (ccv)->ccvc.tcp

#define	CC_ABC(ccv) (ccv)->ccvc.tcp->tcp_tcps->tcps_abc
#define	CC_ABC_L_VAR(ccv) (ccv)->ccvc.tcp->tcp_tcps->tcps_abc_l_var

#define	TCPTV_SRTTBASE 0

#endif /* _NETINET_CC_MODULE_H_ */
/*
 * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
 *	The Regents of the University of California.
 * Copyright (c) 2007-2008,2010
 *	Swinburne University of Technology, Melbourne, Australia.
 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
 * Copyright (c) 2010 The FreeBSD Foundation
 * All rights reserved.
 * Copyright (c) 2017 by Delphix. All rights reserved.
 * Copyright 2020 RackTop Systems, Inc.
 *
 * This software was developed at the Centre for Advanced Internet
 * Architectures, Swinburne University of Technology, by Lawrence Stewart, James
 * Healy and David Hayes, made possible in part by a grant from the Cisco
 * University Research Program Fund at Community Foundation Silicon Valley.
 *
 * Portions of this software were developed at the Centre for Advanced
 * Internet Architectures, Swinburne University of Technology, Melbourne,
 * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * This software was first released in 2007 by James Healy and Lawrence Stewart
 * whilst working on the NewTCP research project at Swinburne University of
 * Technology's Centre for Advanced Internet Architectures, Melbourne,
 * Australia, which was made possible in part by a grant from the Cisco
 * University Research Program Fund at Community Foundation Silicon Valley.
 * More details are available at:
 *   http://caia.swin.edu.au/urp/newtcp/
 */

#include <sys/errno.h>
#include <inet/tcp.h>
#include <inet/tcp_impl.h>
#include <inet/cc.h>
#include <inet/cc/cc_module.h>

static void	newreno_ack_received(struct cc_var *ccv, uint16_t type);
static void	newreno_after_idle(struct cc_var *ccv);
static void	newreno_cong_signal(struct cc_var *ccv, uint32_t type);
static void	newreno_post_recovery(struct cc_var *ccv);

static struct modlmisc cc_newreno_modlmisc = {
	&mod_miscops,
	"New Reno Congestion Control"
};

static struct modlinkage cc_newreno_modlinkage = {
	MODREV_1,
	&cc_newreno_modlmisc,
	NULL
};

struct cc_algo newreno_cc_algo = {
	.name = "newreno",
	.ack_received = newreno_ack_received,
	.after_idle = newreno_after_idle,
	.cong_signal = newreno_cong_signal,
	.post_recovery = newreno_post_recovery,
};

int
_init(void)
{
	int err;

	if ((err = cc_register_algo(&newreno_cc_algo)) == 0) {
		if ((err = mod_install(&cc_newreno_modlinkage)) != 0)
			(void) cc_deregister_algo(&newreno_cc_algo);
	}
	return (err);
}

int
_fini(void)
{
	/* XXX Not unloadable for now */
	return (EBUSY);
}

int
_info(struct modinfo *modinfop)
{
	return (mod_info(&cc_newreno_modlinkage, modinfop));
}

static void
newreno_ack_received(struct cc_var *ccv, uint16_t type)
{
	if (type == CC_ACK && !IN_RECOVERY(ccv->flags) &&
	    (ccv->flags & CCF_CWND_LIMITED)) {
		uint_t cw = CCV(ccv, tcp_cwnd);
		uint_t incr = CCV(ccv, tcp_mss);

		/*
		 * Regular in-order ACK, open the congestion window.
		 * Method depends on which congestion control state we're
		 * in (slow start or cong avoid) and if ABC (RFC 3465) is
		 * enabled.
		 *
		 * slow start: cwnd <= ssthresh
		 * cong avoid: cwnd > ssthresh
		 *
		 * slow start and ABC (RFC 3465):
		 *   Grow cwnd exponentially by the amount of data
		 *   ACKed capping the max increment per ACK to
		 *   (abc_l_var * maxseg) bytes.
		 *
		 * slow start without ABC (RFC 5681):
		 *   Grow cwnd exponentially by maxseg per ACK.
		 *
		 * cong avoid and ABC (RFC 3465):
		 *   Grow cwnd linearly by maxseg per RTT for each
		 *   cwnd worth of ACKed data.
		 *
		 * cong avoid without ABC (RFC 5681):
		 *   Grow cwnd linearly by approximately maxseg per RTT using
		 *   maxseg^2 / cwnd per ACK as the increment.
		 *   If cwnd > maxseg^2, fix the cwnd increment at 1 byte to
		 *   avoid capping cwnd.
		 */
		if (cw > CCV(ccv, tcp_cwnd_ssthresh)) {
			if (CC_ABC(ccv)) {
				if (ccv->flags & CCF_ABC_SENTAWND)
					ccv->flags &= ~CCF_ABC_SENTAWND;
				else
					incr = 0;
			} else
				incr = max((incr * incr / cw), 1);
		} else if (CC_ABC(ccv)) {
			/*
			 * In slow-start with ABC enabled and no RTO in sight?
			 * (Must not use abc_l_var > 1 if slow starting after
			 * an RTO.
			 */
			if (ccv->flags & CCF_RTO) {
				incr = min(ccv->bytes_this_ack,
				    CCV(ccv, tcp_mss));
			} else {
				incr = min(ccv->bytes_this_ack,
				    CC_ABC_L_VAR(ccv) * CCV(ccv, tcp_mss));
			}

		}
		/* ABC is on by default, so incr equals 0 frequently. */
		if (incr > 0)
			CCV(ccv, tcp_cwnd) = min(cw + incr,
			    TCP_MAXWIN << CCV(ccv, tcp_snd_ws));
	}
}

static void
newreno_after_idle(struct cc_var *ccv)
{
	int rw;

	/*
	 * If we've been idle for more than one retransmit timeout the old
	 * congestion window is no longer current and we have to reduce it to
	 * the restart window before we can transmit again.
	 *
	 * The restart window is the initial window or the last CWND, whichever
	 * is smaller.
	 *
	 * This is done to prevent us from flooding the path with a full CWND at
	 * wirespeed, overloading router and switch buffers along the way.
	 *
	 * See RFC5681 Section 4.1. "Restarting Idle Connections".
	 */
	if (CCV(ccv, tcp_init_cwnd) != 0) {
		/*
		 * The TCP_INIT_CWND socket option was used to override the
		 * default.
		 */
		rw = CCV(ccv, tcp_init_cwnd) * CCV(ccv, tcp_mss);
	} else if (CCSV(ccv, tcps_slow_start_initial) != 0) {
		/* The _slow_start_initial tunable was explicitly set. */
		rw = min(TCP_MAX_INIT_CWND, CCSV(ccv, tcps_slow_start_initial))
		    * CCV(ccv, tcp_mss);
	} else {
		/* Do RFC 3390 */
		rw = min(4 * CCV(ccv, tcp_mss),
		    max(2 * CCV(ccv, tcp_mss), 4380));
	}

	CCV(ccv, tcp_cwnd) = min(rw, CCV(ccv, tcp_cwnd));
}

/*
 * Perform any necessary tasks before we enter congestion recovery.
 */
static void
newreno_cong_signal(struct cc_var *ccv, uint32_t type)
{
	uint32_t cwin, ssthresh_on_loss;
	uint32_t mss;

	cwin = CCV(ccv, tcp_cwnd);
	mss = CCV(ccv, tcp_mss);
	ssthresh_on_loss =
	    max((CCV(ccv, tcp_snxt) - CCV(ccv, tcp_suna)) / 2 / mss, 2)
	    * mss;

	/* Catch algos which mistakenly leak private signal types. */
	ASSERT((type & CC_SIGPRIVMASK) == 0);

	cwin = max(cwin / 2 / mss, 2) * mss;

	switch (type) {
	case CC_NDUPACK:
		if (!IN_FASTRECOVERY(ccv->flags)) {
			if (!IN_CONGRECOVERY(ccv->flags)) {
				CCV(ccv, tcp_cwnd_ssthresh) = ssthresh_on_loss;
				CCV(ccv, tcp_cwnd) = cwin;
			}
			ENTER_RECOVERY(ccv->flags);
		}
		break;
	case CC_ECN:
		if (!IN_CONGRECOVERY(ccv->flags)) {
			CCV(ccv, tcp_cwnd_ssthresh) = ssthresh_on_loss;
			CCV(ccv, tcp_cwnd) = cwin;
			ENTER_CONGRECOVERY(ccv->flags);
		}
		break;
	case CC_RTO:
		CCV(ccv, tcp_cwnd_ssthresh) = ssthresh_on_loss;
		CCV(ccv, tcp_cwnd) = mss;
		break;
	}
}

/*
 * Perform any necessary tasks before we exit congestion recovery.
 */
static void
newreno_post_recovery(struct cc_var *ccv)
{
	uint32_t pipe;

	if (IN_FASTRECOVERY(ccv->flags)) {
		/*
		 * Fast recovery will conclude after returning from this
		 * function. Window inflation should have left us with
		 * approximately cwnd_ssthresh outstanding data. But in case we
		 * would be inclined to send a burst, better to do it via the
		 * slow start mechanism.
		 */
		pipe = CCV(ccv, tcp_snxt) - CCV(ccv, tcp_suna);
		if (pipe < CCV(ccv, tcp_cwnd_ssthresh)) {
			/*
			 * Ensure that cwnd does not collapse to 1 MSS under
			 * adverse conditions. Implements RFC6582
			 */
			CCV(ccv, tcp_cwnd) = MAX(pipe, CCV(ccv, tcp_mss)) +
			    CCV(ccv, tcp_mss);
		} else if (CCV(ccv, tcp_cwnd) > CCV(ccv, tcp_cwnd_ssthresh)) {
			CCV(ccv, tcp_cwnd) = CCV(ccv, tcp_cwnd_ssthresh);
		}
	}
}
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright (c) 2017 by Delphix. All rights reserved.
 */

/*
 * The TCP congestion control algorithm extracted from the pre-framework
 * implementation of TCP congestion control.
 */

#include <sys/errno.h>
#include <inet/tcp.h>
#include <inet/tcp_impl.h>
#include <inet/cc.h>
#include <inet/cc/cc_module.h>

static void	sunreno_ack_received(struct cc_var *ccv, uint16_t type);
static void	sunreno_after_idle(struct cc_var *ccv);
static void	sunreno_cong_signal(struct cc_var *ccv, uint32_t type);
static void	sunreno_post_recovery(struct cc_var *ccv);

#define	CC_SUNRENO_ALGO_NAME "sunreno"

static struct modlmisc cc_sunreno_modlmisc = {
	&mod_miscops,
	"SUNReno Congestion Control"
};

static struct modlinkage cc_sunreno_modlinkage = {
	MODREV_1,
	&cc_sunreno_modlmisc,
	NULL
};

struct cc_algo sunreno_cc_algo = {
	.name = CC_SUNRENO_ALGO_NAME,
	.ack_received = sunreno_ack_received,
	.after_idle = sunreno_after_idle,
	.cong_signal = sunreno_cong_signal,
	.post_recovery = sunreno_post_recovery,
};

int
_init(void)
{
	int err;

	if ((err = cc_register_algo(&sunreno_cc_algo)) == 0) {
		if ((err = mod_install(&cc_sunreno_modlinkage)) != 0)
			(void) cc_deregister_algo(&sunreno_cc_algo);
	}
	return (err);
}

int
_fini(void)
{
	return (EBUSY);
}

int
_info(struct modinfo *modinfop)
{
	return (mod_info(&cc_sunreno_modlinkage, modinfop));
}

static void
sunreno_ack_received(struct cc_var *ccv, uint16_t type)
{
	uint32_t add;
	uint32_t cwnd;
	int mss;

	if (type == CC_ACK && !IN_RECOVERY(ccv->flags)) {
		mss = CCV(ccv, tcp_mss);
		cwnd = CCV(ccv, tcp_cwnd);
		add = mss;

		if (cwnd >= CCV(ccv, tcp_cwnd_ssthresh)) {
			/*
			 * This is to prevent an increase of less than 1 MSS of
			 * tcp_cwnd.  With partial increase, tcp_wput_data()
			 * may send out tinygrams in order to preserve mblk
			 * boundaries.
			 *
			 * By initializing tcp_cwnd_cnt to new tcp_cwnd and
			 * decrementing it by 1 MSS for every ACKs, tcp_cwnd is
			 * increased by 1 MSS for every RTTs.
			 */
			if (CCV(ccv, tcp_cwnd_cnt) <= 0) {
				CCV(ccv, tcp_cwnd_cnt) = cwnd + add;
			} else {
				CCV(ccv, tcp_cwnd_cnt) -= add;
				add = 0;
			}
		}
		CCV(ccv, tcp_cwnd) = MIN(cwnd + add, CCV(ccv, tcp_cwnd_max));
	}
}

static void
sunreno_after_idle(struct cc_var *ccv)
{
	int32_t	num_sack_blk = 0;
	int mss;

	if (CCV(ccv, tcp_snd_sack_ok) && CCV(ccv, tcp_num_sack_blk) > 0) {
		int32_t	opt_len;

		num_sack_blk = MIN(CCV(ccv, tcp_max_sack_blk),
		    CCV(ccv, tcp_num_sack_blk));
		opt_len = num_sack_blk * sizeof (sack_blk_t) + TCPOPT_NOP_LEN *
		    2 + TCPOPT_HEADER_LEN;
		mss = CCV(ccv, tcp_mss) - opt_len;
	} else {
		mss = CCV(ccv, tcp_mss);
	}

	TCP_SET_INIT_CWND(CCV_PROTO(ccv), mss,
	    CCSV(ccv, tcps_slow_start_after_idle));
}

/*
 * Perform any necessary tasks before we enter congestion recovery.
 */
static void
sunreno_cong_signal(struct cc_var *ccv, uint32_t type)
{
	int npkt;
	int mss;

	/* Catch algos which mistakenly leak private signal types. */
	ASSERT((type & CC_SIGPRIVMASK) == 0);

	mss = CCV(ccv, tcp_mss);
	npkt = ((CCV(ccv, tcp_snxt) - CCV(ccv, tcp_suna)) >> 1) / mss;

	switch (type) {
	case CC_NDUPACK:
		if (!IN_FASTRECOVERY(ccv->flags)) {
			if (!IN_CONGRECOVERY(ccv->flags)) {
				CCV(ccv, tcp_cwnd_ssthresh) = MAX(npkt, 2) *
				    mss;
				CCV(ccv, tcp_cwnd) = (npkt +
				    CCV(ccv, tcp_dupack_cnt)) * mss;
			}
			ENTER_RECOVERY(ccv->flags);
		}
		break;
	case CC_ECN:
		if (!IN_CONGRECOVERY(ccv->flags) && !CCV(ccv, tcp_cwr)) {
			CCV(ccv, tcp_cwnd_ssthresh) = MAX(npkt, 2) * mss;
			CCV(ccv, tcp_cwnd) = npkt * mss;
			if (CCV(ccv, tcp_cwnd) == 0) {
				/*
				 * This makes sure that when the ACK comes
				 * back, we will increase tcp_cwnd by 1 MSS.
				 */
				CCV(ccv, tcp_cwnd_cnt) = 0;
			}
			ENTER_CONGRECOVERY(ccv->flags);
		}
		break;
	case CC_RTO:
		/*
		 * After retransmission, we need to do slow start.  Set the
		 * ssthresh to one half of current effective window and cwnd to
		 * one MSS.  Also reset tcp_cwnd_cnt.
		 *
		 * Note that if tcp_ssthresh is reduced because of ECN, do not
		 * reduce it again unless it is already one window of data away
		 * (tcp_cwr should then be cleared) or this is a timeout for a
		 * retransmitted segment.
		 */
		if (!CCV(ccv, tcp_cwr) || CCV(ccv, tcp_rexmit)) {
			if (CCV(ccv, tcp_timer_backoff) != 0)
				npkt = CCV(ccv, tcp_cwnd_ssthresh) / 2 / mss;
			CCV(ccv, tcp_cwnd_ssthresh) = MAX(npkt, 2) * mss;
		}
		CCV(ccv, tcp_cwnd) = mss;
		CCV(ccv, tcp_cwnd_cnt) = 0;
		break;
	}
}

/*
 * Perform any necessary tasks before we exit congestion recovery.
 */
static void
sunreno_post_recovery(struct cc_var *ccv)
{
	/*
	 * Restore the congestion window back to ssthresh as per RFC 5681
	 * section 3.2.
	 */
	if (IN_FASTRECOVERY(ccv->flags)) {
		if (CCV(ccv, tcp_cwnd) > CCV(ccv, tcp_cwnd_ssthresh)) {
			CCV(ccv, tcp_cwnd) = CCV(ccv, tcp_cwnd_ssthresh);
		}
	}
	CCV(ccv, tcp_cwnd_cnt) = 0;
}