1 /*
2 * Copyright (c) 2013-2018 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 <sys/param.h>
30 #include <sys/systm.h>
31 #include <sys/kernel.h>
32 #include <sys/syslog.h>
33 #include <sys/protosw.h>
34 #include <sys/socketvar.h>
35 #include <sys/kern_control.h>
36 #include <sys/domain.h>
37
38 #include <netinet/in.h>
39 #include <netinet/tcp.h>
40 #include <netinet/tcp_var.h>
41 #include <netinet/tcp_cc.h>
42 #include <mach/sdt.h>
43 #include <libkern/OSAtomic.h>
44
45 static int tcp_cc_debug;
46 SYSCTL_INT(_net_inet_tcp, OID_AUTO, cc_debug, CTLFLAG_RW | CTLFLAG_LOCKED,
47 &tcp_cc_debug, 0, "Enable debug data collection");
48
49 extern struct tcp_cc_algo tcp_cc_newreno;
50 SYSCTL_INT(_net_inet_tcp, OID_AUTO, newreno_sockets,
51 CTLFLAG_RD | CTLFLAG_LOCKED, &tcp_cc_newreno.num_sockets,
52 0, "Number of sockets using newreno");
53
54 extern struct tcp_cc_algo tcp_cc_ledbat;
55 SYSCTL_INT(_net_inet_tcp, OID_AUTO, background_sockets,
56 CTLFLAG_RD | CTLFLAG_LOCKED, &tcp_cc_ledbat.num_sockets,
57 0, "Number of sockets using background transport");
58
59 #if (DEVELOPMENT || DEBUG)
60 SYSCTL_SKMEM_TCP_INT(OID_AUTO, use_ledbat,
61 CTLFLAG_RW | CTLFLAG_LOCKED, int, tcp_use_ledbat, 0,
62 "Use TCP LEDBAT for testing");
63 #else
64 SYSCTL_SKMEM_TCP_INT(OID_AUTO, use_ledbat,
65 CTLFLAG_RD | CTLFLAG_LOCKED, int, tcp_use_ledbat, 0,
66 "Use TCP LEDBAT for testing");
67 #endif /* (DEVELOPMENT || DEBUG) */
68
69 extern struct tcp_cc_algo tcp_cc_cubic;
70 SYSCTL_INT(_net_inet_tcp, OID_AUTO, cubic_sockets,
71 CTLFLAG_RD | CTLFLAG_LOCKED, &tcp_cc_cubic.num_sockets,
72 0, "Number of sockets using cubic");
73
74 SYSCTL_SKMEM_TCP_INT(OID_AUTO, use_newreno,
75 CTLFLAG_RW | CTLFLAG_LOCKED, int, tcp_use_newreno, 0,
76 "Use TCP NewReno by default");
77
78 static int tcp_check_cwnd_nonvalidated = 1;
79 #if (DEBUG || DEVELOPMENT)
80 SYSCTL_INT(_net_inet_tcp, OID_AUTO, cwnd_nonvalidated,
81 CTLFLAG_RW | CTLFLAG_LOCKED, &tcp_check_cwnd_nonvalidated, 0,
82 "Check if congestion window is non-validated");
83 #endif /* (DEBUG || DEVELOPMENT) */
84
85 #define SET_SNDSB_IDEAL_SIZE(sndsb, size) \
86 sndsb->sb_idealsize = min(max(tcp_sendspace, tp->snd_ssthresh), \
87 tcp_autosndbuf_max);
88
89 /* Array containing pointers to currently implemented TCP CC algorithms */
90 struct tcp_cc_algo* tcp_cc_algo_list[TCP_CC_ALGO_COUNT];
91 struct zone *tcp_cc_zone;
92
93 #define TCP_CCDBG_NOUNIT 0xffffffff
94 static kern_ctl_ref tcp_ccdbg_ctlref = NULL;
95 volatile UInt32 tcp_ccdbg_unit = TCP_CCDBG_NOUNIT;
96
97 void tcp_cc_init(void);
98 static void tcp_cc_control_register(void);
99 static errno_t tcp_ccdbg_control_connect(kern_ctl_ref kctl,
100 struct sockaddr_ctl *sac, void **uinfo);
101 static errno_t tcp_ccdbg_control_disconnect(kern_ctl_ref kctl,
102 u_int32_t unit, void *uinfo);
103 static struct tcp_cc_algo tcp_cc_algo_none;
104 /*
105 * Initialize TCP congestion control algorithms.
106 */
107
108 void
tcp_cc_init(void)109 tcp_cc_init(void)
110 {
111 bzero(&tcp_cc_algo_list, sizeof(tcp_cc_algo_list));
112 bzero(&tcp_cc_algo_none, sizeof(tcp_cc_algo_none));
113
114 tcp_cc_algo_list[TCP_CC_ALGO_NONE] = &tcp_cc_algo_none;
115 tcp_cc_algo_list[TCP_CC_ALGO_NEWRENO_INDEX] = &tcp_cc_newreno;
116 tcp_cc_algo_list[TCP_CC_ALGO_BACKGROUND_INDEX] = &tcp_cc_ledbat;
117 tcp_cc_algo_list[TCP_CC_ALGO_CUBIC_INDEX] = &tcp_cc_cubic;
118
119 tcp_cc_control_register();
120 }
121
122 static void
tcp_cc_control_register(void)123 tcp_cc_control_register(void)
124 {
125 struct kern_ctl_reg ccdbg_control;
126 errno_t err;
127
128 bzero(&ccdbg_control, sizeof(ccdbg_control));
129 strlcpy(ccdbg_control.ctl_name, TCP_CC_CONTROL_NAME,
130 sizeof(ccdbg_control.ctl_name));
131 ccdbg_control.ctl_connect = tcp_ccdbg_control_connect;
132 ccdbg_control.ctl_disconnect = tcp_ccdbg_control_disconnect;
133 ccdbg_control.ctl_flags |= CTL_FLAG_PRIVILEGED;
134 ccdbg_control.ctl_flags |= CTL_FLAG_REG_SOCK_STREAM;
135 ccdbg_control.ctl_sendsize = 32 * 1024;
136
137 err = ctl_register(&ccdbg_control, &tcp_ccdbg_ctlref);
138 if (err != 0) {
139 log(LOG_ERR, "failed to register tcp_cc debug control");
140 }
141 }
142
143 /* Allow only one socket to connect at any time for debugging */
144 static errno_t
tcp_ccdbg_control_connect(kern_ctl_ref kctl,struct sockaddr_ctl * sac,void ** uinfo)145 tcp_ccdbg_control_connect(kern_ctl_ref kctl, struct sockaddr_ctl *sac,
146 void **uinfo)
147 {
148 #pragma unused(kctl)
149 #pragma unused(uinfo)
150
151 UInt32 old_value = TCP_CCDBG_NOUNIT;
152 UInt32 new_value = sac->sc_unit;
153
154 if (tcp_ccdbg_unit != old_value) {
155 return EALREADY;
156 }
157
158 if (OSCompareAndSwap(old_value, new_value, &tcp_ccdbg_unit)) {
159 return 0;
160 } else {
161 return EALREADY;
162 }
163 }
164
165 static errno_t
tcp_ccdbg_control_disconnect(kern_ctl_ref kctl,u_int32_t unit,void * uinfo)166 tcp_ccdbg_control_disconnect(kern_ctl_ref kctl, u_int32_t unit, void *uinfo)
167 {
168 #pragma unused(kctl, unit, uinfo)
169
170 if (unit == tcp_ccdbg_unit) {
171 UInt32 old_value = tcp_ccdbg_unit;
172 UInt32 new_value = TCP_CCDBG_NOUNIT;
173 if (tcp_ccdbg_unit == new_value) {
174 return 0;
175 }
176
177 if (!OSCompareAndSwap(old_value, new_value,
178 &tcp_ccdbg_unit)) {
179 log(LOG_DEBUG,
180 "failed to disconnect tcp_cc debug control");
181 }
182 }
183 return 0;
184 }
185
186 inline void
tcp_ccdbg_trace(struct tcpcb * tp,struct tcphdr * th,int32_t event)187 tcp_ccdbg_trace(struct tcpcb *tp, struct tcphdr *th, int32_t event)
188 {
189 #if !CONFIG_DTRACE
190 #pragma unused(th)
191 #endif /* !CONFIG_DTRACE */
192 struct inpcb *inp = tp->t_inpcb;
193
194 if (tcp_cc_debug && tcp_ccdbg_unit > 0) {
195 struct tcp_cc_debug_state dbg_state;
196 struct timespec tv;
197
198 bzero(&dbg_state, sizeof(dbg_state));
199
200 nanotime(&tv);
201 /* Take time in seconds */
202 dbg_state.ccd_tsns = (tv.tv_sec * 1000000000) + tv.tv_nsec;
203 inet_ntop(SOCK_DOM(inp->inp_socket),
204 ((SOCK_DOM(inp->inp_socket) == PF_INET) ?
205 (void *)&inp->inp_laddr.s_addr :
206 (void *)&inp->in6p_laddr), dbg_state.ccd_srcaddr,
207 sizeof(dbg_state.ccd_srcaddr));
208 dbg_state.ccd_srcport = ntohs(inp->inp_lport);
209 inet_ntop(SOCK_DOM(inp->inp_socket),
210 ((SOCK_DOM(inp->inp_socket) == PF_INET) ?
211 (void *)&inp->inp_faddr.s_addr :
212 (void *)&inp->in6p_faddr), dbg_state.ccd_destaddr,
213 sizeof(dbg_state.ccd_destaddr));
214 dbg_state.ccd_destport = ntohs(inp->inp_fport);
215
216 dbg_state.ccd_snd_cwnd = tp->snd_cwnd;
217 dbg_state.ccd_snd_wnd = tp->snd_wnd;
218 dbg_state.ccd_snd_ssthresh = tp->snd_ssthresh;
219 dbg_state.ccd_pipeack = tp->t_pipeack;
220 dbg_state.ccd_rttcur = tp->t_rttcur;
221 dbg_state.ccd_rxtcur = tp->t_rxtcur;
222 dbg_state.ccd_srtt = tp->t_srtt >> TCP_RTT_SHIFT;
223 dbg_state.ccd_event = event;
224 dbg_state.ccd_sndcc = inp->inp_socket->so_snd.sb_cc;
225 dbg_state.ccd_sndhiwat = inp->inp_socket->so_snd.sb_hiwat;
226 dbg_state.ccd_bytes_acked = tp->t_bytes_acked;
227 dbg_state.ccd_cc_index = tp->tcp_cc_index;
228 switch (tp->tcp_cc_index) {
229 case TCP_CC_ALGO_CUBIC_INDEX:
230 dbg_state.u.cubic_state.ccd_last_max =
231 tp->t_ccstate->cub_last_max;
232 dbg_state.u.cubic_state.ccd_tcp_win =
233 tp->t_ccstate->cub_tcp_win;
234 dbg_state.u.cubic_state.ccd_avg_lastmax =
235 tp->t_ccstate->cub_avg_lastmax;
236 dbg_state.u.cubic_state.ccd_mean_deviation =
237 tp->t_ccstate->cub_mean_dev;
238 break;
239 case TCP_CC_ALGO_BACKGROUND_INDEX:
240 dbg_state.u.ledbat_state.led_base_rtt =
241 get_base_rtt(tp);
242 break;
243 default:
244 break;
245 }
246
247 ctl_enqueuedata(tcp_ccdbg_ctlref, tcp_ccdbg_unit,
248 &dbg_state, sizeof(dbg_state), 0);
249 }
250 DTRACE_TCP5(cc, void, NULL, struct inpcb *, inp,
251 struct tcpcb *, tp, struct tcphdr *, th, int32_t, event);
252 }
253
254 void
tcp_cc_resize_sndbuf(struct tcpcb * tp)255 tcp_cc_resize_sndbuf(struct tcpcb *tp)
256 {
257 struct sockbuf *sb;
258 /*
259 * If the send socket buffer size is bigger than ssthresh,
260 * it is time to trim it because we do not want to hold
261 * too many mbufs in the socket buffer
262 */
263 sb = &tp->t_inpcb->inp_socket->so_snd;
264 if (sb->sb_hiwat > tp->snd_ssthresh &&
265 (sb->sb_flags & SB_AUTOSIZE)) {
266 if (sb->sb_idealsize > tp->snd_ssthresh) {
267 SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
268 }
269 sb->sb_flags |= SB_TRIM;
270 }
271 }
272
273 void
tcp_bad_rexmt_fix_sndbuf(struct tcpcb * tp)274 tcp_bad_rexmt_fix_sndbuf(struct tcpcb *tp)
275 {
276 struct sockbuf *sb;
277 sb = &tp->t_inpcb->inp_socket->so_snd;
278 if ((sb->sb_flags & (SB_TRIM | SB_AUTOSIZE)) == (SB_TRIM | SB_AUTOSIZE)) {
279 /*
280 * If there was a retransmission that was not necessary
281 * then the size of socket buffer can be restored to
282 * what it was before
283 */
284 SET_SNDSB_IDEAL_SIZE(sb, tp->snd_ssthresh);
285 if (sb->sb_hiwat <= sb->sb_idealsize) {
286 sbreserve(sb, sb->sb_idealsize);
287 sb->sb_flags &= ~SB_TRIM;
288 }
289 }
290 }
291
292 /*
293 * Calculate initial cwnd according to RFC3390.
294 */
295 void
tcp_cc_cwnd_init_or_reset(struct tcpcb * tp)296 tcp_cc_cwnd_init_or_reset(struct tcpcb *tp)
297 {
298 if (tp->t_flags & TF_LOCAL) {
299 tp->snd_cwnd = tp->t_maxseg * ss_fltsz_local;
300 } else {
301 if (tcp_cubic_minor_fixes) {
302 tp->snd_cwnd = tcp_initial_cwnd(tp);
303 } else {
304 /* initial congestion window according to RFC 3390 */
305 tp->snd_cwnd = min(4 * tp->t_maxseg,
306 max(2 * tp->t_maxseg, TCP_CC_CWND_INIT_BYTES));
307 }
308 }
309 }
310
311 /*
312 * Indicate whether this ack should be delayed.
313 * Here is the explanation for different settings of tcp_delack_enabled:
314 * - when set to 1, the behavior is same as when set to 2. We kept this
315 * for binary compatibility.
316 * - when set to 2, will "ack every other packet"
317 * - if our last ack wasn't a 0-sized window.
318 * - if the peer hasn't sent us a TH_PUSH data packet (radar 3649245).
319 * If TH_PUSH is set, take this as a clue that we need to ACK
320 * with no delay. This helps higher level protocols who
321 * won't send us more data even if the window is open
322 * because their last "segment" hasn't been ACKed
323 * - when set to 3, will do "streaming detection"
324 * - if we receive more than "maxseg_unacked" full packets
325 * in the last 100ms
326 * - if the connection is not in slow-start or idle or
327 * loss/recovery states
328 * - if those criteria aren't met, it will ack every other packet.
329 */
330 int
tcp_cc_delay_ack(struct tcpcb * tp,struct tcphdr * th)331 tcp_cc_delay_ack(struct tcpcb *tp, struct tcphdr *th)
332 {
333 switch (tcp_delack_enabled) {
334 case 1:
335 case 2:
336 if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
337 (th->th_flags & TH_PUSH) == 0 &&
338 (tp->t_unacksegs == 1)) {
339 return 1;
340 }
341 break;
342 case 3:
343 if (tcp_ack_strategy == TCP_ACK_STRATEGY_LEGACY) {
344 if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
345 (th->th_flags & TH_PUSH) == 0 &&
346 ((tp->t_unacksegs == 1) ||
347 ((tp->t_flags & TF_STRETCHACK) &&
348 tp->t_unacksegs < maxseg_unacked))) {
349 return 1;
350 }
351 } else {
352 uint32_t recwin;
353
354 /* Get the receive-window we would announce */
355 recwin = tcp_sbspace(tp);
356 if (recwin > (uint32_t)(TCP_MAXWIN << tp->rcv_scale)) {
357 recwin = (uint32_t)(TCP_MAXWIN << tp->rcv_scale);
358 }
359
360 /* Delay ACK, if:
361 *
362 * 1. We are not sending a zero-window
363 * 2. We are not forcing fast ACKs
364 * 3. We have more than the low-water mark in receive-buffer
365 * 4. The receive-window is not increasing
366 * 5. We have less than or equal of an MSS unacked or
367 * Window actually has been growing larger than the initial value by half of it.
368 * (this makes sure that during ramp-up we ACK every second MSS
369 * until we pass the tcp_recvspace * 1.5-threshold)
370 * 6. We haven't waited for half a BDP
371 *
372 * (a note on 6: The receive-window is
373 * roughly 2 BDP. Thus, recwin / 4 means half a BDP and
374 * thus we enforce an ACK roughly twice per RTT - even
375 * if the app does not read)
376 */
377 if ((tp->t_flags & TF_RXWIN0SENT) == 0 &&
378 tp->t_forced_acks == 0 &&
379 tp->t_inpcb->inp_socket->so_rcv.sb_cc > tp->t_inpcb->inp_socket->so_rcv.sb_lowat &&
380 recwin <= tp->t_last_recwin &&
381 (tp->rcv_nxt - tp->last_ack_sent <= tp->t_maxseg ||
382 recwin > (uint32_t)(tcp_recvspace + (tcp_recvspace >> 1))) &&
383 (tp->rcv_nxt - tp->last_ack_sent) < (recwin >> 2)) {
384 tp->t_stat.acks_delayed++;
385 return 1;
386 }
387 }
388 break;
389 }
390 return 0;
391 }
392
393 void
tcp_cc_allocate_state(struct tcpcb * tp)394 tcp_cc_allocate_state(struct tcpcb *tp)
395 {
396 if ((tp->tcp_cc_index == TCP_CC_ALGO_CUBIC_INDEX ||
397 tp->tcp_cc_index == TCP_CC_ALGO_BACKGROUND_INDEX) &&
398 tp->t_ccstate == NULL) {
399 tp->t_ccstate = (struct tcp_ccstate *)zalloc(tcp_cc_zone);
400
401 /*
402 * If we could not allocate memory for congestion control
403 * state, revert to using TCP NewReno as it does not
404 * require any state
405 */
406 if (tp->t_ccstate == NULL) {
407 tp->tcp_cc_index = TCP_CC_ALGO_NEWRENO_INDEX;
408 } else {
409 bzero(tp->t_ccstate, sizeof(*tp->t_ccstate));
410 }
411 }
412 }
413
414 /*
415 * If stretch ack was disabled automatically on long standing connections,
416 * re-evaluate the situation after 15 minutes to enable it.
417 */
418 #define TCP_STRETCHACK_DISABLE_WIN (15 * 60 * TCP_RETRANSHZ)
419 void
tcp_cc_after_idle_stretchack(struct tcpcb * tp)420 tcp_cc_after_idle_stretchack(struct tcpcb *tp)
421 {
422 int32_t tdiff;
423
424 if (!(tp->t_flagsext & TF_DISABLE_STRETCHACK)) {
425 return;
426 }
427
428 tdiff = timer_diff(tcp_now, 0, tp->rcv_nostrack_ts, 0);
429 if (tdiff < 0) {
430 tdiff = -tdiff;
431 }
432
433 if (tdiff > TCP_STRETCHACK_DISABLE_WIN) {
434 tp->t_flagsext &= ~TF_DISABLE_STRETCHACK;
435 tp->t_stretchack_delayed = 0;
436
437 tcp_reset_stretch_ack(tp);
438 }
439 }
440
441 /*
442 * Detect if the congestion window is non-vlidated according to
443 * draft-ietf-tcpm-newcwv-07
444 */
445
446 inline uint32_t
tcp_cc_is_cwnd_nonvalidated(struct tcpcb * tp)447 tcp_cc_is_cwnd_nonvalidated(struct tcpcb *tp)
448 {
449 struct socket *so = tp->t_inpcb->inp_socket;
450 if (tp->t_pipeack == 0 || tcp_check_cwnd_nonvalidated == 0) {
451 tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
452 return 0;
453 }
454
455 /*
456 * The congestion window is validated if the number of bytes acked
457 * is more than half of the current window or if there is more
458 * data to send in the send socket buffer
459 */
460 if (tp->t_pipeack >= (tp->snd_cwnd >> 1) ||
461 (so != NULL && so->so_snd.sb_cc > tp->snd_cwnd)) {
462 tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
463 } else {
464 tp->t_flagsext |= TF_CWND_NONVALIDATED;
465 }
466 return tp->t_flagsext & TF_CWND_NONVALIDATED;
467 }
468
469 /*
470 * Adjust congestion window in response to congestion in non-validated
471 * phase.
472 */
473 inline void
tcp_cc_adjust_nonvalidated_cwnd(struct tcpcb * tp)474 tcp_cc_adjust_nonvalidated_cwnd(struct tcpcb *tp)
475 {
476 tp->t_pipeack = tcp_get_max_pipeack(tp);
477 tcp_clear_pipeack_state(tp);
478 tp->snd_cwnd = (max(tp->t_pipeack, tp->t_lossflightsize) >> 1);
479 if (tcp_cubic_minor_fixes) {
480 tp->snd_cwnd = max(tp->snd_cwnd, tp->t_maxseg);
481 } else {
482 tp->snd_cwnd = max(tp->snd_cwnd, TCP_CC_CWND_INIT_BYTES);
483 }
484 tp->snd_cwnd += tp->t_maxseg * tcprexmtthresh;
485 tp->t_flagsext &= ~TF_CWND_NONVALIDATED;
486 }
487
488 /*
489 * Return maximum of all the pipeack samples. Since the number of samples
490 * TCP_PIPEACK_SAMPLE_COUNT is 3 at this time, it will be simpler to do
491 * a comparision. We should change ths if the number of samples increases.
492 */
493 inline u_int32_t
tcp_get_max_pipeack(struct tcpcb * tp)494 tcp_get_max_pipeack(struct tcpcb *tp)
495 {
496 u_int32_t max_pipeack = 0;
497 max_pipeack = (tp->t_pipeack_sample[0] > tp->t_pipeack_sample[1]) ?
498 tp->t_pipeack_sample[0] : tp->t_pipeack_sample[1];
499 max_pipeack = (tp->t_pipeack_sample[2] > max_pipeack) ?
500 tp->t_pipeack_sample[2] : max_pipeack;
501
502 return max_pipeack;
503 }
504
505 inline void
tcp_clear_pipeack_state(struct tcpcb * tp)506 tcp_clear_pipeack_state(struct tcpcb *tp)
507 {
508 bzero(tp->t_pipeack_sample, sizeof(tp->t_pipeack_sample));
509 tp->t_pipeack_ind = 0;
510 tp->t_lossflightsize = 0;
511 }
512