1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 2008-2010 Lawrence Stewart <lstewart@freebsd.org> 5 * Copyright (c) 2010 The FreeBSD Foundation 6 * All rights reserved. 7 * 8 * This software was developed by Lawrence Stewart while studying at the Centre 9 * for Advanced Internet Architectures, Swinburne University of Technology, made 10 * possible in part by a grant from the Cisco University Research Program Fund 11 * at Community Foundation Silicon Valley. 12 * 13 * Portions of this software were developed at the Centre for Advanced 14 * Internet Architectures, Swinburne University of Technology, Melbourne, 15 * Australia by David Hayes under sponsorship from the FreeBSD Foundation. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 /* 40 * An implementation of the CUBIC congestion control algorithm for FreeBSD, 41 * based on the Internet Draft "draft-rhee-tcpm-cubic-02" by Rhee, Xu and Ha. 42 * Originally released as part of the NewTCP research project at Swinburne 43 * University of Technology's Centre for Advanced Internet Architectures, 44 * Melbourne, Australia, which was made possible in part by a grant from the 45 * Cisco University Research Program Fund at Community Foundation Silicon 46 * Valley. More details are available at: 47 * http://caia.swin.edu.au/urp/newtcp/ 48 */ 49 50 #include <sys/cdefs.h> 51 __FBSDID("$FreeBSD$"); 52 53 #include <sys/param.h> 54 #include <sys/kernel.h> 55 #include <sys/limits.h> 56 #include <sys/malloc.h> 57 #include <sys/module.h> 58 #include <sys/socket.h> 59 #include <sys/socketvar.h> 60 #include <sys/sysctl.h> 61 #include <sys/systm.h> 62 63 #include <net/vnet.h> 64 65 #include <netinet/tcp.h> 66 #include <netinet/tcp_seq.h> 67 #include <netinet/tcp_timer.h> 68 #include <netinet/tcp_var.h> 69 #include <netinet/cc/cc.h> 70 #include <netinet/cc/cc_cubic.h> 71 #include <netinet/cc/cc_module.h> 72 73 static void cubic_ack_received(struct cc_var *ccv, uint16_t type); 74 static void cubic_cb_destroy(struct cc_var *ccv); 75 static int cubic_cb_init(struct cc_var *ccv); 76 static void cubic_cong_signal(struct cc_var *ccv, uint32_t type); 77 static void cubic_conn_init(struct cc_var *ccv); 78 static int cubic_mod_init(void); 79 static void cubic_post_recovery(struct cc_var *ccv); 80 static void cubic_record_rtt(struct cc_var *ccv); 81 static void cubic_ssthresh_update(struct cc_var *ccv); 82 static void cubic_after_idle(struct cc_var *ccv); 83 84 struct cubic { 85 /* Cubic K in fixed point form with CUBIC_SHIFT worth of precision. */ 86 int64_t K; 87 /* Sum of RTT samples across an epoch in ticks. */ 88 int64_t sum_rtt_ticks; 89 /* cwnd at the most recent congestion event. */ 90 unsigned long max_cwnd; 91 /* cwnd at the previous congestion event. */ 92 unsigned long prev_max_cwnd; 93 /* Number of congestion events. */ 94 uint32_t num_cong_events; 95 /* Minimum observed rtt in ticks. */ 96 int min_rtt_ticks; 97 /* Mean observed rtt between congestion epochs. */ 98 int mean_rtt_ticks; 99 /* ACKs since last congestion event. */ 100 int epoch_ack_count; 101 /* Time of last congestion event in ticks. */ 102 int t_last_cong; 103 }; 104 105 static MALLOC_DEFINE(M_CUBIC, "cubic data", 106 "Per connection data required for the CUBIC congestion control algorithm"); 107 108 struct cc_algo cubic_cc_algo = { 109 .name = "cubic", 110 .ack_received = cubic_ack_received, 111 .cb_destroy = cubic_cb_destroy, 112 .cb_init = cubic_cb_init, 113 .cong_signal = cubic_cong_signal, 114 .conn_init = cubic_conn_init, 115 .mod_init = cubic_mod_init, 116 .post_recovery = cubic_post_recovery, 117 .after_idle = cubic_after_idle, 118 }; 119 120 static void 121 cubic_ack_received(struct cc_var *ccv, uint16_t type) 122 { 123 struct cubic *cubic_data; 124 unsigned long w_tf, w_cubic_next; 125 int ticks_since_cong; 126 127 cubic_data = ccv->cc_data; 128 cubic_record_rtt(ccv); 129 130 /* 131 * Regular ACK and we're not in cong/fast recovery and we're cwnd 132 * limited and we're either not doing ABC or are slow starting or are 133 * doing ABC and we've sent a cwnd's worth of bytes. 134 */ 135 if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) && 136 (ccv->flags & CCF_CWND_LIMITED) && (!V_tcp_do_rfc3465 || 137 CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh) || 138 (V_tcp_do_rfc3465 && ccv->flags & CCF_ABC_SENTAWND))) { 139 /* Use the logic in NewReno ack_received() for slow start. */ 140 if (CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh) || 141 cubic_data->min_rtt_ticks == TCPTV_SRTTBASE) 142 newreno_cc_algo.ack_received(ccv, type); 143 else { 144 if ((ticks_since_cong = 145 ticks - cubic_data->t_last_cong) < 0) { 146 /* 147 * dragging t_last_cong along 148 */ 149 ticks_since_cong = INT_MAX; 150 cubic_data->t_last_cong = ticks - INT_MAX; 151 } 152 153 /* 154 * The mean RTT is used to best reflect the equations in 155 * the I-D. Using min_rtt in the tf_cwnd calculation 156 * causes w_tf to grow much faster than it should if the 157 * RTT is dominated by network buffering rather than 158 * propagation delay. 159 */ 160 w_tf = tf_cwnd(ticks_since_cong, 161 cubic_data->mean_rtt_ticks, cubic_data->max_cwnd, 162 CCV(ccv, t_maxseg)); 163 164 w_cubic_next = cubic_cwnd(ticks_since_cong + 165 cubic_data->mean_rtt_ticks, cubic_data->max_cwnd, 166 CCV(ccv, t_maxseg), cubic_data->K); 167 168 ccv->flags &= ~CCF_ABC_SENTAWND; 169 170 if (w_cubic_next < w_tf) { 171 /* 172 * TCP-friendly region, follow tf 173 * cwnd growth. 174 */ 175 if (CCV(ccv, snd_cwnd) < w_tf) 176 CCV(ccv, snd_cwnd) = ulmin(w_tf, INT_MAX); 177 } 178 179 else if (CCV(ccv, snd_cwnd) < w_cubic_next) { 180 /* 181 * Concave or convex region, follow CUBIC 182 * cwnd growth. 183 */ 184 if (V_tcp_do_rfc3465) 185 CCV(ccv, snd_cwnd) = ulmin(w_cubic_next, 186 INT_MAX); 187 else 188 CCV(ccv, snd_cwnd) += ulmax(1, 189 ((ulmin(w_cubic_next, INT_MAX) - 190 CCV(ccv, snd_cwnd)) * 191 CCV(ccv, t_maxseg)) / 192 CCV(ccv, snd_cwnd)); 193 } 194 195 /* 196 * If we're not in slow start and we're probing for a 197 * new cwnd limit at the start of a connection 198 * (happens when hostcache has a relevant entry), 199 * keep updating our current estimate of the 200 * max_cwnd. 201 */ 202 if (cubic_data->num_cong_events == 0 && 203 cubic_data->max_cwnd < CCV(ccv, snd_cwnd)) { 204 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 205 cubic_data->K = cubic_k(cubic_data->max_cwnd / 206 CCV(ccv, t_maxseg)); 207 } 208 } 209 } 210 } 211 212 /* 213 * This is a Cubic specific implementation of after_idle. 214 * - Reset cwnd by calling New Reno implementation of after_idle. 215 * - Reset t_last_cong. 216 */ 217 static void 218 cubic_after_idle(struct cc_var *ccv) 219 { 220 struct cubic *cubic_data; 221 222 cubic_data = ccv->cc_data; 223 224 cubic_data->max_cwnd = ulmax(cubic_data->max_cwnd, CCV(ccv, snd_cwnd)); 225 cubic_data->K = cubic_k(cubic_data->max_cwnd / CCV(ccv, t_maxseg)); 226 227 newreno_cc_algo.after_idle(ccv); 228 cubic_data->t_last_cong = ticks; 229 } 230 231 232 static void 233 cubic_cb_destroy(struct cc_var *ccv) 234 { 235 free(ccv->cc_data, M_CUBIC); 236 } 237 238 static int 239 cubic_cb_init(struct cc_var *ccv) 240 { 241 struct cubic *cubic_data; 242 243 cubic_data = malloc(sizeof(struct cubic), M_CUBIC, M_NOWAIT|M_ZERO); 244 245 if (cubic_data == NULL) 246 return (ENOMEM); 247 248 /* Init some key variables with sensible defaults. */ 249 cubic_data->t_last_cong = ticks; 250 cubic_data->min_rtt_ticks = TCPTV_SRTTBASE; 251 cubic_data->mean_rtt_ticks = 1; 252 253 ccv->cc_data = cubic_data; 254 255 return (0); 256 } 257 258 /* 259 * Perform any necessary tasks before we enter congestion recovery. 260 */ 261 static void 262 cubic_cong_signal(struct cc_var *ccv, uint32_t type) 263 { 264 struct cubic *cubic_data; 265 266 cubic_data = ccv->cc_data; 267 268 switch (type) { 269 case CC_NDUPACK: 270 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) { 271 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 272 cubic_ssthresh_update(ccv); 273 cubic_data->num_cong_events++; 274 cubic_data->prev_max_cwnd = cubic_data->max_cwnd; 275 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 276 } 277 ENTER_RECOVERY(CCV(ccv, t_flags)); 278 } 279 break; 280 281 case CC_ECN: 282 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 283 cubic_ssthresh_update(ccv); 284 cubic_data->num_cong_events++; 285 cubic_data->prev_max_cwnd = cubic_data->max_cwnd; 286 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 287 cubic_data->t_last_cong = ticks; 288 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); 289 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 290 } 291 break; 292 293 case CC_RTO: 294 /* 295 * Grab the current time and record it so we know when the 296 * most recent congestion event was. Only record it when the 297 * timeout has fired more than once, as there is a reasonable 298 * chance the first one is a false alarm and may not indicate 299 * congestion. 300 */ 301 if (CCV(ccv, t_rxtshift) >= 2) { 302 cubic_data->num_cong_events++; 303 cubic_data->t_last_cong = ticks; 304 } 305 break; 306 } 307 } 308 309 static void 310 cubic_conn_init(struct cc_var *ccv) 311 { 312 struct cubic *cubic_data; 313 314 cubic_data = ccv->cc_data; 315 316 /* 317 * Ensure we have a sane initial value for max_cwnd recorded. Without 318 * this here bad things happen when entries from the TCP hostcache 319 * get used. 320 */ 321 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 322 } 323 324 static int 325 cubic_mod_init(void) 326 { 327 return (0); 328 } 329 330 /* 331 * Perform any necessary tasks before we exit congestion recovery. 332 */ 333 static void 334 cubic_post_recovery(struct cc_var *ccv) 335 { 336 struct cubic *cubic_data; 337 int pipe; 338 339 cubic_data = ccv->cc_data; 340 pipe = 0; 341 342 /* Fast convergence heuristic. */ 343 if (cubic_data->max_cwnd < cubic_data->prev_max_cwnd) 344 cubic_data->max_cwnd = (cubic_data->max_cwnd * CUBIC_FC_FACTOR) 345 >> CUBIC_SHIFT; 346 347 if (IN_FASTRECOVERY(CCV(ccv, t_flags))) { 348 /* 349 * If inflight data is less than ssthresh, set cwnd 350 * conservatively to avoid a burst of data, as suggested in 351 * the NewReno RFC. Otherwise, use the CUBIC method. 352 * 353 * XXXLAS: Find a way to do this without needing curack 354 */ 355 if (V_tcp_do_rfc6675_pipe) 356 pipe = tcp_compute_pipe(ccv->ccvc.tcp); 357 else 358 pipe = CCV(ccv, snd_max) - ccv->curack; 359 360 if (pipe < CCV(ccv, snd_ssthresh)) 361 /* 362 * Ensure that cwnd does not collapse to 1 MSS under 363 * adverse conditions. Implements RFC6582 364 */ 365 CCV(ccv, snd_cwnd) = max(pipe, CCV(ccv, t_maxseg)) + 366 CCV(ccv, t_maxseg); 367 else 368 /* Update cwnd based on beta and adjusted max_cwnd. */ 369 CCV(ccv, snd_cwnd) = max(1, ((CUBIC_BETA * 370 cubic_data->max_cwnd) >> CUBIC_SHIFT)); 371 } 372 cubic_data->t_last_cong = ticks; 373 374 /* Calculate the average RTT between congestion epochs. */ 375 if (cubic_data->epoch_ack_count > 0 && 376 cubic_data->sum_rtt_ticks >= cubic_data->epoch_ack_count) { 377 cubic_data->mean_rtt_ticks = (int)(cubic_data->sum_rtt_ticks / 378 cubic_data->epoch_ack_count); 379 } 380 381 cubic_data->epoch_ack_count = 0; 382 cubic_data->sum_rtt_ticks = 0; 383 cubic_data->K = cubic_k(cubic_data->max_cwnd / CCV(ccv, t_maxseg)); 384 } 385 386 /* 387 * Record the min RTT and sum samples for the epoch average RTT calculation. 388 */ 389 static void 390 cubic_record_rtt(struct cc_var *ccv) 391 { 392 struct cubic *cubic_data; 393 int t_srtt_ticks; 394 395 /* Ignore srtt until a min number of samples have been taken. */ 396 if (CCV(ccv, t_rttupdated) >= CUBIC_MIN_RTT_SAMPLES) { 397 cubic_data = ccv->cc_data; 398 t_srtt_ticks = CCV(ccv, t_srtt) / TCP_RTT_SCALE; 399 400 /* 401 * Record the current SRTT as our minrtt if it's the smallest 402 * we've seen or minrtt is currently equal to its initialised 403 * value. 404 * 405 * XXXLAS: Should there be some hysteresis for minrtt? 406 */ 407 if ((t_srtt_ticks < cubic_data->min_rtt_ticks || 408 cubic_data->min_rtt_ticks == TCPTV_SRTTBASE)) { 409 cubic_data->min_rtt_ticks = max(1, t_srtt_ticks); 410 411 /* 412 * If the connection is within its first congestion 413 * epoch, ensure we prime mean_rtt_ticks with a 414 * reasonable value until the epoch average RTT is 415 * calculated in cubic_post_recovery(). 416 */ 417 if (cubic_data->min_rtt_ticks > 418 cubic_data->mean_rtt_ticks) 419 cubic_data->mean_rtt_ticks = 420 cubic_data->min_rtt_ticks; 421 } 422 423 /* Sum samples for epoch average RTT calculation. */ 424 cubic_data->sum_rtt_ticks += t_srtt_ticks; 425 cubic_data->epoch_ack_count++; 426 } 427 } 428 429 /* 430 * Update the ssthresh in the event of congestion. 431 */ 432 static void 433 cubic_ssthresh_update(struct cc_var *ccv) 434 { 435 struct cubic *cubic_data; 436 437 cubic_data = ccv->cc_data; 438 439 /* 440 * On the first congestion event, set ssthresh to cwnd * 0.5, on 441 * subsequent congestion events, set it to cwnd * beta. 442 */ 443 if (cubic_data->num_cong_events == 0) 444 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd) >> 1; 445 else 446 CCV(ccv, snd_ssthresh) = ((u_long)CCV(ccv, snd_cwnd) * 447 CUBIC_BETA) >> CUBIC_SHIFT; 448 } 449 450 451 DECLARE_CC_MODULE(cubic, &cubic_cc_algo); 452