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 #include <sys/param.h>
57 #include <sys/kernel.h>
58 #include <sys/khelp.h>
59 #include <sys/limits.h>
60 #include <sys/malloc.h>
61 #include <sys/module.h>
62 #include <sys/queue.h>
63 #include <sys/socket.h>
64 #include <sys/socketvar.h>
65 #include <sys/sysctl.h>
66 #include <sys/systm.h>
67
68 #include <net/vnet.h>
69
70 #include <net/route.h>
71 #include <net/route/nhop.h>
72
73 #include <netinet/in_pcb.h>
74 #include <netinet/tcp.h>
75 #include <netinet/tcp_seq.h>
76 #include <netinet/tcp_timer.h>
77 #include <netinet/tcp_var.h>
78 #include <netinet/cc/cc.h>
79 #include <netinet/cc/cc_module.h>
80
81 #include <netinet/khelp/h_ertt.h>
82
83 /*
84 * Private signal type for rate based congestion signal.
85 * See <netinet/cc.h> for appropriate bit-range to use for private signals.
86 */
87 #define CC_CHD_DELAY 0x02000000
88
89 /* Largest possible number returned by random(). */
90 #define RANDOM_MAX INT_MAX
91
92 static void chd_ack_received(struct cc_var *ccv, uint16_t ack_type);
93 static void chd_cb_destroy(struct cc_var *ccv);
94 static int chd_cb_init(struct cc_var *ccv, void *ptr);
95 static void chd_cong_signal(struct cc_var *ccv, uint32_t signal_type);
96 static void chd_conn_init(struct cc_var *ccv);
97 static int chd_mod_init(void);
98 static size_t chd_data_sz(void);
99
100 struct chd {
101 /*
102 * Shadow window - keeps track of what the NewReno congestion window
103 * would have been if delay-based cwnd backoffs had not been made. This
104 * functionality aids coexistence with loss-based TCP flows which may be
105 * sharing links along the path.
106 */
107 unsigned long shadow_w;
108 /*
109 * Loss-based TCP compatibility flag - When set, it turns on the shadow
110 * window functionality.
111 */
112 int loss_compete;
113 /* The maximum round trip time seen within a measured rtt period. */
114 int maxrtt_in_rtt;
115 /* The previous qdly that caused cwnd to backoff. */
116 int prev_backoff_qdly;
117 };
118
119 static int ertt_id;
120
121 VNET_DEFINE_STATIC(uint32_t, chd_qmin) = 5;
122 VNET_DEFINE_STATIC(uint32_t, chd_pmax) = 50;
123 VNET_DEFINE_STATIC(uint32_t, chd_loss_fair) = 1;
124 VNET_DEFINE_STATIC(uint32_t, chd_use_max) = 1;
125 VNET_DEFINE_STATIC(uint32_t, chd_qthresh) = 20;
126 #define V_chd_qthresh VNET(chd_qthresh)
127 #define V_chd_qmin VNET(chd_qmin)
128 #define V_chd_pmax VNET(chd_pmax)
129 #define V_chd_loss_fair VNET(chd_loss_fair)
130 #define V_chd_use_max VNET(chd_use_max)
131
132
133 struct cc_algo chd_cc_algo = {
134 .name = "chd",
135 .ack_received = chd_ack_received,
136 .cb_destroy = chd_cb_destroy,
137 .cb_init = chd_cb_init,
138 .cong_signal = chd_cong_signal,
139 .conn_init = chd_conn_init,
140 .mod_init = chd_mod_init,
141 .cc_data_sz = chd_data_sz,
142 .after_idle = newreno_cc_after_idle,
143 .post_recovery = newreno_cc_post_recovery,
144 };
145
146 static __inline void
chd_window_decrease(struct cc_var * ccv)147 chd_window_decrease(struct cc_var *ccv)
148 {
149 unsigned long win;
150
151 win = min(CCV(ccv, snd_wnd), CCV(ccv, snd_cwnd)) / CCV(ccv, t_maxseg);
152 win -= max((win / 2), 1);
153 CCV(ccv, snd_ssthresh) = max(win, 2) * CCV(ccv, t_maxseg);
154 }
155
156 /*
157 * Probabilistic backoff function. Returns 1 if we should backoff or 0
158 * otherwise. The calculation of p is similar to the calculation of p in cc_hd.
159 */
160 static __inline int
should_backoff(int qdly,int maxqdly,struct chd * chd_data)161 should_backoff(int qdly, int maxqdly, struct chd *chd_data)
162 {
163 unsigned long p, rand;
164
165 rand = random();
166
167 if (qdly < V_chd_qthresh) {
168 chd_data->loss_compete = 0;
169 p = (((RANDOM_MAX / 100) * V_chd_pmax) /
170 (V_chd_qthresh - V_chd_qmin)) *
171 (qdly - V_chd_qmin);
172 } else {
173 if (qdly > V_chd_qthresh) {
174 p = (((RANDOM_MAX / 100) * V_chd_pmax) /
175 (maxqdly - V_chd_qthresh)) *
176 (maxqdly - qdly);
177 if (V_chd_loss_fair && rand < p)
178 chd_data->loss_compete = 1;
179 } else {
180 p = (RANDOM_MAX / 100) * V_chd_pmax;
181 chd_data->loss_compete = 0;
182 }
183 }
184
185 return (rand < p);
186 }
187
188 static __inline void
chd_window_increase(struct cc_var * ccv,int new_measurement)189 chd_window_increase(struct cc_var *ccv, int new_measurement)
190 {
191 struct chd *chd_data;
192 int incr;
193
194 chd_data = ccv->cc_data;
195 incr = 0;
196
197 if (CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh)) {
198 /* Adapted from NewReno slow start. */
199 if (V_tcp_do_rfc3465) {
200 /* In slow-start with ABC enabled. */
201 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max)) {
202 /* Not due to RTO. */
203 incr = min(ccv->bytes_this_ack,
204 V_tcp_abc_l_var * CCV(ccv, t_maxseg));
205 } else {
206 /* Due to RTO. */
207 incr = min(ccv->bytes_this_ack,
208 CCV(ccv, t_maxseg));
209 }
210 } else
211 incr = CCV(ccv, t_maxseg);
212
213 } else { /* Congestion avoidance. */
214 if (V_tcp_do_rfc3465) {
215 if (ccv->flags & CCF_ABC_SENTAWND) {
216 ccv->flags &= ~CCF_ABC_SENTAWND;
217 incr = CCV(ccv, t_maxseg);
218 }
219 } else if (new_measurement)
220 incr = CCV(ccv, t_maxseg);
221 }
222
223 if (chd_data->shadow_w > 0) {
224 /* Track NewReno window. */
225 chd_data->shadow_w = min(chd_data->shadow_w + incr,
226 TCP_MAXWIN << CCV(ccv, snd_scale));
227 }
228
229 CCV(ccv,snd_cwnd) = min(CCV(ccv, snd_cwnd) + incr,
230 TCP_MAXWIN << CCV(ccv, snd_scale));
231 }
232
233 /*
234 * All ACK signals are used for timing measurements to determine delay-based
235 * congestion. However, window increases are only performed when
236 * ack_type == CC_ACK.
237 */
238 static void
chd_ack_received(struct cc_var * ccv,uint16_t ack_type)239 chd_ack_received(struct cc_var *ccv, uint16_t ack_type)
240 {
241 struct chd *chd_data;
242 struct ertt *e_t;
243 int backoff, new_measurement, qdly, rtt;
244
245 e_t = khelp_get_osd(&CCV(ccv, t_osd), ertt_id);
246 chd_data = ccv->cc_data;
247 new_measurement = e_t->flags & ERTT_NEW_MEASUREMENT;
248 backoff = qdly = 0;
249
250 chd_data->maxrtt_in_rtt = imax(e_t->rtt, chd_data->maxrtt_in_rtt);
251
252 if (new_measurement) {
253 /*
254 * There is a new per RTT measurement, so check to see if there
255 * is delay based congestion.
256 */
257 rtt = V_chd_use_max ? chd_data->maxrtt_in_rtt : e_t->rtt;
258 chd_data->maxrtt_in_rtt = 0;
259
260 if (rtt && e_t->minrtt && !IN_RECOVERY(CCV(ccv, t_flags))) {
261 qdly = rtt - e_t->minrtt;
262 if (qdly > V_chd_qmin) {
263 /*
264 * Probabilistic delay based congestion
265 * indication.
266 */
267 backoff = should_backoff(qdly,
268 e_t->maxrtt - e_t->minrtt, chd_data);
269 } else
270 chd_data->loss_compete = 0;
271 }
272 /* Reset per RTT measurement flag to start a new measurement. */
273 e_t->flags &= ~ERTT_NEW_MEASUREMENT;
274 }
275
276 if (backoff) {
277 /*
278 * Update shadow_w before delay based backoff.
279 */
280 if (chd_data->loss_compete ||
281 qdly > chd_data->prev_backoff_qdly) {
282 /*
283 * Delay is higher than when we backed off previously,
284 * so it is possible that this flow is competing with
285 * loss based flows.
286 */
287 chd_data->shadow_w = max(CCV(ccv, snd_cwnd),
288 chd_data->shadow_w);
289 } else {
290 /*
291 * Reset shadow_w, as it is probable that this flow is
292 * not competing with loss based flows at the moment.
293 */
294 chd_data->shadow_w = 0;
295 }
296
297 chd_data->prev_backoff_qdly = qdly;
298 /*
299 * Send delay-based congestion signal to the congestion signal
300 * handler.
301 */
302 chd_cong_signal(ccv, CC_CHD_DELAY);
303
304 } else if (ack_type == CC_ACK)
305 chd_window_increase(ccv, new_measurement);
306 }
307
308 static void
chd_cb_destroy(struct cc_var * ccv)309 chd_cb_destroy(struct cc_var *ccv)
310 {
311 free(ccv->cc_data, M_CC_MEM);
312 }
313
314 size_t
chd_data_sz(void)315 chd_data_sz(void)
316 {
317 return (sizeof(struct chd));
318 }
319
320 static int
chd_cb_init(struct cc_var * ccv,void * ptr)321 chd_cb_init(struct cc_var *ccv, void *ptr)
322 {
323 struct chd *chd_data;
324
325 INP_WLOCK_ASSERT(tptoinpcb(ccv->ccvc.tcp));
326 if (ptr == NULL) {
327 chd_data = malloc(sizeof(struct chd), M_CC_MEM, M_NOWAIT);
328 if (chd_data == NULL)
329 return (ENOMEM);
330 } else
331 chd_data = ptr;
332
333 chd_data->shadow_w = 0;
334 ccv->cc_data = chd_data;
335
336 return (0);
337 }
338
339 static void
chd_cong_signal(struct cc_var * ccv,uint32_t signal_type)340 chd_cong_signal(struct cc_var *ccv, uint32_t signal_type)
341 {
342 struct ertt *e_t;
343 struct chd *chd_data;
344 int qdly;
345
346 e_t = khelp_get_osd(&CCV(ccv, t_osd), ertt_id);
347 chd_data = ccv->cc_data;
348 qdly = imax(e_t->rtt, chd_data->maxrtt_in_rtt) - e_t->minrtt;
349
350 switch(signal_type) {
351 case CC_CHD_DELAY:
352 chd_window_decrease(ccv); /* Set new ssthresh. */
353 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
354 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
355 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
356 break;
357
358 case CC_NDUPACK: /* Packet loss. */
359 /*
360 * Only react to loss as a congestion signal if qdly >
361 * V_chd_qthresh. If qdly is less than qthresh, presume that
362 * this is a non congestion related loss. If qdly is greater
363 * than qthresh, assume that we are competing with loss based
364 * tcp flows and restore window from any unnecessary backoffs,
365 * before the decrease.
366 */
367 if (!IN_RECOVERY(CCV(ccv, t_flags)) && qdly > V_chd_qthresh) {
368 if (chd_data->loss_compete) {
369 CCV(ccv, snd_cwnd) = max(CCV(ccv, snd_cwnd),
370 chd_data->shadow_w);
371 }
372 chd_window_decrease(ccv);
373 } else {
374 /*
375 * This loss isn't congestion related, or already
376 * recovering from congestion.
377 */
378 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
379 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
380 }
381
382 if (chd_data->shadow_w > 0) {
383 chd_data->shadow_w = max(chd_data->shadow_w /
384 CCV(ccv, t_maxseg) / 2, 2) * CCV(ccv, t_maxseg);
385 }
386 ENTER_FASTRECOVERY(CCV(ccv, t_flags));
387 break;
388
389 default:
390 newreno_cc_cong_signal(ccv, signal_type);
391 }
392 }
393
394 static void
chd_conn_init(struct cc_var * ccv)395 chd_conn_init(struct cc_var *ccv)
396 {
397 struct chd *chd_data;
398
399 chd_data = ccv->cc_data;
400 chd_data->prev_backoff_qdly = 0;
401 chd_data->maxrtt_in_rtt = 0;
402 chd_data->loss_compete = 0;
403 /*
404 * Initialise the shadow_cwnd to be equal to snd_cwnd in case we are
405 * competing with loss based flows from the start.
406 */
407 chd_data->shadow_w = CCV(ccv, snd_cwnd);
408 }
409
410 static int
chd_mod_init(void)411 chd_mod_init(void)
412 {
413
414 ertt_id = khelp_get_id("ertt");
415 if (ertt_id <= 0) {
416 printf("%s: h_ertt module not found\n", __func__);
417 return (ENOENT);
418 }
419 return (0);
420 }
421
422 static int
chd_loss_fair_handler(SYSCTL_HANDLER_ARGS)423 chd_loss_fair_handler(SYSCTL_HANDLER_ARGS)
424 {
425 int error;
426 uint32_t new;
427
428 new = V_chd_loss_fair;
429 error = sysctl_handle_int(oidp, &new, 0, req);
430 if (error == 0 && req->newptr != NULL) {
431 if (new > 1)
432 error = EINVAL;
433 else
434 V_chd_loss_fair = new;
435 }
436
437 return (error);
438 }
439
440 static int
chd_pmax_handler(SYSCTL_HANDLER_ARGS)441 chd_pmax_handler(SYSCTL_HANDLER_ARGS)
442 {
443 int error;
444 uint32_t new;
445
446 new = V_chd_pmax;
447 error = sysctl_handle_int(oidp, &new, 0, req);
448 if (error == 0 && req->newptr != NULL) {
449 if (new == 0 || new > 100)
450 error = EINVAL;
451 else
452 V_chd_pmax = new;
453 }
454
455 return (error);
456 }
457
458 static int
chd_qthresh_handler(SYSCTL_HANDLER_ARGS)459 chd_qthresh_handler(SYSCTL_HANDLER_ARGS)
460 {
461 int error;
462 uint32_t new;
463
464 new = V_chd_qthresh;
465 error = sysctl_handle_int(oidp, &new, 0, req);
466 if (error == 0 && req->newptr != NULL) {
467 if (new <= V_chd_qmin)
468 error = EINVAL;
469 else
470 V_chd_qthresh = new;
471 }
472
473 return (error);
474 }
475
476 SYSCTL_DECL(_net_inet_tcp_cc_chd);
477 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, chd, CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
478 "CAIA Hamilton delay-based congestion control related settings");
479
480 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, loss_fair,
481 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
482 &VNET_NAME(chd_loss_fair), 1, &chd_loss_fair_handler,
483 "IU", "Flag to enable shadow window functionality.");
484
485 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, pmax,
486 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
487 &VNET_NAME(chd_pmax), 5, &chd_pmax_handler,
488 "IU", "Per RTT maximum backoff probability as a percentage");
489
490 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, queue_threshold,
491 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
492 &VNET_NAME(chd_qthresh), 20, &chd_qthresh_handler,
493 "IU", "Queueing congestion threshold in ticks");
494
495 SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, queue_min,
496 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_qmin), 5,
497 "Minimum queueing delay threshold in ticks");
498
499 SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, use_max,
500 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_use_max), 1,
501 "Use the maximum RTT seen within the measurement period (RTT) "
502 "as the basic delay measurement for the algorithm.");
503
504 DECLARE_CC_MODULE(chd, &chd_cc_algo);
505 MODULE_VERSION(chd, 2);
506 MODULE_DEPEND(chd, ertt, 1, 1, 1);
507