/* * TCP Low Priority (TCP-LP) * * TCP Low Priority is a distributed algorithm whose goal is to utilize only *   the excess network bandwidth as compared to the ``fair share`` of *   bandwidth as targeted by TCP. * * As of 2.6.13, Linux supports pluggable congestion control algorithms. * Due to the limitation of the API, we take the following changes from * the original TCP-LP implementation: *   o We use newReno in most core CA handling. Only add some checking *     within cong_avoid. *   o Error correcting in remote HZ, therefore remote HZ will be keeped *     on checking and updating. *   o Handling calculation of One-Way-Delay (OWD) within rtt_sample, sicne *     OWD have a similar meaning as RTT. Also correct the buggy formular. *   o Handle reaction for Early Congestion Indication (ECI) within *     pkts_acked, as mentioned within pseudo code. *   o OWD is handled in relative format, where local time stamp will in *     tcp_time_stamp format. * * Original Author: *   Aleksandar Kuzmanovic <akuzma@northwestern.edu> * Available from: *   http://www.ece.rice.edu/~akuzma/Doc/akuzma/TCP-LP.pdf * Original implementation for 2.4.19: *   http://www-ece.rice.edu/networks/TCP-LP/ * * 2.6.x module Authors: *   Wong Hoi Sing, Edison <hswong3i@gmail.com> *   Hung Hing Lun, Mike <hlhung3i@gmail.com> * SourceForge project page: *   http://tcp-lp-mod.sourceforge.net/ */#include <linux/module.h>#include <net/tcp.h>/* resolution of owd */#define LP_RESOL       1000/** * enum tcp_lp_state * @LP_VALID_RHZ: is remote HZ valid? * @LP_VALID_OWD: is OWD valid? * @LP_WITHIN_THR: are we within threshold? * @LP_WITHIN_INF: are we within inference? * * TCP-LP's state flags. * We create this set of state flag mainly for debugging. */enum tcp_lp_state {	LP_VALID_RHZ = (1 << 0),	LP_VALID_OWD = (1 << 1),	LP_WITHIN_THR = (1 << 3),	LP_WITHIN_INF = (1 << 4),};/** * struct lp * @flag: TCP-LP state flag * @sowd: smoothed OWD << 3 * @owd_min: min OWD * @owd_max: max OWD * @owd_max_rsv: resrved max owd * @remote_hz: estimated remote HZ * @remote_ref_time: remote reference time * @local_ref_time: local reference time * @last_drop: time for last active drop * @inference: current inference * * TCP-LP's private struct. * We get the idea from original TCP-LP implementation where only left those we * found are really useful. */struct lp {	u32 flag;	u32 sowd;	u32 owd_min;	u32 owd_max;	u32 owd_max_rsv;	u32 remote_hz;	u32 remote_ref_time;	u32 local_ref_time;	u32 last_drop;	u32 inference;};/** * tcp_lp_init * * Init all required variables. * Clone the handling from Vegas module implementation. */static void tcp_lp_init(struct sock *sk){	struct lp *lp = inet_csk_ca(sk);	lp->flag = 0;	lp->sowd = 0;	lp->owd_min = 0xffffffff;	lp->owd_max = 0;	lp->owd_max_rsv = 0;	lp->remote_hz = 0;	lp->remote_ref_time = 0;	lp->local_ref_time = 0;	lp->last_drop = 0;	lp->inference = 0;}/** * tcp_lp_cong_avoid * * Implementation of cong_avoid. * Will only call newReno CA when away from inference. * From TCP-LP's paper, this will be handled in additive increasement. */static void tcp_lp_cong_avoid(struct sock *sk, u32 ack, u32 in_flight, int flag){	struct lp *lp = inet_csk_ca(sk);	if (!(lp->flag & LP_WITHIN_INF))		tcp_reno_cong_avoid(sk, ack, in_flight, flag);}/** * tcp_lp_remote_hz_estimator * * Estimate remote HZ. * We keep on updating the estimated value, where original TCP-LP * implementation only guest it for once and use forever. */static u32 tcp_lp_remote_hz_estimator(struct sock *sk){	struct tcp_sock *tp = tcp_sk(sk);	struct lp *lp = inet_csk_ca(sk);	s64 rhz = lp->remote_hz << 6;	/* remote HZ << 6 */	s64 m = 0;	/* not yet record reference time	 * go away!! record it before come back!! */	if (lp->remote_ref_time == 0 || lp->local_ref_time == 0)		goto out;	/* we can't calc remote HZ with no different!! */	if (tp->rx_opt.rcv_tsval == lp->remote_ref_time	    || tp->rx_opt.rcv_tsecr == lp->local_ref_time)		goto out;	m = HZ * (tp->rx_opt.rcv_tsval -		  lp->remote_ref_time) / (tp->rx_opt.rcv_tsecr -					  lp->local_ref_time);	if (m < 0)		m = -m;	if (rhz > 0) {		m -= rhz >> 6;	/* m is now error in remote HZ est */		rhz += m;	/* 63/64 old + 1/64 new */	} else		rhz = m << 6; out:	/* record time for successful remote HZ calc */	if ((rhz >> 6) > 0)		lp->flag |= LP_VALID_RHZ;	else		lp->flag &= ~LP_VALID_RHZ;	/* record reference time stamp */	lp->remote_ref_time = tp->rx_opt.rcv_tsval;	lp->local_ref_time = tp->rx_opt.rcv_tsecr;	return rhz >> 6;}/** * tcp_lp_owd_calculator * * Calculate one way delay (in relative format). * Original implement OWD as minus of remote time difference to local time * difference directly. As this time difference just simply equal to RTT, when * the network status is stable, remote RTT will equal to local RTT, and result * OWD into zero. * It seems to be a bug and so we fixed it. */static u32 tcp_lp_owd_calculator(struct sock *sk){	struct tcp_sock *tp = tcp_sk(sk);	struct lp *lp = inet_csk_ca(sk);	s64 owd = 0;	lp->remote_hz = tcp_lp_remote_hz_estimator(sk);	if (lp->flag & LP_VALID_RHZ) {		owd =		    tp->rx_opt.rcv_tsval * (LP_RESOL / lp->remote_hz) -		    tp->rx_opt.rcv_tsecr * (LP_RESOL / HZ);		if (owd < 0)			owd = -owd;	}	if (owd > 0)		lp->flag |= LP_VALID_OWD;	else		lp->flag &= ~LP_VALID_OWD;	return owd;}/** * tcp_lp_rtt_sample * * Implementation or rtt_sample. * Will take the following action, *   1. calc OWD, *   2. record the min/max OWD, *   3. calc smoothed OWD (SOWD). * Most ideas come from the original TCP-LP implementation. */static void tcp_lp_rtt_sample(struct sock *sk, u32 rtt){	struct lp *lp = inet_csk_ca(sk);	s64 mowd = tcp_lp_owd_calculator(sk);	/* sorry that we don't have valid data */	if (!(lp->flag & LP_VALID_RHZ) || !(lp->flag & LP_VALID_OWD))		return;	/* record the next min owd */	if (mowd < lp->owd_min)		lp->owd_min = mowd;	/* always forget the max of the max	 * we just set owd_max as one below it */	if (mowd > lp->owd_max) {		if (mowd > lp->owd_max_rsv) {			if (lp->owd_max_rsv == 0)				lp->owd_max = mowd;			else				lp->owd_max = lp->owd_max_rsv;			lp->owd_max_rsv = mowd;		} else			lp->owd_max = mowd;	}	/* calc for smoothed owd */	if (lp->sowd != 0) {		mowd -= lp->sowd >> 3;	/* m is now error in owd est */		lp->sowd += mowd;	/* owd = 7/8 owd + 1/8 new */	} else		lp->sowd = mowd << 3;	/* take the measured time be owd */}/** * tcp_lp_pkts_acked * * Implementation of pkts_acked. * Deal with active drop under Early Congestion Indication. * Only drop to half and 1 will be handle, because we hope to use back * newReno in increase case. * We work it out by following the idea from TCP-LP's paper directly */static void tcp_lp_pkts_acked(struct sock *sk, u32 num_acked, s32 rtt_us){	struct tcp_sock *tp = tcp_sk(sk);	struct lp *lp = inet_csk_ca(sk);	if (rtt_us > 0)		tcp_lp_rtt_sample(sk, rtt_us);	/* calc inference */	if (tcp_time_stamp > tp->rx_opt.rcv_tsecr)		lp->inference = 3 * (tcp_time_stamp - tp->rx_opt.rcv_tsecr);	/* test if within inference */	if (lp->last_drop && (tcp_time_stamp - lp->last_drop < lp->inference))		lp->flag |= LP_WITHIN_INF;	else		lp->flag &= ~LP_WITHIN_INF;	/* test if within threshold */	if (lp->sowd >> 3 <	    lp->owd_min + 15 * (lp->owd_max - lp->owd_min) / 100)		lp->flag |= LP_WITHIN_THR;	else		lp->flag &= ~LP_WITHIN_THR;	pr_debug("TCP-LP: %05o|%5u|%5u|%15u|%15u|%15u\n", lp->flag,		 tp->snd_cwnd, lp->remote_hz, lp->owd_min, lp->owd_max,		 lp->sowd >> 3);	if (lp->flag & LP_WITHIN_THR)		return;	/* FIXME: try to reset owd_min and owd_max here	 * so decrease the chance the min/max is no longer suitable	 * and will usually within threshold when whithin inference */	lp->owd_min = lp->sowd >> 3;	lp->owd_max = lp->sowd >> 2;	lp->owd_max_rsv = lp->sowd >> 2;	/* happened within inference	 * drop snd_cwnd into 1 */	if (lp->flag & LP_WITHIN_INF)		tp->snd_cwnd = 1U;	/* happened after inference	 * cut snd_cwnd into half */	else		tp->snd_cwnd = max(tp->snd_cwnd >> 1U, 1U);	/* record this drop time */	lp->last_drop = tcp_time_stamp;}static struct tcp_congestion_ops tcp_lp = {	.flags = TCP_CONG_RTT_STAMP,	.init = tcp_lp_init,	.ssthresh = tcp_reno_ssthresh,	.cong_avoid = tcp_lp_cong_avoid,	.min_cwnd = tcp_reno_min_cwnd,	.pkts_acked = tcp_lp_pkts_acked,	.owner = THIS_MODULE,	.name = "lp"};static int __init tcp_lp_register(void){	BUILD_BUG_ON(sizeof(struct lp) > ICSK_CA_PRIV_SIZE);	return tcp_register_congestion_control(&tcp_lp);}static void __exit tcp_lp_unregister(void){	tcp_unregister_congestion_control(&tcp_lp);}module_init(tcp_lp_register);module_exit(tcp_lp_unregister);MODULE_AUTHOR("Wong Hoi Sing Edison, Hung Hing Lun Mike");MODULE_LICENSE("GPL");MODULE_DESCRIPTION("TCP Low Priority");