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