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