xref: /freebsd/sys/netinet/cc/cc_chd.c (revision 7ef62cebc2f965b0f640263e179276928885e33d)
1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause
3  *
4  * Copyright (c) 2009-2010
5  *	Swinburne University of Technology, Melbourne, Australia
6  * Copyright (c) 2010-2011 The FreeBSD Foundation
7  * All rights reserved.
8  *
9  * This software was developed at the Centre for Advanced Internet
10  * Architectures, Swinburne University of Technology, by David Hayes and
11  * Lawrence Stewart, made possible in part by a grant from the Cisco University
12  * Research Program Fund at Community Foundation Silicon Valley.
13  *
14  * Portions of this software were developed at the Centre for Advanced Internet
15  * Architectures, Swinburne University of Technology, Melbourne, Australia by
16  * David Hayes under sponsorship from the FreeBSD Foundation.
17  *
18  * Redistribution and use in source and binary forms, with or without
19  * modification, are permitted provided that the following conditions
20  * are met:
21  * 1. Redistributions of source code must retain the above copyright
22  *    notice, this list of conditions and the following disclaimer.
23  * 2. Redistributions in binary form must reproduce the above copyright
24  *    notice, this list of conditions and the following disclaimer in the
25  *    documentation and/or other materials provided with the distribution.
26  *
27  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37  * SUCH DAMAGE.
38  */
39 
40 /*
41  * An implementation of the CAIA-Hamilton delay based congestion control
42  * algorithm, based on "Improved coexistence and loss tolerance for delay based
43  * TCP congestion control" by D. A. Hayes and G. Armitage., in 35th Annual IEEE
44  * Conference on Local Computer Networks (LCN 2010), Denver, Colorado, USA,
45  * 11-14 October 2010.
46  *
47  * Originally released as part of the NewTCP research project at Swinburne
48  * University of Technology's Centre for Advanced Internet Architectures,
49  * Melbourne, Australia, which was made possible in part by a grant from the
50  * Cisco University Research Program Fund at Community Foundation Silicon
51  * Valley. More details are available at:
52  *   http://caia.swin.edu.au/urp/newtcp/
53  */
54 
55 #include <sys/cdefs.h>
56 __FBSDID("$FreeBSD$");
57 
58 #include <sys/param.h>
59 #include <sys/kernel.h>
60 #include <sys/khelp.h>
61 #include <sys/limits.h>
62 #include <sys/malloc.h>
63 #include <sys/module.h>
64 #include <sys/queue.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 <net/route.h>
73 #include <net/route/nhop.h>
74 
75 #include <netinet/in_pcb.h>
76 #include <netinet/tcp.h>
77 #include <netinet/tcp_seq.h>
78 #include <netinet/tcp_timer.h>
79 #include <netinet/tcp_var.h>
80 #include <netinet/cc/cc.h>
81 #include <netinet/cc/cc_module.h>
82 
83 #include <netinet/khelp/h_ertt.h>
84 
85 /*
86  * Private signal type for rate based congestion signal.
87  * See <netinet/cc.h> for appropriate bit-range to use for private signals.
88  */
89 #define	CC_CHD_DELAY	0x02000000
90 
91 /* Largest possible number returned by random(). */
92 #define	RANDOM_MAX	INT_MAX
93 
94 static void	chd_ack_received(struct cc_var *ccv, uint16_t ack_type);
95 static void	chd_cb_destroy(struct cc_var *ccv);
96 static int	chd_cb_init(struct cc_var *ccv, void *ptr);
97 static void	chd_cong_signal(struct cc_var *ccv, uint32_t signal_type);
98 static void	chd_conn_init(struct cc_var *ccv);
99 static int	chd_mod_init(void);
100 static size_t	chd_data_sz(void);
101 
102 struct chd {
103 	/*
104 	 * Shadow window - keeps track of what the NewReno congestion window
105 	 * would have been if delay-based cwnd backoffs had not been made. This
106 	 * functionality aids coexistence with loss-based TCP flows which may be
107 	 * sharing links along the path.
108 	 */
109 	unsigned long shadow_w;
110 	/*
111 	 * Loss-based TCP compatibility flag - When set, it turns on the shadow
112 	 * window functionality.
113 	 */
114 	int loss_compete;
115 	 /* The maximum round trip time seen within a measured rtt period. */
116 	int maxrtt_in_rtt;
117 	/* The previous qdly that caused cwnd to backoff. */
118 	int prev_backoff_qdly;
119 };
120 
121 static int ertt_id;
122 
123 VNET_DEFINE_STATIC(uint32_t, chd_qmin) = 5;
124 VNET_DEFINE_STATIC(uint32_t, chd_pmax) = 50;
125 VNET_DEFINE_STATIC(uint32_t, chd_loss_fair) = 1;
126 VNET_DEFINE_STATIC(uint32_t, chd_use_max) = 1;
127 VNET_DEFINE_STATIC(uint32_t, chd_qthresh) = 20;
128 #define	V_chd_qthresh	VNET(chd_qthresh)
129 #define	V_chd_qmin	VNET(chd_qmin)
130 #define	V_chd_pmax	VNET(chd_pmax)
131 #define	V_chd_loss_fair	VNET(chd_loss_fair)
132 #define	V_chd_use_max	VNET(chd_use_max)
133 
134 
135 struct cc_algo chd_cc_algo = {
136 	.name = "chd",
137 	.ack_received = chd_ack_received,
138 	.cb_destroy = chd_cb_destroy,
139 	.cb_init = chd_cb_init,
140 	.cong_signal = chd_cong_signal,
141 	.conn_init = chd_conn_init,
142 	.mod_init = chd_mod_init,
143 	.cc_data_sz = chd_data_sz,
144 	.after_idle = newreno_cc_after_idle,
145 	.post_recovery = newreno_cc_post_recovery,
146 };
147 
148 static __inline void
149 chd_window_decrease(struct cc_var *ccv)
150 {
151 	unsigned long win;
152 
153 	win = min(CCV(ccv, snd_wnd), CCV(ccv, snd_cwnd)) / CCV(ccv, t_maxseg);
154 	win -= max((win / 2), 1);
155 	CCV(ccv, snd_ssthresh) = max(win, 2) * CCV(ccv, t_maxseg);
156 }
157 
158 /*
159  * Probabilistic backoff function. Returns 1 if we should backoff or 0
160  * otherwise. The calculation of p is similar to the calculation of p in cc_hd.
161  */
162 static __inline int
163 should_backoff(int qdly, int maxqdly, struct chd *chd_data)
164 {
165 	unsigned long p, rand;
166 
167 	rand = random();
168 
169 	if (qdly < V_chd_qthresh) {
170 		chd_data->loss_compete = 0;
171 		p = (((RANDOM_MAX / 100) * V_chd_pmax) /
172 		    (V_chd_qthresh - V_chd_qmin)) *
173 		    (qdly - V_chd_qmin);
174 	} else {
175 		if (qdly > V_chd_qthresh) {
176 			p = (((RANDOM_MAX / 100) * V_chd_pmax) /
177 			    (maxqdly - V_chd_qthresh)) *
178 			    (maxqdly - qdly);
179 			if (V_chd_loss_fair && rand < p)
180 				chd_data->loss_compete = 1;
181 		} else {
182 			p = (RANDOM_MAX / 100) * V_chd_pmax;
183 			chd_data->loss_compete = 0;
184 		}
185 	}
186 
187 	return (rand < p);
188 }
189 
190 static __inline void
191 chd_window_increase(struct cc_var *ccv, int new_measurement)
192 {
193 	struct chd *chd_data;
194 	int incr;
195 
196 	chd_data = ccv->cc_data;
197 	incr = 0;
198 
199 	if (CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh)) {
200 		/* Adapted from NewReno slow start. */
201 		if (V_tcp_do_rfc3465) {
202 			/* In slow-start with ABC enabled. */
203 			if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max)) {
204 				/* Not due to RTO. */
205 				incr = min(ccv->bytes_this_ack,
206 				    V_tcp_abc_l_var * CCV(ccv, t_maxseg));
207 			} else {
208 				/* Due to RTO. */
209 				incr = min(ccv->bytes_this_ack,
210 				    CCV(ccv, t_maxseg));
211 			}
212 		} else
213 			incr = CCV(ccv, t_maxseg);
214 
215 	} else { /* Congestion avoidance. */
216 		if (V_tcp_do_rfc3465) {
217 			if (ccv->flags & CCF_ABC_SENTAWND) {
218 				ccv->flags &= ~CCF_ABC_SENTAWND;
219 				incr = CCV(ccv, t_maxseg);
220 			}
221 		} else if (new_measurement)
222 			incr = CCV(ccv, t_maxseg);
223 	}
224 
225 	if (chd_data->shadow_w > 0) {
226 		/* Track NewReno window. */
227 		chd_data->shadow_w = min(chd_data->shadow_w + incr,
228 		    TCP_MAXWIN << CCV(ccv, snd_scale));
229 	}
230 
231 	CCV(ccv,snd_cwnd) = min(CCV(ccv, snd_cwnd) + incr,
232 	    TCP_MAXWIN << CCV(ccv, snd_scale));
233 }
234 
235 /*
236  * All ACK signals are used for timing measurements to determine delay-based
237  * congestion. However, window increases are only performed when
238  * ack_type == CC_ACK.
239  */
240 static void
241 chd_ack_received(struct cc_var *ccv, uint16_t ack_type)
242 {
243 	struct chd *chd_data;
244 	struct ertt *e_t;
245 	int backoff, new_measurement, qdly, rtt;
246 
247 	e_t = khelp_get_osd(&CCV(ccv, t_osd), ertt_id);
248 	chd_data = ccv->cc_data;
249 	new_measurement = e_t->flags & ERTT_NEW_MEASUREMENT;
250 	backoff = qdly = 0;
251 
252 	chd_data->maxrtt_in_rtt = imax(e_t->rtt, chd_data->maxrtt_in_rtt);
253 
254 	if (new_measurement) {
255 		/*
256 		 * There is a new per RTT measurement, so check to see if there
257 		 * is delay based congestion.
258 		 */
259 		rtt = V_chd_use_max ? chd_data->maxrtt_in_rtt : e_t->rtt;
260 		chd_data->maxrtt_in_rtt = 0;
261 
262 		if (rtt && e_t->minrtt && !IN_RECOVERY(CCV(ccv, t_flags))) {
263 			qdly = rtt - e_t->minrtt;
264 			if (qdly > V_chd_qmin) {
265 				/*
266 				 * Probabilistic delay based congestion
267 				 * indication.
268 				 */
269 				backoff = should_backoff(qdly,
270 				    e_t->maxrtt - e_t->minrtt, chd_data);
271 			} else
272 				chd_data->loss_compete = 0;
273 		}
274 		/* Reset per RTT measurement flag to start a new measurement. */
275 		e_t->flags &= ~ERTT_NEW_MEASUREMENT;
276 	}
277 
278 	if (backoff) {
279 		/*
280 		 * Update shadow_w before delay based backoff.
281 		 */
282 		if (chd_data->loss_compete ||
283 		    qdly > chd_data->prev_backoff_qdly) {
284 			/*
285 			 * Delay is higher than when we backed off previously,
286 			 * so it is possible that this flow is competing with
287 			 * loss based flows.
288 			 */
289 			chd_data->shadow_w = max(CCV(ccv, snd_cwnd),
290 			    chd_data->shadow_w);
291 		} else {
292 			/*
293 			 * Reset shadow_w, as it is probable that this flow is
294 			 * not competing with loss based flows at the moment.
295 			 */
296 			chd_data->shadow_w = 0;
297 		}
298 
299 		chd_data->prev_backoff_qdly = qdly;
300 		/*
301 		 * Send delay-based congestion signal to the congestion signal
302 		 * handler.
303 		 */
304 		chd_cong_signal(ccv, CC_CHD_DELAY);
305 
306 	} else if (ack_type == CC_ACK)
307 		chd_window_increase(ccv, new_measurement);
308 }
309 
310 static void
311 chd_cb_destroy(struct cc_var *ccv)
312 {
313 	free(ccv->cc_data, M_CC_MEM);
314 }
315 
316 size_t
317 chd_data_sz(void)
318 {
319 	return (sizeof(struct chd));
320 }
321 
322 static int
323 chd_cb_init(struct cc_var *ccv, void *ptr)
324 {
325 	struct chd *chd_data;
326 
327 	INP_WLOCK_ASSERT(tptoinpcb(ccv->ccvc.tcp));
328 	if (ptr == NULL) {
329 		chd_data = malloc(sizeof(struct chd), M_CC_MEM, M_NOWAIT);
330 		if (chd_data == NULL)
331 			return (ENOMEM);
332 	} else
333 		chd_data = ptr;
334 
335 	chd_data->shadow_w = 0;
336 	ccv->cc_data = chd_data;
337 
338 	return (0);
339 }
340 
341 static void
342 chd_cong_signal(struct cc_var *ccv, uint32_t signal_type)
343 {
344 	struct ertt *e_t;
345 	struct chd *chd_data;
346 	int qdly;
347 
348 	e_t = khelp_get_osd(&CCV(ccv, t_osd), ertt_id);
349 	chd_data = ccv->cc_data;
350 	qdly = imax(e_t->rtt, chd_data->maxrtt_in_rtt) - e_t->minrtt;
351 
352 	switch(signal_type) {
353 	case CC_CHD_DELAY:
354 		chd_window_decrease(ccv); /* Set new ssthresh. */
355 		CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
356 		CCV(ccv, snd_recover) = CCV(ccv, snd_max);
357 		ENTER_CONGRECOVERY(CCV(ccv, t_flags));
358 		break;
359 
360 	case CC_NDUPACK: /* Packet loss. */
361 		/*
362 		 * Only react to loss as a congestion signal if qdly >
363 		 * V_chd_qthresh.  If qdly is less than qthresh, presume that
364 		 * this is a non congestion related loss. If qdly is greater
365 		 * than qthresh, assume that we are competing with loss based
366 		 * tcp flows and restore window from any unnecessary backoffs,
367 		 * before the decrease.
368 		 */
369 		if (!IN_RECOVERY(CCV(ccv, t_flags)) && qdly > V_chd_qthresh) {
370 			if (chd_data->loss_compete) {
371 				CCV(ccv, snd_cwnd) = max(CCV(ccv, snd_cwnd),
372 				    chd_data->shadow_w);
373 			}
374 			chd_window_decrease(ccv);
375 		} else {
376 			 /*
377 			  * This loss isn't congestion related, or already
378 			  * recovering from congestion.
379 			  */
380 			CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
381 			CCV(ccv, snd_recover) = CCV(ccv, snd_max);
382 		}
383 
384 		if (chd_data->shadow_w > 0) {
385 			chd_data->shadow_w = max(chd_data->shadow_w /
386 			    CCV(ccv, t_maxseg) / 2, 2) * CCV(ccv, t_maxseg);
387 		}
388 		ENTER_FASTRECOVERY(CCV(ccv, t_flags));
389 		break;
390 
391 	default:
392 		newreno_cc_cong_signal(ccv, signal_type);
393 	}
394 }
395 
396 static void
397 chd_conn_init(struct cc_var *ccv)
398 {
399 	struct chd *chd_data;
400 
401 	chd_data = ccv->cc_data;
402 	chd_data->prev_backoff_qdly = 0;
403 	chd_data->maxrtt_in_rtt = 0;
404 	chd_data->loss_compete = 0;
405 	/*
406 	 * Initialise the shadow_cwnd to be equal to snd_cwnd in case we are
407 	 * competing with loss based flows from the start.
408 	 */
409 	chd_data->shadow_w = CCV(ccv, snd_cwnd);
410 }
411 
412 static int
413 chd_mod_init(void)
414 {
415 
416 	ertt_id = khelp_get_id("ertt");
417 	if (ertt_id <= 0) {
418 		printf("%s: h_ertt module not found\n", __func__);
419 		return (ENOENT);
420 	}
421 	return (0);
422 }
423 
424 static int
425 chd_loss_fair_handler(SYSCTL_HANDLER_ARGS)
426 {
427 	int error;
428 	uint32_t new;
429 
430 	new = V_chd_loss_fair;
431 	error = sysctl_handle_int(oidp, &new, 0, req);
432 	if (error == 0 && req->newptr != NULL) {
433 		if (new > 1)
434 			error = EINVAL;
435 		else
436 			V_chd_loss_fair = new;
437 	}
438 
439 	return (error);
440 }
441 
442 static int
443 chd_pmax_handler(SYSCTL_HANDLER_ARGS)
444 {
445 	int error;
446 	uint32_t new;
447 
448 	new = V_chd_pmax;
449 	error = sysctl_handle_int(oidp, &new, 0, req);
450 	if (error == 0 && req->newptr != NULL) {
451 		if (new == 0 || new > 100)
452 			error = EINVAL;
453 		else
454 			V_chd_pmax = new;
455 	}
456 
457 	return (error);
458 }
459 
460 static int
461 chd_qthresh_handler(SYSCTL_HANDLER_ARGS)
462 {
463 	int error;
464 	uint32_t new;
465 
466 	new = V_chd_qthresh;
467 	error = sysctl_handle_int(oidp, &new, 0, req);
468 	if (error == 0 && req->newptr != NULL) {
469 		if (new <= V_chd_qmin)
470 			error = EINVAL;
471 		else
472 			V_chd_qthresh = new;
473 	}
474 
475 	return (error);
476 }
477 
478 SYSCTL_DECL(_net_inet_tcp_cc_chd);
479 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, chd, CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
480     "CAIA Hamilton delay-based congestion control related settings");
481 
482 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, loss_fair,
483     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
484     &VNET_NAME(chd_loss_fair), 1, &chd_loss_fair_handler,
485     "IU", "Flag to enable shadow window functionality.");
486 
487 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, pmax,
488     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
489     &VNET_NAME(chd_pmax), 5, &chd_pmax_handler,
490     "IU", "Per RTT maximum backoff probability as a percentage");
491 
492 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, queue_threshold,
493     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
494     &VNET_NAME(chd_qthresh), 20, &chd_qthresh_handler,
495     "IU", "Queueing congestion threshold in ticks");
496 
497 SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, queue_min,
498     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_qmin), 5,
499     "Minimum queueing delay threshold in ticks");
500 
501 SYSCTL_UINT(_net_inet_tcp_cc_chd,  OID_AUTO, use_max,
502     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_use_max), 1,
503     "Use the maximum RTT seen within the measurement period (RTT) "
504     "as the basic delay measurement for the algorithm.");
505 
506 DECLARE_CC_MODULE(chd, &chd_cc_algo);
507 MODULE_VERSION(chd, 2);
508 MODULE_DEPEND(chd, ertt, 1, 1, 1);
509