xref: /freebsd/sys/netinet/cc/cc_newreno.c (revision a25896ca1270e25b657ceaa8d47d5699515f5c25)
1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3  *
4  * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
5  *	The Regents of the University of California.
6  * Copyright (c) 2007-2008,2010,2014
7  *	Swinburne University of Technology, Melbourne, Australia.
8  * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
9  * Copyright (c) 2010 The FreeBSD Foundation
10  * All rights reserved.
11  *
12  * This software was developed at the Centre for Advanced Internet
13  * Architectures, Swinburne University of Technology, by Lawrence Stewart, James
14  * Healy and David Hayes, made possible in part by a grant from the Cisco
15  * University Research Program Fund at Community Foundation Silicon Valley.
16  *
17  * Portions of this software were developed at the Centre for Advanced
18  * Internet Architectures, Swinburne University of Technology, Melbourne,
19  * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
20  *
21  * Redistribution and use in source and binary forms, with or without
22  * modification, are permitted provided that the following conditions
23  * are met:
24  * 1. Redistributions of source code must retain the above copyright
25  *    notice, this list of conditions and the following disclaimer.
26  * 2. Redistributions in binary form must reproduce the above copyright
27  *    notice, this list of conditions and the following disclaimer in the
28  *    documentation and/or other materials provided with the distribution.
29  *
30  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
31  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
34  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40  * SUCH DAMAGE.
41  */
42 
43 /*
44  * This software was first released in 2007 by James Healy and Lawrence Stewart
45  * whilst working on the NewTCP research project at Swinburne University of
46  * Technology's Centre for Advanced Internet Architectures, Melbourne,
47  * Australia, which was made possible in part by a grant from the Cisco
48  * University Research Program Fund at Community Foundation Silicon Valley.
49  * More details are available at:
50  *   http://caia.swin.edu.au/urp/newtcp/
51  *
52  * Dec 2014 garmitage@swin.edu.au
53  * Borrowed code fragments from cc_cdg.c to add modifiable beta
54  * via sysctls.
55  *
56  */
57 
58 #include <sys/cdefs.h>
59 __FBSDID("$FreeBSD$");
60 
61 #include <sys/param.h>
62 #include <sys/kernel.h>
63 #include <sys/malloc.h>
64 #include <sys/module.h>
65 #include <sys/socket.h>
66 #include <sys/socketvar.h>
67 #include <sys/sysctl.h>
68 #include <sys/systm.h>
69 
70 #include <net/vnet.h>
71 
72 #include <netinet/tcp.h>
73 #include <netinet/tcp_seq.h>
74 #include <netinet/tcp_var.h>
75 #include <netinet/cc/cc.h>
76 #include <netinet/cc/cc_module.h>
77 #include <netinet/cc/cc_newreno.h>
78 
79 static MALLOC_DEFINE(M_NEWRENO, "newreno data",
80 	"newreno beta values");
81 
82 #define	CAST_PTR_INT(X) (*((int*)(X)))
83 
84 static void	newreno_cb_destroy(struct cc_var *ccv);
85 static void	newreno_ack_received(struct cc_var *ccv, uint16_t type);
86 static void	newreno_after_idle(struct cc_var *ccv);
87 static void	newreno_cong_signal(struct cc_var *ccv, uint32_t type);
88 static void	newreno_post_recovery(struct cc_var *ccv);
89 static int newreno_ctl_output(struct cc_var *ccv, struct sockopt *sopt, void *buf);
90 
91 VNET_DEFINE_STATIC(uint32_t, newreno_beta) = 50;
92 VNET_DEFINE_STATIC(uint32_t, newreno_beta_ecn) = 80;
93 #define V_newreno_beta VNET(newreno_beta)
94 #define V_newreno_beta_ecn VNET(newreno_beta_ecn)
95 
96 struct cc_algo newreno_cc_algo = {
97 	.name = "newreno",
98 	.cb_destroy = newreno_cb_destroy,
99 	.ack_received = newreno_ack_received,
100 	.after_idle = newreno_after_idle,
101 	.cong_signal = newreno_cong_signal,
102 	.post_recovery = newreno_post_recovery,
103 	.ctl_output = newreno_ctl_output,
104 };
105 
106 struct newreno {
107 	uint32_t beta;
108 	uint32_t beta_ecn;
109 };
110 
111 static inline struct newreno *
112 newreno_malloc(struct cc_var *ccv)
113 {
114 	struct newreno *nreno;
115 
116 	nreno = malloc(sizeof(struct newreno), M_NEWRENO, M_NOWAIT);
117 	if (nreno != NULL) {
118 		/* NB: nreno is not zeroed, so initialise all fields. */
119 		nreno->beta = V_newreno_beta;
120 		nreno->beta_ecn = V_newreno_beta_ecn;
121 		ccv->cc_data = nreno;
122 	}
123 
124 	return (nreno);
125 }
126 
127 static void
128 newreno_cb_destroy(struct cc_var *ccv)
129 {
130 	free(ccv->cc_data, M_NEWRENO);
131 }
132 
133 static void
134 newreno_ack_received(struct cc_var *ccv, uint16_t type)
135 {
136 	if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) &&
137 	    (ccv->flags & CCF_CWND_LIMITED)) {
138 		u_int cw = CCV(ccv, snd_cwnd);
139 		u_int incr = CCV(ccv, t_maxseg);
140 
141 		/*
142 		 * Regular in-order ACK, open the congestion window.
143 		 * Method depends on which congestion control state we're
144 		 * in (slow start or cong avoid) and if ABC (RFC 3465) is
145 		 * enabled.
146 		 *
147 		 * slow start: cwnd <= ssthresh
148 		 * cong avoid: cwnd > ssthresh
149 		 *
150 		 * slow start and ABC (RFC 3465):
151 		 *   Grow cwnd exponentially by the amount of data
152 		 *   ACKed capping the max increment per ACK to
153 		 *   (abc_l_var * maxseg) bytes.
154 		 *
155 		 * slow start without ABC (RFC 5681):
156 		 *   Grow cwnd exponentially by maxseg per ACK.
157 		 *
158 		 * cong avoid and ABC (RFC 3465):
159 		 *   Grow cwnd linearly by maxseg per RTT for each
160 		 *   cwnd worth of ACKed data.
161 		 *
162 		 * cong avoid without ABC (RFC 5681):
163 		 *   Grow cwnd linearly by approximately maxseg per RTT using
164 		 *   maxseg^2 / cwnd per ACK as the increment.
165 		 *   If cwnd > maxseg^2, fix the cwnd increment at 1 byte to
166 		 *   avoid capping cwnd.
167 		 */
168 		if (cw > CCV(ccv, snd_ssthresh)) {
169 			if (V_tcp_do_rfc3465) {
170 				if (ccv->flags & CCF_ABC_SENTAWND)
171 					ccv->flags &= ~CCF_ABC_SENTAWND;
172 				else
173 					incr = 0;
174 			} else
175 				incr = max((incr * incr / cw), 1);
176 		} else if (V_tcp_do_rfc3465) {
177 			/*
178 			 * In slow-start with ABC enabled and no RTO in sight?
179 			 * (Must not use abc_l_var > 1 if slow starting after
180 			 * an RTO. On RTO, snd_nxt = snd_una, so the
181 			 * snd_nxt == snd_max check is sufficient to
182 			 * handle this).
183 			 *
184 			 * XXXLAS: Find a way to signal SS after RTO that
185 			 * doesn't rely on tcpcb vars.
186 			 */
187 			if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max))
188 				incr = min(ccv->bytes_this_ack,
189 				    ccv->nsegs * V_tcp_abc_l_var *
190 				    CCV(ccv, t_maxseg));
191 			else
192 				incr = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
193 		}
194 		/* ABC is on by default, so incr equals 0 frequently. */
195 		if (incr > 0)
196 			CCV(ccv, snd_cwnd) = min(cw + incr,
197 			    TCP_MAXWIN << CCV(ccv, snd_scale));
198 	}
199 }
200 
201 static void
202 newreno_after_idle(struct cc_var *ccv)
203 {
204 	int rw;
205 
206 	/*
207 	 * If we've been idle for more than one retransmit timeout the old
208 	 * congestion window is no longer current and we have to reduce it to
209 	 * the restart window before we can transmit again.
210 	 *
211 	 * The restart window is the initial window or the last CWND, whichever
212 	 * is smaller.
213 	 *
214 	 * This is done to prevent us from flooding the path with a full CWND at
215 	 * wirespeed, overloading router and switch buffers along the way.
216 	 *
217 	 * See RFC5681 Section 4.1. "Restarting Idle Connections".
218 	 */
219 	if (V_tcp_do_rfc3390)
220 		rw = min(4 * CCV(ccv, t_maxseg),
221 		    max(2 * CCV(ccv, t_maxseg), 4380));
222 	else
223 		rw = CCV(ccv, t_maxseg) * 2;
224 
225 	CCV(ccv, snd_cwnd) = min(rw, CCV(ccv, snd_cwnd));
226 }
227 
228 /*
229  * Perform any necessary tasks before we enter congestion recovery.
230  */
231 static void
232 newreno_cong_signal(struct cc_var *ccv, uint32_t type)
233 {
234 	struct newreno *nreno;
235 	uint32_t beta, beta_ecn, cwin, factor;
236 	u_int mss;
237 
238 	cwin = CCV(ccv, snd_cwnd);
239 	mss = CCV(ccv, t_maxseg);
240 	nreno = ccv->cc_data;
241 	beta = (nreno == NULL) ? V_newreno_beta : nreno->beta;
242 	beta_ecn = (nreno == NULL) ? V_newreno_beta_ecn : nreno->beta_ecn;
243 	if (V_cc_do_abe && type == CC_ECN)
244 		factor = beta_ecn;
245 	else
246 		factor = beta;
247 
248 	/* Catch algos which mistakenly leak private signal types. */
249 	KASSERT((type & CC_SIGPRIVMASK) == 0,
250 	    ("%s: congestion signal type 0x%08x is private\n", __func__, type));
251 
252 	cwin = max(((uint64_t)cwin * (uint64_t)factor) / (100ULL * (uint64_t)mss),
253 	    2) * mss;
254 
255 	switch (type) {
256 	case CC_NDUPACK:
257 		if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
258 			if (IN_CONGRECOVERY(CCV(ccv, t_flags) &&
259 			    V_cc_do_abe && V_cc_abe_frlossreduce)) {
260 				CCV(ccv, snd_ssthresh) =
261 				    ((uint64_t)CCV(ccv, snd_ssthresh) *
262 				    (uint64_t)beta) /
263 				    (100ULL * (uint64_t)beta_ecn);
264 			}
265 			if (!IN_CONGRECOVERY(CCV(ccv, t_flags)))
266 				CCV(ccv, snd_ssthresh) = cwin;
267 			ENTER_RECOVERY(CCV(ccv, t_flags));
268 		}
269 		break;
270 	case CC_ECN:
271 		if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
272 			CCV(ccv, snd_ssthresh) = cwin;
273 			CCV(ccv, snd_cwnd) = cwin;
274 			ENTER_CONGRECOVERY(CCV(ccv, t_flags));
275 		}
276 		break;
277 	}
278 }
279 
280 /*
281  * Perform any necessary tasks before we exit congestion recovery.
282  */
283 static void
284 newreno_post_recovery(struct cc_var *ccv)
285 {
286 	int pipe;
287 
288 	if (IN_FASTRECOVERY(CCV(ccv, t_flags))) {
289 		/*
290 		 * Fast recovery will conclude after returning from this
291 		 * function. Window inflation should have left us with
292 		 * approximately snd_ssthresh outstanding data. But in case we
293 		 * would be inclined to send a burst, better to do it via the
294 		 * slow start mechanism.
295 		 *
296 		 * XXXLAS: Find a way to do this without needing curack
297 		 */
298 		if (V_tcp_do_rfc6675_pipe)
299 			pipe = tcp_compute_pipe(ccv->ccvc.tcp);
300 		else
301 			pipe = CCV(ccv, snd_max) - ccv->curack;
302 
303 		if (pipe < CCV(ccv, snd_ssthresh))
304 			CCV(ccv, snd_cwnd) = pipe + CCV(ccv, t_maxseg);
305 		else
306 			CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
307 	}
308 }
309 
310 static int
311 newreno_ctl_output(struct cc_var *ccv, struct sockopt *sopt, void *buf)
312 {
313 	struct newreno *nreno;
314 	struct cc_newreno_opts *opt;
315 
316 	if (sopt->sopt_valsize != sizeof(struct cc_newreno_opts))
317 		return (EMSGSIZE);
318 
319 	nreno = ccv->cc_data;
320 	opt = buf;
321 
322 	switch (sopt->sopt_dir) {
323 	case SOPT_SET:
324 		/* We cannot set without cc_data memory. */
325 		if (nreno == NULL) {
326 			nreno = newreno_malloc(ccv);
327 			if (nreno == NULL)
328 				return (ENOMEM);
329 		}
330 		switch (opt->name) {
331 		case CC_NEWRENO_BETA:
332 			nreno->beta = opt->val;
333 			break;
334 		case CC_NEWRENO_BETA_ECN:
335 			if (!V_cc_do_abe)
336 				return (EACCES);
337 			nreno->beta_ecn = opt->val;
338 			break;
339 		default:
340 			return (ENOPROTOOPT);
341 		}
342 		break;
343 	case SOPT_GET:
344 		switch (opt->name) {
345 		case CC_NEWRENO_BETA:
346 			opt->val = (nreno == NULL) ?
347 			    V_newreno_beta : nreno->beta;
348 			break;
349 		case CC_NEWRENO_BETA_ECN:
350 			opt->val = (nreno == NULL) ?
351 			    V_newreno_beta_ecn : nreno->beta_ecn;
352 			break;
353 		default:
354 			return (ENOPROTOOPT);
355 		}
356 		break;
357 	default:
358 		return (EINVAL);
359 	}
360 
361 	return (0);
362 }
363 
364 static int
365 newreno_beta_handler(SYSCTL_HANDLER_ARGS)
366 {
367 
368 	if (req->newptr != NULL ) {
369 		if (arg1 == &VNET_NAME(newreno_beta_ecn) && !V_cc_do_abe)
370 			return (EACCES);
371 		if (CAST_PTR_INT(req->newptr) <= 0 || CAST_PTR_INT(req->newptr) > 100)
372 			return (EINVAL);
373 	}
374 
375 	return (sysctl_handle_int(oidp, arg1, arg2, req));
376 }
377 
378 SYSCTL_DECL(_net_inet_tcp_cc_newreno);
379 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, newreno, CTLFLAG_RW, NULL,
380     "New Reno related settings");
381 
382 SYSCTL_PROC(_net_inet_tcp_cc_newreno, OID_AUTO, beta,
383 	CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
384 	&VNET_NAME(newreno_beta), 3, &newreno_beta_handler, "IU",
385 	"New Reno beta, specified as number between 1 and 100");
386 
387 SYSCTL_PROC(_net_inet_tcp_cc_newreno, OID_AUTO, beta_ecn,
388 	CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
389 	&VNET_NAME(newreno_beta_ecn), 3, &newreno_beta_handler, "IU",
390 	"New Reno beta ecn, specified as number between 1 and 100");
391 
392 DECLARE_CC_MODULE(newreno, &newreno_cc_algo);
393