1 /*
2 * Copyright (c) 2013-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 #include "tcp_includes.h"
30
31 #include <sys/param.h>
32 #include <sys/kernel.h>
33 #include <sys/syslog.h>
34 #include <sys/kern_control.h>
35 #include <sys/domain.h>
36
37 #include <netinet/in.h>
38 #include <mach/sdt.h>
39 #include <libkern/OSAtomic.h>
40
41 #include <libkern/OSTypes.h>
42
43 extern struct tcp_cc_algo tcp_cc_newreno;
44 extern struct tcp_cc_algo tcp_cc_ledbat;
45 extern struct tcp_cc_algo tcp_cc_cubic;
46 extern struct tcp_cc_algo tcp_cc_prague;
47
48 #define SET_SNDSB_IDEAL_SIZE(sndsb, size) \
49 sndsb->sb_idealsize = min(max(tcp_sendspace, tp->snd_ssthresh), \
50 tcp_autosndbuf_max);
51
52 /* Array containing pointers to currently implemented TCP CC algorithms */
53 struct tcp_cc_algo* tcp_cc_algo_list[TCP_CC_ALGO_COUNT];
54
55 static struct tcp_cc_algo tcp_cc_algo_none;
56 /*
57 * Initialize TCP congestion control algorithms.
58 */
59
60 void
tcp_cc_init(void)61 tcp_cc_init(void)
62 {
63 bzero(&tcp_cc_algo_list, sizeof(tcp_cc_algo_list));
64 bzero(&tcp_cc_algo_none, sizeof(tcp_cc_algo_none));
65
66 tcp_cc_algo_list[TCP_CC_ALGO_NONE] = &tcp_cc_algo_none;
67 tcp_cc_algo_list[TCP_CC_ALGO_NEWRENO_INDEX] = &tcp_cc_newreno;
68 tcp_cc_algo_list[TCP_CC_ALGO_BACKGROUND_INDEX] = &tcp_cc_ledbat;
69 tcp_cc_algo_list[TCP_CC_ALGO_CUBIC_INDEX] = &tcp_cc_cubic;
70 tcp_cc_algo_list[TCP_CC_ALGO_PRAGUE_INDEX] = &tcp_cc_prague;
71
72 tcp_ccdbg_control_register();
73 }
74
75 void
tcp_cc_resize_sndbuf(struct tcpcb * tp)76 tcp_cc_resize_sndbuf(struct tcpcb *tp)
77 {
78 struct sockbuf *sb;
79 /*
80 * If the send socket buffer size is bigger than ssthresh,
81 * it is time to trim it because we do not want to hold
82 * too many mbufs in the socket buffer
83 */
84 sb = &tp->t_inpcb->inp_socket->so_snd;
85 if (sb->sb_hiwat > tp->snd_ssthresh &&
86 (sb->sb_flags & SB_AUTOSIZE)) {
87 if (sb->sb_idealsize > tp->snd_ssthresh) {
88 SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
89 }
90 sb->sb_flags |= SB_TRIM;
91 }
92 }
93
94 void
tcp_bad_rexmt_fix_sndbuf(struct tcpcb * tp)95 tcp_bad_rexmt_fix_sndbuf(struct tcpcb *tp)
96 {
97 struct sockbuf *sb;
98 sb = &tp->t_inpcb->inp_socket->so_snd;
99 if ((sb->sb_flags & (SB_TRIM | SB_AUTOSIZE)) == (SB_TRIM | SB_AUTOSIZE)) {
100 /*
101 * If there was a retransmission that was not necessary
102 * then the size of socket buffer can be restored to
103 * what it was before
104 */
105 SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
106 if (sb->sb_hiwat <= sb->sb_idealsize) {
107 sbreserve(sb, sb->sb_idealsize);
108 sb->sb_flags &= ~SB_TRIM;
109 }
110 }
111 }
112
113 /*
114 * Calculate initial cwnd according to RFC3390.
115 */
116 void
tcp_cc_cwnd_init_or_reset(struct tcpcb * tp)117 tcp_cc_cwnd_init_or_reset(struct tcpcb *tp)
118 {
119 tp->snd_cwnd = tcp_initial_cwnd(tp);
120 }
121
122 /*
123 * Indicate whether this ack should be delayed.
124 * Here is the explanation for different settings of tcp_delack_enabled:
125 * - when set to 1, the behavior is same as when set to 2. We kept this
126 * for binary compatibility.
127 * - when set to 2, will "ack every other packet"
128 * - if our last ack wasn't a 0-sized window.
129 * - if the peer hasn't sent us a TH_PUSH data packet (radar 3649245).
130 * If TH_PUSH is set, take this as a clue that we need to ACK
131 * with no delay. This helps higher level protocols who
132 * won't send us more data even if the window is open
133 * because their last "segment" hasn't been ACKed
134 * - when set to 3, will do "streaming detection"
135 * - if we receive more than "maxseg_unacked" full packets
136 * in the last 100ms
137 * - if the connection is not in slow-start or idle or
138 * loss/recovery states
139 * - if those criteria aren't met, it will ack every other packet.
140 */
141 int
tcp_cc_delay_ack(struct tcpcb * tp,struct tcphdr * th)142 tcp_cc_delay_ack(struct tcpcb *tp, struct tcphdr *th)
143 {
144 switch (tcp_delack_enabled) {
145 case 1:
146 case 2:
147 if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
148 (th->th_flags & TH_PUSH) == 0 &&
149 (tp->t_unacksegs == 1)) {
150 return 1;
151 }
152 break;
153 case 3:
154 {
155 uint32_t recwin;
156
157 /* Get the receive-window we would announce */
158 recwin = tcp_sbspace(tp);
159 if (recwin > (uint32_t)(TCP_MAXWIN << tp->rcv_scale)) {
160 recwin = (uint32_t)(TCP_MAXWIN << tp->rcv_scale);
161 }
162
163 if ((tp->t_flagsext & TF_QUICKACK) &&
164 tp->rcv_nxt - tp->last_ack_sent <= tp->t_maxseg) {
165 return 0;
166 }
167
168 /* Delay ACK, if:
169 *
170 * 1. We are not sending a zero-window
171 * 2. We are not forcing fast ACKs
172 * 3. We have more than the low-water mark in receive-buffer
173 * 4. The receive-window is not increasing
174 * 5. We have less than or equal of an MSS unacked or
175 * Window actually has been growing larger than the initial value by half of it.
176 * (this makes sure that during ramp-up we ACK every second MSS
177 * until we pass the tcp_recvspace * 1.5-threshold)
178 * 6. We haven't waited for half a BDP
179 * 7. The amount of unacked data is less than the maximum ACK-burst (256 MSS)
180 * We try to avoid having the sender end up hitting huge ACK-ranges.
181 *
182 * (a note on 6: The receive-window is
183 * roughly 2 BDP. Thus, recwin / 4 means half a BDP and
184 * thus we enforce an ACK roughly twice per RTT - even
185 * if the app does not read)
186 */
187 if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
188 tp->t_forced_acks == 0 &&
189 tp->t_inpcb->inp_socket->so_rcv.sb_cc > tp->t_inpcb->inp_socket->so_rcv.sb_lowat &&
190 recwin <= tp->t_last_recwin &&
191 (tp->rcv_nxt - tp->last_ack_sent <= tp->t_maxseg ||
192 recwin > (uint32_t)(tcp_recvspace + (tcp_recvspace >> 1))) &&
193 (tp->rcv_nxt - tp->last_ack_sent) < (recwin >> 2) &&
194 (tp->rcv_nxt - tp->last_ack_sent) < 256 * tp->t_maxseg) {
195 tp->t_stat.acks_delayed++;
196 return 1;
197 }
198 }
199 break;
200 }
201 return 0;
202 }
203
204 void
tcp_cc_allocate_state(struct tcpcb * tp)205 tcp_cc_allocate_state(struct tcpcb *tp)
206 {
207 if ((tp->tcp_cc_index == TCP_CC_ALGO_CUBIC_INDEX ||
208 tp->tcp_cc_index == TCP_CC_ALGO_PRAGUE_INDEX ||
209 tp->tcp_cc_index == TCP_CC_ALGO_BACKGROUND_INDEX) &&
210 tp->t_ccstate == NULL) {
211 tp->t_ccstate = &tp->_t_ccstate;
212
213 bzero(tp->t_ccstate, sizeof(*tp->t_ccstate));
214 }
215 }
216
217 /*
218 * Detect if the congestion window is non-validated according to
219 * draft-ietf-tcpm-newcwv-07
220 */
221 inline uint32_t
tcp_cc_is_cwnd_nonvalidated(struct tcpcb * tp)222 tcp_cc_is_cwnd_nonvalidated(struct tcpcb *tp)
223 {
224 struct socket *so = tp->t_inpcb->inp_socket;
225
226 if (tp->t_inpcb->inp_max_pacing_rate != UINT64_MAX) {
227 uint64_t rate;
228
229 rate = tcp_compute_measured_rate(tp);
230
231 /*
232 * Multiply by 2 because we want some amount of standing queue
233 * in the AQM
234 */
235 if (tp->t_inpcb->inp_max_pacing_rate < (rate >> 1)) {
236 return 1;
237 }
238 }
239
240 if (tp->t_pipeack == 0) {
241 tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
242 return 0;
243 }
244
245 /*
246 * The congestion window is validated if the number of bytes acked
247 * is more than half of the current window or if there is more
248 * data to send in the send socket buffer
249 */
250 if (tp->t_pipeack >= (tp->snd_cwnd >> 1) ||
251 (so != NULL && so->so_snd.sb_cc > tp->snd_cwnd)) {
252 tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
253 } else {
254 tp->t_flagsext |= TF_CWND_NONVALIDATED;
255 }
256
257 return tp->t_flagsext & TF_CWND_NONVALIDATED;
258 }
259
260 /*
261 * Adjust congestion window in response to congestion in non-validated
262 * phase.
263 */
264 inline void
tcp_cc_adjust_nonvalidated_cwnd(struct tcpcb * tp)265 tcp_cc_adjust_nonvalidated_cwnd(struct tcpcb *tp)
266 {
267 tp->t_pipeack = tcp_get_max_pipeack(tp);
268 tcp_clear_pipeack_state(tp);
269 tp->snd_cwnd = (max(tp->t_pipeack, tp->t_lossflightsize) >> 1);
270 tp->snd_cwnd = max(tp->snd_cwnd, tp->t_maxseg);
271 tp->snd_cwnd += tp->t_maxseg * tcprexmtthresh;
272 tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
273 }
274
275 /*
276 * Return maximum of all the pipeack samples. Since the number of samples
277 * TCP_PIPEACK_SAMPLE_COUNT is 3 at this time, it will be simpler to do
278 * a comparision. We should change ths if the number of samples increases.
279 */
280 inline uint32_t
tcp_get_max_pipeack(struct tcpcb * tp)281 tcp_get_max_pipeack(struct tcpcb *tp)
282 {
283 uint32_t max_pipeack = 0;
284 max_pipeack = (tp->t_pipeack_sample[0] > tp->t_pipeack_sample[1]) ?
285 tp->t_pipeack_sample[0] : tp->t_pipeack_sample[1];
286 max_pipeack = (tp->t_pipeack_sample[2] > max_pipeack) ?
287 tp->t_pipeack_sample[2] : max_pipeack;
288
289 return max_pipeack;
290 }
291
292 inline void
tcp_clear_pipeack_state(struct tcpcb * tp)293 tcp_clear_pipeack_state(struct tcpcb *tp)
294 {
295 bzero(tp->t_pipeack_sample, sizeof(tp->t_pipeack_sample));
296 tp->t_pipeack_ind = 0;
297 tp->t_lossflightsize = 0;
298 }
299