1 /*- 2 * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995 3 * The Regents of the University of California. 4 * Copyright (c) 2007-2008,2010 5 * Swinburne University of Technology, Melbourne, Australia. 6 * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org> 7 * Copyright (c) 2010 The FreeBSD Foundation 8 * All rights reserved. 9 * 10 * This software was developed at the Centre for Advanced Internet 11 * Architectures, Swinburne University of Technology, by Lawrence Stewart, James 12 * Healy and David Hayes, made possible in part by a grant from the Cisco 13 * University Research Program Fund at Community Foundation Silicon Valley. 14 * 15 * Portions of this software were developed at the Centre for Advanced 16 * Internet Architectures, Swinburne University of Technology, Melbourne, 17 * Australia by David Hayes under sponsorship from the FreeBSD Foundation. 18 * 19 * Redistribution and use in source and binary forms, with or without 20 * modification, are permitted provided that the following conditions 21 * are met: 22 * 1. Redistributions of source code must retain the above copyright 23 * notice, this list of conditions and the following disclaimer. 24 * 2. Redistributions in binary form must reproduce the above copyright 25 * notice, this list of conditions and the following disclaimer in the 26 * documentation and/or other materials provided with the distribution. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 31 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 38 * SUCH DAMAGE. 39 */ 40 41 /* 42 * This software was first released in 2007 by James Healy and Lawrence Stewart 43 * whilst working on the NewTCP research project at Swinburne University of 44 * Technology's Centre for Advanced Internet Architectures, Melbourne, 45 * Australia, which was made possible in part by a grant from the Cisco 46 * University Research Program Fund at Community Foundation Silicon Valley. 47 * More details are available at: 48 * http://caia.swin.edu.au/urp/newtcp/ 49 */ 50 51 #include <sys/cdefs.h> 52 __FBSDID("$FreeBSD$"); 53 54 #include <sys/param.h> 55 #include <sys/kernel.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_var.h> 68 #include <netinet/cc/cc.h> 69 #include <netinet/cc/cc_module.h> 70 71 static void newreno_ack_received(struct cc_var *ccv, uint16_t type); 72 static void newreno_after_idle(struct cc_var *ccv); 73 static void newreno_cong_signal(struct cc_var *ccv, uint32_t type); 74 static void newreno_post_recovery(struct cc_var *ccv); 75 76 struct cc_algo newreno_cc_algo = { 77 .name = "newreno", 78 .ack_received = newreno_ack_received, 79 .after_idle = newreno_after_idle, 80 .cong_signal = newreno_cong_signal, 81 .post_recovery = newreno_post_recovery, 82 }; 83 84 static void 85 newreno_ack_received(struct cc_var *ccv, uint16_t type) 86 { 87 if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) && 88 (ccv->flags & CCF_CWND_LIMITED)) { 89 u_int cw = CCV(ccv, snd_cwnd); 90 u_int incr = CCV(ccv, t_maxseg); 91 92 /* 93 * Regular in-order ACK, open the congestion window. 94 * Method depends on which congestion control state we're 95 * in (slow start or cong avoid) and if ABC (RFC 3465) is 96 * enabled. 97 * 98 * slow start: cwnd <= ssthresh 99 * cong avoid: cwnd > ssthresh 100 * 101 * slow start and ABC (RFC 3465): 102 * Grow cwnd exponentially by the amount of data 103 * ACKed capping the max increment per ACK to 104 * (abc_l_var * maxseg) bytes. 105 * 106 * slow start without ABC (RFC 5681): 107 * Grow cwnd exponentially by maxseg per ACK. 108 * 109 * cong avoid and ABC (RFC 3465): 110 * Grow cwnd linearly by maxseg per RTT for each 111 * cwnd worth of ACKed data. 112 * 113 * cong avoid without ABC (RFC 5681): 114 * Grow cwnd linearly by approximately maxseg per RTT using 115 * maxseg^2 / cwnd per ACK as the increment. 116 * If cwnd > maxseg^2, fix the cwnd increment at 1 byte to 117 * avoid capping cwnd. 118 */ 119 if (cw > CCV(ccv, snd_ssthresh)) { 120 if (V_tcp_do_rfc3465) { 121 if (ccv->flags & CCF_ABC_SENTAWND) 122 ccv->flags &= ~CCF_ABC_SENTAWND; 123 else 124 incr = 0; 125 } else 126 incr = max((incr * incr / cw), 1); 127 } else if (V_tcp_do_rfc3465) { 128 /* 129 * In slow-start with ABC enabled and no RTO in sight? 130 * (Must not use abc_l_var > 1 if slow starting after 131 * an RTO. On RTO, snd_nxt = snd_una, so the 132 * snd_nxt == snd_max check is sufficient to 133 * handle this). 134 * 135 * XXXLAS: Find a way to signal SS after RTO that 136 * doesn't rely on tcpcb vars. 137 */ 138 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max)) 139 incr = min(ccv->bytes_this_ack, 140 ccv->nsegs * V_tcp_abc_l_var * 141 CCV(ccv, t_maxseg)); 142 else 143 incr = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg)); 144 } 145 /* ABC is on by default, so incr equals 0 frequently. */ 146 if (incr > 0) 147 CCV(ccv, snd_cwnd) = min(cw + incr, 148 TCP_MAXWIN << CCV(ccv, snd_scale)); 149 } 150 } 151 152 static void 153 newreno_after_idle(struct cc_var *ccv) 154 { 155 int rw; 156 157 /* 158 * If we've been idle for more than one retransmit timeout the old 159 * congestion window is no longer current and we have to reduce it to 160 * the restart window before we can transmit again. 161 * 162 * The restart window is the initial window or the last CWND, whichever 163 * is smaller. 164 * 165 * This is done to prevent us from flooding the path with a full CWND at 166 * wirespeed, overloading router and switch buffers along the way. 167 * 168 * See RFC5681 Section 4.1. "Restarting Idle Connections". 169 */ 170 if (V_tcp_do_rfc3390) 171 rw = min(4 * CCV(ccv, t_maxseg), 172 max(2 * CCV(ccv, t_maxseg), 4380)); 173 else 174 rw = CCV(ccv, t_maxseg) * 2; 175 176 CCV(ccv, snd_cwnd) = min(rw, CCV(ccv, snd_cwnd)); 177 } 178 179 /* 180 * Perform any necessary tasks before we enter congestion recovery. 181 */ 182 static void 183 newreno_cong_signal(struct cc_var *ccv, uint32_t type) 184 { 185 uint32_t cwin, ssthresh_on_loss; 186 u_int mss; 187 188 cwin = CCV(ccv, snd_cwnd); 189 mss = CCV(ccv, t_maxseg); 190 ssthresh_on_loss = 191 max((CCV(ccv, snd_max) - CCV(ccv, snd_una)) / 2 / mss, 2) 192 * mss; 193 194 /* Catch algos which mistakenly leak private signal types. */ 195 KASSERT((type & CC_SIGPRIVMASK) == 0, 196 ("%s: congestion signal type 0x%08x is private\n", __func__, type)); 197 198 cwin = max(cwin / 2 / mss, 2) * mss; 199 200 switch (type) { 201 case CC_NDUPACK: 202 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) { 203 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 204 CCV(ccv, snd_ssthresh) = ssthresh_on_loss; 205 CCV(ccv, snd_cwnd) = cwin; 206 } 207 ENTER_RECOVERY(CCV(ccv, t_flags)); 208 } 209 break; 210 case CC_ECN: 211 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 212 CCV(ccv, snd_ssthresh) = ssthresh_on_loss; 213 CCV(ccv, snd_cwnd) = cwin; 214 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 215 } 216 break; 217 case CC_RTO: 218 CCV(ccv, snd_ssthresh) = ssthresh_on_loss; 219 CCV(ccv, snd_cwnd) = mss; 220 break; 221 } 222 } 223 224 /* 225 * Perform any necessary tasks before we exit congestion recovery. 226 */ 227 static void 228 newreno_post_recovery(struct cc_var *ccv) 229 { 230 int pipe; 231 pipe = 0; 232 233 if (IN_FASTRECOVERY(CCV(ccv, t_flags))) { 234 /* 235 * Fast recovery will conclude after returning from this 236 * function. Window inflation should have left us with 237 * approximately snd_ssthresh outstanding data. But in case we 238 * would be inclined to send a burst, better to do it via the 239 * slow start mechanism. 240 * 241 * XXXLAS: Find a way to do this without needing curack 242 */ 243 if (V_tcp_do_rfc6675_pipe) 244 pipe = tcp_compute_pipe(ccv->ccvc.tcp); 245 else 246 pipe = CCV(ccv, snd_max) - ccv->curack; 247 248 if (pipe < CCV(ccv, snd_ssthresh)) 249 CCV(ccv, snd_cwnd) = pipe + CCV(ccv, t_maxseg); 250 else 251 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); 252 } 253 } 254 255 256 DECLARE_CC_MODULE(newreno, &newreno_cc_algo); 257