1 | /* |
2 | * Copyright (c) 2010-2021 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | /* |
29 | * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1995 |
30 | * The Regents of the University of California. All rights reserved. |
31 | * |
32 | * Redistribution and use in source and binary forms, with or without |
33 | * modification, are permitted provided that the following conditions |
34 | * are met: |
35 | * 1. Redistributions of source code must retain the above copyright |
36 | * notice, this list of conditions and the following disclaimer. |
37 | * 2. Redistributions in binary form must reproduce the above copyright |
38 | * notice, this list of conditions and the following disclaimer in the |
39 | * documentation and/or other materials provided with the distribution. |
40 | * 3. All advertising materials mentioning features or use of this software |
41 | * must display the following acknowledgement: |
42 | * This product includes software developed by the University of |
43 | * California, Berkeley and its contributors. |
44 | * 4. Neither the name of the University nor the names of its contributors |
45 | * may be used to endorse or promote products derived from this software |
46 | * without specific prior written permission. |
47 | * |
48 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
49 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
50 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
51 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
52 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
53 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
54 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
55 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
56 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
57 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
58 | * SUCH DAMAGE. |
59 | * |
60 | * @(#)tcp_input.c 8.12 (Berkeley) 5/24/95 |
61 | * $FreeBSD: src/sys/netinet/tcp_input.c,v 1.107.2.16 2001/08/22 00:59:12 silby Exp $ |
62 | */ |
63 | |
64 | #include "tcp_includes.h" |
65 | |
66 | #include <sys/param.h> |
67 | #include <sys/kernel.h> |
68 | #include <sys/socketvar.h> |
69 | |
70 | #include <net/route.h> |
71 | #include <netinet/in.h> |
72 | #include <netinet/in_systm.h> |
73 | #include <netinet/ip.h> |
74 | #include <netinet/ip6.h> |
75 | #include <netinet/ip_var.h> |
76 | |
77 | int tcp_newreno_init(struct tcpcb *tp); |
78 | int tcp_newreno_cleanup(struct tcpcb *tp); |
79 | void tcp_newreno_cwnd_init_or_reset(struct tcpcb *tp); |
80 | void tcp_newreno_congestion_avd(struct tcpcb *tp, struct tcphdr *th); |
81 | void tcp_newreno_ack_rcvd(struct tcpcb *tp, struct tcphdr *th); |
82 | void tcp_newreno_pre_fr(struct tcpcb *tp); |
83 | void tcp_newreno_post_fr(struct tcpcb *tp, struct tcphdr *th); |
84 | void tcp_newreno_after_idle(struct tcpcb *tp); |
85 | void tcp_newreno_after_timeout(struct tcpcb *tp); |
86 | int tcp_newreno_delay_ack(struct tcpcb *tp, struct tcphdr *th); |
87 | void tcp_newreno_switch_cc(struct tcpcb *tp); |
88 | |
89 | struct tcp_cc_algo tcp_cc_newreno = { |
90 | .name = "newreno" , |
91 | .init = tcp_newreno_init, |
92 | .cleanup = tcp_newreno_cleanup, |
93 | .cwnd_init = tcp_newreno_cwnd_init_or_reset, |
94 | .congestion_avd = tcp_newreno_congestion_avd, |
95 | .ack_rcvd = tcp_newreno_ack_rcvd, |
96 | .pre_fr = tcp_newreno_pre_fr, |
97 | .post_fr = tcp_newreno_post_fr, |
98 | .after_idle = tcp_newreno_cwnd_init_or_reset, |
99 | .after_timeout = tcp_newreno_after_timeout, |
100 | .delay_ack = tcp_newreno_delay_ack, |
101 | .switch_to = tcp_newreno_switch_cc |
102 | }; |
103 | |
104 | int |
105 | tcp_newreno_init(struct tcpcb *tp) |
106 | { |
107 | #pragma unused(tp) |
108 | os_atomic_inc(&tcp_cc_newreno.num_sockets, relaxed); |
109 | return 0; |
110 | } |
111 | |
112 | int |
113 | tcp_newreno_cleanup(struct tcpcb *tp) |
114 | { |
115 | #pragma unused(tp) |
116 | os_atomic_dec(&tcp_cc_newreno.num_sockets, relaxed); |
117 | return 0; |
118 | } |
119 | |
120 | /* Initialize the congestion window for a connection or |
121 | * handles connections that have been idle for |
122 | * some time. In this state, no acks are |
123 | * expected to clock out any data we send -- |
124 | * slow start to get ack "clock" running again. |
125 | * |
126 | * Set the slow-start flight size depending on whether |
127 | * this is a local network or not. |
128 | */ |
129 | void |
130 | tcp_newreno_cwnd_init_or_reset(struct tcpcb *tp) |
131 | { |
132 | tcp_cc_cwnd_init_or_reset(tp); |
133 | } |
134 | |
135 | |
136 | /* Function to handle an in-sequence ack during congestion avoidance phase. |
137 | * This will get called from header prediction code. |
138 | */ |
139 | void |
140 | tcp_newreno_congestion_avd(struct tcpcb *tp, struct tcphdr *th) |
141 | { |
142 | uint32_t acked = 0; |
143 | acked = BYTES_ACKED(th, tp); |
144 | /* |
145 | * Grow the congestion window, if the |
146 | * connection is cwnd bound. |
147 | */ |
148 | if (tp->snd_cwnd < tp->snd_wnd) { |
149 | tp->t_bytes_acked += acked; |
150 | if (tp->t_bytes_acked > tp->snd_cwnd) { |
151 | tp->t_bytes_acked -= tp->snd_cwnd; |
152 | tp->snd_cwnd += tp->t_maxseg; |
153 | } |
154 | } |
155 | } |
156 | /* Function to process an ack. |
157 | */ |
158 | void |
159 | tcp_newreno_ack_rcvd(struct tcpcb *tp, struct tcphdr *th) |
160 | { |
161 | /* |
162 | * RFC 3465 - Appropriate Byte Counting. |
163 | * |
164 | * If the window is currently less than ssthresh, |
165 | * open the window by the number of bytes ACKed by |
166 | * the last ACK, however clamp the window increase |
167 | * to an upper limit "L". |
168 | * |
169 | * In congestion avoidance phase, open the window by |
170 | * one segment each time "bytes_acked" grows to be |
171 | * greater than or equal to the congestion window. |
172 | */ |
173 | |
174 | uint32_t cw = tp->snd_cwnd; |
175 | uint32_t incr = tp->t_maxseg; |
176 | uint32_t acked = 0; |
177 | |
178 | acked = BYTES_ACKED(th, tp); |
179 | if (cw >= tp->snd_ssthresh) { |
180 | tp->t_bytes_acked += acked; |
181 | if (tp->t_bytes_acked >= cw) { |
182 | /* Time to increase the window. */ |
183 | tp->t_bytes_acked -= cw; |
184 | } else { |
185 | /* No need to increase yet. */ |
186 | incr = 0; |
187 | } |
188 | } else { |
189 | /* |
190 | * If the user explicitly enables RFC3465 |
191 | * use 2*SMSS for the "L" param. Otherwise |
192 | * use the more conservative 1*SMSS. |
193 | * |
194 | * (See RFC 3465 2.3 Choosing the Limit) |
195 | */ |
196 | uint32_t abc_lim; |
197 | abc_lim = (tp->snd_nxt == tp->snd_max) ? incr * 2 : incr; |
198 | |
199 | incr = ulmin(a: acked, b: abc_lim); |
200 | } |
201 | tp->snd_cwnd = min(a: cw + incr, TCP_MAXWIN << tp->snd_scale); |
202 | } |
203 | |
204 | void |
205 | tcp_newreno_pre_fr(struct tcpcb *tp) |
206 | { |
207 | uint32_t win; |
208 | |
209 | win = min(a: tp->snd_wnd, b: tp->snd_cwnd) / |
210 | 2 / tp->t_maxseg; |
211 | if (win < 2) { |
212 | win = 2; |
213 | } |
214 | tp->snd_ssthresh = win * tp->t_maxseg; |
215 | tcp_cc_resize_sndbuf(tp); |
216 | } |
217 | |
218 | void |
219 | tcp_newreno_post_fr(struct tcpcb *tp, struct tcphdr *th) |
220 | { |
221 | int32_t ss; |
222 | |
223 | if (th) { |
224 | ss = tp->snd_max - th->th_ack; |
225 | } else { |
226 | ss = tp->snd_max - tp->snd_una; |
227 | } |
228 | |
229 | /* |
230 | * Complete ack. Inflate the congestion window to |
231 | * ssthresh and exit fast recovery. |
232 | * |
233 | * Window inflation should have left us with approx. |
234 | * snd_ssthresh outstanding data. But in case we |
235 | * would be inclined to send a burst, better to do |
236 | * it via the slow start mechanism. |
237 | * |
238 | * If the flight size is zero, then make congestion |
239 | * window to be worth at least 2 segments to avoid |
240 | * delayed acknowledgement (draft-ietf-tcpm-rfc3782-bis-05). |
241 | */ |
242 | if (ss < (int32_t)tp->snd_ssthresh) { |
243 | tp->snd_cwnd = max(a: ss, b: tp->t_maxseg) + tp->t_maxseg; |
244 | } else { |
245 | tp->snd_cwnd = tp->snd_ssthresh; |
246 | } |
247 | tp->t_bytes_acked = 0; |
248 | } |
249 | |
250 | /* Function to change the congestion window when the retransmit |
251 | * timer fires. |
252 | */ |
253 | void |
254 | tcp_newreno_after_timeout(struct tcpcb *tp) |
255 | { |
256 | /* |
257 | * Close the congestion window down to one segment |
258 | * (we'll open it by one segment for each ack we get). |
259 | * Since we probably have a window's worth of unacked |
260 | * data accumulated, this "slow start" keeps us from |
261 | * dumping all that data as back-to-back packets (which |
262 | * might overwhelm an intermediate gateway). |
263 | * |
264 | * There are two phases to the opening: Initially we |
265 | * open by one mss on each ack. This makes the window |
266 | * size increase exponentially with time. If the |
267 | * window is larger than the path can handle, this |
268 | * exponential growth results in dropped packet(s) |
269 | * almost immediately. To get more time between |
270 | * drops but still "push" the network to take advantage |
271 | * of improving conditions, we switch from exponential |
272 | * to linear window opening at some threshhold size. |
273 | * For a threshhold, we use half the current window |
274 | * size, truncated to a multiple of the mss. |
275 | * |
276 | * (the minimum cwnd that will give us exponential |
277 | * growth is 2 mss. We don't allow the threshhold |
278 | * to go below this.) |
279 | */ |
280 | if (tp->t_state >= TCPS_ESTABLISHED) { |
281 | u_int win = min(a: tp->snd_wnd, b: tp->snd_cwnd) / 2 / tp->t_maxseg; |
282 | if (win < 2) { |
283 | win = 2; |
284 | } |
285 | tp->snd_ssthresh = win * tp->t_maxseg; |
286 | |
287 | tp->snd_cwnd = tp->t_maxseg; |
288 | tcp_cc_resize_sndbuf(tp); |
289 | } |
290 | } |
291 | |
292 | /* |
293 | * Indicate whether this ack should be delayed. |
294 | * We can delay the ack if: |
295 | * - delayed acks are enabled and set to 1, same as when value is set to 2. |
296 | * We kept this for binary compatibility. |
297 | * - delayed acks are enabled and set to 2, will "ack every other packet" |
298 | * - if our last ack wasn't a 0-sized window. |
299 | * - if the peer hasn't sent us a TH_PUSH data packet (this solves 3649245). |
300 | * If TH_PUSH is set, take this as a clue that we need to ACK |
301 | * with no delay. This helps higher level protocols who won't send |
302 | * us more data even if the window is open because their |
303 | * last "segment" hasn't been ACKed |
304 | * - delayed acks are enabled and set to 3, will do "streaming detection" |
305 | * (see the comment in tcp_input.c) and |
306 | * - if we receive more than "maxseg_unacked" full packets in the last 100ms |
307 | * - if the connection is not in slow-start or idle or loss/recovery states |
308 | * - if those criteria aren't met, it will ack every other packet. |
309 | */ |
310 | |
311 | int |
312 | tcp_newreno_delay_ack(struct tcpcb *tp, struct tcphdr *th) |
313 | { |
314 | return tcp_cc_delay_ack(tp, th); |
315 | } |
316 | |
317 | /* Switch to newreno from a different CC. If the connection is in |
318 | * congestion avoidance state, it can continue to use the current |
319 | * congestion window because it is going to be conservative. But |
320 | * if the connection is in slow-start, we will halve the congestion |
321 | * window and let newreno work from there. |
322 | */ |
323 | void |
324 | tcp_newreno_switch_cc(struct tcpcb *tp) |
325 | { |
326 | uint32_t cwnd = min(a: tp->snd_wnd, b: tp->snd_cwnd); |
327 | if (tp->snd_cwnd >= tp->snd_ssthresh) { |
328 | cwnd = cwnd / tp->t_maxseg; |
329 | } else { |
330 | cwnd = cwnd / 2 / tp->t_maxseg; |
331 | } |
332 | tp->snd_cwnd = max(a: tcp_initial_cwnd(tp), b: cwnd * tp->t_maxseg); |
333 | |
334 | /* Start counting bytes for RFC 3465 again */ |
335 | tp->t_bytes_acked = 0; |
336 | |
337 | os_atomic_inc(&tcp_cc_newreno.num_sockets, relaxed); |
338 | } |
339 | |